Part IIThe Core
Cache Coherence Protocols

July 31, 2026·31 min read·advanced
At step 4, Core 1 reads 0 for a variable that was set to 5. And here is the part that should bother you. Nothing malfunctioned. Core 0's cache correctly held a dirty line. Core 1's cache correctly returned a…
01.Part 1, the problem

1.1 Two cores and one variable

Two cores, each with a private L1 cache, sharing one memory. A variable $x$ lives at 0x1000 and starts at 0. Nothing exotic happens. Trace it.
Step	Core 0 does	Core 0's cache	Core 1 does	Core 1's cache	Memory
1	`load x`	miss, fills, holds $x = 0$		empty	$x = 0$
2		holds $x = 0$	`load x`	miss, fills, holds $x = 0$	$x = 0$
3	`store x = 5`	holds $x = 5$ , dirty		holds $x = 0$	$x = 0$
4		holds $x = 5$	`load x`	hit, returns 0	$x = 0$
At step 4, Core 1 reads 0 for a variable that was set to 5. And here is the part that should bother you. Nothing malfunctioned. Core 0's cache correctly held a dirty line. Core 1's cache correctly returned a valid resident line without going to memory, which is the whole reason it exists. Memory correctly held the old value, because write-back means memory is stale by design. Every component behaved to its own specification and the system produced a wrong answer.
That is the shape of every hard problem in multiprocessor hardware. The bug is not in a component, it is in the absence of an agreement between components.
1.2 Why the obvious fixes are not fixes

Two responses come to mind immediately and both fail, which is worth seeing because it motivates the real solution.
Make every cache write-through. Then memory always holds the newest value, so step 3 updates memory to 5. Step 4 still returns 0, because Core 1 hits in its own cache and never asks memory. Write-through fixes the memory copy and does nothing about the stale copies. You would additionally have to force every read to memory, at which point you have no cache.
Do not cache shared data. This is actually done, for device registers and some lock variables, using uncacheable memory types. As a general policy it destroys performance, because in a multithreaded program most data is potentially shared and you cannot generally tell which is which at compile time.
So the fix must be communication between caches. When one cache changes a line, the others must find out. Cache coherence is the machinery for that, and its job is one sentence.
Every read returns the value of the most recent write to that location, whichever cache performed it.
1.3 Coherence is not consistency

These get confused constantly and the distinction is a standard interview probe, so nail it with an example rather than a definition.
Coherence is about one address. It guarantees that all writes to a single location are seen by everyone in the same order, and that a read eventually sees the latest one.
Consistency is about ordering across different addresses. It governs whether Core 1 can observe Core 0's operations in a different order than Core 0 issued them.
Here is a machine that is perfectly coherent and still surprises you.
  int x = 0, flag = 0;

  Core 0:              Core 1:
    x = 1;               while (flag == 0) { }
    flag = 1;            print(x);
