Synchronization

Why this matters

Two functions, each correct on its own, give a wrong result together. A test passes a hundred times and fails on the hundred and first. The bug vanishes the moment you add a printf. There is nothing mystical here. This is concurrent access to shared data, and the theory behind it is quite precise.

Prerequisites. What threads share (module 8), preemption by the scheduler (module 7).

One line of code, three operations

Neither thread made a mistake: the mistake was assuming that x++ runs as one indivisible step.

In source code x++ looks indivisible, but the CPU performs three separate actions: read from memory, modify in a register, write back. Another thread can step in between any two of them, either because the scheduler preempted the first one or because the second is physically running on another core.

A race condition occurs when the result depends on the order in which operations of different threads happened to run. “Happened to” is the key part: the order is not defined anywhere, so the bug does not reproduce every time.

A critical section is a piece of code that works with shared data and must not be executed by two threads at once.

Three requirements for a solution

Any mechanism that protects a critical section has to satisfy three conditions, and each of them can be broken separately:

1. Mutual exclusion. At most one thread is in the critical section at a time.
2. Progress. If the section is free and someone wants to enter, the choice is not postponed indefinitely.
3. Bounded waiting. Whoever is already waiting will eventually get in. Violating this condition is called starvation.

Attempts to do this by hand with ordinary variables, such as Peterson’s algorithm, are mathematically correct but do not work on modern hardware without extra measures: both the CPU and the compiler are allowed to reorder memory operations. More on that below.

The hardware foundation

You cannot build an indivisible operation out of divisible ones in software alone; you need help from the CPU. It provides atomic instructions that execute either completely or not at all.

The basic one is called compare-and-swap, or simply CAS: if the address holds the expected value, replace it with the new one and report whether that worked. One instruction that cannot be interrupted halfway. Everything else is built from it: counters, locks, lock-free queues.

// atomic x++, lock-free
int old;
do { old = x; } while (!compare_and_swap(&x, old, old + 1));

The loop is needed because the value may change between reading x and the CAS. Then the CAS fails and the attempt has to be repeated.

Tools

A mutex provides mutual exclusion for a single critical section. Once one thread holds it, the rest have to wait. Its most important property is that a mutex has an owner: only the thread that acquired it can release it.

A spinlock does the same, but the thread does not go to sleep. It spins in a loop checking whether the lock is free. It pays off only when the wait is known to be shorter than the cost of two context switches, that is, inside the kernel, over a few instructions. In application code it is almost always a mistake.

A condition variable solves a completely different problem: not “let me in” but “wake me up when the condition holds”. A thread atomically releases the mutex and goes to sleep; another thread changes the state and signals. Without it you would have to poll the condition in a loop and waste the CPU.

A semaphore is a counter with two operations: wait decrements it and blocks at zero, signal increments it. A binary semaphore resembles a mutex, but it has no owner, so anyone can increment it. That makes a semaphore suitable for signaling between threads and, at the same time, dangerous as a replacement for a mutex.

Task	Tool
Protect shared data	mutex
Wait for a condition	condition variable
Limit the number of concurrent participants	counting semaphore
Notify about an event	semaphore or condition variable
Counter without a critical section	atomic operation

Check the condition in a loop, not in an if

Waking up on a condition variable does not guarantee that the condition actually holds: spurious wakeups happen, and a third thread may have changed the state between the signal and the mutex being reacquired. So always while (!condition) wait(...), never if. This is the most common mistake in code that uses condition variables.

Memory model

This is the least obvious part of the topic. You wrote: write data, then write ready = 1. Another thread reads ready, sees a one, reads data and gets the old value.

The reason is that nobody preserves the order of memory operations. The compiler reorders instructions while optimizing. The CPU executes them out of order and has store buffers, so writes become visible to other cores in a completely different sequence from the one in which they were executed.

A memory barrier is an instruction that forbids reordering across it. Application code rarely places barriers by hand: the atomic types of languages (std::atomic, AtomicInteger) already carry the necessary guarantees, and a mutex is by definition a barrier on both entry and exit.

The practical conclusion: in C and C++, unlike Java, volatile does not solve this problem. It forbids the compiler from caching the value in a register and tells nothing to the CPU or to other cores.

Classic problems

Bounded buffer. Producers put items in, consumers take them out, space is finite. You need three things: a mutex on the buffer itself and two semaphores, one for free slots and one for available items. This is the model of any task queue.

Dining philosophers. Five philosophers, five forks, each needs the two adjacent ones. If everyone picks up the left fork at the same time, everyone waits for the right one forever. This is the shortest demonstration of deadlock, and of how the order of acquiring resources removes it.

Readers and writers. Many can read at once, but only one can write, and only with no readers present. The problem shows where starvation comes from: a naive implementation that favors readers will not let a writer in as long as new reads keep arriving.

Deadlock

A deadlock occurs when each participant waits for a resource held by another. It happens only when four conditions hold at the same time:

1. Mutual exclusion. The resource cannot be shared.
2. Hold and wait. A participant holds one thing and asks for another.
3. No preemption. The resource cannot be taken by force; it has to be given up.
4. Circular wait. The chain of waits has closed into a ring.

