Memory Consistency Models

Coherence keeps a single location honest: everyone agrees on the order of writes to X. But real programs touch many locations, and the moment two threads read and write X and Y, a new and much harder question appears: in what order does each thread see the other's operations across different variables? That question is memory consistency, and it is where computer architecture reaches up and grabs the programmer by the collar.

This is the most software-facing lesson in the module. Get it wrong and your lock-free code has a bug that appears once a week on one customer's machine and never in your tests. The rules that decide what reorderings the hardware may perform — and how you, the programmer, can forbid them — are the memory consistency model.

Coherence vs consistency — the crucial distinction

Coherence is per location: all cores see the writes to any one address in a single agreed order;
Consistency is across locations: it governs the order in which one core's reads and writes to different addresses become visible to other cores;
coherence is necessary but not sufficient — a perfectly coherent machine can still let threads disagree about the relative order of accesses to different variables.

Keep the slogan: coherence is about one variable; consistency is about the story across variables.

Sequential consistency: the intuitive ideal

The model every programmer wishes the hardware provided is sequential consistency (SC), defined by Leslie Lamport: the result of any execution is the same as if all cores' operations were executed in some single interleaved order, and within each core the operations appear in program order. In plain words: pretend the machine has one memory and one clock, and the threads simply take turns, never reordering their own instructions. It is exactly the mental model you use when you reason about threads on a whiteboard.

SC is beautifully simple to think about — and painfully expensive to build. It forbids the processor from letting a later load overtake an earlier store, even to a different address, even when doing so would be completely safe for a single thread. That reordering is one of the biggest sources of performance in a modern core (it hides store latency behind independent loads). Enforcing SC means giving that up, so essentially no mainstream processor implements it.

The reordering that breaks intuition

Here is the canonical example. Both x and y start at 0. Two threads run:

\text{T1: } x \leftarrow 1;\ r_1 \leftarrow y \qquad\qquad \text{T2: } y \leftarrow 1;\ r_2 \leftarrow x

Under sequential consistency, can both threads end with r_1 = 0 and r_2 = 0? Think it through: for r_1 = 0, T1's read of y happened before T2 wrote y; for r_2 = 0, T2's read of x happened before T1 wrote x. Those two demands contradict each other — impossible under SC. The code below enumerates every SC interleaving to prove (0,0) never appears:

// Enumerate every sequentially-consistent interleaving of: // T1: (a) x=1 (b) r1=y T2: (c) y=1 (d) r2=x // Program order must hold within each thread: a before b, c before d. function interleavings(): string[][] { const out: string[][] = []; function go(a: number, c: number, acc: string[]): void { if (a === 2 && c === 2) { out.push(acc.slice()); return; } if (a < 2) go(a + 1, c, acc.concat(a === 0 ? "x=1" : "r1=y")); if (c < 2) go(a, c + 1, acc.concat(c === 0 ? "y=1" : "r2=x")); } go(0, 0, []); return out; } const seen = new Set<string>(); for (const order of interleavings()) { let x = 0, y = 0, r1 = 0, r2 = 0; for (const step of order) { if (step === "x=1") x = 1; else if (step === "y=1") y = 1; else if (step === "r1=y") r1 = y; else if (step === "r2=x") r2 = x; } seen.add(`(r1=${r1}, r2=${r2})`); } console.log("SC-reachable outcomes:", [...seen].sort().join(" ")); console.log("Is (r1=0, r2=0) possible under SC? ", seen.has("(r1=0, r2=0)"));

Yet on real x86, ARM and POWER hardware, (0,0) does happen. Why?

Why: the store buffer

The culprit is the store buffer. When a core executes x \leftarrow 1, it does not wait for the write to reach cache — that could take dozens of cycles. It drops the store into a small FIFO buffer and moves on immediately to the next instruction, the read of y. So the load of y can complete before the store of x is visible to anyone else. The load has effectively overtaken the store. Do this in both threads and you get (0,0) — a result no interleaving of the original program allows.

This specific relaxation — a load may bypass an earlier store to a different address — is called Total Store Order (TSO), and it is what x86 actually implements. TSO keeps almost all of SC's guarantees (stores from one core still reach others in order) but permits exactly this store→load reorder, because the store buffer is too valuable to give up.

A spectrum of models — and the fence

Architectures sit on a spectrum from strict to relaxed. The more reorderings a model allows, the faster the hardware and the more careful the programmer must be.

Model	Reorderings allowed	Programmer burden	Real example
Sequential (SC)	none	trivial to reason about	(essentially none in HW)
TSO	store→later-load only	low — need a fence for that one case	x86-64, SPARC TSO
Weak / release	almost any, unless a fence forbids it	high — fences/acquire-release everywhere shared	ARM, POWER, RISC-V

The programmer's tool for clawing back order is the memory fence (a barrier — x86's \texttt{MFENCE}, ARM's \texttt{DMB}). A fence forbids the hardware from moving accesses across it: put an \texttt{MFENCE} between the store and the load in the example, and it drains the store buffer first, killing the (0,0) outcome. In modern code you rarely write fences by hand — you use acquire/release atomics (a lock's release "publishes" everything before it; an acquire "sees" it), and the compiler emits the right fences for you. Every mutex, every lock-free queue is built on exactly this.

Because relaxation is performance, and it is worth the most where power matters most. ARM and RISC-V chose weak models precisely to let the hardware reorder aggressively and skip the bookkeeping TSO needs — cheaper, cooler, simpler cores, which is gold in a phone. The bet is that ordinary code is already race-free (protected by locks), and only the tiny amount of lock-free and synchronisation code needs explicit fences. The C++11 and Java memory models exist to make this bearable: you write to the language's model with \texttt{atomic} and acquire/release, and the compiler translates to whatever fences the target ISA needs. Write the fences right and weak hardware is both correct and fast; write them wrong and you get the bug that only reproduces in production.

The most dangerous misconception here: "the caches are coherent, so my threads will see consistent values." No. Coherence guarantees nothing about the ordering across different variables. The flag-based handoff \texttt{data = 42; ready = true;} in one thread and \texttt{while(!ready){} use(data);} in another can still break on relaxed hardware: the reader may see \texttt{ready} become true while \texttt{data} still reads its old value, because the two stores were reordered. Coherence keeps each variable honest; only a fence or a release/acquire pair orders them relative to each other. Never rely on coherence to order different locations.