Belady's Anomaly
There is a reasonable assumption most people make about memory management: give a process more physical frames to work with, and it will produce fewer page faults. More space means more pages can stay in RAM, which means fewer trips to the disk. This logic feels airtight.
Belady's Anomaly is the discovery that this assumption is completely wrong, at least for certain page replacement algorithms. Under specific conditions, handing a process extra frames actually causes MORE page faults. It is one of those counterintuitive results in computer science that genuinely surprises people.
What Exactly is Belady's Anomaly?
Named after László Bélády who documented it in 1969, the anomaly describes a situation where increasing the number of available physical page frames leads to a mathematical increase in page faults.
Algorithms known to exhibit this bizarre behavior include:
- FIFO (First In First Out)
- Random Page Replacement
- Second Chance Page Replacement (Clock Algorithm)
A Normal Scenario
Normally, adding frames helps. Let's look at a standard reference string processed using FIFO to see how it usually works.
Reference string: 1, 2, 3, 1, 4, 2, 5, 1, 4, 2, 3, 5Case 1: Three Frames
| Reference | Memory State | Page Fault |
|---|---|---|
| 1 | 1 | Yes (1) |
| 2 | 1, 2 | Yes (2) |
| 3 | 1, 2, 3 | Yes (3) |
| 1 | 1, 2, 3 | No |
| 4 | 2, 3, 4 | Yes (4) |
| 2 | 2, 3, 4 | No |
| 5 | 3, 4, 5 | Yes (5) |
| 1 | 4, 5, 1 | Yes (6) |
| 4 | 4, 5, 1 | No |
| 2 | 5, 1, 2 | Yes (7) |
| 3 | 1, 2, 3 | Yes (8) |
| 5 | 2, 3, 5 | Yes (9) |
Total Page Faults with 3 frames = 9
Case 2: Four Frames
| Reference | Memory State | Page Fault |
|---|---|---|
| 1 | 1 | Yes (1) |
| 2 | 1, 2 | Yes (2) |
| 3 | 1, 2, 3 | Yes (3) |
| 1 | 1, 2, 3 | No |
| 4 | 1, 2, 3, 4 | Yes (4) |
| 2 | 1, 2, 3, 4 | No |
| 5 | 2, 3, 4, 5 | Yes (5) |
| 1 | 3, 4, 5, 1 | Yes (6) |
| 4 | 3, 4, 5, 1 | No |
| 2 | 4, 5, 1, 2 | Yes (7) |
| 3 | 5, 1, 2, 3 | Yes (8) |
| 5 | 5, 1, 2, 3 | No |
Total Page Faults with 4 frames = 8
Adding a frame successfully reduced the faults from 9 to 8. But now let's look at a reference string that specifically triggers the anomaly.
The Anomaly Scenario
Reference string: 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4Case 1: Three Frames
| Reference | Memory State | Page Fault |
|---|---|---|
| 3 | 3 | Yes (1) |
| 2 | 3, 2 | Yes (2) |
| 1 | 3, 2, 1 | Yes (3) |
| 0 | 2, 1, 0 | Yes (4) |
| 3 | 1, 0, 3 | Yes (5) |
| 2 | 0, 3, 2 | Yes (6) |
| 4 | 3, 2, 4 | Yes (7) |
| 3 | 3, 2, 4 | No |
| 2 | 3, 2, 4 | No |
| 1 | 2, 4, 1 | Yes (8) |
| 0 | 4, 1, 0 | Yes (9) |
| 4 | 4, 1, 0 | No |
Total Page Faults with 3 frames = 9
Case 2: Four Frames
| Reference | Memory State | Page Fault |
|---|---|---|
| 3 | 3 | Yes (1) |
| 2 | 3, 2 | Yes (2) |
| 1 | 3, 2, 1 | Yes (3) |
| 0 | 3, 2, 1, 0 | Yes (4) |
| 3 | 3, 2, 1, 0 | No |
| 2 | 3, 2, 1, 0 | No |
| 4 | 2, 1, 0, 4 | Yes (5) |
| 3 | 1, 0, 4, 3 | Yes (6) |
| 2 | 0, 4, 3, 2 | Yes (7) |
| 1 | 4, 3, 2, 1 | Yes (8) |
| 0 | 3, 2, 1, 0 | Yes (9) |
| 4 | 2, 1, 0, 4 | Yes (10) |
Why Does This Happen?
The root cause comes down to how FIFO makes its decisions. It evicts pages based purely on arrival order, completely ignoring whether a page is still being actively used. An old page that gets referenced constantly has absolutely no protection.
When you increase frames, the set of pages that happen to be in memory shifts in a different way, and certain reference patterns end up with worse coverage at key moments in the sequence.
The technical explanation involves the concept of stack algorithms versus non-stack algorithms.
FIFO violates this subset property. The pages present in memory with 3 frames are NOT necessarily a subset of the pages present with 4 frames. The addition of a frame completely reshuffles which pages get evicted and when.
Algorithms That Are Immune
LRU and Optimal are both stack algorithms. They satisfy the subset property, which mathematically guarantees they will NEVER exhibit Belady's Anomaly. More frames will always result in the same or fewer page faults, never more.
| Algorithm | Exhibits Belady's Anomaly | Type |
|---|---|---|
| FIFO | Yes | Non-stack |
| Random | Yes | Non-stack |
| Second Chance | Yes | Non-stack |
| LRU | No | Stack |
| Optimal | No | Stack |
Summary
Belady's Anomaly is not a constant problem that plagues FIFO every time. It shows up only with specific, rare reference patterns. Many real workloads run FIFO without ever triggering it.
The anomaly matters more as a conceptual warning: memory management has non-obvious consequences, and naive intuitions do not always hold true. When predictable behavior under increasing frames is required, a stack-based algorithm like LRU is the safer choice.
Sort the Concepts
Classify the following Page Replacement Algorithms based on whether they are immune to Belady's Anomaly.