Belady's Anomaly


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.

Memory With 3 Frames

frame 1dddaaaeeeeee
frame 2 cccdddddbaa
frame 3  bbbccccccc
page fault123456789 
page(s) loadeddcbadceba 
page(s) removed   dcbadb 

Memory With 4 Frames

frame 1ddddddeeeeaa
frame 2 ccccccdddde
frame 3  bbbbbbcccc
frame 4   aaaaaabbb
page fault1234  5678910
page(s) loadeddcba  edcbae
page(s) removed      dcbaea


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.

Here is a PDF version of this document.