--- title: Memory Consistency and Synchronization module: Multithreading & Multicore moduleNumber: 9 lessonNumber: 4 order: 904 summary: > Coherence keeps cores agreeing about one location; consistency is the contract about many. We define sequential consistency, then watch real hardware break it: the store buffer lets a load slip ahead of an older store, and the classic two-thread litmus test ends with both sides reading zero. We state x86-TSO precisely, restore order with mfence, build atomic read-modify-write from the lock prefix, xchg, and cmpxchg, and write a spinlock twice — once naively, once bus-friendly — closing with what lock-free progress actually guarantees. topics: [Multithreading & Multicore] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §12.4–12.5 Shared Variables, Synchronizing Threads; §3.5 Arithmetic and Logical Operations" --- [Coherence](/computer-architecture/multithreading-and-multicore/cache-coherence) made a careful, narrow promise: for each memory location _taken alone_, all cores see one agreed sequence of values. It said nothing about how operations on **different** locations interleave, and everything interesting a parallel program does — hand off a buffer, publish a pointer, take a lock — involves at least two locations: the data and the flag that announces it. The contract governing that is the machine's **memory consistency model**, and the central fact of this lesson is that no mainstream machine gives you the contract you would naively assume. ## The model you assume: sequential consistency Start with the intuitive rule, stated precisely. > **Definition (Sequential consistency).** A machine is sequentially consistent > (SC) if every execution's result could have been produced by interleaving the > threads' operations into one global sequence in which (1) each thread's own > operations appear in its program order, and (2) each read returns the value > of the latest write to that address in the sequence. SC says the machine may shuffle threads together any way it likes, but it may not reorder _within_ a thread, and everyone watches the same single tape. Under SC, multithreaded programs mean what they appear to mean. $$ % caption: Sequential consistency: some interleaving of the two program orders % caption: into one global tape, each thread's own order preserved. Any such % caption: merge is legal; nothing else is. \begin{tikzpicture}[font=\footnotesize,>=stealth, op/.style={draw, minimum width=17mm, minimum height=6mm, inner sep=1pt}, gl/.style={draw, fill=acc!8, minimum width=17mm, minimum height=6mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node at (-3.4,2.9) {thread A}; \node[op] (a1) at (-3.4,2.2) {x = 1}; \node[op] (a2) at (-3.4,1.3) {r1 = y}; \draw[->] (a1) -- (a2); \node at (-3.4,-0.1) {thread B}; \node[op] (b1) at (-3.4,-0.8) {y = 1}; \node[op] (b2) at (-3.4,-1.7) {r2 = x}; \draw[->] (b1) -- (b2); \node at (2.6,2.9) {one legal global tape}; \node[gl] (g1) at (2.6,2.2) {x = 1}; \node[gl] (g2) at (2.6,1.4) {y = 1}; \node[gl] (g3) at (2.6,0.6) {r1 = y reads 1}; \node[gl] (g4) at (2.6,-0.2) {r2 = x reads 1}; \draw[->] (g1) -- (g2); \draw[->] (g2) -- (g3); \draw[->] (g3) -- (g4); \draw[->, acc, thick] (-2.3,2.2) -- (g1.west); \draw[->, acc, thick] (-2.3,-0.8) to[bend right=16] (g2.west); \end{tikzpicture} $$ Run thread A = `x = 1; r1 = y` against thread B = `y = 1; r2 = x` (both variables start 0) and enumerate every SC interleaving: whichever load runs last, at least one store precedes it in the global order, so under SC $$\lnot\,(\texttt{r1} = 0 \,\land\, \texttt{r2} = 0).$$ We return to this outcome below. ## Why real hardware reorders: the store buffer SC forbids exactly the optimizations a fast core depends on. The one that matters most is the **store buffer**. A store cannot commit to the L1 until the core owns the line in **M**, which may mean a `BusRdX` and a long wait. Stalling every store on coherence traffic would stall the [pipeline](/computer-architecture/pipelining/the-complete-pipe-processor), so the core instead drops the store into a small private queue, the store buffer, and moves on. The buffer drains to the cache when ownership arrives. Loads check the buffer first (**store forwarding**), so the core always sees its _own_ stores; other cores see nothing until the drain. > **Definition (Store buffer).** A per-core FIFO holding stores that have > retired but not yet reached the cache. The owning core's loads read from it; > no other core can. A store becomes globally visible only when it drains. $$ % caption: The store buf\/fer sits between the core and its L1. Stores queue and % caption: drain when the line is owned; the core's own loads check the buf\/fer % caption: f\/irst, so a core never notices its stores are still in f\/light. \begin{tikzpicture}[font=\footnotesize,>=stealth, b/.style={draw, minimum width=24mm, minimum height=7mm, align=center}, q/.style={draw, minimum width=24mm, minimum height=5.5mm, fill=acc!8, align=center}] \definecolor{acc}{HTML}{2348F2} \node[b] (core) at (0,3.1) {core}; \node[q] (sb1) at (0,1.85) {store x = 1}; \node[q] (sb2) at (0,1.25) {store f\/lag = 1}; \node[anchor=west] at (1.5,1.55) {store buf\/fer}; \node[b] (l1) at (0,-0.1) {L1 cache}; \draw[->, thick] (core.south) -- node[right=2pt] {\scriptsize stores enter} (sb1.north); \draw[->, thick] (sb2.south) -- node[right=2pt] {\scriptsize drain on ownership} (l1.north); % load path: bypasses on the left \draw[->, acc, thick] (core.west) to[out=200, in=160, looseness=1.3] node[left=2pt, font=\scriptsize, text=acc] {loads: buf\/fer f\/irst, then L1} (l1.west); \end{tikzpicture} $$ The store buffer is invisible to a single thread, which is why nothing in the single-core modules ever mentioned it. With two threads it is very visible: between retirement and drain, a store has happened for its own core and not happened for everyone else. A younger **load** can complete during that window, and the machine has then effectively reordered a load ahead of an older store to a different address. ## The litmus test Run the two-thread program from above on x86, both counters starting 0. ```asm [litmus.s] # thread 0 # thread 1 movl $1, x(%rip) movl $1, y(%rip) movl y(%rip), %eax movl x(%rip), %ebx ``` Each core's store parks in its own store buffer. Each core's load then goes to cache (the load is to a _different_ address, so store forwarding finds nothing to forward) and reads the other variable's old value: **0**. Both stores drain later, in coherence-respecting order, but after both loads have already completed. Result: `%eax = 0` **and** `%ebx = 0`, the outcome SC proved impossible. Real x86 hardware produces it readily; this Dekker-style litmus test is the standard demonstration that your machine is not sequentially consistent. $$ % caption: Both loads beat both drains. Each store waits in a private buf\/fer % caption: while its core's load reads the other location from cache: r1 = 0 and % caption: r2 = 0 together, an outcome no SC interleaving allows. \begin{tikzpicture}[font=\footnotesize,>=stealth, ev/.style={draw, minimum width=25mm, minimum height=6mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.5,1.5) {core 0}; \node[ev, fill=acc!8] (a1) at (1.0,1.5) {x = 1 to buf\/fer}; \node[ev, fill=acc!8] (a2) at (4.2,1.5) {load y: reads 0}; \node[ev, fill=black!6] (a3) at (7.4,1.5) {x drains}; \node[anchor=east] at (-0.5,0.3) {core 1}; \node[ev, fill=acc!25] (b1) at (1.0,0.3) {y = 1 to buf\/fer}; \node[ev, fill=acc!25] (b2) at (4.2,0.3) {load x: reads 0}; \node[ev, fill=black!6] (b3) at (7.4,0.3) {y drains}; \draw[->, black] (-0.4,-0.5) -- (9.1,-0.5) node[anchor=west] {time}; \end{tikzpicture} $$ ## x86-TSO in practice x86's actual contract is **total store order** (TSO), and it is precisely "SC plus a store buffer." Loads are not reordered with loads; stores are not reordered with stores; stores from all cores drain into a single total order everyone agrees on. The one relaxation is the one the buffer creates: a load may complete ahead of an **older store to a different address**. That single license is enough to break Dekker, and it is the _only_ surprise TSO permits — which makes x86 comparatively easy to reason about. ARM and POWER relax far more (loads pass loads, stores pass stores) and need this reasoning everywhere, not just around store-then-load patterns. The whole difference between memory models is which of the four program-order pairs — store-then-store, store-then-load, load-then-load, load-then-store — a later operation is allowed to overtake an earlier one to a _different_ address. Laid out as a table, x86-TSO is the model with exactly one relaxation, and the weaker architectures are the ones with more: | reordered pair | SC | x86-TSO | ARM / POWER | |:---|:---:|:---:|:---:| | store → later store | no | no | **yes** | | store → later load | no | **yes** | **yes** | | load → later load | no | no | **yes** | | load → later store | no | no | **yes** | On x86 you must reason about the one "yes" — a load slipping ahead of an older store — and that single case is what breaks Dekker; everywhere else program order is preserved for free. On ARM or POWER every cell is "yes," so a correct program must place a fence at _every_ ordering it depends on, which is why lock-free code written for x86 is notoriously wrong when ported to ARM without adding barriers the x86 never needed. The table is the checklist a systems programmer runs down before trusting any two-location handoff. When the reordering is intolerable, order is restored explicitly with a **fence**. `mfence` drains the store buffer: no later load executes until every earlier store is globally visible. ```asm [dekker_fixed.s] # thread 0 (thread 1 symmetric) movl $1, x(%rip) mfence # drain: x = 1 visible everywhere movl y(%rip), %eax # only now may the load run ``` With the fence on both sides, at least one thread's load runs after both stores are visible, and the both-zero outcome disappears. Fences cost tens of cycles (a full buffer drain), so the goal is to use as few as correctness requires, usually by hiding them inside a synchronization library rather than sprinkling them by hand. ## Atomic read-modify-write Ordering is half of synchronization; the other half is **atomicity**. Lesson 1's `shared += 1` compiles to load, add, store, and two cores can interleave the sequences so one increment vanishes. No amount of fencing fixes that; the fix is making the whole read-modify-write one indivisible bus-visible operation. x86 spells it with the **`lock` prefix**: `lock addq $1, (%rdi)` acquires the line in **M**, performs the add, and holds the line against all snoops until the store lands: one atomic unit, and a full fence besides. `xchg` (swap register with memory) carries an implicit `lock`. The most general primitive is **compare-and-swap**: ```asm [cas.s] # long cas(long *p, long expected, long desired) # returns the value actually found at *p movq %rsi, %rax # rax = expected lock cmpxchg %rdx, (%rdi) # if (*p == rax) *p = rdx; else rax = *p ret # atomically, either way ``` `cmpxchg` succeeds only if the location still holds what you expected, so it turns "read, think, write" into "read, think, write **if nothing changed**, else retry", the loop at the bottom of every lock-free structure. | primitive | operation | implicit `lock` | generality | |:---|:---|:---:|:---| | `lock add` | `*p += v` atomically | explicit prefix | fixed op | | `xchg` | swap register with `*p` | yes | test-and-set | | `cmpxchg` | `if (*p == exp) *p = new` | with `lock` prefix | universal RMW | For example, trace an atomic increment built from it. To add 1 to `*p` atomically: read `*p` into `old`; compute `new = old + 1`; then `cmpxchg(p, old, new)` — write `new` only if `*p` is still `old`. Run two cores racing on `*p = 5`: 1. Core A reads `old = 5`, computes `new = 6`. 2. Core B reads `old = 5`, computes `new = 6`, and its `cmpxchg` fires first: `*p` is still 5, so it succeeds and `*p` becomes 6. 3. Core A's `cmpxchg` now runs: it expects 5 but finds **6**, so it _fails_, returns the 6 it found, and A loops — reads `old = 6`, computes `new = 7`, and this time succeeds, `*p` becomes 7. Both increments land; the final value is 7, not the 6 that the lost-update race of lesson 1 produced. The compare is the guard: A's write is refused precisely because the value changed under it, and the retry re-reads the fresh value. This read-compute-`cmpxchg`-retry loop underlies the atomic increment, the lock-free stack push, and the lock acquire alike. ## Building a spinlock A spinlock is one word: 0 free, 1 held. Acquire = atomically set it to 1 and learn what it was; if it was already 1, someone else holds it, try again. ```asm [spin_tas.s] # void lock(long *l) : test-and-set acquire: movl $1, %eax xchg %eax, (%rdi) # atomic swap, implicit lock prefix testl %eax, %eax # what was there before? jnz acquire # 1 = held: spin ret release: movl $0, (%rdi) # plain store: TSO stores are ordered ret ``` This is correct but expensive. Every `xchg` is a `BusRdX`: each spinning core grabs the line in **M**, sees 1, and by grabbing it invalidated every other spinner, who each grab it back. $N$ waiting cores turn one held lock into a continuous storm of coherence traffic that slows everyone, including the core trying to _release_ the lock through the same contended bus. The fix is to spin **reading**. A read leaves the line in **S**, and every spinner can hit on its own shared copy forever, generating zero bus traffic, until the holder's release-store invalidates them all at once. Only then do the spinners attempt the expensive atomic. This is **test-and-test-and-set**: ```asm [spin_ttas.s] # void lock(long *l) : test-and-test-and-set acquire: cmpl $0, (%rdi) # spin on a READ: line stays in S, no bus jne acquire movl $1, %eax # looks free: now try to take it xchg %eax, (%rdi) # the one atomic, only when plausible testl %eax, %eax jnz acquire # lost the race: back to quiet spinning ret ``` $$ % caption: Why spin-on-read is kinder. Test-and-set spinners trade BusRdX storms % caption: that bounce the line among caches. Test-and-test-and-set spinners each % caption: hit their own Shared copy silently until the release invalidates them. \begin{tikzpicture}[font=\footnotesize,>=stealth, co/.style={draw, minimum width=17mm, minimum height=6.5mm, align=center}] \definecolor{acc}{HTML}{2348F2} % left: TAS storm \node at (1.35,2.35) {test-and-set}; \node[co] (t0) at (0,1.5) {spinner 0}; \node[co] (t1) at (2.7,1.5) {spinner 1}; \node[co, fill=acc!8] (lk) at (1.35,0) {lock line}; \draw[->, acc, thick] (t0.south) to[bend right=14] node[left=2pt] {\scriptsize BusRdX} (lk.north west); \draw[->, acc, thick] (t1.south) to[bend left=14] node[right=2pt] {\scriptsize BusRdX} (lk.north east); \node at (1.35,-0.85) {\scriptsize line bounces every attempt}; % right: TTAS quiet \node at (7.75,2.35) {test-and-test-and-set}; \node[co] (s0) at (6.4,1.5) {spinner 0}; \node[co] (s1) at (9.1,1.5) {spinner 1}; \node[co, fill=acc!8] (sc0) at (6.4,0) {copy in S}; \node[co, fill=acc!8] (sc1) at (9.1,0) {copy in S}; \draw[->, thick] (s0.south) -- node[left=2pt] {\scriptsize local hit} (sc0.north); \draw[->, thick] (s1.south) -- node[right=2pt] {\scriptsize local hit} (sc1.north); \node at (7.75,-0.85) {\scriptsize silent until release}; \end{tikzpicture} $$ The scale of the difference grows with the waiters. Under test-and-set, $N$ spinning cores each fire a `BusRdX` per attempt, and each `BusRdX` invalidates the other $N-1$ copies, so the lock line ricochets around the interconnect $O(N)$ times per unit of waiting — every one of those transactions competing on the same bus the lock _holder_ needs to release. Adding cores makes the critical section slower, the opposite of what more hardware should buy. Under test-and-test-and-set the $N$ waiters sit on **S** copies and generate _zero_ bus traffic while spinning; the only coherence event is the single release-store, which invalidates all $N$ copies at once, after which one waiter wins the atomic and the rest re-share. Bus cost per wait drops from $O(N)$ to $O(1)$ — the difference between a lock that scales to many cores and one that collapses under a dozen. Production spin loops add one more instruction: `pause`, dropped into the read loop's body. It is a hint, not a fence — it tells the core this is a spin-wait, so the core stops speculating dozens of iterations ahead (avoiding a costly pipeline flush when the lock word finally changes), draws less power, and, on an [SMT core](/computer-architecture/multithreading-and-multicore/hardware-multithreading), hands its issue slots to the sibling thread doing real work. A spinning hyperthread without `pause` can measurably slow the very sibling that is trying to release the lock it waits for. Release needs no atomic at all on x86: the lock word's new value 0 is a plain store, TSO orders it after every store the critical section made, and the protected data is therefore visible before the lock ever looks free. (Weaker architectures need a release fence here; the reasoning is the same, but the fence is explicit.) ## Progress guarantees, briefly Locks make waiting explicit: a thread that cannot get the lock does nothing useful, and if the holder is descheduled everyone spins on its behalf. Lock-free programming trades that for guarantees stated without locks at all. The guarantees form a strict hierarchy — wait-free implies lock-free implies obstruction-free: | guarantee | promise | who may starve | |:---|:---|:---| | obstruction-free | a thread running _alone_ finishes in finite steps | any, under contention | | lock-free | _some_ thread always finishes in finite steps | individual threads | | wait-free | _every_ thread finishes in _bounded_ steps | none | Each level costs more design effort than the last; `lock cmpxchg` retry loops give lock-freedom naturally, and wait-freedom usually costs enough that engineers stop at lock-free plus fairness in practice. The primitives, either way, are the ones this lesson built: ordered visibility from fences, indivisibility from locked read-modify-write. ## Models, litmus tests, and the language contract Everything in this lesson rests on a formal literature that turned "the machine reorders things" into precise, testable contracts. **Sequential consistency** is Leslie Lamport's (1979, _IEEE Trans. Computers_): a one-page definition that fixed what a correct multiprocessor _ought_ to do and became the yardstick every real, weaker model is measured against. **x86-TSO** is the model this lesson names, formalized by Sewell, Sarkar, Owens, and colleagues ("x86-TSO: A Rigorous and Usable Programmer's Model," 2010, _CACM_) after Intel's and AMD's own prose manuals proved ambiguous enough that experts disagreed about what the both-zero litmus test was allowed to do. Their store-buffer model is the one drawn above, and it is now the reference. The same group's tooling gave the field its shared vocabulary of **litmus tests** — small two- and four-instruction programs, each probing one reordering — and the herd/ litmus tools that run them against real silicon and against candidate models. The weaker end of the spectrum has its own canon. ARM and POWER are described by _relaxed_ or _weak_ memory models where, as the table showed, nearly every program-order pair can be reordered; Adve and Gharachorloo's survey (1996, _IEEE Computer_) remains the standard tour, and the reason "sprinkle a fence until it works" is dangerous advice. Finally, the contract moved up into the languages. The **C11 and C++11 memory model** (Batty et al., 2011, POPL) gave programmers `atomic` types with explicit `memory_order` annotations — `relaxed`, `acquire`, `release`, `seq_cst` — so that portable code states the ordering it needs and the compiler emits whatever fences the target requires: nothing on x86 where TSO already provides acquire/release, a `dmb` on ARM. The **Java memory model** (Manson, Pugh, and Adve, 2005, POPL) did the same for the JVM a few years earlier, after the original was found broken. This is where the fences of this lesson actually live in modern code: inside `std::atomic` and `java.util.concurrent`, chosen by the model, not typed by hand. > **Takeaway.** Consistency, not coherence, decides what multi-location > programs mean. SC is the intuitive contract; store buffers break it the > moment a load passes an older store, which x86-TSO legalizes as its one > relaxation, and the Dekker litmus test exhibits. Order is restored with > `mfence`, atomicity with `lock`-prefixed read-modify-writes (`xchg`, > `cmpxchg`). A spinlock built from them should spin on reads, not atomics — > the Shared state makes waiting free — and lock-free structures replace > waiting with `cmpxchg` retries whose guarantee is system-wide, not > per-thread, progress. The protocols, buffers, and fences of the last two lessons all live somewhere physical — on a die where distance is latency and the interconnect has a shape. The [final lesson](/computer-architecture/multithreading-and-multicore/multicore-organization) draws the floorplan.