In computer storage, 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 faults for certain memory access patterns. This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm. 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 demonstrated this in 1969.[1]
Page requests
3
2
1
0
3
2
4
3
2
1
0
4
Newest page
3
2
1
0
3
2
4
4
4
1
0
0
3
2
1
0
3
2
2
2
4
1
1
Oldest page
3
2
1
0
3
3
3
2
4
4
Page requests
3
2
1
0
3
2
4
3
2
1
0
4
Newest page
3
2
1
0
0
0
4
3
2
1
0
4
3
2
1
1
1
0
4
3
2
1
0
3
2
2
2
1
0
4
3
2
1
Oldest page
3
3
3
2
1
0
4
3
2
An example of Bélády's anomaly. Using three page frames, nine page faults occur. Increasing to four page frames causes ten page faults to occur. Page faults are in red. This can be thought of as a result of a "Penny Wise, Pound Foolish" behavior.
In common computer memory management, information is loaded in specific-sized chunks. Each chunk is referred to as a page. 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 unboundededit
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.
Referencesedit
^Christopher Kruegel (3 December 2012). (PDF). cs.UCSB.edu. Archived from the original (PDF) on 10 August 2016. Retrieved 13 June 2016.
External linksedit
Bélády's 1969 paper: An anomaly in space-time characteristics of certain programs running in a paging machine
Internet Problem Solving Contest Solutions – Problem L – Librarian
April 12, 2024
bélády, anomaly, this, article, needs, additional, citations, verification, please, help, improve, this, article, adding, citations, reliable, sources, unsourced, material, challenged, removed, find, sources, news, newspapers, books, scholar, jstor, november, . This article needs additional citations for verification Please help improve this article by adding citations to reliable sources Unsourced material may be challenged and removed Find sources Belady s anomaly news newspapers books scholar JSTOR November 2021 Learn how and when to remove this template message In computer storage Belady s anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns This phenomenon is commonly experienced when using the first in first out FIFO page replacement algorithm 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 Laszlo Belady demonstrated this in 1969 1 Time displaystyle ce gt atop text Time Page requests 3 2 1 0 3 2 4 3 2 1 0 4Newest page 3 2 1 0 3 2 4 4 4 1 0 0 3 2 1 0 3 2 2 2 4 1 1Oldest page 3 2 1 0 3 3 3 2 4 4 Time displaystyle ce gt atop text Time Page requests 3 2 1 0 3 2 4 3 2 1 0 4Newest page 3 2 1 0 0 0 4 3 2 1 0 4 3 2 1 1 1 0 4 3 2 1 0 3 2 2 2 1 0 4 3 2 1Oldest page 3 3 3 2 1 0 4 3 2An example of Belady s anomaly Using three page frames nine page faults occur Increasing to four page frames causes ten page faults to occur Page faults are in red This can be thought of as a result of a Penny Wise Pound Foolish behavior Contents 1 Background 2 Belady s anomaly is unbounded 3 References 4 External linksBackground editIn common computer memory management information is loaded in specific sized chunks Each chunk is referred to as a page 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 Belady 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 Belady s anomaly is unbounded editBelady 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 Ivanyi showed that the anomaly is in fact unbounded and that one can construct a reference string to any arbitrary page fault ratio References edit Christopher Kruegel 3 December 2012 Operating Systems CS170 08 course PDF cs UCSB edu Archived from the original PDF on 10 August 2016 Retrieved 13 June 2016 External links editBelady s 1969 paper An anomaly in space time characteristics of certain programs running in a paging machine FIFO anomaly is unbounded arXiv 1003 1336 Internet Problem Solving Contest Solutions Problem L Librarian Retrieved from https en wikipedia org w index php title Belady 27s anomaly amp oldid 1146815732, wikipedia, wiki, book, books, library,
