DEV Community

Cover image for More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement
Binary Dose
Binary Dose

Posted on Originally published at binarydose.in

More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement

#operatingsystems #computermemory #algorithms #computerscience

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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 M frames is guaranteed to be a hit under M+1 frames.
  • Adding RAM can never increase page faults under LRU or Optimal replacement!

Explore interactive page replacement simulations at Binary Dose.

Top comments (0)