2.4 — Concurrency Primitives

2.3 gave threads their superpower: shared memory, so cooperating tasks can pass data by simply touching the same variable. This chapter is about the catastrophe that superpower invites, and the tools built to tame it. When two threads read and write the same data at overlapping moments, the result can be silently, non-deterministically wrong — a bug that passes every test, then corrupts a bank balance in production at 3 a.m. and never reproduces. Understanding why is one of the genuine rites of passage in systems programming, and the tools that fix it — the mutex, the semaphore, the condition variable — are among the most reused ideas in all of software, appearing from OS kernels to databases to your own application code. We'll also meet the trap those tools set: the deadlock, where threads freeze forever waiting on each other.

1. The race condition: why count++ can lose data

Here is the smallest program that demonstrates the whole problem. Two threads share one integer, count, starting at 0. Each thread runs count = count + 1 one million times. When both finish, what is count?

The obvious answer — 2,000,000 — is wrong, or rather, it's only sometimes right. Run it and you'll often get 1,700,000, or 1,300,000, or some different number every time. Data vanished. To see why, you must remember from 1.5 that count = count + 1 is not one indivisible action to the CPU. It's three separate machine instructions:

1. Load the current value of count from memory into a register.
2. Add 1 to the register.
3. Store the register back to count in memory.

Now imagine two threads, A and B, running this on count = 41, and the 2.3 scheduler happens to interleave them at the worst moment:

Figure 1 — A lost update. Both threads read 41 before either stored 42. Two increments produced one net increment. Nothing is "broken" — each instruction ran correctly — yet the result is wrong, because the read-modify-write wasn't indivisible.

Both threads read 41, both computed 42, both stored 42. Two increments, but count advanced by one. An update was silently lost. This is a race condition: a bug where the correctness of the result depends on the timing of how threads interleave — a race the threads didn't know they were running. The section of code that touches the shared data (the load-add-store) is called the critical section, and the deep problem is that it is not atomic — not indivisible. The scheduler can preempt a thread in the middle of it, letting another thread see a half-finished world.

Three things make race conditions uniquely nasty, and worth internalising. They are non-deterministic — they depend on exact timing, so they appear randomly and often vanish under a debugger (which changes the timing). They are invisible in testing — with two threads and a fast machine, the bad interleaving might occur one time in a million, passing your whole test suite and failing in production. And they scale with load — the more concurrency (more threads, more cores, more traffic), the more often the rare interleaving happens. This is why concurrency bugs are legendary, and why the tools below are not optional niceties but the price of admission to shared-memory programming.

2. Mutual exclusion: the mutex

The fix follows directly from the diagnosis. If the trouble is two threads inside the critical section at once, then let only one in at a time. This property is mutual exclusion, and the tool that enforces it is the mutex (a contraction of mutual exclusion) — sometimes called a lock.

A mutex is a simple object with two operations: lock (acquire) and unlock (release). The rule the kernel and hardware guarantee: at most one thread can hold the lock at a time. A thread calls lock() before entering the critical section; if the mutex is free, it takes it and proceeds; if another thread already holds it, the caller blocks (goes to sleep, using no CPU — the Blocked state from 2.2) until the holder calls unlock(), at which point one waiting thread wakes and acquires it.

mutex.lock();          // only one thread past this point at a time
count = count + 1;     // critical section — now safe
mutex.unlock();        // let the next waiting thread in

With the mutex, our two threads can no longer interleave inside the load-add-store: whichever grabs the lock first runs all three instructions to completion before the other is even allowed to start. The lost update is impossible. Problem solved — but the solution introduces its own costs and hazards, which is the rest of this chapter.

The natural question: how can lock() itself be safe? Checking "is the lock free?" and then "take it" is a read-modify-write — the very race we're trying to fix! The answer reaches back to the hardware: CPUs provide special atomic instructions (like compare-and-swap, CAS, and test-and-set) that perform a read-modify-write as a single, indivisible operation the hardware guarantees no other core can interrupt. The mutex is built on these atomic primitives — the one place the "make it indivisible" problem is solved in silicon, so everything above can rely on it. (Those same atomic instructions also enable lock-free data structures — algorithms that coordinate using only CAS, no locks at all, avoiding blocking entirely at the cost of much harder reasoning. Powerful, expert-level, and easy to get subtly wrong.)

