--- title: "FIFO Belady's anomaly; thrashing" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:belady-anomaly-thrashing" source: https://www.bctengineer.com/q/semester_6/operating_system/belady-anomaly-thrashing site: BCT Engineering --- # FIFO Belady's anomaly; thrashing Operating System · Chapter 4: Memory Management - Asked in: 2073 Bhadra, 3+2 marks - Video: [L-5.23: Belady's Anomaly in FIFO page Replacement with example | Operating System](https://www.youtube.com/watch?v=pR1uhp--COc) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/belady-anomaly-thrashing - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question With an example, show that FIFO page replacement algorithm suffers from Belady's anomaly. What is 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. ## Answer #### 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) ```text 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** ```text 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is Belady's anomaly? A. Pages get lost B. More frames leads to more faults C. Fewer frames means fewer faults D. Faults equal frames Answer: B. Occurs in FIFO. (Key point: Belady) 2. For 1,2,3,4,1,2,5,1,2,3,4,5 FIFO faults with 3 and 4 frames? A. 10 and 9 B. 9 and 10 C. 8 and 10 D. 9 and 9 Answer: B. More memory gave more faults. (Key point: Example) 3. Which algorithms are immune? A. FIFO only B. None C. LRU and Optimal D. FIFO and LRU Answer: C. They are stack algorithms. (Key point: Stack algorithms) 4. What is thrashing? A. More time paging than doing useful work B. Too many frames C. CPU overheating D. Disk full Answer: A. Process lacks frames for its working set; CPU utilization drops. (Key point: Thrashing) ## Related in Operating System - [Thrashing; page faults on 3 frames](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Athrashing-page-faults-fifo-opt-lru-lfu) — Operating System, chapter 4 - [Page faults: LRU, FIFO, Optimum](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-lru-fifo-optimum) — Operating System, chapter 4 - [Page faults: FIFO, Optimal, LFU, LRU](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-fifo-optimal-lfu-lru-5frames) — Operating System, chapter 4, asked 2× - [Page faults with 3 frames: LRU, FIFO, OPT](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-circumstances-lru-fifo-optimal) — Operating System, chapter 4, asked 2× - [Race condition; optimal page replacement limits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-optimal-limitation) — Operating System, chapter 3 - [Page fault; allocation and replacement](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-allocation-replacement) — Operating System, chapter 4 ## Related in other subjects - [Mapping function and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amapping-replacement) — Computer Organization and Architecture, chapter 6 - [Replacement algorithm in associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-assoc) — Computer Organization and Architecture, chapter 6 - [Need for replacement algorithm in cache](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-why) — Computer Organization and Architecture, chapter 6 - [Cache write policy and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-write-policy-replacement) — Embedded System, chapter 4