```text
On a weakly ordered machine, Core 1 can print **0**. Coherence is not violated anywhere. The write to `x` and the write to `flag` are writes to **different addresses**, and coherence says nothing about their relative order. Core 0's store buffer may drain `flag` before `x`, or Core 1's loads may execute out of order, and both are legal under a weak memory model.

The fix is not a better coherence protocol, it is a **memory barrier** between the two stores and between the two loads. ARM, and therefore Apple silicon, is weakly ordered, so this matters concretely and is why acquire and release semantics exist. [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering) carries the consistency half properly.

The one-line answer to have ready. **Coherence makes caches invisible. Consistency defines what the memory system is allowed to do once they are invisible.**

### 1.4 The two invariants

Every protocol in this note enforces exactly two rules. If you can state them you can derive most protocol behavior live in an interview, which is far more useful than reciting a table.

**Single writer, multiple reader.** For any address, at any instant, either exactly one cache may write it and no cache may read it, or any number may read it and none may write. Never both.

**Data value invariant.** The value at the start of a read-only epoch equals the value at the end of the immediately preceding read-write epoch. In plain terms, when the writer gives up its exclusive right, the value it produced is what the readers see next.

Everything below is an implementation of these two sentences with different amounts of cleverness bolted on to avoid unnecessary traffic.

---

## Part 2, MSI, the minimum protocol

### 2.1 The three states

Every cache line in every cache carries a state. The minimum viable set is three.

- **M, modified.** This cache holds the only copy and it differs from memory. This cache owes memory a writeback.
- **S, shared.** This cache holds a clean copy. Other caches may hold it too. Memory is current.
- **I, invalid.** No usable copy here. Either the line was never fetched or somebody took it away.

Check them against the invariants. M is the single-writer state, and it is exclusive by construction. S is the multiple-reader state and no cache in S may write without first changing state. I is the absence of rights. Three states is the smallest set that can express the invariants.

### 2.2 The transition table

Two kinds of events drive transitions. **Local** events come from this core's own loads and stores. **Remote** events are transactions from other caches that this cache observes. The bus transactions are `BusRd` for a read request, `BusRdX` for a read-with-intent-to-modify, and `BusUpgr` for an upgrade from S to M with no data transfer needed.

| State | Event | Next | Action taken |
|---|---|---|---|
| I | local read | S | issue `BusRd`, wait for data |
| I | local write | M | issue `BusRdX`, which invalidates every other copy |
| S | local read | S | nothing, it is a hit |
| S | local write | M | issue `BusUpgr`, invalidating other copies, no data needed |
| S | remote `BusRd` | S | nothing, sharing is fine |
| S | remote `BusRdX` or `BusUpgr` | I | invalidate |
| M | local read or write | M | nothing, it is a hit |
| M | remote `BusRd` | S | **flush** the data, then downgrade |
| M | remote `BusRdX` | I | **flush** the data, then invalidate |
| M | eviction | I | write back to memory |
| S | eviction | I | silent, no traffic, the copy was clean |

The two flush rows are the ones that matter. A cache in M holds the only correct copy in the machine, so it cannot simply drop its rights when somebody else asks. It must supply the data, either to memory or directly to the requester.

### 2.3 The trace, fixed

Re-run the two-core example under MSI.

| Step | Core 0 | C0 state | Bus | Core 1 | C1 state | Memory |
|---|---|---|---|---|---|---|
| 1 | `load x` | I to **S** | `BusRd` | | I | 0 |
| 2 | | S | `BusRd` | `load x` | I to **S** | 0 |
| 3 | `store x=5` | S to **M** | `BusUpgr` | sees it | S to **I** | 0 |
| 4 | supplies data | M to **S** | `BusRd` | `load x` misses | I to **S** | 0, then 5 on flush |

Step 3 is where the fix happens. Core 0's `BusUpgr` forces Core 1 to invalidate, so Core 1's step 4 is now a **miss** rather than a stale hit. On that miss Core 0, holding M, flushes the modified data and downgrades to S. Core 1 sees 5. The invariant held throughout, since at step 3 exactly one cache had write rights and no cache had read rights.

Notice what it cost. Step 4 went from a 4-cycle L1 hit to a full coherence miss, likely 40 to 100 cycles depending on whether the fabric can do cache-to-cache transfer. That is the **coherence miss** category from [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching), and it is the price of correctness.

---

## Part 3, MESI, and exactly what the E state buys

### 3.1 The waste, counted

MSI has one specific inefficiency, and MESI exists solely to remove it. Find it by looking at the most common access pattern in all of software.

```c
  for (i = 0; i < N; i++)
      a[i]++;            /* read, then write, same location */
