--- title: "Page fault; allocation and replacement" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:page-fault-allocation-replacement" source: https://www.bctengineer.com/q/semester_6/operating_system/page-fault-allocation-replacement site: BCT Engineering --- # Page fault; allocation and replacement Operating System · Chapter 4: Memory Management - Asked in: year not given - 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-fault-allocation-replacement - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question What do you mean by page fault? Explain page allocation and page replacement algorithms with numerical example. ## Short answer A page fault occurs when a referenced page is not in memory; the OS loads it, possibly replacing a page. Frame allocation methods include equal and proportional. For reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, FIFO causes 15 page faults, LRU 12, and Optimal 9. ## Answer #### Page fault A **page fault** is the trap generated when a process references a page that is not in main memory. The OS locates the page on disk, finds a free frame (or selects a victim page by a replacement algorithm), reads the page into it, updates the page table and restarts the instruction. #### Page (frame) allocation Decides how many frames each process gets from the total available. - **Equal allocation:** m frames divided equally among n processes (m/n each). - **Proportional allocation:** frames in proportion to process size. For process size s_i and total S: a_i = (s_i / S) × m. Example: m = 62 frames, sizes 10 and 127 pages: a₁ = 10/137 × 62 ≈ 4, a₂ = 127/137 × 62 ≈ 57. - **Priority allocation:** more frames to high-priority processes. - **Global vs local replacement:** global lets a process take a frame from any process; local only from its own frames. #### Page replacement algorithms When no frame is free, a victim page is chosen. - **FIFO:** replace the oldest page. Simple, can show Belady's anomaly. - **Optimal:** replace the page not used for the longest future time; best but not implementable. - **LRU:** replace the page unused for the longest past time; good approximation of optimal. - **LFU/NFU, second chance (clock), aging** are other methods. #### Numerical example Reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames (`*` = fault). FIFO ```text ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 F2 - 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 F3 - - 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 * * * * * * * * * * * * * * * ``` FIFO = 15 faults. LRU ```text ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 F2 - 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 F3 - - 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 * * * * * * * * * * * * ``` LRU = 12 faults. Optimal ```text ref 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 F2 - 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 F3 - - 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * ``` Optimal = 9 faults. **Summary: FIFO 15, LRU 12, Optimal 9 page faults.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. After a page fault, what does the OS do? A. Locate page on disk, get a free frame or victim, read the page in, update the page table, restart the instruction B. Kill the process C. Flush the TLB only D. Resume at the next instruction Answer: A. These are the standard demand-paging steps. (Key point: Page fault handling) 2. How is a frame count allocated under proportional allocation? A. a_i = m / n B. a_i = (s_i / S) x m C. a_i = s_i x n D. Based only on priority Answer: B. Frames are allocated in proportion to process size s_i over total S times m frames. (Key point: Proportional allocation) 3. Which statement is correct? A. FIFO replaces the page unused longest; LRU replaces the oldest loaded B. FIFO replaces the oldest page and can show Belady's anomaly; Optimal is not implementable C. Optimal is easy to implement D. LRU shows Belady's anomaly Answer: B. FIFO may fault more with more frames (Belady); Optimal needs future knowledge. (Key point: Replacement features) 4. For the 20-reference string with 3 frames, which fault counts are correct? A. FIFO 9, LRU 12, Optimal 15 B. FIFO 15, LRU 12, Optimal 9 C. FIFO 12, LRU 9, Optimal 15 D. FIFO 15, LRU 9, Optimal 12 Answer: B. Simulation gives FIFO 15, LRU 12, Optimal 9. (Key point: Numerical result) ## Related in Operating System - [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; virtual to physical address](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-64k-virtual-32k-physical) — Operating System, chapter 4 - [Page fault, demand paging, address translation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-demand-paging-address) — Operating System, chapter 4 - [Scheduling algorithms with numerical](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ascheduling-algorithms-numerical) — Operating System, chapter 2 - [Disk scheduling algorithms with numerical](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adisk-scheduling-algorithms-numerical) — Operating System, chapter 6 - [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 other subjects - [Associative mapping and replacement algorithms](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassociative-mapping) — Computer Organization and Architecture, chapter 6, asked 2× - [Data types and classification of algorithms](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-types-classify-algorithms) — Data Structure and Algorithm, chapter 1 - [Replacement analysis, defender vs challenger by AEC](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Areplacement-analysis-defender-challenger-aec) — Engineering Economics, chapter 5 - [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