Cache Coherence
Imagine two CPU cores each keep a private copy of variable `x = 0` in their own cache. Core A writes `x = 1`. But Core B's cache still holds the stale value `0`. If Core B reads `x` next, which answer is correct? Without a fix, the two cores simply disagree about the state of shared memory. Any program relying on that shared variable — a lock, a counter, a queue — silently breaks. This is the cache coherence problem. It exists precisely because Multicore Processors and Thread-Level Parallelism gives every core its own fast private cache. Yet all cores still share one logical memory. Caching is essential for performance. Without it, every load and store would hit slow main memory. But private caching plus shared data creates a risk. Multiple copies of the same memory location can drift out of sync. Cache coherence protocols are the hardware machinery that prevents this drift. They guarantee that all cores eventually observe a single, agreed-upon view of every memory location. Coherence protocols matter because every commercial multicore chip implements one. This ranges from a phone's ARM cluster to a 64-core server Xeon. They are invisible to programmers, in the sense that ordinary loads and stores "just work" across cores. Yet they are among the most intricate pieces of hardware/software co-design in a modern processor. They involve finite-state machines, interconnect bandwidth, and subtle races. Getting coherence wrong produces bugs that appear only under specific timing. They surface on specific hardware, once in a billion instructions. This is the worst kind of bug to debug. This article builds the coherence problem from first principles. It derives the snooping approach to solving it. It works through the classic MSI protocol state machine in full detail. This includes its finite-state diagram, a worked multi-core trace, and the performance/correctness tradeoffs. These tradeoffs motivate later refinements (MESI, MOESI). They also set up the deeper question of Memory Consistency Models: coherence fixes per-location agreement, but consistency governs the global ordering of operations on different locations.
- Private per-core caches sharing one memory can hold stale/conflicting copies of the same address — the cache coherence problem.
- Coherence is usually defined by two guarantees: write propagation (updates become visible) and write serialization (all cores see writes to one location in the same order).
- Snooping protocols broadcast every cache's bus transactions to all other caches over a shared bus; each cache "snoops" and reacts.
- MSI (Modified/Shared/Invalid) is the canonical baseline protocol: three states per cache line, transitions driven by local reads/writes and snooped bus messages.
- Coherence guarantees consistency per memory location only; it says nothing about ordering across different locations — that is the job of a memory consistency model.
- Real chips extend MSI to MESI/MOESI to cut needless bus traffic, and use directories instead of broadcast snooping at large core counts.
Cache coherence keeps every core's private copy of a shared memory location honest by forcing all writes to that location to be seen, in the same order, by every core.
The idea
Formally, a memory system is coherent if it satisfies two properties for every individual memory location (address). First, write propagation: a write by one core eventually becomes visible to reads by all other cores — no core can be stuck seeing a stale value forever. Second, write serialization: writes to the same location, from any cores, appear to occur in some single total order, and every core observes writes to that location in that same order. Equivalently, all cores agree on a single sequence of values that a given memory location takes on over time. Note carefully what coherence does not promise. It says nothing about the relative order of operations on different addresses. If core A writes `x` then `y`, coherence alone permits core B to observe the write to `y` before the write to `x`. Reasoning about cross-address ordering is the province of a memory consistency model, a separate (and stricter) contract layered on top of coherence. Coherence is the "per-line correctness" layer; consistency is the "global ordering" layer built above it. The dominant hardware mechanism for enforcing coherence at moderate core counts is snooping: every cache is connected to a shared broadcast medium (historically a bus, today often a broadcast-capable ring or mesh), and every cache continuously "snoops" (monitors) every transaction issued by every other cache. When core A's cache issues a bus transaction — for example, "I intend to write address `0x1000`" — every other cache sees that transaction on the shared wire at the same instant and reacts by invalidating or updating its own copy of that line, if it has one. Because the bus is a single serializing medium (only one transaction can be granted the bus at a time), the order in which transactions appear on the bus automatically gives a global total order for all writes to any one address — which is exactly write serialization. Each cache line carries a small coherence state (e.g., Modified, Shared, Invalid) that records whether the line is private/dirty, shared/clean, or absent, and a finite-state machine governs how that state changes in response to local CPU requests and snooped bus messages.
How it works
The canonical teaching protocol is MSI, named for its three per-line states:
- M (Modified): this cache holds the only copy, and it is dirty (different from memory) — the cache owns write permission.
- S (Shared): this cache holds a clean copy, and other caches may hold the same clean copy — read-only.
- I (Invalid): this cache does not have a valid copy of the line.
Each core's cache controller reacts to two kinds of events: processor requests (PrRd = local read, PrWr = local write) issued by its own CPU, and bus messages (BusRd, BusRdX, BusUpgr) snooped from the shared interconnect, issued by other caches' controllers. The controller for a given line runs independently of every other line, so we can describe the FSM for a single cache line in isolation.
Bus message vocabulary (issued by a cache to request permission):
- `BusRd` — "I want to read this line" (issued on a local read miss to a line not held anywhere, or held only clean elsewhere).
- `BusRdX` — "I want to write this line, invalidate everyone else" (issued on a local write to a line not owned exclusively).
- `BusUpgr` — "I already have it Shared, just invalidate other copies" (cheaper than `BusRdX`, avoids re-fetching data you already hold).
- Any cache holding the line in M must supply the data (flush/writeback) when it snoops a `BusRd` or `BusRdX` for that address, since memory itself may be stale.
``` STATE MACHINE for one cache line, per cache (MSI protocol) State ∈ {M, S, I} -- initial state = I on PrRd (local CPU read): if state == I: issue BusRd on the bus
# if some other cache is in M, it must write back and transition to S
# this cache loads the line and transitions to S state := S elif state == S or state == M:
# cache hit, no bus transaction needed return data # state unchanged on PrWr (local CPU write): if state == I: issue BusRdX on the bus # fetch + invalidate others state := M elif state == S: issue BusUpgr on the bus # already have data, just invalidate others state := M elif state == M:
# already exclusive & dirty, write locally return # state unchanged on snoop BusRd (another cache wants to read this address): if state == M: flush (write back) dirty data to memory / forward to requester state := S # both caches now share clean copy elif state == S: pass # no action needed, both stay S elif state == I: pass # we don't have it, ignore on snoop BusRdX (another cache wants to write this address): if state == M: flush (write back) dirty data state := I # must give up ownership entirely elif state == S: state := I # invalidate our stale-about-to-be copy elif state == I: pass on snoop BusUpgr (another cache already has data, wants exclusive): if state == S: state := I # give up our copy, we're now stale
# (cannot occur while we are in M, since owner is unique) ``` The state machine above lives inside every cache's controller, replicated per line. When core A's controller issues `BusRdX`, every other core's controller for that same address independently runs its own `on snoop BusRdX` transition at essentially the same moment, because the bus broadcasts the request to all listeners simultaneously. This simultaneity — enforced by the bus's arbitration hardware, which grants exactly one transaction ownership of the bus at a time — is what turns "everyone reacts to the same sequence of events" into "everyone agrees on the order of writes."
Complexity & correctness
Space overhead. Each cache line needs only `⌈log₂ 3⌉ = 2` extra state bits (M/S/I plus the existing valid bit reused). For a cache with `L` lines this is `O(L)` bits — negligible compared to line data (typically 512 bits for a 64-byte line), so coherence state costs roughly 0.4% extra storage per line. This is a constant-factor overhead, not a scaling problem, at the level of a single cache.
Bus/interconnect bandwidth. This is the real cost driver. Every cache miss that needs new data, every write to a shared line, and every eviction of a modified line generates a broadcast bus transaction seen and processed by all N caches. Under naive snooping, each cache controller must inspect (snoop) every transaction on the bus, so the total snoop work across the system scales as `O(N)` per bus transaction, and a shared bus itself has bounded bandwidth independent of `N`. This is why pure broadcast snooping is typically used only up to roughly 8–32 cores; beyond that, chips switch to directory-based coherence, where a directory tracks exactly which caches hold each line, turning broadcasts into point-to-point messages sent only to actual sharers — trading a directory-storage cost (extra bits per memory block, or a distributed directory) for interconnect scalability. Snooping and directories solve the identical correctness problem; they differ only in how the "who has this line, and who must I tell" information is obtained (broadcast-and-listen vs. explicit-record).
Correctness argument. We must show MSI actually satisfies both coherence properties. Write serialization. At any moment, at most one cache may hold a line in state M (the FSM never lets two controllers reach M for the same address: to enter M a cache must issue `BusRdX`/`BusUpgr`, which the bus arbiter grants to only one requester at a time, and every other cache's snoop handler for that message forces its own copy to I before the requester's write is allowed to proceed). So writes to a given address are strictly serialized by bus-grant order — there is a unique global sequence of "who owns the line for writing, when," and this sequence is the total order coherence requires. Every cache that later reads the line must first re-fetch it (its state was invalidated), so every core observes writes in that same bus order. Write propagation. A write can only complete after the writer has become the unique owner in M (obtained via a bus transaction that every other cache has snooped and reacted to by invalidating). Any subsequent read by another core misses (state is I), forcing a fresh `BusRd`/`BusRdX`, which — per the `on snoop BusRd`/`on snoop BusRdX` rules — forces the current M-holder to flush its dirty value before anyone else can proceed. Hence the new value is guaranteed visible to the next reader; no core can be permanently stuck with a stale copy. Invariant to state explicitly: at most one cache is in M for a given address, and if any cache is in M, no cache is in S for that same address. This "M excludes everyone else" invariant is maintained by every transition rule above (entering M always drives all other copies to I first) and is exactly what prevents two cores from silently diverging on the value of `x`.
Tradeoffs. MSI is simple and provably correct but wasteful in one common case: a core that already holds a line exclusively in M, and writes to it again, pays no bus traffic (good) — but a core transitioning from I straight to M for data it will immediately overwrite still needs a `BusRdX` to fetch data it may not even need to read first. More importantly, a line that only one core ever touches still goes S→ (upgrade) →M on the very first write, generating unnecessary bus traffic if no one else was actually sharing it; MESI fixes this by adding an Exclusive (E) state indicating "I'm the sole cache holding this clean, so a future write can go straight to M with no bus message." MOESI further adds an Owned (O) state so a dirty line can be shared directly from cache to cache without writing back to memory first. These are refinements of the identical correctness argument, not different guarantees — the invariant above still holds.
Worked example
Three cores, A, B, C, share a bus. Address `x` starts in main memory only (all caches: I). Trace the following access sequence:
| Step | Action | A's state | B's state | C's state | Bus message | Notes |
|---|---|---|---|---|---|---|
| 0 | — | I | I | I | — | line not cached anywhere |
| 1 | A reads `x` | S | I | I | `BusRd` | memory supplies data (no one had it dirty) |
| 2 | B reads `x` | S | S | I | `BusRd` | A snoops, stays S (was already clean); B loads clean copy |
| 3 | C writes `x` | I | I | M | `BusRdX` | A and C... wait, A and B both snoop BusRdX and invalidate: A: S→I, B: S→I; C fetches & becomes M |
| 4 | A reads `x` | S | I | S | `BusRd` | C (in M) snoops BusRd, flushes dirty value to memory/A, C: M→S; A loads fresh value, A: I→S |
| 5 | B writes `x` | I | M | I | `BusRdX` | A (S) and C (S) both snoop BusRdX, invalidate to I; B fetches, becomes M |
| 6 | A writes `x` | M | I | I | `BusRdX` | B (in M) snoops BusRdX, must flush dirty data first, then B: M→I; A becomes M |
Walk through step 4 carefully, since it is the step that most often gets skipped in a shallow explanation. Before step 4, C holds `x` in M — the only copy, and it is dirty (different from what's in main memory, since C's write in step 3 never went to memory). When A issues `BusRd`, C's controller must recognize (via its own snoop logic) that it holds the authoritative value, and it must write that value back (either directly to memory, or via cache-to-cache transfer depending on implementation) before A's read completes. If this flush didn't happen, A would load memory's stale value and the two cores would disagree about `x` — exactly the coherence violation the protocol exists to prevent. After the flush, both A and C hold the same clean value in S, correctly reflecting C's step-3 write. Step 6 illustrates the mirror case for a dirty-to-dirty handoff: B holds `x` in M with an even newer value than what memory (or A) has seen; A's `BusRdX` forces B to flush first, so the data A ultimately writes over is B's true latest value, not a stale one. If the protocol let A skip waiting for B's flush, A's subsequent read-modify-write (if any) would be operating on wrong data — a correctness bug, not just a performance one.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Forgetting to flush on `BusRdX`/`BusRd` while in M | Treating snoop handling as "just invalidate," ignoring that dirty data must reach the requester/memory first | Reader gets stale data — coherence broken, not just slow |
| Confusing coherence with consistency | Assuming "coherent" means "operations across different addresses appear in program order" | Reordering bugs in lock-free code that coherence alone cannot prevent — this is the consistency model's job |
| Allowing two caches in M simultaneously | Race in bus arbitration logic, or ignoring that `BusRdX` must invalidate before granting ownership | Classic lost-update bug: both cores think they own the line and write independently |
| Treating snooping as free | Assuming bus broadcast scales; not accounting for `O(N)` snoop bandwidth per transaction | Snoop traffic saturates the bus well before `N` gets large, capping scalability |
| Ignoring false sharing | Two unrelated variables happen to sit in the same cache line, so unrelated writes by different cores still ping-pong the line M↔I | Severe, easily-missed performance cliff with no correctness bug at all |
Pioneers & history
Cache coherence became an urgent engineering problem only once shared-memory multiprocessors with per-CPU caches became commercially viable in the 1980s. Before that, single-CPU machines with one cache had no coherence problem at all — the issue is fundamentally a multiprocessor phenomenon, and it emerged alongside the broader push toward Multicore Processors and Thread-Level Parallelism.
Origins · 1 minLucien M. Censier and how this was discovered
Censier and Feautrier's 1978 paper is widely credited as one of the first rigorous formulations of maintaining cache consistency in a shared-memory multiprocessor using a directory structure, laying groundwork that both snooping and directory protocols later built on.
Where this matters
Every general-purpose multicore CPU shipped today — Intel and AMD x86 chips, Arm-based mobile and server SoCs (Apple Silicon, Qualcomm Snapdragon, AWS Graviton), IBM POWER — implements a hardware coherence protocol, typically a MESI or MOESI variant on-chip, because programmers expect ordinary shared variables, mutexes, and lock-free data structures to behave correctly without manual cache management. GPU architectures increasingly add limited coherence support (e.g., coherent unified memory between CPU and GPU) to simplify heterogeneous programming models like CUDA Unified Memory and Apple's unified memory architecture. Large multi-socket servers and high-core-count chips (64+ cores) typically abandon pure broadcast snooping in favor of directory-based coherence protocols precisely because of the `O(N)` snoop-bandwidth wall described above, while still preserving the identical M/S/I-style correctness invariants underneath. Cache coherence is also the mechanism that hardware synchronization primitives such as atomic compare-and-swap and spinlocks quietly depend on: an atomic instruction is only meaningful because the coherence protocol guarantees exclusive M-state ownership during the read-modify-write. Finally, coherence is the essential floor beneath Memory Consistency Models: a system can be perfectly coherent (every address individually behaves sanely) yet still permit reorderings across addresses that break naive concurrent algorithms, which is exactly the next layer of the memory-model story.
Ask the tutor: How does directory-based coherence replace bus broadcast with point-to-point messages while preserving the same write-serialization guarantee?
Why can't we just make caches write-through and skip coherence protocols entirely?
Write-through alone does not solve coherence. Write-through means every write updates main memory immediately, but it does nothing to invalidate or update other cores' cached copies of that same address. Core B could still be reading its own stale cached value even though memory has been updated. You would additionally need every other cache to snoop write-through traffic and invalidate matching lines — which is itself a (simpler, less efficient) coherence protocol, just without the Modified state. Real systems avoid pure write-through for performance reasons (it saturates the bus with every single write) and instead use write-back caches with an explicit coherence protocol like MSI, which only generates bus traffic when a line's ownership must actually change.
Does cache coherence guarantee that a multithreaded program is free of race conditions?
No. Coherence guarantees that all cores eventually agree on the value of any single memory location and see writes to it in a consistent order, but it says nothing about the timing or interleaving of when that agreement becomes visible relative to other variables. A classic race condition — two threads incrementing a shared counter without a lock — remains a race even on a perfectly coherent machine, because the read-modify-write sequence isn't atomic without explicit synchronization (like a compare-and-swap, which coherence merely makes possible to implement correctly). Coherence is necessary infrastructure for correct concurrent programming, but locks, atomics, and a memory consistency model are still required on top of it.
What is false sharing, and why does coherence make it a performance problem rather than a correctness problem?
False sharing happens when two unrelated variables, used by different cores, happen to land in the same cache line simply due to memory layout. Even though the cores never touch the same logical variable, the coherence protocol tracks state per line, not per byte, so a write by one core to its variable invalidates the whole line — including the other core's unrelated variable — in every other cache. The result is the line "ping-pongs" between Modified and Invalid across cores, generating heavy bus traffic and stalling both cores, even though there is no actual data race. It's purely a performance pathology; correctness is unaffected because the protocol still enforces the same invariants, just inefficiently. The fix is padding or restructuring data so independently-accessed variables land in separate cache lines.
How does MESI improve on MSI, and does it change the correctness guarantee?
MESI adds an Exclusive (E) state: a line that is clean and held by exactly one cache, with no other cache sharing it. In plain MSI, even a core that is the sole reader of a line must issue a `BusUpgr`/re-request when it later writes that line, because Shared doesn't distinguish "shared with others" from "clean but actually alone." MESI's E state lets that same core silently transition E→M on a local write, with zero bus traffic, since no other cache needs to be told. This is purely a performance optimization: the underlying invariant — at most one cache in M, and M excludes all Shared copies — is unchanged, so the correctness argument for MSI carries over verbatim to MESI.
Why is a shared bus itself a serializing structure, and why does that matter for correctness?
A physical bus (or any single broadcast medium) can only grant ownership to one transaction at a time via its arbitration logic — two caches cannot simultaneously "win" the bus for conflicting requests to the same address. This total order of bus-grant events becomes the reference order that defines write serialization: since every cache snoops the bus in that same physical order, every core witnesses writes to a given address in exactly that sequence. If the underlying interconnect were not a single serializing point (e.g., a naive multi-path network where messages can arrive at different caches in different orders), you would need an entirely different mechanism — typically a directory with explicit acknowledgments — to reconstruct a consistent total order, which is exactly why large-scale coherent systems move to directory protocols instead of a literal bus.
Can cache coherence be implemented purely in software instead of hardware?
Yes, and some systems do — particularly in message-passing clusters or software-managed scratchpad architectures (e.g., some GPU shared memory, older Cell processor SPEs) where hardware coherence is deliberately omitted to save power and complexity. Software coherence requires the programmer or compiler to insert explicit synchronization (flushes, invalidations, barriers) at the right points, which is more error-prone and burdens the programmer, but avoids the hardware cost of snooping logic and directory storage entirely. Hardware coherence's appeal is that ordinary loads/stores work correctly across cores with zero programmer effort, which is why it dominates general-purpose CPUs, while software-managed coherence tends to appear in specialized, performance-critical, expert-tuned domains.
What happens if a cache is evicting a Modified line right as it snoops a BusRd for that same address?
This is a genuine race that real controllers must handle carefully: the eviction and the snoop both want to act on the same line at nearly the same instant. Correct implementations resolve this by making the snoop response take priority — the controller must first supply/flush the dirty data to satisfy the snooped request (transitioning appropriately, e.g., M→S), and only then complete the eviction (or fold the eviction into the same flush operation). If a design instead let the eviction silently write back stale-ordering data or drop the dirty value without responding to the snoop, the requester would receive incorrect data — a genuine coherence violation. This is exactly the class of subtle interaction that makes coherence protocol verification a serious formal-methods discipline in real chip design.