Write policies — write-through, write-back, write-allocate: Worked examples

Before we start, the two independent axes (from the parent), restated so nothing is used before it's named:

On a write HIT → write-through (update cache and memory now) or write-back (update cache only, set the dirty bit, tell memory later).
On a write MISS → write-allocate (fetch the block into cache first, then write) or no-write-allocate (write straight to memory, leave cache alone).

The dirty bit is one extra bit per cache line meaning "this cached copy has been changed and memory does not know yet." dirty=0 means cache and memory agree; dirty=1 means memory is stale.

The scenario matrix

Every write question is one cell of this grid. Our job: make sure every cell has a worked example.

Cell	Case class	What it stresses
C1	Write HIT, write-back	Does memory stay untouched? Does `dirty` flip to 1?
C2	Write HIT, write-through	Does memory get written every time?
C3	Write MISS, write-allocate	Block fetched, then written as a hit
C4	Write MISS, no-write-allocate	Straight to memory, cache untouched
C5	Eviction of a dirty block	The one forced memory write-back
C6	Eviction of a clean block	Silent discard, zero memory writes
C7	Zero / degenerate input ( $m = 0$ , or $d = 0$ )	Limiting behaviour of the cost formula
C8	Limiting input ( $m \to 1$ , or $d = 1$ )	Worst case, when write-back loses its edge
C9	Real-world word problem (`memset` streaming)	Why no-write-allocate exists
C10	Exam twist (mixed WT+write-allocate)	The "unnatural" pairing, counting both costs

The cost model we reuse (from the parent) — every symbol earned:

The worked examples

C1 + C2 — a HIT under both hit-policies

Worked example Example 1 — one write that hits, two policies (cells C1, C2)

Block for address x is already resident and clean. CPU issues W x. Count memory writes under (a) write-back and (b) write-through.

Forecast: guess how many DRAM writes each causes before reading on.

(a) Write-back: write the new value into the cache line only; set dirty=1. Why this step? Write-back defers memory traffic — the dirty bit records the debt instead of paying it now. Memory writes so far: 0.
(b) Write-through: write the cache line and push the same value to memory. Why this step? Write-through's defining rule is "memory is never behind," so every hit costs one memory write. Memory writes: 1.

Verify: In (a), if we read x next it comes from cache — value is correct, and memory is allowed to be stale because dirty=1 flags it. In (b), memory and cache hold the same value, so a DMA engine reading memory directly would see the fresh value. Both correct; write-back just paid less. Answer: 0 vs 1.

C3 + C4 — a MISS under both allocate-policies

Worked example Example 2 — one write that misses, two policies (cells C3, C4)

Block for x is not in cache. CPU issues W x. Under (a) write-allocate and (b) no-write-allocate, how many block fetches and memory writes happen, and is the block cached afterward?

Forecast: which policy leaves x in cache?

(a) Write-allocate: fetch the whole block from memory into a cache line (1 fetch), then write the new value into that line. Why this step? Allocate bets you'll touch this block again, so it pays a fetch up front to make future accesses hits. Fetches: 1. If paired with write-back, memory writes now: 0 (deferred); the line is cached with dirty=1.
(b) No-write-allocate: send the value straight to memory; do not touch any cache line. Why this step? No-allocate bets this is a one-off write not worth a cache slot. Fetches: 0, memory writes: 1, block not cached.

Verify: After (a) a subsequent R x is a hit (block resident). After (b) a subsequent R x is a miss (block never loaded). This is exactly the trade: (a) spends a fetch to buy future hits; (b) spends nothing but caches nothing. Answer: fetches 1 vs 0, cached yes vs no.

C5 + C6 — eviction of dirty vs clean

The following figure shows both eviction paths on one cache line.

Figure — Write policies — write-through, write-back, write-allocate

Worked example Example 3 — evicting a dirty block vs a clean block (cells C5, C6)

A cache line currently holds block A. We must load block B (they map to the same line, so A is the victim). Count memory writes caused by the eviction when (a) A has dirty=1, (b) A has dirty=0.

