Foundations — Replacement policies (LRU, FIFO, random)

Before you can compare LRU, FIFO, and Random on the parent topic, you must own every piece of vocabulary they lean on. We build each one in order, picture first.

1. Memory vs. Cache — the shelf and the library

Look at the figure: the big teal box on the right is main memory — huge, slow to reach. The small orange box on the left is the cache — only a few slots, but the CPU can grab from it almost instantly.

Why the topic needs this: replacement only ever happens because the cache is small. If the cache were as big as memory, nothing would ever need evicting, and this whole topic would vanish. Smallness is the source of the entire problem.

2. Block — the unit that moves

We label blocks with letters $A,B,C,D,\dots$ in every example. When we write "load $A$", we mean: copy the block named $A$ from main memory into a cache slot.

Why the topic needs this: the "item" you evict is always a whole block. The letters in every access sequence (like $A,B,A,C$) are block names. If you did not know that a block is the atomic unit, the sequences would be meaningless. See 5.4.01-Cache-organizationand-addressing for how memory addresses map to blocks.

3. Hit, Miss, and Eviction — the three events

The picture shows the decision as a fork: "Is the block here?" → yes = hit (green path), no = miss (orange path) → "Is there a free slot?" → no = evict someone first.

Why the topic needs this: the replacement policy runs only at the eviction step. Hits never trigger it. Misses trigger it only when the cache is already full. Every policy is precisely a rule for that one red box.

4. Set and Way — where a block is allowed to live

An n-way associative set has $n$ slots (ways numbered $0,1,\dots ,n-1$). A 2-way set has 2 slots; a 4-way set has 4.

In the figure the cache is drawn as rows (sets) and columns (ways). A new block goes to its row, then the policy decides which column to overwrite when the row is full.

Why the topic needs this: replacement is always a within-a-set decision. When the parent says "2-way set-associative cache with blocks A and B", it means one row holding two blocks — and eviction picks between exactly those two. The number $n$ is the number of candidates the policy chooses among.

5. Recency and Insertion order — the two clocks

The three policies differ only in what they remember. Two notions of "old" exist, and confusing them is the classic trap.

Why the topic needs this: the entire difference between LRU and FIFO is which clock they watch. A block hit ten times in a row is "fresh" by recency but still "old" by insertion order. That gap is where FIFO can throw out a hot block.

6. The recency counter — reading the LRU formula

The parent writes LRU with a counter per block:

${\text{Recency}}_i(t+1)=\{\begin{array}{ll}0& \text{if block }i\text{ accessed at time }t\\ \min ({\text{Recency}}_i(t)+1,n-1)& \text{otherwise}\end{array}$

Let us decode every symbol so it reads like plain English.

• $i$ — which block (an index, block number $0$ through $n-1$).
• $t$ — the time step: a counter that ticks up by one on every access. $t$, then $t+1$, is "now, then next".
• ${\text{Recency}}_i(t)$ — a number attached to block $i$: 0 means "just used", and a bigger number means "staler". The maximum $n-1$ means "coldest possible".
• The two-line brace $\{\begin{array}{l}\dots \end{array}$ means "pick the top line if its condition holds, else the bottom line."
• $\min (x,n-1)$ — "take $x$, but never let it exceed $n-1$." Why cap it? Because with $n$ blocks the oldest possible rank is $n-1$; going higher is meaningless.
• $\mathrm{mod}n$ (used later in FIFO) — the remainder after dividing by $n$. It makes a counter wrap around: for $n=4$, counting $0,1,2,3$ then $\mathrm{mod}4$ sends the next value back to $0$. This is how a pointer cycles through the ways forever.

Why the topic needs this: without decoding $i$, $t$, $\min$, $\mathrm{mod}$, and the cases brace, the LRU and FIFO update rules on the parent page are unreadable. Now every symbol is earned.

7. Miss rate and AMAT — why any of this pays off

The parent measures every policy by how it moves this number, through:

$\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$

• Hit Time — how long a hit takes (small).
• Miss Penalty — the extra cost of going to memory on a miss (large).
• The product $\text{Miss Rate}\times \text{Miss Penalty}$ is the average extra time added per access. Because Miss Penalty is big, even a tiny drop in Miss Rate is a large win — that is why a smart eviction rule matters at all.

Why the topic needs this: it is the scoreboard. Every claim like "LRU beats FIFO on this trace" is really a claim about this number. This all rests on Temporal-and-spatial-locality — the reason past behavior predicts the future.

How the foundations feed the topic

Equipment checklist

Cover the right side; recover each from the picture in your head.

Next: return to the parent topic and read the LRU/FIFO/Random mechanisms — every symbol there is now defined. Related prerequisites: Working-set-model, Cache-conscious-programming, 5.5.02-Virtual-memory-and-TLBs.