Optimal Page Replacement

• An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms (called OPT or MIN). It is simply this:

  Replace the page that will not be used
  for the longest period of time.
  

• Use of this page-replacement algorithm guarantees the lowest possible page-fault rate for a fixed number of frames.
• For example, on our sample reference string, the optimal page-replacement algorithm would yield nine page faults (see Fig. 9.13).

  Figure 9.13: Optimal page-replacement algorithm.

  
  • The first three references cause faults that fill the three empty frames.
  • The reference to page 2 replaces page 7, because 7 will not be used until reference 18,
  • whereas page 0 will be used at 5, and page 1 at 14.
  • The reference to page 3 replaces page 1, as page 1 will be the last of the three pages in memory to be referenced again.
• With only nine page faults, optimal replacement is much better than a FIFO algorithm, which resulted in fifteen faults.
• If we ignore the first three, which all algorithms must suffer, then optimal replacement is twice as good as FIFO replacement.
• Unfortunately, the optimal page-replacement algorithm is difficult to implement, because it requires future knowledge of the reference string (similar situation with the SJF CPU-scheduling algorithm).
• As a result, the optimal algorithm is used mainly for comparison studies.