Forecast: how many memory writes does each eviction cost?

(a) dirty=1: before overwriting, write A's whole block back to memory, then load B. Why this step? dirty=1 means memory's copy of A is stale; if we discarded silently the update to A would be lost forever. Memory writes: 1 (look at the red write-back arrow in the figure).
(b) dirty=0: memory already matches A, so just overwrite the line with B. Why this step? A clean copy carries no debt — discarding it loses nothing. Memory writes: 0 (the green discard path).

Verify: The dirty case's cost is the $d t_{m}$ term in $T_{w b}$ ; the clean case is why that term is multiplied by $d < 1$ and not by $1$ . If every victim were clean ( $d = 0$ ), eviction would never write memory — checked next in C7. Answer: 1 vs 0.

C7 — degenerate inputs to the cost formula

Worked example Example 4 — the "perfect locality" limit (cell C7)

Use $t_{c} = 1$ , $t_{m} = 50$ . Evaluate $T_{w b}$ for two degenerate inputs: (a) miss rate $m = 0$ ; (b) dirty fraction $d = 0$ with $m = 0.05$ .

Forecast: what happens to the slow $t_{m}$ term when $m = 0$ ?

(a) $m = 0$ : $T_{w b} = t_{c} + 0 \cdot t_{m} (1 + d) = t_{c} = 1$ . Why this step? With zero misses every write is a cache hit costing only $t_{c}$ ; the memory term vanishes entirely. This is the best case — write-back touches DRAM never.
(b) $d = 0$ , $m = 0.05$ : $T_{w b} = 1 + 0.05 \cdot 50 \cdot (1 + 0) = 1 + 2.5 = 3.5$ . Why this step? With no dirty victims, misses still cost a fetch ( $m t_{m}$ ) but never a write-back, so the $(1 + d)$ factor collapses to $1$ .

Verify: Compare (a) to write-through at the same point: $T_{w t} = t_{c} + t_{m} = 51$ regardless of $m$ . Even with $m = 0$ , write-through still pays $51$ because it writes memory on hits too — precisely the traffic write-back eliminates. Answers: 1 and 3.5.

C8 — worst-case limit, where write-back loses its edge

The next figure plots $T_{w b}$ against $T_{w t}$ as the miss rate sweeps from good to terrible.

Worked example Example 5 — when does write-back stop winning? (cell C8)

Same $t_{c} = 1$ , $t_{m} = 50$ . Take the worst case $d = 1$ (every victim dirty). Find the miss rate $m^{⋆}$ at which $T_{w b} = T_{w t}$ .

Forecast: guess whether write-back ever costs more than write-through.

Set the costs equal: $t_{c} + m t_{m} (1 + d) = t_{c} + t_{m}$ . Why this step? The crossover is exactly where the two policies cost the same; beyond it write-back is worse.
Cancel $t_{c}$ and $t_{m}$ : $m (1 + d) = 1$ . With $d = 1$ : $2 m = 1 \Rightarrow m^{⋆} = 0.5$ . Why this step? Algebra isolates the miss rate; the $t_{m}$ magnitude drops out, so the crossover depends only on $m$ and $d$ .

Verify: At $m = 0.5, d = 1$ : $T_{w b} = 1 + 0.5 \cdot 50 \cdot 2 = 1 + 50 = 51 = T_{w t}$ . ✔ Equal, as claimed — see where the two curves cross in the figure. For $m > 0.5$ write-back would actually be worse, but such miss rates mean a nearly useless cache; real hot data sits far left where write-back dominates. Answer: $m^{⋆} = 0.5$ .

C9 — real-world word problem

Worked example Example 6 —

memset on a huge array (cell C9) You zero a 4096-byte buffer you will never read back. Block size = 64 bytes, so there are $4096/64 = 64$ blocks. Compare memory-block transfers (fetches + write-backs) under (a) write-back + write-allocate versus (b) write-through + no-write-allocate. Assume each block is fully overwritten and every allocated line is dirty on eviction.

