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