--- title: "Page faults with 3 frames: LRU, FIFO, OPT" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:page-fault-circumstances-lru-fifo-optimal" source: https://www.bctengineer.com/q/semester_6/operating_system/page-fault-circumstances-lru-fifo-optimal site: BCT Engineering --- # Page faults with 3 frames: LRU, FIFO, OPT Operating System · Chapter 4: Memory Management - Asked in: 2073 Magh, 4+6 marks - Video: [Page Replacement Algorithm|| FIFO, LRU & Optimal || Operating System](https://www.youtube.com/watch?v=rFnkcq_PwT8) — Arfa Shaikh - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/page-fault-circumstances-lru-fifo-optimal - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question Under what circumstances do page faults occur? Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the LRU replacement, FIFO replacement and optimal replacement algorithms by assuming three frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each. ## Short answer Page faults occur on first reference, after replacement, or on invalid access. With three frames, LRU yields 14 faults, FIFO 15, and Optimal 11. ## Answer #### Circumstances for page faults A page fault occurs when a running process references a page whose page-table entry is marked invalid (not present in main memory). The usual circumstances are: 1. **First reference** to a page under demand paging: the page has never been loaded. 2. The page was **replaced earlier** (swapped out) to make room for another page and is needed again. 3. Reference to a page that is part of the process's address space but **not yet allocated** (e.g. stack growth) so the OS must create a frame. 4. A **copy-on-write** page is written to (the OS makes a private copy). 5. An **illegal reference** (invalid address or protection violation): this is a fault the OS turns into termination of the process. #### Simulation (3 frames, initially empty) Reference string (18 references): 1, 2, 3, 4, 2, 1, 5, 6, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. `*` = fault. **LRU** ```text ref 1 2 3 4 2 1 5 6 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 4 4 4 5 5 5 3 3 3 3 3 3 3 3 3 F2 - 2 2 2 2 2 2 6 6 6 7 7 7 2 2 2 2 2 F3 - - 3 3 3 1 1 1 2 2 2 6 6 6 1 1 1 6 * * * * * * * * * * * * * * ``` Faults = 14, hits = 4. **FIFO** ```text ref 1 2 3 4 2 1 5 6 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 4 4 4 4 6 6 6 7 7 7 7 1 1 1 1 F2 - 2 2 2 2 1 1 1 2 2 2 6 6 6 6 6 3 3 F3 - - 3 3 3 3 5 5 5 3 3 3 3 2 2 2 2 6 * * * * * * * * * * * * * * * ``` Faults = 15, hits = 3. **Optimal** ```text ref 1 2 3 4 2 1 5 6 2 3 7 6 3 2 1 2 3 6 F1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 6 F2 - 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2 F3 - - 3 4 4 4 5 6 6 6 6 6 6 6 1 1 1 1 * * * * * * * * * * * ``` Faults = 11, hits = 7. | Algorithm | Faults | Hits | |---|---|---| | LRU | 14 | 4 | | FIFO | 15 | 3 | | Optimal | 11 | 7 | **Answer: LRU = 14, FIFO = 15, Optimal = 11 page faults.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. When does a page fault occur? A. When the page-table entry for the referenced page is marked invalid (page not in main memory) B. When the TLB is full C. When the CPU cache misses on a data word D. When a process is created Answer: A. A page fault is raised when the referenced page's page-table entry is invalid, i.e. the page is not in main memory. (Key point: Page fault trigger) 2. What does the OS do on a page fault caused by an illegal reference (invalid address or protection violation)? A. Loads the page from disk anyway B. Terminates the process C. Replaces a random page D. Doubles the number of frames Answer: B. Illegal references cannot be satisfied by loading a page, so the OS terminates the process. (Key point: Illegal reference) 3. With 3 frames, which set of faults is correct for the given 18-reference string? A. LRU = 15, FIFO = 14, Optimal = 11 B. LRU = 14, FIFO = 15, Optimal = 11 C. LRU = 11, FIFO = 14, Optimal = 15 D. LRU = 14, FIFO = 11, Optimal = 15 Answer: B. Simulation gives LRU 14, FIFO 15 and Optimal 11 faults. (Key point: Fault counts) 4. Why does Optimal give the fewest faults (11)? A. It replaces the oldest page B. It replaces the page not used for the longest time in the future C. It replaces the least recently used page D. It never replaces pages Answer: B. Optimal looks ahead and evicts the page needed furthest in the future, which is why it is best but not implementable. (Key point: Optimal replacement) ## Close variants set in other exams - [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× ## 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