1.1Consistency (a.k.a. Memory Consistency, Memory Consistency Model, or Memory Model)

Why correctness of shared memory is a real question

Most multicore chips support shared memory in hardware: every core can read and write a single shared address space. Such a shared memory system shared memory system A system in which processor cores read and write a single shared address space. defined in Chapter 1 — open in glossary is judged on performance, power, and cost — but none of that matters unless the system is correct first. And here is the surprise that motivates half of this book: it is genuinely hard even to define what “correct shared memory” means, let alone to build hardware that satisfies the definition. The subtleties must be mastered in silicon, where a bug fix costs a respin, and they bite academics too — a proposed design that ignores them simply won’t work.

Two distinct topics govern this correctness, and this book is organized around keeping them apart:

• Memory consistency — the definition of correct shared-memory behavior. An architectural specification, visible to software.
• Cache coherence cache coherence Making caches functionally invisible by propagating one processor's writes to other processors' caches; a means of supporting a consistency model, not a correctness definition itself. defined in Chapter 1 — open in glossary — a mechanism (invisible to software in the systems of chapters 6–9) that most hardware uses to help enforce a consistency model. Coherence is a means, not the correctness criterion itself.

This section introduces the first topic.

A consistency problem you already understand

Before any formalism, the book grounds the idea in a story with no computers in it — just a university registrar, a schedule website, and a student. Step through it:

The registrar performed her two “writes” — (1) change the room on the schedule, (2) tell students to look — in a perfectly sensible order. The student observed them in the opposite order and went to the wrong room. Note that nothing was lost and everything was eventually updated; the failure was purely one of ordering as observed by a reader.

A memory consistency model memory consistency model The precise, architecturally visible definition of shared-memory correctness in terms of loads and stores; usually admits multiple correct executions. defined in Chapter 1 — open in glossary is the rule-book that decides whether this behavior is correct (so a careful user must protect herself) or incorrect (so the system must prevent the reordering). Either answer can make a workable system — what’s fatal is not writing the rule down.

From registrars to hardware

The story used email and text messages, but real shared-memory hardware reorders in exactly the same way, through mechanisms like:

• out-of-order cores, which execute memory operations in a different order than the program lists them;
• write buffers, which hold committed stores before they reach the cache (these star in Chapter 4);
• prefetching, which reads data earlier than the program asks for it;
• multiple cache banks, which let different addresses proceed at different speeds.

Each of these is a performance feature. Each can make one thread’s writes visible to another thread in a surprising order. So we must define shared memory correctness — which behaviors are allowed — so that programmers know what to expect and implementors know the limits of what they may build.

What a memory model actually specifies

Shared memory correctness is specified by a memory consistency model — or just memory model. Precisely:

For a multithreaded program executing with specific input data, the memory model specifies what values dynamic loads may return and, optionally, what the possible final states of memory are.

Contrast this with a single-threaded core. There, the architecture mandates that executing a thread transforms a given input state into a single well-defined output state — even on a wildly out-of-order core, there is one correct result and everything else is wrong. Shared memory is different: because the ISA allows multiple threads to run concurrently, with many legal interleavings of their instructions, many different executions are all correct — and many more are incorrect. One correct answer becomes a set of correct answers, and that multiplicity is what makes consistency subtle.

The road ahead (chapters 3–5)

The consistency track of this book unfolds in three steps:

1. Sequential consistency (Chapter 3). The strongest, most intuitive model: a multithreaded execution must look like an interleaving of each thread’s sequential execution, as if all threads were time-multiplexed on a single core. The chapter formalizes SC and shows how to implement it — naively, then aggressively, ending with the MIPS R10000.
2. Total store order (Chapter 4). The model of x86 and historical SPARC. Motivated by a concrete optimization: FIFO write buffers that hold committed stores before they drain to the cache. That optimization violates SC — but it is so valuable that architects defined a new model, TSO, that permits it.
3. Relaxed models (Chapter 5). Most orderings enforced by strong models are unnecessary: if a thread updates ten data items and then a synchronization flag, nobody cares whether the ten updates happen in order — only that all ten precede the flag. Relaxed models (studied via the example model XC) enforce order only where the programmer asks for it with a FENCE instruction. The chapter also shows the great escape hatch: write your program data-race-free, and most relaxed models promise you SC behavior anyway (“SC for DRF”).

In the registrar’s terms: email + web admin + text messages form an extremely weak consistency model, and the registrar needed a FENCE after her email — wait for the schedule to actually change — before texting.