More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement
Intuition suggests that allocating more physical memory (RAM frames) to a process must either decrease the number of page faults or, in the worst case, keep them unchanged.
Yet in 1969, computer scientist László Bélády proved a startling paradox: under First-In, First-Out (FIFO) page replacement, increasing the number of page frames can actually increase the total page faults.
This phenomenon is known as Bélády's Anomaly.
1. The Mathematical Counterexample
Consider the following reference string of page requests:
σ = 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Trace A: 3 Page Frames
- Tracing FIFO replacement through the 12 memory accesses results in 9 Page Faults.
Trace B: 4 Page Frames
- Expanding physical allocation to 4 frames results in 10 Page Faults!
Adding a 4th physical frame increases total page faults by 11%.
2. Why FIFO Suffers: The Lack of Locality
FIFO replacement selects the page that has been in memory the longest time.
Crucially, the age of a page has no correlation with its future utility. When a 4th frame is added, the timing of page evictions shifts. A frequently accessed page that happened to survive under 3 frames is prematurely evicted under 4 frames, triggering an avalanche of subsequent faults.
3. Why LRU Is Immune: The Stack Inclusion Property
Why does Least Recently Used (LRU) never exhibit Bélády's Anomaly?
LRU belongs to a mathematical class known as Stack Algorithms.
A page replacement algorithm is a stack algorithm if it satisfies the Inclusion Property:
B(M, t) ⊆ B(M+1, t) Where B(M, t) represents the set of pages present in memory of size M at time t.
In LRU, the top M most recently used pages are always a strict subset of the top M+1 most recently used pages. Therefore:
- Any memory hit under
Mframes is guaranteed to be a hit underM+1frames. - Adding RAM can never increase page faults under LRU or Optimal replacement!
Explore interactive page replacement simulations at Binary Dose.
