Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 67 ยท Memory Hierarchy

Replacement and Write Policies

Learn how a cache chooses a victim (LRU, FIFO, random) and how it handles stores (write-through, write-back, write-allocate), with Python simulations.

A cache is small, so sooner or later it is full and a new block arrives. Something has to leave. The rule that picks the victim is the replacement policy. A second question comes up whenever the CPU executes a store: should the new value go to main memory right away, or only to the cache? That rule is the write policy. Neither choice changes what your program computes, but both change how fast it runs and how much traffic reaches memory.

In this lesson you will compare FIFO, LRU and random replacement on a few access patterns, then compare write-through and write-back caches by counting the bytes each one sends to memory. If the vocabulary of sets, ways and blocks is new, read Cache Memory Basics and Direct, Associative and Set-Associative Mapping first.

Where replacement matters

In a direct-mapped cache every block has exactly one possible line, so there is no choice to make. In a set-associative cache with N ways, a new block may go into any of the N lines of its set, and if all N are valid the policy must pick one. A fully associative cache is the extreme case: the whole cache is one set.

The policies below all work on one set at a time. The simulations use a single set so you can follow every step.

Three replacement policies

FIFO (first in, first out) evicts the block that has been in the set the longest. It is simple, needs only a queue pointer per set, and ignores how often a block is used. A block that is read constantly will still be thrown out when its turn comes.

LRU (least recently used) evicts the block that has gone unused the longest. It follows the idea of temporal locality from The Memory Hierarchy and Locality: if you used something recently, you will probably use it again soon. Every hit updates the recency order, which makes LRU the most expensive to implement exactly.

Random evicts any line in the set. It needs no history at all, and it avoids the worst-case patterns that can trap deterministic policies.

flowchart TD
  A["Access block B in a full set"] --> H{"Is B in the set?"}
  H -- "yes (hit)" --> U["LRU only: mark B as most recent"]
  H -- "no (miss)" --> V["Policy picks a victim"]
  V --> F["FIFO: oldest arrival"]
  V --> L["LRU: least recently used"]
  V --> R["Random: any line"]
  F --> N["Victim replaced by B"]
  L --> N
  R --> N

A hit changes state only under LRU; a miss always triggers the victim choice.

Here is LRU traced step by step on a 3-way set. The list is ordered from least recent to most recent, so the leftmost block is always the next victim.

Python LRU, one access at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the fourth access. Block A was loaded first, but touching it again moved it to the right end, so when D arrives the victim is B, not A. FIFO would have thrown A out, because A arrived first.

Comparing the policies on real patterns

No policy wins on every workload. The next program simulates one 4-way set with each policy over three traces. The random policy uses a fixed seed, so the numbers are reproducible.

Python FIFO vs LRU vs random on three traces

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output tells three stories:

  • Hot block plus a scan (A is used constantly while other blocks pass through once). LRU keeps A safe because A is always recent; it scores 17 hits against 13 for FIFO. FIFO evicts A on a schedule, regardless of use.
  • A loop slightly bigger than the set (5 blocks, 4 ways). Both FIFO and LRU score 0 hits: each block is evicted just before it is needed again. This is the classic LRU failure, called thrashing. Random gets 14 hits here precisely because it is not predictable.
  • A loop that fits (4 blocks, 4 ways). After the four compulsory misses everything hits, whichever policy you use. Replacement only matters when the working set does not fit.

Real hardware rarely implements exact LRU for 8 or 16 ways, because tracking a full ordering costs many bits and time per access. Designers use pseudo-LRU: a small binary tree of bits per set, where each bit points toward the half that was used less recently. It costs N - 1 bits for N ways and approximates LRU well.

Write policies: what happens on a store

Reads are easy: a hit returns data, a miss fetches the block. Writes raise a new problem, because the cache and memory now both hold a copy and the copies can disagree. Two decisions define a write policy.

1. When does memory find out?

  • Write-through: every store updates the cache line and also writes to memory immediately. Memory is always current. The price is traffic: each store costs a memory write, so designers put a small write buffer between cache and memory so the CPU does not wait.
  • Write-back: a store updates only the cache line and sets a dirty bit on it. Memory is out of date until that line is evicted, at which point a dirty line is written back and a clean line is simply dropped. Repeated stores to the same line cost one memory write in total.

