Multi-core CPUs keep a private cache per core yet still present a single view of each memory location. Explain how a MESI-style cache coherence protocol achieves that: what the Modified, Exclusive, Shared and Invalid states mean, and what happens when one core writes a line another core is caching.

middleshould knowfreq 38%

answer

M dirty+alone, E clean+alone, S clean+maybe-shared, I unusable
Write needs ownership → read-for-ownership invalidates others
E → M is silent, the cheap write
Snooping (broadcast) vs directory (targeted, scalable, NUMA)
Coherence is per location; it is not a memory model

basics

~20 s

Each cached line carries a state: Modified (dirty, mine alone), Exclusive (clean, mine alone), Shared (clean, others may hold it), Invalid (unusable). Writing requires exclusive ownership, so the writer requests the line and invalidates all other copies; those drop to Invalid and must refetch, taking the data from the writer's cache.

solid answer

~60 s

MESI keeps a per-line state machine in each core's cache and enforces the invariant one writer or many readers for every line.

Modified — this cache alone holds the line and has changed it; memory is stale, so this cache must supply the data and eventually write it back.
Exclusive — this cache alone holds the line, unmodified; it can be written silently, moving to Modified without any bus traffic.
Shared — the line is clean and other caches may hold it too; reads are local, writes are not permitted from this state.
Invalid — not usable; any access misses.

A write to a Shared or Invalid line issues a read-for-ownership: other caches see it, invalidate their copies, and a Modified holder supplies the current data. The writer ends in Modified, everyone else in Invalid. Cores discover these requests by snooping a shared bus in small systems, or through a directory that tracks sharers in large ones. The practical consequence is that shared reads are cheap and replicate freely, while contended writes serialise on ownership transfer.

MESI keeps a per-line state machine in each core's cache and enforces the invariant *one writer or many readers* for every line. - **Modified** — this cache alone holds the line and has changed it; memory is stale, so this cache must supply the data and eventually write it back. - **Exclusive** — this cache alone holds the line, unmodified; it can be written silently, moving to Modified without any bus traffic. - **Shared** — the line is clean and other caches may hold it too; reads are local, writes are not permitted from this state. - **Invalid** — not usable; any access misses. A write to a Shared or Invalid line issues a read-for-ownership: other caches see it, invalidate their copies, and a Modified holder supplies the current data. The writer ends in Modified, everyone else in Invalid. Cores discover these requests by snooping a shared bus in small systems, or through a directory that tracks sharers in large ones. The practical consequence is that shared reads are cheap and replicate freely, while contended writes serialise on ownership transfer.

code

text · 8 lines

text

start:   coreA: S   coreB: S   (both read the line, memory clean)
coreA writes:
         coreA issues read-for-ownership
         coreB: S -> I          (copy invalidated)
         coreA: S -> M          (dirty, sole owner)
coreB reads:
         coreA supplies data, coreA: M -> S
         coreB: I -> S

go deeper

for a junior

Know that each core caches memory, that a protocol keeps copies consistent, and that writing requires invalidating other copies.

for a middle

Name and define the four states, describe the read-for-ownership on a write, and state the one-writer-or-many-readers invariant.

for a senior

Add snooping versus directory, the cost asymmetry between shared reads and contended writes, and connect it to false sharing and NUMA effects.

for a principal

Reason about it as a scalability budget: how many ownership transfers per operation the design implies, and how to partition state so hot writes stay core-local.

The problem being solved

Each core has its own L1 (and usually L2) cache, so the same memory location can exist in several places at once. Coherence is the hardware guarantee that, for a single location, all cores eventually see a single agreed sequence of values, and that a read returns the most recent write in that sequence. Without it, a program could not reason about shared memory at all.

Note the scope: coherence is a per-location property. It says nothing about the relative order of operations on different locations — that is the memory consistency model, a separate concern handled by ordering rules and fences. A common interview trap is to conclude "the caches are coherent, so I do not need synchronisation". Coherence does not stop store buffers, out-of-order execution or a compiler from reordering your accesses to different variables.

