For the page reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, count the page faults using FIFO replacement with 3 frames and with 4 frames. What does the result show?
Show hints
Trace the frames step by step; evict whichever page was loaded earliest.
Show the explanation
Worked answer. Frames start empty; FIFO evicts the oldest loaded page. F = fault, H = hit.
3 frames
| Ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frames after | 1 | 1 2 | 1 2 3 | 2 3 4 | 3 4 1 | 4 1 2 | 1 2 5 | 1 2 5 | 1 2 5 | 2 5 3 | 5 3 4 | 5 3 4 |
| Result | F | F | F | F | F | F | F | H | H | F | F | H |
Faults = 9.
4 frames
| Ref | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Frames after | 1 | 1 2 | 1 2 3 | 1 2 3 4 | 1 2 3 4 | 1 2 3 4 | 2 3 4 5 | 3 4 5 1 | 4 5 1 2 | 5 1 2 3 | 1 2 3 4 | 2 3 4 5 |
| Result | F | F | F | F | H | H | F | F | F | F | F | F |
Faults = 10.
What it shows: Belady's anomaly. Giving FIFO more frames produced more faults (10 vs 9). FIFO evicts purely by load time, so the pages held with 4 frames are not always a superset of those held with 3.
Immune algorithms: stack algorithms, where pages kept with n frames are always a subset of those kept with n + 1, cannot show the anomaly. LRU and optimal (OPT) are stack algorithms.
Follow-up: "Why not use exact LRU?" Tracking the order of every access is too expensive; real systems approximate it with a reference bit, e.g. the clock (second-chance) algorithm.
Original UniCircle question. Last reviewed 28 Oct 2026.