Data Races, Memory Models, and Where Parallel Algorithms Lose Determinism

The work-span model assumes each node reads a definite value. On a single processor that is true. On a multiprocessor with caches, stores become visible to other processors in an order that need not match program order, and the value a node reads can depend on timing. Two distinct failures follow: a data race, where the program has no defined meaning at all, and a race-free computation whose result nevertheless varies with the schedule. Separating them matters because the first is a correctness bug and the second is often an accepted design choice.

The intuition that hardware does not honour

Sequential consistency, as Lamport defined it, requires that the result of any execution be the same as if the operations of all processors were executed in some sequential order, and that the operations of each processor appear in program order within that sequence. It is the model most programmers carry implicitly: threads interleave at statement boundaries, each statement is atomic, and every thread sees every write immediately.

No mainstream multiprocessor implements it, because doing so would forbid store buffers and out-of-order execution. The store buffer alone is enough to break it: a processor writes a value, the write sits in a private buffer, and another processor reads the old value from its own cache. On x86 the result is TSO, total store order, in which a processor’s own stores are seen by itself in order but may be delayed for others; loads may be reordered with respect to earlier stores to different addresses. On ARM and POWER the model is weaker still: loads and stores to different addresses may be reordered freely, and a value written by one processor may be observed in different orders by two others, unless a barrier forbids it.

The canonical demonstration is Dekker’s and Peterson’s algorithms for mutual exclusion. Both are correct under sequential consistency and both fail on hardware that permits a load to be reordered before a store. The failure is not a compiler bug and not a hardware defect; it is the model being different from the one the proof assumed. The repair is a fence or an atomic operation with the right ordering, which costs a pipeline flush or a cache-line transfer.

What counts as a data race

The C11 and C++11 memory model defines a data race precisely: two accesses to the same memory location, at least one of them a write, that are not ordered by happens-before. The consequence is severe — a program with a data race has undefined behaviour, not merely an unpredictable value. The compiler is licensed to assume no race exists, which means it may hoist a load out of a loop, duplicate it, or delete it entirely.

Happens-before is built from three ingredients: sequenced-before within a thread, synchronises-with between threads, and transitivity. A synchronises-with edge is created by a release operation on one thread matching an acquire operation on another that reads the released value — a mutex unlock followed by a lock, a store with release semantics followed by a load with acquire semantics, or the creation of a thread, which synchronises with the start of the thread function.

#include <stdatomic.h>
#include <threads.h>

static int payload;                 /* plain int, protected by the flag */
static atomic_int ready;

int producer(void *arg)
{
    payload = 42;                                  /* plain store */
    atomic_store_explicit(&ready, 1, memory_order_release);
    return 0;                                      /* release publishes payload */
}

int consumer(void *arg)
{
    while (atomic_load_explicit(&ready, memory_order_acquire) == 0)
        ;                                          /* spin until published */
    return payload;                                /* guaranteed to be 42 */
}

The release store orders the preceding plain write before it, and the acquire load orders the following plain read after it, so the two accesses to payload are ordered by happens-before and there is no race. Removing either annotation makes the program racy: with relaxed ordering on both sides, the consumer may read payload before the store to it becomes visible, and with a plain int flag the compiler may cache the flag in a register and never exit the loop.

The crucial point is that the annotations are needed even though the hardware might happen to preserve the order. TSO does preserve store-store order, so this particular program might work on x86 without the annotations; ARM does not, and a compiler may reorder regardless of the target. Reasoning from one machine’s behaviour to another’s is the standard source of latent portability bugs.

Race-free but not deterministic

A program can be entirely free of data races and still produce different results on different runs. That is a property of the algorithm, not of the memory model, and it is often unavoidable.

Nondeterministic selection. A work-stealing scheduler assigns tasks to workers in an order that depends on timing. If tasks write to a shared accumulator, the order of additions varies and, for floating point, so does the sum. The program is race-free because the accumulator is a mutex-protected or atomic object; the result is still schedule-dependent.

Nondeterministic traversal. Graph algorithms that expand a frontier in parallel and mark visited nodes with an atomic test-and-set visit nodes in an order determined by which thread wins each race. The output set is the same; the traversal order, and hence the work done, is not. Breadth-first search with this pattern explores the same levels but may duplicate work when two threads expand the same node concurrently.