To solve the problem, it is enough to remove any one of them. In practice the fourth is the cheapest: establish a global order for acquiring resources and always follow it. If everyone takes the lower-numbered fork first, the ring never closes.

Starvation is a separate problem that is often confused with deadlock. In a deadlock nobody moves at all. Under starvation the system keeps working, but one particular participant never gets the resource.

A related issue, priority inversion, occurs when a low-priority thread holds a lock that a high-priority one needs, and the latter effectively drops to the other’s priority. This caused the Mars Pathfinder failures in 1997. The cure is priority inheritance: the lock owner temporarily gets the priority of the highest-priority thread waiting on it.

How it actually works in Linux

cat > race.c <<'EOF'
#include <pthread.h>
#include <stdio.h>
static volatile long counter;
static void *bump(void *_) {
    for (int i = 0; i < 1000000; i++) counter++;
    return NULL;
}
int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, bump, NULL);
    pthread_create(&b, NULL, bump, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    printf("%ld (expected 2000000)\n", counter);
}
EOF
gcc -O2 -pthread race.c -o race && ./race && ./race && ./race

Three runs give three different numbers, and none of them is correct: around a million instead of two.

Remove volatile and the race disappears

Try building the same code without volatile. The result will be exactly 2000000 every time, and it is easy to conclude, wrongly, that there is no race.

The reason is visible in the assembly (gcc -O2 -S): without volatile the compiler proves that the loop adds one a million times and folds it into one instruction, addq $1000000, counter(%rip). The window in which another thread could step in shrinks almost to zero.

volatile forbids that optimization, which is why the race becomes visible. But note: it exposed the bug, it did not fix it. The result is still wrong, because counter++ is still three operations. The “common misconceptions” section below makes the same point.

gcc -O2 -pthread -fsanitize=thread race.c -o race-tsan && ./race-tsan

ThreadSanitizer finds the race even when a particular run gave the right answer. For concurrent code it is a mandatory tool: you cannot rely on a test having “passed”.

grep -E 'futex' /proc/self/status; man 2 futex | head -20

futex is the mechanism on which mutexes and semaphores are built in Linux. Acquiring a free mutex does not enter the kernel at all: it is an atomic operation in user space. Only those who have to wait go into the kernel.

Common misconceptions

“volatile makes a variable thread-safe.” Not in C and C++. It forbids the compiler from caching the value in a register and guarantees nothing about atomicity or about ordering between cores. You need atomic types or locks.

“It’s one operation, so it’s atomic.” x++ is three operations. What’s more, assigning a 64-bit value on a 32-bit platform can also split in two.

“The bug doesn’t reproduce, so it doesn’t exist.” A race shows up only under a rare coincidence of scheduling, and a change in load or new hardware makes that coincidence ordinary. A passing test proves nothing. The proof is a sanitizer report.

“A semaphore is the same thing as a mutex.” A mutex has an owner; a semaphore does not. A semaphore can be released by a thread other than the one that acquired it, and that is a perfectly legal operation, which makes it dangerous as a replacement for a mutex.

“A spinlock is faster because there are no switches.” It is faster only when the wait is shorter than two context switches. Otherwise the thread burns its time quantum doing nothing and also keeps the lock owner from getting the CPU.

“More locks means safer.” Every additional lock adds one more way to close the ring. It is safer to have less shared state.

Check yourself

1. Two threads each run x++ a million times. What will the final value be?

Exactly 2,000,000Between 1,000,000 and 2,000,000, different on every runExactly 1,000,000Always 0

2. What does volatile in C guarantee for a variable read by two threads?

Atomic accessOnly that the compiler will not cache the value in a register: no atomicity, no ordering between coresMutual exclusionA memory barrier on every access

3. What is the fundamental difference between a mutex and a binary semaphore?

A mutex is fasterA mutex has an owner: only the thread that acquired it can release itA semaphore works only between processesA mutex does not block the thread

4. Why is the condition of a condition variable checked in a while and not in an if?

The code is shorter that wayWaking up does not guarantee the condition holds: spurious wakeups happen, and another thread may have changed the stateif does not work with mutexeswhile reduces the number of context switches

5. Five philosophers picked up the left fork at the same time. Which of the four deadlock conditions is cheapest to remove?

Mutual exclusion: allow a fork to be sharedCircular wait: introduce a global order for acquiring resourcesHold and wait: forbid holding anything while waitingNo preemption: allow forks to be taken by force

6. A low-priority thread holds a lock that a high-priority thread needs. What is this called and how is it cured?

Deadlock; cured by a restartPriority inversion; cured by the lock owner inheriting the priorityStarvation; cured by agingA race; cured by atomic operations

Lab

A3 — producer–consumer. Part one: a mutex and a condition variable, checked with ThreadSanitizer. Part two: a lock-free ring buffer built on CAS, and a measurement of which loads it actually wins under and which it loses under.

Sources

• OSTEP: Locks, Condition Variables, Semaphores, Deadlock
• Silberschatz, Operating System Concepts, chapters 6–8
• man 7 pthreads, man 2 futex, man 3 pthread_cond_wait
• The Little Book of Semaphores — a problem book on semaphores
• Memory Barriers: a Hardware View — the Linux kernel memory model