Data Race

concurrency

Definition

Data Race

A data race occurs when two or more threads concurrently access the same memory location, at least one access is a write, and no synchronisation mechanism orders the accesses.

Formally, for threads $T_1,T_2$ and a shared variable $x$, there is a data race iff

$$\begin{array}{rl}& \text{access}(T_1,x)\wedge \text{access}(T_2,x)\wedge \\ & \\ & (\text{write}(T_1,x)\vee \text{write}(T_2,x))\wedge \\ & \neg \text{ordered}(T_1,T_2;x),\\ & \end{array}$$

where $\text{ordered}(T_1,T_2;x)$ means the two accesses are separated by a synchronisation edge (happens-before).

Relation to Race Condition

A data race is a condition on access patterns; a race condition is a condition on outcomes.

Data race $⟹$ race condition

A data race implies that the program’s observable behaviour depends on the interleaving of unsynchronised accesses, hence the outcome is nondeterministic — a race condition. The converse does not hold: a race condition can occur even with atomic variables if the logical ordering of updates is uncontrolled.

Race condition without data race

Two threads atomically increment a shared counter. No data race (the increment is atomic), but the final value depends on which thread executes first: the outcome is a race condition. The access pattern is safe; the program logic is not.

Hardware-Level Data Race

Instruction-level interleaving

Even a single high-level statement like *lockvar = 1 decomposes into multiple instructions (load, compare, store). If two threads execute these instruction sequences concurrently without atomicity, their individual instructions can interleave at the microarchitectural level, producing a data race on the lock variable itself.

This is why a lock variable implemented with ordinary loads and stores fails under preemptive multithreading: the read of *lockvar and the subsequent write are not indivisible.

Non-Atomic Access

Non-atomic word write

Assume a 16-bit word is written by copying two 8-bit halves separately. Let $S=0$ and thread $T_1$ write $S:=-1$ (two’s complement: 1111 1111 1111 1111).

$T_2$ reads $S$ between the two half-writes:

$$S=(\underset{\text{first half}}{\underbrace{\text{1111 1111}}}\underset{\text{second half}}{\underbrace{\text{0000 0000}}}{)}_2=-256\text{or}-128$$

$T_2$ should only ever observe $0$ or $-1$. The intermediate value is a data race artefact: the write was not atomic, so a concurrent read saw a torn state.