In Cache Mapping Techniques we decided where a block may live in the cache. Two practical questions were left open, and every real cache must answer both:
Replacement: when a new block must come into a set (or a fully associative cache) that is already full, which old block should be thrown out?
Writing: when the CPU stores to an address, should the change go to the cache only, to main memory too, or both? And what if the block is not in the cache at all?
The answers are called the replacement policy and the write policy. They have a big effect on the miss rate and on how much traffic flows to main memory. In this chapter we trace each policy by hand, see how hardware implements them, and solve the typical GATE numericals.
When Is a Replacement Policy Needed?
Direct-mapped cache: never. A block has exactly one possible line, so the block already in that line is the only candidate for eviction.
Set-associative cache: yes, but only among the k lines of the one set the new block maps to.
Fully associative cache: yes, among all lines.
And a replacement only happens on a miss when the set is full. If an invalid (empty) line exists in the set, it is used first.
The Replacement Policies
Random
Pick a victim at random (in hardware, usually from a simple counter or a linear-feedback shift register). It needs almost no state and works surprisingly well for large, highly associative caches, because no access pattern can consistently fool it. Some ARM cores have offered a pseudo-random option.
FIFO (First-In, First-Out)
Evict the block that has been in the set the longest, regardless of how often or how recently it was used. Hardware needs only a round-robin pointer per set (log2k bits). Its weakness: a heavily used block is evicted just because it arrived early.
LRU (Least Recently Used)
Evict the block whose last use is furthest in the past. It relies on temporal locality: something used recently will probably be used again soon, so the block that has gone unused the longest is the best guess for "not needed". LRU is the policy GATE assumes by default when it says "set associative with LRU".
LFU (Least Frequently Used)
Evict the block with the fewest accesses. It needs a counter per line and a tie-breaking rule. A block that was used heavily long ago can stay forever, so pure LFU is rare in CPU caches.
Optimal (Belady's MIN)
Evict the block that will be used furthest in the future (or never again). It gives the minimum possible number of misses for a given cache, but it needs knowledge of the future, so it cannot be built. We use it as a yardstick to judge how good a real policy is.
Worked Example: Tracing FIFO, LRU and Optimal
A fully associative cache has 3 lines (equivalently, one set of a 3-way cache). The block reference string is: 4, 1, 5, 4, 2, 4, 1, 4, 3, 2, 4, 3. The cache is initially empty. Count the misses for FIFO, LRU and Optimal.
The first three accesses (4, 1, 5) are compulsory misses for every policy; the cache becomes {4, 1, 5}. The policies differ only when a victim must be chosen.
FIFO
| # | Block | Result | Evicted (oldest) | Cache after |
|---|---|---|---|---|
| 1 | 4 | Miss | - | 4 |
| 2 | 1 | Miss | - | 4, 1 |
| 3 | 5 | Miss | - | 4, 1, 5 |
| 4 | 4 | Hit | - | 4, 1, 5 |
| 5 | 2 | Miss | 4 | 2, 1, 5 |
| 6 | 4 | Miss | 1 | 2, 4, 5 |
| 7 | 1 | Miss | 5 | 2, 4, 1 |
| 8 | 4 | Hit | - | 2, 4, 1 |
| 9 | 3 | Miss | 2 | 3, 4, 1 |
| 10 | 2 | Miss | 4 | 3, 2, 1 |
| 11 | 4 | Miss | 1 | 3, 2, 4 |
| 12 | 3 | Hit | - | 3, 2, 4 |
FIFO: 9 misses, 3 hits. Look at step 5: block 4 was just used at step 4, yet FIFO evicts it because it arrived first. It is needed again at step 6, causing another miss.
LRU
| # | Block | Result | Evicted (least recent) | Cache after |
|---|---|---|---|---|
| 1-3 | 4, 1, 5 | 3 misses | - | 4, 1, 5 |
| 4 | 4 | Hit | - | 4, 1, 5 |
| 5 | 2 | Miss | 1 | 4, 2, 5 |
| 6 | 4 | Hit | - | 4, 2, 5 |
| 7 | 1 | Miss | 5 | 4, 2, 1 |
| 8 | 4 | Hit | - | 4, 2, 1 |
| 9 | 3 | Miss | 2 | 4, 3, 1 |
| 10 | 2 | Miss | 1 | 4, 3, 2 |
| 11 | 4 | Hit | - | 4, 3, 2 |
| 12 | 3 | Hit | - | 4, 3, 2 |
LRU: 7 misses, 5 hits. Because block 4 is used every other access, LRU never evicts it. At step 5 the recency order (oldest first) is 1, 5, 4, so 1 goes.
Optimal
| # | Block | Result | Reasoning for the victim | Cache after |
|---|---|---|---|---|
| 1-3 | 4, 1, 5 | 3 misses | - | 4, 1, 5 |
| 4 | 4 | Hit | - | 4, 1, 5 |
| 5 | 2 | Miss | Next uses: 4 at #6, 1 at #7, 5 never → evict 5 | 4, 1, 2 |
| 6-8 | 4, 1, 4 | 3 hits | - | 4, 1, 2 |
| 9 | 3 | Miss | Next uses: 4 at #11, 1 never, 2 at #10 → evict 1 | 4, 3, 2 |
| 10-12 | 2, 4, 3 | 3 hits | - | 4, 3, 2 |
Optimal: 5 misses, 7 hits.
| Policy | Misses | Hits | Hit ratio |
|---|---|---|---|
| FIFO | 9 | 3 | 3/12 = 25% |
| LRU | 7 | 5 | 5/12 ≈ 41.7% |
| Optimal | 5 | 7 | 7/12 ≈ 58.3% |
No real policy can beat Optimal. On this string LRU closes half the gap between FIFO and Optimal, which is typical for programs with good temporal locality.
Belady's Anomaly: When More Cache Hurts
You would expect that a bigger cache never gives more misses. For FIFO this is not always true. Take the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 on a fully associative cache:
| Policy | 3 lines | 4 lines |
|---|---|---|
| FIFO | 9 misses | 10 misses (worse!) |
| LRU | 10 misses | 8 misses |
LRU and Optimal (and also LFU) are stack algorithms: the set of blocks held by a cache of n lines is always a subset of the blocks a cache of n + 1 lines would hold on the same string. Such policies can never show the anomaly. FIFO is not a stack algorithm. The same anomaly appears in page replacement in operating systems, because a page frame is just a "line" of a much bigger cache.
How Hardware Implements LRU
Exact LRU with Age Counters
Give each line in a k-way set a small counter of log2k bits holding its age rank (0 = most recently used, k − 1 = least recently used).
On a hit to a line with age c: every line in the set with age less than c increments by 1, and the hit line becomes 0.
On a miss: the line with age k − 1 is the victim. Every other line increments by 1, and the new block gets age 0.
4-way set, ages shown as [A B C D]
Start: A=0 B=1 C=2 D=3 (D is LRU)
Hit on C (age 2): A=1 B=2 C=0 D=3 (A, B were younger than 2 → +1)
Miss, new E: victim D (age 3) → A=2 B=3 C=1 E=0This costs k × log2k bits per set (8 bits for 4-way). The theoretical minimum is log2(k!) bits, because there are k! possible recency orders: ⌈log224⌉ = 5 bits for 4-way, but ⌈log240320⌉ = 16 bits for 8-way, and the update logic grows quickly. That is why true LRU is rarely built beyond 4 to 8 ways.
Tree Pseudo-LRU (PLRU)
A cheaper approximation uses a binary tree of k − 1 bits per set (3 bits for 4-way, 7 for 8-way). Each bit points towards the half that was used less recently. On every access, the bits on the path to the used line are set to point away from it. To pick a victim, follow the bits from the root.
b0
/ \
b1 b2 b = 0 means "victim is on the left"
/ \ / \ b = 1 means "victim is on the right"
L0 L1 L2 L3Trace the access sequence A, B, C, D, A, E in a 4-way set (A→L0, B→L1, C→L2, D→L3 as they fill):
| Access | b0 b1 b2 after | Note |
|---|---|---|
| A (L0) | 1 1 0 | point away from L0 |
| B (L1) | 1 0 0 | point away from L1 |
| C (L2) | 0 0 1 | point away from L2 |
| D (L3) | 0 0 0 | point away from L3 |
| A (L0) hit | 1 1 0 | point away from L0 |
| E miss | - | b0 = 1 → right; b2 = 0 → L2 (C) evicted |
True LRU would have evicted B (recency order B, C, D, A). PLRU picked C instead: it only remembers which half was used less recently, not a complete order. In practice the difference in miss rate is small, and the hardware saving is large.
Write Policies: What Happens on a Store?
Reads never change data, so a cache can always simply discard a block it read. Writes are harder: once the cache holds a newer value than memory, the two copies disagree, and that must be handled. There are two separate decisions.
Decision 1: Write Hit (Block Is in the Cache)
Write-through: every write updates both the cache and main memory.
Write-back (copy-back): a write updates only the cache and marks the line dirty. Main memory is updated only when the dirty block is evicted.
Write-through Write-back
CPU ── store x ──► cache ──► memory CPU ── store x ──► cache (dirty = 1)
(both updated) memory updated later,
only on evictionThe dirty bit (modified bit) is one extra bit per line. A clean line can be dropped silently on eviction; a dirty line must first be written back. This is why the eviction of a dirty block costs roughly two block transfers (write the old block, read the new one).
The Write Buffer
Pure write-through would make every store wait for slow main memory. Real write-through caches put a small write buffer (a FIFO queue) between the cache and memory: the CPU drops the write into the buffer and continues, and the buffer drains to memory in the background. The CPU stalls only when the buffer is full, for example during a burst of many stores.
Decision 2: Write Miss (Block Is Not in the Cache)
Write-allocate (fetch on write): bring the block into the cache first, then perform the write as a write hit.
No-write-allocate (write-around): write the data directly to main memory and do not load the block into the cache.
Any combination is possible, but two pairings are natural:
| Pairing | Why it makes sense |
|---|---|
| Write-back + write-allocate | Later writes to the same block will hit and stay in the cache. Used by most modern L1/L2/L3 data caches. |
| Write-through + no-write-allocate | Writes go to memory anyway, so loading the block gives little benefit unless it is read soon. |
Worked Example: Counting Memory Traffic
A direct-mapped cache has 4 lines; line = block mod 4. The access trace (R = read, W = write, number = block) is: R0, W0, W0, W1, R4, W4, R0, W0, W0, R8. Count the memory transfers for (a) write-through with no-write-allocate, and (b) write-back with write-allocate.
Blocks 0, 4 and 8 all map to line 0; block 1 maps to line 1.
(a) Write-Through + No-Write-Allocate
| Access | Result | Memory action | Line 0 | Line 1 |
|---|---|---|---|---|
| R0 | Miss | Fetch block 0 | 0 | - |
| W0 | Hit | Write word to memory | 0 | - |
| W0 | Hit | Write word to memory | 0 | - |
| W1 | Miss | Write word to memory (no allocate) | 0 | - |
| R4 | Miss | Fetch block 4 | 4 | - |
| W4 | Hit | Write word to memory | 4 | - |
| R0 | Miss | Fetch block 0 | 0 | - |
| W0 | Hit | Write word to memory | 0 | - |
| W0 | Hit | Write word to memory | 0 | - |
| R8 | Miss | Fetch block 8 | 8 | - |
Total: 4 block reads and 6 word writes (one per store). Memory is always up to date.
(b) Write-Back + Write-Allocate
| Access | Result | Memory action | Line 0 (dirty?) | Line 1 (dirty?) |
|---|---|---|---|---|
| R0 | Miss | Fetch block 0 | 0 (clean) | - |
| W0 | Hit | None, set dirty | 0 (dirty) | - |
| W0 | Hit | None | 0 (dirty) | - |
| W1 | Miss | Fetch block 1 (allocate) | 0 (dirty) | 1 (dirty) |
| R4 | Miss | Write back block 0, fetch block 4 | 4 (clean) | 1 (dirty) |
| W4 | Hit | None, set dirty | 4 (dirty) | 1 (dirty) |
| R0 | Miss | Write back block 4, fetch block 0 | 0 (clean) | 1 (dirty) |
| W0 | Hit | None, set dirty | 0 (dirty) | 1 (dirty) |
| W0 | Hit | None | 0 (dirty) | 1 (dirty) |
| R8 | Miss | Write back block 0, fetch block 8 | 8 (clean) | 1 (dirty) |
Total: 5 block reads and 3 block write-backs. Block 1 is still dirty in the cache and will be written back whenever it is evicted.
Which is better? It depends on the pattern. Here the lines thrash (0, 4, 8 conflict), so write-back moves whole blocks often. But imagine a loop that updates the same counter 1,000 times: write-through sends 1,000 writes to memory, while write-back sends one block, once, on eviction. Programs usually write the same blocks repeatedly, which is why write-back wins for most workloads.
Numericals on Write Policies
Example 1: Write-Back With Dirty Blocks
A write-back cache has a hit time of 1 cycle and a miss rate of 5%. Transferring a block between memory and cache takes 40 cycles. On average 25% of the blocks being replaced are dirty. Find the average memory access time.
Miss penalty = fetch new block + (fraction dirty × write back old block)
= 40 + 0.25 × 40 = 50 cycles
AMAT = hit time + miss rate × miss penalty
= 1 + 0.05 × 50
= 3.5 cyclesIf the cache were never dirty (for example, an instruction cache), the AMAT would be 1 + 0.05 × 40 = 3 cycles. The dirty write-backs cost an extra 0.5 cycle per access.
Example 2: Write-Through With and Without a Write Buffer
Cache access time is 10 ns and a main-memory access (a block fetch or a single word write) takes 100 ns. 80% of references are reads and 20% are writes. The read hit ratio is 0.9. On a read miss the block is fetched and then read from the cache. The cache is write-through with no-write-allocate. Find the average access time (a) with no write buffer, so every write waits for memory, and (b) with a write buffer that never fills.
Average read time = 0.9 × 10 + 0.1 × (100 + 10) = 9 + 11 = 20 ns
(a) every write waits for memory: write time = 100 ns
Average = 0.8 × 20 + 0.2 × 100 = 16 + 20 = 36 ns
(b) writes go into the buffer at cache speed: write time = 10 ns
Average = 0.8 × 20 + 0.2 × 10 = 16 + 2 = 18 nsThe write buffer halves the average access time here. That is why no real write-through cache is built without one.
GATE questions model write policies in slightly different ways (for example, whether a read miss costs tm or tc + tm). Always build the formula from the exact wording, as we did above, instead of memorising one formula.
Comparison Tables
Replacement Policies
| Policy | Victim | State per set (k-way) | Belady's anomaly possible? | Used in practice |
|---|---|---|---|---|
| Random | Any line at random | None (one global generator) | No guarantee (not a stack algorithm) | Some large caches, embedded cores |
| FIFO | Oldest arrival | log2k bits (pointer) | Yes | Simple caches, buffers |
| LRU | Least recently used | k log2k bits (counters) | No | Small associativity |
| Tree PLRU | Approximately LRU | k − 1 bits | No guarantee (not a stack algorithm) | Very common in CPU caches |
| LFU | Fewest uses | A counter per line | No (stack algorithm) | Rare in hardware caches |
| Optimal | Used furthest in future | Needs the future | No | Benchmark only |
Write Policies
| Aspect | Write-through | Write-back |
|---|---|---|
| Memory updated | On every write | Only when a dirty block is evicted |
| Extra bit per line | None (just valid) | Dirty bit |
| Memory traffic | High (every store) | Low (once per dirty eviction) |
| Eviction cost | Cheap (memory already current) | Dirty eviction needs a write-back |
| Memory consistency | Memory always up to date (easier for I/O and multiprocessors) | Memory can be stale; needs coherence handling |
| Helper hardware | Write buffer | Write-back buffer (optional) |
| Natural write-miss partner | No-write-allocate | Write-allocate |
Common Mistakes
Applying a replacement policy to a direct-mapped cache. There is no choice to make; the only candidate is the block in that line.
Treating a hit as "arrival" in FIFO. FIFO order depends only on when a block was loaded. Hits do not change it. In LRU, hits do update the order.
Running LRU over the whole cache in a set-associative trace. Recency is tracked separately inside each set.
Forgetting the write-back cost. A dirty victim adds a block transfer to the miss penalty.
Mixing up hit and miss policies. Write-through/write-back decide what happens on a write hit; write-allocate/no-write-allocate decide what happens on a write miss.
Thinking write-back loses data. Nothing is lost: the newest value lives in the cache and reaches memory on eviction (or when software flushes the cache).
GATE and Interview Questions
Q1. A 2-way set-associative cache has 4 sets and uses LRU. Blocks are accessed in the order 0, 8, 0, 16, 8, 0. How many misses?
All blocks are multiples of 4, so all map to set 0 (block mod 4). Trace: 0 miss {0}; 8 miss {0, 8}; 0 hit; 16 miss, LRU is 8 → {0, 16}; 8 miss, LRU is 0 → {8, 16}; 0 miss, LRU is 16 → {8, 0}. 5 misses, 1 hit.
Q2. How many bits per set does an exact LRU implementation with age counters need for an 8-way cache? What does tree PLRU need?
Age counters: 8 lines × 3 bits = 24 bits. Tree PLRU: 8 − 1 = 7 bits. The information-theoretic minimum for exact LRU would be ⌈log28!⌉ = ⌈log240320⌉ = 16 bits.
Q3. Why is write-back usually combined with write-allocate?
With write-back, writes that hit stay in the cache and cost no memory traffic. Allocating the block on a write miss means the following writes to the same block (very likely, due to spatial and temporal locality) will hit. Without allocation, every one of those writes would go to memory, losing the benefit of write-back.
Q4. A write-back cache has a miss rate of 4%, hit time 2 cycles, and block transfer time 50 cycles. 40% of replaced blocks are dirty. What is the AMAT?
Miss penalty = 50 + 0.4 × 50 = 70 cycles. AMAT = 2 + 0.04 × 70 = 4.8 cycles.
Q5. What is Belady's anomaly and which policies suffer from it?
It is the situation where increasing the number of lines (or page frames) increases the number of misses for some reference string. FIFO is the classic example. LRU and Optimal are stack algorithms and never show it, no matter what the reference string is.
Q6. Why is write-through simpler for systems with DMA or multiple processors?
Main memory always holds the latest value, so a DMA device or another processor reading memory never sees stale data. With write-back, the latest value may sit only in one cache, so extra hardware (cache coherence, or flushing) is needed. Multi-core coherence is covered in Multicore Processors & Cache Coherence.
Summary
A replacement policy chooses the victim on a miss in a full set; direct-mapped caches need none.
FIFO evicts the oldest arrival, LRU the least recently used, LFU the least frequently used, and Optimal the block used furthest in the future. On our example: FIFO 9, LRU 7, Optimal 5 misses.
FIFO can suffer Belady's anomaly; LRU and Optimal cannot.
Exact LRU needs k log2k bits per set with counters; tree PLRU approximates it with k − 1 bits.
Write-through updates memory on every write (use a write buffer); write-back updates memory only when a dirty block is evicted.
Write-allocate loads the block on a write miss; no-write-allocate writes around the cache. Common pairs: write-back + write-allocate, write-through + no-write-allocate.
Write-back miss penalty = block fetch + (dirty fraction × block write-back).
Next, Cache Performance & Multi-level Caches puts all of this into formulas for AMAT, CPI and execution time, and explains why modern CPUs use L1, L2 and L3.