3 · Sharing between threads Draft
Chapter 3 — Sharing between threads
On this page
One thread on one core is the easy case: one stream of instructions, one set of caches, and an operating system underneath it. A program that does real work at speed is several threads. One receives, one decides, one sends, one writes down what happened, and they must hand each other data. The obvious way is shared memory, since every thread of a process sees the same addresses. The moment two threads touch the same address, a question appears that one thread never had to ask: when this core writes a value, when does that core see it, and in what order relative to the writes around it? The source code implies an answer, and the machine does not give it. Each core keeps private copies of the lines it uses, and parks its writes in a small queue of its own before even its own cache sees them. The cores run a protocol between them to keep their copies consistent. And the compiler rearranges loads and stores on the assumption that no other thread is looking.
That protocol has prices, and they sit easily against the 1 µs budget. A load or store to a line the core already owns costs about a nanosecond. An atomic read-modify-write on such a line, an instruction that reads a value, changes it and writes it back with no other core able to act in between, costs about 5 ns, because the core must hold the line alone and empty its queue of pending writes first. Every lock is built from that one instruction, and so are most structures that avoid locks. If another core wrote the line last, the instruction first waits for the line to cross: 50–100 ns on one socket and two to three times that between sockets, a tenth of the budget or more for one variable. A mutex, the lock that lets one thread in at a time, costs 20–40 ns to take and release when nobody else wants it. When another thread does want it, the loser asks the kernel to put it to sleep, and waking it costs 5–20 µs on a good day and 100–200 µs after a quiet spell: five to two hundred budgets, spent waiting in a queue nobody designed. If the thread holding the lock is preempted, everyone behind it waits out the whole time slice, which is milliseconds.
None of the expensive cases is the common one, and that is the shape of the problem again. A benchmark of a mutex measures the uncontended path and reports 30 ns; the running system’s histogram carries the contended path in its p99.9 and its max. The second price is not time but correctness. A write that another core sees out of order is a bug that x86 hardware rarely exposes and ARM hardware exposes readily, so code can pass every test on one machine and fail on another, or pass on both and fail after a compiler upgrade. Safe Rust settles part of this at compile time. It refuses to compile a data race, two threads touching the same ordinary memory without synchronisation, which would be undefined behaviour. It does not forbid race conditions, outcomes that depend on timing, and an atomic used with too weak an ordering compiles in safe code and simply gives wrong answers. Which ordering each access needs is left to the programmer, and that is most of this chapter.
The chapter starts with what shared memory physically is: cores, their private caches, the store buffer that holds each core’s writes before its cache sees them, and the coherence protocol that keeps the copies consistent. Then the ladder of what each kind of sharing costs. Then one mechanism per section, atomic operations, reordering, the memory model that says which reorderings are allowed, locks, structures that do without locks, and the protocols for publishing data from one thread to others, asking of each what it is, why a machine of many cores needs it, and what it costs. What follows for a hot path is collected in one place near the end, after the understanding that justifies it. The labs specify programs and models to implement under ch03-concurrency/; companion code is not included here. Timings are estimates, and model-checking results must be obtained from the implementation rather than assumed from this text.