CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 5 min read

Ordering

Atomics, ordering and a checklist

In plain words: A letter in a locked post box may be collected only after the stamp is applied. The postal worker must see the stamp before the letter is taken. The same holds for data and a ready flag: the flag must be seen to be set only when the data is already there. The analogy stops in one place: a postal worker sees a stamp, and a processor needs an ordering instruction to guarantee it.

C11 provides atomic types in <stdatomic.h> and operations with an explicit memory order. The two orders that matter most make a pair: a release store says "everything I wrote before this is visible to a thread that sees this store", and an acquire load says "after I see this value, I also see everything written before the matching release". Together they pass data from one thread to another:

static int data;  static atomic_int ready;

/* producer */  data = 42;  atomic_store_explicit(&ready, 1, memory_order_release);

/* consumer */  while (!atomic_load_explicit(&ready, memory_order_acquire)) ;
                printf("data = %d\n", data);        /* always 42 */

This is a happens-before relationship: the write of data happens before the read of data, so the plain variable data is safe to read, and there is no data race. The run printed data = 42, and TSan, which understands acquire and release, reported nothing for it. The default order, memory_order_seq_cst, is the strongest and the easiest to reason about (page 1 used it to fix Peterson's lock). The weaker orders can be faster and are harder to get right, so use the default until measurement shows a need.

A checklist from the experience of this level:

  1. Share as little as possible (page 4 of Level 2). Data that one thread owns needs no lock.
  2. Protect each shared variable with one named lock, and write the name in a comment.
  3. Make check and use one critical section (atomicity), and enforce the order of setup and use (order).
  4. Take several locks in one global order (page 7).
  5. Wait in a loop on a condition variable (page 4).
  6. Never use a plain variable for cross-thread communication; use a lock or an atomic.
  7. Run the tests under ThreadSanitizer, with timing noise added (a short random sleep) to widen the windows.

Happens-before

Happens-before is the ordering relation between memory operations in different threads that is established by synchronisation, such as an unlock followed by a lock of the same mutex or a release store seen by an acquire load, so that the effects of the first are guaranteed to be visible to the second.

Example: the producer's write of data happens before the consumer's read, because the consumer's acquire load saw the producer's release store.

Common mistake

Treating a passing test as proof. A concurrency bug can pass a million runs. Test with tools, with injected delays, and with more threads than processors.

Interview angle

Answer in your head first, then open it.

What is a data race?

Two unordered accesses to one location, at least one a write; undefined behaviour in C.

What is an atomicity violation?

A check and an action that another thread can split, such as test-then-use of a pointer.

What is an order violation?

Code that assumes one thread has set something up before another uses it.

How do you find races?

ThreadSanitizer or Helgrind, plus stress tests.

What do acquire and release mean?

A release store makes earlier writes visible to the thread whose acquire load sees it.

Check yourself: 1. What does a release store guarantee? 2. Why is the plain data read safe in the example? 3. Name three items of the checklist.

Words you will meet

Word Meaning
Atomicity violation A group of steps meant to be indivisible gets interleaved
Order violation An assumed order of operations is not enforced
Data race Unordered conflicting accesses, one a write
Undefined behaviour The language promises nothing about the result
ThreadSanitizer A compiler-based tool that finds races
Helgrind A Valgrind tool for races and lock order
Lock-order inversion Two threads take two locks in opposite orders
Memory order The ordering guarantee of an atomic operation
Acquire and release A matched pair that passes data between threads
Happens-before A guaranteed ordering between operations

Quick notes

  • An atomicity violation is a concurrency bug in which a group of operations that must execute without interruption, such as checking a condition and acting on it, is interleaved with operations of another thread that invalidate the condition in between.
  • An order violation is a concurrency bug in which one operation is assumed to occur before another, such as initialisation before use, but nothing in the program forces that order, so a different interleaving reverses it.
  • A data race is a situation in which two threads access the same memory location without ordering by synchronisation, at least one of them writing, and which the C standard defines as undefined behaviour for the whole program.
  • ThreadSanitizer is a dynamic analysis tool, built into the compiler, that instruments a program to record memory accesses and synchronisation, and that reports data races and lock-order inversions found during a run, with the code locations involved.
  • Happens-before is the ordering relation between memory operations in different threads that is established by synchronisation, such as an unlock followed by a lock of the same mutex or a.