Virtual memory: page faults and replacement
Goals and assumptions
Trace FIFO, LRU and optimal replacement; distinguish faults from replacements; and estimate fault cost with consistent units. Prerequisite: paging and address translation. Replacement examples use one process, three initially empty frames, fixed page sizes and a supplied reference string. Every reference requires its page to be resident; the first reference to a missing page faults. There is no prefetching, pinning or shared-page complication. Page numbers are labels, not addresses to divide again.
1. A small workbench and a large store
A craftsperson keeps currently needed tools on a small workbench and others in a store. A missing tool must be brought to the bench. If the bench is full, another tool must leave first. In demand paging, a legal but nonresident page can similarly trigger a page fault and require a frame. A free frame avoids eviction but not the fault. Not every fault means disk I/O: a zero-filled new page can be created without reading old file data. Accesses to invalid or prohibited addresses may instead fail; they are not promises that the OS can always supply the requested page.
A dirty victim has been modified and may require writeback before its frame is reused. A clean page backed by an unchanged file may be discarded and later reread. Therefore the number of faults alone does not completely determine real execution time. This lesson's replacement traces count faults, not device transactions.
2. FIFO remembers loading; LRU remembers use
FIFO evicts the page that entered the resident set earliest among current pages. A hit does not move that page to the back of the FIFO queue. LRU evicts the resident page whose most recent reference is oldest. A hit changes recency under LRU, even though no fault occurs. A page loaded into a free frame still counts as a fault when it was missing.
Use reference string 1,2,3,1,4,1,2,5 with three initially empty frames. In the following table the resident sets are written in sorted order only for readability; the policy state is explained separately.
| Step | Page | FIFO resident set | FIFO result | LRU resident set | LRU result |
|---|---|---|---|---|---|
| 1 | 1 | {1} | F | {1} | F |
| 2 | 2 | {1,2} | F | {1,2} | F |
| 3 | 3 | {1,2,3} | F | {1,2,3} | F |
| 4 | 1 | {1,2,3} | H | {1,2,3} | H |
| 5 | 4 | {2,3,4} | F | {1,3,4} | F |
| 6 | 1 | {1,3,4} | F | {1,3,4} | H |
| 7 | 2 | {1,2,4} | F | {1,2,4} | F |
| 8 | 5 | {1,2,5} | F | {1,2,5} | F |
FIFO has 7 faults and 4 evictions; the first three faults use empty frames. At step 5 FIFO evicts page 1, because its step-4 hit did not change loading order. LRU has 6 faults and 3 evictions. At step 5 it evicts page 2, whose last use was step 2; at step 7 it evicts page 3, last used at step 3; at step 8 it evicts page 4, last used at step 5. Writing only sets without recency/loading records is insufficient for later choices.
3. Optimal replacement looks ahead
OPT evicts the page whose next reference is farthest in the future, treating a page never referenced again as infinitely distant. It is a benchmark with knowledge unavailable to an ordinary online OS. In the same string, after the first three faults and the hit on 1, requesting 4 should evict 3: it will never be used again, while 1 and 2 will. Requests 1 and 2 then hit. Request 5 faults; no later references remain, so any resident page is an equally valid victim. Total OPT faults=5. Five different pages are referenced, so at least five compulsory first-reference faults are necessary under these empty-frame/no-prefetch assumptions; OPT reaches that lower bound here.
4. More frames: what is guaranteed?
FIFO can show Belady's anomaly: more frames can produce more faults on some strings. This is not a claim that every larger FIFO run gets worse. LRU is a stack algorithm: with compatible initial states, the resident set with k frames is contained in the set with k+1 frames after each prefix, so increasing frames cannot increase LRU faults. OPT's minimum achievable fault count also cannot increase with more frames, since extra capacity need not be used harmfully. Do not transfer these guarantees to every approximate policy or every changing workload.
5. Fault cost and thrashing
Let a normal access cost 100 ns and a faulting reference cost a total 5 ms, explicitly including all handling and its eventual completion. With fault probability p=10^−5, use the same units: 5 ms=5,000,000 ns. Effective time=(1−p)×100+p×5,000,000=149.999 ns. If a problem instead gives only extra fault penalty, use normal cost plus p times that extra penalty. Avoid charging normal access twice or mixing milliseconds with nanoseconds.
When active working sets greatly exceed available frames, repeated faults can dominate useful work: thrashing. Adding multiprogrammed processes can worsen this pressure instead of improving useful throughput. A working set is tied to a recent reference window; it is not automatically every page the process has ever touched.
Self-check
Write initial frames, reference order, policy and tie rules. Mark hits as carefully as faults. Record FIFO age or LRU recency after every reference. Distinguish fault count from eviction count, and fault probability from the probability of a TLB miss.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
VM01. With three initially empty frames and FIFO, reference string 1,2,3,1,4,1,2,5 has how many page faults? No prefetching.
A. 5 B. 6 C. 7 D. 8
Answer: C
A: Five is OPT for this string, not FIFO.
B: Six is LRU here.
C: Only step 4 hits; the other seven references fault.
D: The second reference to 1 at step 4 is a hit.
VM02. With three initially empty frames and LRU, reference string 1,2,3,1,4,1,2,5 has how many page faults?
A. 5 B. 6 C. 7 D. 8
Answer: B
A: Five is OPT here.
B: Steps 1,2,3,5,7,8 fault; steps 4 and 6 hit.
C: Seven is FIFO here; LRU preserves recently used 1 at step 5.
D: There are two hits, so not eight faults.
VM03. For three initially empty frames and references 1,2,3,1,4,1,2,5, which page should OPT evict when page 4 is requested?
A. 1 B. 2 C. 3 D. 4
Answer: C
A: 1 is needed at the next reference.
B: 2 is needed later; 3 is never needed again.
C: 3 has no future reference and is the farthest-next-use victim.
D: 4 is the requested page and is not yet a resident victim.
VM04. A normal reference costs 100 ns; a faulting reference costs a total 5,000,000 ns including its completion. Fault probability is 0.00001. What is the effective time?
A. 100 ns B. 149.999 ns C. 50 ns D. 5,000,100 ns
Answer: B
A: This omits faulting references.
B: 0.99999×100+0.00001×5,000,000=149.999 ns.
C: 50 ns is only the weighted fault contribution.
D: This treats every reference as faulting and adds an already included normal completion.
VM05. Which policy can exhibit more page faults after increasing frame count for the same reference string and initially empty memory?
A. LRU B. Optimal minimum-fault replacement C. FIFO D. None of these
Answer: C
A: LRU has the stack property under these conditions.
B: More capacity cannot worsen the optimum.
C: FIFO can exhibit Belady’s anomaly.
D: FIFO is a counterexample to the universal claim.
VM06. A legal nonresident page is referenced when one unused frame is available. No prefetching has occurred. What is necessary in the demand-paging model?
A. A fault and an eviction B. A fault, but no eviction is necessary C. Neither fault nor eviction D. A TLB hit proves the page is resident despite the premise
Answer: B
A: A free frame avoids evicting an existing page.
B: The page is missing, so it faults; the free frame supplies capacity.
C: Missing residency still requires fault handling.
D: A valid resident translation cannot override the stated nonresident condition.
Sources and scope
This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in