Cache coherence problem: Visual walkthrough — Hardware deep dive

Step 1 — Draw the machine before anything goes wrong

WHAT. Two little computers ("cores") sit side by side. Each has its own tiny fast notebook called a cache. Below them is one big slow book called main memory. Inside memory lives a single box labelled X — think of it as one number stored at one address. Right now that box holds the number 5.

WHY. Before we can talk about copies disagreeing, we must see the layout that lets copies exist at all: each core has a private notebook. That privacy is the seed of the whole problem. Caches are there for speed — reaching your own notebook is fast; walking down to the big book is slow.

PICTURE. Look at the two white boxes (the caches) — both are empty right now. Only the amber box in memory holds a value.

Step 2 — Both cores read: now there are three copies

WHAT. Core A reads X. It doesn't have X yet, so it walks to memory, finds 5, and copies it into Cache A. Then Core B does the same. Now X = 5 sits in three places at once: Cache A, Cache B, and memory.

WHY. Reading pulls a copy up into the private cache so the next read is fast. This is normal, correct, desirable behaviour — and it is precisely the act that creates the danger. Multiple valid copies of one address now exist.

PICTURE. Follow the two cyan arrows going up from memory into each cache. All three X boxes show the same amber 5 — everyone agrees. This agreement is the state we are about to break.

Step 3 — Core A writes. The bug is born.

WHAT. Core A changes X to 10. Because these are write-back caches (the parent note's setup), A writes the new value only into its own notebook — it does not immediately tell memory or Cache B. So: Cache A says 10; Cache B still says 5; memory still says 5.

WHY. Write-back is a speed trick: don't pay the slow trip to memory on every write; just scribble locally and flush later. But a local scribble touches one copy. The other two copies were never informed. This is the exact instant coherence dies.

PICTURE. The amber flash on Cache A shows the fresh 10. The two red ❌ marks sit on Cache B and memory — both are now stale (holding an old value that is no longer the truth).

Step 4 — Write the invariant we WANTED, and watch it snap

WHAT. Let's state, in symbols, the single rule that should always hold. We introduce three pieces of notation — each earned:

$the number core i has for address X cache_{i} (X) true/false: is core i ’s copy still trustworthy? Valid_{i} (X) "for every pair of cores i and j " \forall i, j$

The rule we want:

$\forall i, j : A’s copy trusted Valid_{i} (X) \land B’s copy trusted Valid_{j} (X) \Rightarrow ...then they must be equal cache_{i} (X) = cache_{j} (X)$

Read aloud: "If two cores both trust their copy of X, those copies must hold the same number." The symbol $\land$ means and; $\Rightarrow$ means then.

WHY. We write the rule down so we can point to the precise moment it breaks. At Step 3, both copies were still marked valid ( $Valid_{A} = Valid_{B} = true$ ), yet $cache_{A} (X) = 10 \neq = 5 = cache_{B} (X)$ . The and on the left is true; the equal on the right is false. The invariant is violated.

PICTURE. The green invariant sits on top; below it, the term-by-term breakdown lights up the offending clause in red — "both valid, yet not equal."

Step 5 — Core B reads its own stale copy (the crash)

WHAT. Core B now reads X. Its own notebook says 5 and is marked valid, so B trusts it and returns 5 — never walking to memory. But the true value is 10. B is now confidently wrong.

WHY. This is the payoff of the bug. B did nothing incorrect by its own rules — a valid cached copy is supposed to be usable without a memory trip. The whole failure is that "valid" lied. Note memory also still says 5, so even fetching from memory wouldn't save B here (that's the separate write-back-timing bug).

PICTURE. The red arrow shows B's read stopping inside its own cache — it never reaches memory. The returned value 5 is circled in red against the true value 10.

Step 6 — The fix is forced: kill stale copies. Only two ways exist.

