Level 5 · Research· Lesson 8 of 9 · 45 min
Weak memory and concurrency theory
Formal memory models — sequential consistency, TSO, the C++/Rust model, litmus tests, out-of-thin-air, linearizability, and model checking with loom.
Level 4 taught the memory orderings operationally. This lesson examines the theory beneath them: how memory models are defined, what can and cannot be proven about them, and how correctness of concurrent objects is stated formally.
Sequential consistency and why hardware abandons it
Lamport’s sequential consistency (1979): the result of any execution is as if all operations were executed in some total order consistent with each thread’s program order. It is the model everyone carries in their head — “threads interleave”.
No modern multiprocessor implements it for plain memory accesses, because it forbids two things that make processors fast: store buffers (a write is queued locally before it reaches the cache) and out-of-order execution. Compilers break it too: reordering two independent writes is unobservable to a single thread but visible to another.
A memory model specifies which non-SC behaviours are permitted. There are three kinds to keep apart:
| Level | Examples | Defined by |
|---|---|---|
| Hardware | x86-TSO, Armv8, RISC-V RVWMO, POWER | Vendor specifications; formalised by Sewell, Alglave, Maranget and others |
| Language | C/C++11 and later, Rust (which adopts C++20’s), Java | The language standard |
| Compiler IR | LLVM | Mostly follows C++ |
The language model must be weak enough to compile efficiently to every target and to permit optimisations, and strong enough to program against.
Litmus tests
Memory models are studied through tiny programs that ask “is this outcome allowed?”. All variables start at 0.
Store buffering (SB)
Thread 1 Thread 2
x := 1 y := 1
r1 := y r2 := x
Can r1 = r2 = 0 ?
SC: no. x86-TSO: yes. Arm, POWER: yes. Rust: yes with Relaxed or Release/Acquire; no with SeqCst.
Load buffering (LB)
Thread 1 Thread 2
r1 := x r2 := y
y := 1 x := 1
Can r1 = r2 = 1 ?
Each thread appears to read a value written later by the other. TSO: no. Arm and POWER architectures allow it (loads can be satisfied late); compilers can produce it by reordering the independent load and store. Rust with Relaxed: allowed.
Message passing (MP)
Thread 1 Thread 2
data := 42 r1 := flag
flag := 1 r2 := data
Can r1 = 1 and r2 = 0 ?
TSO: no (stores stay in order). Arm, POWER: yes. Rust: yes if flag is Relaxed (and then it is also a data race if data is non-atomic — UB); no with a Release store and Acquire load. This is the publication pattern from Level 4.
Independent reads of independent writes (IRIW)
Thread 1 Thread 2 Thread 3 Thread 4
x := 1 y := 1 r1 := x; r2 := y r3 := y; r4 := x
Can r1 = 1, r2 = 0, r3 = 1, r4 = 0 ? (the two readers disagree on the order of the writes)
TSO: no. POWER: yes; Armv8 forbids it. Rust: allowed with Acquire loads; forbidden only with SeqCst. This is the canonical case where SeqCst’s single total order gives something AcqRel cannot.
The hardware model in one line each:
- x86-TSO (Sewell et al., 2010): each core has a FIFO store buffer; loads read from the own buffer first. Only store→load reordering. It is why so much incorrect lock-free code “works on my machine”.
- Arm / RISC-V / POWER: loads and stores to different addresses may be reordered in almost any way absent dependencies or barriers.
The herd and diy tools generate and run thousands of such tests against formal models and real chips.
The C++/Rust model, axiomatically
The language model (Boehm and Adve, 2008; formalised by Batty et al., POPL 2011) is axiomatic: instead of describing how a machine steps, it defines which candidate executions are consistent.
An execution is a graph. Nodes are events — reads, writes, updates (RMW), each with a location, value and ordering. Edges are relations:
sb(sequenced-before): program order within a thread.rf(reads-from): links each read to the write whose value it returns.mo(modification order): a total order on the writes to each atomic location.sw(synchronises-with): a release write to the acquire read that reads from it; unlock to lock; spawn; join.hb(happens-before): the transitive closure ofsb ∪ sw.sc: a total order over allSeqCstevents.
A candidate execution is consistent if it satisfies a list of axioms, such as: hb is acyclic; a read does not read from a write that happens after it, nor from one hidden by a later write that happens before the read (coherence); RMWs are atomic (no write intervenes in mo between the value read and the value written); sc is consistent with hb and mo.
Then:
- Enumerate all consistent executions of the program.
- If any of them contains a data race — two conflicting non-atomic accesses unordered by
hb— the program has undefined behaviour. - Otherwise the program’s behaviours are exactly those executions.
Two theorems make this usable:
DRF-SC. If every SC execution of a program is data-race free and it uses only
SeqCstatomics and locks, then all its executions are SC.
Safe Rust is data-race free. (By the type system,
Send/Sync, and the soundness of the libraries — RustBelt.)
Together: in safe Rust with mutexes and SeqCst you may reason by interleaving. Weak memory is something you opt in to, one Ordering at a time.
Two famous flaws
SeqCst was wrong
The original C++11 axioms for SeqCst, when mixed with weaker accesses to the same location, were both too strong to be implemented efficiently on POWER and Arm and too weak to guarantee what programmers expected. Lahav, Vafeiadis, Kang, Hur and Dreyer, “Repairing Sequential Consistency in C/C++11” (PLDI 2017), found the problem and proposed RC11; the fix was adopted in C++20, which is the model Rust references.
Out-of-thin-air
Thread 1 Thread 2
r1 := x (relaxed) r2 := y (relaxed)
y := r1 (relaxed) x := r2 (relaxed)
Can r1 = r2 = 42 ?
Nothing in the program writes 42. Yet the axiomatic rules, read literally, admit an execution where each read “justifies” the other’s write in a causal cycle. No hardware or compiler produces it — and if it were allowed, no invariant about values could ever be proven, and type safety itself would fail (the 42 could be a forged pointer).
The obvious fix — forbid cycles in sb ∪ rf, as RC11 does — also forbids the load-buffering outcome above, which real compilers do produce when they reorder an independent load and store. So the simple fix costs performance on Arm and POWER or forbids standard optimisations.
A semantics that allows load buffering and standard optimisations while forbidding thin-air values has been an open problem for well over a decade. The most influential answer is the promising semantics (Kang, Hur, Lahav, Vafeiadis and Dreyer, POPL 2017; “Promising 2.0”, PLDI 2020): an operational model in which a thread may promise a future write, provided it can certify that it will be able to fulfil the promise when running in isolation. Self-justifying cycles cannot be certified. The standards have not adopted it; the text of C++ says, in effect, “implementations should not do this”.
Operational and axiomatic models
| Axiomatic | Operational | |
|---|---|---|
| Defined as | Consistency predicates over whole execution graphs | A transition system with extra state (buffers, timestamps, views, promises) |
| Good for | Litmus tests, exhaustive exploration of small programs | Program logics, simulation proofs, interpreters |
| Examples | C++11, RC11, the “cat” models of herd | x86-TSO, promising semantics, ORC11, what Miri implements |
Miri’s weak-memory emulation is operational: each atomic location keeps a buffer of recent stores, and a load may return an older one, subject to the thread’s view (a vector-clock-like record of what it has already observed).
Proving concurrent Rust correct
What is “correct”? For a concurrent object the standard criterion is linearizability (Herlihy and Wing, 1990): every concurrent history is equivalent to a sequential one that respects real-time order of non-overlapping operations. Equivalently — and this is the form used in proofs — the implementation contextually refines an atomic specification: no client can distinguish them (Filipović et al., 2010). Under weak memory even this needs care, since “real-time order” is no longer simple.
Program logics for weak memory. Separation logic has been adapted to non-SC models:
- RSL and FSL (Vafeiadis and Narayan, 2013; Doko and Vafeiadis) — relaxed separation logic for release/acquire and for relaxed accesses.
- GPS (Turon, Vafeiadis and Dreyer, 2014) — ghost state, protocols and separation for release/acquire.
- iGPS and iRC11 — these logics rebuilt inside Iris, which is what RustBelt Meets Relaxed Memory (Dang, Jourdan, Kaiser and Dreyer, POPL 2020) uses. It re-proved RustBelt’s results under ORC11, a relaxed model with release/acquire and relaxed accesses, and re-verified
Arc. The proof effort uncovered a real bug:Arc::get_mutused aRelaxedload whereAcquirewas required, admitting a data race. It was fixed in the standard library.
The pattern is worth noticing. Twice — MutexGuard’s Sync bound and Arc::get_mut’s ordering — formal verification of the standard library found bugs that review, testing and years of production use had not.
Model checking
Proofs are expensive. Stateless model checking explores executions of a test exhaustively:
loom(Tokio project): replacestd::syncandstd::threadwith loom’s versions undercfg(loom); loom runs the test under every interleaving, using dynamic partial-order reduction to skip equivalent ones, and models weak behaviours of atomics according to the C11 model (with some bounds and limitations — notably,SeqCsthandling is approximate, and it cannot produce load-buffering behaviours).shuttle(AWS): randomised scheduling with probabilistic guarantees (PCT); scales to larger tests than exhaustive search.- GenMC (Kokologiannakis and Vafeiadis): an exhaustive model checker parametric in an axiomatic memory model (RC11, IMM). Work to drive it from Miri brings sound-and-complete weak-memory exploration to Rust programs.
- CDSChecker, RCMC, Nidhugg — the research lineage.
// A loom test (crate: loom; run with RUSTFLAGS="--cfg loom" cargo test --release)
#[cfg(loom)]
#[test]
fn message_passing_is_safe() {
use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering::*};
use loom::sync::Arc;
loom::model(|| {
let data = Arc::new(AtomicUsize::new(0));
let flag = Arc::new(AtomicBool::new(false));
let (d, f) = (data.clone(), flag.clone());
let t = loom::thread::spawn(move || {
d.store(42, Relaxed);
f.store(true, Release); // change to Relaxed and loom finds the failing execution
});
if flag.load(Acquire) {
assert_eq!(data.load(Relaxed), 42);
}
t.join().unwrap();
});
}
Open questions
- A language-level semantics that forbids thin-air values, permits all intended optimisations, and compiles efficiently to all architectures — and proofs of compilation correctness to Arm and RISC-V models.
- Specification and verification of lock-free algorithms with safe memory reclamation under weak memory.
- Linearizability-like criteria and refinement techniques that are sound under weak memory.
- Interaction of weak memory with Rust’s aliasing model:
noaliasassumptions in concurrent code. - Mixed-size accesses, and atomics shared with other processes or hardware (memory-mapped I/O), which the language model excludes.
- Scalable model checking: exploring realistic programs, not ten-line tests.
Reading list
- Adve and Gharachorloo, “Shared Memory Consistency Models: A Tutorial” (1996) — still the best start.
- Sewell et al., “x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors” (CACM 2010).
- Boehm and Adve, “Foundations of the C++ Concurrency Memory Model” (PLDI 2008).
- Batty et al., “Mathematizing C++ Concurrency” (POPL 2011).
- Lahav et al., “Repairing Sequential Consistency in C/C++11” (PLDI 2017).
- Kang et al., “A Promising Semantics for Relaxed-Memory Concurrency” (POPL 2017).
- Alglave, Maranget and Tautschnig, “Herding Cats” (TOPLAS 2014).
- Herlihy and Wing, “Linearizability: A Correctness Condition for Concurrent Objects” (TOPLAS 1990).
- Dang et al., “RustBelt Meets Relaxed Memory” (POPL 2020).
- Kokologiannakis and Vafeiadis, “GenMC: A Model Checker for Weak Memory Models” (CAV 2021).
- Bos, Rust Atomics and Locks — for the practice that this theory explains.
Exercises
- For each of SB, LB, MP and IRIW, write the Rust program with atomics and state, for each choice of ordering, whether the weak outcome is allowed by the language model.
- Draw the execution graph (
sb,rf,mo,sw) for the weak outcome of MP with relaxed accesses. Show that making the flag accesses release/acquire creates anhbpath that the outcome contradicts. - Run the SB test in a loop of ten million iterations on your machine and count the
(0, 0)outcomes. Then try it on an Arm machine (a phone or a Raspberry Pi) with the MP test. - Write the loom test above, change
ReleasetoRelaxed, and read the failing trace. - Explain why the thin-air example threatens type safety, not only functional correctness.
- State the linearization points of a lock-free counter built on
fetch_add, and of the Treiber stack’spush. Then explain why “linearization point” is harder to define under relaxed memory.
Check your understanding
Pick an answer to see the explanation.
1.What does the DRF-SC theorem state?
2.In the store-buffering litmus test, why can both threads read 0 on x86?
3.What is the out-of-thin-air problem?