Belady's Anomaly and Stack Algorithms

Belady’s anomaly

Belady’s anomaly is the counter-intuitive phenomenon where increasing the number of available frames can increase the number of page faults — for a given reference string and a given algorithm.

FIFO is the classic example. Consider the reference string 1 2 3 4 1 2 5 1 2 3 4 5:

• With 3 frames: 9 page faults.
• With 4 frames: 10 page faults — more frames, more faults.

The anomaly occurs because FIFO’s eviction decision depends only on load order, not on recency of use. Adding a frame changes load order in ways that can cause a just-evicted page to be demanded again immediately on the next reference.

Stack algorithms

A page-replacement algorithm is a stack algorithm if the set of pages in memory with $n$ frames is always a subset of the set of pages in memory with $n+1$ frames (subject to the same reference string).

Stack algorithms are immune to Belady’s anomaly: adding frames can only reduce or keep the same the number of page faults, never increase them.

LRU is a stack algorithm. The set of pages in memory with $n$ frames under LRU is always the $n$ most-recently-used pages. The $n+1$ most-recently-used pages strictly contain the $n$ most-recently-used pages.

OPT is a stack algorithm. With $n$ frames, OPT keeps the $n$ pages whose next use is farthest in the future. With $n+1$ frames, OPT adds one more page (whose next use is nearer than the farthest among the $n$). The $n$ set is always a subset of the $n+1$ set — they differ by exactly the one additional page, or are identical if the extra frame is never needed.

FIFO is NOT a stack algorithm. The set of pages in memory depends on load order, which changes when the number of frames changes. A page may be in memory with 3 frames but absent with 4 frames at the same point in the reference string.

Proof sketch: LRU is a stack algorithm

Define $S_n(t)$ as the set of pages in memory with $n$ frames after reference $t$. Under LRU:

• $S_n(t)$ = the $n$ most-recently-referenced distinct pages after reference $t$.
• If a page is among the $n$ most-recently-referenced, it is necessarily among the $n+1$ most-recently-referenced (since the ordering is the same, and $n < n+1$).
• Therefore $S_n(t) \subseteq S_{n+1}(t)$ for all $t$.

This subset property implies the inclusion property: a page fault with $n+1$ frames implies a page fault with $n$ frames. The number of page faults with $n+1$ frames ≤ the number with $n$ frames.

Why this matters for the Tripos

The question typically asks:

1. State Belady’s anomaly and give an example (FIFO with 3 vs 4 frames on a reference string).
2. Explain why OPT and LRU do not exhibit it (they are stack algorithms). Show the subset argument for LRU.
3. Explain why FIFO can (eviction depends on load order, not recency; changing frame count changes the set composition in non-monotonic ways).

Summary

• Belady’s anomaly: more frames → more faults. Counter-intuitive and pathological.
• Stack algorithms satisfy $S_n \subseteq S_{n+1}$, guaranteeing no Belady’s anomaly.
• LRU and OPT are stack algorithms; FIFO is not.
• The subset property directly implies the monotonicity property (more frames never increase faults).