Belady's Anomaly
What You'll Learn
You'll discover a surprising situation where giving your system more memory frames can actually cause more page faults with FIFO replacement.
The Counterintuitive Phenomenon
In most areas of computing, adding resources improves performance. More memory? Fewer page faults, right? Not always! Belady's Anomaly reveals that when using FIFO (First-In-First-Out) page replacement, increasing the number of available frames can paradoxically increase the number of page faults.
This was discovered by László Bélády in 1969 and shocked researchers because it violated their intuition about memory management.
Why Does This Happen?
FIFO replaces pages based purely on arrival order, ignoring how often or recently they're used. When you add frames, you change the entire eviction pattern. Pages that would have been evicted early with fewer frames might stick around longer with more frames, only to be evicted right before they're needed again.
Think of it like checkout lanes at a store: adding a lane doesn't always reduce your wait time if it changes which lane you pick and how the crowd distributes itself. The new pattern might put you behind slower customers.
Classic Example
Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
- With 3 frames (FIFO): 9 page faults
- With 4 frames (FIFO): 10 page faults ❗
More frames, more faults!
Important Notes
Belady's Anomaly is specific to FIFO. Other algorithms like LRU (Least Recently Used) or Optimal don't suffer from this anomaly because they belong to a class called "stack algorithms" that guarantee monotonic behavior—more frames never hurts.
Key Takeaway: Belady's Anomaly shows that FIFO page replacement can produce more page faults when given more frames, demonstrating that FIFO's simplicity comes at the cost of unpredictable performance characteristics.