advanced23 min studyLesson 151 in Engineering

Data races: draw the ordering argument

Build a happens-before graph for shared data and distinguish language-level undefined behavior from an ordinary timing-dependent result.

On this page

What you’ll understand

  • Identify conflicting accesses and missing happens-before edges.
  • Explain why elapsed time and volatile do not establish C++ thread synchronization.
  • Prove a one-shot publication pattern under explicit ownership assumptions.

Imagine a model-serving process building a configuration on one thread while workers wait for a ready flag. A test that always prints the expected configuration does not prove the publication safe. The question is which language rules order the producer's writes before the consumers' reads. This lesson uses the C++ abstract machine, ordinary threads, and a one-shot immutable payload. Other languages have different race semantics, so carry over the graph-building method rather than assuming their consequences are identical.

Shared access needs an actual relation

Label each relevant evaluation: writing the payload, publishing readiness, observing readiness, and reading the payload. Within one thread, the specified sequencing supplies edges. Between threads, a suitable synchronization operation supplies an edge only when its requirements are satisfied. Combine those edges transitively to establish happens-before. The graph describes an ordering guarantee, not timestamps collected from the operating system. A sleep, an observed scheduling order, or two log lines appearing in a convenient sequence does not substitute for synchronization.

In the C++ model, conflicting accesses include a write against another read or write of the same memory location; lifetime changes can conflict too. Potentially concurrent conflicting actions create a data race when at least one is non-atomic and neither happens before the other, subject to the standard's special signal-handler rules. A data race yields undefined behavior. Therefore, do not teach an unsynchronized ordinary increment as merely a counter that sometimes loses one update: the language gives no such bounded-result contract.

W≺sbS,S≺swL,L≺sbR⟹W≺hbRW \prec_{\rm sb} S,\quad S \prec_{\rm sw} L,\quad L \prec_{\rm sb} R\quad\Longrightarrow\quad W \prec_{\rm hb} R
For a one-shot publication, W writes payload, S release-stores readiness, L acquire-loads the value written by S, and R reads payload. sb is sequenced-before, sw synchronizes-with, and hb happens-before. These are dimensionless event relations, not measured times.↔ Scroll wide equations horizontally.

Publication includes a lifetime promise

A producer can initialize an ordinary payload and then perform a release store of true to an atomic ready flag. A worker repeatedly acquire-loads the flag and reads the payload only after observing that publication. Assuming the flag starts false and is not reused, that observation connects the producer's initialization to the read. The payload need not become atomic just because multiple workers read it. It must remain alive and unmodified for the entire period in which those readers may access it.

Reusing the flag changes the problem. A later generation of configuration can overwrite the same payload while a reader still uses the earlier generation, even if every flag access is atomic. Publication alone does not provide exclusion, ownership transfer, or reclamation. Pick an explicit protocol such as locking the full access, publishing independently owned immutable snapshots, or waiting for all prior readers. In C++, volatile supports particular observable-access requirements; it is not the mechanism that makes an ordinary payload safe between threads.

safeRead⁡(R)⇒(W≺hbR) ∧ alive⁡(R) ∧ noConflictingOverwrite⁡(R)\operatorname{safeRead}(R) \Rightarrow \bigl(W \prec_{\rm hb} R\bigr)\ \land\ \operatorname{alive}(R)\ \land\ \operatorname{noConflictingOverwrite}(R)
This is a checklist for the immutable-publication example, not a complete theorem for arbitrary C++ programs. The predicates concern an event R and its payload lifetime; no physical units or probabilities are implied.↔ Scroll wide equations horizontally.

Review the invariant, then inspect execution

Write an ownership table before changing a memory order: which thread creates, publishes, reads, mutates, and destroys each object? Mark the synchronization object next to every cross-thread handoff. An atomic counter of completed requests may be safely updated with relaxed read-modify-write operations if its value is only a statistic, yet the same counter cannot automatically serve as a publication barrier for request outputs. Whether a value is correct depends on what the program subsequently infers from it.

The network lab shows an actual data dependency in a small computation: a sigmoid reads the weighted input minus one half. Set weight to zero and predict whether changing the input can affect the output; restore weight one and compare. A computation's dependence on a value does not itself establish cross-thread happens-before when another thread supplies that value. The diagram computes one pure scalar function. It contains no threads, synchronization, or publication proof; its graph helps identify consumed values, while the language contract supplies the required ordering edges.

Account for one published configuration

A producer fills 64 four-byte configuration entries, then release-stores true to an initially false atomic flag. Three workers acquire-load that true value and read only. The producer retains the immutable configuration until all workers join. Audit the handoff.

  1. Count the initialized payload: 64 × 4 = 256 bytes. Payload size affects the memory budget but does not change the need for an ordering edge for all initialized entries.

  2. For each of the three workers, connect its successful acquire observation to the producer's release store. Initialization is sequenced before release and each payload read follows acquire, giving the required transitive happens-before paths.

  3. Check the conditions outside the graph: no worker writes the entries, no later generation overwrites them, and the producer keeps them alive until the three joins complete. If any condition changes, repeat the proof rather than relying on the old flag pattern.

The result

The specified one-shot handoff safely publishes 256 bytes to three readers. Replacing either flag operation with relaxed ordering removes this particular synchronization argument; it does not merely make the handoff a little slower or less likely.

Explore the model

Interactive lab

Interactive lab · network

Data dependency still needs a safe handoff

Set weight w to zero, vary input x, then restore w=1 and predict the changed sigmoid output. The pure graph σ(wx−0.5) identifies consumed values; it does not execute threads, synchronize memory, or validate publication.

Data dependency still needs a safe handoffOne inspectable sigmoid unit, σ(wx − 0.5). Playback traces the computation graph. There is no training, attention mechanism or hidden deep network. Current readings: Product · wx: 1.2; Logit · wx − 0.5: 0.7; Sigmoid output: 0.6682. All parameters are adjustable with the labeled controls below.One input. One weight. One sigmoid.x1.20× w1.20+ b0.70σ0.668output0.668w = 1.00b = −0.50σ(z) = 1 / (1 + exp(−z))
Computation graphSignal trace
Product · wx
1.2
Logit · wx − 0.5
0.7
Sigmoid output
0.6682
t = 0 s

One inspectable sigmoid unit, σ(wx − 0.5). Playback traces the computation graph. There is no training, attention mechanism or hidden deep network. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA computation depends on its inputs, but a cross-thread source needs a separately proved ordering and lifetime protocol.

Check your understanding

Why can an acquire read of the producer's release-stored ready value safely precede ordinary immutable-payload reads in the stated one-shot pattern?

Try it yourself

A revised design publishes an ordinary 128-byte payload through a relaxed atomic flag, then overwrites that payload immediately for the next update. Identify two independent gaps and propose one simple repair.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Ask first how initialization becomes ordered before reads, then ask who prevents a new write during an old read.

Compare with the solution

The relaxed handoff lacks the release/acquire edge used in the publication proof. Immediate reuse also permits conflicting payload accesses and can violate the reader's lifetime or generation assumptions. A straightforward repair is to guard every payload read and update with the same mutex, retaining storage while it is in use. Alternatively, publish release/acquire immutable snapshots with an independently correct lifetime protocol. The 128-byte size does not repair either gap.

Take it with you

  • Happens-before follows sequencing and specified synchronization, not elapsed time.
  • C++ data races have undefined behavior; a lost-update story is not a portable result bound.
  • A publication proof must include immutable access and a valid object lifetime.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.