Memory models — sequential consistency, TSO, relaxed: Question bank

Before we start, a quick vocabulary anchor so nothing below uses an undefined word:

Recall Vocabulary refresher (open if any term feels shaky)

Store ::: a write to memory (x = 1).
Load ::: a read from memory (r = x).
Store buffer ::: a small per-core queue where a store waits before it becomes visible to other cores — see Store Buffers and Out-of-Order Execution.
Globally visible ::: the moment every other core could read the new value, not just the writing core.
Reordering ::: two operations from one thread taking effect (as seen by other threads) in a different order than the program text.
SC / TSO / Relaxed ::: the three rungs of the ladder — strongest to weakest.
Fence / barrier ::: an instruction that forbids certain reorderings across it — see Memory Barriers and Fences.
Acquire / release ::: language-level annotations that create ordering — see C++ Atomics and memory_order.

The two canonical tests these traps orbit around

Almost every question below refers to one of two tiny programs. Read them once here so the acronyms SB and MP are never a mystery.

Definition SB — the Store Buffer test

Two threads, shared x = y = 0. Each thread stores to one variable, then loads the other:

Thread 1:  x = 1;   r1 = y;      // r1 is Thread 1's register
Thread 2:  y = 1;   r2 = x;      // r2 is Thread 2's register

The famous outcome we keep calling 0,0 means precisely: r1 == 0 in Thread 1 AND r2 == 0 in Thread 2 — both loads read the old zero. Look at the buffer sketch: each store parks in its core's store buffer while the load races ahead and reads stale memory.

Definition MP — the Message Passing test

One thread is a producer (writes data, then raises a flag), one is a consumer (waits for the flag, then reads data):

Producer:  data = 42;   flag = 1;
Consumer:  while (flag == 0) {}   r = data;   // r is the consumer's register

The trap outcome is: consumer sees flag == 1 but reads r == 0 (stale data). It happens when the two stores propagate to the other core in swapped order, or the two loads reorder. The timeline shows the flag arriving before the data.

Recall What is DMB? (the ARM barrier named below)

DMB = Data Memory Barrier — an ARM instruction that forbids memory reorderings across it (the common inner-shareable variant is DMB ISH). It is ARM's way of doing what MFENCE does on x86; see Memory Barriers and Fences.

True or false — justify

TSO is just "SC but a little slower".

False — TSO is weaker (permits more outcomes), not slower-SC. It allows the store→load reordering that SC forbids, so it can produce results SC never can (e.g. r1==0 and r2==0 together in the SB test).

Under SC every thread runs its instructions in program order.

True, but incomplete — SC also requires that all threads' operations fit into one single global total order. Per-thread program order alone (without the single interleaving) does not give you SC.

x86 is a sequentially consistent machine because it forbids most reorderings.

False — x86 is TSO. It forbids store→store, load→load, load→store but still allows store→load, which SC forbids. That one gap is exactly why Dekker/Peterson locks need a fence — see Peterson and Dekker Locks.

On a relaxed model, a single thread can observe its own operations out of order.

False — every model preserves the illusion of program order for the thread itself (via store forwarding and dependency tracking). Reordering is only ever visible to other threads.

A memory model constrains the ordering of two operations to the same address.

False — same-address ordering is guaranteed everywhere by cache coherence (Cache Coherence (MESI)). Memory models are about ordering across different addresses.

Adding a fence makes a program faster because the CPU stops guessing.

False — a fence costs time (it drains the store buffer and forces global round-trips). You add it for correctness, and you add the weakest one that suffices.

Under TSO, the Message Passing (MP) pattern needs no barrier.

True — TSO keeps store→store and load→load in order, so publishing data before flag and reading flag before data is automatic. This "free publication" is not portable to ARM/POWER.

memory_order_relaxed still guarantees the atomic write is not torn.

True — relaxed gives atomicity and per-location coherence; it only drops cross-location ordering. The value is never half-written; it just isn't ordered against other locations.

If code works on your x86 laptop, it will work on an ARM phone.

False — ARM is relaxed and permits reorderings x86 forbids. TSO-correct-by-accident code (missing barriers) can break on relaxed hardware. Reason at the language model, not the chip.

Two seq_cst operations and one relaxed operation all share a single global order.

False — only the seq_cst operations join the single total order. A relaxed op is not part of that order and can appear "out of place" relative to them.

Spot the error

"In the SB test the r1==0, r2==0 outcome means the hardware lost a write."

Wrong — no write is lost. Both x=1 and y=1 execute and eventually become visible; they were simply still sitting in store buffers when the two loads ran, so the loads legitimately read the old 0.

"MFENCE orders my store before some other core's load."