2. What happens on a write miss?

  • Write-allocate: fetch the block into the cache first, then perform the write as a hit. This pays off when more accesses to that block follow.
  • No-write-allocate (write-around): send the write straight to memory and do not bring the block in. This avoids polluting the cache with data that is written once and never touched again.

The common pairings are write-back with write-allocate (most modern L1, L2 and L3 caches) and write-through with no-write-allocate (simple designs and some L1 caches in front of a write-back L2).

flowchart LR
  CPU["CPU store"] --> C{"Line in cache?"}
  C -- "hit" --> P{"Policy"}
  P -- "write-through" --> T["Update line and memory"]
  P -- "write-back" --> D["Update line, set dirty bit"]
  C -- "miss" --> A{"Allocate?"}
  A -- "yes" --> F["Fetch block, then treat as hit"]
  A -- "no" --> W["Write to memory only"]

The dirty bit is what lets a write-back cache delay and combine its memory writes.

Counting memory traffic

The simulator below is a small set-associative LRU cache that records how many bytes it reads from and writes to memory. The workload mimics a loop that reads a 256-byte table, updates a counter variable several times between reads, and finally fills a fresh 64-byte buffer with stores.

Python Write-through vs write-back traffic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table row by row:

  • Write-through, no-allocate never caches the counter or the buffer, because writes do not allocate. Each of the 56 stores goes straight to memory (56 times 4 bytes is 224 bytes written), and each one counts as a miss. Only the 48 table reads hit.
  • Write-through, allocate hits 99 times, since the counter now lives in the cache. It reads 80 more bytes than the previous row (the counter block and the four buffer blocks must be fetched), but it still writes 224 bytes, because every store is still forwarded.
  • Write-back, allocate has the same hits and reads, yet writes only 80 bytes: one dirty counter block (16 bytes) and the four dirty buffer blocks (64 bytes), each written once when flushed. Forty stores to the counter collapsed into a single memory write.

That collapse is the whole case for write-back: repeated stores to hot data cost almost nothing. The cost is complexity. Memory is stale, so when several processors share data, they need a protocol to find the freshest copy. You will meet that in Cache Coherence and Memory Consistency.

Dirty data is also why a power failure or a hardware reset can lose recent stores that never left a write-back cache. Operating systems and databases issue explicit flush instructions when they need data to reach memory or storage.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In which cache organisation is a replacement policy unnecessary?

    A direct-mapped block can live in only one line, so there is never a choice of victim. Associative caches must pick one.
  2. 2. A program loops over 5 blocks that all map to one 4-way set. What does LRU achieve after the first pass?

    In a cyclic pattern one larger than the set, the least recently used block is always the one needed next, so LRU evicts exactly the wrong block every time.
  3. 3. What does the dirty bit record?

    A write-back cache sets the dirty bit on a store. When the line is evicted, a dirty line must be written back to memory, while a clean one can simply be dropped.
  4. 4. Why is write-back with write-allocate a good match?

    After the block is fetched, repeated writes to it stay inside the cache and produce one memory write when the line is evicted.
  5. 5. Which statement about pseudo-LRU is correct?

    Exact LRU needs a full ordering of the ways, which is costly. Tree-based pseudo-LRU uses N - 1 bits for N ways and usually evicts a line that was not recently used.

Summary

  • Associative caches need a replacement policy to choose a victim: FIFO (oldest arrival), LRU (least recently used), or random.
  • LRU exploits temporal locality but can thrash on loops just larger than the set; random avoids such worst cases; real hardware often uses pseudo-LRU.
  • Replacement matters only when the working set does not fit in the set.
  • Write-through updates memory on every store; write-back sets a dirty bit and writes the block when it is evicted.
  • Write-allocate fetches the block on a write miss; no-write-allocate sends the write straight to memory.
  • Write-back with write-allocate is the common modern pairing because repeated stores to hot data cost one memory write.

Continue with Cache Performance and the Three Cs.