Cache coherence — MESI protocol in multicore: Question bank

Before we start, one word that must be earned: an invariant is a rule that is always true, at every instant, no matter what the cores are doing. MESI's governing invariant is SWMR = Single-Writer / Multiple-Reader: for each memory line, at any moment there is either exactly one core that may write it, or any number of cores that may only read it — never both. Keep that sentence in your head; most answers below just re-derive it.

True or false — justify

True or false: A line in state E means no other cache holds this line.

True. E (Exclusive) is defined as "sole clean copy." The snoop responses at load time reported no sharers, which is exactly what lets a later write become M silently.

True or false: A line in state M is guaranteed to differ from the value in DRAM.

True by definition — M (Modified) means dirty: this cache holds the only valid copy and memory is stale, which is why a write-back is mandatory before another core may read it.

True or false: A line in state S always matches DRAM.

True. S (Shared) is a clean, read-only copy; it matches memory. The moment any sharer wants to write, it must leave S (via BusUpgr) — so writable-and-dirty never happens while in S.

True or false: Two different caches can simultaneously hold the same line, one in M and one in S.

False. That would be "one writer + one reader" on the same line, violating SWMR. M is exclusive; any other cache holding the line forces both toward S or I.

True or false: Two different caches can simultaneously hold the same line, both in S.

True — that is the entire point of S. Multiple readers with clean copies is the "MR" half of SWMR and is perfectly legal.

True or false: Evicting an E line requires a bus write-back.

False. E is clean (matches DRAM), so it can be dropped silently. Only M (dirty) requires a write-back on eviction. This clean/dirty split is exactly why E and M are separate states.

True or false: MESI guarantees that a program which increments a shared counter without locks will produce the correct total.

False. MESI guarantees each core sees a consistent value for the address, but read-modify-write is several operations; two cores can each read the same value and each write back, losing an increment. You still need atomics — see Atomics, locks, and the LL-SC / cmpxchg.

True or false: Coherence and the memory consistency model are the same guarantee.

False. Coherence is per-address (everyone agrees on the timeline of X). Consistency is cross-address ordering (does the write to X become visible before the write to Y?). MESI gives the first, not the second — that needs fences. See Memory consistency models.

True or false: With MESI, reading shared data is always free once it is cached.

False. An S read is a local hit until another core writes that line. That write invalidates your copy (→ I), so your next read misses and must refetch — the cost is deferred, not removed.

Spot the error

"Core0 is in E and writes; it must broadcast a BusUpgr to invalidate sharers." — where's the error?

There are no sharers to invalidate — E means sole owner. The write is a silent E→M with zero bus traffic. That silent upgrade is the whole reason E exists.

"Core1 has the line in S and writes; it may go straight to M silently like an E line does." — error?

In S you do not know you are alone; other caches may hold clean copies. A write from S must issue BusUpgr/Invalidate first so those copies drop to I. Only then can you be the single writer.

"A core in M snoops a BusRd from another core and simply transitions to I." — error?

On a BusRd (a read, not a write-for-ownership), the M holder must first flush its dirty data (cache-to-cache and to memory), then drop to S — not I. It drops to I only on a BusRdX/Invalidate. Flushing to I on a plain read would lose the only valid copy... wait, it isn't lost, but you'd needlessly invalidate yourself when a shared read-only copy is legal.

"Since coherence works per-address, two cores writing different variables never contend." — error?

Coherence works at cache-line granularity, not per-variable. If the two variables share a 64-byte line, every write ping-pongs the line between cores — that is false sharing. Pad to separate lines (alignas(64)).

"A read miss on Core0 with no other cache holding the line results in state S." — error?

With no sharers, the correct install state is E, not S. Installing S would forfeit the future silent E→M upgrade and force a wasted BusUpgr on the first write.

"On a BusRdX, an S holder must flush its data to the requester." — error?

An S copy is clean and matches DRAM, so it has no fresher data to supply; it simply invalidates itself (S→I). Only a dirty (M) holder must flush. (An E holder is also clean and just goes to I.)

Why questions

Why does MESI have four states instead of just Valid/Invalid?

The extra states are pure performance optimizations of the same SWMR contract: M vs E avoids a write-back when evicting clean data, and E vs S enables the silent first-write upgrade, saving a bus transaction on every freshly-loaded private line.

Why can't we avoid all of this by just writing every store straight to DRAM (write-through, no caching)?

Writes are extremely frequent; a multi-GHz core would spend almost all its time stalling on ~100 ns DRAM trips. We want private caches — MESI's job is to make private caches behave like one shared memory. See Write-back vs write-through caches.

Why is the flush-on-snoop rule essential rather than optional?

Without it, a core reading a line that another core holds dirty in M would fetch stale DRAM. The flush (cache-to-cache transfer) hands over the freshest value, keeping every read consistent as SWMR shifts from single-writer to multiple-reader.

Why does the E state save more bandwidth in real programs than you'd expect?

Most data is thread-local (stack frames, per-thread heap). Each such line loads to E and its first write becomes M silently. Over millions of accesses that is one saved broadcast each — and the interconnect is the scarce shared resource in a multicore. See Bus snooping and interconnects.

Why does false sharing hurt even though the cores touch different bytes?

Because the coherence unit is the whole cache line. Writing any byte requires owning the line in M, which invalidates the other core's copy of the entire line, so the two cores fight over one line despite never touching the same byte.

Why does snooping become impractical at high core counts, and what replaces it?

Every cache must watch every transaction, so bus/broadcast traffic grows with core count and the shared bus becomes a bottleneck. Large chips move to Directory-based coherence, which tracks sharers per line and sends point-to-point messages instead of broadcasting.

Edge cases

Edge case: a line is in I and this core neither reads nor writes it — what happens on another core's BusRdX?

Nothing. I means "as good as not present," so there is no copy to invalidate or flush; the bystander simply ignores the transaction.

Edge case: two cores issue a write to the same I line at (logically) the same time — can both reach M?

No. The interconnect serializes the two BusRdX requests; whichever is ordered first reaches M, and its transaction invalidates/forces the second requester to re-miss. SWMR is preserved because there is a single global order of bus transactions.

Edge case: Core0 holds a line in E and simply evicts it (no write) — is any bus traffic needed?

No. E is clean, so eviction is silent and no other core's state changes. This is the degenerate "clean sole-owner drop" — the cheapest possible eviction.

Edge case: a line sits in M, is never read by anyone else, and is finally evicted — what must happen?

A write-back to DRAM is mandatory because M is dirty and holds the only valid copy; dropping it silently would lose the data. No other cache is involved since nobody else held it.

Edge case: Core0 in S, Core1 in S, Core2 writes the line — what are all three final states?

Core2 issues BusUpgr/BusRdX and becomes M; both Core0 and Core1 snoop the invalidate and drop S→I. Result: exactly one writer, zero readers — SWMR holds.

Edge case: does going from E to M on your own write ever produce a snoop transaction other cores react to?

No — it is the silent upgrade. Because E already proved sole ownership, no invalidate is broadcast, so no other core sees or reacts to anything.

Recall One-line self-test before you close this page

Name the single invariant every question above ultimately checks. ::: SWMR — Single-Writer / Multiple-Reader: for each line, either one writer or many readers, never both, at every instant.