Replacement policies: LRU, FIFO, random, optimal; tracing sets

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Blocks 0, 4, 8, 0, 4, 8, 1 on a 4-line fully associative LRU cache: misses? from Lesson 4.2.4
• Comparators in an 8-way cache? from Lesson 4.2.2
• Tag-directory bits for 1,024 lines with 17-bit tags plus V and D? from Lesson 4.2.3

1 · The Hook

🎣

When a set is full and a new block arrives, someone must leave. Evict the wrong one and it is needed again a moment later. The replacement policy makes that choice, and the same reference sequence can give noticeably different miss counts under LRU and FIFO. GATE asks you to trace both.

2 · Predict First

🤔

A 3-line fully associative cache receives 2, 6, 10, 2, 14. When 14 arrives, which block does LRU evict, and which does FIFO evict?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

LRU evicts the block used least recently: 2 was just reused, so 6 goes. FIFO evicts the block loaded first: 2 (its reuse does not matter to FIFO).

The policies

• LRU (least recently used): evict the block whose last use is oldest. Exploits temporal locality; on every hit the block becomes most recent.
• FIFO (first in, first out): evict the block that has been in the cache longest; hits do not change the order.
• Random: pick any block. Cheap, surprisingly decent.
• Optimal (Belady's OPT/MIN): evict the block whose next use is farthest in the future (or never). Needs the future, so it cannot be built; it is the benchmark: no policy has fewer misses.
• LFU (least frequently used): evict the block used the fewest times.

Only associative caches (k ≥ 2) need a policy.

Tracing LRU vs FIFO (3 lines, blocks 2, 6, 10, 2, 14, 6, 2, 10)

LRU: 6 misses; FIFO: 5 misses. LRU is usually better, but not always.

Belady's sequence

Blocks 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5:

With FIFO, going from 3 to 4 lines increases misses from 9 to 10: Belady's anomaly. LRU and OPT never suffer it.

Implementation cost

• LRU for a k-way set: track the order of k blocks. A simple scheme keeps a log₂ k-bit age counter per line; exact LRU needs at least ⌈log₂ k!⌉ bits per set. Expensive for large k; real caches use approximations (pseudo-LRU).
• FIFO: a log₂ k-bit pointer per set (round-robin).
• Random: a random-number generator, no per-line state.

4 · Visual

LRU vs FIFO on a hit to block 2 (set holds 2, 6, 10; 2 was loaded first)

LRU : order by last USE   ->  6 10 2   (2 becomes most recent; 6 is next victim)
FIFO: order by LOAD time  ->  2 6 10   (unchanged; 2 is still next victim)

5 · Worked Examples

Example 1 Easy

A 2-way set holds blocks A (loaded first) and B. The CPU reads A, then needs C. Which block does LRU evict? FIFO?

Solution

LRU evicts B (A was just used); FIFO evicts A (loaded first).

Example 2 Medium

Belady's sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 on a 4-line fully associative cache with OPT. Misses?

Solution

6: compulsory misses for 1, 2, 3, 4; then 5 evicts 4 (used farthest); 1, 2, 3 hit; 4 misses (evicts 1, 2 or 3, none used again); 5 hits.

Example 3 GATE

A 4-line fully associative LRU cache receives 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Misses?

Solution

7 M, 0 M, 1 M, 2 M, 0 H, 3 M (evict 7), 0 H, 4 M (evict 1), 2 H, 3 H, 0 H, 3 H, 2 H → 6 misses.

6 · GATE Traps

⚠️

• FIFO ignores hits; LRU reorders on every hit.
• OPT evicts the block used farthest in the future; it is a benchmark, not a real policy.
• Belady's anomaly affects FIFO, not LRU or OPT.
• Direct-mapped caches have no replacement choice.

7 · Memory Hook

🧠

"LRU looks back at use, FIFO looks back at arrival, OPT looks forward."

8 · Connect the Dots

Chapter 4.2 is complete: mapping, address splits, tag storage, tracing and replacement. Chapter 4.3 measures performance: what happens on writes, how long a miss really takes, multilevel caches and how loop order changes the miss count.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksLRU trace

A 3-line fully associative LRU cache receives 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Number of misses?

Numerical answer: ________

Q2NAT2 marksFIFO trace

The same sequence on a 3-line fully associative FIFO cache. Number of misses?

Numerical answer: ________

Q3NAT1 markOPT

Belady's sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 on 3 lines with OPT. Misses?

Numerical answer: ________

Q4MCQ1 markAnomaly

Belady's anomaly (more lines giving more misses) can occur with:

• (A) Direct mapping only
• (B) FIFO
• (C) OPT
• (D) LRU

Q5MSQ2 marksPolicies

Which statements are true?

• (A) A direct-mapped cache needs no replacement policy.
• (B) FIFO evicts the block that has been in the cache longest.
• (C) LRU updates its ordering on every hit.
• (D) OPT can be built in hardware with a counter per line.

10 · Rule Card

• LRU: evict least recently used (hits reorder). FIFO: evict earliest loaded (hits don't). Random. OPT: evict farthest next use (benchmark). LFU: least used.
• Belady's anomaly: FIFO only.
• LRU state: log₂ k bits per line (counter scheme); ≥ ⌈log₂ k!⌉ per set exact.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

replacement policyLRUFIFOrandom replacementoptimal (Belady OPT/MIN)LFUBelady's anomalyLRU state bitspseudo-LRU

12 · Answer Vault