```text
This is single-threaded. No other core ever touches `a`. Trace one line under MSI.

The load misses, so the cache issues `BusRd` and lands in **S**. Then the store happens. The line is in S, and the table says S plus local write requires a `BusUpgr` to reach M. So the cache broadcasts an upgrade request, on a shared bus or fabric, to invalidate copies that **do not exist**.

Count it on a 1 MB array with 64-byte lines, so 16384 lines. Under MSI that is 16384 `BusRd` transactions plus 16384 `BusUpgr` transactions, for **32768 bus transactions**. Half of them accomplish nothing. And every one of them costs snoop bandwidth at every other cache in the system, so on an 8-core machine those 16384 useless upgrades cause 114688 useless tag lookups elsewhere.

Private data is the overwhelmingly common case in real programs. MSI taxes it on every read-modify-write.

### 3.2 The E state

MESI adds **E, exclusive**. Clean like S, meaning memory is current, but known to be **the only cached copy in the machine**.

Getting into E requires one piece of information at fill time. When a cache issues `BusRd`, the interconnect must tell it whether anybody else had the line. On a classic shared bus this is a wired-OR signal, historically called the **shared line**, that any snooping cache asserts if it holds a copy. On a modern fabric the same answer comes back as a field in the response.

- Read miss, **nobody else has it** (shared line deasserted), go to **E**.
- Read miss, **somebody else has it** (shared line asserted), go to **S**.

Then the payoff. A cache in E that performs a local write moves to **M silently**. No bus transaction of any kind. It is provably the only copy, so there is provably nobody to invalidate.

Rerun the loop. Now each line costs one `BusRd` and zero upgrades, so **16384 transactions instead of 32768**. Exactly half, on the most common pattern in software, for the cost of one extra state encoding and one wire.

That is the whole answer to "why does MESI have an E state", and the interviewer is listening for the phrase **read-then-write on private data upgrades silently**.

### 3.3 The state diagram

<Figure src="/figures/hardware-interview-prep/iv-10-Cache-Coherence-Protocols-fig01.svg" alt="Every path into M either carries a BusRdX or a BusUpgr that invalidates the other copies, or is the silent edge out of E where the cache is provably the only holder, so the single-writer invariant is visible in the shape of the graph." caption="Every path into M either carries a BusRdX or a BusUpgr that invalidates the other copies, or is the silent edge out of E where the cache is provably the only holder, so the single-writer invariant is visible in the shape of the graph." id="fig:10-Cache-Coherence-Protocols-1" />

Two properties of this diagram are worth saying out loud because they are the invariants made visible. Every path into M passes through either a `BusRdX` or a `BusUpgr` or the silent E-to-M edge, and all three guarantee no other cache holds the line, which is single-writer. And no cache can sit in E or M while another sits in S or E for the same address, which the shared line enforces at fill time.

### 3.4 The subtlety people miss about E

E is a **clean** state, so a cache holding E may evict the line **silently** with no writeback and no announcement. That creates a small correctness wrinkle. After a silent E eviction, memory is still correct, so nothing is lost. But if a cache in E is later asked for the line by a snoop, it must respond, and if it silently dropped the line it simply responds as I and memory supplies. That works.

The wrinkle bites in directory protocols, covered in Part 5, where the directory now believes a cache holds a line it has actually discarded. The directory sends it a needless invalidate and the cache answers with a null acknowledgement. Correct, but it costs a message, and this class of stale-directory-information case is exactly the kind of thing that gets missed in a first implementation and found by formal verification.

---

## Part 4, MOESI and MESIF

### 4.1 What MESI still wastes

MESI removed the useless upgrade. It leaves a different waste, visible when two cores actually share a hot line.

Look at the M-plus-remote-`BusRd` row of the table. The M cache must **write the line back to memory** and then go to S. Now suppose the line is a shared counter or a work-queue head that both cores keep modifying. The sequence is Core 0 writes, Core 1 reads, Core 1 writes, Core 0 reads, and so on. Each handoff drags a full 64-byte writeback to DRAM through the memory controller.

Count 1000 handoffs on a hot shared line. MESI produces roughly **1000 writebacks to memory**, each of which is a DRAM write of 64 bytes with real energy cost, and every one of them is immediately made stale by the next write. The data never needed to reach memory at all until the sharing ended.

### 4.2 The O state

MOESI adds **O, owned**. The line is modified relative to memory, is shared with other caches, and **this** cache is the designated owner responsible for supplying it and eventually writing it back.

A cache in M that sees a remote `BusRd` now moves to **O** instead of S. It supplies the data **directly** to the requester, cache to cache, and it does **not** write back. Other sharers hold S. Memory stays stale, and that is fine, because exactly one cache is on the hook for it.

Rerun the 1000 handoffs. Writebacks to memory drop from about 1000 to about **1**, the one that happens when the owner finally evicts the line. AMD has used MOESI extensively for this reason.

The cost is that S no longer implies memory is current, which complicates every path that assumed it, and that the owner has to be tracked and transferred correctly, which is more transient states.

### 4.3 The F state

MESIF attacks a different waste and is the Intel variant. Suppose eight caches hold a line in S and a ninth requests it. Under plain MESI on a broadcast fabric, **any** cache in S could answer, and if the protocol permits cache-to-cache transfer from S, several of them may answer at once. Eight caches each shipping a 64-byte line to the same requester is 512 bytes of fabric traffic to deliver 64 useful bytes, seven eighths of it discarded.

**F, forward**, designates exactly one sharer as the responder. The other seven stay in plain S and stay silent. The requester gets **one** reply. When a new sharer joins, the F designation typically migrates to the newest sharer, on the reasoning that the most recent requester is the most likely to still hold the line when the next request arrives.

F is **clean**. Memory is current, unlike O.

### 4.4 O versus F, the comparison question

| | O, owned | F, forward |
|---|---|---|
| Line versus memory | dirty, memory is stale | clean, memory is current |
| What it optimizes | **dirty sharing**, avoids repeated writebacks | **clean sharing**, avoids duplicate responses |
| Duty of the holder | supply data and eventually write back | supply data, no writeback owed |
| On eviction | must write back | silent |
| Traffic saved | memory writes | fabric data responses |
| Associated with | AMD MOESI | Intel MESIF |

The sentence that answers the comparison. **O optimizes dirty sharing by avoiding writebacks. F optimizes clean sharing by avoiding duplicate responses.** They are orthogonal, and some protocols carry both, which is where you get MOESIF and similar alphabet growth.

---

## Part 5, snooping versus directory

### 5.1 The two implementations

<Figure src="/figures/hardware-interview-prep/iv-10-Cache-Coherence-Protocols-fig02.svg" alt="Snooping sends every request to every cache, so a request costs a tag lookup per core, while a directory records which caches hold each line and sends messages only to those, so a request costs work proportional to the number of actual sharers." caption="Snooping sends every request to every cache, so a request costs a tag lookup per core, while a directory records which caches hold each line and sends messages only to those, so a request costs work proportional to the number of actual sharers." id="fig:10-Cache-Coherence-Protocols-2" />

**Snooping.** Every cache watches every transaction and reacts. No central structure, low latency because there is no extra hop, and the ordering point is the bus itself, which serializes requests for free. That free serialization is worth more than it looks, because it makes reasoning about races far easier.

**Directory.** A structure records, per line, which caches hold it and in what state. Requests go to the directory, which sends messages only to caches that actually care. The **home node** for a line, meaning the directory slice responsible for it, becomes the serialization point.

### 5.2 The scaling argument, with numbers

Snooping dies for a reason you can compute. Let each of $N$ cores generate $m$ coherence transactions per cycle. Every transaction is broadcast, and every cache must perform a tag lookup for it. Total snoop lookups per cycle across the machine is

$$N \times (N \times m) = N^2 m$$

and, more importantly, the load **on each individual cache** is $N \times m$ snoop lookups per cycle, on top of the accesses its own core is making.

Take $m = 0.05$, a plausible coherence transaction rate per core.

| Cores | Broadcasts per cycle | Snoop lookups per cache per cycle | Total lookups per cycle |
|---|---|---|---|
| 4 | 0.2 | 0.2 | 0.8 |
| 8 | 0.4 | 0.4 | 3.2 |
| 16 | 0.8 | 0.8 | 12.8 |
| 32 | 1.6 | **1.6** | 51.2 |
| 64 | 3.2 | **3.2** | 205 |

Read the third column, since that is the one that kills you. At 32 cores each L1 must absorb 1.6 snoop tag lookups every cycle. An L1 tag array has one port and the core wants it every cycle for its own loads. You would need to duplicate the tag array, or add ports, or throttle the core. At 64 cores you need 3.2 lookups per cycle per cache, which is simply not buildable at L1 speeds.

That is the crossover, and it lands somewhere in the low tens of cores depending on how much duplicate-tag hardware you are willing to buy.

Directory traffic instead grows with the **number of actual sharers**, which for most lines is one or two regardless of how many cores exist. The costs are an extra hop of latency, since a request goes to the home node and then to the owner rather than straight to the owner, and real storage.

### 5.3 Directory storage, worked

The simplest directory is a **full bit vector**, one bit per core per line plus a couple of state bits.

Take 64 cores and a 32 MB last-level cache with 64-byte lines.

$$\text{lines} = \frac{32 \times 2^{20}}{64} = 524288$$
$$\text{bits per entry} = 64\ \text{presence} + 2\ \text{state} = 66$$
$$\text{storage} = 524288 \times 66 = 34.6\ \text{Mbit} = 4.32\ \text{MB}$$

That is 13.5 percent overhead on top of the cache's own data, which is already carrying the 7.6 percent tag overhead computed in [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching). Tolerable, barely.

Now scale the cores to 256 and hold the cache size.

$$524288 \times 258 = 135\ \text{Mbit} = 16.9\ \text{MB}, \quad \mathbf{53\ \text{percent}}$$

Half the area of the cache, spent on bookkeeping. And it gets worse, because a full-vector directory that must cover **memory** rather than the cache is hopeless. Covering 16 GB of DRAM at 64 bytes per line is $2.68 \times 10^8$ lines times 66 bits, which is **2.2 GB of directory**. Absurd on its face.

The cost grows as $O(N \cdot L)$ for $N$ cores and $L$ lines, and both terms grow. Three mitigations exist and each trades a different thing.

**Limited pointer.** Store only $k$ sharer IDs instead of a full vector, each $\log_2 N$ bits, plus an overflow bit. For 64 cores and $k = 4$ that is $4 \times 6 + 1 + 2 = 27$ bits per entry instead of 66, giving $524288 \times 27 = 1.77$ MB, a 5.5 percent overhead. When a fifth sharer appears you overflow and fall back to broadcast for that line, or you evict one of the existing sharers to make room. The bet is that almost all lines have few sharers, which measurement supports, with the exception of widely-read data like a lock or a hot read-only table.

**Coarse vector.** One presence bit covers a **group** of cores. For 64 cores in groups of 4 that is 16 bits plus state, giving $524288 \times 18 = 1.18$ MB, a 3.7 percent overhead. The cost is precision. When one core in a group holds the line, an invalidate goes to all four, so you traded storage for spurious messages and spurious snoop lookups.

**Sparse directory.** Track only lines that are **actually cached somewhere**, as a tagged, set-associative structure rather than a flat array indexed by line address. This is the important one conceptually, because it changes what the storage scales with. A full directory scales with **memory** size. A sparse directory scales with **total cache** capacity, since a line not in any cache needs no entry. With 64 cores holding 512 KB of private cache each, total cached lines is $64 \times 512\text{KB} / 64 = 524288$, so a sparse directory of about a million entries covers it with headroom, at a fixed cost independent of how much DRAM the system has.

The catch is the same one that afflicts every cache. A sparse directory can **run out of ways in a set**, and when it evicts a directory entry it must **invalidate the corresponding line from every cache that holds it**, because losing the tracking information means losing the ability to maintain the invariant. That is a directory-induced invalidation of live data, it is invisible to software, and it is a genuinely nasty performance pathology when the directory's associativity is too low.

### 5.4 Snoop filters, the hybrid

Keep broadcast snooping, which is simple and low latency, and add a structure that can **prove** a line is not cached anywhere else, so the snoop can be skipped.

The structure is conservative in a specific direction. It may say "possibly cached" when the line is not, which costs a needless snoop and is harmless. It must **never** say "not cached" when a line actually is, because that would break the invariant. That asymmetry makes a Bloom-filter-style structure or an inclusive duplicate-tag array a natural fit.

The most common form is a duplicate copy of the inner caches' tags held at the outer level, which is exactly what an **inclusive** hierarchy gives you for free, as discussed in [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching). That is the real reason inclusion is attractive despite wasting capacity. Look up the L2 tags, and if the line is not there, no L1 in that cluster can have it, so the snoop never disturbs the L1 tag array. A NINE hierarchy has to build a snoop filter explicitly to get the same property back.

Apple uses a coherent fabric across performance and efficiency clusters plus a system level cache. Public detail is limited, so in an interview reason about mechanisms and their trade-offs rather than asserting a specific implementation. Saying "I would expect a filter or directory at the cluster boundary because snooping does not scale past the low tens of agents, and here is the arithmetic" is a much better answer than a confident guess about internals.

---

## Part 6, false sharing

### 6.1 Worked, with a slowdown factor

Two cores write two **different** variables that happen to occupy the **same cache line**. The program has no logical conflict at all. Coherence works at line granularity, so the hardware sees a conflict anyway.

```c
  struct counters {
      long a;      /* bytes  0..7   */
      long b;      /* bytes  8..15  */
  };                /* both inside ONE 64-byte line */

  struct counters c;

  thread 0:  for (i = 0; i < 10000000; i++) c.a++;
  thread 1:  for (i = 0; i < 10000000; i++) c.b++;