Forecast: which policy wastes bandwidth fetching blocks you're about to obliterate?

(a) WB + write-allocate: each of the 64 blocks misses on its first write → fetch it (64 fetches), then all writes to it hit. Later each dirty line is evicted → written back (64 write-backs). Why this step? Allocate insists on fetching before writing, even though we overwrite the whole block — the fetch is pure waste. Transfers: $64 + 64 = 128$ .
(b) WT + no-write-allocate: each write misses and goes straight to memory, no fetch, nothing cached. There are $4096/64 = 64$ block-writes worth of data. Why this step? No-allocate never fetches a block just to overwrite it; write-through streams the data out. Transfers: 64.

Verify: No-write-allocate does half the memory traffic here ( $64$ vs $128$ ) and pollutes zero cache lines. This is why streaming/memset-style code favours no-write-allocate — the "bet" that you won't reread pays off. Answer: 128 vs 64.

C10 — the exam twist: the unnatural pairing

Worked example Example 7 — write-through + write-allocate (cell C10)

The rare pairing. Stream on a fresh cache, all mapping to one line: W x; W x; R x. Count memory writes and fetches for WT + write-allocate.

Forecast: does allocating on a write-through miss save any memory writes?

W x — miss → write-allocate fetches the block (1 fetch), writes the cache line, and — because it's write-through — writes memory too (1 memory write). Why this step? You pay the allocate cost and the through cost; the two costs stack.
W x — hit → write cache and memory again (1 memory write). Why this step? Write-through writes memory on every hit; allocating earlier bought you nothing on the memory-write side.
R x — hit → read from cache, no memory traffic. Why this step? Here the fetch from step 1 did help: the read is a hit.

Verify: Totals — fetches 1, memory writes 2. Compare: pure WT + no-allocate on the same stream writes memory on both W x (2 writes) and never fetches, so 2 memory writes, 0 fetches — and the R x then misses. So WT+write-allocate spent an extra fetch to make the read a hit but saved no write traffic. That's why it's "unnatural": you inherit allocate's fetch cost with none of write-back's write savings. Answers: 1 fetch, 2 memory writes.

One consolidated trace (ties C1, C3, C5 together)

Worked example Example 8 — full trace, write-back + write-allocate (cells C3→C1→C5)

Fresh cache. x and y map to the same line. Stream: W x; W x; R x; W y. Count total memory writes.

Forecast: how many times does DRAM get written across the whole stream?

W x — miss (C3) → fetch block, write, dirty=1. Memory writes: 0.
W x — hit (C1) → write cache only, dirty=1. Memory writes: 0.
R x — hit → read cache. Memory writes: 0.
W y — miss, victim is x with dirty=1 (C5) → write x's block back (1 memory write), then fetch/write y. Memory writes: 1.

Verify: Total memory writes = 1, all three of x's writes collapsed into that single eviction write-back. Under write-through the same stream would write memory on steps 1, 2, and 4 (no-allocate) — 3 memory writes. The $3 \to 1$ collapse is locality captured by the dirty bit exactly as the parent's Example 1 claimed. Answer: 1.

Recall

Recall Every cell, one line each

HIT + write-back memory writes for one write ::: 0 (dirty bit set instead) HIT + write-through memory writes for one write ::: 1 (every write hits DRAM) MISS + write-allocate: block cached afterward? ::: Yes (fetched then written) MISS + no-write-allocate: block cached afterward? ::: No (written straight to memory) Eviction of a dirty block costs ::: 1 memory write-back Eviction of a clean block costs ::: 0 memory writes $T_{w b}$ when miss rate $m = 0$ ::: $t_{c}$ (memory term vanishes) Crossover miss rate for $d = 1$ (WB vs WT) ::: $m^{⋆} = 0.5$ Why memset prefers no-write-allocate ::: avoids fetching blocks it will fully overwrite

See also: Cache Memory Fundamentals, Cache Replacement Policies, Memory Hierarchy and AMAT, Write Buffers and Store Buffers, Cache Coherence — MESI, DMA and I/O Consistency.