Belady’s Anomaly, explained.
Belady’s anomaly is an increase in page faults after increasing cache capacity under some replacement policies, including FIFO.
Why it happens
The request stream is 1,2,3,4,1,2,5,1,2,3,4,5. FIFO evicts the earliest arrival without refreshing hits; LRU refreshes recency. Complete FIFO traces have nine faults with three slots and ten with four.
Belady’s anomaly is an increase in page faults after increasing cache capacity under some replacement policies, including FIFO.
Read the result
Compare fault counts after the same number of requests. A larger FIFO cache has a different eviction history, not simply the smaller cache plus one page.
A worked example
A twelve-request cache counterexample
Replay the full declared stream through the three-slot and four-slot FIFO caches.
Inspect the complete fault totals of nine and ten, tracing the queue contents where their histories diverge.
Switch to LRU and replay the identical requests to see why the policy’s inclusion property changes the conclusion.
OPTIONAL DEEPER DETAILGo deeper: inside the model
Inside this model
The request stream is 1,2,3,4,1,2,5,1,2,3,4,5. FIFO evicts the earliest arrival without refreshing hits; LRU refreshes recency. Complete FIFO traces have nine faults with three slots and ten with four.
Where this idea is useful
A practical use
Measure the replacement policy as well as capacity before assuming more memory always reduces misses on a workload.
A common misconception
“Increasing cache capacity can never increase misses under any policy.”
FIFO is not a stack policy and can exhibit the anomaly. LRU retains the inclusion property that prevents it under the same request stream.
What this explanation leaves out
- The anomaly is policy- and workload-dependent; LRU’s stack property rules it out for that policy.
Does the example mean a smaller cache is generally better?
No. It is a counterexample to a universal claim, not a workload distribution or a recommendation for smaller memory.
Does your performance assumption depend on a policy property you have actually checked?
Associated thinkers
Associations marked provisional are awaiting source review.
Further reading
Explore the original research or the teaching reference behind this experiment.