In a shared-memory concurrent program, what does it mean to say that one action happens-before another, and what does that relationship guarantee about what a thread can see?
answer
- program order + synchronization order, transitive
- release pairs with the acquire that observes it
- partial order: unordered pairs = races
- visibility AND ordering in one package
- not wall-clock, not atomicity
basics
~20 sHappens-before orders actions: program order inside a thread, plus synchronization edges across threads (a release paired with a matching acquire). If A happens-before B, every write made before A is visible to B. It is transitive, not chronological.
solid answer
~50 sHappens-before is the partial order at the heart of every modern memory model. It comes from two sources: program order (inside one thread, an earlier statement happens-before a later one) and synchronization edges between threads - releasing a mutex happens-before the next acquisition of that same mutex; a release-store to a synchronized variable happens-before the acquire-read that observes it; starting a thread happens-before its first action; a thread's last action happens-before a successful join; a hand-off into a synchronized queue happens-before the take that receives it. The relation is transitive, so edges chain across threads. The guarantee is visibility plus ordering: if A happens-before B, the thread executing B must observe every memory effect that preceded A. If two conflicting accesses are ordered in neither direction, that is a data race and the model promises nothing - the reader may keep seeing a stale value indefinitely. It is not wall-clock order, not mutual exclusion, and not a cache flush.
code
text · 12 linesshared: data (plain), ready (release/acquire)
T1: data = 42 // plain write
release_store(ready, true) // release
T2: while (!acquire_load(ready)) {} // acquire; observes T1's store
print(data) // guaranteed 42
Edges: data=42 -(program order)-> release_store
release_store -(sync)-> acquire_load
acquire_load -(program order)-> print
=> data=42 happens-before print (transitivity)go deeper
Be able to say that without synchronization one thread may not see another's writes at all, and name two edge-creating operations such as lock/unlock and thread start/join.
Give the definition as program order plus synchronization edges plus transitivity, and show that one edge carries all the plain writes made before it.
Stress that it is a partial order, that unordered conflicting accesses are exactly the definition of a data race, and that testing cannot establish an edge exists - only naming the release/acquire pair can.
Frame it as the contract that lets compilers and CPUs optimize aggressively while still giving programmers a usable model, and connect it to the same construction in distributed systems (Lamport ordering, vector clocks).
## The problem it solves Reasoning about a concurrent program by interleaving its threads' statements assumes sequential consistency. Real platforms do not give that for free: compilers keep values in registers, hoist loads out of loops and reorder independent statements; processors buffer stores and execute out of order. Every one of those transformations is invisible to the thread doing it, but a second thread reading the same memory can observe a different order. A memory model is the contract that says which observations are legal, and happens-before is its central relation - the same shape appears in Java, C++11 and later, Go, C#, and Rust. ## The definition Happens-before is a partial order over memory actions, built from three rules. 1. **Program order**: within a single thread, an action written earlier happens-before an action written later. 2. **Synchronization order**: certain paired actions in different threads create an edge. A release action happens-before the acquire action that observes it. Canonical pairs: unlock then lock of the same mutex; store then load of a synchronized/atomic variable; thread start then the thread's first action; a thread's final action then a join that returns; enqueue on a synchronized channel then the matching dequeue. 3. **Transitivity**: if A happens-before B and B happens-before C, then A happens-before C. *Partial* is the key word. Most pairs of actions in different threads are unordered, and those are exactly the pairs that can race. ## What the edge buys you If A happens-before B, the thread performing B is guaranteed to see all writes that were performed before A, and to see them consistent with source order. Visibility and ordering come as one package - that is why a single synchronization edge can carry an arbitrary amount of ordinary, unsynchronized data written before it. If two accesses touch the same location, at least one writes, and neither happens-before the other, the program has a data race. The model then makes no promise: the reader may see the old value, see it forever, or in C and C++ trigger undefined behaviour. ## What it is not - **Not wall-clock time.** The write can occur an hour earlier and still not be visible; only an edge creates the obligation. - **Not mutual exclusion.** Ordering says nothing about the atomicity of a read-modify-write. - **Not a cache flush.** Mainstream CPU caches are coherent; staleness comes mainly from compiler register allocation, store buffers and reordering. The model deliberately abstracts over the mechanism so it can describe every platform at once. - **Not symmetric or total.** ## Using it in practice The working rule for design and review: for every piece of state shared between threads, name the edge that carries it - which release, and which acquire that observes it. If you cannot name the pair, there is no guarantee, however plausible the timing looks in testing. This also explains why correctness cannot be established by running the program: an absent edge usually still works on x86 and fails on a weaker memory model, a different compiler, or under load. The relation generalizes beyond memory. Lamport's happened-before for distributed systems - local order plus send-before-receive, closed transitively - is the same construction applied to events instead of loads and stores, which is why vector clocks and memory models feel so similar.
- If thread A writes data then hands off to B through a synchronized queue, and B later hands off to C the same way, is A's data guaranteed visible to C?Yes, by transitivity. A's write happens-before its enqueue (program order), the enqueue happens-before B's dequeue (synchronization edge), B's dequeue happens-before B's own enqueue (program order), and that happens-before C's dequeue. Chaining the edges gives A's write happens-before C's read, even though A and C never synchronized directly. This piggybacking is why a single handoff can safely carry a large, entirely unsynchronized object graph.
- Two threads each acquire a different mutex. Does that create any happens-before relationship between them?No. Edges are created only by matching operations on the same synchronization object - the same mutex, the same atomic variable, the same channel. Two unrelated locks order each thread's own actions internally but leave the two threads mutually unordered, so shared data touched under different locks still races. This is one of the most common ways a program that looks fully synchronized still has a visibility bug.
Like a relay race: the baton pass is the only moment the next runner is guaranteed to have what the previous one carried. Two runners on the track at the same time who never pass a baton share nothing, no matter who started first.
saying these in an interview costs you the question
- Saying happens-before means 'happens earlier in time' - it is an ordering obligation, not a clock reading
- Claiming synchronization is needed only to prevent lost updates, not for reading a value someone else already wrote
- Believing a value becomes visible eventually on its own, so a delay or sleep fixes it
- Describing it as 'flushing the CPU cache', which misses compiler register caching and reordering entirely
- Assuming any two synchronized operations create an edge, without checking they act on the same object