FIFO anomaly
FIFO anomaly (English Bélády ’s anomaly ) describes a phenomenon occurring in computer science that can occur when using the FIFO replacement strategy for virtual memory management in computer systems.
Explanation
A FIFO anomaly occurs when more page faults occur in virtual memory management in computer systems with larger main memory than in systems with smaller main memory. This is due to the FIFO strategy, which overwrites the oldest memory block first, even if this is the most frequently used.
An example of the FIFO anomaly: With three page frames, nine page faults occur. Increasing it to four page frames causes ten page faults. Page faults are shown in red .
| Page requests | 3 | 2 | 1 | 0 | 3 | 2 | 4th | 3 | 2 | 1 | 0 | 4th |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Latest page | 3 | 2 | 1 | 0 | 3 | 2 | 4th | 4th | 4th | 1 | 0 | 0 |
| 3 | 2 | 1 | 0 | 3 | 2 | 2 | 2 | 4th | 1 | 1 | ||
| Oldest site | 3 | 2 | 1 | 0 | 3 | 3 | 3 | 2 | 4th | 4th |
| Page requests | 3 | 2 | 1 | 0 | 3 | 2 | 4th | 3 | 2 | 1 | 0 | 4th |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Latest page | 3 | 2 | 1 | 0 | 0 | 0 | 4th | 3 | 2 | 1 | 0 | 4th |
| 3 | 2 | 1 | 1 | 1 | 0 | 4th | 3 | 2 | 1 | 0 | ||
| 3 | 2 | 2 | 2 | 1 | 0 | 4th | 3 | 2 | 1 | |||
| Oldest site | 3 | 3 | 3 | 2 | 1 | 0 | 4th | 3 | 2 |
Avoidance
As a rule, the least recently used (LRU) strategy is preferable to FIFO, as LRU pages that have recently been used are not replaced. But LRU can degenerate into FIFO, i.e. H. if memory pages are requested that are not related, LRU behaves exactly like FIFO.
Another strategy for avoiding the FIFO anomaly is the "second chance algorithm". Here, each memory page is marked with an access bit when it is accessed and a cyclic pointer sets the access bit back to 0. A second pointer, which lies behind the first pointer, checks whether another access has taken place in the meantime and, if necessary, gives the memory page one new chance. If the second pointer finds the entry unmarked, the memory page is removed.
literature
- LA Belady, RA Nelson, GS Shedler: An Anomaly in Space-time Characteristics of Certain Programs Running in a Paging Machine . In: Commun. ACM . tape 12 , no. 6 , June 1, 1969, ISSN 0001-0782 , pp. 349-353 , doi : 10.1145 / 363011.363155 .