liveBook · Manning

Happens-before relation

As explained in Modern C, Third Edition

A happened-before relation is a partial ordering that establishes that one event in a concurrent execution precedes another for purposes of reasoning about their effects.

The happens-before relation, written F → E, provides a partial ordering for reasoning about events across concurrent threads. It combines same-thread sequencing with cross-thread synchronization. section 21.1

Its ordering rules include:

  • If F is sequenced before E in one thread, then F happens before E. section 21.1
  • Atomic operations can synchronize threads when one thread writes a value and another reads that value. section 21.1
  • Modifications of an atomic object follow a modification order consistent with each thread’s sequenced-before ordering. section 21.1
  • Certain C library calls, including thrd_join and mtx_lock, also provide synchronization. section 21.0

Atomic modification order

An atomic object can connect operations performed by different threads: _Atomic(unsigned) x = 11; one thread may execute ++x and x = 31, while another may execute x--, x = 5, and read x. The possible modifications are arranged in an order consistent with each thread’s local sequencing. section 21.1

_Atomic(unsigned) x = 11;

Inspect the atomic declaration used to anchor the modification-order example. section 21.1

How Modern C, Third Edition covers it

How deep it goes
Defines the relation, derives it from sequencing and synchronization, and stops short of exhaustive memory-model details.
Examples
Uses an atomic unsigned variable, cross-thread increments and assignments, reads, and a modification-order diagram.
What it assumes
Assumes threads, atomic objects, sequenced-before ordering, and synchronizing C library calls as working concepts.
What you can do after
Evaluate/understand concurrent behavior by identifying sequencing and synchronization that establish event ordering.
How it connects
Connects sequenced-before relations, synchronization, atomic objects, modification order, sequential consistency, and acquire-release consistency.

Also explained in

Compare how 5 books explain happens-before relation →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Modern C, Third Edition. The section links point to the parts of the book it draws on.