Memory Consistency Models
Two threads share a flag and a data variable, with no locks in sight. Thread A writes `data = 42` then `flag = 1`. Thread B spins on `flag` and then reads `data`. On paper, once B sees `flag == 1`, it should also see `data == 42`. On real multicore hardware, this can fail. B can observe `flag == 1` while `data` still reads as its old value. This is not a bug in Cache Coherence. Coherence only guarantees that all cores eventually agree on the value of each individual memory location. It says nothing about the order in which writes to different locations become visible to other cores. That missing piece is the memory consistency model. It governs the order in which memory operations from different threads become visible to each other. Consistency models matter for a clear reason. Every multithreaded program, every lock-free data structure, every garbage collector's write barrier, and every compiler's instruction scheduler depends on ordering assumptions. Get the model wrong and you get race conditions. These reproduce once in a billion executions, vanish under a debugger, and only appear in production at scale. Hardware vendors relax ordering guarantees aggressively because strict ordering costs real performance. It forces store buffers to drain. It blocks instruction reordering. It stalls out-of-order execution pipelines that also rely on Hardware Multithreading and Simultaneous Multithreading to hide latency. The consistency model is the contract that lets programmers, compiler writers, and hardware designers reason about the same program. They can do this without knowing each other's implementation details. The big picture is a spectrum. At one end sits sequential consistency (SC), the model that matches naive intuition. The whole multithreaded execution behaves as if all operations from all threads were interleaved into one global sequence. Each thread's own operations stay in program order. At the other end sit relaxed (or weak) models. These include x86-TSO, ARM/POWER weak ordering, and the C++/Java memory models. They permit visible reordering of independent operations in exchange for speed. They require programmers to insert explicit fences (memory barriers) or use synchronization primitives. This restores the orderings they actually need. This article builds the mental model from the ground up. It covers what guarantees SC actually makes, and why hardware wants to violate them. It explains the concrete mechanisms (store buffers, speculative loads) that cause violations. It covers the standard relaxed models and their fence vocabulary. It also covers the litmus tests architects use to distinguish one model from another. It closes by connecting consistency models to how correctness is achieved at the scale of Warehouse-Scale Computing. There, thousands of cores across many chips must still agree on a coherent notion of "happens-before."
- Cache coherence guarantees agreement on one memory location; a consistency model governs ordering across locations and across threads.
- Sequential consistency (SC): all operations appear in a single global order consistent with each thread's program order — intuitive but expensive.
- Real hardware uses relaxed models (store buffering in x86-TSO; further reordering in ARM/POWER) enabled by write buffers and speculative execution.
- Litmus tests like store-buffering (SB) and message-passing (MP) empirically distinguish which reorderings a model permits.
- Fences/barriers and synchronization primitives (locks, atomics with acquire/release) restore the orderings programmers need without paying for global ordering everywhere.
- Language-level models (C++11, Java) define data-race-free semantics: if you synchronize correctly, you get SC-like behavior — "SC for data-race-free programs."
A memory consistency model is the contract specifying which reorderings of memory operations across threads are legal to observe — and hardware relaxes that contract for speed, shifting the burden of ordering onto explicit fences and synchronization.
The idea
A memory consistency model defines, for a shared-memory multiprocessor, the set of legal outcomes for any program that reads and writes shared variables from multiple threads. It answers a precise question: given the reads and writes each thread issues, in what orders may those operations appear to take effect, as observed by other threads? This is a distinct concern from cache coherence. Coherence is a per-location guarantee — it ensures all cores see a single agreed-upon sequence of values for one variable, and that writes to that variable eventually become visible. Consistency is a cross-location, cross-thread guarantee — it constrains how operations on different variables interleave in the global view. The gold-standard reference model is sequential consistency, formalized by Leslie Lamport in 1979: a multiprocessor is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. SC has two components worth separating: program order (each thread's own operations stay in the order the thread issued them) and a single global total order into which all threads' operations are interleaved atomically. This second requirement is what makes SC strong: it forbids any observer from seeing operations interleaved differently from any other observer. Real processors deviate from SC because enforcing a strict global order forecloses common hardware optimizations. A store buffer lets a core retire a store instruction immediately into a small FIFO buffer, forwarding the value to its own later loads, while the store drains to the coherent cache hierarchy asynchronously — this hides store latency but lets a later store's effects, or a remote core's load, become visible before an earlier store does. Out-of-order execution lets independent loads and stores issue outside program order as long as single-thread data dependencies are respected, but nothing forces two independent memory operations to become globally visible in program order. Speculative load execution allows a load to execute early and be validated later; if invalidated, the pipeline squashes and replays — but a load can transiently observe a stale value in the interim in ways that leak into weaker models. Each of these mechanisms buys instruction-level parallelism at the cost of ordering guarantees, and consistency models are precisely the vocabulary for stating exactly which guarantees survive.
How it works
The strict end: sequential consistency
Under SC, imagine a single arbiter that, at each step, picks one thread and lets it perform its next memory operation (in program order), updating a single shared global memory instantaneously. Every thread's view of memory is this same interleaved sequence — there is no way for two threads to disagree about the relative order of two operations. SC can be implemented (inefficiently) by making every core execute memory operations strictly in program order, one at a time, with each store completing (becoming visible to all cores) before the next instruction issues. This forbids store buffering, forbids most reordering, and stalls the pipeline on every store — devastating for performance.
Litmus tests: the empirical vocabulary
Architects describe consistency models using small, canonical programs called litmus tests. Two are foundational.
Store Buffering (SB). Initially `x = y = 0`. ``` Thread 1 Thread 2 x = 1 y = 1 r1 = y r2 = x ``` Under SC, can both `r1 == 0` and `r2 == 0`? No — for both loads to read the old value 0, both stores must be ordered after both loads in the global order, which is impossible since each thread's store precedes its own load in program order. Yet on x86 (TSO) hardware, `r1 == 0 && r2 == 0` is observable, because each store initially lands in a private store buffer, and each thread's own load can race ahead and read memory before its own store has drained.
Message Passing (MP). Initially `data = 0`, `flag = 0`. ``` Thread 1 Thread 2 data = 42 r1 = flag flag = 1 r2 = data ``` Under SC, if Thread 2 observes `r1 == 1` (it saw the flag), it must also observe `r2 == 42` (SC forbids the flag's store from passing the data store in the global order, and forbids Thread 2's own load of `data` from passing its load of `flag`). This does hold on TSO (x86), because TSO preserves store-store order and load-load order from the same thread of causally related stores in this pattern — but it can fail on more aggressively relaxed models (like ARM or POWER without a fence) because those models permit store-store reordering, letting the `flag` write become globally visible before the `data` write.
The relaxed spectrum
Consistency models are organized by which program orders they preserve:
| Model | Preserves | Relaxes | Representative hardware |
|---|---|---|---|
| Sequential Consistency (SC) | all four orderings (load→load, load→store, store→load, store→store) | none | reference model, MIPS R10000 in strict mode |
| Total Store Order (TSO) | load→load, load→store, store→store | store→load (via store buffer) | x86, SPARC (default) |
| Partial Store Order (PSO) | load→load, load→store | store→load, store→store | SPARC (relaxed mode) |
| Weak / Release Consistency | none by default; ordering only around synchronization | almost everything | ARMv7, ARMv8 (weak mode), POWER |
Weak models require the programmer (or compiler) to insert explicit memory fences (also called barriers) to force ordering at specific points:
- A store fence (`sfence`, or a full fence) ensures all prior stores are globally visible before any later store.
- A load fence (`lfence`) ensures all prior loads have completed before any later load issues.
- A full fence (`mfence`, `dmb` on ARM, `sync` on POWER) orders everything before it against everything after it.
- Acquire/release semantics — a lighter-weight idiom used in C++11 `memory_order_acquire`/`memory_order_release` and Java `volatile` — order a specific load (acquire) so nothing after it in program order can be reordered before it, and a specific store (release) so nothing before it can be reordered after it. Paired correctly (a release store observed by an acquire load), they recreate the MP litmus test's intuitive guarantee without a full fence's cost.
The programmer-facing contract: data-race-free programming
High-level languages (C++11, Java, and, following them, Rust) adopt a pragmatic compromise: they guarantee sequential consistency only for programs free of data races — programs where every conflicting access (a write and any concurrent access to the same location) is mediated by synchronization (locks, atomics). This is the DRF-SC (data-race-free implies SC) contract. It lets ordinary programmers write correctly-synchronized code and reason about it as if it ran under SC, while compilers and hardware are still free to aggressively reorder unsynchronized accesses, which by DRF assumption can never be observed to race. ```pseudocode // Message-passing pattern, made correct on a relaxed model // using explicit acquire/release ordering. // Shared: data : int = 0 flag : atomic = 0 // Thread 1 (producer) procedure PRODUCE(): data = 42 // ordinary store ATOMIC_STORE(flag, 1, memory_order_release) // release: publishes data // Thread 2 (consumer) procedure CONSUME(): loop: r1 = ATOMIC_LOAD(flag, memory_order_acquire) // acquire if r1 == 1: break r2 = data // guaranteed to see 42 assert r2 == 42 // Correctness argument: // The release store to `flag` establishes a "synchronizes-with" edge // to the acquire load that observes value 1. // Program order (data write -> release write) combined with // synchronizes-with (release write -> acquire read) // combined with program order (acquire read -> data read) // yields a happens-before chain: // data=42 --po--> flag=1(rel) --sw--> flag==1(acq) --po--> read data // happens-before is transitive, so data=42 happens-before read data, // forcing r2 == 42 in any correct implementation. ``` ```pseudocode // A minimal spinlock built from acquire/release primitives, // showing how ordinary mutual exclusion recreates SC-like // behavior for the critical section on a relaxed-model machine. procedure LOCK(L: atomic): while COMPARE_AND_SWAP(L, 0, 1, memory_order_acquire) != 0: pause() // spin, back off procedure UNLOCK(L: atomic): ATOMIC_STORE(L, 0, memory_order_release) // Any two threads' critical sections guarded by the same L // are totally ordered: the release-unlock of one critical // section synchronizes-with the acquire-lock of the next, // so all shared-memory effects inside one critical section // happen-before all effects inside the next. ```
Complexity & correctness
Time cost of enforcement, not asymptotic complexity. Consistency models are not algorithms with input-size-dependent asymptotics; the relevant "complexity" is the per-operation latency overhead a model imposes, and it trades off directly against the reordering freedom given to hardware.
- SC enforcement cost. A literal SC implementation must make each store's effect globally visible (propagated through the coherence protocol and acknowledged) before the issuing core proceeds to its next memory operation. If a coherence invalidation round trip costs on the order of tens to a couple hundred cycles (typical cross-core/cross-socket latencies), a strict SC machine pays that latency on every store, serialized. Since store instructions are commonly a sizable fraction (often 15–30%) of dynamic memory operations, this is a severe, uniformly-applied tax.
- TSO cost. A store buffer decouples the issuing core's forward progress from the coherence round trip: the store is buffered in O(1) time locally, and drains asynchronously. The cost reappears only at explicit `mfence`/`lock`-prefixed instructions, which the compiler and programmer insert only where cross-thread ordering matters — e.g., around a handful of synchronization operations per critical section rather than every store. This is the core efficiency argument for relaxed models: pay the round-trip latency O(number of synchronization points) instead of O(number of stores).
- Weak-model cost. ARM/POWER go further, allowing store-store and load-load reordering absent explicit barriers, which lets the memory system and out-of-order core exploit even more independence between unrelated accesses — at the price of requiring more, and more careful, fence placement in hand-written concurrent code.
Correctness argument for DRF-SC. The guarantee that "data-race-free programs behave as if sequentially consistent" rests on a happens-before relation, built from two ingredients: 1. Program order: within one thread, operation a happens-before operation b if a precedes b in that thread's code. 2. Synchronizes-with: a release-store of a synchronization variable happens-before every subsequent acquire-load of that same variable that reads the stored value (or a value from a later release in the release sequence). Happens-before is the transitive closure of these two relations. The correctness claim is: if a program is properly labeled — every pair of conflicting accesses (same location, at least one is a write) from different threads is separated by a happens-before edge — then the program cannot exhibit a data race, and the only observable outcomes are exactly those obtainable under some SC interleaving. Proof sketch. Suppose, for contradiction, that a data-race-free program produces a result impossible under any SC interleaving. Because there is no data race, every pair of conflicting accesses is ordered by happens-before, which forms a strict partial order (irreflexive: no operation happens-before itself, by well-foundedness of program order plus acyclicity of synchronizes-with in any realizable execution; transitive: by definition). Any strict partial order on a finite set of events extends to a total order (topological sort) that respects it — this is precisely a legal SC interleaving, since it respects each thread's program order and respects the observed synchronization order. Because the memory model guarantees that unordered (non-conflicting or non-racing) operations cannot affect each other's outcome, the result under this topological-sort interleaving matches the actual result. This contradicts the assumption, so no such impossible result exists. Hence DRF programs behave exactly as SC.
The honest tradeoff. DRF-SC says nothing about programs with data races — and relaxed hardware is explicitly permitted to produce "impossible," non-SC results in that case (as the SB and MP litmus tests show). This is a deliberate, load-bearing design choice: it lets 99% of application code (written against locks, atomics, and language-level memory models) enjoy simple SC-like reasoning, while lock-free data-structure authors and compiler/runtime engineers absorb the complexity of reasoning about the underlying relaxed model directly.
Worked example
Trace the message-passing litmus test on TSO (x86-like) hardware step by step, showing why the naive interleaving intuition is right here, but the SB test shows it can fail elsewhere. Initial state: `data = 0`, `flag = 0` in shared memory, each core has its own store buffer.
| Step | Core 1 (producer) | Core 2 (consumer) | Store buffer C1 | Store buffer C2 | Shared memory |
|---|---|---|---|---|---|
| 0 | — | — | empty | empty | data=0, flag=0 |
| 1 | `data = 42` (buffered) | — | [data=42] | empty | data=0, flag=0 |
| 2 | `flag = 1` (buffered) | — | [data=42, flag=1] | empty | data=0, flag=0 |
| 3 | store buffer drains in FIFO order: data=42 commits first | `r1 = flag` reads 0, spins | [flag=1] | empty | data=42, flag=0 |
| 4 | flag=1 commits (FIFO order preserved) | `r1 = flag` reads 0, spins | empty | empty | data=42, flag=1 |
| 5 | done | `r1 = flag` reads 1, exits loop | empty | empty | data=42, flag=1 |
| 6 | — | `r2 = data` reads 42 | empty | empty | data=42, flag=1 |
Result: `r1 == 1, r2 == 42` — matches SC intuition. The key structural fact making this work on TSO specifically is that store buffers drain in FIFO order (store-store order is preserved), so `flag=1` can never become globally visible before `data=42` does, since they were enqueued in that order by the same core. Now contrast with the SB litmus test on the same TSO hardware.
| Step | Core 1 | Core 2 | Store buffer C1 | Store buffer C2 | Shared memory |
|---|---|---|---|---|---|
| 0 | — | — | empty | empty | x=0, y=0 |
| 1 | `x = 1` (buffered) | `y = 1` (buffered) | [x=1] | [y=1] | x=0, y=0 |
| 2 | `r1 = y`: forwards from shared memory, not own buffer (y not in C1's buffer) → reads 0 | `r2 = x`: similarly reads 0 from shared memory | [x=1] | [y=1] | x=0, y=0 |
| 3 | buffers drain | buffers drain | empty | empty | x=1, y=1 |
Result: `r1 == 0, r2 == 0` — impossible under SC, because under SC one of the two stores must precede both loads in the single global order, forcing at least one load to see the new value. This demonstrates concretely that TSO is strictly weaker than SC: MP "just happens" to be preserved by TSO's FIFO store-buffer draining, while SB is not, because SB's violation comes from store→load reordering (a core's own load bypassing its own not-yet-drained store to a different address), which TSO explicitly permits and SC forbids. This is exactly the row marked "S→L ✗" for TSO in the spectrum figure.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Assuming coherence implies consistency | Coherence is per-location; consistency is cross-location/thread ordering | Treat them as orthogonal guarantees; check the ISA's memory model document, not just its cache protocol |
| "It worked on my x86 laptop" | x86/TSO is comparatively strong (preserves most orders); code without fences may silently break on ARM/POWER | Test on, or reason about, the weakest model you must support; never rely on incidental TSO strength |
| Missing fence around double-checked locking | The classic broken singleton: a non-atomic flag check races with an unfenced object construction | Use acquire/release atomics (or a proper `once`-style primitive), not raw flags |
| Treating `volatile` as a memory fence in C/C++ | C/C++ `volatile` only prevents compiler reordering/elision, not hardware reordering | Use `std::atomic` with explicit memory orders for cross-thread synchronization |
| Believing one fence "fixes" a lock-free algorithm | Fences must be placed at both the release side and the acquire side to form a synchronizes-with edge | Verify with a litmus-test-style argument: trace the happens-before chain end to end |
| Reasoning about relaxed atomics using SC intuition | `memory_order_relaxed` provides no ordering with other operations, only atomicity | Reserve relaxed atomics for counters/statistics; use acquire/release or seq_cst for publication patterns |
Pioneers & history
The formal notion of sequential consistency was crystallized by Leslie Lamport, building on decades of concurrent-systems work by researchers wrestling with the gap between hardware reality and programmer intuition. As multiprocessors moved from research curiosities to mainstream servers and then to every multicore laptop and phone, memory models moved from a niche hardware-verification concern to a first-class concept in programming-language design, culminating in the explicit memory models of Java (2004-era JSR-133) and C++11.
Origins · 1 minLeslie Lamport and how this was discovered
Lamport formalized sequential consistency in his 1979 paper "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," giving architects and programmers a precise, checkable definition of what "correct" shared-memory behavior means. His broader body of work on logical clocks, the Bakery algorithm for mutual exclusion, and Paxos for distributed consensus shaped how the field reasons about ordering and agreement across independent, asynchronous actors — the same core problem, at different scales, that consistency models address for shared-memory multiprocessors.
Where this matters
Every concurrent runtime and every operating-system kernel encodes assumptions about consistency models directly in its lowest-level primitives. The Linux kernel's `smp_wmb`/`smp_rmb`/`smp_mb` barrier macros exist purely to bridge the gap between architectures with different consistency guarantees (x86 vs. ARM vs. POWER) so that lock-free kernel data structures (RCU, seqlocks, wait-free queues) behave identically across platforms. Language runtimes for Java, C++, Rust, and Go each specify an explicit memory model precisely so that garbage collectors, JIT compilers, and concurrent collections (lock-free hash maps, work-stealing deques) can be proven correct against a fixed contract rather than "whatever the current CPU happens to do." Database engines and distributed key-value stores build their own consistency ladders (linearizability, causal consistency, eventual consistency) directly on top of the same happens-before intuition first developed for shared-memory hardware. At the largest scale, understanding the cost of strict ordering — and where it can be safely relaxed — is exactly the design discipline that lets Warehouse-Scale Computing systems scale synchronization-heavy workloads across racks of machines without paying an SC-sized latency tax on every memory operation; the same store-buffer-and-fence vocabulary reappears, translated, as the cross-datacenter ordering guarantees offered by distributed consensus and replication protocols.
Ask the tutor: How would you rewrite the message-passing example using only relaxed atomics, and what specifically would break?
Is cache coherence the same thing as memory consistency?
No. Cache coherence guarantees that all cores eventually agree on the value of any single memory location and that writes to it become visible in some consistent order for that location alone. Consistency governs the ordering across different locations and across threads — for instance, whether a write to `data` becomes visible before a later write to `flag`, as seen by a third thread. A machine can have perfect cache coherence (every core agrees on each variable's value history) while still permitting SC-violating behaviors like the store-buffering litmus test, because coherence alone never constrains inter-variable ordering. The two mechanisms work together: coherence ensures individual locations behave sanely, and the consistency model layered on top governs how operations on multiple locations interleave.
Why doesn't every processor just implement sequential consistency?
Because a literal SC implementation forces every store to be acknowledged by all other cores (via the coherence protocol) before the issuing core can proceed, which serializes the pipeline on coherence round-trip latency for every store instruction. Modern out-of-order cores rely on store buffers and speculative execution to hide memory latency, both of which introduce visible reorderings that violate strict SC. Vendors instead adopt relaxed models like TSO that preserve most useful orderings cheaply and require explicit fences only where the programmer truly needs stronger guarantees, trading a small amount of programmer/compiler complexity for a large amount of hardware performance.
What exactly does a memory fence (barrier) do?
A fence is an instruction that restricts reordering across a specific point in the instruction stream. A store fence ensures all preceding stores are globally visible before any subsequent store; a load fence ensures preceding loads complete before subsequent loads issue; a full fence orders everything before it against everything after it in both directions. Fences do not make memory operations faster — they add latency exactly where placed — but they let programmers "pin down" the handful of orderings that matter (like publishing a data structure via a flag) without paying for global ordering on every single memory access.
What is a litmus test and why do architects use them?
A litmus test is a minimal, canonical concurrent program — usually two or three threads with a handful of loads and stores — designed to expose exactly one kind of reordering. Store-buffering (SB) exposes store→load reordering; message-passing (MP) exposes store→store or acquire/release violations. Architects and formal-methods researchers use suites of these tests (and tools like the herd7 simulator) to empirically and formally characterize which outcomes a real chip or a written specification permits, because full consistency-model specifications are notoriously easy to get subtly wrong in prose, while litmus tests give an unambiguous, checkable ground truth.
Does using `volatile` in C or C++ make a variable safe for cross-thread synchronization?
No, and this is a very common misconception. In C and C++, `volatile` only prevents the compiler from eliminating, reordering, or caching accesses to that variable in registers — it says nothing about the hardware's memory ordering. Two threads can each read/write a `volatile` variable and still observe hardware-level reorderings (like the SB or MP litmus test failures) because `volatile` inserts no fences and provides no acquire/release semantics. The correct tool is `std::atomic` with an explicit memory order (`acquire`, `release`, `seq_cst`), which is guaranteed by the language standard to insert whatever fences or atomic instructions the target hardware needs.
How do Java and C++ memory models relate to hardware consistency models?
Both languages define an abstract memory model — specifying happens-before, synchronizes-with, and (in C++) explicit memory-order tags on atomics — independent of any specific CPU architecture. A compiler targeting x86, ARM, or POWER is responsible for translating these language-level guarantees into whatever concrete fences or atomic instructions that hardware's consistency model requires: on x86/TSO, an acquire load often needs no extra instruction (TSO is already strong enough), while on ARM it may need an explicit `ldar`/`dmb`-class instruction. This layering is exactly what lets a correctly-synchronized Java or C++ program behave identically (under DRF-SC) regardless of which underlying hardware consistency model it runs on.
Can a program with data races ever be considered "correct" under these models?
Under the DRF-SC contract, a program with an unsynchronized data race has undefined behavior in the formal sense used by C++ and Java: the language memory model makes no guarantee about the outcome, and compilers are permitted to assume racy code paths are unreachable, sometimes optimizing in ways that make the bug worse (not just "wrong value" but arbitrary behavior). Certain narrow patterns — relaxed atomics used purely for statistics counters, or hardware-specific lock-free algorithms verified against a fixed model — can be deliberately racy-looking but are actually synchronized through atomics with carefully chosen memory orders, which is different from an accidental data race on plain variables.