FIFO Page replacement Algorithm in Python
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.
- Read Also – FIFO algorithm in C++
Program in Python
# 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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment