Three constraints out of four
SC requires each core to preserve program order for all four combinations: Load→Load, Load→Store, Store→Store, and Store→Load. TSO keeps the first three and drops the fourth. That’s the entire change — and for most programs it doesn’t matter at all.
For the flag/data program (Table 4.2 = Table 3.1), TSO allows exactly the same executions as SC, because it preserves C1’s store→store order and C2’s load→load order:
Figure 4.1 (recreated): a TSO execution of Table 4.2’s program — indistinguishable from the SC execution of Figure 3.2.
More generally, TSO matches SC for the workhorse idiom of parallel software: C1 stores data D1…Dn, then stores a flag F; C2 loads F (spinning, often with an RMW), then loads and stores the data. Nothing in that pattern needs Store→Load ordering.
Where TSO differs: the fourth outcome
For the Dekker program, TSO allows all four outcomes — switch between the SC and TSO models below and watch (0, 0) appear, now produced by the real operational mechanism (stores entering and draining a FIFO write buffer) rather than an abstract reordering:
Table 4.1: the Dekker core under SC vs TSO
| Core C1 | Core C2 |
|---|---|
| S1: x = NEW; | S2: y = NEW; |
| L1: r1 = y; | L2: r2 = x; |
Initially x = 0, y = 0. Table 3.3 (Dekker-inspired): can both r1 and r2 be set to 0?
Possible outcomes (r1, r2) under TSO (write buffers):
22 executions — show one
S1▸buf → L1 → S1▸mem → S2▸buf → L2 → S2▸mem18 executions — show one
S1▸buf → L1 → S2▸buf → L2 → S1▸mem → S2▸mem18 executions — show one
S1▸buf → S1▸mem → S2▸buf → L2 → S2▸mem → L122 executions — show one
S1▸buf → S2▸buf → L2 → S1▸mem → S2▸mem → L1TSO enumeration is operational: ▸buf = store enters the FIFO write buffer, ▸mem = it drains to memory, (bypass) = a load read its own core's buffered store.
The non-SC execution looks like this — note the program-order arrows pointing upward: each load entered memory order before its own thread’s earlier store, which is exactly the Store→Load violation:
Figure 4.2d (recreated): the loads precede the stores in memory order while following them in program order.
Two design notes fall out immediately. First, keeping Store→Store order means the write buffer must be FIFO — not, for example, coalescing. Second, programmers who need the forbidden ordering can have it: a FENCE fence Instruction forcing all program-order-earlier memory operations into memory order before all later ones (a.k.a. memory barrier). defined in Chapter 4 — open in glossary between S1 and L1 (and between S2 and L2) ensures all of a core’s pre-FENCE operations enter memory order before its post-FENCE operations. FENCEs are rarely needed under TSO — it “does the right thing” for most programs — but they become the main event in chapter 5.
The bypassing corner case
Now the non-intuitive part. Modify Dekker so each core makes a local copy of its own variable before reading the other’s (Table 4.3). If r2 and r4 both read 0 — the stores still buffered — must r1 and r3 also read 0?
Table 4.3: can r1 or r3 be set to 0?
| Core C1 | Core C2 |
|---|---|
| S1: x = NEW; | S2: y = NEW; |
| L1: r1 = x; | L3: r3 = y; |
| L2: r2 = y; | L4: r4 = x; |
Initially x = 0, y = 0. Table 4.3: can r1 or r3 be set to 0? (Each core copies its own variable first.)
Possible outcomes (r1, r2, r3, r4) under TSO (write buffers):
149 executions — show one
S1▸buf → L1(bypass) → L2 → S1▸mem → S2▸buf → L3(bypass) → L4 → S2▸mem68 executions — show one
S1▸buf → L1(bypass) → L2 → S2▸buf → L3(bypass) → L4 → S1▸mem → S2▸mem264 executions — show one
S1▸buf → L1(bypass) → S1▸mem → S2▸buf → L3(bypass) → L4 → S2▸mem → L2149 executions — show one
S1▸buf → L1(bypass) → S2▸buf → L3(bypass) → L4 → S1▸mem → S2▸mem → L2TSO enumeration is operational: ▸buf = store enters the FIFO write buffer, ▸mem = it drains to memory, (bypass) = a load read its own core's buffered store.
No: r1 and r3 always read NEW. To preserve single-thread sequential semantics, each core must see its own stores in program order, even before other cores can — bypassing bypassing A load returning the value of its own core's latest program-order-earlier buffered store, overriding memory order. defined in Chapter 4 — open in glossary from the write buffer overrides the rest of the memory system:
Figure 4.3 (recreated): r1 and r3 receive NEW by bypassing from the per-core write buffers, even though both stores follow all four loads in memory order.
Check yourself
1.Which single program-order constraint does TSO drop relative to SC?
2.Why does TSO behave exactly like SC for the flag/data producer-consumer idiom (Table 4.2)?
3.In Table 4.3, cores copy their own variables first (r1 = x after storing x). Given r2 = r4 = 0, what are r1 and r3 — and why?
4.How does a programmer forbid the (0, 0) outcome of the Dekker program under TSO?