Threads and synchronization

A process has one address space and, so far, one flow of execution. But many programs want to do several things at once: a server handling many clients, a browser decoding images while the page scrolls, a compiler using all the cores of the machine. Separate processes could do it, but they don't share memory, and creating and switching them is expensive. Threads are the answer: several flows of execution inside one process, sharing its memory. And the moment two flows share memory, a new class of bug appears, which the OS has to provide tools to prevent.

The classic topics are cooperating processes, the race conditions they cause, and semaphores to fix them. This chapter covers them in C with POSIX threads, measured on the Apple M2 it was written on, under macOS and in a Linux virtual machine.

Threads: one address space, several flows

Each thread has what it needs to run on its own: its own registers, program counter and stack. Everything else belongs to the process and is shared: the code, the global variables, the heap, the open files. A pointer to a heap object is valid in every thread, which makes cooperation cheap, and makes it possible for two threads to modify the same object at the same moment.

#include <pthread.h>

void *work(void *arg) {         // runs in the new thread
    /* ... */
    return NULL;
}

pthread_t t;
pthread_create(&t, NULL, work, NULL);   // start a second flow of execution
/* ... the first flow continues here ... */
pthread_join(t, NULL);                  // wait for it to finish

The kernel schedules threads, not processes: on Linux each thread is a task of its own, created by the clone system call with flags that say what to share with the parent, and it shows up under /proc/<pid>/task. On each core, a context switch between two threads of the same process is cheaper than between processes, since the address space and the TLB stay as they are. Creation is cheaper too. Creating and joining a thread that does nothing took 23 µs on macOS and 62–65 µs in the Linux VM, against 0.7–1 ms and 0.12 ms for fork plus wait in the processes chapter.

The classic example of why threads matter is a web server with a cache of pages: while one thread waits for the disk, others serve requests from the shared cache. It's still the right picture, even if the disk wait is now closer to 100 µs than 20 ms.

A race, for real

Two threads each add 1 to a shared counter ten million times. The total should be twenty million:

static volatile long counter;   // volatile: really load and store each time

void *work(void *arg) {
    for (long i = 0; i < 10000000; i++)
        counter++;
    return NULL;
}

Three runs on the M2 under macOS printed 10091509, 10163404 and 10069050. In the Linux VM: 10145520, 10440722 and 10643606. Nearly half of the increments were lost, and a different number each time.

The reason is that counter++ isn't one indivisible step. On ARM64 it compiles to three instructions: load the value into a register, add 1, store it back.

ldr  x9, [x8]        ; read counter
add  x9, x9, #1      ; add 1 in a register
str  x9, [x8]        ; write it back

If both threads load the same value, both store value + 1, and one increment is lost. x86-64 compiles it to a single instruction, inc QWORD PTR [rip+counter], but that doesn't help: the instruction still reads memory and then writes it, and another core can slip in between. The simulator's micro view shows the two separate transactions on the bus:

A bus READ of counter, the ALU adds 1, then a bus WRITE: three bus cycles counting the instruction fetch, two of them for the data. On a multicore machine, those two data transactions are exactly where another core's increment can fall. This is a race condition: the result depends on the timing of the threads. A classic example is subtler (a lost wakeup in a producer-consumer pair), but the nature is the same: a sequence of operations that must happen as one, and doesn't.

Mutual exclusion

The part of the code that must not run in two threads at once (here, counter++) is a critical section. The standard tool to protect it is a mutex (from mutual exclusion): a lock that one thread at a time can hold.

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);      // blocks while another thread holds it
counter++;
pthread_mutex_unlock(&lock);

With the mutex, all three runs printed exactly 20000000, on both systems. The price: the loop took 193–197 ms on macOS instead of 6.5 ms, and 610–670 ms instead of 17–19 ms in the Linux VM.

How can a lock be built, when checking "is it free?" and then taking it is itself a race? With the CPU's atomic instructions, which read and modify a memory location as one indivisible operation that no other core can interrupt: x86's lock-prefixed instructions and cmpxchg, ARM64's ldadd, cas and the load-exclusive/store-exclusive pairs ldxr/stxr. A mutex is a word in memory: locking it is an atomic compare-and-swap from "free" to "taken". If that succeeds, the thread continues without ever entering the kernel. Only if the lock is taken does the thread ask the kernel to put it to sleep (on Linux with the futex system call, "fast user-space mutex", which sleeps until the word at a given address changes), and the unlocking thread wakes it with another futex call. Windows's critical sections, fast because they stay in user space, work the same way.

Semaphore operations used to be system calls, made indivisible on a single processor by disabling interrupts. Both describe older systems. Today's locks and semaphores are built on atomic instructions in user space, which work across cores, and they cost a system call only when a thread actually has to wait.

Atomic operations

For a single counter, a lock is overkill: the CPU can do the whole increment atomically. C11 exposes it:

#include <stdatomic.h>
static _Atomic long counter;

atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

Here is what compilers emit for a plain increment and for this atomic one:

With atomics, all runs printed 20000000, in 155–170 ms on macOS and 120–129 ms on Linux. The memory_order argument says how the operation is ordered with respect to the thread's other memory accesses; relaxed means "atomic, but no ordering promise". The default, sequential consistency, is stronger and, on ARM64, uses ldaddal instead of ldadd. The ISA chapter shows with litmus tests why ordering matters when threads communicate through memory, and what acquire and release mean.

What synchronization costs

Measured as time per operation over 20 million operations, split across 1 to 8 threads all hitting the same variable:

