Skip to main content
Be Bitwise

Memory Ordering & Barriers

Advanced Concurrency · VR Foundations track

7 min read

In this module

Why Memory Ordering Matters

Write x = 1; y = 2; in C and the natural assumption is that every other thread sees x change first. On x86 that holds up most of the time, courtesy of its relatively strong memory model (Total Store Order). On ARM or RISC-V, another core might cheerfully see y become 2 before x becomes 1. The CPU reorders memory operations to chase performance, and absent explicit ordering, your carefully designed concurrent algorithm rots from the inside out.

CPU Memory Models

A memory model defines which reorderings a CPU is allowed to perform. Think of it as the contract between hardware and programmer.

Sequential Consistency is the strongest model. Every operation appears to execute in a single global total order consistent with each thread's program order. No mainstream CPU defaults to this — it's just too expensive to implement.

Total Store Order (TSO), the model on x86 and SPARC, permits one key reordering: a load may be reordered ahead of an earlier store to a different address. Stores land in a store buffer and don't become visible to other cores until they drain into cache. The owning core gets to read its own stores early from the buffer (store-buffer forwarding), while everyone else sees them later. So x86 can exhibit store-load reordering but never store-store or load-load.

Relaxed models (ARM, RISC-V, POWER) let almost anything reorder: loads past loads, stores past stores, loads past stores. The hardware gets maximum freedom to schedule and reorder. The programmer pays the bill, sprinkling explicit barriers wherever ordering actually matters.

Store Buffers and Visibility

Every CPU core has a store buffer — a small queue that parks pending writes before they hit cache. When a core executes a store, the value lands in the buffer first. The core then keeps charging through subsequent instructions without waiting for cache coherence to settle. Great for hiding write latency, terrible for anyone expecting other cores to observe the write immediately.

text
Core 0: Core 1:
x = 1; // in store buffer y = 1; // in store buffer
r0 = y; // reads 0 (!) r1 = x; // reads 0 (!)

On x86, both r0 and r1 can simultaneously read 0. That's the classic store buffering (SB) litmus test. (It's sometimes confused with IRIW, "independent reads of independent writes", which is a different test with four threads.) Even on TSO hardware the reordering is perfectly legal: each core reads cache before the other core's store buffer has drained.

Real threads can't run in the browser runner, and a two-thread test would only show (0, 0) now and then anyway. So this program models the two store buffers and enumerates every order in which the six events (two stores, two loads, two buffer drains) can happen. Predict which of the four (r0, r1) outcomes each setup allows before you run it.

Try itPredict all three rows first; the middle one, with a fence on only one core, is the one people get wrong.
C (GCC 9.2.0)

In C11 terms, the fix is memory_order_seq_cst on all four accesses, which GCC compiles on x86 to an xchg (or mov plus mfence) for each store. Release stores and acquire loads aren't enough here: (0, 0) is still allowed under acquire/release, because SB is precisely the store-then-load reordering they permit.

Memory Fences

A memory fence (or barrier) is an instruction that prevents certain reorderings from crossing it.

  • Store fence (sfence on x86): all stores before the fence become visible before any stores after it.
  • Load fence (lfence on x86): all loads before the fence complete before any loads after it.
  • Full fence (mfence on x86, dmb on ARM): no loads or stores cross the fence in either direction.

On x86, ordinary stores are already ordered with each other and loads with each other, so sfence mainly matters for non-temporal (streaming) stores, and lfence today is mostly used to stop speculation. The reordering x86 does allow, store then load, needs mfence or a lock-prefixed instruction.

On ARM, you have even finer-grained barriers: dmb ish (inner shareable domain, the most common), dmb ishst (store-only barrier), and dmb ishld (load-only barrier).

Compiler vs CPU Barriers

Two layers of reordering can ruin your day. The compiler reorders during optimisation. The CPU reorders during execution. A compiler barrier like asm volatile("" ::: "memory") in GCC blocks the compiler but does nothing to the CPU. A hardware fence blocks the CPU. The C11/C++11 atomic primitives bundle both — compiler and hardware barriers — appropriate to whichever memory order you ask for.

Cache Coherence Protocols

