Belady's anomaly

-
An example of Bélády's anomaly. Using three page frames, 9 page faults occur. Increasing four page frames causes 10 page faults to occur. Page faults are in red.In computer storage, Bélády's anomaly proves that it is possible to have more page faults when increasing the number of page frames while using FIFO method of frame management. László Bélády demonstrated this in 1969.

In common computer memory management, information is loaded in specific sized chunks. Each chunk is referred to as a "page". The central processor can only load a limited number of pages at a time. It requires a "frame" for each page it can load. A "page fault" occurs when a page is not found, and might need to be loaded from disk into memory.

When a page fault occurs and all frames are in use, one must be cleared to make room for the new page. A simple algorithm is FIFO. Whichever page has been in the frames the longest is the one that is cleared. Until Bélády's anomaly was demonstrated, the FIFO algorithm was assumed to be acceptable.

References

* Bélády's 1969 paper: [http://portal.acm.org/citation.cfm?doid=363011.363155 An anomaly in space-time characteristics of certain programs running in a paging machine]