3. The semaphore: counting, not just locking

A mutex is binary: locked or unlocked, one holder or none. But some problems need to allow up to N threads through, not just one — "at most 5 concurrent database connections," "at most 10 downloads at once." For that, Edsger Dijkstra invented the semaphore in 1965, and it's worth understanding precisely because it's both more general than a mutex and frequently misunderstood.

A semaphore is essentially a protected counter with two atomic operations, traditionally named from Dutch:

• wait (also P, or acquire, or down): decrement the counter. If the counter is now negative (i.e., it was already 0), block until someone signals.
• signal (also V, or release, or up): increment the counter, waking a blocked waiter if any.

The counter represents how many units of a resource are available. Initialise it to 5, and the first five wait() calls sail through (counter 5→4→3→2→1→0); the sixth blocks until some thread signal()s (returns a unit). It's a bouncer at a club with a capacity of 5: let people in until full, and admit one more each time someone leaves. A binary semaphore (initialised to 1) acts much like a mutex — but with a subtle, important difference: a mutex has the notion of ownership (only the thread that locked it should unlock it), whereas a semaphore is just a counter anyone can signal, which makes semaphores also perfect for a different job: signalling between threads ("thread A, wake up, I've produced something for you"), not just guarding a resource.

The etymology is delightful and clarifying: Dijkstra named it after the railway semaphore — the mechanical signal arm beside train tracks that tells a train "stop" or "proceed," preventing two trains from entering the same section of track at once. A concurrency semaphore does exactly that for threads and a shared resource: it's the signal that says how many may proceed.

Curiosity: "semaphore" in the wild — is it a file? Does AWS use it to track user-data?

