You have met the coherence problem in the parent note Cache coherence problem . There you saw one failure table and three example sketches. This page does the opposite of "sketch": it lists every kind of situation the coherence problem can throw at you, then works each one to the last message count so you never meet a case you haven't seen.
Before we start, let us re-earn the vocabulary so no symbol sneaks in unexplained.
Definition The words we will use (all re-defined here)
Line (or block) — a fixed-size chunk of memory (say 64 bytes) that a cache stores as one unit. A cache never holds "just variable X"; it holds the whole line X sits in.Valid copy — a cached line whose stored value still equals the true logical value. If it drifted, it is stale .Dirty line — a line a core wrote to, so its cache holds a newer value than main memory. (This word matters only for write-back caches, which delay pushing writes to memory.)Bus event — one message that must travel on the shared wire connecting cores: an invalidate, an update broadcast, a read-miss fetch, or a write-back flush. We count these because they are the cost of coherence — see Bus Traffic & Scalability .Write-invalidate — after a write, tell every other cache "your copy of this line is now invalid."Write-update — after a write, send the new value to every other cache holding the line.
Everything below is just these words applied to different starting conditions.
Coherence outcomes depend on who holds the line , what operation happens , which protocol enforces coherence, and when memory gets refreshed (write-through vs write-back). Here is the full grid of case-classes this topic can produce:
#
Case class
The variable being stressed
Covered by
C1
Single writer, other caches stale, no protocol
baseline bug
Ex 1
C2
Write-invalidate restores coherence
the invalidate cure
Ex 2
C3
Write-update restores coherence
the update cure
Ex 3
C4
Repeated writes , one writer (invalidate favoured)write-run length
Ex 4
C5
Producer/consumer , read-after-each-write (update favoured)sharing tightness
Ex 5
C6
Write-through vs write-back : is memory correct?when memory refreshes
Ex 6
C7
Degenerate: only one core caches the line (no sharer)zero other copies
Ex 7
C8
Degenerate: two cores only read , nobody writeszero writes
Ex 8
C9
Limiting case: N sharers , one write — how traffic scalesscaling with N
Ex 9
C10
Real-world word problem + exam twist (false sharing)different addresses, same line
Ex 10
Read the matrix as: rows C1–C3 are the three protocol behaviours; C4–C5 are when each protocol wins; C6 isolates the memory-freshness axis; C7–C8 are the degenerate (nothing-to-fix) cases; C9 pushes the sharer count to the limit; C10 is the sneaky one.
Throughout, the base scenario is: variable X starts at 5 in memory , cores are Core A and Core B (plus more when stated), caches are write-back unless a row says otherwise.
Worked example Example 1 — C1: no protocol, the raw bugCore A and B both cache X=5. A executes X=10 (write-back). Then B reads X. What value does B see?
Forecast: guess B's value and whether memory is fresh, before reading on.
A writes X=10 into its own line only. Why this step? A write with no protocol touches exactly one cache — A's. Nothing tells B.A's line is now dirty; memory still holds 5. Why this step? write-back means the new value stays in A's cache until eviction; it has not flushed.B reads X → B's copy is still marked valid → returns its own 5. Why this step? A read uses the local copy whenever it believes it is valid, and nothing invalidated it.
Answer: B reads 5 (stale); memory = 5 (also stale vs A).
Verify: Two bugs, as the parent promised — cache-vs-cache (B's 5 ≠ A's 10) and memory-vs-cache (memory's 5 ≠ A's 10). Consistent with the parent's forecast box. ✅
Worked example Example 2 — C2: write-invalidate cures itSame start. Now the system runs write-invalidate . A writes X=10, then B reads.
Forecast: how many bus events, and what does B finally read?
A writes X=10 → broadcasts one invalidate. Why this step? invalidate's rule: on a write, kill every other copy. That is 1 bus event.B marks its line Invalid. Why this step? an invalidated line can no longer be trusted; a future read must go fetch.B reads X → its line is Invalid → read miss → fetch fresh value (10). Why this step? the forced miss is the whole trick — silent staleness became a loud fetch. That is a 2nd bus event.
Answer: B reads 10 (coherent). Bus events = 2 (1 invalidate + 1 read miss).
Verify: Matches the parent's Example 1 (coherent) and Example 2's count of 2 for a single write. ✅
Worked example Example 3 — C3: write-update cures itSame start. Now write-update . A writes X=10, then B reads.
Forecast: message count and B's value?
A writes X=10 → broadcasts the new value 10 to all sharers. Why this step? update's rule: don't kill copies, refresh them. 1 bus event.B's line is overwritten in place with 10, stays valid. Why this step? update keeps the copy alive, so no future miss is needed.B reads X → local hit → returns 10. Why this step? the copy is already fresh; the read costs 0 bus events.
Answer: B reads 10 (coherent). Bus events = 1 (1 update, read is a free hit).
Verify: For a single write-then-read, update (1) beats invalidate (2). This is exactly the producer/consumer advantage the parent hinted at, seen at its smallest. ✅
Worked example Example 4 — C4: repeated writes, invalidate winsOne sharer (B). Core A writes X three times in a row, then B reads once. Count bus events for each protocol.
Forecast: which protocol is cheaper, and by how much?
Invalidate, write #1: A broadcasts invalidate → B invalid, A now has the line exclusively . 1 event.Invalidate, writes #2 and #3: A already owns the line alone → no other copies to kill → 0 events. Why this step? once you're the sole owner, there is nobody to notify — this is why runs are cheap. (See MESI Protocol for the "Exclusive/Modified" states that record ownership.)Invalidate, B's read: B is invalid → read miss → 1 event. Invalidate total = 2. Update, writes #1–#3: each write must broadcast the newest value → 3 events. B already has the line, so its read = 0. Update total = 3.
Answer: Invalidate = 2 events, Update = 3 events. Invalidate wins.
Verify: Matches the parent's Example 2 (2 vs 3). The gap grows with the write-run length — see Bus Traffic & Scalability . ✅
Worked example Example 5 — C5: producer/consumer, update winsA writes X once , then B reads it immediately , and this ping-pong repeats. Count events for one write-then-read round.
Forecast: flip the winner from Example 4?
Update: A writes → 1 update broadcast → B's copy is now fresh. B reads → local hit, 0. Update total = 1. Invalidate: A writes → 1 invalidate → B invalid. B reads → miss → fetch, 1. Invalidate total = 2.
Answer: Update = 1, Invalidate = 2. Update wins.
Verify: Same numbers as parent Example 3. Together Ex 4 and Ex 5 prove neither protocol is universally best — the traffic pattern decides. ✅
Worked example Example 6 — C6: ismemory correct? Write-through vs write-back
Isolate the memory-freshness axis. A writes X=10. Immediately after (no eviction, no protocol on memory yet), ask: what does main memory hold under each write policy? See Write-through vs Write-back .
Forecast: which policy leaves memory fresh?
Write-through: every write is pushed to memory at once → memory = 10 immediately. Why this step? that is the definition of write-through.Write-back: the write stays in A's cache as a dirty line; memory is untouched until eviction → memory = 5. Why this step? write-back trades freshness for fewer memory trips.But do other caches update? In both policies, B's cached copy is untouched unless a coherence protocol acts. Why this step? write policy is about the memory-vs-cache gap; coherence is about the cache-vs-cache gap — two independent axes.
Answer: write-through → memory = 10; write-back → memory = 5. Neither fixes B's stale copy.
Verify: This is the parent's steel-man made numeric: write-through fixes memory (5→10) but B still reads its own stale copy. ✅
Worked example Example 7 — C7 (degenerate): only one core caches the lineCore A is the only core with X cached. A writes X=10. How many coherence bus events under invalidate?
Forecast: with zero other sharers, is any coherence traffic needed?
A writes → protocol looks for other sharers → finds none. Why this step? the invariant is only threatened when another valid copy exists; here it doesn't.No invalidate is sent. Coherence bus events = 0.
Answer: 0 coherence events. (A memory write-back may happen later on eviction, but that is the write-policy axis, not coherence.)
Verify: Set N (number of other sharers) = 0 in the invalidate cost formula "invalidate cost = 1 if N ≥ 1 else 0". N=0 → 0. Degenerate case behaves as the invariant predicts. ✅
Worked example Example 8 — C8 (degenerate): all reads, no writesA and B both cache X and only ever read it. How many coherence events, ever?
Forecast: can two read-only copies ever be incoherent?
No write occurs → no copy ever changes. Why this step? incoherence is created only by a write (cache_i(X) := new). No write, no drift.Both copies stay valid and equal forever. Coherence events = 0.
Answer: 0 events; shared read-only data is trivially coherent.
Verify: This is the safe "Shared" state in MESI Protocol — multiple readers coexist with zero traffic. Confirms writes are the sole trigger. ✅
Worked example Example 9 — C9 (limiting): scaling to N sharersA line is cached (valid) by N cores. One of them writes it once. Give coherence events as a function of N for each protocol, then plug in N = 1, 4, 64.
Forecast: which protocol's cost grows with N?
Invalidate: the writer sends one broadcast invalidate; every other sharer drops its copy. With snooping (a shared bus, see Snooping vs Directory Coherence ) this is 1 event regardless of N . Why this step? a bus broadcast is heard by all at once.Update: the writer must deliver the value to each of the (N−1) other sharers. Cost grows as N−1 . Why this step? every sharer needs the actual bytes, not just a "you're stale" flag.Plug in: invalidate → 1, 1, 1. Update → N−1 = 0, 3, 63.
Answer: invalidate = 1 for all N; update = 0 (N=1), 3 (N=4), 63 (N=64).
Verify: As N→large, update traffic → ∞ while invalidate stays flat — this is why large multicores use invalidate. See Bus Traffic & Scalability . ✅
Worked example Example 10 — C10: real-world word problem + exam twist (false sharing)Word problem: A line holds two independent 4-byte counters packed together: hitsA at bytes 0–3 and hitsB at bytes 4–7 — one 8-byte line . Core A only ever writes hitsA; Core B only ever writes hitsB. They never touch each other's counter. Both keep the line cached, write-invalidate protocol. Core A writes hitsA 10 times; interleaved, Core B writes hitsB 10 times, alternating A,B,A,B,… Count invalidate events.
Forecast: since A and B touch different counters, guess "0 conflicts." Then read on — this is the twist.
Coherence tracks whole lines, not bytes. Why this step? the valid/invalid flag lives per line . A write to any byte invalidates the whole line in other caches.A writes hitsA → invalidates B's copy of the line (even though B only cares about hitsB). 1 event. Why this step? the protocol can't tell the writes are to disjoint bytes.B then writes hitsB → but B's line is now Invalid → read-for-ownership miss (1) → write → invalidate A's copy (1). A's next write repeats the cycle. Each of the 20 alternating writes triggers coherence traffic it "shouldn't."Count: first A-write invalidates B (1). Each subsequent write finds the line stolen away, so it costs a miss + an invalidate. Roughly 2 events per write after the first , ≈ 1 + 2·19 = 39 events — versus 0 if the two counters lived in different lines.
Answer: ≈39 bus events from data that never truly conflicts. This is False Sharing — the exam twist. Fix: pad the counters into separate cache lines → traffic drops to ~0.
Verify: Sanity: with A and B in separate lines, each core owns its line exclusively (Ex 7 logic) → 0 coherence events. The 39-vs-0 gap is entirely an artifact of line granularity, not real sharing. ✅
The figure plots coherence traffic for one write as the number of sharers N pale-yellow flat line is write-invalidate (always 1 broadcast). The chalk-pink rising line is write-update (N − 1 N = 2 N = 64 That crossing is the entire argument for why real CPUs are invalidate-based.
Recall Which protocol wins — quick self-testA tight producer/consumer loop (write, then the other core reads immediately, repeat) — invalidate or update? ::: Update — it avoids the read miss (Ex 5).
A single core writing the same line 100 times before anyone reads — which is cheaper? ::: Invalidate — one invalidate then silent ownership; update would broadcast 100 times (Ex 4).
Two counters in one line, written by two cores — what problem, and does it involve real data conflict? ::: False sharing; no real conflict — coherence tracks whole lines, not bytes (Ex 10).
Under write-back with no protocol, A writes X=10 then B reads: B's value and memory's value? ::: B reads stale 5; memory is also 5 (Ex 1).
Mnemonic The matrix in one breath"Writes cause coherence; reads and lone owners are free; invalidate scales, update ping-pongs, and lines — not bytes — are the unit."
