The Coherence Problem

The Problem

Consider two cores, each with a private L1 cache, sharing main memory:

1. Core 0 reads address $A$ → cached in Core 0’s L1
2. Core 1 reads address $A$ → cached in Core 1’s L1
3. Core 0 writes $A = 7$ → Core 0’s cache is updated, but Core 1 still sees the old value

This is a coherence violation: two caches disagree on the value at the same address. Without a protocol to manage this, multicore systems would produce incorrect results.

Interactive: Step Through the Violation (and the Fix)

Click through the canonical scenario. Switch between “no protocol” (you’ll watch the caches diverge) and “MSI protocol” (Core 1’s stale copy is invalidated before it can be observed).

What Coherence Guarantees

A coherent memory system must satisfy:

1. Write propagation: A write to $A$ by any core must eventually become visible to all cores
2. Write serialization: All cores observe writes to the same address in the same order

These guarantee that there is a single, consistent view of memory — even though data is replicated across caches.

Coherence Mechanisms

Mechanism	How it works	Scalability
Snooping	All caches monitor (snoop) a shared bus for transactions	Good for 2–8 cores; bus becomes bottleneck
Directory-based	A central directory tracks which caches hold each line	Scales to many cores; higher per-operation latency

Most desktop/laptop CPUs use snooping (simpler, lower latency for small core counts). Server chips with many cores often use directory-based protocols.

Coherence vs. Consistency

These are often confused but are distinct concepts:

• Coherence: guarantees about a single address — all cores see the same sequence of values for address $A$
• Consistency: guarantees about multiple addresses — the order in which writes to different addresses become visible

Coherence is the mechanism (MSI, MESI). Consistency is the contract (Sequential Consistency, TSO). We cover consistency models in Section 3.

Common misconception: “Coherence is a software responsibility.”

Coherence is enforced entirely by hardware — neither the application code nor the OS issues any coherence messages explicitly. What software does control is the consistency model (via memory fences and atomics). The two are easily confused because both involve “memory ordering”: coherence guarantees there’s a single value per address; consistency guarantees an ordering of operations across addresses. Buggy multithreaded code is almost always a consistency bug, not a coherence bug — the hardware never gives you stale data, but it can reorder when a write becomes visible relative to other addresses.

What’s Next

• MSI Protocol — the simplest coherence protocol with three states
• MESI & MOESI — practical extensions that reduce bus traffic