The four states

Every line in a cache carries a state:

M (Modified) — present only here, and dirty. Main memory is out of date. This cache is responsible for supplying the data to any requester and for writing it back on eviction.
E (Exclusive) — present only here, and clean. Identical to memory. The key value of E is that a subsequent write can go straight to M with no bus traffic, because no one else has a copy to invalidate.
S (Shared) — clean, and one or more other caches may hold it. Reads hit locally; a write must first gain ownership.
I (Invalid) — the entry holds no usable data; access misses.

The invariant across all caches is: at most one M or E copy, or any number of S copies, never both.

Transitions

Read miss. The core requests the line. If no other cache holds it, it arrives in E. If others hold it, everyone (including the requester) settles in S. If some cache holds it in M, that cache supplies the data — cache-to-cache transfer, usually with a write-back or a transition to a shared-dirty state in richer protocols — and both end in S.

Write to a line in E. Silent promotion to M. This is the cheap case, and it is why thread-private data that no one else has touched is fast to write.

Write to a line in S or I. The core issues a read-for-ownership (RFO): an invalidate request plus a data request. Every other cache sees it and drops its copy to I; an M holder supplies the data first. The writer ends in M. This is the expensive case — it costs an interconnect round trip and stalls the store until ownership arrives.

Eviction of M. Write back to the next level.

How cores find out

Snooping. All caches observe a shared bus or ring and react to requests for lines they hold. Simple and low-latency, but every request is broadcast, so traffic grows with core count.
Directory. A directory (often alongside the last-level cache, or per memory controller) records which caches hold each line, and sends targeted invalidations. This scales to many cores and to multi-socket systems, at the cost of an extra hop — and on NUMA machines, that hop may cross sockets, which is markedly slower.

Real CPUs extend MESI: MOESI adds Owned so a dirty line can be shared without writing back to memory, MESIF adds Forward to nominate a single responder among sharers. The four-state model is the one to explain; naming a variant shows depth.

Why this shapes performance

The protocol makes two costs visible to software:

Reads of shared, unmodified data are nearly free and scale. Any number of cores can hold the line in S simultaneously and hit locally.
Writes to a line other cores hold do not scale. Each write serialises on an ownership transfer, so a line written by many cores becomes a hardware-level serialisation point even with no locks in the program. Ownership moves at line granularity, which is exactly why two unrelated variables in one line (false sharing) contend.

So the design advice that follows from MESI is: keep frequently written data private to one core, keep frequently read data clean and replicated, and never let the two mix in one line.

