Memory models — sequential consistency, TSO, relaxed
WHY does a memory model even exist?
WHAT it governs: the visible ordering of operations on different memory locations across threads. (Single-location ordering is handled by cache coherence and is assumed everywhere.)
HOW we reason: we pick a small canonical test (a litmus test), enumerate which final register/memory values are possible, and a memory model is simply which outcomes it allows.
The ladder of models (strong → weak)
| Reordering allowed? | SC | TSO | Relaxed |
|---|---|---|---|
| Store → Load | ✗ | ✓ | ✓ |
| Store → Store | ✗ | ✗ | ✓ |
| Load → Load | ✗ | ✗ | ✓ |
| Load → Store | ✗ | ✗ | ✓ |
Deriving the canonical litmus tests from first principles
Store Buffer (SB) test — distinguishes SC from TSO
Shared x = y = 0. Two threads:
T1: x = 1; r1 = y;
T2: y = 1; r2 = x;
Message Passing (MP) test — distinguishes TSO from Relaxed
T1: data = 42; flag = 1; // producer
T2: while(flag==0){} r = data; // consumer
The language layer: C11/C++11 memory orders
memory_order_relaxed— only atomicity + per-location coherence. No cross-location ordering.acquire(loads) /release(stores) — a release-store synchronizes-with an acquire-load that reads it, publishing everything before the release. Implements MP correctly.seq_cst(default) — restores a single global total order (SC) across allseq_cstops. On x86 aseq_cststore ≈ store +MFENCE; on ARM ≈ barriers.
Flashcards
What does a memory model specify?
Define sequential consistency.
What single relaxation defines TSO vs SC?
Which reorderings does TSO forbid?
Which reorderings does a relaxed model (ARM/POWER) allow?
In the SB test, is r10 && r20 possible under SC?
In the SB test, is r10 && r20 possible under TSO/x86?
What instruction restores SC for the SB pattern on x86?
In the MP test, can the consumer see flag==1 but stale data under TSO?
In the MP test, why can relaxed hardware show stale data?
What C++ orders implement correct MP cheaply?
What does a release→acquire pair guarantee?
Recall Feynman: explain it to a 12-year-old
Imagine each worker (CPU core) writes notes and drops them in an outbox. A note isn't seen by others until the mail actually goes out — even though the worker already moved on. Sequential consistency = a strict office where one shared list records every action in one true order, so everyone agrees what happened when. TSO = the office mostly agrees, but each worker has a little outbox, so they can do their next reading before their last written note has been mailed. Relaxed = a chaotic office where letters arrive in any order unless you explicitly stamp "send this one first!" (a barrier). The stamp is slow but guarantees order.
Connections
- Cache Coherence (MESI) — guarantees single-location ordering; memory models govern multi-location ordering.
- Store Buffers and Out-of-Order Execution — the hardware reason TSO exists.
- Memory Barriers and Fences — MFENCE, DMB, lwsync/sync, isb.
- C++ Atomics and memory_order — language-level model.
- Lock-free Programming — where release/acquire and seq_cst matter most.
- Peterson and Dekker Locks — break under TSO without a fence (SB pattern).
- Happens-before and Synchronizes-with — formal ordering relation.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Socho har CPU core apne "store buffer" naam ke chhote outbox me likhe gaye values temporarily rakhta hai. Memory model basically ek contract hai jo batata hai ki dusre threads tumhare reads aur writes ko kis order me dekh sakte hain. Sequential Consistency (SC) sabse strict hai — jaise ek single global list ho jisme sab operations ek hi true order me likhe jaate hain, sab cores us par agree karte hain. Yahan koi surprise nahi, lekin hardware slow ho jaata hai.
TSO (x86 isi par chalta hai) thoda relaxed hai: sirf ek hi cheez allow hai — store ke baad ka load aage nikal sakta hai, kyunki store abhi buffer me pada hai aur globally visible nahi hua. Isi wajah se SB litmus test me r1==0 && r2==0 x86 par possible hai, jo SC me kabhi nahi hota. Iska fix: store aur load ke beech MFENCE lagao, jo buffer ko drain kar deta hai.
Relaxed models (ARM, POWER, RISC-V) bilkul jungli hain — chaaron reorderings allowed hain. Yahan agar tum producer-consumer MP test karo (data=42; flag=1;), to consumer ko flag==1 dikh sakta hai par data abhi bhi purana (0)! Isliye ARM par tumhe release-acquire ya barrier (DMB) explicitly use karna padta hai. Yaad rakho: code me "pehle likha" ka matlab "globally pehle visible" nahi hota weak hardware par. Aur ek bada trap — x86 strong hai isliye galat code bhi "chal jaata" hai, par compiler bhi reorder karta hai, isliye hamesha std::atomic aur sahi memory_order use karo, na ki sirf chip ke behaviour par bharosa.