3.9Atomic Operations with SC

Why atomics exist

Writing multithreaded code requires synchronizing threads, and synchronization often means performing pairs of operations atomically. That functionality comes from read-modify-write read-modify-write (rmw) An atomic instruction (e.g., test-and-set, fetch-and-increment, compare-and-swap) whose load and store appear consecutively in memory order. defined in Chapter 3 — open in glossary instructions — test-and-set, fetch-and-increment, compare-and-swap — the raw material of spin-locks and every other synchronization primitive. For a spin-lock, the programmer uses an RMW to atomically read whether the lock is free (say, 0) and write it taken (1).

Under SC, atomicity has a precise meaning inherited from §3.5: the RMW’s load and store must appear consecutively in the memory order memory order The total order (<m) on all cores' memory operations that an execution appears to perform. defined in Chapter 3 — open in glossary . Nothing — to the same address or any other — may interpose between the test and the set.

Three implementations, increasingly clever

Conceptually simple; naively slow. Step through the progression:

The key insight behind the fast versions: SC requires only the appearance of a total order. The standard implementation obtains the block in state M and then loads and stores entirely within the cache — no coherence messages, no bus locking — while briefly deferring any incoming coherence request for that block until after the store. The deferral cannot deadlock, because the store is guaranteed to complete.

The optimized version goes further: with the block merely in a read-only state, the load part performs speculatively right away while the cache controller issues the upgrade to read-write; the store part performs when M arrives. Atomicity survives as long as the block was not evicted between the two parts — verified with exactly the speculation support of §3.8 (track the block; squash and retry on eviction or invalidation).