Wrong — a fence only orders operations within the thread that executes it. It drains this core's store buffer so this core's store becomes globally visible before this core's later load; it says nothing directly about another core's instruction stream.

"I'll use a volatile variable in C++ so my flag is safe across threads."

Wrong — volatile in C/C++ prevents compiler caching but provides no cross-thread ordering or atomicity guarantees. Use std::atomic with the right memory_order — see C++ Atomics and memory_order.

"On ARM, since data is written before flag in the source, the reader who sees flag==1 sees data==42."

Wrong — that is the classic MP trap. On relaxed hardware the two stores propagate independently; flag=1 can be seen first. You need a release store + acquire load (or a barrier) to tie them together via Happens-before and Synchronizes-with.

"A release store pushes all prior writes out to other cores immediately."

Wrong — a release does not force immediate propagation. It guarantees that if an acquire load reads that release, then everything before the release is visible to the acquirer. It is a conditional ordering, not an eager flush.

"Load→load reordering can't matter because both loads just read — reads don't change anything."

Wrong — reading stale values changes program logic. In the MP test, if the consumer's load of data slips ahead of its load of flag, it reads data before publication and observes 0.

"Peterson's lock is correct on any CPU because the algorithm is proven correct."

Wrong — the proof assumes SC. On TSO/relaxed the store→load reordering of the "set my flag, then read yours" step breaks mutual exclusion until you add a fence — see Peterson and Dekker Locks.

Why questions

Why does store→load reordering exist even on strong x86?

Because the store parks in the store buffer to hide memory-write latency, and there is no reason to stall the pipeline on a later, independent load while it drains. Letting the load proceed is a big, cheap performance win — see Store Buffers and Out-of-Order Execution.

Why does a single-threaded program never expose any of these reorderings?

Because the hardware tracks dependencies and forwards the core's own buffered stores to its own later loads, so the one thread always sees its writes. Reordering is only observable when a second thread peeks at the same memory.

Why do languages define their own memory model instead of just using the CPU's?

For portability. The same source must compile to correct code on TSO x86 and relaxed ARM, so the language exposes an abstract model (relaxed/acquire-release/seq_cst) and the compiler emits the minimum fences each target needs.

Why is acquire/release usually preferred over seq_cst?

Because seq_cst forces participation in one global total order, which on ARM/POWER means heavier barriers. Acquire/release gives just the producer→consumer ordering the MP test needs, at lower cost — the pattern behind most Lock-free Programming.

Why can't cache coherence alone give you sequential consistency?

Coherence only orders operations to a single location (all cores agree on the history of one variable). SC additionally requires a consistent global order across different locations, which store buffers and reordering can violate.

Why does inserting MFENCE between the store and load fix the SB test?

The fence drains the store buffer, forcing this core's store to become globally visible before its load executes. Now the load can no longer "jump ahead" of the store, so at least one thread sees the other's 1 — restoring the SC outcome set.

Edge cases

If both threads in the SB test wrote to the same variable instead of two different ones, could you still get the reordering surprise?

No — single-location ordering is enforced by coherence, so the two threads would agree on one history of that variable; the SB paradox specifically needs two distinct addresses.

What happens in the MP test if data and flag are the same variable?

The pattern collapses — you can't separately publish and signal with one location. The whole point of MP is one variable carrying the data and another (flag) acting as the signal whose ordering must be tied to the data.

Is the r1==0, r2==0 outcome in the SB test guaranteed to appear on x86, or merely allowed?

Merely allowed — the model permits it, so it appears sometimes (depending on timing/buffer state). A memory model states what is possible, never what is forced; correctness reasoning must assume every allowed outcome can occur.

On a relaxed model, are two stores to different addresses ever kept in order without a barrier?

Only if there is a genuine dependency (e.g. the second store's address or value is computed from the first). Pure independent stores can be reordered; dependencies are the one implicit ordering relaxed hardware respects.

What is the weakest thing you can add to fix the MP test on ARM?

A release store on flag paired with an acquire load on flag (equivalently a DMB-style barrier between each thread's two operations). This creates a synchronizes-with edge and thus a happens-before chain — see Happens-before and Synchronizes-with.

If a program uses only memory_order_relaxed atomics, can it still deadlock or livelock?

Yes — relaxed gives atomicity but no ordering, so hand-rolled synchronization built on it can spin forever observing stale values. Relaxed atomics prevent torn reads, not logical progress bugs.

Does making every atomic seq_cst guarantee your concurrent algorithm is correct?

No — seq_cst removes reordering surprises but does not fix logic errors (missing checks, lost wakeups, ABA problems). It buys you SC reasoning; the algorithm still has to be correct under SC.

Recall One-line summary to carry away

The trap is always the same shape ::: "program text order across threads" is not "global visibility order" unless SC or an explicit fence/acquire-release makes it so.