Skip to content

Latest commit

 

History

History
51 lines (33 loc) · 2.47 KB

README.md

File metadata and controls

51 lines (33 loc) · 2.47 KB
Raw

Program for FIFO page-replacement algorithm

solution raw output

The first-in, first-out (FIFO) page replacement algorithm is a low-overhead algorithm that requires little book keeping on the part of the operating system.

The idea is obvious from the name – the operating system keeps track of all the pages in memory in a queue, with the most recent arrival at the back, and the oldest arrival in front.

When a page needs to be replaced, the page at the front of the queue (the oldest page) is selected.

Implementation – Let capacity be the number of pages that memory can hold. Let set be the current set of pages in memory.

  • Start traversing the pages :

    • If set holds less pages than capacity.
      • Check if current page is present in set
        • If not :
          • Remove the first page from the queue as it was the first to be entered in the memory
          • Replace the first page in the queue with the current page in the string.
          • Simultaneously maintain the pages in the queue to perform FIFO.

  • Return page faults.

While FIFO is cheap and intuitive, it performs poorly in practical application. Thus, it is rarely used in its unmodified form. This algorithm experiences Bélády's anomaly.

In simple words, on a page fault, the frame that has been in memory the longest is replaced.

FIFO is a conservative algorithm, so it is -competitive.

Output

output_img

Reference