Two threads run concurrently on shared variables x and y, both initially 0. Thread 1 does: store x=1, then load y into r1. Thread 2 does: store y=1, then load x into r2. On typical hardware, can the program end with r1=0 and r2=0, and why?
answer
- store buffering / SB litmus test
- store retired to private buffer, load bypasses it
- no SC interleaving gives 0,0
- x86 TSO allows store→load only
- needs full fence; Dekker/Peterson depend on it
basics
~20 sYes. Each core buffers its store and lets the later load execute before that store is visible to the other core. No interleaving of the source order explains r1=r2=0, so it proves the machine is not sequentially consistent. Only a full fence between store and load forbids it.
solid answer
~50 sYes — this is the *store buffering* litmus test, and both readings can be 0 on essentially every mainstream CPU including x86. Each core retires its store into a private store buffer and continues; the subsequent load of the *other* variable is satisfied from cache before the buffered store has been made globally visible. Effectively the store is delayed past the load — store→load reordering. Enumerate the four sequentially consistent interleavings and none of them yields r1=0 and r2=0, which is exactly why this outcome is the standard proof that real hardware is not sequentially consistent. Even x86's relatively strong TSO model permits it; TSO forbids store→store, load→load and load→store reordering but explicitly allows store→load. The fix is a full barrier (a StoreLoad fence, or a sequentially consistent atomic operation) between each store and the following load, which forces the store buffer to drain first.
code
text · 6 linescore1: x=1 -> store buffer (not yet visible)
core2: y=1 -> store buffer (not yet visible)
core1: load y from cache -> 0 (r1 = 0)
core2: load x from cache -> 0 (r2 = 0)
core1: store buffer drains -> x = 1 globally
core2: store buffer drains -> y = 1 globallygo deeper
Know that the answer is 'yes, both can be 0' and that the reason is writes being buffered before other cores can see them.
Explain the store buffer, show that no sequentially consistent interleaving yields 0/0, and note that this is store→load reordering.
Add the architecture map (x86 TSO permits exactly this; weak architectures permit more), that acquire/release does not fix it, and that the repair is a full StoreLoad fence with a real cycle cost.
Connect it to design: any hand-rolled mutual exclusion or cross-signal has this shape, full fences are the expensive ones, and this is a reason to prefer library-provided synchronization over bespoke flag protocols.
## The scenario ``` initially x = 0, y = 0 Thread 1 Thread 2 x = 1 y = 1 r1 = y r2 = x question: can r1 == 0 and r2 == 0 ? ``` This is called the *store buffering* (SB) litmus test, and it is the compact way interviewers probe whether you actually understand memory ordering rather than reciting slogans. ## Why sequential consistency says no Sequential consistency (SC) means the execution is equivalent to *some* interleaving of the threads' instructions, with each thread's instructions in program order. Enumerate them: whichever of the two stores goes first, the load that comes after it in the interleaving must see it. Every SC interleaving produces at least one 1. So r1=r2=0 is impossible under SC — which makes observing it a direct proof that the machine is not SC. ## Why real hardware says yes A core does not push a store into the coherent cache immediately. It retires the store into a private FIFO *store buffer* and moves on, because waiting for cache-line ownership would stall the pipeline for tens or hundreds of cycles. Meanwhile the following load of a *different* address is served from cache right away. So on Thread 1, `x = 1` sits in the buffer while `r1 = y` reads the old y. Symmetrically on Thread 2. Both loads see 0. From outside, each core's store appears to have moved *after* its load: **store→load reordering**. A core does forward its *own* buffered stores to its *own* loads of the same address (store forwarding), which preserves the as-if-serial illusion for a single thread. That is precisely why the hazard is invisible until a second thread exists. ## The architecture landscape - **x86/x86-64 (TSO, total store order):** forbids store→store, load→load and load→store reordering, but *allows* store→load. So SB is observable on the strongest mainstream commodity architecture. This is important: candidates who believe 'x86 doesn't reorder' get this question wrong. - **ARM, POWER, RISC-V (weakly ordered):** allow much more, including load→load and store→store reordering, so SB is observable and other litmus tests (message passing, independent reads of independent writes) fail too. - **Compilers:** independently of hardware, an optimizer may swap the store and the load since they touch different locations — so this outcome is reachable even on a hypothetically SC machine if the code is unsynchronized. ## The fix and its price The only repair is a **StoreLoad barrier** between the store and the load in each thread — a full fence, or equivalently making the store a sequentially consistent atomic write (compilers implement that on x86 as a locked instruction or explicit fence). It forces the store buffer to drain before the load may be satisfied, costing tens of cycles. Notably, acquire/release ordering is *not* enough here: a release store followed by an acquire load still permits SB, because acquire/release are one-way and never order a store before a later load. This is the standard demonstration that acquire/release is strictly weaker than sequential consistency. ## Where it shows up in real code SB is the shape of **Dekker's** and **Peterson's** mutual exclusion algorithms: each thread announces its intent by writing its own flag, then reads the other's. If both writes are delayed past both reads, both threads conclude the other is not interested and both enter the critical section. Any hand-rolled lock, hand-rolled 'seen it first' flag, or double-checked cross-signal has this shape. It is also the reason such algorithms need a full fence, not a cheap one. ## Interview delivery Answer 'yes', name store buffering as the mechanism, state that no SC interleaving produces it (so it disproves SC), note it happens even on x86 because TSO permits store→load, and finish with 'the fix is a full StoreLoad fence — acquire/release will not do it'. That sequence is a complete senior answer.
- Would making both stores and loads release/acquire operations forbid the r1=r2=0 outcome?No. Release and acquire are one-way fences: a release store keeps earlier operations from sinking below it, and an acquire load keeps later operations from rising above it. Neither prevents a store from being delayed past a subsequent load in the same thread. Forbidding store buffering requires a full StoreLoad barrier, which is what a sequentially consistent operation emits.
- Why does the litmus outcome not violate as-if-serial semantics for either thread?Because each thread in isolation still behaves correctly: it sees its own store to x when it reads x, thanks to store forwarding from the buffer. The reordering is only observable to a second thread reading the other variable, and single-thread dependency analysis has no way to detect that observer.
Two people each drop a note in their own outbox and then walk to the other's inbox. Neither outbox has been delivered yet, so each finds an empty inbox and concludes the other said nothing.
saying these in an interview costs you the question
- Answering 'no, that outcome is impossible' by enumerating interleavings and forgetting the machine isn't sequentially consistent
- Claiming x86 forbids all reordering
- Saying acquire/release ordering is enough to prevent it
- Blaming stale caches — cache coherence still holds; the delay is in the store buffer before coherence sees the write
- Proposing a volatile-style 'always read from memory' fix without a barrier between the store and the load