Page Replacement Algorithms — Deep Dive & Solved Numericals

CSS Optional — Paper-II, Section-A · P-II.III.VI (cont.) · Page-replacement traces, Belady's Anomaly, frame allocation, and Effective Access Time are where most [Virtual Memory Management] numericals actually come from. This page works through all of them on shared, fully-verified reference strings so the frame-by-frame mechanics are unambiguous.

1. FIFO, Optimal, and LRU on the Same Reference String (direct comparison)

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 · Frames = 3 · 13 references total.

FIFO Trace — Step by Step

Rule: on a miss with all frames full, evict the OLDEST-inserted page (hits never change the queue order).

1. ref 7 → miss (empty frame) → frames = {7} → queue = [7]
2. ref 0 → miss → frames = {7,0} → queue = [7,0]
3. ref 1 → miss (now full) → frames = {7,0,1} → queue = [7,0,1]
4. ref 2 → miss → evict oldest 7 → frames = {0,1,2} → queue = [0,1,2]
5. ref 0 → hit (queue order unchanged for FIFO)
6. ref 3 → miss → evict oldest 0 → frames = {1,2,3} → queue = [1,2,3]
7. ref 0 → miss → evict oldest 1 → frames = {2,3,0} → queue = [2,3,0]
8. ref 4 → miss → evict oldest 2 → frames = {3,0,4} → queue = [3,0,4]
9. ref 2 → miss → evict oldest 3 → frames = {0,4,2} → queue = [0,4,2]
10. ref 3 → miss → evict oldest 0 → frames = {4,2,3} → queue = [4,2,3]
11. ref 0 → miss → evict oldest 4 → frames = {2,3,0} → queue = [2,3,0]
12. ref 3 → hit
13. ref 2 → hit

FIFO total = 10 page faults (10 misses, 3 hits).

Optimal (OPT/MIN) Trace — Step by Step

Rule: on a miss, evict whichever resident page is used farthest in the future (or never again).

1. ref 7 → miss → frames = {7}
2. ref 0 → miss → frames = {7,0}
3. ref 1 → miss → frames = {7,0,1}
4. ref 2 → miss, full. Look ahead: 7 is never referenced again → evict 7 → frames = {0,1,2}
5. ref 0 → hit
6. ref 3 → miss. Look ahead: 1 is never referenced again → evict 1 → frames = {0,2,3}
7. ref 0 → hit
8. ref 4 → miss. Next-use positions: 0→pos11, 2→pos9, 3→pos10 → farthest is 0 → evict 0 → frames = {2,3,4}
9. ref 2 → hit
10. ref 3 → hit
11. ref 0 → miss. Next-use: 2→pos13, 3→pos12, 4→never → evict 4 → frames = {2,3,0}
12. ref 3 → hit
13. ref 2 → hit

Optimal total = 7 page faults (7 misses, 6 hits) — the theoretical best possible for this string and frame count.

LRU Trace — Step by Step

Rule: on a miss, evict whichever resident page was used least recently (any access, including a hit, makes that page most-recently-used).

1. ref 7 → miss → frames = {7}, recency = [7]
2. ref 0 → miss → frames = {7,0}, recency = [7,0]
3. ref 1 → miss → frames = {7,0,1}, recency = [7,0,1]
4. ref 2 → miss, evict LRU 7 → frames = {0,1,2}, recency = [0,1,2]
5. ref 0 → hit, move to MRU → recency = [1,2,0]
6. ref 3 → miss, evict LRU 1 → frames = {2,0,3}, recency = [2,0,3]
7. ref 0 → hit → recency = [2,3,0]
8. ref 4 → miss, evict LRU 2 → frames = {3,0,4}, recency = [3,0,4]
9. ref 2 → miss, evict LRU 3 → frames = {0,4,2}, recency = [0,4,2]
10. ref 3 → miss, evict LRU 0 → frames = {4,2,3}, recency = [4,2,3]
11. ref 0 → miss, evict LRU 4 → frames = {2,3,0}, recency = [2,3,0]
12. ref 3 → hit → recency = [2,0,3]
13. ref 2 → hit → recency = [0,3,2]

LRU total = 9 page faults (9 misses, 4 hits).

Comparison Table

This ordering (OPT ≤ LRU ≤ FIFO in fault count) is the expected pattern for most reference strings, though FIFO is not mathematically guaranteed worse than LRU in every case — only Optimal's minimality is guaranteed.

