Replacement policies (LRU, FIFO, random): Visual walkthrough

This page builds the three replacement policies — LRU, FIFO, and Random — from nothing but a row of boxes. We will watch each policy make its choice, one access at a time, and then watch FIFO do something that feels impossible — get worse when you give it more room. Every symbol is earned before it appears.

Step 1 — The shelf, the slots, and one word we will reuse everywhere

WHAT. Draw a set of the cache as a row of boxes. Each box is called a way — it is one physical slot that can hold one block (a chunk of memory the size the cache moves around). A set with $n$ boxes is == $n$ -way associative==. Here $n = 4$ .

WHY. Every policy we study is just a different answer to one question: "the four boxes are full and block $E$ wants in — which box gets emptied?" We cannot ask that question until we can see the four boxes.

PICTURE (Figure s01). Four empty boxes labelled way 0 … way 3, with the incoming stream $A, B, C, D, A, E$ drawn as an orange queue above them and a "time →" arrow. This is the access sequence, the order the processor asks for blocks. We will feed this same sequence to LRU and FIFO so the difference is purely the policy.

Figure — Replacement policies (LRU, FIFO, random)

Figure s01 — A fresh 4-way set: four empty boxes (way 0 to way 3) below, the access sequence A B C D A E as an orange queue above, flowing left to right in time.

A single request is a hit if the block is already in a box, or a miss if it is not — and a miss on a full set is what forces an eviction (emptying a box). See 5.4.01-Cache-organizationand-addressing for how the address chooses which set.

Step 2 — LRU's ruler: the recency counter, and the exact order of operations

WHAT. Give every occupied box a small number written under it: its recency. Recency $0$ means "just touched, the freshest block." A bigger number means "staler." We update it with one rule, and — crucially — we fix the exact sequence in which the miss is handled.

WHY. LRU (Least Recently Used) wants to throw away the block nobody has touched in the longest time. To do that it needs a way to measure "how long ago" — recency is that ruler. Why measure the past at all? Because of temporal locality: a block used recently is likely to be used again, so the least recently used is the safest to discard. But a ruler alone is not a policy: we must also say when we read it, when we age the counters, and what number the brand-new block gets.

PICTURE (Figure s02). Read the update rule right off the boxes, then read the operational recipe below it.

Definition The exact order of operations on one access (this removes all ambiguity)

When access $t$ arrives, do these in this order — evict-then-update:

Hit? If the block is already in a box, that box is "the one accessed at time $t$ ": set its recency to $0$ , age every other occupied box by $+ 1$ (capped at $n - 1$ ), done. No eviction.
Miss with an empty way? Load the block into the lowest-numbered empty way. Then treat that box as "the one accessed": set its recency to $0$ and age every other occupied box by $+ 1$ . No eviction.
Miss with a full set? First read the current recencies and choose the victim = the box with the largest recency. Then empty that box, load the new block into it, and finally apply the update: set the new block's recency to $0$ and age every other box by $+ 1$ .

What recency does a brand-new block get? Always $0$ — it was, by definition, just accessed. So the update is applied after the victim is chosen, never before.

Figure s02 — LRU's ruler: four boxes each carrying a recency counter; green marks recency 0 (freshest), red marks recency n−1 = 3 (oldest, the victim). The red down-arrow shows the box with the maximum recency being evicted.

Step 3 — Watch LRU run the sequence A B C D A E

WHAT. Feed $A, B, C, D, A, E$ to the four boxes, drawing the recency number under each box after each access is fully handled (following the evict-then-update recipe of Step 2).

WHY. This is the payoff of Step 2 — we see the counters age, the hit on $A$ reset $A$ to $0$ , the victim chosen before the new block's counter is written, and the new block $E$ enter with recency $0$ . Note the first four accesses just fill empty ways; no eviction happens until the set is full.

PICTURE (Figure s03). Follow the coloured strip. The star marks the eviction.

Access	Boxes (way0…way3)	Recency after	What happened
$A$	$A, -, -, -$	$0, -, -, -$	miss, empty way 0 → load $A$ , set its recency 0
$B$	$A, B, -, -$	$1, 0, -, -$	miss, empty way 1 → load $B$ (rec 0), $A$ ages to 1
$C$	$A, B, C, -$	$2, 1, 0, -$	miss, empty way 2 → load $C$ (rec 0), $A, B$ age
$D$	$A, B, C, D$	$3, 2, 1, 0$	miss, empty way 3 → load $D$ (rec 0), set now full
$A$	$A, B, C, D$	$0, 3, 2, 1$	hit on $A$ → reset $A$ to 0, others age $+ 1$
$E$	$A, E, C, D$	$1, 0, 3, 2$	miss, full → evict $⋆ B$ , load $E$ (rec 0), rest age $+ 1$

