The academic literature offers many alternative relaxed models and concepts; this section reviews a few for basic understanding. The book’s own advice applies here: users of SC for DRF — most programmers — don’t need to master this difficult material and may skim on a first pass.
5.5.1 Release consistency
In the same ISCA 1990 session where Adve and Hill proposed SC for DRF, Gharachorloo et al. proposed release consistency release consistency (rc) Relaxed model observing that an acquire needs only a succeeding fence and a release only a preceding one, replacing full FENCEs with one-direction ACQUIRE/RELEASE. defined in Chapter 5 — open in glossary (RC). Its key observation: surrounding every synchronization operation with FENCEs is overkill. A synchronization acquire needs only a succeeding FENCE; a release needs only a preceding one.
Concretely, in Table 5.4’s critical sections, FENCEs F11, F14, F21, and F24 may be omitted. Consider R11 (the release): F13 must stay — it orders the critical section’s loads and stores before the lock release — but F14 protects nothing: no harm if C1’s subsequent operations drift earlier than the release. RC goes further than XC could: those subsequent operations may move as early as the beginning of the critical section.
RC provides ACQUIRE and RELEASE acquire/release One-direction ordering operations: ACQUIRE orders itself before later loads/stores, RELEASE after earlier ones; ACQUIREs and RELEASEs stay SC-ordered among themselves. defined in Chapter 5 — open in glossary operations that order memory accesses in one direction only, unlike a FENCE’s two:
A FENCE orders both directions; RC’s ACQUIRE and RELEASE each order only one. Crossing in the ✓ direction is legal motion, ✗ is forbidden.
In full, RC requires only:
- ACQUIRE → Load, Store (but not Load, Store → ACQUIRE);
- Load, Store → RELEASE (but not RELEASE → Load, Store); and
- SC ordering of ACQUIREs and RELEASEs among themselves: ACQUIRE → ACQUIRE, ACQUIRE → RELEASE, RELEASE → ACQUIRE, and RELEASE → RELEASE.
5.5.2 Causality and write atomicity
Two subtle properties distinguish relaxed models from one another.
Causality — “if I see it and tell you about it, then you will see it too.” causality "If I see a store and tell you about it, you will see it too"; implied by write atomicity but not vice versa. defined in Chapter 5 — open in glossary In Table 5.9, C2 spins until it sees C1’s store S1, FENCEs, then stores data2; C3 spins until it sees that store, FENCEs, then loads data1. If r3 is guaranteed to be NEW, causality holds; r3 = 0 would violate it. XC — try it — keeps the guarantee:
Table 5.9: causality — must C3 see what C2 saw?
| Core C1 | Core C2 | Core C3 |
|---|---|---|
| S1: data1 = NEW; | L1: r1 = data1; | L2: r2 = data2; |
| F1: FENCE | F2: FENCE | |
| S2: data2 = NEW; | L3: r3 = data1; |
Initially data1 = 0, data2 = 0. Table 5.9 (causality): C2 sees S1 and tells C3 via S2 — must C3 then see S1 (r3 = NEW)?
Possible outcomes (r3) under XC (FENCEs only):
1 execution — show one
S1 → L1 → F1 → S2 → L2 → F2 → L3XC enumeration reorders each thread freely EXCEPT across a FENCE and for same-address Load→Load / Load→Store / Store→Store; (bypass) = the load read its own thread's program-order-earlier store even though that store enters memory order later (the extended value rule).
Only executions where C2's spin loop exited (r1 = NEW) are shown.
Only executions where C3's spin loop exited (r2 = NEW) are shown.
Write atomicity write atomicity A store becomes logically visible to all other cores at once (its own core may see it early); a.k.a. store atomicity or multi-copy atomicity. defined in Chapter 5 — open in glossary (also store atomicity or multi-copy atomicity) — a core’s store is logically seen by all other cores at once. XC is write atomic by definition: its total memory order <m gives every store one logical instant at which it takes effect — before it, no other core sees the new value; after it, every other core sees the new value (or a later store’s). Note the twist that makes some call the name poor: write atomicity allows the storing core to see its own value early — exactly XC’s bypassing.
A necessary — but not sufficient — condition for write atomicity is proper handling of Independent Read Independent Write ( IRIW iriw Independent-Read-Independent-Write litmus test: two writers and two readers observing the writes in opposite orders; proper handling is necessary but not sufficient for write atomicity. defined in Chapter 5 — open in glossary , Table 5.10): two writers, two readers, and the question of whether the readers can disagree about the order of the writes:
Table 5.10: IRIW — can C3 and C4 disagree on the store order?
| Core C1 | Core C2 | Core C3 | Core C4 |
|---|---|---|---|
| S1: data1 = NEW; | S2: data2 = NEW; | L1: r1 = data1; | L3: r3 = data2; |
| F1: FENCE | F2: FENCE | ||
| L2: r2 = data2; | L4: r4 = data1; |
Initially data1 = 0, data2 = 0. Table 5.10 (IRIW): C3 saw data1's store and C4 saw data2's store. Can they disagree on the order — (r2, r4) = (0, 0)?
Possible outcomes (r2, r4) under XC (FENCEs only):
68 executions — show one
S1 → S2 → L1 → F1 → L2 → L3 → F2 → L41 execution — show one
S1 → L1 → F1 → L2 → S2 → L3 → F2 → L41 execution — show one
S2 → L3 → F2 → L4 → S1 → L1 → F1 → L2XC enumeration reorders each thread freely EXCEPT across a FENCE and for same-address Load→Load / Load→Store / Store→Store; (bypass) = the load read its own thread's program-order-earlier store even though that store enters memory order later (the extended value rule).
Executions filtered to r1 = NEW (C3 observed S1) and r3 = NEW (C4 observed S2).
The forbidden outcome (r2, r4) = (0, 0) — C3 sees S1-then-S2 while C4 sees S2-then-S1 — never appears: with a total memory order, the stores aren’t just “unreordered,” some order of them must exist. If the outcome did occur, no store order would exist at all, and write atomicity would be violated. (Both widget models assume a total memory order, which is exactly why neither can produce it — Power, in §5.6, has no such order.)
Two more facts, “that can make your head hurt and long for SC, TSO, or SC for DRF”:
Bottom line for our example model: XC is store atomic, and therefore also maintains causality.
Check yourself
1.Release consistency's key observation about XC's FENCE-around-every-sync policy (Table 5.4) is that it's overkill. Which FENCEs can go?
2.Which orderings does release consistency actually require?
3.What is CAUSALITY, in the book's memory-model sense?
4.Why does the book call "write atomicity" a POOR NAME for the property it denotes?
5.In IRIW, C3 sees data1's store before data2's, while C4 sees data2's before data1's. What does this outcome imply, and what is its relationship to write atomicity?