Skip to main content

FIFO Belady's anomaly; thrashing

Short answer

Belady's anomaly occurs when increasing frames raises page faults, e.g., FIFO with reference string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames but 10 with 4. Thrashing is excessive paging when a process lacks enough frames for its working set.

With an example, show that FIFO page replacement algorithm suffers from Belady's anomaly. What is thrashing?

Belady's anomaly in FIFO

Belady's anomaly is the situation in which increasing the number of page frames increases the number of page faults. FIFO suffers from it because it ignores how often or how recently a page is used, so more frames can change which pages get evicted for the worse.

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

FIFO with 3 frames (* = fault)

ref  1 2 3 4 1 2 5 1 2 3 4 5
F1   1 1 1 4 4 4 5 5 5 5 5 5
F2   - 2 2 2 1 1 1 1 1 3 3 3
F3   - - 3 3 3 2 2 2 2 2 4 4
     * * * * * * *     * *

Faults = 9.

FIFO with 4 frames

ref  1 2 3 4 1 2 5 1 2 3 4 5
F1   1 1 1 1 1 1 5 5 5 5 4 4
F2   - 2 2 2 2 2 2 1 1 1 1 5
F3   - - 3 3 3 3 3 3 2 2 2 2
F4   - - - 4 4 4 4 4 4 3 3 3
     * * * *     * * * * * *

Faults = 10.

With 3 frames there are 9 faults but with 4 frames there are 10 faults: more memory gave more faults. LRU and Optimal are stack algorithms and never show this anomaly.

Thrashing

Thrashing is a condition in which a process (or the whole system) spends more time paging (swapping pages in and out) than executing useful work. It happens when a process does not have enough frames for its working set: it faults, replaces a page that is needed again at once, and faults again. CPU utilization drops; the OS may then wrongly raise the degree of multiprogramming, making it worse. Remedies: working-set model, page-fault-frequency control, local replacement, reducing the degree of multiprogramming.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 4 questions →