Belady's anomaly demonstrates that increasing the number of page frames may also increase the number of page faults. Suppose the reference string is ω = dcbadcedcbae. The page replacement algorithm is FIFO. Let us consider two memories, one with 3 frames and one with 4 frames.
| time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ω | d | c | b | a | d | c | e | d | c | b | a | e |
| frame 1 | d | d | d | a | a | a | e | e | e | e | e | e |
| frame 2 | c | c | c | d | d | d | d | d | b | a | a | |
| frame 3 | b | b | b | c | c | c | c | c | c | c | ||
| page fault | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||
| page(s) loaded | d | c | b | a | d | c | e | b | a | |||
| page(s) removed | d | c | b | a | d | b |
| time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ω | d | c | b | a | d | c | e | d | c | b | a | e |
| frame 1 | d | d | d | d | d | d | e | e | e | e | a | a |
| frame 2 | c | c | c | c | c | c | d | d | d | d | e | |
| frame 3 | b | b | b | b | b | b | c | c | c | c | ||
| frame 4 | a | a | a | a | a | a | b | b | b | |||
| page fault | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
| page(s) loaded | d | c | b | a | e | d | c | b | a | e | ||
| page(s) removed | d | c | b | a | e | a |
The memory with 3 frames produces 9 page faults. The memory with 4 page frames produces 10 page faults.
To see why, look at the pages in memory at each time unit. At time 6, the set of pages in the 3-frame memory is not a subset of the set in the 4-frame memory. This means the 4-frame memory will producing a page fault that does not occur in the 3-frame memory. You can see this again at time 7 and time 10.
If the pages in the frames of a memory are also in the frames of a larger memory, the algorithm is said to be a stack algorithm. Because a stack algorithm by definition prevents the discrepancy above, no stack algorithm can suffer from Belady's anomaly.