LRU Page Replacement

• The key distinction between the FIFO and OPT algorithms (other than looking backward versus forward in time) is that
  • the FIFO algorithm uses the time when a page was brought into memory,
  • whereas the OPT algorithm uses the time when a page is to be used.
• If we use the recent past as an approximation of the near future, then we can replace the page that has not been used for the longest period of time (see Fig. 14).

  Figure 14: LRU page-replacement algorithm.

  
• This approach is the least-recently-used (LRU) algorithm. The result of applying LRU replacement to our example reference string is shown in Fig. 14. The LRU algorithm produces 12 faults.
  • Notice that the first 5 faults are the same as those for optimal replacement.
  • When the reference to page 4 occurs, however, LRU replacement sees that, of the three frames in memory, page 2 was used least recently.
  • Thus, the LRU algorithm replaces page 2, not knowing that page 2 is about to be used.
  • When it then faults for page 2, the LRU algorithm replaces page 3, since it is now the least recently used of the three pages in memory.
• Despite these problems, LRU replacement with 12 faults is much better than FIFO replacement with 15.