Page Replacement Algorithms

Introduction

When physical memory is full and a new page must be loaded, the operating system must decide which existing page to evict. This decision is critical — evict the wrong page and you will need it back immediately, causing another expensive page fault. Choose wisely and the evicted page may never be needed again. Page replacement algorithms are the strategies for making this choice.

Think of it like a bookshelf that holds only 4 books. When you need a fifth book, one must go back to storage. Which one do you remove? The one you just used (probably a bad choice)? The one you have not touched in weeks (probably safe)? The one you know you will not need for the longest time (optimal but requires fortune-telling)?

FIFO (First In, First Out)

The simplest algorithm: evict the page that has been in memory the longest.

Example: 3 frames, reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

Belady's Anomaly: Surprisingly, FIFO can produce MORE page faults with MORE frames. Adding memory can actually hurt performance with FIFO (this does not happen with LRU or Optimal).

Optimal Page Replacement (OPT)

Replace the page that will not be used for the longest time in the future. This is provably optimal (minimum possible faults) but impossible to implement in practice since it requires knowledge of future references.

Same example: 3 frames, reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

OPT is used as a benchmark — if your algorithm gets close to OPT's fault count, it is good.

LRU (Least Recently Used)

Replace the page that has not been used for the longest time in the PAST. The rationale: if you have not used it recently, you probably will not need it soon (temporal locality).

LRU approximates OPT by using past behavior to predict future behavior.

Same example with LRU:

LRU Implementation

True LRU is expensive to implement in hardware:

Counter method: Each page table entry has a timestamp. On every access, store the current clock value. To replace, scan all entries for the smallest timestamp. Problem: requires searching all entries and updating on every access.

Stack method: Maintain a stack of page numbers. On each reference, move that page to the top. The bottom of the stack is always the LRU page. Problem: updating the stack on every memory access is expensive.

LRU Approximation: Clock Algorithm (Second Chance)

Since true LRU is too expensive, most real systems use approximations. The Clock Algorithm (Second Chance) is the most popular:

Each page has a reference bit set by hardware whenever the page is accessed. The algorithm uses a circular pointer (like a clock hand):

Pages that are frequently accessed always have their reference bit set (getting cleared and re-set repeatedly), so they get many "second chances" and are never evicted. Pages that are not accessed have their bit stay at 0 and are evicted.

Comparison

Real-World Analogy

Page replacement is like managing a small closet. FIFO removes whatever you put in longest ago (even if you wore it yesterday). Optimal removes whatever you will not wear for the longest time (requires knowing next season's fashion — impossible). LRU removes what you have not worn recently (if you have not touched it in months, it probably goes to storage). Clock is like a quick scan: "Have I worn this recently? Yes → keep. No → donate."

Key Takeaways

• Page replacement selects which page to evict when memory is full
• FIFO is simple but can suffer from Belady's anomaly (more frames → more faults)
• Optimal (OPT) gives minimum faults but requires future knowledge — used only as benchmark
• LRU approximates OPT using past behavior and does not suffer Belady's anomaly
• True LRU is too expensive for hardware — approximations like Clock algorithm are used in practice
• The Clock (Second Chance) algorithm uses reference bits in a circular scan
• Good algorithms keep the page fault rate low, which is critical for virtual memory performance