Belady's anomaly
Encyclopedia
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| An example of Bélády's anomaly. Using three page frames, 9 page faults occur. Increasing to four page frames causes 10 page faults to occur. Page faults are in red. |
In computer storage
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....
, Bélády's anomaly proves that it is possible to have more page fault
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...
s when increasing the number of page frames while using the First in First Out (FIFO
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
) page replacement algorithm
Page replacement algorithm
In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out when a page of memory needs to be allocated...
. László Bélády demonstrated this in 1969.
In common computer memory management
Memory management
Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
, information is loaded in specific sized chunks. Each chunk is referred to as a page
Page (computing)
A page, memory page, or virtual page is a fixed-length contiguous block of virtual memory that is the smallest unit of data for the following:* memory allocation performed by the operating system for a program; and...
. 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
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
. Whichever page has been in the frames the longest is the one that is cleared. Until Bélády's anomaly was demonstrated, it was believed that an increase in the number of page frames would always provide the same number or fewer page faults.
Belady's Anomaly is Unbounded
Belady, Nelson and Shedler constructed reference strings for which FIFO page replacement algorithm produced near twice more page faults in a larger memory than in a smaller one and they formulated the conjecture that 2 is a general bound.In 2010, Fornai and Ivanyi showed that in fact this anomaly is unbounded by showing how to construct a reference string to any arbitrary page fault ratio number.
- Bélády's 1969 paper: An anomaly in space-time characteristics of certain programs running in a paging machine
- FIFO anomaly is unbounded.
- http://ipsc.ksp.sk/contests/ipsc2006/real/solutions/l.php