Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 67 ยท Memory Hierarchy

Cache Coherence and Memory Consistency

Understand how multicore caches stay in sync: the MESI protocol, false sharing and memory consistency models, with a MESI simulator and a litmus test.

On a single core, a cache is invisible: the program always sees the latest value it wrote. A multicore chip breaks that comfort. Each core has its own private L1 (and often L2) cache, and two of them may hold copies of the same memory block. If core 0 changes its copy, core 1's copy is now stale, and a program that reads it gets the wrong answer.

Two separate questions follow. Cache coherence asks: how do the copies of one memory location stay in agreement? Memory consistency asks: in what order do the reads and writes of many locations appear to other cores? This lesson answers the first with the MESI protocol and the second with a famous litmus test. It builds on the write-back caches from Replacement and Write Policies.

The coherence problem

Suppose a shared variable x is 0 in memory, and both cores have read it. Core 0 now executes x = 1. With a write-back cache, core 0 updates only its own copy. Core 1 keeps reading 0 from its private cache, perhaps forever. A coherent system must guarantee two things for every memory location:

  1. Write propagation: a write by one core becomes visible to the others eventually.
  2. Write serialization: all cores see the writes to that location in the same order.

The standard solution for a small number of cores is snooping. All caches are connected to a shared bus (or ring), and every cache watches ("snoops") the transactions that other cores place there. When a cache sees a request that affects a block it holds, it reacts. The usual reaction on a write is to invalidate its own copy, so the writer holds the only valid one. Larger machines use directories instead, which record which cores hold each block and send point-to-point messages, because a broadcast bus does not scale.

The MESI protocol

Each cache line carries a two-bit state. In MESI the four states are:

State Meaning Memory up to date? Other caches may hold it?
Modified Only this cache has it, and it was written No (this copy is newest) No
Exclusive Only this cache has it, not yet written Yes No
Shared Possibly several caches hold it, unchanged Yes Yes
Invalid The line holds no usable data n/a n/a

Transitions are driven by two kinds of events: the core's own reads and writes, and the bus transactions snooped from other cores.

stateDiagram-v2
  [*] --> I
  I --> E: own read, no other copy
  I --> S: own read, others have it
  I --> M: own write (BusRdX)
  E --> M: own write (silent)
  S --> M: own write (BusUpgr)
  E --> S: snoop - other core reads
  M --> S: snoop read - flush data
  M --> I: snoop write - flush and invalidate
  E --> I: snoop write
  S --> I: snoop write

MESI transitions. Reads and writes that hit in M, or read hits in E and S, need no bus traffic.

Three details make MESI better than the simpler MSI protocol:

  • The E state lets a core that is the only reader of a block write to it silently, with no bus transaction, because nobody else can have a copy. Programs that mostly touch private data benefit a lot.
  • A write to an S line sends a small upgrade (or invalidate) message and does not need to refetch the data.
  • A snooped read of an M line forces that cache to flush the dirty data (to memory or directly to the requester) before the line drops to S.

A MESI simulator

The class below tracks the state of one block in each of three caches and counts bus transactions. A script of reads and writes shows how the states move.

Python MESI state changes for one block

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk through the trace:

  • Step 1. Core 0 reads with no other copies, so it gets E. Step 2. Its write needs no bus message: E to M silently.
  • Step 3. Core 1 reads. Core 0 holds a dirty copy, so it flushes it and both caches move to S. Step 4 adds core 2 as a third sharer.
  • Step 5. Core 2 writes to its shared copy. One upgrade message invalidates the other two copies, and core 2 becomes M.
  • Step 6. Core 0 reads again; its copy is invalid, so it misses. Core 2 must flush the new value. This is the price of sharing: the data bounces between caches.
  • Step 7. Core 1 has no copy, so it issues a read-for-ownership; the two sharers (no dirty owner now) are invalidated.

The final tally of 4 reads on the bus, 1 read-for-ownership, 1 upgrade and 2 write-backs is the traffic you pay for communication through memory. Variants exist: MOESI (AMD) adds an Owned state so a dirty line can be shared without writing it back first, and MESIF (Intel) adds a Forward state to pick one sharer to answer requests.

False sharing

