Memory model

Rules specifying which shared-data observations and operation orders are allowed. Sequential consistency is the model used in the two diagrams. A language memory model can permit weaker ordering and impose additional conditions on conflicting accesses. Correct use of an indivisible flag must therefore be checked against that memory model, including happens-before relationships for the data guarded by the flag.

Execution behaves as if steps occurred in one total order preserving each participant's program order; reads observe the latest preceding writes in that order. This is the definition given in the 1979 paper How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, printed p. 690. It permits many thread interleavings, including the lost update under mutual exclusion; ordering individual accesses does not combine them into one atomic operation.

For the C++ case used here, conflicting accesses by different software threads, at least one non-atomic, with neither ordered before the other by happens-before. Such a data race has undefined behavior. A race condition is broader: the lost update with separate atomic reads and writes depends on their order while avoiding a data race.^[ref]

An ordering binary relation used by a memory model to constrain observation of shared data. For the mutex example, T1's write precedes its release, that release synchronizes with T2's successful acquisition, and that acquisition precedes T2's read. Together these steps order the write before the read. Wall-clock timing alone does not establish happens-before.^[ref]

A release on an atomic object can synchronize with an acquire that reads the released value, establishing happens-before for surrounding accesses. A test-and-set spinlock needs suitable acquisition and release semantics for its guarded data; relaxed flag operations alone do not supply that relationship. This is a separate question from the flag's indivisibility.^[ref]