- 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.Incomputer storage , Bélády's anomaly proves that it is possible to have morepage fault s when increasing the number of page frames while usingFIFO method of frame management. László Bélády demonstrated this in1969 .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]
Wikimedia Foundation. 2010.