Three lessons. Uncontended, a mutex costs about 6–7 ns, far less than the 95–155 ns of a system call, which confirms that no system call is involved. Contended, everything gets slower, because the cache line holding the variable has to travel from core to core for every operation: a shared counter is a bottleneck no matter how it's protected. And under heavy contention the mutex can beat the atomic: a thread that holds the lock does many increments in a row while the others sleep, whereas atomics make the line bounce on every single one. The sleeping shows up in the Linux VM's context-switch counts: a few dozen at most for the atomic runs, 1,200–3,700 for the mutex with two threads, and about 115,000 with eight, each one a futex sleep and wakeup.

The practical answer is to share less. A program that needs a global count gives each thread its own counter and adds them up at the end.

Semaphores and producer-consumer

The central example is the producer-consumer problem: one thread produces items into a bounded buffer, another consumes them. The consumer must wait when the buffer is empty, the producer when it's full. A naive first attempt, with explicit sleep and wakeup calls, has a race: the consumer checks that the buffer is empty, the producer inserts an item and sends a wakeup before the consumer has gone to sleep, the wakeup is lost, and eventually both sleep forever.

Dijkstra's semaphores fix it. A semaphore is a counter with two atomic operations: down (sem_wait in POSIX) decrements it, or sleeps while it's 0; up (sem_post) increments it and wakes a sleeper if there is one. A wakeup sent early is not lost: it stays in the count. Two semaphores solve producer-consumer, one counting empty slots and one counting full slots:

sem_t empty_slots, full_slots;          // start at SLOTS and 0

void *producer(void *arg) {
    for (long i = 1; i <= ITEMS; i++) {
        sem_wait(&empty_slots);         // down: wait for a free slot
        buf[in] = i; in = (in + 1) % SLOTS;
        sem_post(&full_slots);          // up: one more item
    }
    return NULL;
}

void *consumer(void *arg) {
    long sum = 0;
    for (long i = 1; i <= ITEMS; i++) {
        sem_wait(&full_slots);          // down: wait for an item
        sum += buf[out]; out = (out + 1) % SLOTS;
        sem_post(&empty_slots);         // up: one more free slot
    }
    *(long *)arg = sum;
    return NULL;
}

With an 8-slot buffer and a million items, the consumer's sum came out as 500000500000, the correct total, in every run on Linux, at about 4 µs per item: the threads spend most of their time sleeping and waking each other. With one producer and one consumer, each index is only touched by one thread, so no mutex is needed; with several producers, in would need one.

On macOS, the same program fails at the first line: sem_init returns −1 with ENOSYS, "Function not implemented". macOS supports only named POSIX semaphores (sem_open) and offers its own alternatives, such as Grand Central Dispatch's semaphores. The standard that promised portability doesn't guarantee it for every call.

Condition variables

The more common tool today is a mutex paired with condition variables, part of the pthread API. A condition variable lets a thread sleep until another thread signals that something has changed, releasing the mutex while it sleeps and taking it back before it returns:

pthread_mutex_lock(&m);
while (count == 0)                        // re-check after every wakeup
    pthread_cond_wait(&not_empty, &m);    // unlock, sleep, relock
int item = buf[out]; out = (out + 1) % SLOTS; count--;
pthread_cond_signal(&not_full);
pthread_mutex_unlock(&m);

Unlike a semaphore, a condition variable has no memory: a signal with nobody waiting is lost. That's why the condition is kept in ordinary variables protected by the mutex (count here), and why it's tested in a while loop: the state is checked under the lock, so no wakeup can fall between the test and the sleep. The same million items went through in about 1 µs per item on macOS and 4.2–4.6 µs in the Linux VM, with the correct sum.

Deadlock

Locks solve races and create a new problem. Two threads each need two mutexes, a and b, and take them in opposite orders:

void *t1(void *x) { for (;;) { lock(&a); lock(&b); rounds++; unlock(&b); unlock(&a); } }
void *t2(void *x) { for (;;) { lock(&b); lock(&a); rounds++; unlock(&a); unlock(&b); } }

If t1 takes a while t2 takes b, each waits forever for the lock the other holds. A watchdog thread that checks every 0.1 s whether rounds is still increasing caught it every time, in ten runs out of ten: after as few as 19 rounds and as many as 3,474. Changing t2 to take a first, like t1, made the same program run for 5 s and 177 million rounds without a hitch.

A deadlock needs four conditions at once (Coffman and colleagues, 1971): resources used in mutual exclusion; threads that hold one resource while waiting for another; no preemption (a lock can't be taken away from its holder); and a circular wait. Removing any one prevents it. In practice, programs break the circle: every thread takes locks in the same global order, as in the fix above. Databases, which can't impose an order on arbitrary transactions, detect cycles instead and abort one of the transactions involved.

Takeaways

• Threads are flows of execution sharing one address space; each has its own registers and stack. They're cheaper to create than processes: 23 µs on macOS, 62–65 µs in the Linux VM.
• A race condition is a result that depends on timing. counter++ from two threads lost nearly half of 20 million increments, because it's a read, an add and a write.
• A mutex protects a critical section. It's built on atomic instructions and enters the kernel (via futex on Linux) only to sleep: about 6–7 ns uncontended.
• Atomics (lock inc, ldadd) make single operations indivisible: 2 ns relaxed, 4 ns sequentially consistent. Under contention, any shared variable costs tens of nanoseconds per operation.
• Semaphores count wakeups so none is lost, and solve producer-consumer with two counters; macOS doesn't implement unnamed ones. Condition variables plus a mutex are the usual alternative, always waited on in a while loop.
• A deadlock needs mutual exclusion, hold-and-wait, no preemption and a circular wait. Taking locks in a fixed order prevents it.