Coherence works on whole blocks (typically 64 bytes), not on individual variables. That creates a nasty effect called false sharing: two cores update two different variables that happen to sit in the same block. Logically they never communicate, but the hardware sees writes to one block and ping-pongs it back and forth.

The next simulator makes two cores alternate writes to their own counters. In one run the counters are 8 bytes apart (same block), in the other 64 bytes apart (different blocks).

Python False sharing in a block-granular cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 2,000 writes in total, the shared-block layout misses on every write and causes 1,999 invalidations, while the separated layout misses only twice (the first write by each core) and then runs entirely from private caches. On real hardware this can slow a parallel loop several times over, even though the program has no data race.

The fix is padding or alignment: give each thread's hot data its own cache line, for example by padding a per-thread counter structure to 64 bytes or by using language features such as C++ alignas(64). Compilers do not do this for you because it wastes memory. It is one of the standard tricks you will meet again in Writing Cache- and CPU-Friendly Code.

Memory consistency: the order of different locations

Coherence says every core agrees about the order of writes to one address. It says nothing about how writes to different addresses are ordered from another core's point of view. That is the job of the memory consistency model, a contract between the hardware and the programmer.

The strongest model is sequential consistency (SC): the result is as if all operations of all cores were interleaved into one sequence, with each core's operations in program order. It is the easiest to reason about but forbids useful optimisations.

Real CPUs relax SC. A very common optimisation is the store buffer: when a core executes a store, it parks the value in a small queue and keeps going, instead of waiting for the cache line to arrive in M state. Later loads by the same core can read the buffered value, but other cores cannot see it until the store drains to the cache. x86 uses this design (called total store order, TSO). ARM and RISC-V allow even more reordering, and need explicit fences or acquire/release instructions to restore order when you need it.

The classic test uses two cores, with x and y both starting at 0:

  • Core 0: x = 1, then r1 = y
  • Core 1: y = 1, then r2 = x

The program below explores every possible interleaving, once under SC and once with store buffers.

Python The store-buffer litmus test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Under sequential consistency, at least one core must run its store before the other core's load, so the outcome (r1, r2) = (0, 0) is impossible. With store buffers it appears: both stores sit in their buffers while both loads read the old values from memory. This is not a bug; it is the documented behaviour of x86, and it is why lock-free algorithms such as Dekker's mutual exclusion need a memory fence (on x86, MFENCE or a locked instruction) between the store and the load.

For everyday programming you rarely write fences yourself. Locks, atomics and language memory models (Java's volatile, C++ std::atomic) insert the right ones. The practical rule: if two threads touch the same variable and at least one writes, use a synchronisation primitive.

Coherence does not make your code thread-safe. It keeps single locations consistent, but a pair of operations like "read x, then write x + 1" can still interleave between cores. That needs an atomic instruction or a lock.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between cache coherence and memory consistency?

    Coherence handles multiple copies of a single address. Consistency defines the legal orderings of accesses to many addresses as seen by different cores.
  2. 2. A core holds a line in the Exclusive state and writes to it. What happens?

    In E, the core knows no other cache has a copy, so it can write immediately and mark the line Modified without telling anyone.
  3. 3. What is false sharing?

    Coherence works on whole blocks. Independent variables in one block make the block bounce between caches even though the threads never share data logically.
  4. 4. In the store-buffer litmus test, which outcome is possible with store buffers but not under sequential consistency?

    Both stores can sit in their buffers while both loads read the old zero values from memory. Under SC one store must precede the other core's load.
  5. 5. Why is a Shared line said to need an upgrade message before a write?

    A Shared line can exist in several caches. To keep one writable copy, the writer broadcasts an invalidate and then moves to Modified.

Summary

  • Private caches in a multicore chip can hold stale copies; coherence keeps the copies of each location in agreement through write propagation and write serialization.
  • Snooping protocols broadcast on a bus; directory protocols track sharers and scale to many cores.
  • MESI gives each line a state (Modified, Exclusive, Shared, Invalid); the E state makes writes to private data free of bus traffic.
  • Coherence works on blocks, so independent variables in one block cause false sharing; padding to 64 bytes avoids it.
  • Memory consistency defines the order of accesses to different locations; sequential consistency is the strongest, and store buffers make real CPUs weaker.
  • Use locks, atomics or fences for shared data; coherence alone does not make code thread-safe.

Continue with Virtual Memory and Paging.