Page replacement — FIFO, LRU, Clock, Optimal: Visual walkthrough

Step 1 — The shelf and the books

WHAT. Picture RAM as a tiny shelf with a fixed number of slots. Each slot is called a frame. Your program's data is chopped into equal-sized chunks called pages. A page is a book; a frame is a shelf-slot; the shelf holds far fewer books than the program owns.

WHY. A program's whole address space (all its pages) is huge and lives on disk. Only a handful of pages fit in RAM frames at once. So there is a permanent shortage: many books, few slots. That shortage is the entire reason page replacement exists.

PICTURE. Below: the big disk library on the left holds pages $0, 1, 2, \dots$ ; the shelf on the right has exactly 3 frames. The arrow is a page being carried from disk into a frame.

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

See Virtual Memory & Paging for how pages and frames are wired together in hardware.

Step 2 — What a page fault is, drawn

WHAT. The CPU asks for page $p$ . We look at the shelf.

If $p$ is already on a shelf → a hit. Free, fast.
If $p$ is not on the shelf → a page fault. We must fetch it from disk.

WHY. A disk trip is about $1 0^{5}$ times slower than reading RAM. So every fault is a punishment measured in millions of wasted CPU cycles. Our entire goal will be fewest faults. Each reference is either a hit or a fault — there is no third outcome — which is why we can just count.