Reading the last row carefully (this is the fix). Just before handling $E$ , the recencies are $A = 0, B = 3, C = 2, D = 1$ . Following the recipe:

Choose the victim first from these current values: the maximum is $B = 3$ , so ==LRU evicts $B$ == (way 1). The recent hit on $A$ saved it.
Then load $E$ into way 1 and apply the update: $E$ gets recency $0$ ; every other box ages $+ 1$ , so $A : 0 \to 1$ , $C : 2 \to 3$ , $D : 1 \to 2$ .

That gives the final row $[A = 1, E = 0, C = 3, D = 2]$ , i.e. $[1, 0, 3, 2]$ across ways $0, 1, 2, 3$ . (The previous draft wrote $[1, 0, 2, 3]$ ; that would only be correct under an "update-then-evict" ordering, which we explicitly rejected — we age the survivors after choosing the victim, so $C$ , being older than $D$ , ends up the stalest survivor at $3$ .)

Figure s03 — LRU on A B C D A E, six columns (one per access). Each column shows way 0 to way 3 top to bottom with its recency number; the hit on A resets it to 0, and the final column evicts B (red, starred) with E entering at recency 0.

Step 4 — FIFO's ruler: a single pointer, and hits change nothing

WHAT. Throw away all four recency counters. Keep one number for the whole set: the queue pointer, written $QueuePtr$ , which just remembers "which box gets emptied next." It starts at $QueuePtr (0) = 0$ on a fresh, empty set — the pointer begins at way 0.

WHY. FIFO (First-In First-Out) evicts by arrival order — first block in is the first block out, like a lunch queue. It never looks at whether a block was used again. Why would anyone want a policy that ignores hits? Cost: FIFO needs only $⌈ lo g_{2} n ⌉$ bits per set instead of a counter per box — for $n = 4$ that is a single 2-bit number.

PICTURE (Figure s04). The pointer sweeps in a circle around the four boxes.

Formula FIFO pointer update

