Belady's anomaly
Encyclopedia : B : BE : BEL : Belady's anomaly
Belady's anomaly states that it is possible to have more page faults when increasing the number of page frames while using FIFO method of frame management. Lazlo Belady demonstrated this in 1970. Previously, it was believed that an increase in the number of page frames would always provide the same number or fewer page faults.
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 must be loaded from 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, the FIFO algorithm was assumed to be acceptable.
The following is an example of Belady'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.
| Page Requests | 3 | 2 | 1 | 0 | 3 | 2 | 4 | 3 | 2 | 1 | 0 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 1 | 3 | 3 | 3 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 |
| Frame 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | |
| Frame 3 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 0 | 0 |
| Page Requests | 3 | 2 | 1 | 0 | 3 | 2 | 4 | 3 | 2 | 1 | 0 | 4 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frame 1 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 0 | 0 |
| Frame 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | |
| Frame 3 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | ||
| Frame 4 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | |||
| (red indicates page fault) | ||||||||||||
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.