Memory Consistency and Synchronization

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.

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.

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 $\neg (\text{r1}=0\wedge \text{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, 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.

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.

# 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.

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:

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.

# 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:

# 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.

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.

# 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:

# 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

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, 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:

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.

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 draws the floorplan.