2. Belady's Anomaly — Numerically Demonstrated

Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (12 references). Run FIFO with 3 frames, then again with 4 frames.

FIFO, 3 frames — step by step:

1. 1 → miss → {1}
2. 2 → miss → {1,2}
3. 3 → miss → {1,2,3}
4. 4 → miss, evict 1 → {2,3,4}
5. 1 → miss, evict 2 → {3,4,1}
6. 2 → miss, evict 3 → {4,1,2}
7. 5 → miss, evict 4 → {1,2,5}
8. 1 → hit
9. 2 → hit
10. 3 → miss, evict 1 → {2,5,3}
11. 4 → miss, evict 2 → {5,3,4}
12. 5 → hit

Total = 9 faults.

FIFO, 4 frames — step by step:

1. 1 → miss → {1}
2. 2 → miss → {1,2}
3. 3 → miss → {1,2,3}
4. 4 → miss → {1,2,3,4} (now full)
5. 1 → hit
6. 2 → hit
7. 5 → miss, evict oldest 1 → {2,3,4,5}
8. 1 → miss, evict oldest 2 → {3,4,5,1}
9. 2 → miss, evict oldest 3 → {4,5,1,2}
10. 3 → miss, evict oldest 4 → {5,1,2,3}
11. 4 → miss, evict oldest 5 → {1,2,3,4}
12. 5 → miss, evict oldest 1 → {2,3,4,5}

Total = 10 faults.

Giving FIFO MORE memory produced MORE faults — this counter-intuitive result is Belady's Anomaly. It is possible only for FIFO (and similar non-stack algorithms); LRU and Optimal are "stack algorithms" and are mathematically proven immune to it — a frequently tested true/false MCQ fact.

3. Clock (Second-Chance) Algorithm — Mechanism Trace, Step by Step

Each frame carries a use/reference bit. On a fault, the clock hand scans frames circularly: if the pointed-to frame's use-bit is 1, clear it to 0 and advance (giving it a "second chance"); the first frame found with use-bit already 0 is evicted, and the hand advances past it.

Frames = 3, string: 1, 2, 3, 4, 1, 2, 5

1. ref 1 → miss → slot0 = 1 (use=1), hand → slot1
2. ref 2 → miss → slot1 = 2 (use=1), hand → slot2
3. ref 3 → miss → slot2 = 3 (use=1), hand → slot0
4. ref 4 → miss, full:
   • slot0 (1, use=1) → clear to 0, advance
   • slot1 (2, use=1) → clear to 0, advance
   • slot2 (3, use=1) → clear to 0, advance
   • slot0 (1, use=0 now) → evict, place 4 (use=1), hand → slot1
5. ref 1 → miss → slot1 (2, use=0) → evict directly, place 1 (use=1), hand → slot2
6. ref 2 → miss → slot2 (3, use=0) → evict directly, place 2 (use=1), hand → slot0
7. ref 5 → miss, full:
   • slot0 (4, use=1) → clear, advance
   • slot1 (1, use=1) → clear, advance
   • slot2 (2, use=1) → clear, advance
   • slot0 (4, use=0 now) → evict, place 5 (use=1)

