Memory models — sequential consistency, TSO, relaxed: Visual walkthrough

This is the deep-dive companion to the parent topic. We build every idea from zero: no prior notion of "reordering", "buffer", or "fence" is assumed.

Step 1 — What is memory here, and what do "read" and "write" mean?

WHAT. Picture a shared whiteboard with two named cells on it: a cell labelled x and a cell labelled y. Both start holding the number 0. Two people (threads) can walk up to the board.

To write x = 1 means: erase what's in cell x and chalk a 1.
To read r1 = y means: copy whatever is currently in cell y into your own private notebook, on the line named r1.

WHY this picture. Everything mysterious that follows is only about the gap between "I decided to write" and "the mark actually appears on the shared board for others to see." If writing were instantaneous and visible to all, there would be no puzzle. So we must draw the board and the private notebooks as separate things.

PICTURE.

Figure — Memory models — sequential consistency, TSO, relaxed

Step 2 — The program we will trace (the SB litmus test)

WHAT. Two threads run these four lines. Shared start: $x = y = 0$ .

T1:  (a) x = 1;    (b) r1 = y;
T2:  (c) y = 1;    (d) r2 = x;

Read it as: "I raise my own flag, then I peek at yours." T1 raises x, peeks at y. T2 raises y, peeks at x.

WHY this exact program. It is the smallest program that can tell two memory models apart. Each thread does exactly one write then one read, and the write and read touch different cells — that "different cell" part is the whole game, because ordering rules only ever bite across different locations.

The question we obsess over for the rest of the page:

PICTURE.

Step 3 — The strong world (SC): line everyone up in one queue

WHAT. Suppose the world obeys Sequential Consistency: every operation from both threads is squeezed into one single line (a total order), and inside that line each thread's own two steps keep their written order (a before b, c before d).

WHY this model first. It is the intuition a beginner already has: "surely everything happens in some definite order, one thing after another." We test whether 0,0 can survive that assumption.

Let's exhaustively line them up. The only freedom is how we interleave {a,b} with {c,d} while keeping a<b and c<d. There are six such lines. Take one:

$a (x = 1) \to b (r 1 = y) \to c (y = 1) \to d (r 2 = x)$

At b, y is still 0, so $r 1 = 0$ . Fine so far.
But at d, x was already set to 1 back at a. So $r 2 = 1$ . Not both zero.

