--- title: "Page faults: FIFO, Optimal, LFU, LRU" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:page-faults-fifo-optimal-lfu-lru-5frames" source: https://www.bctengineer.com/q/semester_6/operating_system/page-faults-fifo-optimal-lfu-lru-5frames site: BCT Engineering --- # Page faults: FIFO, Optimal, LFU, LRU Operating System · Chapter 4: Memory Management - Asked in: 2070 Magh, 2+8 marks - Video: [Lec29 Page Replacement Algorithms | LRU and optimal | Operating Systems](https://www.youtube.com/watch?v=DXU7SqsYDvg) — Jenny's Lectures CS IT - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/page-faults-fifo-optimal-lfu-lru-5frames - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question What is page fault? Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the FIFO, Optimal, LFU and LRU replacement algorithms having five frames? Remember all frames are initially empty, so your first unique page will cost one fault each. ## Short answer A page fault occurs when a process accesses a page not in main memory. With 5 frames, FIFO results in 10 faults, Optimal 7, LFU 8, and LRU 8. ## Answer #### Page fault A **page fault** occurs when a process accesses a page that is not currently in main memory (its page-table entry is invalid). The OS brings the page from disk into a frame, replacing a page if no frame is free. #### Simulation (5 frames, initially empty) Reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 (20 references). `*` = page fault. **FIFO** ```text ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 F2 - 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 F3 - - 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7 * * * * * * * * * * ``` Faults = 10. **Optimal** ```text ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 F3 - - 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 F4 - - - 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7 * * * * * * * ``` Faults = 7. **LFU** (replace the page with the smallest reference count; ties broken by FIFO, the oldest page goes first) ```text ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 F3 - - 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7 * * * * * * * * ``` Faults = 8. At the reference 6, counts are 1:2, 2:2, 3:1, 4:1, 5:1; the oldest of the lowest count is 3, so 3 is replaced. At the reference 3 (position 12), pages 4, 5 and 6 all have count 1; the oldest, 4, is replaced. **LRU** ```text ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 F3 - - 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7 * * * * * * * * ``` Faults = 8. #### Result | Algorithm | Page faults | |---|---| | FIFO | 10 | | Optimal | 7 | | LFU | 8 | | LRU | 8 | **Answer: FIFO = 10, Optimal = 7, LFU = 8, LRU = 8 page faults.** There are 7 distinct pages (1 to 7), so 7 faults is the minimum possible, and Optimal achieves it. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With 5 frames, FIFO faults? A. 7 B. 12 C. 10 D. 8 Answer: C. FIFO: 10; Optimal 7; LFU 8; LRU 8. (Key point: Fault counts) 2. Why is 7 the minimum for this string? A. Optimal always gives 7 B. There are 7 distinct pages, each faulting at least once C. 7 is the string length D. There are 7 frames Answer: B. The first reference to each distinct page faults. (Key point: Minimum faults) 3. What does LFU replace? A. The oldest page always B. The page with the smallest reference count C. The most recently used D. The largest page number Answer: B. Ties are broken by FIFO. (Key point: LFU rule) 4. Which algorithm gives the fewest faults here? A. Optimal B. LFU C. LRU D. FIFO Answer: A. Optimal gets 7 faults. (Key point: Optimal) ## Close variants set in other exams - [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× ## 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 - [LRU algorithm; page faults on string](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Alru-page-faults-ref-string) — Operating System, chapter 4 - [Hits and faults: FIFO, LRU, Optimal](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ahits-faults-fifo-lru-optimal-3frames) — Operating System, chapter 4