## The problem being solved Each core has its own L1 (and usually L2) cache, so the same memory location can exist in several places at once. **Coherence** is the hardware guarantee that, for a single location, all cores eventually see a single agreed sequence of values, and that a read returns the most recent write in that sequence. Without it, a program could not reason about shared memory at all. Note the scope: coherence is a *per-location* property. It says nothing about the relative order of operations on *different* locations — that is the memory consistency model, a separate concern handled by ordering rules and fences. A common interview trap is to conclude "the caches are coherent, so I do not need synchronisation". Coherence does not stop store buffers, out-of-order execution or a compiler from reordering your accesses to *different* variables. ## The four states Every line in a cache carries a state: - **M (Modified)** — present only here, and dirty. Main memory is out of date. This cache is responsible for supplying the data to any requester and for writing it back on eviction. - **E (Exclusive)** — present only here, and clean. Identical to memory. The key value of E is that a subsequent write can go straight to M with **no bus traffic**, because no one else has a copy to invalidate. - **S (Shared)** — clean, and one or more other caches may hold it. Reads hit locally; a write must first gain ownership. - **I (Invalid)** — the entry holds no usable data; access misses. The invariant across all caches is: at most one M or E copy, or any number of S copies, never both. ## Transitions **Read miss.** The core requests the line. If no other cache holds it, it arrives in **E**. If others hold it, everyone (including the requester) settles in **S**. If some cache holds it in **M**, that cache supplies the data — cache-to-cache transfer, usually with a write-back or a transition to a shared-dirty state in richer protocols — and both end in **S**. **Write to a line in E.** Silent promotion to **M**. This is the cheap case, and it is why thread-private data that no one else has touched is fast to write. **Write to a line in S or I.** The core issues a **read-for-ownership** (RFO): an invalidate request plus a data request. Every other cache sees it and drops its copy to **I**; an M holder supplies the data first. The writer ends in **M**. This is the expensive case — it costs an interconnect round trip and stalls the store until ownership arrives. **Eviction of M.** Write back to the next level. ## How cores find out - **Snooping.** All caches observe a shared bus or ring and react to requests for lines they hold. Simple and low-latency, but every request is broadcast, so traffic grows with core count. - **Directory.** A directory (often alongside the last-level cache, or per memory controller) records which caches hold each line, and sends targeted invalidations. This scales to many cores and to multi-socket systems, at the cost of an extra hop — and on NUMA machines, that hop may cross sockets, which is markedly slower. Real CPUs extend MESI: **MOESI** adds Owned so a dirty line can be shared without writing back to memory, **MESIF** adds Forward to nominate a single responder among sharers. The four-state model is the one to explain; naming a variant shows depth. ## Why this shapes performance The protocol makes two costs visible to software: 1. **Reads of shared, unmodified data are nearly free and scale.** Any number of cores can hold the line in S simultaneously and hit locally. 2. **Writes to a line other cores hold do not scale.** Each write serialises on an ownership transfer, so a line written by many cores becomes a hardware-level serialisation point even with no locks in the program. Ownership moves at line granularity, which is exactly why two unrelated variables in one line (false sharing) contend. So the design advice that follows from MESI is: keep frequently written data private to one core, keep frequently read data clean and replicated, and never let the two mix in one line.

If the hardware guarantees coherence, why does a program still need synchronisation or memory fences?
Coherence only guarantees a single agreed order of values for each location individually. It does not constrain how operations on different locations appear to interleave: store buffers, out-of-order execution and compiler transformations can make one thread's writes become visible in a different order than they were issued. Ordering across locations comes from the memory model and the fences or ordering-annotated operations a program uses, not from MESI.
How does the picture change on a large multi-socket machine?
Broadcast snooping stops scaling, so large systems use directories that track sharers and send targeted invalidations. Ownership transfers may then cross a socket boundary, costing substantially more than a same-socket transfer, and memory itself is NUMA-partitioned. The practical consequence is that a line written by cores on different sockets is far more expensive than the same pattern within one socket, which pushes designs toward per-socket or per-core partitioning.

A shared document with a checkout rule: many people may hold read-only copies (Shared), one person may hold the only copy (Exclusive), and to edit you must recall every copy so yours is the sole authoritative one (Modified). Everyone else's copy is stamped void (Invalid) until they fetch again.

saying these in an interview costs you the question

Claiming coherence makes fences and synchronisation unnecessary
Saying every read of shared data costs interconnect traffic — clean shared lines are replicated and hit locally
Describing invalidation as happening per variable rather than per line
Confusing coherence (per location) with consistency or ordering (across locations)
Thinking Modified means another core cannot read the value at all, rather than that it must be supplied by the owner

Multi-core CPUs keep a private cache per core yet still present a single view of each memory location. Explain how a MESI-style cache coherence protocol achieves that: what the Modified, Exclusive, Shared and Invalid states mean, and what happens when one core writes a line another core is caching.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The problem being solved

The four states

Transitions

How cores find out

Why this shapes performance

▾common follow-ups2 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions3 questions

▾related topics3 topics

The problem being solved

The four states

Transitions

How cores find out

Why this shapes performance

answer

go deeper

context