$QueuePtr (t + 1) = {(QueuePtr (t) + 1) mod n QueuePtr (t) if this access is a miss that loads a block if this access is a hit$

$QueuePtr$ — the arrow; what it does: points at the box that will next receive a block (and, once the set is full, the box that gets evicted first).
$+ 1$ — after loading a block (whether into an empty way or over an evicted victim), step to the next box.
$mod n$ — wrap from box $n - 1$ back to box $0$ , making the boxes a circle.
the bottom line — a hit leaves the arrow frozen. This is the whole personality of FIFO.

Why the pointer advances on every load, not just evictions: the arrow marks arrival order. While the set fills (accesses that load into empty ways), the arrow steps forward to record where the next arrival goes. Once the set is full, the arrow keeps stepping in the same rhythm — now each step also names the oldest survivor as the victim. Both phases are "a block was loaded," so both advance the pointer by 1; only hits freeze it. FIFO needs no tie-break: the single pointer always names exactly one box.

Figure s04 — FIFO's ruler: one orange arrow (the queue pointer) starting at way 0, sweeping clockwise around the four boxes. A curved gray arrow shows the circular wrap from way 3 back to way 0.

Step 5 — Watch FIFO run the same sequence A B C D A E

WHAT. Same input, same boxes, but now the only state is the arrow, starting at $QueuePtr (0) = 0$ .

WHY. Running the identical stream through both policies isolates the difference to one decision. Watch the hit on $A$ do nothing.

PICTURE (Figure s05). The arrow is the orange marker; the star is the eviction.

Access	Boxes	QueuePtr after	What happened
$A$	$A, -, -, -$	1	miss, load into empty way 0, arrow steps →1
$B$	$A, B, -, -$	2	miss, load empty way 1, arrow →2
$C$	$A, B, C, -$	3	miss, load empty way 2, arrow →3
$D$	$A, B, C, D$	0	miss, load empty way 3, arrow wraps →0
$A$	$A, B, C, D$	0	hit on $A$ — arrow frozen, nothing moves
$E$	$E, B, C, D$	1	miss, set full, arrow=0 → evict way 0 ( $⋆ A$ ), load $E$ , arrow →1

Which box died? The arrow sat at way 0, which held $A$ . So ==FIFO evicts $A$ == — the very block LRU just saved. FIFO never noticed the recent hit. Notice the pointer advanced on all five loads (the four fills and the eviction) but stood still on the one hit — exactly the rule in Step 4.

Figure s05 — FIFO on the same stream, six columns. The orange arrow shows QueuePtr after each access; on the A-hit column the arrow does not move, and on the E column it evicts way 0 (A, red, starred) and steps to 1.

Step 6 — The third policy: Random, no ruler at all

WHAT. Random replacement keeps no history — no recency counters, no queue pointer. On a miss into a full set it picks a victim uniformly at random (every box equally likely) and overwrites it. On a miss with an empty way it still just fills the lowest empty way (the shared insertion rule of Step 1); only when the set is full does randomness kick in. Hits do nothing.

WHY. When you cannot afford to predict the future, you refuse to guess and flip a coin. This is cheaper than both alternatives — a tiny pseudorandom bit source, zero per-block state — and it is immune to the pathological patterns that trap FIFO (Step 8), because it has no rhythm for a pattern to fight against.

PICTURE (Figure s06). Four full boxes; a spinner points to whichever box the coin flips choose. On the same $A, B, C, D, A, E$ stream, Random might evict any of $A, B, C, D$ on the $E$ miss — each with probability $\frac{1}{4}$ . There is no single "the answer": that is the whole point.

Figure s06 — Random replacement: four full boxes A,B,C,D each labelled p = 1/4, with an orange spinner in the centre pointing at one box — the uniformly random victim on the E miss.

Step 7 — A yardstick so we can compare miss counts

WHAT. Define miss rate plainly: the fraction of accesses that were misses. And place it inside the cost of memory.

WHY. We keep saying one policy is "better." Better means fewer misses, because misses are slow. This step gives us the yardstick before the finale.

PICTURE (Figure s07). A bar showing hit time as a short green segment and miss penalty as a long red one; miss rate is how often you pay the red one.

Figure s07 — AMAT as a bar: a short green "Hit Time" segment followed by a long red "Miss Penalty" segment paid a Miss-Rate fraction of the time. Lower miss rate means fewer red penalties.

Naively you'd expect: more boxes → more blocks kept → fewer misses. For LRU that is guaranteed true — and the reason has a name we define now, before the anomaly, because it is the whole explanation.

Definition Fully associative, and the stack-algorithm property (defined before we use them)

Fully associative ::: a cache (or a single "frame pool") in which any block may live in any slot — there is exactly one set containing all the slots, so a block competes with every other block, not just those mapping to one set. In Steps 8–9 we use a fully-associative pool of "frames" (a frame = one slot in that single big set) so that the only thing deciding evictions is the replacement policy, with no address-mapping to muddy the count.
Stack algorithm ::: a replacement policy is a stack algorithm if, for every access sequence, the set of blocks it keeps in a cache of size $k$ is always a subset of the blocks it keeps in a cache of size $k + 1$ . Plain words: a bigger cache holds everything the smaller one held, plus more — it never drops a block the smaller cache kept.
- LRU is a stack algorithm → a bigger cache can only remove misses, never add them → LRU cannot suffer Belady's Anomaly.
- FIFO is not a stack algorithm → its size- $k$ contents can differ arbitrarily from its size- $(k + 1)$ contents → the anomaly is possible, as Steps 8–9 will show.

Step 8 — Belady's Anomaly, 3 frames: 9 misses

WHAT. Use a fully-associative FIFO (as just defined: one big pool of frames, any block in any frame) with the classic stream $1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$ and three frames. Count misses.

WHY. This is the setup half of the anomaly. We need the 3-frame count first so we have something to compare the 4-frame count against.

PICTURE (Figure s08). Twelve columns, each showing the hit/miss verdict after that access; misses marked in red.

Tracing FIFO (fill empty frames first, then evict oldest arrival; hits don't reorder):

step	1	2	3	4	1	2	5	1	2	3	4	5
hit/miss	M	M	M	M	M	M	M	H	H	M	M	H

That is 9 misses out of 12. The two hits on $1$ and $2$ near the end are what save it.

Figure s08 — 3-frame fully-associative FIFO on the classic stream. Each of the 12 columns is the requested block, red boxes = miss, green = hit; the tally reads 9 misses.

Step 9 — Belady's Anomaly, 4 frames: 10 misses (the impossible-feeling result)

WHAT. Same stream, same fully-associative FIFO, now with four frames. Count misses again.

WHY. We added capacity — one more frame — expecting fewer misses. Watch it get worse. This is the degenerate case that kills the "bigger is always better" intuition, and it is possible precisely because FIFO is not a stack algorithm (Step 7).

PICTURE (Figure s09). Same twelve columns, one extra frame; the extra room shifts which block is oldest at each eviction, so blocks get thrown out right before they're reused.

step	1	2	3	4	1	2	5	1	2	3	4	5
hit/miss	M	M	M	M	H	H	M	M	M	M	M	M

That is 10 misses — one more than with three frames.

Figure s09 — 4-frame fully-associative FIFO on the identical stream. Same red/green column layout as s08, but the tally now reads 10 misses — worse than the 3-frame cache.

The one-picture summary

WHAT. One figure stacking all three verdicts: the same stream, LRU vs FIFO vs Random victims side by side, plus the anomaly bars $9 \to 10$ .

WHY. Everything on this page reduces to two facts — what ruler each policy uses, and what happens when the ruler ignores usage.

Figure s10 — The whole page compressed: three labelled boxes (LRU→evicts B using USAGE, FIFO→evicts A using ARRIVAL, Random→any of A–D using NOTHING) on the left, and two bars on the right showing FIFO's 9 misses at 3 frames rising to 10 misses at 4 frames — the anomaly LRU's stack property forbids.

Recall Feynman retelling — say it back in plain words

Picture a shelf of four slots. While the shelf still has empty slots, every policy does the same boring thing: drop the new book into the next empty slot. The interesting decision only happens once the shelf is full and a new book arrives — one book must fall off.

LRU writes a little "last touched" number under every book. When a miss forces an eviction, it first reads those numbers and picks the book ignored longest, then loads the newcomer into that spot and stamps it fresh (number 0) while every other book ages by one. Re-reading a book resets its number, so re-reading protects it. In our run, re-reading $A$ meant $B$ (untouched longest) fell off — and afterward $C$ , the older survivor, became the stalest.

FIFO is lazier and cheaper: it keeps one arrow that just remembers whose turn it is to leave, going strictly by arrival order. The arrow starts at slot 0 and steps forward every time a book is loaded, wrapping around the shelf in a circle; re-reading a book does nothing to it. So in the exact same run, $A$ — the book we'd just re-read — got shoved off, because it arrived first.

Random keeps no notes at all: when the shelf is full it flips a coin and evicts whatever slot the coin names. Cheapest of all, occasionally unlucky, but impossible to trap.

Then the twist: with FIFO, giving the shelf a fifth slot made it drop more books (10 instead of 9) on a nasty repeating stream, because the extra slot shifted the arrow's rhythm so books got tossed just before they were wanted again. That's Belady's Anomaly. LRU can never misbehave that way — it is a "stack algorithm," meaning a bigger cache always keeps everything the smaller one kept — which is exactly why hardware leans on LRU-style rules despite their higher cost.

One line: LRU measures usage (safe, expensive); FIFO measures only arrival (cheap, trickable into getting worse with more memory); Random measures nothing (cheapest, coin-flip).

Recall Quick self-test

While the set still has empty ways, what does each policy do on a miss? ::: The same thing — fill the lowest-numbered empty way; no eviction. The policies only differ once the set is full. On an LRU full-set miss, do we choose the victim before or after writing the new block's recency? ::: Before — evict-then-update: read recencies, pick the max as victim, load the new block, then set it to 0 and age the survivors. What recency does a freshly loaded block get under LRU? ::: 0 — it was just accessed by definition. After the hit on $A$ in step 5, which block does FIFO evict on the next miss, and why? ::: $A$ (way 0) — the queue pointer sat at 0 and FIFO ignores the hit; arrival order alone decides. Why can LRU never show Belady's Anomaly? ::: LRU is a stack algorithm — its size- $k$ contents are always a subset of its size- $(k + 1)$ contents, so more capacity can only remove misses, never add them. In A,B,C,D,A,E which block does LRU evict, and why not $A$ ? ::: $B$ ; the hit on $A$ reset $A$ 's recency to 0, making $B$ (recency 3) the least recently used. On the same stream, which block does Random evict on the $E$ miss? ::: Any of $A, B, C, D$ , each with probability $\frac{1}{4}$ — Random keeps no history, so there is no single answer.

Related depth: exact vs pseudo-LRU cost trade-offs tie into Cache-conscious-programming; policies interact with 5.4.03-Write-policies-(write-through,-write-back), 5.4.06-Cache-coherence-protocols, and reappear for page frames in 5.5.02-Virtual-memory-and-TLBs.