FIFO Page Replacement

• The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm.
• A FIFO replacement algorithm associates with each page the time when that page was brought into memory.
• When a page must be replaced, the oldest page is chosen.
• For our example reference string, our three frames are initially empty.

  Figure 9.12: FIFO page-replacement algorithm.

  
  • The first three references (7, 0, 1) cause page faults and are brought into these empty frames.
  • The next reference (2) replaces page 7, because page 7 was brought in first.
  • Since 0 is the next reference and 0 is already in memory, we have no fault for this reference.
  • The first reference to 3 results in replacement of page 0, since it is now first in line.
  • Because of this replacement, the next reference, to 0, will fault.
  • Page 1 is then replaced by page O. This process continues and there are 15 faults altogether.
• The FIFO page-replacement algorithm is easy to understand and program. However, its performance is not always good.
• On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed.
• On the other hand, it could contain a heavily used variable that was initialized early and is in constant use.
• Notice that, even if we select for replacement a page that is in active use, everything still works correctly.
  • After we replace an active page with a new one, a fault occurs almost immediately to retrieve the active page.
  • Some other page will need to be replaced to bring the active page back into memory.
  • Thus, a bad replacement choice increases the page-fault rate and slows process execution.
  • It does not cause incorrect execution.