Reduction order. Covered in detail in the reduction article: a tree whose shape depends on the number of workers produces different rounding for different P. Fixing the tree shape, not adding synchronisation, is what makes the result reproducible.

The distinction matters for debugging. A race-free non-deterministic program can be tested with a schedule randomiser and its result compared against a tolerance or a canonical form. A racy program cannot be tested that way, because a run that produces the right answer proves nothing and a run that produces a wrong one may be impossible to reproduce. The classification determines the tool.

False sharing and the cost of coherence

Coherence operates on cache lines, not variables. Two threads writing different variables that share a 64-byte line cause the line to ping-pong between cores: each write invalidates the other core’s copy, and the next write must fetch it back. The program is race-free and correct, and it can be an order of magnitude slower than the same program with the variables separated.

The pattern appears in per-thread counters in an array, per-thread statistics in a struct, and work-stealing deques allocated adjacent to each other. The fix is alignment and padding: place each hot per-thread variable on its own line, either by aligning the containing object to 64 bytes and padding to that size, or by using a padded wrapper type. The cost is memory, which is the trade: a 64-byte pad per counter is nothing for a few dozen counters and significant for a million.

The diagnostic is a coherence-miss counter, and the signature is a program whose scaling curve flattens while its instruction count per element stays constant. That is the one overhead in the scaling discussion that looks like a serial fraction and is actually a cache-line conflict.

Ordering choices and their prices

The memory model offers a menu, and each entry has a cost on at least one architecture:

• Sequentially consistent atomics. The default in C and C++ for atomic operations without an explicit order. On x86 a store becomes a locked instruction or a fence, flushing the store buffer; on ARM it is a barrier instruction. Correct and expensive.
• Acquire and release. Enough for the publication pattern above and for most lock implementations. On x86, release stores are plain stores and acquire loads are plain loads, so the pair costs nothing beyond preventing compiler reordering; on ARM they are dedicated instructions.
• Relaxed. Atomicity without ordering. Correct for counters and flags whose value is read on its own, and wrong for anything used to publish other data. Cheap everywhere.
• Fences. Explicit barriers for the cases where the pairing is not a single load-store pair, such as a store followed later by a relaxed store that must be ordered.

The rule that ties these together is that a synchronises-with edge must exist for each pair of threads that share data. A relaxed atomic protects only the location it is applied to: it makes that one access indivisible, and it establishes no ordering for any other location. If a thread writes a data structure with plain stores and then publishes a pointer with a relaxed atomic store, a reader that loads the pointer with a relaxed load has no guarantee of seeing the stores to the structure, so those plain accesses still race. Making the pointer release/acquire is what orders the whole group. Atomics prevent torn values and lost updates; they do not, by themselves, create the edges that make surrounding plain accesses defined.

This is also why the work-stealing deque needs more than atomic indices. The owner’s plain array write must be ordered before the publication of the index, or a thief can read a slot that has been claimed but not yet filled. That single edge — a release operation publishing the bottom index after the element write — is what makes the deque correct, and it is the kind of requirement that is invisible in a sequentially consistent mental model.

Verifying the absence of races

Static analysis and dynamic race detectors both exist, and both have the same limitation: they find races that occur on the observed schedule, and a race that requires a rare interleaving is likely to be missed. Dynamic detectors such as happens-before trackers or lockset analysers instrument every access and are correct for the executions they see, at a slowdown of an order of magnitude or more and with memory overhead proportional to the access history.

The stronger approach is to design the algorithm so that shared mutable state is confined to well-defined synchronisation points: a parallel phase writes only its own partition, then a barrier or a reduction combines the partitions, then the next phase begins. That structure makes the happens-before graph explicit in the code and reduces the number of places where a subtle ordering error can hide. Fork-join runtimes enforce it by construction, since tasks that do not share a parent’s state cannot communicate except through explicit synchronisation.

The residual risk is in the runtime and in library code, where the ordering annotations are hand-written and hard to test. That is where the formal memory models earn their keep: a proof that the algorithm’s synchronisation establishes the needed edges is a proof about every execution, not about the ones a test happened to produce.