Page replacement — FIFO, LRU, Clock, Optimal: Worked examples

This page is the drill floor for the parent topic. The parent taught you how each policy picks a victim. Here we hit every case class a page-replacement problem can throw at you — cold starts, full frames, immediate re-references, the tie between OPT and LRU, Clock sweeps, and the notorious anomaly.

Before any symbol appears: a reference string is just the ordered list of page numbers a program touches, like reading numbers off a shopping list one by one. A frame is one physical slot in RAM that holds exactly one page. $F$ is how many such slots we have. We write $S$ for the set of pages currently sitting in frames — so $∣ S ∣$ (the size of that set) is just "how many frames are occupied right now," and it can never exceed $F$ . A fault ✗ means "the page wasn't in any slot, go fetch it from disk"; a hit ✓ means "already in a slot, free." That is the whole vocabulary — nothing else is assumed.

Throughout this page every reasoning move is tagged the same way — Why this step? — so you always know exactly which decision is being justified.

The scenario matrix

Every page-replacement problem is built from these case-classes. The examples below are labelled with the cell they cover, and together they touch every row.

Cell	Case class	What makes it special
A	Cold-start fill ( $∣ S ∣ < F$ )	Frames empty → every reference faults, no victim chosen
B	Steady state, full frames	Victim policy actually fires
C	Immediate re-reference	Page evicted then needed right away (FIFO's blind spot)
D	Degenerate: 1 frame	Every distinct new page evicts — all policies collapse to the same
E	Degenerate: string fits in frames	Zero replacements ever — only cold faults
F	The OPT = LRU tie	OPT does not strictly beat LRU
G	Belady's Anomaly	More frames → more faults (FIFO only)
H	Clock second-chance sweep	Reference bits decide the victim
I	Word problem (real workload)	Translate a story into a reference string

Example 1 — Cold start + first victim (cells A, B)

Forecast: Guess the fault count before reading on. How many of these 4 references can possibly be hits?

Refs 1, 2, 3 — frames start empty, so $∣ S ∣ < F$ each time. Why this step? Cell A: with a free slot you never choose a victim, you just insert. Frames become [1,2,3]. Three faults.
Ref 4 — now $∣ S ∣ = F = 3$ , full. Why this step? Cell B fires: FIFO evicts the earliest arrival, which is 1. Frames [2,3,4]. Fault.

Verify: All four pages are distinct and none repeats, so no policy could ever score a hit — 4 faults is forced. The first three are cold-start (cell A), the fourth is the only real replacement.

Example 2 — Immediate re-reference (cell C)

Forecast: Page 0 appears at positions 2, 5, 7. FIFO evicts 0 at step 6. Will it be sorry?

Step 1 — Ref 7: frame empty, insert → [7]. Fault. Why this step? Cell A: $∣ S ∣ < F$ , so no victim, just fill.
Steps 2–3 — Refs 0, 1: still filling → [7,0,1], two more faults. Why this step? Cell A continues while a free frame exists.
Step 4 — Ref 2: full, evict oldest 7 → [0,1,2]. Fault. Why this step? Cell B: FIFO's victim is the earliest arrival, 7.
Step 5 — Ref 0: present → hit. Why this step? FIFO does not reorder on a hit — 0 keeps its arrival position, so it stays "old."
Step 6 — Ref 3: evict oldest, which is now 0 → [1,2,3]. Fault. Why this step? Cell C trap: FIFO tosses 0 purely on age, ignoring that it was just used.
Step 7 — Ref 0: fault! We threw 0 out one step ago and now need it back. Evict oldest 1 → [2,3,0]. Why this step? This is the immediate re-reference penalty — FIFO's blindness costs a fault here.
Step 8 — Ref 4: evict oldest 2 → [3,0,4]. Fault. Why this step? Cell B again: earliest arrival among [2,3,0] is 2.

Verify: Faults at steps 1,2,3,4,6,7,8; only step 5 (0) is a hit → 7 faults.

Example 3 — Same string, LRU beats FIFO (cells B, C resolved)

Forecast: Will LRU still be holding 0 when step 7 asks for it?

Steps 1–3 — Fill 7 0 1 → order LRU→MRU [7,0,1], 3 faults. Why this step? Cell A: free frames, just insert.
Step 4 — Ref 2: evict LRU 7 → [0,1,2]. Fault. Why this step? Cell B: 7 is the least recently used.
Step 5 — Ref 0: hit, move 0 to MRU → [1,2,0]. Why this step? Cell C fix: LRU refreshes recency on a hit, protecting 0.
Step 6 — Ref 3: evict LRU 1 → [2,0,3]. Fault. Why this step? 1 is now the least recently used — LRU spares 0, unlike FIFO.
Step 7 — Ref 0: hit — 0 survived because it was recently used → [2,3,0]. Why this step? The step-5 refresh is exactly what saves us here.
Step 8 — Ref 4: evict LRU 2 → [3,0,4]. Fault. Why this step? 2 has gone untouched longest.

Verify: Faults at steps 1,2,3,4,6,8; hits at steps 5,7 → 6 faults. LRU (6) < FIFO (7). ✓

Example 4 — The OPT = LRU tie (cell F)

Forecast: OPT is unbeatable — surely it drops below 6? Commit to a number first.

Steps 1–3 — Fill 7 0 1 → [7,0,1], 3 faults. Why this step? Cell A: free frames, no victim needed.
Step 4 — Ref 2: full. Look ahead — 7 is never referenced again, so its "next use" is $\infty$ . Evict 7 → [0,1,2]. Fault. Why this step? OPT evicts the furthest future use; a never-used page beats everything.
Step 5 — Ref 0: hit. Why this step? 0 is resident, so no fault and no lookahead needed.
Step 6 — Ref 3: look ahead from here. 0 is used again at step 7; 1 and 2 are never used again. Evict a never-used page — tie broken to 1 → [0,2,3]. Fault. Why this step? OPT compares next-use distances; both 1 and 2 are $\infty$ , so either works — we pick 1.
Step 7 — Ref 0: hit (we deliberately kept it). Why this step? OPT's step-6 choice was designed to protect 0.
Step 8 — Ref 4: 2 never used again → evict 2 → [0,3,4]. Fault. Why this step? 2's next use is $\infty$ , the furthest possible.

Verify: Faults at steps 1,2,3,4,6,8 → 6, equalling LRU.

Example 5 — Degenerate: one frame (cell D)

Forecast: With one slot, is there any freedom in who to evict?

Single-candidate rule: with $F = 1$ , whenever the incoming page differs from the single held page, that page must be the victim — there is only one candidate. Why this step? Cell D collapses all policies: no choice means no policy difference.
Trace 1 2 1 2 1: 1✗ → 2✗ → 1✗ → 2✗ → 1✗. Every reference alternates and evicts. Why this step? Consecutive references never repeat, so each one misses the lone held page.

Verify: No two consecutive references are equal, and only one slot exists → every reference faults → 5. ✓

Example 6 — Degenerate: string fits in frames (cell E)

Forecast: Only three distinct pages, three frames — after warm-up, can anything ever fault?

Cold-start fill 1 2 3 → [1,2,3], 3 faults. Why this step? Cell A: free frames absorb the first three references.
Every later ref (1 2 3 1) is resident → all hits. Why this step? Cell E: once the whole working set fits in frames, replacement never triggers, regardless of policy.

Verify: 3 distinct pages $\leq$ 3 frames, so only the 3 cold-start references miss. ✓

Example 7 — Belady's Anomaly (cell G)

Forecast: More frames should help, right? Predict $F = 4 <$ $F = 3$ ... or not.

We trace FIFO carefully. Notation: queue oldest→newest.

$F = 3$ : 1✗[1] · 2✗[1,2] · 3✗[1,2,3] · 4✗ evict1 [2,3,4] · 1✗ evict2 [3,4,1] · 2✗ evict3 [4,1,2] · 5✗ evict4 [1,2,5] · 1✓ · 2✓ · 3✗ evict1 [2,5,3] · 4✗ evict2 [5,3,4] · 5✓. Faults $= 9$ .

$F = 4$ : 1✗[1] · 2✗[1,2] · 3✗[1,2,3] · 4✗[1,2,3,4] · 1✓ · 2✓ · 5✗ evict1 [2,3,4,5] · 1✗ evict2 [3,4,5,1] · 2✗ evict3 [4,5,1,2] · 3✗ evict4 [5,1,2,3] · 4✗ evict5 [1,2,3,4] · 5✗ evict1 [2,3,4,5]. Faults $= 10$ .

Verify: Both fault counts are machine-checked below.

Example 8 — Clock second-chance sweep (cell H)

Forecast: Everyone's R bit is 1. Who gets evicted, and after how many hand moves?

Figure — Page replacement — FIFO, LRU, Clock, Optimal

Ref A: hit — A already resident, its R stays 1. Why this step? Hits set/keep the reference bit; no eviction happens.
Ref D, sweep move 1: fault, frames full → sweep begins. A(1): R=1, give second chance → set A(0), advance hand. Why this step? Clock never evicts a page with R=1; it clears the bit instead.
Sweep move 2: B(1): R=1 → set B(0), advance. Why this step? Same second-chance rule applies to B.
Sweep move 3: C(1): R=1 → set C(0), advance (hand wraps to A). Why this step? Same rule; now every bit is cleared.
Sweep move 4: A(0): R=0 → evict A, install D(1), advance. Why this step? After one full cleansing loop, the first page revisited with R=0 loses.

Verify: 3 pages each with R=1 → each costs one clearing pass, then the 4th check finds R=0 → 4 checks; victim is the first-checked page A.

Example 9 — Word problem: a real workload (cell I)

Forecast: Translate the story first, then guess. The reference string is 1 2 3 1 2 4 1 2 3.

Model it: each request = auth template user = 1 2 <user>. Three requests → 1 2 3 1 2 4 1 2 3. Why this step? Cell I is always "story → reference string" first — you cannot count faults until the sequence is explicit.
Trace LRU (order LRU→MRU):
- 1✗[1] · 2✗[1,2] · 3✗[1,2,3] (cold, 3 faults)
- 1✓ → [2,3,1] · 2✓ → [3,1,2] · 4✗ evict LRU 3 → [1,2,4]
- 1✓ → [2,4,1] · 2✓ → [4,1,2] · 3✗ evict LRU 4 → [1,2,3] Why this step? LRU keeps the hot pages 1 and 2 (touched every request) and evicts the stale user page each time.

Verify: Faults at positions 1,2,3 (cold), 6 (4), 9 (3) → 5 faults; positions 4,5,7,8 are hits.

Recall

Recall Which cell has

no victim choice at all? Cell A (cold-start) and cell D ( $F = 1$ ) — either a free frame exists or there is only one candidate. No policy freedom.

Recall On

7 0 1 2 0 3 0 4 with 3 frames, order FIFO vs LRU vs OPT faults. FIFO 7, LRU 6, OPT 6. OPT ties LRU — it never loses, but need not strictly win.

Belady safe?

LRU and OPT never show the anomaly (stack algorithms); FIFO can — see Example 7.

Clock checks on all-ones frames before evicting n pages?

n + 1

(one clearing pass each, then the revisit finds R=0).

Related: Virtual Memory & Paging · TLB & Address Translation · Cache Replacement Policies · Thrashing & Working Set Model.