• FIFO is a simplest page replacement algorithm.
  • In this algorithm arrival time of the page into the memory is recorded.
  • When there are no free frames available in the memory and a page must be replaced, the oldest page is chosen to be replaced with new page.
  • In other words, the first or earliest page that was loaded into the memory will be selected for replacement.
  • FIFO algorithm can be implemented by creating a FIFO queue to store all pages in memory.
  • We replace the page from the top of the FIFO queue. When a page is brought into memory, it will be inserted at the end of the FIFO queue.
  • In our example reference string (7, 0, 1) the three frames are empty.
  • The first three reference page generates page fault and brought into memory.
  • The next page reference is page 2. Now we have no free frame available to load this page into memory. So we will replace page 7 with page 2 because page 7 was the first page loaded in memory.
  • Since 0 is the next page reference but as it is already available in memory, it does not generate any page fault.
  • Similarly page 3 will replace page 0 and so on.

Example:

  • Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
  • No. of frames: 3

FIFO Page Replacement Algorithm

  • Total No. of page fault in FIFO is 15.
  • FIFO page replacement algorithm is easy to understand and program but its performance is not good.
  • It has the higher level of page fault than other method.