The key observation: for both reads to be 0, both reads (b and d) must come before both writes (a and c) in the single line. But a must come before b (T1's program order) — so a is before b is before... there is no way to push both writes after both reads without breaking somebody's own order.

WHY it's truly impossible. Whichever write lands first in the queue, the other thread's read comes later in the same queue and must therefore see that 1. So at least one register is 1.

PICTURE.

Step 4 — Enter the store buffer: writing is not instant

WHAT. Real hardware does not put your write straight on the shared board. Each core owns a private store buffer — think of it as a outbox tray on the core's desk. x = 1 first lands in the outbox. Only later does a courier carry it to the shared board (memory). Meanwhile the core, not wanting to wait for the courier, runs the next instruction immediately.

WHY hardware does this. Writing to the shared board is slow (it must travel through the cache-coherence machinery). Waiting for every write to land would stall the core. The outbox lets the core "fire and forget" and keep working. This is exactly the mechanism described in Store Buffers and Out-of-Order Execution.

The one subtle rule: a load that reads the same cell as something still in the outbox is allowed to peek into the outbox (called store forwarding) — so a thread always sees its own writes. But a load of a different cell just goes to the board and reads whatever is there.

PICTURE.

This single relaxation — a load may run before its own earlier store reaches the board — is the entire definition of store→load reordering, and it is what makes TSO weaker than SC.

Step 5 — The frame-by-frame trace that produces `0,0`

WHAT. Now replay the SB program under TSO and watch the outboxes.

T1 executes x = 1. → The 1 drops into T1's outbox. The board still shows x = 0.
T2 executes y = 1. → The 1 drops into T2's outbox. The board still shows y = 0.
T1 executes r1 = y. y is a different cell — nothing about y is in T1's outbox — so it reads the board: y = 0. Thus $r 1 = 0$ .
T2 executes r2 = x. Same story: x is not in T2's outbox, board still shows x = 0. Thus $r 2 = 0$ .
Later, both couriers deliver, and the board finally becomes x=1, y=1. Too late — the reads already happened.

WHY this is legal. Nobody broke any rule. Each thread saw its own program order. Each write did land eventually. The loads simply jumped ahead of the still-in-outbox stores. That is the permitted store→load reordering.

PICTURE.

Step 6 — The fix: `MFENCE` drains the outbox

WHAT. Put a fence between the store and the load in each thread:

T1:  x = 1;  MFENCE;  r1 = y;
T2:  y = 1;  MFENCE;  r2 = x;

The fence MFENCE means: "do not run any later instruction until my outbox is empty (drained to the board)."

WHY it works. Now step 3 cannot happen until T1's x=1 is on the board. Trace it: T1 drains → board shows x=1. T2 drains → board shows y=1. Whichever drains second, its following load sees the other's 1. So 0,0 is impossible again — we've bought back SC for this pattern.

WHAT IT COSTS. Draining is a global round-trip: the store must become visible everywhere before you proceed. That's why fences are expensive and why Dekker/Peterson locks need exactly one here.

PICTURE.

At the language level (see C++ Atomics and memory_order), you don't write MFENCE by hand: a seq_cst store/load, or the right happens-before annotation, tells the compiler to emit it for the target chip.

Step 7 — Degenerate & boundary cases (never leave a gap)

WHAT. We tie off every corner so no scenario surprises you.

Same cell instead of different cells. If both threads touched only x, single-location coherence would force an order and store-forwarding would apply — 0,0 couldn't arise. The puzzle needs two distinct cells.
One thread only. With a single thread, its own load reads its own outbox (forwarding), so it always sees its latest write. Reordering is invisible to the thread that did it — that's the whole illusion.
Empty outboxes at the read. If a courier happens to deliver before the load runs, that thread reads 1. 0,0 is possible, not guaranteed — it depends on courier timing. Any of the four outcomes may appear across runs.
Relaxed (ARM/POWER) hardware. There the outbox model is even looser (all four reorderings), so 0,0 is also allowed, and even the "publication" pattern (MP test) breaks — see the parent note. Everything on this page is the milder TSO case.

PICTURE.

The one-picture summary

Recall Feynman retelling — say it out loud

Two cells on a shared board, x and y, both 0. Two workers. Each worker raises their own flag, then glances at the other's flag. You'd swear at least one glance must catch a raised flag. And in a single-queue world (SC) — yes, it must: whoever raises first, the other's later glance sees it. But real desks have an outbox: when a worker "raises a flag," the mark only lands in their own tray, and a slow courier carries it to the board later. So each worker glances at the board while their own flag is still sitting in their tray — the board is still blank — and both write down 0. Nobody cheated: every worker kept their own order, every flag eventually got posted. The only cure is to shout "empty your tray before you glance!" — that's a fence (MFENCE), which forces your write onto the board first, and instantly the impossible 0,0 becomes impossible again. The price: you wait for the courier, a full round-trip.

Recall Self-test

Why is 0,0 impossible under SC? ::: In one single queue, whichever store is first, the other thread's later load is behind it in the same queue and must read the 1. What hardware feature makes 0,0 possible under TSO? ::: The per-core store buffer (outbox): a load of a different cell runs before the earlier store is drained to memory. Why does a thread still see its own writes? ::: Store forwarding — a same-cell load peeks into its own outbox. What does MFENCE do, physically? ::: Blocks later instructions until the store buffer is drained to global memory. Does the fix change performance? ::: Yes — draining forces a global round-trip, so the store becomes visible everywhere before proceeding.