Page Replacement

1. What Is It?

Page-replacement algorithms are similar to cache-eviction policies. The former solve a capacity problem, while the latter solve a speed problem.

• Cache-eviction policy: memory can be viewed as a cache for disk. Data that will be used should be kept in memory, and data that will not be used should be moved out of memory.
• Page-replacement algorithm: disk can be viewed as auxiliary space for memory. Data that will be used should be loaded into memory, and data that will not be used should be moved back to secondary storage.
  • The main goal is to minimize the page-fault rate.

2. Page-Replacement Algorithms

2.1. Optimal Page Replacement (OPT)

Each time, choose for eviction the page that will never be used again, or that will not be accessed for the longest time.

2.2. First-In First-Out (FIFO)

Each time, the page selected for eviction is the page that entered memory earliest.

2.3. Least Frequently Used (LFU)

2.4. Least Recently Used (LRU)

Each time, evict the page that has gone unused for the longest recent period.

3. References