Bélády's anomaly

FIFO anomaly (English Bélády 's anomaly ) denotes an occurring in the computer science phenomenon that can occur when using the FIFO replacement strategy for virtual memory management in computer systems.

Explanation

One speaks of a FIFO anomaly when in virtual memory management in computer systems with a larger main memory page faults occur more than in systems with a smaller main memory. The reason is that the FIFO strategy the oldest memory block as the first overwrites, although this is perhaps the most frequently used.

An example of the FIFO anomaly. With three side frames are joined by nine page faults. The increase to four page frames caused ten page faults. Page faults are shown in red.

Avoidance

In general, the least- recently-used strategy ( LRU) is ( " the longest unused" ) FIFO preferable because LRU memory pages that have recently been used, not replaced. However, LRU can degenerate into FIFO, that is, when consecutive memory pages are requested, not related to LRU behaves like FIFO.

Another strategy to avoid the FIFO anomaly is the "Second -chance algorithm ". Here, each memory page is marked with an access to a access bit and a cyclic pointer sets the access bit back to 0 A second pointer that is located behind the first pointer checks if in the meantime, a new access has occurred and is the memory page where appropriate, a new opportunity. Find the second pointer to the entry unmarked before, the memory page will be removed.

• Digital technology