When a page fault occurs and no free frame is available, the OS must evict a page to make room. The page replacement algorithm picks which page to evict. The goal: minimize future page faults.
Algorithms Compared
| Algorithm | Decision basis | Anomaly? | Implementable? |
|---|---|---|---|
| FIFO | Age (oldest page evicted) | Belady’s anomaly | Yes |
| Optimal (OPT) | Future reference (page used farthest in future) | No | No (needs oracle) |
| LRU | Past reference (page not used for longest time) | No | Approximated |
FIFO (First-In, First-Out)
Evict the page that has been in memory the longest. Simple, but can evict a heavily-used page that happened to be loaded early.
Belady’s Anomaly: With FIFO, adding more frames can increase page faults — counterintuitive. This happens because a frequently-used page can be evicted early, then immediately faulted back in.
Optimal (OPT / MIN)
Evict the page that will be used farthest in the future. Provides the theoretical minimum page fault rate. Used only as a benchmark — requires future knowledge.
LRU (Least Recently Used)
Evict the page that hasn’t been used for the longest time. Exploits temporal locality: if a page was used recently, it’s likely to be used again soon.
LRU doesn’t suffer from Belady’s anomaly (it’s a stack algorithm). But exact LRU is expensive — requires timestamping every memory access. Hardware provides approximate LRU via the reference bit.
Reference Bit Approximation
The hardware sets a reference bit whenever a page is accessed. The OS periodically clears these bits. Pages whose bits are still clear haven’t been accessed recently. The clock algorithm (second chance) gives each page a second chance before evicting — a circular list with a reference bit.
Dirty Bit (Modify Bit)
A hardware bit set when a page is written to. During eviction:
- Dirty → must be written back to disk (costly)
- Clean → can be discarded immediately (cheap)
Better algorithms prefer evicting clean pages.
Q: What is Belady’s Anomaly?
A: A phenomenon where increasing the number of page frames results in more page faults. Occurs with FIFO (and some other algorithms) but NOT with LRU or Optimal. LRU is a “stack algorithm” — the set of pages in memory with N frames is a subset of the set with N+1 frames.
Q: Why is LRU better than FIFO?
A: LRU uses past behavior to predict future — if a page was used recently, it’s likely to be needed again (temporal locality). FIFO ignores usage patterns and may evict a critical page that happened to be loaded early. LRU also avoids Belady’s anomaly.
Q: Is the Optimal algorithm implementable?
A: No — it requires knowing future memory references. But it’s invaluable as a benchmark. If Algorithm X has 80 faults vs OPT’s 50, you know there’s room for improvement.
Q: What is the reference bit and how is it used?
A: Hardware sets a bit whenever a page is accessed. The OS uses this to approximate LRU. The clock algorithm scans pages in a circle; if the reference bit is set, it clears it and gives the page a “second chance.” If the bit is already clear, evict it.
Premium Content
Unlock Page Replacement Algorithms and all premium lessons with a subscription.
From ₹199.99/year — See plans