FIFO Page replacement Algorithm in Python

FIFO in OS

FIFO Page Replacement Algorithm in Python

FIFO is an acronym for First in First Out in the case of an operating system. The concept is a page replacement technique used to switch data to and from and the main memory. The technique replaces the page from the queue which was first inserted. The operating system uses this concept to switch memory chunks, also known as the pages from the secondary memory to the main memory.

The approach is implemented in every operating system with the help of an algorithm. Such an algorithm is known as the scheduling algorithm and is used to assign processing time to every process which is in the waiting state.

Program in Python

Run
# Python3 implementation of FIFO page
# replacement in Operating Systems.
from queue import Queue


# Function to find page faults using FIFO
def pageFaults(incomingStream, n, frames):
    print("Incoming \t pages")
    # Using Hashset to quickly check if a given
    # incoming stream item in set or not
    s = set()

    # Queue created to store pages in FIFO manner
    # since set will not store order or entry
    # we will use queue to note order of entry of incoming page
    queue = Queue()

    page_faults = 0
    for i in range(n):

        # if set has lesser item than frames
        # i.e. set can hold more items
        if len(s) < frames:

            # If incoming item is not present, add to set
            if incomingStream[i] not in s:
                s.add(incomingStream[i])

                # increment page fault 
                page_faults += 1

                # Push the incoming page into the queue
                queue.put(incomingStream[i])

        # If the set is full then we need to do page replacement
        # in FIFO manner that is remove first item from both
        # set and queue then insert incoming page
        else:

            # If incoming item is not present
            if incomingStream[i] not in s:
                # remove the first page from the queue
                val = queue.queue[0]

                queue.get()

                # Remove from set
                s.remove(val)

                # insert incoming page to set
                s.add(incomingStream[i])

                # push incoming page to queue
                queue.put(incomingStream[i])

                # Increment page faults 
                page_faults += 1

        print(incomingStream[i], end="\t\t")
        for q_item in queue.queue:
            print(q_item, end="\t")

        print()
    return page_faults


# Driver code
incomingStream = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1]
n = len(incomingStream)
frames = 3
page_faults = pageFaults(incomingStream, n, frames)
hits = n - page_faults

print("\nPage Faults: " + str(page_faults))
print("Hit: " + str(hits))

Output –

Incoming 	pages
7		7	
0		7	0	
1		7	0	1	
2		0	1	2	
0		0	1	2	
3		1	2	3	
0		2	3	0	
4		3	0	4	
2		0	4	2	
3		4	2	3	
0		2	3	0	
3		2	3	0	
2		2	3	0	
1		3	0	1	

Page Faults: 11
Hit: 3

Other pages

  1. Page Replacement Algorithms
    1. LRU – C | C++ | Java | Python
    2. FIFO – C | C++ | Java | Python
    3. Optimal Page Replacement algorithm – C | C++ | Java | Python