In
computer storage
Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers.
The central processing unit (CPU) of a compute ...
, Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of
page fault
In computing, a page fault (sometimes called PF or hard fault) is an exception that the memory management unit (MMU) raises when a process accesses a memory page without proper preparations. Accessing the page requires a mapping to be added to t ...
s for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out (
FIFO)
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, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page repl ...
.
In FIFO, the page fault may or may not increase as the page frames increase, but in optimal and stack-based algorithms like
LRU, as the page frames increase, the page fault decreases.
László Bélády
László "Les" Bélády (born April 29, 1928, in Budapest; died November 6, 2021) was a Hungarian computer scientist notable for devising the Bélády's Min theoretical memory caching algorithm in 1966 while working at IBM Research. He also demo ...
demonstrated this in 1969.
Background
In common computer
memory management
Memory management is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and free it for reuse when ...
, information is loaded in specific-sized chunks. Each chunk is referred to as a ''
page
Page most commonly refers to:
* Page (paper), one side of a leaf of paper, as in a book
Page, PAGE, pages, or paging may also refer to:
Roles
* Page (assistance occupation), a professional occupation
* Page (servant), traditionally a young mal ...
''. Main memory can hold only 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, it was believed that an increase in the number of page frames would always result in the same number of or fewer page faults.
Bélády's anomaly is unbounded
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.
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.
References
External links
* Bélády's 1969 paper
An anomaly in space-time characteristics of certain programs running in a paging machine* FIFO anomaly is unbounded.
Internet Problem Solving Contest Solutions – Problem L – Librarian
{{DEFAULTSORT:Belady's anomaly
Memory management