5. Synchronization
Chapter 3 gave threads a shared address space, which makes cooperation cheap and correctness fragile: two threads touching the same data at the same time can produce results that no sequential execution could ever produce. This chapter defines that hazard precisely, works up from the hardware instructions that make any solution possible to the primitives programmers actually use, applies them to the classic problems that every synchronization mechanism is measured against, and closes with the approaches that avoid locks altogether. Getting this material right is what separates a program that works from one that works until it is busy.
<a id="51-the-critical-section-problem"></a>
5.1 The Critical Section Problem
This section states the problem formally: what goes wrong when threads share data, what any correct solution must guarantee, and what a purely software solution looks like.
Race Conditions
Theory
A race condition exists when the result of a computation depends on the relative timing of concurrent operations. The program is not merely slow or occasionally wrong — it has no single defined behaviour, and the same input can produce different output on different runs.
The reason is that operations which look atomic in source code are not atomic in hardware. Consider the most famous example, counter++. In C or Java it is one expression; on the machine it is three separate steps:
- Load the value from memory into a register.
- Increment the register.
- Store the register back to memory.
A thread can be preempted between any two of these (Chapter 4), or two cores can execute them genuinely simultaneously (Chapter 3). If two threads each increment a counter of 10, the interleaving load(10), load(10), add, add, store(11), store(11) produces 11 instead of 12. One update is silently lost.
Three properties make race conditions uniquely nasty:
- They are intermittent. The bad interleaving may occur once in millions of executions, so the bug passes testing and appears in production under load.
- They are timing-sensitive. Adding a print statement, attaching a debugger, or running on a slower machine changes the timing and can hide the bug — the "Heisenbug" effect.
- They corrupt silently. A lost update produces no error, no exception, and no log entry. The data is simply wrong.
The precondition for a race is specific and worth memorising: two or more threads access the same memory location, at least one access is a write, and the accesses are not ordered by synchronization. Remove any of those three and there is no race — which is why immutable data and thread-confined data need no locks at all.
Analogy: two people editing the same paragraph of a shared document by loading it into their own editor, changing it, and saving. Both saw the original; the second save overwrites the first. No error is reported, and the first person's edit simply vanishes.
Example
counter++ is three machine operations, not one
Thread A memory Thread B
-------- ------ --------
load r1 <- counter (10) 10
10 load r2 <- counter (10)
add r1 <- r1 + 1 (11) 10
10 add r2 <- r2 + 1 (11)
store counter <- r1 11
11 store counter <- r2 (11)
^
Final value 11. Expected 12. One update LOST.
A correct interleaving, for contrast:
Thread A memory Thread B
load r1 <- 10 10
add r1 = 11 10
store counter <- 11 11
11 load r2 <- 11
11 add r2 = 12
12 store counter <- 12
The hardware permits BOTH. Without synchronization you get whichever
the scheduler and the memory system happen to produce.
public class LostUpdate {
private static int counter = 0; // shared, unsynchronised
public static void main(String[] args) throws InterruptedException {
Runnable task = () -> {
for (int i = 0; i < 1_000_000; i++) {
counter++; // load, add, store: 3 steps,
// interruptible between any two
}
};
Thread t1 = new Thread(task);
Thread t2 = new Thread(task);
t1.start(); t2.start();
t1.join(); t2.join();
// Expected 2,000,000. Actual: some smaller, unpredictable number,
// different on each run and on each machine.
System.out.println("counter = " + counter);
}
}
# The same defect, and the three conditions that create it.
import threading
balance = 1000 # (1) shared location
def withdraw(amount):
global balance
if balance >= amount: # CHECK
# A thread can be preempted right here. Both threads passed the check
# while the balance was still 1000.
balance -= amount # (2) at least one access is a WRITE
# (3) no synchronization orders them
threads = [threading.Thread(target=withdraw, args=(800,)) for _ in range(2)]
for t in threads: t.start()
for t in threads: t.join()
print(balance) # can be -600: both withdrawals passed the check.
# This class of bug is called check-then-act.
Key takeaways
- A race condition makes a program's result depend on timing, so it has no single defined behaviour.
- Operations that look atomic in source code (
counter++) are multi-step at the machine level and interruptible. - A race requires three things: shared access, at least one write, and no synchronization ordering them.
- Races are intermittent, timing-sensitive, and silent, which is why they survive testing and appear under production load.
🧪 Practice
- Run the Java example several times and record the results. Explain why the value differs between runs and why it is always at most 2,000,000.
- Identify the race in this pair of lines executed by two threads:
if (map.get(k) == null) map.put(k, v);. Name the pattern.- Interview-style: "A bug disappears when you add a logging statement. What does that tell you?" Hint: consider what logging does to timing and to the width of the vulnerable window.
Mutual Exclusion Requirements
Theory
Since the hazard is concurrent access to shared data, the remedy is to ensure that only one thread at a time executes the code that touches it. That code is a critical section, and the general structure of any solution is fixed:
do {
entry section // request permission to enter
critical section // access the shared data
exit section // release permission
remainder section // everything else
} while (true);
Mutual exclusion is the first and most important requirement: if one thread is executing in its critical section, no other thread may execute in its critical section. Everything else in this chapter is machinery for achieving that property efficiently and without introducing new failures.
Two points are commonly misunderstood and worth being precise about:
- Mutual exclusion is a property of the data, not of the code. Two different functions that modify the same structure are in the same critical section and must exclude each other. Conversely, two threads running the identical function on different data need no exclusion at all. This is why locks are conceptually attached to data — the lock protects an invariant, not a block of text.
- The critical section should be as short as possible. While one thread holds exclusive access, every other thread that needs the data is stalled. A long critical section serialises the program and destroys the parallelism Chapter 3 worked to obtain. Do expensive, blocking, or I/O-bound work outside it.
Any solution must also operate under realistic assumptions: threads execute at nonzero but otherwise unpredictable speeds, no assumptions may be made about the number of cores or the scheduler's choices, and a thread may be preempted anywhere — including inside the entry section itself.
Finally, the discipline is only as strong as its weakest participant. A lock protects data only if every accessor uses it. One function that touches the structure without taking the lock reintroduces the race for everybody — which is why access to shared state is normally encapsulated behind an interface that takes the lock internally.
Analogy: a meeting room with one key. Exclusion works only if everyone who needs the room takes the key; a single person who climbs in through the window makes the whole protocol meaningless.
Example
The four sections, and where the danger lies
+-------------------+
| entry section | <- request permission; may block here
+-------------------+
| CRITICAL SECTION | <- at most ONE thread here at a time
| (touch shared | keep it SHORT: everyone else is waiting
| data) |
+-------------------+
| exit section | <- release permission; must always run
+-------------------+
| remainder | <- unrelated work; full concurrency here
+-------------------+
Exclusion is per-DATA, not per-function
deposit() --+
+--> both modify `balance` -> SAME critical section
withdraw() --+ they must exclude each other
process(order_A) and process(order_B) -> different data,
no exclusion needed
Critical section length
BAD GOOD
lock() data = compute_expensive() // outside
data = compute_expensive() result = fetch_from_disk() // outside
result = fetch_from_disk() lock()
shared.update(data, result) shared.update(data, result) // short
unlock() unlock()
-> holds the lock for milliseconds -> holds it for nanoseconds
import threading
class Account:
"""Encapsulation is what makes the discipline enforceable: callers cannot
touch `_balance` without going through a method that takes the lock."""
def __init__(self, initial=0):
self._balance = initial
self._lock = threading.Lock() # the lock belongs to the DATA
def deposit(self, amount):
expensive = self._audit_record(amount) # entry: do slow work OUTSIDE
with self._lock: # entry section
self._balance += amount # critical section: short
return expensive # exit is automatic (with)
def withdraw(self, amount):
with self._lock: # SAME lock: deposit and withdraw
if self._balance < amount: # are one critical section because
return False # they touch the same data
self._balance -= amount
return True
@property
def balance(self):
with self._lock: # even READS need the lock, or they
return self._balance # can observe a torn/stale value
Key takeaways
- Every solution has the same shape: entry section, critical section, exit section, remainder.
- Mutual exclusion means at most one thread executes in its critical section at a time.
- Exclusion is a property of the shared data: different functions touching the same data share one critical section.
- Critical sections must be short, and the protocol only works if every accessor participates — hence encapsulation.
🧪 Practice
- Identify the critical sections in a linked-list implementation with
insert,delete, andsearch. Which must exclude which?- Rewrite a function that holds a lock across a network call so the lock covers only the shared-state update.
- Interview-style: "Is it safe for a getter to read a shared integer without the lock?" Hint: consider visibility across cores and multi-word values, not just torn reads.
Progress and Bounded Waiting
Theory
Mutual exclusion alone is trivially satisfiable — a solution that lets nobody enter the critical section excludes perfectly and is useless. Two liveness requirements rule out such degenerate answers, and together with mutual exclusion they form the complete specification of the critical-section problem.
Progress. If no thread is in its critical section and some threads wish to enter, then only those threads that are not in their remainder section may participate in deciding who enters next, and the decision cannot be postponed indefinitely.
Two clauses matter here. First, a thread that is uninterested — off doing unrelated work in its remainder — must not be able to block an interested thread. A solution where "it is B's turn" prevents A from entering even though B is not asking is a progress violation, and it is the exact defect of the naive turn-taking algorithm. Second, the decision must actually be reached in finite time; the system may not deadlock while the critical section stands empty.
Bounded waiting. There must exist a bound on the number of times other threads are allowed to enter their critical sections after a thread has requested entry and before that request is granted.
This rules out starvation. Progress guarantees someone gets in; bounded waiting guarantees everyone eventually gets in. Without it, a thread could lose the race indefinitely while others repeatedly enter — a live system in which one participant makes no progress. Note the requirement is only that a bound exists, not that it be small; a fair queue gives a bound of n-1, which is the practical target.
The three properties are independent, and it is instructive to see how each can fail alone:
| Property violated | Symptom |
|---|---|
| Mutual exclusion | Data corruption; the race is not prevented |
| Progress | Deadlock, or an uninterested thread blocking an interested one |
| Bounded waiting | Starvation; one thread waits forever while others proceed |
Analogy: mutual exclusion is "one person in the room at a time". Progress is "if the room is empty and someone is waiting, the door opens" — and someone who has gone home does not get a vote. Bounded waiting is "you will not be skipped an unlimited number of times".
Example
The three requirements, and a violation of each
1. MUTUAL EXCLUSION -- at most one thread in the CS
violated: |== A in CS ==|
|== B in CS ==| overlap -> corruption
2. PROGRESS -- an empty CS plus a waiter must lead to entry
violated by strict alternation:
turn = 0
A enters, exits, goes to its remainder (long computation)
B wants to enter -> waits for turn == 1 ... which only A can set
CS is EMPTY, B is waiting, and A is not even interested.
-> progress violated
3. BOUNDED WAITING -- a limit on how often others may overtake you
violated: A requests entry
B enters, exits, re-enters, exits, re-enters ... forever
A never gets in although the system is making progress.
-> starvation
Correct behaviour
A requests --> at most (n-1) other entries --> A enters
# A deliberately broken solution: mutual exclusion holds, progress does not.
turn = 0 # whose turn it is
def thread_0():
global turn
while True:
while turn != 0: # entry section: spin until it is my turn
pass
critical_section()
turn = 1 # exit: hand the turn to the other thread
remainder_0() # <-- if this takes an hour, thread_1 can run
# exactly once more and then blocks forever
def thread_1():
global turn
while True:
while turn != 1:
pass
critical_section()
turn = 0
remainder_1()
# Mutual exclusion: SATISFIED (turn has one value, so only one can proceed).
# Progress: VIOLATED (strict alternation forces an uninterested
# thread to act before an interested one can enter).
# Bounded waiting: satisfied (the bound is 1) -- correctness needs ALL THREE.
Key takeaways
- A correct solution must provide mutual exclusion, progress, and bounded waiting; the three are independent.
- Progress forbids threads in their remainder section from influencing who enters, and forbids indefinite postponement.
- Bounded waiting forbids starvation by capping how many times others may enter ahead of a waiting thread.
- Strict alternation satisfies mutual exclusion but violates progress, which is why it is not a solution.
🧪 Practice
- For the strict-alternation code above, construct a concrete execution that leaves thread 1 blocked while the critical section is empty.
- Design a solution that satisfies mutual exclusion and progress but violates bounded waiting, and describe the starving execution.
- Interview-style: "Why is 'nobody may ever enter' not an acceptable solution?" Hint: name which of the three requirements it satisfies and which it destroys.
Peterson's Solution
Theory
Peterson's solution (1981) is the classic proof that the critical-section problem can be solved in software alone, for two threads, using only ordinary loads and stores. Its value today is pedagogical rather than practical, and both halves of that statement are worth understanding.
It combines two ideas that fail individually:
- A flag array:
flag[i] = trueannounces "thread i wants to enter". Flags alone deadlock — both threads can set their flag and then wait for the other forever. - A turn variable: strict alternation. Turn alone violates progress, as shown above.
Peterson's insight is to use the flag to express intent and the turn to break ties, with one counter-intuitive detail: on entry, a thread sets turn to the other thread's index. Each politely yields, so whichever writes turn last loses the tie and waits. Since turn holds exactly one value, exactly one thread proceeds.
The entry condition — while (flag[other] && turn == other) — requires both clauses. A thread waits only if the other both wants in and holds the turn. If the other is uninterested, flag[other] is false and entry is immediate, which is precisely what fixes the progress violation of strict alternation.
All three requirements hold, and each can be argued directly: mutual exclusion, because both threads can only be inside if turn were simultaneously 0 and 1; progress, because an uninterested thread's flag is false; and bounded waiting, because after a thread exits it sets its flag false, so the waiter enters before the exiting thread could re-enter and re-take the turn — a bound of one.
The reason it is not used in practice is the important lesson: Peterson's solution assumes sequential consistency, and no modern processor provides it. Both CPUs and compilers reorder memory operations. If the write to flag[i] becomes visible to the other core after the read of flag[other], both threads can enter simultaneously. Making it work on real hardware requires memory barriers and atomic operations — the subject of 5.2 — at which point the hardware primitives are simpler and faster than the algorithm they were added to rescue.
Example
Peterson's entry protocol for two threads
Thread i: Thread j:
flag[i] = true; flag[j] = true;
turn = j; // yield to j turn = i; // yield to i
while (flag[j] && turn == j) while (flag[i] && turn == i)
; // wait ;
CRITICAL SECTION CRITICAL SECTION
flag[i] = false; flag[j] = false;
Why exactly one proceeds
Both set their flag -> both want in
Both write turn -> the LAST write wins and that thread WAITS
turn holds ONE value -> the other thread's condition is false
-> exactly one enters
Why an uninterested thread does not block anyone
flag[j] == false -> the while condition is false immediately
-> thread i enters without consulting `turn` at all
-> progress restored (this is what strict alternation lacked)
Why it BREAKS on real hardware
Thread i writes flag[i]=true | store buffered, not yet visible to core j
Thread i reads flag[j] | reads STALE false
Thread j writes flag[j]=true | store buffered
Thread j reads flag[i] | reads STALE false
-> BOTH enter the critical section. Mutual exclusion lost to reordering.
/* Peterson's solution -- correct on paper, broken on a real CPU
unless the marked barriers are present. */
#include <stdatomic.h>
#include <stdbool.h>
static atomic_bool flag[2] = {false, false}; /* "I want to enter" */
static atomic_int turn; /* tie-breaker */
void enter_critical(int self) {
int other = 1 - self;
atomic_store(&flag[self], true); /* 1. announce intent */
atomic_store(&turn, other); /* 2. politely yield the turn */
/* Without sequentially consistent atomics (or an explicit
atomic_thread_fence(memory_order_seq_cst) here), the CPU may reorder
the store above past the load below, and BOTH threads enter. */
while (atomic_load(&flag[other]) && atomic_load(&turn) == other)
; /* 3. wait only if the other
wants in AND holds the turn */
}
void leave_critical(int self) {
atomic_store(&flag[self], false); /* release: bound of one */
}
# The same algorithm, showing why it does not generalise past two threads.
# Peterson's is inherently 2-thread. The n-thread software solutions
# (Lamport's Bakery, Eisenberg-McGuire) are considerably more complex --
# another reason hardware support won.
class Peterson:
def __init__(self):
self.flag = [False, False]
self.turn = 0
def lock(self, me):
other = 1 - me
self.flag[me] = True # intent
self.turn = other # yield: last writer waits
while self.flag[other] and self.turn == other:
pass # spin
def unlock(self, me):
self.flag[me] = False
Key takeaways
- Peterson's solution proves the problem is solvable in software alone, for two threads, with plain loads and stores.
- Flags express intent and the turn variable breaks ties; a thread yields the turn to the other on entry.
- It satisfies all three requirements, with a bounded waiting bound of one.
- It fails on real hardware because CPUs and compilers reorder memory operations, which is why hardware primitives are used instead.
🧪 Practice
- Trace Peterson's solution with both threads calling
locksimultaneously, and show that exactly one enters.- Explain why setting
turn = selfinstead ofturn = otherbreaks the algorithm. Construct the failing execution.- Interview-style: "Peterson's solution is provably correct. Why does no operating system use it?" Hint: the proof assumes a memory model that no shipping processor implements.
<a id="52-hardware-support"></a>
5.2 Hardware Support
Peterson's solution failed on real machines because the hardware does not execute memory operations in program order; this section covers the instructions processors provide to make correct synchronization possible at all.
Memory Barriers
Theory
Programmers imagine memory operations happen in the order written, and every core sees the same order. That model — sequential consistency — is what Peterson's solution assumed, and no modern processor provides it, because enforcing it would forfeit most of the performance of the last thirty years of CPU design.
Reordering happens at three levels, and all three must be considered:
- The compiler reorders and eliminates memory accesses during optimisation, hoisting loads out of loops and sinking stores.
- The processor executes out of order and uses store buffers: a write sits in a per-core buffer before reaching cache, so the writing core sees it immediately while other cores do not.
- The cache system propagates invalidations asynchronously, so different cores can observe writes in different orders.
A memory model specifies which reorderings are permitted. x86-64 uses TSO (total store order), which is relatively strong — it only allows a store to be reordered past a later load. ARM and POWER are far weaker and permit almost any reordering. Code that is accidentally correct on x86 frequently breaks on ARM, which is a common and expensive surprise.
A memory barrier (or fence) is an instruction that forbids reordering across it. The usual forms:
| Barrier | Guarantees |
|---|---|
Store barrier (sfence) | All stores before it are visible before any store after it |
Load barrier (lfence) | All loads before it complete before any load after it |
Full barrier (mfence) | Both, in both directions |
| Acquire | No later operation moves before this one (used when taking a lock) |
| Release | No earlier operation moves after this one (used when releasing a lock) |
Acquire/release is the pairing that matters in practice: a lock acquisition is an acquire barrier and a lock release is a release barrier, and together they guarantee that everything a thread did inside a critical section is visible to the next thread that acquires the same lock. This is precisely why correctly locked code needs no explicit fences — the locking primitives contain them.
Analogy: a barrier is a checkpoint on a production line. Work items may otherwise be reordered freely for efficiency, but nothing crosses the checkpoint out of order.
Example
Why store buffers break intuition (the classic "store buffer" litmus test)
initially x = 0, y = 0
Core 0: Core 1:
x = 1; y = 1;
r1 = y; r2 = x;
Intuition: r1 == 0 && r2 == 0 is impossible -- one store must land first.
Reality on x86 (TSO): BOTH stores sit in per-core store buffers while
both loads read from cache. r1 == 0 && r2 == 0 DOES occur.
core0 store buffer: [x=1] core1 store buffer: [y=1]
core0 reads y from cache -> 0 core1 reads x from cache -> 0
Fix: a full barrier between the store and the load on both cores.
Memory model strength
stronger x86-64 (TSO) : only store->load reordering allowed
ARM64 : almost anything, unless barriers are used
weaker POWER : weakest of the mainstream architectures
Code that "works" on x86 and fails on ARM is a standard porting bug.
Acquire / release pairing
Thread A Thread B
data = 42; while (!flag.load(acquire))
flag.store(true, release); ;
^ read(data); // guaranteed to see 42
nothing above may sink below ^
nothing below may rise above
#include <stdatomic.h>
int data = 0;
atomic_bool ready = false;
void producer(void) {
data = 42; /* ordinary write */
atomic_store_explicit(&ready, true,
memory_order_release); /* RELEASE barrier:
the write to `data`
cannot sink below */
}
void consumer(void) {
while (!atomic_load_explicit(&ready, memory_order_acquire))
; /* ACQUIRE barrier:
the read below
cannot rise above */
printf("%d\n", data); /* guaranteed to be 42 */
}
/* Without the release/acquire pair, the consumer may observe ready == true
while `data` is still 0: the two writes can become visible out of order. */
public class Visibility {
// `volatile` in Java gives release semantics on write and acquire on read.
private volatile boolean ready = false;
private int data = 0;
void producer() {
data = 42;
ready = true; // volatile write: a release barrier
}
void consumer() {
while (!ready) { } // volatile read: an acquire barrier
assert data == 42; // guaranteed by the happens-before edge
}
// Remove `volatile` and the JIT may hoist the read of `ready` out of the
// loop entirely, producing an infinite loop even on a strong CPU.
}
Key takeaways
- No modern processor provides sequential consistency; compilers, CPUs, and caches all reorder memory operations.
- Memory models differ by architecture: x86-64 (TSO) is strong, ARM and POWER are much weaker.
- Barriers forbid reordering across a point; acquire and release are the pairing used by locks.
- Correctly locked code needs no explicit barriers because lock acquire and release contain them.
🧪 Practice
- Write the store-buffer litmus test with two threads in a loop and count how often
r1 == 0 && r2 == 0occurs on your machine.- Remove
volatilefrom the Java example and run it. Explain the hang in terms of compiler optimisation, not CPU reordering.- Interview-style: "Code passes all tests on an x86 CI runner and deadlocks on ARM servers. Where do you look?" Hint: name the property x86 provides for free that ARM does not.
Atomic Instructions
Theory
Software alone cannot solve the critical-section problem efficiently, because the problem is fundamentally that read-modify-write sequences are interruptible. The hardware answer is an instruction that performs a read, a modification, and a write as one indivisible operation: no other core can observe or interleave with the intermediate state.
Atomicity is enforced at the cache-coherence level. To execute an atomic instruction, a core acquires exclusive ownership of the target cache line and holds it for the duration of the operation. Other cores requesting that line are made to wait. (Historically this was implemented by locking the entire memory bus, which is why x86 uses the lock instruction prefix; modern implementations use cache-line locking, which is far cheaper but not free.)
The common atomic primitives:
| Instruction | Operation | Typical use |
|---|---|---|
| Test-and-set | Set to 1, return the old value | Simple locks |
| Compare-and-swap | If value == expected, set to new; return success | General-purpose, lock-free structures |
| Fetch-and-add | Add and return the previous value | Counters, ticket locks |
| Exchange | Swap a register with memory | Simple locks, ownership transfer |
| Load-linked / store-conditional | Load, then store only if untouched since | ARM/RISC-V/POWER equivalent of CAS |
Two properties are worth internalising:
- Atomic instructions imply memory barriers on most architectures (or accept an explicit ordering argument, as in C++ and Rust). This is what makes them usable as synchronization rather than merely as indivisible arithmetic.
- They are not free. An uncontended atomic operation costs roughly 10-50 cycles versus about 1 for a normal store. Under contention it is much worse: the cache line ping-pongs between cores, and each transfer costs a coherence round trip. A hot atomic counter shared by 16 cores can be slower than a mutex, because every increment invalidates 15 caches.
The theoretical hierarchy is worth knowing: not all atomic operations are equally powerful. Test-and-set can build a lock but cannot implement wait-free consensus for more than two threads; compare-and-swap can do so for any number. This is Herlihy's consensus hierarchy, and it is why CAS is the primitive every modern lock-free algorithm is built on.
Example
What "atomic" means at the cache level
WITHOUT atomicity (three separate operations)
core0: load 10 -----+
core1: load 10 -----+---> both see 10, both store 11: one update lost
core0: store 11
core1: store 11
WITH an atomic instruction
core0: [ acquire exclusive ownership of the line ]
[ load 10, add 1, store 11 ] indivisible
[ release ]
core1: ... waits for the line ... then load 11, add 1, store 12
Result: 12. Correct.
Cost of contention: cache line ping-pong
1 thread : ~20 cycles per atomic op
2 threads : ~50 cycles (line bounces between two cores)
16 threads : ~500+ cycles (every op invalidates 15 other caches)
This is why "just use an atomic counter" can be SLOWER than a mutex
at high thread counts, and why sharded/per-CPU counters exist.
Consensus hierarchy (how many threads an operation can coordinate)
atomic read/write .................. 1
test-and-set, fetch-and-add ........ 2
compare-and-swap ................... infinite <- why CAS is universal
#include <stdatomic.h>
#include <stdio.h>
atomic_int counter = 0;
void increment_atomic(void) {
atomic_fetch_add(&counter, 1); /* ONE indivisible read-modify-write.
Compiles to `lock xadd` on x86. */
}
/* The same thing, spelled out, to show what the hardware guarantees. */
void increment_by_cas(void) {
int expected = atomic_load(&counter);
while (!atomic_compare_exchange_weak(&counter, &expected, expected + 1)) {
/* CAS failed: another thread changed `counter` between our load and
our attempt. `expected` was updated with the current value by the
call itself, so we simply retry with fresh information.
This retry loop is the shape of EVERY lock-free algorithm. */
}
}
int main(void) {
/* Relaxed ordering: atomic, but with NO barrier. Fine for a statistics
counter whose value is not used to order other memory accesses. */
atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
printf("%d\n", atomic_load(&counter));
return 0;
}
x86-64 assembly for the two forms
counter++ (NOT atomic) atomic_fetch_add(&counter, 1)
------------------------------- -----------------------------
mov eax, [counter] lock xadd [counter], eax
add eax, 1 ^^^^
mov [counter], eax the LOCK prefix makes the whole
^ interruptible between any two read-modify-write indivisible
Key takeaways
- Atomic instructions perform read-modify-write indivisibly by taking exclusive ownership of the cache line.
- On most architectures they also act as memory barriers, which is what makes them usable for synchronization.
- They cost 10-50 cycles uncontended and far more under contention, as the cache line bounces between cores.
- Compare-and-swap is universal in the consensus hierarchy, which is why lock-free algorithms are built on it.
🧪 Practice
- Benchmark 10 million increments using a plain
int, anatomic_int, and a mutex, at 1, 4, and 16 threads. Explain the crossover.- Explain when
memory_order_relaxedis safe, and give one example where using it is a bug.- Interview-style: "Why can an atomic counter be slower than a mutex under heavy contention?" Hint: think about what happens to the cache line on every single operation.
Test-and-Set
Theory
Test-and-set is the simplest useful atomic instruction: it writes true into a memory location and returns whatever was there before, indivisibly.
Its use as a lock follows immediately. A thread repeatedly executes test-and-set on a shared boolean. If the returned value is false, the lock was free and this thread has just claimed it — the write already happened, atomically, so no one else can have claimed it in between. If the returned value is true, someone else holds it, and the thread retries. Unlocking is a plain store of false.
The correctness argument is short and worth appreciating: exactly one thread can receive false from a location that transitions from false to true, because the transition happens once and the operation is indivisible.
Its limitations are equally clear:
- No bounded waiting. Every waiter races on each release, and nothing prevents the same unlucky thread from losing every time. It satisfies mutual exclusion and progress but not the third requirement of 5.1. A ticket lock or a queue-based lock fixes this by imposing FIFO order.
- Cache-line hammering. The naive loop performs an atomic write on every iteration, which invalidates the line in every other core's cache. Ten spinning threads generate continuous coherence traffic that slows the lock holder — so contention makes the critical section itself slower.
The standard mitigation is test-and-test-and-set (TTAS): spin on an ordinary read until the lock appears free, and only then attempt the atomic operation. Reads can be served from each core's own cache without invalidating anything, so waiting threads become nearly silent, and the expensive atomic is attempted only when it has a chance of succeeding. Adding exponential backoff between attempts reduces the thundering herd further.
Analogy: test-and-set is grabbing a door handle and being told whether it was already turned. TTAS is watching the handle from across the room and only walking over when it looks free.
Example
Test-and-set semantics (all of it, indivisibly)
bool test_and_set(bool *target) {
bool old = *target;
*target = true;
return old; // false means "it was free and is now MINE"
}
Two threads racing for a free lock
lock = false
A: test_and_set -> returns false, lock is now true -> A ENTERS
B: test_and_set -> returns true, lock stays true -> B SPINS
A: lock = false (release)
B: test_and_set -> returns false -> B ENTERS
TAS vs TTAS cache traffic with 8 spinning threads
TAS : every waiter issues an atomic WRITE every iteration
-> the line is invalidated in 7 caches, 8 times per loop
-> coherence storm; even the LOCK HOLDER runs slower
TTAS : waiters issue ordinary READS from their own cache
-> zero coherence traffic while the lock is held
-> one burst of atomics only when the lock is released
#include <stdatomic.h>
atomic_flag lock = ATOMIC_FLAG_INIT;
/* --- Naive test-and-set spinlock --- */
void tas_acquire(void) {
while (atomic_flag_test_and_set(&lock))
; /* an atomic WRITE every iteration:
hammers the cache line for all cores */
}
void tas_release(void) {
atomic_flag_clear(&lock);
}
/* --- Test-and-test-and-set: the version you should actually write --- */
atomic_bool lock2 = false;
void ttas_acquire(void) {
for (;;) {
while (atomic_load_explicit(&lock2, memory_order_relaxed))
cpu_relax(); /* spin on a plain READ:
served from the local cache,
generates no coherence traffic.
cpu_relax() = PAUSE on x86,
YIELD on ARM: hints to the core
that this is a spin loop */
if (!atomic_exchange_explicit(&lock2, true, memory_order_acquire))
return; /* only NOW pay for the atomic,
and only when it may succeed */
}
}
void ttas_release(void) {
atomic_store_explicit(&lock2, false, memory_order_release);
}
# Why test-and-set alone cannot guarantee bounded waiting.
#
# lock free -> threads A, B, C all attempt test_and_set
# whichever the hardware serves first wins; the others retry
# nothing records that A has been waiting longest
#
# A can lose to B and C indefinitely: mutual exclusion and progress
# hold, but A starves.
#
# The fix is to impose an order -- a ticket lock:
class TicketLock:
def __init__(self):
self.next_ticket = 0 # atomic fetch-and-add in real code
self.now_serving = 0
def acquire(self):
my = self.next_ticket # atomically take a number
self.next_ticket += 1
while self.now_serving != my: # wait for YOUR number: strict FIFO,
pass # so waiting is bounded by n-1
return my
def release(self):
self.now_serving += 1
Key takeaways
- Test-and-set writes
trueand returns the previous value atomically; receivingfalsemeans the lock was acquired. - It gives mutual exclusion and progress but not bounded waiting, so threads can starve.
- The naive spin loop performs an atomic write per iteration, flooding the interconnect and slowing the lock holder.
- Test-and-test-and-set spins on a plain read and attempts the atomic only when the lock looks free.
🧪 Practice
- Implement both TAS and TTAS spinlocks and benchmark them with 2, 8, and 32 threads. Explain the divergence.
- Show an execution in which a thread starves under a TAS lock, and explain how a ticket lock prevents it.
- Interview-style: "Why does adding the
PAUSEinstruction to a spin loop improve performance?" Hint: it tells the core about speculative memory-order violations and reduces power in the pipeline.
Compare-and-Swap
Theory
Compare-and-swap (CAS) is the most powerful of the common atomic primitives and the foundation of essentially all lock-free programming. It takes three arguments — a memory location, an expected value, and a new value — and atomically writes the new value only if the location still holds the expected one, reporting whether it succeeded.
The conditional nature is what makes it general. Test-and-set can only claim a boolean; CAS can attempt any state transition and detect interference. The standard usage is the CAS retry loop:
- Read the current value.
- Compute the desired new value from it.
- CAS: install the new value if nothing has changed.
- If the CAS failed, someone else modified it — start again with the fresh value.
This loop is the shape of every lock-free algorithm. It is optimistic: it assumes no conflict, does the work, and validates at the moment of commit. Under low contention it is faster than locking; under high contention threads burn CPU on retries, and a lock can win.
CAS provides lock-freedom, not wait-freedom: the system as a whole always makes progress (some thread's CAS always succeeds), but an individual thread can retry indefinitely. That distinction matters for real-time systems.
The characteristic hazard is the ABA problem. CAS checks that the value is unchanged, not that it was never changed. If a value goes A → B → A between a thread's read and its CAS, the CAS succeeds although the world has moved on. In a lock-free stack this can splice freed nodes back into the list. Three standard remedies: attach a monotonically increasing version counter to the pointer (double-width CAS), use hazard pointers or epoch-based reclamation to defer memory reuse, or rely on a garbage collector that never recycles a node while it is reachable.
RISC architectures (ARM, POWER, RISC-V) provide load-linked/store-conditional instead: LL reads and marks the address, SC stores only if nothing has touched it since. This is strictly stronger in one respect — it detects any write, so it is immune to ABA — at the cost of spurious failures from unrelated cache events.
Example
CAS semantics, indivisibly
bool compare_and_swap(int *addr, int expected, int new_value) {
if (*addr == expected) { *addr = new_value; return true; }
else { return false; }
}
The universal retry loop
do {
old = *addr; // 1. read the current state
new = f(old); // 2. compute the desired state
} while (!CAS(addr, old, new)); // 3. commit only if nothing changed
// otherwise retry with fresh data
The ABA problem
Thread 1: reads head -> node A stack: A -> B -> C
Thread 1: PREEMPTED, about to CAS(head, A, B)
Thread 2: pops A, pops B, frees B, pushes A back stack: A -> C
Thread 1: resumes. CAS(head, A, B) SUCCEEDS -- head is still A!
stack: B -> ??? B was FREED. Corruption.
Fix: version-tagged pointers
Thread 1: reads (head=A, version=17), CAS expects (A, 17)
Thread 2's operations bump the version to 19
Thread 1: CAS((A,17) -> ...) FAILS correctly, and retries.
#include <stdatomic.h>
/* --- The retry loop, in its most common form: atomic maximum --- */
void atomic_max(atomic_int *target, int value) {
int current = atomic_load(target);
while (value > current &&
!atomic_compare_exchange_weak(target, ¤t, value)) {
/* compare_exchange_weak updates `current` with the actual value on
failure, so the loop condition is re-evaluated with fresh data.
`weak` may fail spuriously on LL/SC machines, which is fine and
cheaper inside a loop that retries anyway. */
}
}
/* --- A lock-free stack push: no mutex anywhere --- */
struct node { int value; struct node *next; };
_Atomic(struct node *) head = NULL;
void push(int value) {
struct node *n = malloc(sizeof *n);
n->value = value;
n->next = atomic_load(&head); /* read current head */
while (!atomic_compare_exchange_weak(&head, &n->next, n)) {
/* Failure means another thread pushed or popped first.
`n->next` has been refreshed with the new head, so we simply
retry -- no lock was ever taken, and no thread can block another. */
}
}
import java.util.concurrent.atomic.AtomicStampedReference;
// The ABA fix in the standard library: a value plus a monotonic stamp.
class SafeStack<T> {
private final AtomicStampedReference<Node<T>> head =
new AtomicStampedReference<>(null, 0);
void push(T value) {
int[] stampHolder = new int[1];
Node<T> newNode = new Node<>(value, null);
Node<T> current;
int stamp;
do {
current = head.get(stampHolder); // read value AND stamp
stamp = stampHolder[0];
newNode.next = current;
} while (!head.compareAndSet(current, newNode, stamp, stamp + 1));
// ^^^^^ ^^^^^^^^^
// The stamp must ALSO match, so an A -> B -> A sequence is detected:
// the value returned to A, but the stamp advanced.
}
}
Key takeaways
- CAS atomically installs a new value only if the location still holds an expected one, reporting success.
- The read-compute-CAS-retry loop is the structural basis of every lock-free algorithm.
- CAS gives lock-freedom (the system progresses) but not wait-freedom (one thread may retry indefinitely).
- The ABA problem defeats naive CAS; version stamps, hazard pointers, or a garbage collector are the standard fixes.
🧪 Practice
- Implement a lock-free counter with a CAS retry loop and compare it with a mutex-protected counter at 2 and 16 threads.
- Construct a concrete ABA failure in a lock-free stack, then show how a version stamp prevents it.
- Interview-style: "Why is a CAS loop lock-free but not wait-free?" Hint: distinguish 'some thread always makes progress' from 'every thread makes progress'.
Spinlocks
Theory
A spinlock is a lock whose waiters busy-wait — they loop, repeatedly testing the lock, rather than sleeping. Building one requires only the atomic primitives above.
The trade-off against a blocking mutex is a straightforward cost comparison. Blocking involves two context switches (out and back), each costing roughly 1-5 microseconds plus cache pollution (Chapter 2). Spinning wastes CPU for the duration of the wait but avoids those switches entirely. Therefore:
Spin when the expected wait is shorter than the cost of two context switches; block when it is longer.
That single rule determines where spinlocks are appropriate:
| Use a spinlock when | Use a blocking mutex when |
|---|---|
| Critical sections are very short (tens to hundreds of ns) | Critical sections are long, or perform I/O |
| Multiple cores are available | The system may be single-core |
| You cannot sleep (interrupt handlers) | Sleeping is permitted |
| Contention is low | Contention is high |
Two rules are non-negotiable in kernel code and explain most spinlock bugs:
- Never sleep while holding a spinlock. Waiters are burning CPU waiting for you; if you block on I/O, they spin for milliseconds. Worse, on a single core the waiter can never be descheduled in favour of the holder, so the system deadlocks outright.
- Disable interrupts if the lock is taken in interrupt context. If a thread holds a spinlock and an interrupt handler on the same core tries to take it, the handler spins forever waiting for a thread that cannot resume until the handler returns. Linux's
spin_lock_irqsaveexists exactly for this.
Real implementations refine the basic loop considerably: TTAS to reduce cache traffic, a PAUSE/YIELD hint to the core, exponential backoff, and queue-based designs (MCS, CLH locks) where each waiter spins on its own cache line, eliminating coherence storms and providing FIFO fairness. Many systems use adaptive mutexes, which spin briefly and then block — capturing the best of both when the holder is running on another core.
Example
Spin or block? Compare the wait against the switch cost
critical section 50 ns -> SPIN (blocking costs ~4000 ns: 80x worse)
critical section 10 us -> either (roughly break-even)
critical section 10 ms -> BLOCK (spinning wastes 10 ms of a core)
The single-core deadlock
core0: thread A holds the spinlock, is preempted
core0: thread B tries to acquire it -> spins for its ENTIRE quantum
A cannot run because B is running. Pure waste, and on a
non-preemptive kernel, a permanent hang.
-> spinlocks only make sense on multiprocessors
The interrupt deadlock
thread holds spinlock L on core 0
-> interrupt fires on core 0
-> handler tries to take L
-> handler spins; the thread cannot resume until the handler returns
-> HARD LOCKUP. Fix: spin_lock_irqsave() disables local interrupts.
Queue locks: each waiter spins on its own cache line
simple spinlock: all waiters spin on ONE line -> coherence storm
MCS lock: A -> B -> C queue, each spinning on a private flag
the holder sets only its successor's flag: one transfer,
FIFO fairness, no storm
/* A production-shaped spinlock: TTAS + pause + release barrier. */
#include <stdatomic.h>
typedef struct { atomic_bool locked; } spinlock_t;
static inline void spin_lock(spinlock_t *l) {
for (;;) {
/* Fast path: try once. Uncontended acquisition is a single atomic. */
if (!atomic_exchange_explicit(&l->locked, true, memory_order_acquire))
return;
/* Slow path: spin on a READ so we do not invalidate other caches. */
while (atomic_load_explicit(&l->locked, memory_order_relaxed))
__builtin_ia32_pause(); /* PAUSE: reduces power, avoids a
memory-order violation penalty on
exiting the loop */
}
}
static inline void spin_unlock(spinlock_t *l) {
atomic_store_explicit(&l->locked, false, memory_order_release);
/* RELEASE: everything done in the critical section is visible to the
next thread that acquires this lock. */
}
/* Linux kernel idioms, and what each one guards against. */
spin_lock(&lock); /* plain: safe only if this lock is never
taken from interrupt context */
spin_unlock(&lock);
unsigned long flags;
spin_lock_irqsave(&lock, flags); /* saves and disables local interrupts:
required if an IRQ handler takes this
same lock -- prevents the hard lockup */
spin_unlock_irqrestore(&lock, flags);
/* FORBIDDEN while holding a spinlock: */
/* kmalloc(size, GFP_KERNEL) -- may sleep */
/* copy_to_user(...) -- may page-fault and sleep */
/* mutex_lock(...) -- may sleep */
Key takeaways
- A spinlock busy-waits instead of sleeping, trading wasted CPU for the avoided cost of two context switches.
- Spin when the expected wait is shorter than a context-switch pair; block otherwise.
- Never sleep while holding a spinlock, and disable interrupts if the lock is also taken in interrupt context.
- Production spinlocks use TTAS, pause hints, backoff, or per-waiter queue locks to avoid coherence storms.
🧪 Practice
- Measure the cost of a context switch on your machine, then compute the critical-section length at which spinning stops paying.
- Explain step by step why taking a spinlock without disabling interrupts can hard-lock a core.
- Interview-style: "Why do MCS locks scale better than simple spinlocks?" Hint: count how many caches are invalidated per lock handoff in each design.
<a id="53-synchronization-primitives"></a>
5.3 Synchronization Primitives
The hardware instructions of 5.2 are correct but awkward; this section covers the abstractions built on top of them that programmers actually use.
Mutex Locks
Theory
A mutex (mutual exclusion lock) is the simplest and most widely used primitive. It has two states — locked and unlocked — and two operations: acquire, which blocks until the lock is free and then takes it, and release, which frees it.
The essential difference from the spinlock of 5.2 is what a waiter does. A mutex blocks: the thread is moved to a wait queue associated with the lock, marked Blocked (Chapter 2), and the scheduler runs someone else. On release, a waiter is moved back to Ready. No CPU is consumed while waiting.
Modern implementations are hybrids and worth understanding, because they explain surprising performance results. Linux's futex ("fast userspace mutex") takes the uncontended path entirely in user space with a single CAS — no system call at all — and only enters the kernel when there is actual contention and someone must be put to sleep. Since most lock acquisitions are uncontended, this makes the common case cost roughly 20 nanoseconds instead of a microsecond. Many implementations additionally spin briefly before blocking (an adaptive mutex), which pays off when the holder is running on another core and will release shortly.
Three properties define correct mutex use:
- Ownership. A mutex is owned by the thread that locked it, and only that thread may unlock it. This is what allows deadlock detection, priority inheritance (5.5), and error checking — and it is the main semantic difference from a binary semaphore.
- Release must be guaranteed. A lock that is not released on an early return, an exception, or a
gotodeadlocks the program permanently. Every language provides a scope-based mechanism for this: RAII (std::lock_guard) in C++,within Python,deferin Go,try/finallyin Java. Manual lock/unlock pairs are a defect waiting to happen. - Non-recursive by default. Locking a mutex you already hold deadlocks immediately, unless it is explicitly a recursive mutex. Recursive mutexes are usually a sign that the ownership structure of the code is unclear.
Analogy: a mutex is a key to a single-occupancy room, where waiters sit in the corridor asleep rather than rattling the handle, and where only the person who took the key may return it.
Example
Mutex state machine and the wait queue
UNLOCKED --acquire--> LOCKED (owner: T1)
^ |
| | T2 acquires: BLOCKS
| v
| wait queue: [T2][T3]
| |
+---release----------+ one waiter is made READY
Fast path vs slow path (futex)
uncontended: CAS on a user-space word ~20 ns, NO system call
contended: CAS fails -> futex(FUTEX_WAIT) ~1-2 us, kernel involved
release -> futex(FUTEX_WAKE)
This is why lock cost varies by two orders of magnitude with contention.
Spinlock vs mutex
| spinlock | mutex
---------------+---------------------+-------------------------
waiter does | burns CPU | sleeps, CPU freed
wait cost | proportional to wait| ~2 context switches
ownership | usually none | owned; only owner unlocks
may sleep in CS| NO | yes
use for | very short CS | anything longer
#include <mutex>
#include <stdexcept>
class Account {
mutable std::mutex m_; // mutable: const methods still need to lock
double balance_ = 0;
public:
void transfer_out(double amount) {
std::lock_guard<std::mutex> guard(m_); // RAII: acquires here
if (balance_ < amount)
throw std::runtime_error("insufficient funds");
// ^ The mutex is STILL released: guard's destructor runs during
// stack unwinding. A manual unlock() after this line would
// never execute, deadlocking the program permanently.
balance_ -= amount;
} // released here, always
};
import threading
lock = threading.Lock()
# CORRECT: the context manager releases on every exit path.
def transfer(accounts, src, dst, amount):
with lock:
if accounts[src] < amount:
return False # `with` still releases the lock
accounts[src] -= amount
accounts[dst] += amount
return True
# BROKEN: an early return or exception leaks the lock forever.
def transfer_bad(accounts, src, dst, amount):
lock.acquire()
if accounts[src] < amount:
return False # LOCK NEVER RELEASED -> permanent deadlock
accounts[src] -= amount
lock.release()
# Deadlocks immediately: a plain Lock is not recursive.
def recursive_bad():
with lock:
with lock: # blocks waiting for a lock this thread holds
pass
# Use threading.RLock() if re-entry is genuinely required -- but prefer
# restructuring so it is not.
Key takeaways
- A mutex blocks waiters on a wait queue instead of spinning, freeing the CPU for other work.
- Implementations take the uncontended path in user space with a single atomic, entering the kernel only under contention.
- Mutexes are owned: only the locking thread may unlock, which enables error checking and priority inheritance.
- Always release with a scope-based mechanism, and treat the need for a recursive mutex as a design smell.
🧪 Practice
- Write a function that returns early while holding a manually acquired mutex, demonstrate the deadlock, then fix it with RAII or
with.- Benchmark an uncontended mutex and one contended by 8 threads. Explain the difference using the futex fast/slow paths.
- Interview-style: "When would you choose a spinlock over a mutex in kernel code?" Hint: consider the length of the critical section and whether the code may sleep.
Semaphores
Theory
A semaphore, introduced by Dijkstra in 1965, generalises the mutex. It is an integer counter with two atomic operations:
wait(P, from proberen): decrement the counter; if it becomes negative, block the calling thread.signal(V, from verhogen): increment the counter; if any thread is blocked, wake one.
The counter represents available units of a resource. This makes semaphores strictly more expressive than mutexes, and they are used in two distinct ways that are worth separating clearly:
- A counting semaphore initialised to N controls access to N interchangeable resources — a connection pool, a buffer of N slots, a limit of N concurrent downloads. This is the use case a mutex cannot express at all.
- A binary semaphore initialised to 1 behaves like a lock. It is not a mutex, however: it has no ownership, so any thread may signal it, and it lacks the error checking and priority inheritance that ownership makes possible.
That absence of ownership is not merely a limitation — it is what enables the second major use: signalling between threads. A semaphore initialised to 0 lets thread A block until thread B signals, establishing an ordering constraint. A mutex cannot do this, because the thread that would need to unlock is not the one that locked.
| Use | Initial value | Pattern |
|---|---|---|
| Mutual exclusion | 1 | Same thread waits and signals |
| Resource counting | N | Same thread waits and signals |
| Signalling / ordering | 0 | One thread waits, a different thread signals |
The danger is that semaphores are unstructured. Nothing associates a wait with its signal, so a missing signal deadlocks silently, an extra signal corrupts the count, and reversed order in two threads deadlocks. There is no compiler help and no scope-based idiom. This is precisely why monitors (below) were invented, and why modern code prefers mutexes plus condition variables for exclusion and reserves semaphores for genuine counting and signalling.
Analogy: a semaphore is a bowl of N parking tokens. Take one to park (blocking if the bowl is empty), return it on leaving. Nothing records who took which token, so anyone can return one — powerful, and easy to get wrong.
Example
Semaphore semantics
wait(S): S.count--; if (S.count < 0) { block(this thread) }
signal(S): S.count++; if (S.count <= 0) { wake one blocked thread }
A negative count tells you how many threads are waiting.
Counting semaphore: 3 database connections, 5 threads
count=3 T1 wait -> 2, proceeds
T2 wait -> 1, proceeds
T3 wait -> 0, proceeds
T4 wait -> -1, BLOCKS (one waiter)
T5 wait -> -2, BLOCKS (two waiters)
T1 signal -> -1, wakes T4
T2 signal -> 0, wakes T5
Signalling: a semaphore initialised to 0 orders two threads
Thread A Thread B
wait(done) <-blocks
do_work()
signal(done)
use_result() <-proceeds
A mutex CANNOT express this: B never locked anything.
import threading, time
# --- Use 1: counting a limited resource ---
db_pool = threading.Semaphore(3) # exactly 3 connections exist
def query(n):
with db_pool: # wait(): blocks if all 3 are in use
time.sleep(0.1) # hold a connection
print(f"query {n} done")
# signal() happens on exit; at most 3 queries run concurrently
# --- Use 2: signalling an ordering between different threads ---
data_ready = threading.Semaphore(0) # starts at 0: waiters block immediately
result = None
def producer():
global result
result = expensive_computation()
data_ready.release() # signal: a DIFFERENT thread than the
# one that will wait
def consumer():
data_ready.acquire() # blocks until the producer signals
print(result) # guaranteed to be computed
# --- The unstructured hazard ---
sem = threading.Semaphore(1)
def buggy():
sem.acquire()
if error_condition():
return # MISSING RELEASE: the count is now 0 forever.
sem.release() # No language mechanism catches this.
#include <semaphore.h>
sem_t slots; /* how many free buffer slots exist */
sem_t items; /* how many filled items exist */
sem_init(&slots, 0, 10); /* 0 = shared between threads (1 = between
processes, via shared memory); 10 slots */
sem_init(&items, 0, 0); /* nothing produced yet */
/* Two counting semaphores used together give bounded-buffer flow control:
this is the producer-consumer solution developed in 5.4. */
Key takeaways
- A semaphore is a counter with atomic
wait(decrement, block if negative) andsignal(increment, wake one). - A counting semaphore limits access to N interchangeable resources, which a mutex cannot express.
- Having no ownership lets one thread signal what another waits on, enabling ordering between threads.
- Semaphores are unstructured: a missing or misplaced signal causes silent deadlock with no compiler assistance.
🧪 Practice
- Use a counting semaphore to limit a downloader to 4 concurrent connections, and verify the limit holds under 50 tasks.
- Explain why a binary semaphore is not equivalent to a mutex. Give a specific bug that ownership would have caught.
- Interview-style: "Implement a barrier for N threads using only semaphores." Hint: you need a counter protected by one semaphore and a second one to release the group.
Condition Variables
Theory
Mutexes solve exclusion but not waiting for a condition. A consumer that must wait until a queue is non-empty cannot simply hold the mutex and loop — no producer could ever acquire the lock to add an item. Releasing the lock and polling in a loop works but burns CPU and is racy.
A condition variable solves this precisely. It supports three operations, always used in conjunction with a mutex:
wait(mutex)— atomically releases the mutex and blocks the thread. When it returns, the mutex has been reacquired. The atomicity of the release-and-block is the crux: without it, a signal arriving in between would be missed forever.signal— wakes one waiting thread.broadcast— wakes all waiting threads.
Three rules govern correct use, and violating any of them is a classic bug:
- Always wait inside a
whileloop, never anif. Three separate reasons make this mandatory: spurious wakeups are permitted by POSIX and do occur; stolen wakeups happen when another thread acquires the mutex between the signal and the waiter's resumption and consumes the condition; and broadcast wakes everyone, though the condition may only be satisfiable for one. Re-checking the predicate on waking is the only safe discipline. - Hold the mutex when calling wait. The predicate is shared state; testing it without the lock is itself a race.
- Prefer
broadcastwhen in doubt.signalis more efficient but is only correct when any single waiter can make progress. With multiple distinct predicates on one condition variable,signalcan wake the wrong thread and stall the system.
The pairing of a mutex with condition variables is the standard general-purpose tool, and it is more expressive than semaphores because the condition can be an arbitrary predicate over shared state rather than a single counter.
Analogy: a condition variable is a waiting room with a bell. You put down the key to the room (release the mutex) and sleep. When someone rings the bell you wake, pick up the key again, and check whether what you were waiting for is actually there — because someone else may have taken it first.
Example
Why wait() must release the mutex ATOMICALLY
BROKEN (if release and block were separate):
consumer: holds mutex, sees queue empty
consumer: releases mutex
---- producer adds an item and SIGNALS here: nobody is waiting yet ----
consumer: blocks
-> the signal was missed; the consumer sleeps forever with data available
CORRECT: wait() performs release-and-block indivisibly, so no signal
can slip into the gap.
Why `while`, not `if`
T1 waiting on "queue not empty"
producer adds ONE item, signals
T1 wakes and must reacquire the mutex ...
... but T2 (not waiting; just called pop()) grabs the mutex first
and takes the item.
T1 finally gets the mutex: the queue is empty AGAIN.
With `if` -> T1 proceeds and dereferences an empty queue. CRASH.
With `while` -> T1 re-checks, sees empty, and waits again. Correct.
The canonical shape
lock(m);
while (!predicate) <- ALWAYS a loop
cond_wait(cv, m); <- releases m, blocks, reacquires m
/* predicate is true AND we hold the mutex */
do_work();
unlock(m);
#include <pthread.h>
#define CAPACITY 10
int buffer[CAPACITY], count = 0, in = 0, out = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
/* TWO condition variables, one per predicate: signalling `not_empty` then
wakes only consumers, never a producer that cannot proceed. */
void produce(int item) {
pthread_mutex_lock(&mutex);
while (count == CAPACITY) /* WHILE, never IF */
pthread_cond_wait(¬_full, &mutex); /* releases mutex, blocks,
reacquires on wake */
buffer[in] = item;
in = (in + 1) % CAPACITY;
count++;
pthread_cond_signal(¬_empty); /* a consumer can now proceed */
pthread_mutex_unlock(&mutex);
}
int consume(void) {
pthread_mutex_lock(&mutex);
while (count == 0)
pthread_cond_wait(¬_empty, &mutex);
int item = buffer[out];
out = (out + 1) % CAPACITY;
count--;
pthread_cond_signal(¬_full); /* a producer can now proceed */
pthread_mutex_unlock(&mutex);
return item;
}
import threading, collections
class BoundedQueue:
def __init__(self, capacity):
self._q = collections.deque()
self._capacity = capacity
self._lock = threading.Lock()
self._not_full = threading.Condition(self._lock) # share ONE lock
self._not_empty = threading.Condition(self._lock)
def put(self, item):
with self._not_full:
while len(self._q) >= self._capacity: # loop, not `if`
self._not_full.wait() # releases the lock
self._q.append(item)
self._not_empty.notify() # wake one consumer
def get(self):
with self._not_empty:
while not self._q:
self._not_empty.wait()
item = self._q.popleft()
self._not_full.notify()
return item
def close(self):
with self._lock:
self._closed = True
self._not_empty.notify_all() # BROADCAST: every waiter must
self._not_full.notify_all() # re-check and exit
Key takeaways
- A condition variable lets a thread wait for an arbitrary predicate while holding a mutex, atomically releasing it.
- The atomic release-and-block is essential; otherwise a signal can arrive in the gap and be lost forever.
- Always re-check the predicate in a
whileloop: spurious wakeups, stolen wakeups, and broadcasts all require it. - Use one condition variable per distinct predicate, and prefer broadcast when several different conditions share one.
🧪 Practice
- Replace the
whilewith anifin the bounded queue and construct an execution that corrupts it or crashes.- Implement a one-shot latch: N worker threads wait until a coordinator signals that setup is complete.
- Interview-style: "What is a spurious wakeup and why does the standard permit it?" Hint: consider what implementations gain by not having to suppress them.
Monitors
Theory
Semaphores and raw mutexes are error-prone for a structural reason: the synchronization is separate from the data it protects. Nothing in the language connects a lock to the variables it guards, so a programmer can forget to lock, lock the wrong mutex, or fail to unlock on an error path.
A monitor (Hoare and Brinch Hansen, 1974) is a language construct that fuses them. It is an abstract data type in which:
- All shared data is private to the monitor — unreachable from outside.
- All procedures are automatically mutually exclusive: at most one thread executes inside the monitor at a time, enforced by the compiler or runtime rather than by programmer discipline.
- Condition variables inside the monitor allow threads to wait for predicates, with the monitor's lock released while waiting.
The gain is that correctness moves from convention to construction. You cannot forget to lock, because entry is the lock. You cannot forget to unlock, because exit is the unlock. The exclusion boundary and the data boundary are the same boundary.
The design question a monitor must answer is what happens when a thread signals a condition while inside the monitor — two threads would then be runnable inside, violating exclusion. There are two classic answers:
| Hoare semantics (signal-and-wait) | Mesa semantics (signal-and-continue) | |
|---|---|---|
| On signal | Signaller yields the monitor immediately to the waiter | Signaller continues; the waiter becomes merely eligible |
| Waiter can assume | The predicate is true on waking (if suffices) | Nothing — must re-check (while required) |
| Cost | Two extra context switches per signal | None |
| Used by | Textbook theory | Java, C#, Python, pthreads — every real system |
Mesa semantics won on efficiency, and that choice is exactly why the while loop of the previous topic is mandatory everywhere in practice.
Java implements monitors directly: every object has an intrinsic lock, synchronized methods acquire it, and wait/notify/notifyAll are the condition operations. ConcurrentHashMap, BlockingQueue, and Python's threading.Condition-based classes are all monitors in this sense.
Analogy: a monitor is a building with a turnstile admitting one person at a time, where the valuables are only reachable inside. Compare a mutex, which is a padlock you must remember to attach to the right cabinet and to close behind you.
Example
Monitor structure
+--------------------------------------------+
| monitor BoundedBuffer |
| |
| PRIVATE data: buffer[], count, in, out | <- unreachable outside
| |
| condition not_full, not_empty |
| |
| procedure put(item) \ |
| procedure get() > automatically | <- at most ONE thread
| procedure size() / mutually | inside at a time
| exclusive |
+--------------------------------------------+
^
| entry queue: threads waiting to get IN
[T2][T3]
Hoare vs Mesa, on signal
HOARE: signaller BLOCKS, waiter runs immediately with the predicate true
|-- signaller --|>>> waiter runs >>>|-- signaller resumes --|
waiter may use `if`. Costs two extra switches per signal.
MESA: signaller CONTINUES; waiter joins the entry queue
|------ signaller continues to end of procedure ------|
then waiter competes
By the time the waiter runs, the predicate may be false again
-> `while` is MANDATORY. This is what every real system does.
// Java: `synchronized` IS a monitor. The lock is the object itself.
public class BoundedBuffer<T> {
private final Object[] items; // private: unreachable from outside
private int count = 0, in = 0, out = 0;
public BoundedBuffer(int capacity) { items = new Object[capacity]; }
// `synchronized` = acquire this object's intrinsic lock on entry,
// release on exit, INCLUDING on an exception. Cannot be forgotten.
public synchronized void put(T item) throws InterruptedException {
while (count == items.length) // MESA semantics -> while, not if
wait(); // releases the monitor lock, blocks
items[in] = item;
in = (in + 1) % items.length;
count++;
notifyAll(); // wake all: producers and consumers
} // share one condition here
@SuppressWarnings("unchecked")
public synchronized T get() throws InterruptedException {
while (count == 0)
wait();
T item = (T) items[out];
out = (out + 1) % items.length;
count--;
notifyAll();
return item;
}
public synchronized int size() { return count; } // even reads are inside
}
import threading
class Monitor:
"""Python has no monitor keyword, so the pattern is built explicitly:
private data + one lock + conditions, all encapsulated in the class."""
def __init__(self, capacity):
self.__items = [] # name-mangled: effectively private
self.__capacity = capacity
self.__lock = threading.RLock()
self.__not_full = threading.Condition(self.__lock)
self.__not_empty = threading.Condition(self.__lock)
def put(self, item):
with self.__not_full: # entry = acquire
while len(self.__items) >= self.__capacity:
self.__not_full.wait()
self.__items.append(item)
self.__not_empty.notify()
# exit = release, guaranteed
Key takeaways
- A monitor bundles private data, an implicit lock, and condition variables into one language construct.
- Mutual exclusion is enforced by construction, so locking cannot be forgotten or misapplied.
- Hoare semantics hand the monitor to the waiter on signal; Mesa semantics let the signaller continue.
- Every real system uses Mesa semantics, which is exactly why predicates must be rechecked in a
whileloop.
🧪 Practice
- Implement a bounded buffer as a Java monitor, then rewrite it with explicit
ReentrantLockandCondition. Compare the failure modes.- Explain why
notifyAllis safer thannotifywhen producers and consumers share one condition, and construct the stall thatnotifycan cause.- Interview-style: "Why do monitors reduce concurrency bugs compared with raw mutexes?" Hint: think about what a programmer can no longer forget to do.
Readers-Writers Locks
Theory
A plain mutex serialises everything, but that is stronger than many workloads require. Reading shared data does not modify it, so any number of readers may proceed simultaneously without any race. Only writers need exclusivity.
A readers-writers lock (shared/exclusive lock) exploits this with two acquisition modes:
- Shared (read) mode: any number of threads may hold it concurrently.
- Exclusive (write) mode: only one thread may hold it, and no readers may hold it at the same time.
The compatibility rule is simply: readers exclude writers, writers exclude everyone, readers do not exclude each other.
The benefit is large only for read-heavy workloads. A configuration table read thousands of times per second and written once an hour is an ideal candidate. But the lock itself is more complex than a mutex — it must track a reader count and a writer flag atomically — so acquisition costs more. For write-heavy or balanced workloads, a plain mutex is usually faster, and this is a common misapplication.
The design decision is the fairness policy, and it determines which side starves:
| Policy | Behaviour | Starves |
|---|---|---|
| Reader-preferring | A new reader joins even if a writer is waiting | Writers, under continuous read load |
| Writer-preferring | A waiting writer blocks new readers | Readers, under continuous write load |
| Fair (FIFO) | Requests are served in arrival order | Neither |
Reader-preferring gives maximum read throughput and is the classic textbook version, but writer starvation is a real production hazard: a configuration update that never lands because reads never stop. Most production implementations are writer-preferring or fair for this reason.
Modern alternatives often beat readers-writers locks outright. RCU (read-copy-update, 5.5) makes readers entirely lock-free. Seqlocks let readers proceed optimistically and retry if a write occurred. Copy-on-write replaces an immutable snapshot atomically, so readers need no synchronization at all.
Analogy: a library reading room. Any number of people may read a reference book simultaneously; the librarian who needs to update it must wait until the room is empty and then keep everyone out while writing.
Example
Compatibility matrix
| reader wants in | writer wants in
-----------------+-----------------+----------------
readers active | ALLOW | BLOCK
writer active | BLOCK | BLOCK
nothing active | ALLOW | ALLOW
Concurrency gained on a read-heavy workload
mutex: R1 | R2 | R3 | R4 | W1 | strictly serial
rwlock: R1 R2 R3 R4 (concurrent) | W1 | 4x the read throughput
Writer starvation under a reader-preferring policy
time ->
R1 [========]
R2 [========]
R3 [========]
R4 [========] readers keep overlapping
W1 waiting.............................. forever
^ a new reader is admitted every time, so the count never hits zero
Rule of thumb
reads >> writes (say 100:1) -> rwlock wins
balanced or write-heavy -> plain mutex is faster (less bookkeeping)
#include <pthread.h>
pthread_rwlock_t lock = PTHREAD_RWLOCK_INITIALIZER;
struct config shared_config;
/* Many threads may execute this concurrently. */
const char *lookup(const char *key) {
pthread_rwlock_rdlock(&lock); /* SHARED: other readers welcome */
const char *value = config_find(&shared_config, key);
pthread_rwlock_unlock(&lock);
return value;
}
/* At most one, and only when no reader holds the lock. */
void reload(const char *path) {
struct config fresh = parse_file(path); /* expensive work OUTSIDE the lock */
pthread_rwlock_wrlock(&lock); /* EXCLUSIVE: blocks everyone */
shared_config = fresh; /* keep the critical section tiny */
pthread_rwlock_unlock(&lock);
}
import threading
class RWLock:
"""Writer-preferring: a waiting writer blocks NEW readers, so writers
cannot starve under continuous read load."""
def __init__(self):
self._lock = threading.Condition(threading.Lock())
self._readers = 0
self._writers_waiting = 0
self._writer_active = False
def acquire_read(self):
with self._lock:
# Yield to waiting writers: this single clause is the entire
# difference between writer-preferring and reader-preferring.
while self._writer_active or self._writers_waiting > 0:
self._lock.wait()
self._readers += 1
def release_read(self):
with self._lock:
self._readers -= 1
if self._readers == 0:
self._lock.notify_all() # the last reader out wakes writers
def acquire_write(self):
with self._lock:
self._writers_waiting += 1
while self._writer_active or self._readers > 0:
self._lock.wait()
self._writers_waiting -= 1
self._writer_active = True
def release_write(self):
with self._lock:
self._writer_active = False
self._lock.notify_all()
Key takeaways
- Readers-writers locks allow concurrent readers but give writers exclusive access.
- They pay off only for read-heavy workloads; for balanced or write-heavy ones a plain mutex is usually faster.
- The fairness policy determines which side starves: reader-preferring starves writers, writer-preferring starves readers.
- RCU, seqlocks, and copy-on-write often outperform readers-writers locks by removing reader synchronization entirely.
🧪 Practice
- Benchmark a mutex against a readers-writers lock at read:write ratios of 1:1, 10:1, and 1000:1. Find the crossover point.
- Demonstrate writer starvation with a reader-preferring lock and a continuous stream of readers.
- Interview-style: "Your service uses a readers-writers lock and is slower than with a mutex. What would you check?" Hint: measure the actual read:write ratio and the cost of the lock's own bookkeeping.
Barriers
Theory
The primitives so far protect data. A barrier does something different: it synchronises time. It is a rendezvous point where N threads must all arrive before any is allowed to continue.
The need arises whenever a computation proceeds in phases and phase k+1 depends on every thread finishing phase k. Iterative simulations, matrix algorithms, parallel sorts, and graph algorithms all have this shape: each thread updates its portion of a grid, and no thread may start the next iteration until all updates are complete, or it would read a mix of old and new values.
The operation is a single call: barrier.wait() blocks until N threads have called it, then releases them all.
Three implementation concerns matter:
- Reusability. A barrier used once per iteration must reset correctly. The classic bug is a fast thread racing round the loop and entering the next barrier before slow threads have left the previous one. The standard fix is a sense-reversing barrier, where each generation flips a shared boolean that threads compare against a private copy — so an early arrival at generation k+1 cannot be mistaken for a straggler from generation k.
- Cost. A barrier is only as fast as its slowest participant: every thread pays the maximum. Load imbalance is therefore amplified — a barrier in a loop turns a 10% imbalance into a 10% slowdown for every thread on every iteration. Reducing barrier count and balancing work matters more than optimising the barrier itself.
- Scalability. A single shared counter becomes a contention point at high thread counts, so large systems use tree barriers (log n depth) or hardware-assisted barriers.
Related constructs solve nearby problems: a latch (Java's CountDownLatch) is a one-shot barrier that is not reusable; a phaser allows the participant count to change dynamically; and joining all threads is a barrier that also terminates them.
Analogy: a group hike where everyone regroups at each junction. Nobody proceeds until the last person arrives, so the group moves at the pace of its slowest member — which is exactly the cost model.
Example
A barrier across three threads
T1: [== phase 1 ==]--------wait--------|[== phase 2 ==]
T2: [==== phase 1 ====]----wait--------|[== phase 2 ==]
T3: [======== phase 1 ========]--------|[== phase 2 ==]
^
all three released together
Every thread pays the cost of the SLOWEST. T1 and T2 idle while T3 works.
Why a naive reusable barrier breaks
count = 0
arrive: count++; if (count == N) { count = 0; release_all(); }
else wait_for_release();
T1 is released, loops around, and calls arrive() AGAIN
-> count becomes 1 before T2 and T3 have even woken from generation k
-> the barrier is corrupted across generations
Sense reversal fixes it
shared: sense = false
each thread: local_sense = !local_sense // flip my private copy
if (last to arrive) { count = N; sense = local_sense; }
else while (sense != local_sense) ; // wait for THIS generation
An early arrival at generation k+1 has already flipped, so it cannot be
confused with a straggler from generation k.
#include <pthread.h>
pthread_barrier_t barrier;
#define THREADS 4
double grid[N][N], next[N][N];
void *simulate(void *arg) {
int id = *(int *)arg;
for (int iteration = 0; iteration < 1000; iteration++) {
compute_my_rows(id, grid, next); /* phase: read grid, write next */
pthread_barrier_wait(&barrier); /* BARRIER 1: everyone has
finished writing `next` */
if (id == 0)
swap_buffers(&grid, &next); /* only one thread may swap */
pthread_barrier_wait(&barrier); /* BARRIER 2: everyone sees the
swap before reading again.
Omitting this is a classic bug:
fast threads would read `grid`
mid-swap. */
}
return NULL;
}
int main(void) {
pthread_barrier_init(&barrier, NULL, THREADS); /* N participants */
/* ... create THREADS threads running simulate ... */
pthread_barrier_destroy(&barrier);
return 0;
}
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.CountDownLatch;
// CyclicBarrier: reusable, with an optional action run once per generation
// by the last thread to arrive -- neatly replacing the "if (id == 0)" idiom.
CyclicBarrier barrier = new CyclicBarrier(4, () -> {
swapBuffers(); // runs once, after all 4 arrive,
}); // before any is released
// CountDownLatch: ONE-SHOT. Cannot be reset; use for start/stop signals.
CountDownLatch ready = new CountDownLatch(4);
// workers: ready.countDown(); coordinator: ready.await();
Key takeaways
- A barrier blocks every participant until all N have arrived, then releases them together.
- It is used for phase-synchronous computations where the next phase depends on all of the previous one.
- Reusable barriers need sense reversal so a fast thread cannot corrupt the next generation.
- Every thread pays the cost of the slowest, so barriers amplify load imbalance; latches and phasers cover related cases.
🧪 Practice
- Implement a reusable barrier with a mutex and condition variable, then demonstrate the generation bug without sense reversal.
- Write a phase-synchronous heat-diffusion simulation with four threads. Remove the second barrier and describe the corruption.
- Interview-style: "You add a barrier per iteration and parallel speed-up drops from 7x to 2x on 8 cores. Why?" Hint: think about what determines the duration of every single iteration.
<a id="54-classic-problems"></a>
5.4 Classic Problems
These four problems are the standard test suite for synchronization mechanisms: each isolates a distinct difficulty, and any new primitive is judged by how cleanly it expresses their solutions.
Producer-Consumer Problem
Theory
The producer-consumer (bounded buffer) problem is the most practically important of the four, because it is the shape of nearly every real concurrent system: a work queue, a network receive path, a logging pipeline, a video decoder feeding a renderer.
The setup: one or more producers generate items and place them in a fixed-size buffer; one or more consumers remove and process them. Three requirements must hold simultaneously:
- Mutual exclusion — producers and consumers both modify the buffer's indices and count, so those updates must not interleave.
- A producer must block when the buffer is full, rather than overwriting or growing without bound.
- A consumer must block when the buffer is empty, rather than spinning or reading garbage.
The blocking requirements are what make it more than a mutex exercise, and the bounded buffer is the point: an unbounded queue converts a temporary imbalance into unbounded memory growth. A bounded buffer provides backpressure — a fast producer is forced to slow to the consumer's rate, which is a system-design property, not merely a synchronization detail.
The classic solution uses three semaphores, and the reasoning is worth following:
empty, initialised to N: counts free slots. A producer waits on it.full, initialised to 0: counts filled slots. A consumer waits on it.mutex, initialised to 1: protects the buffer structure.
The counting semaphores handle the blocking conditions and the binary one handles exclusion. The order of the waits is critical: a producer must wait(empty) before wait(mutex). Reversing them deadlocks — a producer would hold the mutex while blocking on a full buffer, so no consumer could ever acquire the mutex to free a slot. This is the single most instructive bug in the chapter.
Modern code uses a mutex plus two condition variables (as in 5.3) or a library queue (BlockingQueue, queue.Queue, Go channels), all of which implement exactly this.
Example
Bounded buffer, capacity 5
producers ---> [ A ][ B ][ C ][ ][ ] ---> consumers
^ ^
out in
count = 3, empty = 2, full = 3
full -> producers block (backpressure: the fast side is throttled)
empty -> consumers block
THE DEADLOCK: wrong order of waits
Producer: wait(mutex) <- takes the mutex FIRST
wait(empty) <- buffer is full: BLOCKS while HOLDING mutex
Consumer: wait(full) <- ok, an item exists
wait(mutex) <- BLOCKS: the producer holds it forever
Nobody can proceed. Correct order:
Producer: wait(empty) <- block on the CONDITION first, holding nothing
wait(mutex) <- only then take the lock
... insert ...
signal(mutex)
signal(full)
Rule: acquire the counting semaphore BEFORE the mutex, and release in
the reverse order.
#include <semaphore.h>
#include <pthread.h>
#define N 10
int buffer[N], in = 0, out = 0;
sem_t empty; /* free slots: init N */
sem_t full; /* filled slots: init 0 */
sem_t mutex; /* exclusion: init 1 */
void producer(int item) {
sem_wait(&empty); /* 1. block if full -- holding NOTHING */
sem_wait(&mutex); /* 2. only now take the lock */
buffer[in] = item; /* critical section: short */
in = (in + 1) % N;
sem_post(&mutex); /* 3. release in REVERSE order */
sem_post(&full); /* 4. announce an item is available */
}
int consumer(void) {
sem_wait(&full); /* block if empty */
sem_wait(&mutex);
int item = buffer[out];
out = (out + 1) % N;
sem_post(&mutex);
sem_post(&empty); /* a slot is now free: may wake a producer */
return item;
}
import queue, threading, time
# In practice, use the library: queue.Queue IS the bounded-buffer solution.
work = queue.Queue(maxsize=10) # bounded -> backpressure
SENTINEL = object()
def producer():
for i in range(100):
work.put(i) # BLOCKS when full: the producer is
# throttled to the consumer's rate
work.put(SENTINEL) # signal end of stream
def consumer():
while True:
item = work.get() # BLOCKS when empty
if item is SENTINEL:
work.put(SENTINEL) # re-post so other consumers also stop
break
process(item)
work.task_done()
# Setting maxsize=0 makes the queue UNBOUNDED: a fast producer then grows
# it until memory is exhausted. The bound is a feature, not a limitation.
Key takeaways
- Producer-consumer requires mutual exclusion plus blocking on both the full and empty conditions.
- The classic solution uses two counting semaphores (
empty,full) and one binary semaphore for exclusion. - Waiting on the mutex before the counting semaphore deadlocks; always block on the condition first.
- A bounded buffer provides backpressure, which is why unbounded queues are a memory-exhaustion hazard.
🧪 Practice
- Implement the bounded buffer with a mutex and two condition variables instead of semaphores, and test with 3 producers and 2 consumers.
- Swap the two
sem_waitcalls in the producer, run it, and explain the deadlock you observe.- Interview-style: "Why would you choose a bounded queue over an unbounded one in a service?" Hint: consider what happens when the consumer slows down for ten minutes.
Readers-Writers Problem
Theory
The readers-writers problem asks how to coordinate threads that only read shared data with those that modify it — the problem the readers-writers lock of 5.3 solves. Studying it as a problem rather than a primitive makes the fairness trade-off explicit, because there is no single correct answer: there are several formulations, and each starves someone.
The first readers-writers problem (reader-priority). No reader waits unless a writer already holds the lock. This maximises read concurrency and is the simplest to implement — but writers can starve indefinitely: as long as at least one reader is always active, the reader count never reaches zero and a waiting writer never proceeds.
The second readers-writers problem (writer-priority). Once a writer is waiting, no new reader may begin. Writers get timely access; readers can now starve under a continuous stream of writes.
The third formulation (fair / no starvation). Requests are served in arrival order, typically by having both readers and writers queue on a common turnstile semaphore. Neither side starves, at some cost in read throughput.
The reader-priority solution is the one worth being able to write from memory, because its structure recurs:
- A
read_countvariable, itself protected by amutex. - A
rw_mutexheld by writers exclusively, and acquired by the first reader and released by the last reader.
That last idea — the first arrival acquires on behalf of the whole group and the last departure releases — is a general pattern (a "lightswitch") that appears well beyond this problem.
The practical guidance from 5.3 still applies: prefer a library implementation, choose a writer-preferring or fair one for anything that must accept updates, and consider RCU or copy-on-write when reads dominate overwhelmingly.
Example
Reader-priority: the lightswitch pattern
first reader in -> acquires rw_mutex (locking out writers for the group)
readers 2..n -> just increment the count; no writer can be active anyway
last reader out -> releases rw_mutex
read_count: 0 -> 1 (acquire rw_mutex)
1 -> 2, 2 -> 3 (no lock operations at all)
3 -> 2, 2 -> 1
1 -> 0 (release rw_mutex)
The three formulations and who starves
formulation | new reader arrives while a writer waits | starves
-----------------+----------------------------------------+---------
first (readers) | admitted immediately | writers
second (writers) | must wait | readers
third (fair) | queues behind the writer | nobody
Writer starvation, concretely
R1 [=====] R3 [=====]
R2 [=====] R4 [=====] read_count never hits 0
W1 waiting .............................. -> rw_mutex never released
#include <semaphore.h>
sem_t rw_mutex; /* init 1: held by a writer, or by the reader group */
sem_t mutex; /* init 1: protects read_count */
int read_count = 0;
/* --- Writer: straightforward exclusive access --- */
void writer(void) {
sem_wait(&rw_mutex);
write_shared_data();
sem_post(&rw_mutex);
}
/* --- Reader: the lightswitch --- */
void reader(void) {
sem_wait(&mutex);
read_count++;
if (read_count == 1) /* FIRST reader locks out writers for
the whole group */
sem_wait(&rw_mutex);
sem_post(&mutex);
read_shared_data(); /* many readers execute here at once */
sem_wait(&mutex);
read_count--;
if (read_count == 0) /* LAST reader lets writers back in */
sem_post(&rw_mutex);
sem_post(&mutex);
}
/* This is the FIRST formulation: a new reader arriving while a writer waits
simply increments read_count and proceeds -> writers may starve. */
import threading
class FairRWLock:
"""Third formulation: a turnstile enforces arrival order, so neither
readers nor writers can starve."""
def __init__(self):
self._turnstile = threading.Semaphore(1) # every arrival passes here
self._rw = threading.Semaphore(1) # exclusive access
self._mutex = threading.Lock()
self._readers = 0
def acquire_read(self):
self._turnstile.acquire() # queue in ARRIVAL ORDER;
self._turnstile.release() # a waiting writer holds it,
# so later readers queue behind
with self._mutex:
self._readers += 1
if self._readers == 1:
self._rw.acquire() # lightswitch on
def release_read(self):
with self._mutex:
self._readers -= 1
if self._readers == 0:
self._rw.release() # lightswitch off
def acquire_write(self):
self._turnstile.acquire() # HOLD it: blocks new readers
self._rw.acquire() # wait for current readers
def release_write(self):
self._rw.release()
self._turnstile.release() # let the queue drain
Key takeaways
- The problem has three standard formulations, distinguished by who is allowed to overtake whom.
- Reader-priority maximises read concurrency and starves writers; writer-priority does the reverse.
- The reader solution uses a lightswitch: the first reader acquires the exclusive lock for the group, the last releases it.
- A fair solution adds a turnstile that both sides must pass, enforcing arrival order and eliminating starvation.
🧪 Practice
- Implement the reader-priority solution and demonstrate writer starvation with a continuous stream of readers.
- Modify it to be writer-preferring, then show that readers can now starve.
- Interview-style: "Which formulation would you choose for a routing table read on every packet and updated on topology change?" Hint: ask what the consequence is of a stale table versus a delayed packet.
Dining Philosophers Problem
Theory
Dijkstra's dining philosophers (1965) is the canonical illustration of deadlock, and its value is that the deadlock is not a coding mistake — it arises from a symmetric, apparently reasonable protocol.
Five philosophers sit around a table, alternating between thinking and eating. Between each pair is a single chopstick, and a philosopher needs both neighbouring chopsticks to eat. The obvious algorithm is: pick up the left chopstick, then the right one, eat, put both down.
This deadlocks. If all five simultaneously pick up their left chopstick, each holds one and waits forever for a right one that will never be released. All four Coffman conditions (Chapter 6) are present: mutual exclusion on chopsticks, hold-and-wait, no preemption, and a circular wait around the table.
The classic remedies each break one condition, and comparing them is the real lesson:
| Solution | Condition broken | Cost |
|---|---|---|
| Allow at most 4 at the table | Circular wait | Requires a global counting semaphore |
| Asymmetric: one philosopher picks up right first | Circular wait | Breaks the cycle with a single exception |
| Pick up both or neither (atomic acquisition) | Hold-and-wait | Needs a lock over the whole table; less concurrency |
| Global ordering: always take the lower-numbered chopstick first | Circular wait | The general, practical answer |
| Timeout and retry | No preemption | Risks livelock without randomised backoff |
The global lock ordering solution is the one that generalises to real software, and it is the single most useful takeaway in this chapter: if every thread acquires locks in the same global order, circular wait is impossible and deadlock cannot occur. This is why production codebases document a lock hierarchy, and why the two-account transfer problem is solved by locking accounts in ID order.
A subtlety: solving deadlock is not the same as ensuring fairness. A solution can be deadlock-free while allowing one philosopher to starve — the two properties must be checked separately.
Example
The table
P0
C4 C0
P4 P1
C3 C1
P3 C2 P2
THE DEADLOCK (every philosopher takes left first, simultaneously)
P0 holds C0, waits for C1
P1 holds C1, waits for C2
P2 holds C2, waits for C3
P3 holds C3, waits for C4
P4 holds C4, waits for C0 <- the cycle closes: nobody proceeds
FIX BY ASYMMETRY (P4 takes right first)
P4 tries C0 first. Either it gets C0 (so P0 cannot hold it and the cycle
is broken), or it does not (so it holds nothing and blocks harmlessly).
The cycle can never close.
FIX BY GLOBAL ORDERING (always take the LOWER-numbered chopstick first)
P0: C0 then C1 P1: C1 then C2 P2: C2 then C3
P3: C3 then C4 P4: C0 then C4 <- note: NOT C4 then C0
Acquisition order is monotonic for everyone -> no cycle is possible.
#include <pthread.h>
#define N 5
pthread_mutex_t chopstick[N];
/* --- DEADLOCKS: symmetric left-then-right --- */
void philosopher_broken(int i) {
while (1) {
think();
pthread_mutex_lock(&chopstick[i]); /* left */
pthread_mutex_lock(&chopstick[(i + 1) % N]); /* right -- may never come */
eat();
pthread_mutex_unlock(&chopstick[(i + 1) % N]);
pthread_mutex_unlock(&chopstick[i]);
}
}
/* --- CORRECT: global lock ordering. The general solution. --- */
void philosopher(int i) {
int left = i, right = (i + 1) % N;
int first = left < right ? left : right; /* always the LOWER index first */
int second = left < right ? right : left;
while (1) {
think();
pthread_mutex_lock(&chopstick[first]); /* monotonic order for every
philosopher -> no cycle */
pthread_mutex_lock(&chopstick[second]);
eat();
pthread_mutex_unlock(&chopstick[second]);
pthread_mutex_unlock(&chopstick[first]);
}
}
import threading
# The same principle in real code: the classic two-account transfer.
class Account:
def __init__(self, id_, balance):
self.id = id_
self.balance = balance
self.lock = threading.Lock()
def transfer_broken(src, dst, amount):
with src.lock: # thread 1: A then B
with dst.lock: # thread 2: B then A -> DEADLOCK
src.balance -= amount
dst.balance += amount
def transfer(src, dst, amount):
# Order the locks by a stable global key -- exactly the philosophers' fix.
first, second = (src, dst) if src.id < dst.id else (dst, src)
with first.lock:
with second.lock:
if src.balance >= amount:
src.balance -= amount
dst.balance += amount
return True
return False
Key takeaways
- Dining philosophers shows that a symmetric, reasonable protocol can deadlock without any coding error.
- The deadlock arises from a circular wait, one of the four conditions covered in Chapter 6.
- Standard fixes limit concurrency, break symmetry, acquire atomically, or impose a global ordering.
- Global lock ordering is the solution that generalises: identical acquisition order everywhere makes deadlock impossible.
🧪 Practice
- Implement the broken version with five threads and observe the deadlock. Confirm the state with a thread dump or
gdb.- Implement two different fixes and compare their throughput. Which permits the most concurrent eating?
- Interview-style: "Two threads transfer money between the same pair of accounts in opposite directions and the service hangs. Diagnose and fix." Hint: this is the philosophers' cycle with N = 2.
Sleeping Barber Problem
Theory
The sleeping barber problem (Dijkstra) models a service system with a finite waiting area, and it isolates a difficulty the previous problems do not: the rendezvous between a server that sleeps when idle and clients that must decide whether to wait or leave.
The setup: a barber shop has one barber, one barber chair, and N waiting chairs. If there are no customers, the barber sleeps. A customer who arrives wakes the barber if asleep, sits in a waiting chair if one is free, or leaves immediately if the waiting room is full.
Three coordination problems must be solved at once:
- The barber must sleep when idle rather than busy-waiting for customers.
- A customer must wake a sleeping barber, and exactly one customer must be served per wake.
- The waiting room is bounded, so an arriving customer must atomically check for a free chair and either take it or leave.
That third point is where the classic race lives. Checking "is a chair free?" and then sitting down must be one atomic operation — otherwise two customers can both observe the last free chair and both sit, overflowing the room. The count must be protected by a mutex, and the decision to leave must be made while holding it.
The standard solution uses three semaphores:
customers, initialised to 0: the barber waits on it, so it sleeps when there are none.barber, initialised to 0: a customer waits on it until the barber is ready for them.mutex, initialised to 1: protectswaiting, the count of seated customers.
The customers/barber pair is a rendezvous: each side signals the other and waits, so neither proceeds until both are ready. This is the reusable idea, and it appears in every thread-pool implementation — the pool's worker threads sleep on a queue-not-empty condition, submitters wake exactly one, and a bounded queue rejects work when full. The barber is a worker thread, the waiting chairs are the queue, and a customer leaving is a rejection policy (Chapter 4's CallerRunsPolicy and friends).
Example
The shop
+-------------------------------------------+
| waiting chairs: [C][C][ ][ ][ ] (N = 5) |
| |
| barber chair: [ BARBER + customer ] |
+-------------------------------------------+
customers arrive -> chair free? sit and signal the barber
-> room full? LEAVE (this is a rejection policy)
The rendezvous
CUSTOMER BARBER
wait(mutex) wait(customers) <- SLEEPS here when 0
if waiting == N: wait(mutex)
signal(mutex); leave waiting--
waiting++ signal(barber) <- "I am ready for you"
signal(customers) ------------> signal(mutex)
signal(mutex) cut_hair()
wait(barber) <------------
get_haircut()
THE RACE without the mutex
two customers both read waiting == 4 (one chair left)
both increment -> waiting == 6 in a 5-chair room
The check and the increment must be ONE atomic step.
The same structure, in production
barber = a worker thread in a pool
waiting chairs = the bounded task queue
sleeping barber = a worker blocked on "queue not empty"
customer leaves = the pool's rejection policy when the queue is full
#include <semaphore.h>
#define CHAIRS 5
sem_t customers; /* init 0: counts waiting customers; the barber sleeps here */
sem_t barber; /* init 0: signals a customer that the barber is ready */
sem_t mutex; /* init 1: protects `waiting` */
int waiting = 0;
void barber_thread(void) {
while (1) {
sem_wait(&customers); /* SLEEP until a customer arrives */
sem_wait(&mutex);
waiting--; /* take one customer out of the waiting room */
sem_post(&barber); /* tell that customer to come over */
sem_post(&mutex);
cut_hair(); /* outside the mutex: it takes a long time */
}
}
void customer_thread(void) {
sem_wait(&mutex); /* check-and-sit must be ATOMIC */
if (waiting < CHAIRS) {
waiting++;
sem_post(&customers); /* wake the barber if it is asleep */
sem_post(&mutex); /* release BEFORE blocking, or nobody
else could ever enter the shop */
sem_wait(&barber); /* wait my turn */
get_haircut();
} else {
sem_post(&mutex); /* room full: leave. Must release the mutex. */
leave_without_haircut();
}
}
import threading, queue
# The modern equivalent: a worker pool with a bounded queue and a
# rejection policy. Same three problems, solved by the library.
class BarberShop:
def __init__(self, chairs=5):
self._chairs = queue.Queue(maxsize=chairs) # the waiting room
self._barber = threading.Thread(target=self._work, daemon=True)
self._barber.start()
def _work(self):
while True:
customer = self._chairs.get() # SLEEPS here when empty:
# exactly the sleeping barber
self._cut_hair(customer)
self._chairs.task_done()
def arrive(self, customer):
try:
self._chairs.put_nowait(customer) # atomic check-and-sit
return True
except queue.Full:
return False # the customer leaves
Key takeaways
- The sleeping barber models a server that sleeps when idle and a bounded waiting area for clients.
- It requires a rendezvous: the barber signals readiness and the customer signals arrival, each waiting for the other.
- Checking for a free chair and taking it must be atomic, or the waiting room overflows.
- The structure is exactly a thread pool: sleeping workers, a bounded queue, and a rejection policy when full.
🧪 Practice
- Implement the solution and verify that customers are turned away when all chairs are occupied.
- Extend it to multiple barbers. What changes, and what does not?
- Interview-style: "Map the sleeping barber onto a web server with a connection backlog." Hint: identify the barber, the chairs, and what corresponds to a connection being refused.
<a id="55-alternative-approaches"></a>
5.5 Alternative Approaches
Locks are not the only answer, and sometimes they are the wrong one; this section covers techniques that avoid blocking, that make composition easier, and that the kernel itself relies on.
Lock-Free Data Structures
Theory
Locks have costs beyond their execution time. A thread holding a lock and then descheduled blocks every waiter for its entire absence — convoying. A thread that crashes or is killed while holding a lock leaves it held forever. Locks cannot be taken in some contexts (interrupt handlers, signal handlers). And composing two lock-protected operations atomically requires holding both locks, reintroducing deadlock risk.
Lock-free programming avoids all of this by using atomic operations directly, with the guarantee that at least one thread always makes progress, regardless of what any other thread does — including being preempted mid-operation. There is a precise hierarchy:
| Property | Guarantee |
|---|---|
| Blocking | A stalled thread can prevent all progress |
| Obstruction-free | A thread makes progress if it runs alone (others may cause it to retry) |
| Lock-free | Some thread always makes progress; individual threads may starve |
| Wait-free | Every thread completes in a bounded number of steps |
Wait-freedom is the strongest and rarest, valuable for real-time systems where per-thread bounds matter.
The universal building block is the CAS retry loop of 5.2. The characteristic difficulty is memory reclamation: with locks, you know nobody is inside a structure when you free a node. Lock-free, another thread may hold a pointer to a node you are about to free, and there is no lock to tell you. Three standard solutions exist — hazard pointers (each thread publishes what it is reading; nothing published may be freed), epoch-based reclamation (free only when all threads have passed an epoch boundary), and garbage collection (why lock-free structures are notably easier in Java and Go than in C++).
The honest assessment: lock-free code is difficult to write, harder to verify, and frequently slower than a good lock under contention, since retries waste work that a lock would have avoided. Use existing library implementations (ConcurrentLinkedQueue, crossbeam, folly), and write your own only with a measured reason.
Example
Progress guarantees
BLOCKING (mutex)
T1 takes the lock, is preempted for 10 ms
T2, T3, T4 -> all blocked for 10 ms (convoying)
LOCK-FREE (CAS)
T1 is preempted mid-operation
T2 CASes successfully and completes system progresses
T1 resumes, its CAS fails, it retries T1 may retry many times
WAIT-FREE
every thread completes within a bounded number of steps, always
The memory reclamation hazard
T1: reads head -> node A, about to dereference A->next
T2: pops A and calls free(A)
T1: dereferences freed memory <- use-after-free
There is no lock to tell T2 that T1 is still inside.
Hazard pointers
T1 publishes: "I am reading A" -> hazard[T1] = A
T2 wants to free A: scans all hazard slots, sees A is published,
defers the free to a retire list and reclaims it later.
import java.util.concurrent.atomic.AtomicReference;
// A lock-free (Treiber) stack. No mutex anywhere; the GC handles reclamation.
public class LockFreeStack<T> {
private static class Node<T> {
final T value; Node<T> next;
Node(T value) { this.value = value; }
}
private final AtomicReference<Node<T>> head = new AtomicReference<>();
public void push(T value) {
Node<T> newHead = new Node<>(value);
Node<T> oldHead;
do {
oldHead = head.get(); // 1. read current state
newHead.next = oldHead; // 2. compute desired state
} while (!head.compareAndSet(oldHead, newHead));
// ^ 3. commit only if nothing changed; otherwise retry.
// A preempted thread here blocks NOBODY.
}
public T pop() {
Node<T> oldHead, newHead;
do {
oldHead = head.get();
if (oldHead == null) return null;
newHead = oldHead.next;
} while (!head.compareAndSet(oldHead, newHead));
return oldHead.value;
// In C++ this would be an ABA and use-after-free minefield; the JVM's
// GC will not recycle `oldHead` while any thread can still reach it.
}
}
# When lock-free is the WRONG choice: measure before you commit to it.
#
# contention | mutex | lock-free CAS
# -------------+--------------+---------------------------
# none | ~20 ns | ~20 ns (comparable)
# low | ~50 ns | ~30 ns (CAS wins)
# high (16 thr)| ~500 ns | ~2000 ns (retries dominate: LOCK wins)
#
# Under heavy contention the CAS loop repeatedly does work and throws it
# away, while a mutex lets losers sleep instead of burning CPU.
Key takeaways
- Lock-free algorithms guarantee that some thread always progresses, avoiding convoying and lock-holder failure.
- The hierarchy runs blocking, obstruction-free, lock-free, wait-free, with wait-freedom the strongest.
- The hard part is memory reclamation: hazard pointers, epoch-based schemes, or a garbage collector are required.
- Lock-free is often slower than a good lock under high contention; prefer library implementations and measure first.
🧪 Practice
- Implement a lock-free counter and a mutex counter, and benchmark both at 1, 4, and 32 threads. Identify the crossover.
- Explain why the Treiber stack above is safe in Java but would need hazard pointers in C.
- Interview-style: "Why is 'lock-free' not the same as 'faster'?" Hint: consider what a losing thread does in each design and how much work it discards.
Transactional Memory
Theory
Locks have a composability problem that no amount of care fixes. Given a thread-safe withdraw and a thread-safe deposit, there is no way to compose them into an atomic transfer without reaching inside both and taking their locks — which requires knowing their internals and reintroduces lock-ordering deadlock. Locks do not compose.
Transactional memory (TM) borrows the database solution. A block of code is marked as a transaction: it executes optimistically while the system tracks every memory location read and written; at commit, if no other transaction touched those locations, the changes are applied atomically. If there was a conflict, the transaction is rolled back and retried.
The advantages are substantial:
- Composability. Nested transactions compose naturally — a transaction containing two others is simply a bigger transaction.
- No deadlock, because no locks are taken and there is no acquisition order to get wrong.
- Optimistic concurrency. Operations that touch disjoint data proceed in parallel without the programmer having to prove they are disjoint, which is what fine-grained locking demands.
- Simplicity. The programmer marks what must be atomic instead of designing how to make it so.
Two implementations exist. Software TM (STM) needs no hardware but adds substantial overhead — often 2-5x — because every read and write is instrumented. Hardware TM (Intel TSX, IBM POWER) uses the cache-coherence protocol to detect conflicts nearly for free, but transactions are bounded by cache capacity, can abort for reasons unrelated to conflicts (interrupts, page faults, system calls), and therefore always require a fallback path, usually a conventional lock.
The state of the art is mixed. Intel disabled TSX on many parts after security vulnerabilities were discovered, and hardware TM never became mainstream. STM is genuinely successful in Haskell and Clojure, where the language's control over side effects makes rollback safe — and that is the deep limitation: irreversible operations cannot be rolled back. A transaction that performs I/O, sends a network message, or takes a lock cannot simply be retried, which is why STM works best in languages that can restrict what a transaction may do.
Example
The composability problem locks cannot solve
Thread-safe pieces:
account.withdraw(x) -- takes account's lock
account.deposit(x) -- takes account's lock
Wanted: transfer(a, b, x) that is atomic as a WHOLE.
With locks: you must reach INSIDE both objects, take both locks in a
globally consistent order, and hope no other code path disagrees.
With transactions: just wrap both calls. Nesting composes automatically.
How a transaction executes
BEGIN
read set = { } every read is recorded
write set = { } every write is buffered, not applied
... run the block optimistically ...
COMMIT
if nothing else wrote to my read set -> apply the write set atomically
else -> DISCARD everything and RETRY
Two transactions on disjoint data both commit: full parallelism,
with no lock and no programmer-supplied proof that they are disjoint.
Why hardware TM needs a fallback
abort causes: conflict, cache capacity exceeded, interrupt, page fault,
system call, unsupported instruction
-> a transaction may NEVER succeed, so code must fall back to a lock
after a few attempts.
-- Haskell STM: the type system guarantees a transaction cannot do I/O,
-- which is exactly what makes rollback safe.
import Control.Concurrent.STM
transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to amount = do
balance <- readTVar from
if balance < amount
then retry -- block until `from` CHANGES, then
-- re-run: no condition variable needed
else do
writeTVar from (balance - amount)
modifyTVar' to (+ amount)
main :: IO ()
main = do
a <- atomically $ newTVar 1000
b <- atomically $ newTVar 500
atomically $ transfer a b 300 -- the WHOLE thing is atomic
-- Composition, which locks cannot express safely:
atomically $ do
transfer a b 100 -- two atomic operations become
transfer b a 50 -- ONE atomic operation, for free
/* Hardware TM (Intel TSX), with the mandatory lock fallback. */
#include <immintrin.h>
void transfer(struct account *a, struct account *b, int amount) {
for (int attempt = 0; attempt < 3; attempt++) {
unsigned status = _xbegin();
if (status == _XBEGIN_STARTED) {
if (a->balance >= amount) { /* speculative execution: */
a->balance -= amount; /* tracked by the cache */
b->balance += amount; /* coherence protocol */
}
_xend(); /* commit atomically */
return;
}
/* Aborted: conflict, capacity, interrupt, or page fault. Retry. */
}
/* FALLBACK: a transaction may never succeed, so a lock path is
mandatory, not optional. */
lock_both_ordered(a, b);
if (a->balance >= amount) { a->balance -= amount; b->balance += amount; }
unlock_both(a, b);
}
Key takeaways
- Transactional memory executes a block optimistically, tracking reads and writes, and retries on conflict.
- It solves the composability problem that locks cannot: nested transactions merge into one atomic operation.
- Software TM is portable but slow; hardware TM is fast but bounded and always needs a lock fallback.
- Transactions cannot contain irreversible operations, which is why STM succeeds mainly in languages that restrict side effects.
🧪 Practice
- Explain why
transfercannot be composed from thread-safewithdrawanddepositwithout reaching inside both.- Name three reasons a hardware transaction can abort that have nothing to do with a data conflict.
- Interview-style: "Why can't a transaction send a network packet?" Hint: consider what the system must be able to do if the transaction aborts.
Priority Inversion and Inheritance
Theory
Priority inversion occurs when a high-priority task is blocked by a lower-priority one, effectively inverting their priorities. It is unavoidable in principle whenever priorities coexist with locks: if a low-priority task holds a lock a high-priority task needs, the high-priority task must wait. That much is bounded inversion, and it is acceptable.
The failure is unbounded priority inversion, which requires a third participant:
- Low acquires lock L.
- High becomes runnable, tries to acquire L, and blocks.
- Medium — which needs no lock at all — becomes runnable and preempts Low, because it has higher priority.
- Low cannot run, so it cannot release L, so High cannot run.
High is now effectively waiting behind Medium, a task it outranks, for an unbounded time. There can be any number of medium-priority tasks, so the delay has no upper bound at all.
This is not a theoretical concern. In July 1997 the Mars Pathfinder lander began resetting repeatedly on the Martian surface: a high-priority bus management task blocked on a mutex held by a low-priority meteorological task, which was preempted by medium-priority communications work. A watchdog timer detected the missed deadline and reset the system. The fix — enabling priority inheritance on that mutex — was uploaded to Mars.
Two protocols solve it:
- Priority inheritance. When a high-priority task blocks on a lock, the holder temporarily inherits the waiter's priority, so it cannot be preempted by medium-priority tasks and finishes quickly. On release, it reverts. This is the common solution (
PTHREAD_PRIO_INHERIT, and the default forSCHED_DEADLINEand RT mutexes in Linux). - Priority ceiling. Each lock is statically assigned a ceiling equal to the highest priority of any task that may acquire it. A task holding the lock runs at that ceiling immediately. This bounds blocking more tightly and prevents deadlock as a side effect, but requires knowing the full set of lock users in advance.
The general lesson beyond real-time systems: priorities and locks interact badly, and any system that uses both needs an inheritance protocol.
Example
UNBOUNDED PRIORITY INVERSION
priority
HIGH | [blocked on L .................................] [runs]
MED | [============ runs freely ==============]
LOW | [takes L][preempted..................................][release L]
+--------------------------------------------------------------> time
^ ^
H blocks here L finally resumes
H waits for MED, which it outranks, for an UNBOUNDED time
(add more medium tasks and the delay grows without limit)
WITH PRIORITY INHERITANCE
priority
HIGH | [blocked][=================================][runs]
MED | [runs]
LOW | [takes L][runs AT HIGH PRIORITY][release L]
+--------------------------------------------------------------> time
^ ^
L inherits HIGH, so MED L reverts to LOW
cannot preempt it H proceeds immediately
Blocking is now bounded by the LENGTH OF THE CRITICAL SECTION,
not by the amount of medium-priority work in the system.
#include <pthread.h>
/* Enable priority inheritance -- the Mars Pathfinder fix, in two lines. */
pthread_mutex_t lock;
pthread_mutexattr_t attr;
void init_rt_mutex(void) {
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
/* Alternative: PTHREAD_PRIO_PROTECT with an explicit ceiling.
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_PROTECT);
pthread_mutexattr_setprioceiling(&attr, 80);
Tighter bound, but requires knowing every user of the lock. */
pthread_mutex_init(&lock, &attr);
}
/* Without setprotocol, the default is PTHREAD_PRIO_NONE: no inheritance,
and unbounded inversion is possible. This is the default almost
everywhere, which is why it must be set explicitly. */
# The general lesson, in plain terms.
#
# Any system combining PRIORITIES with LOCKS can invert. That includes:
# - RTOS tasks and a shared mutex
# - a thread pool with prioritised work and a shared cache lock
# - Linux SCHED_FIFO threads sharing a futex with SCHED_OTHER threads
#
# Mitigations, in order of preference:
# 1. Enable priority inheritance on every shared mutex.
# 2. Do not share locks across priority bands at all (partition the data).
# 3. Keep critical sections extremely short, bounding the inversion.
# 4. Use lock-free structures, where there is no holder to preempt.
Key takeaways
- Priority inversion is a high-priority task blocked by a lower-priority lock holder; some inversion is unavoidable.
- Unbounded inversion needs a third, medium-priority task that preempts the holder while the high task waits.
- Priority inheritance temporarily raises the holder to the waiter's priority, bounding the delay by the critical section.
- Priority ceiling assigns each lock the highest priority of any user, bounding blocking further and preventing deadlock.
🧪 Practice
- Draw a timeline of unbounded inversion with three tasks, then redraw it with priority inheritance enabled.
- Explain why priority ceiling requires static knowledge of the system and what it gains in return.
- Interview-style: "An RTOS task misses its deadline only when an unrelated medium-priority task is active. Diagnose it." Hint: look for a lock shared between the high-priority task and something below the medium one.
Kernel Synchronization Mechanisms
Theory
The kernel faces every problem in this chapter under harder constraints. It runs on all cores simultaneously, is entered from interrupt handlers that cannot sleep, must not deadlock against itself, and its synchronization cost is paid by every process on the machine. It therefore uses a wider and more specialised toolkit.
The core constraint that shapes everything: some kernel contexts cannot sleep. Interrupt handlers and code holding a spinlock must never block, which immediately rules out mutexes and semaphores in those paths.
| Mechanism | Sleeps? | Use |
|---|---|---|
| Spinlock | No | Short critical sections, any context including interrupts |
| Mutex / semaphore | Yes | Longer sections in process context only |
spin_lock_irqsave | No | When the same lock is taken in interrupt context |
| Atomic variables | No | Counters and flags, no lock needed |
| Per-CPU variables | N/A | Eliminate sharing entirely — the cheapest option |
| Seqlock | No | Write-rare, read-frequent data (timekeeping) |
| RCU | Readers never block | Read-mostly structures: routing tables, module lists |
Two mechanisms deserve particular attention because they represent genuinely different ideas:
RCU (read-copy-update) makes readers completely free — no locks, no atomic operations, not even a memory barrier on strongly ordered architectures. A writer copies the data, modifies the copy, and atomically swaps the pointer. Old readers continue safely on the old version; the old copy is freed only after a grace period, when every CPU has passed through a context switch and therefore cannot still hold a reference. RCU trades write cost and reclamation delay for essentially zero read cost, which is exactly the right trade for the kernel's many read-mostly structures.
Seqlocks let writers proceed without waiting for readers. A sequence counter is incremented before and after each write (making it odd during the write). A reader samples the counter, reads the data, and samples again; if the values differ or are odd, it retries. This suits small, frequently read values such as the system clock.
Per-CPU variables deserve the last word: the cheapest synchronization is none. Giving each CPU its own copy of a counter and summing on demand eliminates contention entirely, and it is why kernel statistics are almost always per-CPU.
Example
Choosing a kernel primitive
Can this code sleep?
|
+-- NO (interrupt handler, holding a spinlock)
| |
| +-- Is it also taken from an IRQ? -> spin_lock_irqsave
| +-- Just a counter? -> atomic_t
| +-- Read-mostly? -> RCU / seqlock
| +-- Otherwise -> spin_lock
|
+-- YES (process context)
|
+-- Long critical section -> mutex
+-- Counting a resource -> semaphore
+-- Read-heavy -> rw_semaphore or RCU
RCU: how a reader pays nothing
readers: rcu_read_lock() ... use pointer ... rcu_read_unlock()
^ on most architectures this compiles to NOTHING but a
compiler barrier and preemption bookkeeping
writer: copy = clone(old)
modify(copy)
rcu_assign_pointer(ptr, copy) <- one atomic pointer swap
synchronize_rcu() <- WAIT for the grace period
kfree(old) <- now provably unreachable
timeline:
old readers ---[still using old]---|
new readers ------------------[use new]------------>
^
grace period ends here; old is freed
Seqlock: writers never wait for readers
writer: seq++ (now ODD) ... write ... seq++ (now EVEN)
reader: s1 = seq; if odd, retry
read data
s2 = seq; if s1 != s2, RETRY (a write happened mid-read)
/* --- RCU: the kernel's read-mostly workhorse --- */
struct config __rcu *global_config;
/* READER: no lock, no atomic, no wait. Runs concurrently with the writer. */
int lookup_timeout(void) {
struct config *cfg;
int value;
rcu_read_lock(); /* marks a read-side section;
essentially free */
cfg = rcu_dereference(global_config); /* safe pointer load */
value = cfg->timeout;
rcu_read_unlock();
return value;
}
/* WRITER: copy, modify, swap, then wait before freeing. */
void update_timeout(int new_timeout) {
struct config *old, *new;
new = kmalloc(sizeof *new, GFP_KERNEL);
old = rcu_dereference_protected(global_config, lockdep_is_held(&cfg_lock));
*new = *old; /* COPY */
new->timeout = new_timeout; /* UPDATE the copy */
rcu_assign_pointer(global_config, new); /* atomic swap: new readers
see `new`, old ones are
still safely using `old` */
synchronize_rcu(); /* wait until no reader can
hold `old` any more */
kfree(old); /* only NOW is it safe */
}
/* --- Per-CPU: the cheapest synchronization is none at all --- */
DEFINE_PER_CPU(unsigned long, packets_received);
void on_packet(void) {
this_cpu_inc(packets_received); /* no atomic, no lock, no contention:
each CPU touches only its own copy */
}
unsigned long total_packets(void) {
unsigned long total = 0;
int cpu;
for_each_possible_cpu(cpu)
total += per_cpu(packets_received, cpu); /* sum only when asked */
return total;
}
# Observing kernel synchronization on a live system.
cat /proc/lock_stat # lock contention statistics (CONFIG_LOCK_STAT)
dmesg | grep -i lockdep # lockdep: runtime lock-order validation
perf lock report # which locks are contended, and for how long
cat /sys/kernel/debug/rcu/rcugp # RCU grace period progress
Key takeaways
- The kernel's defining constraint is that interrupt handlers and spinlock holders must never sleep.
- Primitive choice follows from context: spinlocks and atomics where sleeping is forbidden, mutexes where it is allowed.
- RCU gives readers essentially zero cost by copying on write and deferring reclamation until a grace period ends.
- Seqlocks let writers proceed without waiting for readers, and per-CPU variables remove contention entirely.
🧪 Practice
- For each case, choose a primitive and justify it: an interrupt-handler counter, a rarely updated routing table, a long file-system operation, per-CPU statistics.
- Explain what a grace period is and why RCU cannot free the old copy before it ends.
- Interview-style: "Why is RCU better than a readers-writers lock for the kernel's module list?" Hint: count the atomic operations a reader performs in each design, and how often that list is read versus written.
<a id="6-deadlocks"></a>