Cache coherence and memory consistency
The MESI protocol and snooping, directory protocols, false sharing, sequential consistency with proof, store buffers and the TSO model, fences and atomic operations.
In a multicore processor every core has its own caches, but memory is shared: when a core modifies a datum, the others must see the new value and not an old copy left in their caches. Two different questions must be kept apart: coherence, which concerns a single address, and consistency, which concerns the order in which operations on different addresses become visible. In this lesson we look at the MESI protocol, directory protocols, false sharing, the sequential consistency model with the proof of one of its properties, and why real processors violate it.
The coherence problem
Core 0 reads variable 
, which ends up in its cache; core 1 reads it and modifies it in its own. If core 0 rereads from its cache, it gets the old value. A system is coherent if, for every address, all cores see the writes in the same order and a read always returns the last value written according to that order. The Computer Systems course introduced the problem; here we see how hardware solves it.
The MESI protocol
In systems with few cores the caches are connected to a common medium that all of them observe (snooping): every cache “listens” to the requests of the others. Every block in a cache is in one of four states:
- M (modified): only this cache has the block, and it differs from memory;
- E (exclusive): only this cache has the block, equal to memory;
- S (shared): the block may be in several caches, all equal to memory;
- I (invalid): the block is not valid.
The fundamental rule is single writer or multiple readers. To write a block a cache must have it in state M or E: if it has it in S, it first sends an invalidation request, and all other copies go to I. When another cache asks to read a block that is in M, the owner supplies the up-to-date data and goes to S. The E state is an important optimisation: a datum read by a single core, a very frequent case, can then be written without any bus message, going straight to M.
Directory protocols
Snooping requires every request to reach every cache: with 
cores each miss generates 
lookups, and with tens of cores the common medium becomes the bottleneck. Large systems use a directory: for every memory block a record says which caches have a copy and in what state. Requests go to the directory, which forwards invalidations only to the caches concerned. Traffic no longer grows with the number of cores but with the number of actual copies, at the price of the memory occupied by the directory and an extra hop.
False sharing
Coherence works on blocks, typically 64 bytes, not on variables. If two cores modify two different variables that sit in the same block, for instance two adjacent counters in an array, every write by one invalidates the other’s copy, and the block bounces back and forth between the two caches, even though the two cores share no data. This is false sharing: a correct parallel program can run slower than the sequential one. It is solved by spacing the data used by different threads at least one block apart.
Sequential consistency
Coherence is not enough. Consider two threads, with 
initially:
- thread 1:
; then 
- thread 2:
; then 
The most intuitive model is sequential consistency (Lamport, 1979): the result must be that of some interleaving of the operations of all threads in a single order, in which every thread keeps its own program order.
Theorem. Under sequential consistency, the outcome 
is impossible.
Proof. Consider the last of the four operations in the global order. It cannot be a write, because in each thread the write precedes the read. If it is , then happened before, and 
. If it is , then happened before, and 
. In every case at least one of the two is 1. ∎
Why processors violate it
Yet on an x86 processor the outcome is actually observed. The reason is the store buffer: so as not to stall, each core puts its write into a buffer and immediately goes on with the read, which goes to the cache. Both reads can happen while both writes are still in the buffers, invisible to the other core: both read 0. The x86 model, called TSO (total store order), allows exactly this reordering of a read before an earlier write to a different address. The ARM and RISC-V architectures have even more relaxed models, which allow almost all reorderings, in exchange for better performance.
The programmer restores order when needed with fences, instructions that force earlier operations to complete before later ones, and with atomic operations (read-modify-write such as compare-and-swap), on which locks and concurrent data structures are built. Modern languages (C11, C++11, Java, Rust) define their own memory model and translate atomic operations into the right fences for each processor: a data-race-free program, which protects every shared datum with a lock or an atomic operation, behaves as if consistency were sequential.
