3.1Problems with Shared Memory Behavior

Where this chapter goes

This chapter defines memory consistency models properly and then develops the most intuitive one — sequential consistency — all the way from Lamport’s definition (§3.4) and a reusable formalism (§3.5) to naive operational implementations (§3.6), a coherence-based implementation (§3.7), aggressively optimized ones (§3.8), atomic operations (§3.9), and a real machine, the MIPS R10000 (§3.10). But first it must convince you there is a problem at all. Throughout, “core” means software’s view of a core — a real core or a thread context of a multithreaded core — and all examples assume every variable starts at zero.

Example 1: the flag that lies

Core C1 writes some data, then sets a flag; core C2 spins until it sees the flag, then reads the data. Surely r2 must be NEW?

On some of today’s systems, r2 can be 0. Hardware can reorder C1’s stores S1 and S2: locally the reordering looks harmless — they access different addresses — but C2 can then observe flag = SET while data is still 0 (execution order S2, L1, L2, S1). Flip the Store→Store toggle above and watch the (SET, 0) outcome appear. Then try Load→Load instead: reordering C2’s loads produces the same disaster, and is even more plausible if the branch of the spin loop is elided.

One recorded execution of this kind (the book’s Table 3.2), with the coherence state of each block alongside:

Look at the state columns: the SWMR invariant swmr invariant Single-writer–multiple-reader: for any memory location at any moment, either one core may write (and read) it, or some number of cores may only read it. defined in Chapter 2 — open in glossary holds at every cycle. This execution satisfies coherence cache coherence Making caches functionally invisible by propagating one processor's writes to other processors' caches; a means of supporting a consistency model, not a correctness definition itself. defined in Chapter 1 — open in glossary perfectly. Incoherence is not the culprit — ordering is.

Example 2: Dekker’s disappointment

The core of Dekker’s mutual-exclusion algorithm: each thread announces itself with a store, then checks whether the other announced.

Intuition says three outcomes: (0, NEW), (NEW, 0), or (NEW, NEW). Surprisingly, most real hardware — including x86 systems from Intel and AMD — also allows (0, 0), because FIFO write buffers let each core’s load slip past its own buffered store. Enable Store→Load above to see it. And again: every one of these executions, including (0, 0), satisfies cache coherence.

Why we can’t just shrug this off

Two objections the book preempts:

• “This is non-deterministic and confusing.” All current multiprocessors are non-deterministic by default: every architecture permits multiple interleavings of concurrent threads. The illusion of determinism is created — sometimes — by software synchronization. A definition of shared memory behavior must embrace non-determinism.
• “Just define behavior for correct programs.” Memory behavior is usually defined for all executions of all programs — including incorrect ones and intentionally subtle ones (e.g., non-blocking synchronization algorithms). (Chapter 5’s high-level-language models will carve out a deliberate exception: executions with data races may get undefined behavior.)

Without a precise definition of what hardware may do, nobody can say which of these reorderings are bugs and which are features. That definition is the memory consistency model — next section.