WHAT. Go back to the broken invariant. A write set $cache_{i} (X) := new$ on core $i$ only. To restore the rule, we must destroy the mismatch. Logically there are exactly two moves:

$Invalidate: \forall j \neq = i : mark everyone else’s copy "not trusted" Valid_{j} (X) \leftarrow false$

$Update: \forall j \neq = i : push the new number into everyone else cache_{j} (X) \leftarrow new$

Here $j \neq = i$ means "every core except the writer," and $\leftarrow$ means "gets set to."

WHY. The invariant breaks only through the clause $Valid_{i} \land Valid_{j} \Rightarrow equal$ . To make a broken implication true again you either make its left side false (invalidate — turn a Valid off) or make its right side true (update — force the numbers equal). There is no third lever. So these are the only two protocol families that can exist — we didn't guess them, the logic squeezed them out.

PICTURE. Left panel: the invalidate move greys out Cache B and stamps it INVALID. Right panel: the update move flashes 10 into Cache B. Both make all trusted copies agree again.

Step 7 — Which fix wins? Count the arrows (the repeated-write case)

WHAT. Core A writes X three times in a row, then Core B reads once, with B as the only other sharer.

Invalidate: first write sends 1 invalidate; after that A owns the line exclusively, so writes 2 and 3 send nothing. B's read is then a miss ⇒ 1 fetch. Total = 2 bus events.
Update: each of the 3 writes broadcasts the new value ⇒ 3 updates; B already has it, so its read is free. Total = 3 bus events.

WHY. The bus (the shared wire all caches listen on) is the scarce resource — more messages means worse scaling. Update pays for every write even when nobody is reading. This is why real CPUs (MESI Protocol) are invalidate-based.

PICTURE. Two message-timelines stacked: invalidate fires once then goes quiet (2 amber ticks); update fires on every write (3 amber ticks).

Step 8 — The edge case that flips the answer (producer/consumer)

WHAT. Now A writes X once, and B reads it immediately, repeatedly (tight sharing).

Update: 1 write ⇒ 1 update; B's copy is refreshed, every later read is free ⇒ 1 event.
Invalidate: 1 write ⇒ 1 invalidate; B's very next read is now a miss ⇒ 1 extra fetch ⇒ 2 events.

WHY. When the reader wants the value right after each write, invalidate's "forced miss" is pure waste — the value was needed anyway. So neither protocol is universally best; the traffic pattern decides. This same "who touches what, when" reasoning is what Snooping vs Directory Coherence and False Sharing build on.

PICTURE. Mirror of Step 7: here update is the short timeline (1 tick) and invalidate is the longer one (invalidate + miss = 2 ticks) — the winner has flipped.

The one-picture summary

Everything above compressed into a single flow: three copies born → one write → invariant snaps → two (and only two) cures → traffic decides which cure.

Recall Feynman retelling — the whole walk in plain words

You and a friend each copy the scoreboard number 5 into your own notebook — now the number lives in three places and everyone agrees. You score and change your notebook to 10, but you tell no one. Your notebook, your friend's notebook, and the big board now hold three... well, two different numbers, yet your friend still trusts his 5. When he reads his notebook he confidently says "5" — wrong. The rule "if two people both trust their copy, the copies must match" just broke, and it broke in the one clause about both being trusted. To fix a broken "if-both-trusted-then-equal" rule you have exactly two moves: make one side not trusted (shout "cross out your number!" — invalidate) or make them equal (shout "change yours to 10!" — update). If you keep scoring over and over, shouting "cross it out" once is cheaper. If your friend needs the new score the instant you write it, shouting the new number is cheaper. That trade-off — not magic — is why real chips choose invalidate but the choice isn't free.

Connections

Parent: Cache coherence problem · Hinglish: 5.4.14 Cache coherence problem (Hinglish)
Write-through vs Write-back · MESI Protocol · Snooping vs Directory Coherence
Memory Consistency Models · False Sharing · Bus Traffic & Scalability