Sources this series builds on: Chili's (ChiliTomatoNoodle) multithreading
playlist,
CMU 15-213 (Computer Systems: A Programmer's Perspective), various CppCon talks,
and LLMs for restructuring and sanity-checking. Everything here is my own code,
compiled and run — not just transcribed.
Recap — and the question this article finally answers
Parts 3 through 5 built up a single-core picture: bytes and addresses, why
caches exist, and cache lines as fixed 64-byte aligned chunks. This article
introduces the piece that was missing — what happens when more than one
core wants the same memory at the same time — and it's the direct,
mechanical answer to the question this series has been sitting on since
Part 1: why did the mutex-protected version cost 13.2 seconds, over 4x
slower than not threading at all?
The new problem: private caches, shared memory
Registers, L1, and L2 are private per core. Only L3 and RAM are shared
across the whole chip (Part 4). That means the same 64-byte cache line can
end up copied into more than one core's private cache at the same time.
If nothing handled this, one core could write a value and another core
could read the same location moments later and get something already out
of date — not because of a bug in your code, purely because of where the
data happened to be cached. Hardware solves this fully automatically, with
no code from you required, via a coherency protocol.
The four states every cached line is tagged with (MESI)
The most common protocol family is called MESI, named after the four
states a cached line can be in on any given core:
- Modified (M) — only this core has it, and it's dirty (differs from memory). Free to read or write. Nobody else has a copy.
- Exclusive (E) — only this core has it, and it's clean (matches memory). Free to read; writing it silently flips it to Modified with zero bus traffic, since nobody else needs telling.
- Shared (S) — this core and at least one other core have clean copies. Free to read. Cannot write without first evicting everyone else's copy — this is the expensive transition.
- Invalid (I) — this core doesn't have a usable copy. The next access is a miss.
Every private cache runs this state machine independently, watching every
other core's traffic to know when to react. You don't configure it or see
it — it's just always running.
What actually crosses the wires
The state diagram shows the outcome. What physically happens on the
interconnect between cores is a small set of message types — every cache
"snoops" (watches) this traffic to see if it needs to react:
| Message | Sent when... | Effect on other cores |
|---|---|---|
| BusRd (Read) | "I want to read a line I don't have" | holders downgrade to Shared; a Modified holder flushes first |
| BusRdX (Read-For-Ownership) | "I want to write a line I don't have" | every other copy anywhere is invalidated |
| BusUpgr (Upgrade) | "I already have it Shared, now I want to write" | every other copy invalidated — no data re-fetch needed, just permission |
| Flush | "I had it Modified and someone else needs it" | dirty data written back before giving up ownership |
Here's the exact sequence two cores fighting over one line generate, every
time ownership swings back and forth:
Every BusRdX round trip costs on the order of the L3/interconnect
latency — tens of cycles — even though the actual arithmetic underneath is
a single cycle. This ping-pong is what's actually being measured whenever
two cores contend for the same line — not the math.
A cost ladder — not every core-to-core interaction is equal
Two cores sharing a line can meet in several different ways, and they are
not all the same price. Cheapest to most expensive:
| Scenario | What happens | Relative cost |
|---|---|---|
| Local hit — already M/E on this core, no contention | Write happens purely in L1, zero bus traffic | Free |
| Cold read/write — nobody else has the line | Fetch from L3/DRAM, no one to invalidate | Cheap |
| Read, another core has it clean | Cache-to-cache copy, no invalidation | Moderate |
| Write, another core has it Shared (upgrade) | Permission-only request, no re-fetch | Moderate |
| Write, another core has it Exclusive/clean | Cache-to-cache transfer, invalidate, no flush | Moderate |
| Read, another core has it dirty | Full flush + cache-to-cache transfer | Expensive |
| Write, another core has it dirty | Full flush + invalidate + cache-to-cache transfer | Most expensive |
The bottom row — write, while the other core is sitting on a dirty
(Modified) copy — is the one that matters most for this series:
Once two threads are both actively writing the same line, every single
write from either side lands in exactly this scenario — because whichever
side wrote last leaves the line Modified, which is precisely the expensive
case for whoever writes next. This back-and-forth, repeating on every write,
is the physical mechanism behind Part 1's 13.2 seconds: 400 million
lock/write cycles, each one paying this full flush-and-invalidate round
trip whenever the line had bounced to the other core since the last write.
The key insight: invalidation happens per line, not per variable
The coherency protocol doesn't know or care that a line contains "your
variable A" and "my unrelated variable B." It only knows this line was
written to — so it invalidates the whole line for every other core
holding it, even if those cores only ever touch a completely different
variable that just happens to live in the same 64 bytes.
Two threads can have zero shared variables in their own program logic —
no mutex, no atomic, nothing that looks like synchronization in the code at
all — and still slow each other down, purely because the hardware treats a
write to any part of a line as a reason to invalidate the entire line. This
isn't hypothetical. It's exactly what's waiting in the next article.
Wait — doesn't this mean coherency already prevents races?
Worth closing a gap explicitly, because it's a natural question once you've
seen how much machinery MESI actually runs: if hardware keeps every core's
cache honest automatically, why did Part 1's cnt += x still race?
Because coherency is a per-transaction guarantee, and cnt += x is not
one transaction — it's three (Part 1: read, modify, write). MESI correctly
guarantees that each individual read or write sees a consistent value.
It says nothing about a sequence of them. Nothing in MESI stops Core B
from sneaking in its own read between Core A's read and Core A's write —
there's no rule saying "once a core reads a line intending to write it
back, nobody else may touch that line until it does." That gap is exactly
where a race condition lives.
Every individual bus transaction above was perfectly coherent — the line
moved Shared → Modified → Invalid → Modified exactly as MESI dictates.
Coherency did its job at every single step. The bug isn't in the protocol;
it's in the gap between load and store, a gap coherency was never designed
to close. This is exactly what the lock prefix fixes and coherency alone
doesn't: it extends exclusive ownership across the whole read-modify-write,
not just one step of it, so no other core's read can slip into that gap.
Glossary added this part
| Term | Meaning |
|---|---|
| Cache coherency | The guarantee that all cores see a consistent, up-to-date view of memory, even with private cached copies |
| MESI | Modified / Exclusive / Shared / Invalid — the four states a cached line can be in |
| BusRd / BusRdX / BusUpgr | The actual messages cores send to read, write, or upgrade permission on a line |
| Snoop | A cache watching bus traffic to see if it needs to react (invalidate, flush) |
lock prefix |
An x86 instruction prefix forcing a read-modify-write to hold exclusive line ownership for its entire duration |
Takeaways
- Cache coherency is real, automatic, and enforced entirely in hardware via a state machine (commonly MESI) and a small set of bus messages — no code of yours configures or sees it directly.
- Not all core-to-core interactions cost the same. Writing while another core holds a dirty copy is the most expensive case there is — a full flush, invalidate, and transfer, every time — and it's exactly the case two threads land in on every write once they're actively contending for one line.
- Coherency and atomicity are different guarantees. Coherency keeps a
single access honest; atomicity (the
lockprefix) keeps a sequence of accesses honest.cnt += xneeds both, and plain non-atomic code only ever gets the first one — which is exactly why Part 1's race happened despite coherency running the whole time. - Invalidation happens per cache line, not per variable — two threads with zero shared variables in their own logic can still contend, purely from memory layout.
Top comments (0)