Cache coherence protocols keep all cores agreeing on what's in memory despite each holding its own private cache. The most widespread is MESI (Modified, Exclusive, Shared, Invalid), extended to MOESI on AMD (an extra Owned state) and MESIF, which Intel introduced with its QuickPath Interconnect (an extra Forward state). Which protocol a given chip actually runs depends on the generation and on whether it's a multi-socket part.

Under MESI, when Core 0 wants to write to a cache line Core 1 also holds in Shared state, Core 0 fires off an invalidation message. Core 1 marks its copy Invalid. Core 0 promotes the line to Modified. That invalidation traffic is the hidden tax on every concurrent program. Each write to a shared variable kicks off coherence chatter that scales with core count, and at 64 cores you're suddenly very aware of which lines are bouncing.

Happens-Before Relationships

The C11 and C++11 memory models formalise ordering through happens-before relationships. If operation A happens-before B, then A's effects are guaranteed to be visible to B. Happens-before falls out of three sources:

  • Program order: within a single thread, every operation happens-before the next.
  • Synchronisation: an atomic store with release ordering happens-before an atomic load with acquire ordering that reads the stored value (or a later value).
  • Transitivity: if A happens-before B and B happens-before C, then A happens-before C.

acquire and release semantics map to one-way barriers. An acquire load stops subsequent operations from drifting up past it. A release store stops preceding operations from drifting down past it. Together they form a synchronisation pair that establishes ordering between threads without paying for a full fence.

c
// Thread 1 (producer)
data = 42; // (1)
atomic_store_explicit(&flag, 1, memory_order_release); // (2)
// Thread 2 (consumer)
while (atomic_load_explicit(&flag, memory_order_acquire) != 1); // (3)
printf("%d\n", data); // guaranteed to print 42 // (4)

This is the message passing (MP) litmus test, and acquire/release is exactly enough for it. The release store at (2) makes everything in (1) visible before (2) becomes observable. The acquire load at (3) ensures (4) sees every write that happened before (2). Stitched together, Thread 2 is guaranteed to read data = 42.

SB, MP and a third test, load buffering (LB), where each thread reads one variable and then writes the other, make a handy set for comparing memory models. Pick a test and a model below and see which final register values survive. Try MP on Arm with no barriers, then with a DMB in T0 only, and work out why fixing the writer alone doesn't save the reader.

Litmus test explorer

Two threads, shared variables x and y, both 0 at the start. Pick a test and a memory model, then check which final register values the model allows.

Memory model

MP (message passing). T0 writes the data x, then sets the flag y. T1 reads the flag, then the data.

T0
  1. x = 1
  2. y = 1
T1
  1. r0 = y
  2. r1 = x
Final outcomes of MP under Arm (relaxed) with no barriers
OutcomeUnder Arm (relaxed)SC interleavings
r0 = 0, r1 = 0allowed1 of 6
r0 = 0, r1 = 1allowed4 of 6
r0 = 1, r1 = 0surprisingallowed0 of 6
r0 = 1, r1 = 1allowed1 of 6

r0 = 1, r1 = 0 is allowed under Arm (relaxed) with no barriers. T1 saw the flag but not the data it was meant to publish.

Arm may make the two stores visible out of order, and may also satisfy the two loads out of order.

Why there’s no step-through for Arm

Arm’s behaviour can’t be drawn as one store buffer per core: stores can reach other cores in different orders and loads can be satisfied out of order. Switch to x86-TSO to watch store buffers at work.

Sequential consistency and x86-TSO outcomes are found by trying every order of events; x86-TSO uses the store-buffer machine of Sewell et al., “x86-TSO”, CACM 2010. Arm verdicts are the published architectural results (Alglave, Maranget and Tautschnig, “Herding cats”, TOPLAS 2014; Pulte et al., POPL 2018), not a simulation. The SC column counts interleavings of the program as shown.

Practical Implications

When writing concurrent code, use the highest-level abstractions available: mutexes, condition variables, and channels. These include the correct memory barriers internally. If you must use atomics, prefer memory_order_seq_cst (the default) unless profiling shows it is a bottleneck. Only then consider weaker orderings like acquire/release, and only after careful reasoning about which orderings your algorithm actually requires. Getting memory ordering wrong produces bugs that are architecture-dependent, non-deterministic, and nearly impossible to reproduce in testing.