The word semaphore shows up in two very different places, and conflating them causes confusion. (1) The OS concurrency primitive just described — a counter living in kernel memory (a named/System V semaphore can be shared between processes and does have a kernel-managed identity, but it is not a normal file with readable "content"; it's a small kernel object you interact with via syscalls). (2) A .semaphore-style marker/lock file that scripts create on disk to mean "this ran already, don't run again" — a do-once flag, borrowing the concurrency idea (one-at-a-time / already-done) but implemented as an ordinary file whose mere existence is the signal. AWS EC2 user-data (a boot-time script) uses exactly pattern (2): the cloud-init system writes a marker file (a semaphore/sentinel file, e.g. under /var/lib/cloud/instances/…/sem/) after running your user-data script, so on the next reboot it sees the marker and skips re-running it — "run user-data once per instance." So AWS isn't tracking your script with a kernel concurrency semaphore; it's using a marker file as a run-once flag, which people colloquially call a semaphore because it serves the same "gate/already-done" role. Same word, same idea (a signal that controls whether you proceed), two different mechanisms — knowing which is meant is the whole clarity. ^{⚑What is a semaphore — conceptually and technically; is it a file; what's its content; how does AWS track user-data loading through it? [EQ-39]}

4. Condition variables: waiting for a state, efficiently

Mutexes guard data; semaphores count resources. But there's a third common need: a thread must wait until some condition becomes true — "wait until the queue is non-empty," "wait until the buffer has space." You could busy-wait — loop checking the condition over and over — but that spinning burns a whole CPU doing nothing, starving other threads. The efficient tool is the condition variable (condvar): it lets a thread sleep until another thread signals that the condition may have changed.

A condition variable is always paired with a mutex, and supports: wait (atomically release the mutex and sleep — so another thread can change the state — then re-acquire the mutex on waking) and signal/notify ("wake up one/all waiters; the condition might now hold"). The standard use is the producer–consumer pattern — the backbone of virtually every task queue, thread pool, and message system: producers add items to a shared buffer and signal "not empty"; consumers wait while the buffer is empty and wake to process items. Producer and consumer never busy-wait; each sleeps efficiently until the other gives it work. (You'll build exactly this pattern, at application scale, in Part 9.5 and again as message queues in Part 10.8 — the OS condition variable is its ancestor.)

One crucial subtlety that trips up every newcomer and is a favourite interview probe: always re-check the condition in a loop, not an if, after waking (while (queue.isEmpty()) cond.wait();). Why? Because of spurious wakeups (a waiter can wake without a real signal, permitted by the standards for implementation reasons) and stolen wakeups (another thread grabbed the item between your wake and your re-acquiring the lock). Re-checking guarantees you only proceed when the condition genuinely holds. "while, not if, around wait" is a rule worth burning into memory.

5. Deadlock: the cure becomes the disease

Locks prevent races — but used carelessly, they create a failure that is arguably worse, because instead of corrupting data quietly, the program simply freezes forever. This is deadlock: two or more threads each holding a resource the other needs, each waiting for the other, neither ever proceeding.

The textbook picture: Thread A locks mutex 1, then tries to lock mutex 2. Thread B locks mutex 2, then tries to lock mutex 1. If the timing lines up, A holds 1 and waits for 2, while B holds 2 and waits for 1 — forever. It's the traffic gridlock where four cars each block the next in a circle, or the "dining philosophers" puzzle where each philosopher grabs the fork on their left and waits eternally for the fork on their right.

Figure 2 — Deadlock. A holds Lock 1 and wants Lock 2; B holds Lock 2 and wants Lock 1. Each waits for the other. Solid = holds, dashed = wants. The cycle never breaks on its own.

Deadlock requires four conditions to hold simultaneously (the Coffman conditions, and knowing them is knowing how to prevent deadlock — break any one):

1. Mutual exclusion — the resources can't be shared (only one holder).
2. Hold and wait — a thread holds one resource while waiting for another.
3. No preemption — a resource can't be forcibly taken from its holder.
4. Circular wait — a cycle of threads each waiting for the next's resource.

Because all four are necessary, you prevent deadlock by denying any one. The most common and practical technique attacks circular wait: enforce a global lock ordering — every thread must acquire locks in the same fixed order (always lock 1 before lock 2, never the reverse). With a consistent order, the cycle can't form. Other approaches: use timeouts (give up and retry if a lock isn't acquired in time — attacking hold-and-wait), acquire all needed locks at once or none, or use lock-free structures. Deadlock is the reason "just add a lock" is not a safe reflex — every lock is a potential participant in a future deadlock, and the discipline of how you lock matters as much as that you lock.

6. The expert lens

The real cost of locks is lost parallelism. A lock, by definition, serialises — it forces threads through the critical section one at a time. So the more time your threads spend holding locks, the less they run in parallel, and the less your extra cores help. This is Amdahl's Law made concrete: if 10% of the work must be serial (under a lock), then even with infinite cores you can never go more than 10× faster. The art of high-performance concurrency is therefore minimising the critical section — holding locks for as few instructions as possible, using fine-grained locks (many small locks over disjoint data rather than one big lock over everything), or eliminating shared mutable state entirely. "Lock contention" — many threads fighting over one hot lock — is a top cause of concurrent programs that mysteriously fail to scale, echoing the false sharing hardware version from 1.6.

The best synchronisation is no synchronisation. Every lock is a bug waiting to happen (a race if you forget one, a deadlock if you take two). So the most robust concurrent designs avoid sharing mutable state rather than guarding it. Three escape routes recur across the whole book: immutability (data that never changes needs no locks — the functional-programming insight, Part 3), isolation (give each thread its own copy, combine results at the end — the map-reduce idea), and message passing (threads/processes own their data privately and communicate by sending copies, never sharing — the model of Go's channels, Erlang's actors, and, scaled up, microservices in Part 10). Notice these are the same ideas as avoiding the shared-cache-line problem in hardware and the shared-database problem in distributed systems — "don't share mutable state" is a principle that pays off at every scale.

This is where "thread-safe" earns its meaning. When a library says a type is "thread-safe," it means its internal critical sections are correctly protected so concurrent calls won't corrupt it. When it says "not thread-safe" (like most collections by default, for speed), it's telling you you must provide the mutual exclusion. Knowing which is which — and that "thread-safe" often costs performance you may not need in single-threaded code — is everyday engineering judgment. And it's why single-threaded runtimes like Node.js are, perversely, simpler and safer for many workloads: with one thread, there are no data races on your application state at all, sidestepping this entire chapter's hazards (at the cost of the parallelism discussed in 2.3).

Next chapter: we've assumed each process has its own private memory, and that threads share it — but how does the OS give every process the illusion of its own vast, private address space on a machine with limited physical RAM, while keeping them perfectly isolated? That's virtual memory, one of the most ingenious abstractions in all of computing, and Chapter 2.5 builds it from the ground up.

Recall

• A race condition is a bug where correctness depends on thread timing: count++ is really load-add-store, and two threads interleaving inside that critical section can lose an update. Races are non-deterministic, invisible in testing, and worsen under load.
• A mutex (lock) enforces mutual exclusion — at most one thread in the critical section — built on hardware atomic instructions (compare-and-swap). A semaphore is a counting generalisation (allow up to N through), also usable for signalling; a condition variable lets a thread sleep efficiently until a condition holds (the producer–consumer backbone — always re-check the condition in a while loop).
• Deadlock = threads frozen forever, each holding a resource the other needs. It needs all four Coffman conditions (mutual exclusion, hold-and-wait, no preemption, circular wait); break any one — most practically, impose a global lock ordering to kill circular wait.
• Locks serialise, so they cost parallelism (Amdahl's Law); minimise critical sections and lock contention.
• The best synchronisation is none: prefer immutability, isolation, and message passing over shared mutable state — the same principle that pays off in caches (1.6) and distributed systems (Part 10).

Self-test: Why is count++ unsafe across two threads, in terms of machine instructions? How does a mutex fix it, and what hardware feature makes the mutex itself safe? How does a semaphore differ from a mutex? Name the four conditions for deadlock and the most practical one to break. Why do locks limit how much extra cores can help?

Quiz Bank

FoundationalWhat is a race condition? Give the classic example.

A race condition is a bug whose outcome depends on the timing/interleaving of concurrent threads. Classic example: two threads each incrementing a shared count a million times. Because count = count + 1 compiles to three instructions (load, add, store), the scheduler can interrupt one thread between them, so both read the same old value, both compute the same new value, and one increment is lost. The final total is unpredictably less than expected. The unsafe region (the read-modify-write) is the critical section; the root cause is that it isn't atomic.

FoundationalWhat is a mutex and how does it prevent a race condition?

A mutex (mutual-exclusion lock) is an object with lock() and unlock() such that at most one thread holds it at a time. A thread locks before its critical section and unlocks after; if another thread already holds the lock, the caller blocks (sleeps) until it's released. This guarantees only one thread executes the critical section at once, so the load-add-store of a shared counter runs to completion atomically with respect to other threads — eliminating the interleaving that caused the lost update.

AppliedIf checking-and-taking a lock is itself a read-modify-write, how can a mutex be implemented safely?

Via hardware atomic instructions — CPU operations like compare-and-swap (CAS) or test-and-set that perform a read-modify-write as a single, indivisible step the hardware guarantees no other core can interrupt. The mutex's acquire is built on these: e.g. atomically "if the lock is 0, set it to 1 and report success." Because the atomicity is enforced in silicon (across all cores, respecting cache coherence — 1.6), the mutex above it is safe. These same primitives also enable lock-free data structures that coordinate purely via CAS without blocking.

AppliedHow does a semaphore differ from a mutex, and when would you use one?

A mutex is binary (locked/unlocked) and has ownership (the locker should unlock). A semaphore is a counter initialised to N, with wait (decrement, block if it would go negative) and signal (increment, wake a waiter) — it lets up to N threads proceed, and has no ownership, so any thread can signal it. Use a semaphore to limit concurrency to a fixed capacity (e.g. at most 5 simultaneous DB connections or downloads), or to signal between threads (a producer signalling a consumer). A binary semaphore (N=1) resembles a mutex but lacks ownership semantics.

InterviewWhat is a deadlock, and what four conditions are required for it?

A deadlock is when two or more threads are each blocked forever, waiting for a resource the other holds. It requires all four Coffman conditions simultaneously: (1) mutual exclusion (resources are non-shareable), (2) hold and wait (a thread holds one resource while waiting for another), (3) no preemption (resources can't be forcibly taken), and (4) circular wait (a cycle of threads each waiting on the next). Since all four are necessary, preventing deadlock means denying at least one — most practically, imposing a global lock ordering so all threads acquire locks in the same order, breaking circular wait.

InterviewWhy must you re-check a condition variable's predicate in a while loop rather than an if?

Because a waiter can wake when the condition doesn't actually hold. Two reasons: spurious wakeups (permitted by the standards — a wait may return without any signal, for implementation-efficiency reasons) and stolen wakeups (between your wake and re-acquiring the mutex, another thread consumed the item/state you were signalled about). An if would proceed on a false assumption (e.g. dequeue from an empty queue); a while re-checks the predicate after every wake and only proceeds when it genuinely holds. Hence the rule: while (!condition) cond.wait();.

StaffA multithreaded service scales well up to 8 threads then plateaus — adding more threads gives no speedup despite idle CPU capacity. Diagnose using this chapter.

The likely culprit is lock contention serialising the work — an instance of Amdahl's Law. If a significant fraction of each request runs inside a shared critical section (one hot mutex over a shared cache, counter, or connection pool), then threads queue for that lock and effectively run that portion one at a time no matter how many cores exist; beyond the point where the lock is saturated, more threads just wait, so throughput plateaus (and can worsen from context-switch and wakeup overhead). Diagnose by profiling for lock wait time / contention (e.g. perf, lock profilers) and checking whether threads are Blocked on a mutex rather than Running. Fixes, in order of preference: shrink the critical section (hold the lock for fewer instructions, do expensive work outside it); use fine-grained locking (shard the data so threads lock disjoint pieces — e.g. striped locks / a concurrent map) to reduce collisions; replace the lock with lock-free/atomic operations for simple shared state (e.g. an atomic counter); or eliminate the sharing via immutability/per-thread state/message passing. The staff framing: past a point, the bottleneck isn't CPU, it's the serial fraction, and only reducing shared mutable state removes it.

Flashcards

FlashWhy is count++ not thread-safe?

It's load-add-store (three instructions); two threads can interleave, both read the old value, and one increment is lost — a race condition.

FlashMutex vs semaphore

Mutex: binary, owned, one holder — mutual exclusion. Semaphore: counter (N), unowned — allows up to N through, and can signal between threads.

FlashWhat makes a mutex itself safe?

Hardware atomic instructions (compare-and-swap / test-and-set) that do a read-modify-write indivisibly across all cores.

FlashCondition variable rule

Pair it with a mutex; always re-check the predicate in a while loop after wait (spurious/stolen wakeups). Backbone of producer–consumer.

FlashFour Coffman conditions for deadlock

Mutual exclusion, hold-and-wait, no preemption, circular wait — all four needed; break one (usually via global lock ordering).

FlashAmdahl's law intuition for locks

The serial fraction (time under locks) caps speedup: 10% serial ⇒ at most 10× even with infinite cores. Minimise critical sections.

FlashBest way to avoid concurrency bugs

Avoid shared mutable state: prefer immutability, per-thread isolation, or message passing over locking.

Scenario Drill

DrillTwo bank-transfer operations run concurrently: transfer(A→B) and transfer(B→A). Each locks the source account, then the destination, then moves money. Occasionally the whole service hangs. Explain the bug and give two fixes.

This is a textbook deadlock from inconsistent lock ordering. transfer(A→B) locks A then wants B; transfer(B→A) locks B then wants A. If they run at the same time, the first holds A and waits for B while the second holds B and waits for A — the circular wait closes and both hang forever (satisfying all four Coffman conditions). It's intermittent because it only manifests when the two transfers interleave at just the wrong moment.

Fix 1 — global lock ordering (preferred): always acquire the two account locks in a fixed standard order regardless of transfer direction — e.g. by account ID (lock the lower-numbered account first, then the higher). Now both transfers try A before B, so no cycle can form; this deterministically eliminates the deadlock.

Fix 2 — lock with timeout / try-lock: attempt to acquire both locks with a timeout; if the second can't be taken, release the first, back off a random interval, and retry — breaking hold-and-wait. (Timeouts are more forgiving but waste work on retries and can livelock under heavy contention, so ordering is cleaner when feasible.) Deeper design note: at real scale you'd avoid holding two locks across the transfer at all — model it as an atomic transaction in the database (Part 7), or as an event/saga (Part 10.8) — because "lock two things at once" is exactly the pattern that breeds deadlocks.