MESI and Its Relatives
Coherence needs each cached line tagged with what the core is allowed to do with it. MESI — Modified, Exclusive, Shared, Invalid — is the canonical four-state answer and the one worth learning. It is a family, not a standard: real chips extend it, and which variant yours uses is usually undocumented.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The four states
MESI tags each cached line with one of four states. Modified means this core has the only copy and has changed it; memory is stale and this core must write back before anyone else may read. Exclusive means this core has the only copy and has not changed it; it matches memory, and the core may write without notifying anyone. Shared means several cores may hold clean copies; reads are free, but a write must first invalidate the others. Invalid means the copy is stale and must be re-fetched.
The Exclusive state is the one worth pausing on, because it is what makes single-threaded code on a multicore machine fast. Without it, every first write to a line would need an invalidation broadcast even when no other core has ever touched it. Exclusive lets a core that loaded a line nobody else wants upgrade to Modified silently. Most of your code is in this state most of the time, and it costs nothing.
| State | Other copies? | Matches memory? | Write without a transaction? |
|---|---|---|---|
| Modified | No — sole copy | No — memory is stale | Yes; already exclusive and dirty |
| Exclusive | No — sole copy | Yes | Yes; upgrades silently to Modified |
| Shared | Possibly several | Yes | No — must invalidate the other copies first |
| Invalid | Irrelevant | Irrelevant | No — must fetch the line first |
A read-for-ownership, step by step
The transition worth memorising is the one a contended write triggers. Core 2 wants to store into a line that core 1 currently holds Modified. Core 2 issues a *read-for-ownership*: it needs both the current data and exclusive rights. Core 1 sees the request, supplies its dirty copy, and downgrades its own state to Invalid. Core 2 installs the line as Modified and performs the store.
Two things are worth noticing. First, the data moved cache to cache, not through memory — which is faster than a memory round trip but far slower than a local hit. Second, core 1 now has nothing: if it wants that line back, the whole sequence runs again in the opposite direction. Two cores alternately writing one line ping-pong ownership on every access, and that is exactly the false-sharing pathology.
Core 1 state Event Core 2 state
------------ ----- ------------
Invalid core 1 reads the line Invalid
Exclusive (sole copy, clean) Invalid
Modified core 1 stores Invalid
Modified core 2 wants to store ----------> Invalid
Invalid <-- read-for-ownership, line transferred Modified
Invalid core 1 wants to store ----------> Modified
Modified <-- line transferred back Invalid
... and so on, once per write ...
Each arrow is an interconnect transaction. Neither core is
doing anything wrong; the line is simply being shared for writes.It is a family, not a standard
MESI is the teaching protocol, not the shipping one. Real designs extend it to cut traffic. MOESI adds an Owned state, letting one core hold a dirty line while others share it — so a modified line can be read by peers without a write-back to memory first. MESIF adds a Forward state that nominates exactly one sharer to answer requests, so several caches do not all respond to the same read.
The other axis of variation is how the protocol finds the holders. Small systems snoop: every request is broadcast and every cache checks its own tags. That is simple and low-latency, and it stops scaling once broadcast traffic grows with core count. Large systems use a directory recording which cores hold each line, so invalidations go point-to-point at the cost of an extra hop.
The practical stance: learn MESI as the model, reason with it confidently, and do not assert which protocol a specific chip implements. Vendors rarely document it, it changes between generations, and — the useful part — your optimisation strategy is the same regardless. Every variant makes read sharing cheap and write sharing expensive, so "keep written data private, keep shared data read-mostly" is correct under all of them.
- Modified / Exclusive — sole copy; writes are local and free. This is where well-partitioned code lives.
- Shared — reads free, writes need invalidation. Fine for read-mostly data.
- Invalid — must re-fetch. The state another core's write left you in.
- Owned / Forward — real extensions that cut traffic; the asymmetry they optimise is unchanged.
Key points
- Each cached line carries protocol state that decides whether an access is local or becomes an interconnect transaction.
- Exclusive is what makes uncontended code fast: a sole clean copy can be written without notifying anyone.
- A write to a Shared line must invalidate every other copy first; that is the cost of write sharing.
- Read-for-ownership transfers data cache-to-cache and leaves the previous owner Invalid, which is the ping-pong mechanism.
- MESI is a family — MOESI, MESIF, snooping and directory variants all exist — but all of them make reads cheap and shared writes expensive.
Cache Coherence
Change an input and watch which number moves — and which one refuses to.
MESI is one protocol family among several — MOESI and directory-based schemes differ. The states below are the common teaching set.
Both cores start Invalid. Try: core 1 reads, core 2 reads, core 1 writes.
Alternate writes between the two cores and watch the line bounce between Modified and Invalid. Every bounce is a message on the interconnect. Nothing in the source code shows it — and if the two cores are writing two different variables that happen to share this line, nothing in the source code even suggests they interact.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Load → line Invalid: the core issues a read request onto the interconnect for the current copy.
- 2Peer caches → responder: a core holding the line supplies it, or memory does if none holds it; the requester installs it Shared or Exclusive.
- 3Store → line Shared: the core issues an invalidate, waits for other copies to drop, then upgrades to Modified.
- 4Store → line Exclusive: the core upgrades silently to Modified with no interconnect traffic at all.
- 5Peer read-for-ownership → this core Modified: it supplies the dirty line, then transitions itself to Invalid.
- • "MESI is what my CPU implements" — it is the model; your CPU probably implements an undocumented extension of it.
- • "A store is a store" — a store to an Exclusive line is free and a store to a Shared line is a transaction.
- • "Invalidation means the data was lost" — it means the local copy was dropped; the data is safe with the new owner.
- • "Snooping and directories differ in correctness" — they differ in how holders are located; the guarantee is identical.
Consequences, controls and cost
- • A store can cost a full interconnect round trip or nothing at all, depending purely on the line's current state.
- • Two cores alternately writing one line transfer it on every single access.
- • Read-mostly shared data settles into Shared across cores and stops generating traffic entirely.
- • The same instruction sequence has wildly different costs depending on what other cores did to the line.
- • Arrange for written lines to stay Exclusive to one core by partitioning data per thread.
- • Let shared data be read-mostly so it settles into Shared and stops generating transactions.
- • Batch writes to shared state locally, so ownership transfers happen once per batch rather than once per update.
- • Avoid asserting a specific protocol when reasoning; use the read-cheap/write-expensive asymmetry, which holds for all of them.
- • Watch counters for lines fetched in a modified state from a peer — that event is the read-for-ownership path.
- • Compare a per-thread-private version of the hot structure against the shared one; the delta is protocol cost.
- • Sweep thread count and watch for the throughput peak-then-fall shape that indicates ownership ping-pong.
- • Check the layout of hot written fields for accidental line sharing before assuming the algorithm is at fault.
- • Partitioning to keep lines Exclusive costs memory and adds a combine step.
- • Batching writes reduces transactions but delays visibility of the shared value.
- • Optimising for one machine's protocol variant is fragile; the asymmetry is portable, the specifics are not.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICMESI is a teaching model. Shipping designs use MOESI, MESIF or proprietary variants, and choose snooping or directories by scale. Do not assume specific states or transition costs for a given CPU.
- SIMPLIFIEDThe four-state model omits write-back timing, store buffers, non-temporal stores and the interaction with the memory-ordering rules covered in Why Your Loads and Stores Happen Out of Order.