Belady's anomaly

Common sense says that giving a program more memory can only help — surely more frames can never produce more page faults. For most algorithms that intuition is correct. But in 1969 László Bélády found a startling exception: with FIFO replacement, on certain reference strings, increasing the number of frames actually increases the number of faults. That backwards, can't-be-true-but-it-is result is Belady's anomaly.

It happens because FIFO evicts purely by age, and adding a frame changes which pages happen to be the oldest at each step — in a way that is not guaranteed to keep the larger set's contents a superset of the smaller set's. With three frames a useful page might survive by luck; with four frames the same page can get pushed out at exactly the wrong moment, causing a later fault that the three-frame run avoided. The textbook string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 is the classic demonstration: FIFO gives 9 faults with three frames but 10 faults with four.

Why it matters: the anomaly tells you something deep about what makes a replacement algorithm well-behaved. Algorithms that are stack algorithms — where the pages held with n frames are always a subset of the pages held with n+1 frames — provably cannot suffer it; LRU and optimal are both stack algorithms, so for them more frames never means more faults. FIFO is not a stack algorithm, which is exactly why it is vulnerable. The anomaly is rare in practice and the extra faults are usually few, but it is a famous warning against assuming an algorithm behaves monotonically just because it is simple.