```text
Trace one round. Thread 0 increments `c.a`, which requires the line in M, which invalidates thread 1's copy. Thread 1 then increments `c.b`, misses because it was just invalidated, requests the line for writing, and invalidates thread 0. Thread 0's next increment misses. And so on, forever.

Count it. Every iteration on both threads is a coherence miss, so **20 million coherence misses**. At roughly 100 cycles each for a cache-to-cache transfer that is $2 \times 10^9$ cycles. The same two loops on separate lines run at roughly one increment per cycle, so about $2 \times 10^7$ cycles. That is a **100x slowdown** produced by moving one variable 56 bytes.

The fix is padding.

```c
  struct counters {
      long a;
      char pad[56];    /* push b onto the next line */
      long b;
  };
```text
Modern C++ also exposes a standard constant named `hardware_destructive_interference_size` for exactly this purpose, which tells you the line size to align against without hardcoding 64.

### 6.2 Finding it

False sharing is hard to spot because **the profiler shows a hot line, not a hot variable**. The source line that increments `c.a` looks expensive, and there is nothing wrong with it. The usual detection route is hardware performance counters that report cache-to-cache transfers or hit-modified events, which let you attribute stalls to a specific line address, and then a tool that maps that address back to the data structure. On Linux `perf c2c` does exactly this. Knowing that the tool exists and what counter it keys on is a good, concrete thing to say.

This is a favorite interview question because it tests one thing directly. Does the candidate understand that **the unit of coherence is the line, not the variable.** The related trap is the assumption that read-only sharing causes the same problem. It does not. Many caches can hold a line in S indefinitely with zero traffic, so false sharing requires at least one **writer**.

---

## Part 7, the hard parts, which is where an RTL role lives

### 7.1 Transient states, and a race worked

Everything above showed **stable** states. A real controller has many more, because a transaction is not instantaneous. Between issuing a request and receiving every response, the line is in a **transient** state, and the controller must handle any incoming message while it sits there.

Work one. Core 0 holds a line in S and its core issues a store. The controller sends `BusUpgr` and moves the line to a transient state, conventionally written **SM_A**, meaning "was S, going to M, awaiting acknowledgement". At that exact moment an invalidate for the same line arrives, because Core 1 raced for the same line and won the serialization at the home node.

What must happen. The line's data is now stale, so Core 0 must give up its S rights. But the outstanding `BusUpgr` is still in flight and its acknowledgement will arrive later, so Core 0 must not forget that it has a request outstanding. The correct move is a transition to **IM_A**, "invalid, still awaiting completion of a request that must now bring data as well as ownership", and the upgrade must be reissued or converted into a full `BusRdX`, because an upgrade carries no data and Core 0 no longer has valid data to upgrade.

Now look at the two wrong answers, since this is what makes the example worth memorizing.

If the controller goes to plain **I** and drops the outstanding request, the acknowledgement arrives later with no matching transaction. Either it is dropped, and the core's store hangs forever, or it is misapplied to some other line. That is a **lost request**, and it manifests in silicon as an intermittent hang under a specific timing alignment.

If the controller **ignores the invalidate** and stays in SM_A, then when the acknowledgement arrives it goes to M while Core 1 also believes it has M. Two writers. The single-writer invariant is broken, and the failure is silent data corruption rather than a hang, which is far worse.

Counting states makes the point. Stable MSI is 3 states. A real MSI controller is closer to 10 or 15. MESI reaches the 20s and a MOESI directory protocol can carry 40 or more states per cache controller, plus a similar count at the directory. Then the **system** state is the cross product across every controller and every in-flight message, and that space is astronomically large.

**This is why most real coherence bugs live in transient states**, and it is why formal verification rather than simulation is the primary tool. A directed test only reaches a transient race if the stimulus happens to align two events in the same few cycles. A formal tool explores the reachable state space exhaustively and finds the alignment you did not think of. Section 8 connects this to your own background.

### 7.2 Protocol races

Two cores request the same line for writing in the same cycle. The protocol must serialize them, must not lose either request, and must not deadlock. Snooping gets serialization free from the bus, since the bus arbiter picks one and everyone observes the same order. A directory serializes at the home node, and the home node must therefore either buffer or negatively acknowledge the loser, which is where the design choices start.

A related race is the **early response**, where a requester receives data from a supplier before it receives the acknowledgement from the directory that the transaction is complete. It cannot use the data yet, because the directory has not confirmed that every other copy is gone. Handling that correctly needs a transient state that counts acknowledgements, and forgetting to count one of them is a classic bug.

### 7.3 Deadlock and virtual channels

A coherence transaction generates responses, and responses can generate further messages. That dependency structure is where deadlock hides.

<Figure src="/figures/hardware-interview-prep/iv-10-Cache-Coherence-Protocols-fig03.svg" alt="One queue deadlocks because the response the head request is waiting on sits behind that head and can never advance past it, and giving requests and responses separate virtual channels breaks the circular wait because the response channel is a sink that always drains." caption="One queue deadlocks because the response the head request is waiting on sits behind that head and can never advance past it, and giving requests and responses separate virtual channels breaks the circular wait because the response channel is a sink that always drains." id="fig:10-Cache-Coherence-Protocols-3" />

The fix is **virtual channels**, meaning separate buffers and separate flow control per **message class** sharing the same physical wires. The design rule is a strict dependency ordering. A message class may depend only on classes below it, and the lowest class, responses, must never generate anything. Then the lowest class always drains, which lets the class above it drain, and so on up. Typical classes are request, then forwarded or intervention request, then response.

This is worth being fluent in, because deadlock avoidance is named in these role descriptions and because it is the same reasoning as credit-based flow control in [Interconnect and AMBA](/learn/hardware-interview-prep/interconnect-and-amba). If you can say "requests may block, responses must never block, and the two need separate buffers even though they share wires", you have said the thing.

### 7.4 Starvation and livelock

Deadlock is nothing moving. **Starvation** is one agent never making progress while others do. Under heavy contention on a hot line, a core can repeatedly request it, get it invalidated before its store retires, and try again forever. Its neighbors make progress. It does not.

The mechanisms that prevent this are fairness at the serialization point, meaning a fair arbiter per [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams) or FIFO ordering at the home node, and forward-progress guarantees such as guaranteeing that a core holding a line for a store retains it long enough to complete at least one store before it can be stolen. That last one is what makes an atomic read-modify-write implementable, since a compare-and-swap needs the line in M for the full duration of the operation.

**Livelock** is the case where everything is moving and no useful work completes, for example two cores endlessly stealing a line from each other and each retrying from scratch. It is harder to detect than deadlock precisely because the machine looks busy.

---

## Part 9, check yourself

Answer out loud in full sentences, as though an interviewer asked. If you cannot, reread the section named.

1. Trace two cores reading and writing one variable with no coherence, and say precisely which component malfunctioned. (1.1)
2. Why does making every cache write-through fail to fix the problem. (1.2)
3. Give a code example of a machine that is perfectly coherent and still returns a surprising answer, and name the actual fix. (1.3)
4. State the two invariants, then use single-writer to explain why MSI cannot have fewer than three states. (1.4, 2.1)
5. Write the MSI transition table from memory. Which two rows require flushing data, and why. (2.2)
6. Why does MESI have an E state when MSI works. Give the exact access pattern and count the bus transactions saved on a 1 MB array. (3.1, 3.2)
7. How does a cache know at fill time whether to enter E or S. (3.2)
8. Compare MOESI's O state with MESIF's F state in one sentence each, then say which is clean and which is dirty. (4.2, 4.3, 4.4)
9. Derive the per-cache snoop load as a function of core count, and say where snooping stops being buildable and why. (5.2)
10. Compute full bit-vector directory storage for 64 cores over a 32 MB cache, then say what you would do instead at 256 cores. (5.3)
11. What does a sparse directory's storage scale with, and what is its unpleasant failure mode. (5.3)
12. What must a snoop filter never do, and why does an inclusive hierarchy give you one for free. (5.4)
13. Write a two-variable false sharing example, estimate the slowdown factor, and say how you would find it in a real program. (6.1, 6.2)
14. A cache in S issues an upgrade and receives an invalidate before the acknowledgement. Give the correct transition and both wrong ones, with their failure modes. Then say how a protocol deadlocks and what rule about message classes prevents it. (7.1, 7.3)
15. Where would you apply formal verification on a coherence controller, and name four properties you would write. (7.1, 8)

---

## Part 10, related notes

- [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) for the single-cache foundation, line granularity, inclusion, and the coherence miss category
- [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering) for the consistency half, barriers, atomics, and how the store buffer meets an incoming invalidate
- [Interconnect and AMBA](/learn/hardware-interview-prep/interconnect-and-amba) for the fabric this protocol runs over, credits, and virtual channels in their native setting
- [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams) for the fair arbitration that prevents starvation at a serialization point
- [Verification Methodology](/learn/hardware-interview-prep/verification-methodology) for how formal is actually deployed, and where your existing experience plugs in
- [DFT and Silicon Debug](/learn/hardware-interview-prep/dft-and-silicon-debug) for catching a coherence hang after tapeout
- [Advanced Cache Topics](/learn/computer-architecture/advanced-caches) for the vault's coherence preview, which stops where this note starts
Book mode