Belady's anomaly


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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Anomalie De Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalie de belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Laszlo Belady — (born April 29 1928 in Hungary) is a computer scientist notable for devising the Belady s Min theoretical memory caching algorithm in 1966 while working at IBM Research. He also demonstrated the existence of a Belady s anomaly.In his later years… …   Wikipedia

  • Anomalie de Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache FIFO. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n …   Wikipédia en Français

  • Anomalía de Belady — Saltar a navegación, búsqueda La anomalía de Belady es un efecto descubierto y demostrado en 1969 por el científico de la computación húngaro Laszlo Belady, por el cual es posible tener más fallos de página al aumentar el número de marcos en la… …   Wikipedia Español

  • Page replacement algorithm — This article is about algorithms specific to paging. For outline of general cache algorithms (e.g. processor, disk, database, web), see Cache algorithms. In a computer operating system that uses paging for virtual memory management, page… …   Wikipedia

  • History of CP/CMS — This lengthy article explores the History of CP/CMS the historical context in which this important IBM time sharing operating system was built. It provides details to support for the main CP/CMS and History of IBM articles, drawing on source… …   Wikipedia

  • IBM M44/44X — The IBM M44/44X was an experimental computer system from the mid 1960s, designed and operated at IBM s Thomas J. Watson Research Center at Yorktown Heights, New York. It was based on an IBM 7044 (the M44 ), and simulated multiple 7044 virtual… …   Wikipedia