Clock approximates true LRU cheaply (O(1) amortized per fault, no timestamps needed) by using the second-chance bit as a coarse recency proxy — this is why real OS kernels (Linux's "clock-pro" family) use Clock variants instead of exact LRU, which would need a full access-ordered list.

4. Frame Allocation — Equal vs Proportional (Worked Numerical)

Equal allocation: total usable frames = 100, OS reserves 8 → 92 available, split across 4 processes → 92 ÷ 4 = 23 frames each, regardless of each process's actual size.

Proportional allocation (Silberschatz's classic example): 62 total frames, two processes of virtual sizes s₁ = 10 pages and s₂ = 127 pages (S = 137):

Step 1 - compute the ratio for each process:
  ratio1 = s1 / S = 10 / 137
  ratio2 = s2 / S = 127 / 137

Step 2 - multiply by total frames m = 62:
  a1 = (10 / 137) x 62 = 4.5  -> round to 4 frames
  a2 = (127 / 137) x 62 = 57.5 -> round to 57 frames

Step 3 - sanity check: 4 + 57 = 61 (one frame short of 62 due to rounding)
  -> the leftover frame is conventionally given to the larger process -> a2 = 58

Proportional allocation gives bigger processes more frames (matching their actual footprint), but a large low-locality process can still hog frames a smaller high-locality process needed more urgently — this is the trade-off to name if asked "is proportional allocation always better than equal?"

Local vs Global replacement (a paired concept, often confused with allocation itself): local replacement confines a faulting process to evicting only its OWN frames (predictable performance per process, ignores current global need); global replacement lets it evict ANY process's frame, including a higher-priority process's (better overall throughput, but one heavy process can degrade another's performance unpredictably).

5. Effective Access Time (EAT) From Page-Fault Rate — Worked Numerical

Given: memory access time = 100 ns, page-fault service time = 10 ms, page-fault rate p = 0.001 (1 in 1000 references faults).

Step 1 - write the formula:
  EAT = (1 - p) x (memory access time) + p x (page fault service time)

Step 2 - convert units so both terms are in nanoseconds:
  page fault service time = 10 ms = 10,000,000 ns

Step 3 - substitute:
  EAT = (1 - 0.001) x 100 ns + 0.001 x 10,000,000 ns
      = 0.999 x 100 + 0.001 x 10,000,000
      = 99.9 + 10,000
      = 10,099.9 ns

Answer: EAT ≈ 10,099.9 ns ≈ 10.1 microseconds — roughly 101× slower than the fault-free 100 ns access time, even though only 1 access in 1000 actually faults. This dramatic sensitivity is exactly why keeping the page-fault rate low is critical, and it's the standard justification for "why does a small increase in fault rate cause a large slowdown" essay questions.

6. Working Set Model — Worked Numerical

Reference string (positions 1-15): 2,6,1,5,7,7,7,7,5,1,6,2,3,4,1, window Δ = 10.

At time t = 10 (look at the most recent 10 references, positions 1-10: 2,6,1,5,7,7,7,7,5,1):

• Distinct pages referenced = {2, 6, 1, 5, 7}
• Working set size = 5

At time t = 15 (most recent 10 references, positions 6-15: 7,7,7,5,1,6,2,3,4,1):

• Distinct pages referenced = {7, 5, 1, 6, 2, 3, 4}
• Working set size = 7

If the sum of all active processes' working-set sizes exceeds the number of physical frames available, the OS should suspend a process (reduce the degree of multiprogramming) rather than let everyone thrash — this is the precise, examinable trigger condition for thrashing under the Working Set Model.

---

🎯 CSS Exam Angle

A reference-string numerical almost always asks for both the fault count and a named comparison ("compare with LRU," "show Belady's Anomaly") — always draw the full frame-state table for each step, not just the final tally, since intermediate frame contents carry marks independently of the final count. For EAT questions, write the formula in symbols first, then substitute — partial marks are awarded for the correct formula alone.

📌 Related Past CSS Paper Questions

See [Virtual Memory Management] → Worked Numericals for the exact past-paper versions; the traces on this page are additional verified practice covering FIFO/OPT/LRU comparison, Belady's Anomaly, Clock, frame allocation, and Working Set — topics the syllabus line covers but that don't yet have a dedicated past-paper numerical.

⚠️ MCQ Traps

• Belady's Anomaly is a FIFO-family phenomenon — stating that "increasing frames can increase faults" without naming FIFO (or claiming it can happen to LRU/Optimal) is wrong; LRU and Optimal are proven immune.
• The Clock algorithm's second-chance bit is not the same as an LRU timestamp — it's a coarse 1-bit recency approximation, cheap to maintain, and can misjudge recency compared to true LRU.
• Proportional allocation still uses a FIXED formula per process size — it does NOT adapt in real time to which process is currently faulting most; that adaptive behavior is what global replacement (not allocation policy) provides.
• A higher page-fault rate causes a disproportionately large EAT increase — because the page-fault service time (milliseconds) is roughly 100,000× the raw memory access time (nanoseconds), even a tiny fault rate dominates the formula.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-II · Q4(a) · 8 marks

Q. What are the differences between the Optimal and LRU (Least Recently Used) page replacement policies?

Ans.

• 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: Optimal = 9 page faults, LRU = 12, FIFO = 15.

MCQs

2025 P-II · Q14. For 3 page frames, the reference string is 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1. How many page faults does the LRU page replacement algorithm produce?

• (A) 10
• (B) 15
• (C) 11
• (D) 12 ✅
• Answer: (D) 12.
• Working (LRU replaces the page not used for the longest time; F = fault, H = hit):

• Total page faults = 12.
• Why not the others: FIFO would give 15 faults and the optimal policy 9, so 10, 11 and 15 do not match LRU.