$fault rate = \frac{# faults times we hit disk}{total page requests # references}$

Term by term: the top counts only the misses (disk trips); the bottom counts every request the CPU made. Their ratio is the probability that a random request misses.

PICTURE. A green check where the requested page sits on the shelf (hit); a red slash and a long arrow down to disk where it does not (fault).

Step 3 — The fork: free frame vs. full shelf

WHAT. When a fault happens, everything hinges on one question: is there an empty slot?

Shelf not full ( $∣ S ∣ < F$ ) → just drop the new page into the empty slot. No one gets thrown out.
Shelf full ( $∣ S ∣ = F$ ) → we must evict a victim first, then insert.

WHY. You cannot put a book on a full shelf without removing one. The choice of who to remove is where the four policies differ — everything before this fork is identical for all of them.

PICTURE. A decision diamond. Left branch: empty slot, page slides in, nobody harmed. Right branch: full shelf, a book gets pushed off the edge (the victim) before the new one lands.

Here is the whole loop, once, before we pick a policy:

Step 4 — FIFO: throw out the oldest arrival

WHAT. FIFO (First-In, First-Out) picks the victim by arrival time only: the page that has sat on the shelf longest gets evicted, no matter how useful it still is.

WHY. It is dirt cheap — you just keep the shelf as a queue and pop the front. No timestamps, no tracking usage. That cheapness is its only virtue.

PICTURE. The shelf as a conveyor belt. New pages enter on the right; the belt pushes the oldest page off the left edge when a new one needs room. We replay the string 7 0 1 2 0 3 0 4 with $F = 3$ . Watch step 6: FIFO evicts page 0 purely for being old — then step 7 immediately needs 0 back. That wasted fault is FIFO's signature blunder.

Step	Ref	Shelf (oldest→newest)	Result
4	2	[0,1,2]	fault, evict 7
5	0	[0,1,2]	hit
6	3	[1,2,3]	fault, evict 0 ← the blunder
7	0	[2,3,0]	fault (0 just left!)
8	4	[3,0,4]	fault, evict 2

FIFO total = 7 faults.

Step 5 — LRU: throw out the one untouched longest

WHAT. LRU (Least Recently Used) picks the victim by last-access time: the page whose most recent use is furthest in the past gets evicted.

WHY. Locality of reference — programs reuse pages they just touched. So "not touched in a long time" is a good bet for "won't be touched soon." LRU turns that bet into a rule. See Locality of Reference.

PICTURE. The same shelf, but now every access slides the used page to the front (MRU end); the victim is always plucked from the back (LRU end). Replay 7 0 1 2 0 3 0 4. At step 5 the reference to 0 bumps 0 to the front — so at step 7, when 0 is needed again, it is still on the shelf. LRU wins exactly the fault FIFO lost.

Step	Ref	Shelf (LRU→MRU)	Result
5	0	[1,2,0]	hit — 0 slides to front
6	3	[2,0,3]	fault, evict 1 (coldest)
7	0	[2,3,0]	hit — LRU kept it!
8	4	[3,0,4]	fault, evict 2 (coldest)

LRU total = 6 faults — one better than FIFO on this string.

The catch: exact LRU must update a recency record on every single memory access, which is too slow in hardware. That cost is what Clock cleverly dodges (Step 7).

Step 6 — Optimal: the crystal-ball benchmark

WHAT. OPT evicts the page whose next use lies furthest in the future (a page never used again is best of all — its "next use" is infinity).

WHY. No real machine can see the future, so OPT is unbuildable. We still care about it because it is the lower bound: no policy can beat OPT. It is the finish line we measure everyone against.

PICTURE. Look forward from each fault. For every page on the shelf, draw an arrow to its next appearance in the string. Evict the one whose arrow reaches furthest (or off the end = never). Replay 7 0 1 2 0 3 0 4:

Step 4 (need 2): future uses — 7 never again, 0@step5, 1 never. Evict a never-used one → 7.
Step 6 (need 3): 0@step7, 1 never, 2 never → evict a never-used → 1.
Step 8 (need 4): 0 never again here, 2 never, 3 never → evict 2.

OPT total = 6 faults.

Step 7 — Clock: LRU's cheap twin

WHAT. Clock (Second-Chance) arranges frames in a circle with a moving hand. Each frame carries one reference bit $R$ , set to $1$ by hardware whenever the page is touched. To evict:

Hand sees $R = 1$ → give a second chance: set $R \leftarrow 0$ , advance (do not evict).
Hand sees $R = 0$ → evict here, install new page with $R = 1$ , advance.

WHY. Exact LRU needs per-access bookkeeping (Step 5's slide-to-front on every access). Clock replaces "exactly how recently" with one bit: "used since I last looked?" A page that keeps getting referenced keeps flipping its bit back to $1$ and survives sweeps — so Clock approximates LRU using just one bit per frame and zero per-access work.

PICTURE. The circular clock face, hand sweeping. On string A B C A D: after loading, all bits are $1$ . The D fault makes the hand sweep past $A, B, C$ clearing bits to $0$ , then it returns to $A (0)$ and evicts it.

Step 8 — The degenerate & edge cases (never leave a gap)

WHAT & WHY. Real strings hit corners the tidy examples hide. Here they are, each drawn.

PICTURE. Four mini-panels: cold start, one frame, all-hits, and Belady's Anomaly.

Cold start ( $S$ empty). The first $F$ distinct pages always fault — the shelf starts bare. These "compulsory misses" hit every policy equally. (In our string: 7,0,1 = 3 guaranteed faults.)
One frame ( $F = 1$ ). The shelf holds a single page, so every reference to a different page faults and there is only one possible victim. All four policies become identical.
All-hits (string reuses only in-shelf pages). After the cold start, zero faults — the best case. Fault rate drops toward $\frac{F}{# references}$ .
Belady's Anomaly. For FIFO only, more frames can mean more faults. String 1 2 3 4 1 2 5 1 2 3 4 5: 3 frames → 9 faults, 4 frames → 10. FIFO's victim depends on arrival order, not usefulness, so a bigger queue can cling to the wrong page. LRU and OPT are "stack algorithms" — the pages held with $k$ frames are always a subset of those held with $k + 1$ — so they never show the anomaly. Full story: Belady's Anomaly.

Recall Why does FIFO trip on Belady but LRU/OPT don't?

FIFO orders victims by arrival, which is not nested as frames grow — so adding a slot can reshuffle who survives and accidentally evict a needed page. LRU/OPT order by recency/future, which is nested (stack property), so more frames can only help. ::: FIFO is not a stack algorithm; LRU and OPT are.

The one-picture summary

PICTURE. All four policies race the same string 7 0 1 2 0 3 0 4 on the same 3-frame shelf, faults tallied in an amber bar. FIFO = 7, LRU = 6, Clock ≈ LRU, OPT = 6 (the floor). See at a glance: OPT is the wall, LRU hugs it, Clock trails LRU cheaply, FIFO lags and can even go backwards (Belady).

Recall Feynman retelling — say the whole walkthrough in plain words

RAM is a tiny shelf; the program owns a huge library of pages. When the CPU wants a page that's not on the shelf, that's a fault — a slow disk trip we want to avoid. If a slot is free we just drop the page in; if the shelf is full we must evict someone, and who we evict is the policy. FIFO kicks out whoever arrived first — cheap but blind, so it sometimes dumps a page it needs a moment later. LRU kicks out whoever went untouched longest, betting recent use predicts future use — it saved exactly the fault FIFO wasted. Clock fakes LRU with one bit per page and a sweeping hand, giving still-warm pages a second chance. OPT peeks at the future and evicts whoever's needed furthest ahead — impossible to build, but it's the lowest fault count anyone could ever hit, so we grade real policies against it. Edges: the first $F$ distinct pages always fault (cold start); one frame makes all policies identical; and FIFO can weirdly get worse with more frames (Belady's Anomaly), while LRU and OPT never do because they're stack algorithms. One line to remember ::: FIFO = oldest arrival, LRU = coldest use, Clock = LRU on a bit-budget, OPT = the unbeatable future-seeing floor.

Prerequisites & neighbours: Virtual Memory & Paging · TLB & Address Translation · Locality of Reference · Thrashing & Working Set Model · Cache Replacement Policies · Belady's Anomaly · Hinglish version