Bélády's anomaly

This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm.

[1] In common computer memory management, information is loaded in specific-sized chunks.

A simple algorithm is FIFO: whichever page has been in the frames the longest is the one that is cleared.

Bélády, Nelson and Shedler constructed reference strings for which FIFO page replacement algorithm produced nearly twice as many page faults in a larger memory than in a smaller one and they formulated the conjecture that 2 is a general bound.

[citation needed] In 2010, Fornai and Iványi showed that the anomaly is in fact unbounded and that one can construct a reference string to any arbitrary page fault ratio.