Foundations — MESI - MOESI coherence protocols
This page is the ground floor for MESI/MOESI. Before we can talk about states like Modified or messages like BusRdX, we have to earn every word: what a cache is, what a "line" is, what "dirty" means, what a "bus" is, and what "snooping" looks like. We build each from a picture, in an order where nothing is used before it exists.
1. Core, memory, and the speed gap — WHY caches exist at all
The picture: memory is a long shelf of numbered mailboxes. Address X is one mailbox; right now it holds the value 5.
WHY we need anything more: a core runs far faster than main memory can answer. If the core waited for RAM on every load, it would spend most of its life idle. So we put a small, fast copy-store right next to the core.
The picture: a tiny sticky-note pad on each core's desk. Instead of walking to the mailbox shelf, the core scribbles a copy onto its own pad and reads that.
2. Cache line — the unit everything happens to
The picture: you don't photocopy one letter of the library book, you photocopy a whole page. The page is the line.
WHY this matters for the whole topic: the coherence rules track state per line, not per byte. This is the seed of False Sharing — two cores touching different variables that happen to sit on the same line still fight over it, because the line is the smallest thing the protocol can reason about.
3. Address, value, and "the same X in two places"
The picture below is the entire reason coherence exists: address X in RAM says 5, Core 0's pad says 5, Core 1's pad says 5. Three copies, all agreeing — for now.
WHY it's dangerous: the moment one core scribbles a new value on its pad without telling anyone, the copies disagree. Whoever reads an old pad reads a stale (out-of-date) value.
4. Clean vs Dirty — has this copy been edited?
The picture: a clean pad and a shelf mailbox both show 5 (agree). A dirty pad shows 9 while the mailbox still shows 5 (disagree — the pad is ahead).
WHY the topic needs this word: "dirty" is one of the two yes/no questions MESI answers. A dirty line is precious — it holds the only up-to-date value, so it must be written back before it can be thrown away. This connects to Write-back vs Write-through caches: MESI/MOESI assume write-back caches, where writes stay local (making a line dirty) instead of going straight to memory every time.
5. Exclusive vs Shared — how many copies exist?
The picture: exclusive = one pad in the whole classroom has this page. Shared = several pads have photocopied the same page.
WHY the topic needs this word: this is the second yes/no question. Combine the two questions and you get the whole MESI table:
| Only copy | Others may have it | |
|---|---|---|
| Dirty | (exclusive + dirty) | (the gap MOESI fills) |
| Clean | (exclusive + clean) | (shared + clean) |
Every MESI state is just one cell of this 2×2 grid. You already understand the questions; the parent note only gives them letters (M/E/S). See also Cache Coherence vs Memory Consistency — coherence is about this single address staying consistent across caches; consistency is the separate question of ordering across different addresses.
6. The bus — the shared wire everyone can hear
The picture: a single classroom loudspeaker. Anyone can announce something; everyone hears every announcement. Because only one can speak at once, we need bus arbitration to decide whose turn it is.
The picture: each student keeps one ear on the loudspeaker. When they hear "everyone tear out page 7," anyone holding page 7 acts.
WHY the topic needs this: snooping is how the protocol enforces its rules without a central boss. The alternative — a directory that tracks who holds what — scales better to many cores but is a different mechanism; MESI is classically explained on a snooping bus.
7. Bus messages — the vocabulary of the protocol
Now that "bus" and "snooping" exist, the two core messages make sense:
The picture: BusRd is asking a classmate "can I photocopy your page?". BusRdX is announcing "I'm about to edit this page — everyone tear yours out so nobody reads a wrong version."
8. Invalidate and Write-back — the two corrective actions
The picture: crumpling your photocopy into the bin because you heard someone is editing the master.
The picture: before you throw away a page you edited, you first walk to the library and update the master book — otherwise your edits are lost forever.
WHY these two exist: every dangerous scenario is fixed by one of them. A reader about to get a stale value → the dirty holder does a write-back (or forwards its value) first. A writer about to create a second, conflicting copy → it invalidates everyone else first. These two moves are the SWMR guarantee in action.
9. SWMR — the promise all of this keeps
The picture: a whiteboard with a "MARKER" token. Whoever holds the token may write, and while they hold it everyone else must step back. Drop the marker, and many people may crowd in to read — but the moment someone wants to write again, they grab the token and everyone else steps away.
This single sentence is what the entire MESI/MOESI state machine exists to guarantee. Every transition in the parent note is derivable from the question "does this keep SWMR true?"
Prerequisite map
Read it top-down: hardware facts (cache, line) create the problem (shared copies), the two questions become the state grid, the bus enables snooping and messages, and messages enable the corrective actions — together they enforce SWMR, which is exactly what MESI/MOESI encode.
Equipment checklist
- What is a cache and why does every core have a private one? ::: A small fast memory next to the core holding copies of recent data, so the core avoids slow trips to main memory.
- What is a cache line and why is it the unit of coherence? ::: A fixed-size chunk (≈64 bytes) copied as a whole; protocol state is tracked per line, not per byte.
- What does "dirty" mean? ::: The cache holds a newer value than main memory because a write happened locally and hasn't been written back yet.
- What is the difference between an exclusive and a shared copy? ::: Exclusive = this cache is the only holder; shared = other caches may also hold the line.
- What is a bus, and what does snooping mean? ::: A shared wire where every cache hears every message; snooping is each cache listening and reacting to messages about lines it holds.
- What is the difference between BusRd and BusRdX? ::: BusRd just fetches a copy to read; BusRdX fetches AND invalidates every other copy so the requester may write next.
- What are the two corrective actions and when is each used? ::: Invalidate (drop your copy before someone writes) and write-back (flush a dirty line to memory before losing it).
- State the SWMR invariant from memory. ::: For any location, at any instant, either exactly one core writes (no other valid copies) OR any number read with no writer.