Concurrency problems: races, deadlocks, and the fixes
A single-threaded program has one story: each line runs, then the next. Add a second thread and the stories interleave — and almost every classic bug in concurrent code is a bad interleaving. Two increments can lose one update. Two threads can each wait forever for the other. A polite program can dance forever without moving. A low-priority thread can hold up the most important task in the system. This page builds each failure live, in a stepper or simulator you control, then applies the standard fix in the same picture: mutexes, lock ordering, fair queues, randomised backoff, priority inheritance, semaphores, and lock-free compare-and-swap.
The one-sentence idea. Concurrency bugs are rarely about a wrong line of code — they are about a schedule you did not imagine, so every fix works by removing bad schedules: serialising a critical section, ordering lock acquisition, bounding waits, breaking symmetry, or making an update atomic so no schedule can split it.
1 — The dining philosophers: every problem at one table
Edsger Dijkstra posed this problem in 1965 (Tony Hoare later gave it its familiar form) to make the dangers of shared resources impossible to ignore. Five philosophers sit around a round table. Each alternates between thinking and eating. In the centre is a bowl of rice; between each pair of neighbours lies a single fork — five forks in total. To eat, a philosopher needs both forks beside their plate: the one on their left and the one on their right. A fork can be held by only one philosopher at a time. When finished eating, a philosopher puts both forks down and goes back to thinking.
Read the table as code and it is the whole of this page in miniature. A philosopher is a thread. A fork is a lock guarding a shared resource. Eating is a critical section that needs two locks at once. Thinking is work that needs no locks at all. The obvious protocol — pick up your left fork, then pick up your right fork, eat, put both down — looks harmless for one philosopher. Run five copies at once and a schedule exists in which nobody ever eats again.
| The cast, translated | Philosopher → thread or process. Fork → lock / shared resource (mutual exclusion: one holder at a time). Needs both forks to eat → a critical section that must hold two locks at once. Waiting with one fork in hand → hold-and-wait, one of the four Coffman conditions for deadlock in Step 3. |
|---|---|
| The naive protocol | think(); take(left fork); take(right fork); eat(); put down both forks;, with take() blocking until the fork is free. Every philosopher runs exactly this code, in exactly this order. |
| What can go wrong | Deadlock if all five pick up their left fork at once: each holds one fork and waits forever for a neighbour’s fork. The same table can also show starvation (a philosopher whose neighbours keep alternating so one fork is always taken). That is why a correct solution must guarantee not just that someone can eat, but that everyone eventually does. |
Step through the naive protocol below and watch the wait cycle close — each philosopher waiting on the next, all the way around the table and back to the start. Then tick the fix and step again. The fix changes only one philosopher’s code: Philosopher 5 picks up forks in the opposite order (right fork first). That single asymmetry means Philosopher 5 and Philosopher 1 contend for the same first fork, so one of them starts empty-handed instead of holding a fork hostage — the circle can never close, and the meal works its way around the table.
Intro figure: Naive protocol, step 0 of 3: all five thinking, all forks on the table
The stepper above runs one fixed schedule. The table below has no script at all — you are the scheduler. Click a philosopher to select them, then click one of the two forks beside their plate to pick it up; click a fork they already hold to put it back down. Forks that are not beside the selected philosopher, or are already in someone else’s hand, refuse to move — and the box under the diagram explains, after every click, exactly what state the table is in and why. Try to feed everyone. Then try to recreate the deadlock from the scripted run with your own clicks: give every philosopher exactly one fork.
Try it yourself: no forks held, nobody eating
Why this one problem previews the whole page
- Deadlock (Step 3) is the closed ring of waiting below: all four Coffman conditions hold at once — forks are exclusive, philosophers hold-and-wait, forks cannot be preempted, and the wait is circular.
- The fix is lock ordering in disguise (Step 3 again). Reversing one philosopher’s pickup order is the dining-table version of a resource hierarchy: it breaks circular wait, the one Coffman condition that ordering can remove.
- Other classic fixes exist. A waiter (arbitrator) who seats at most four philosophers at once guarantees at least one diner can always get both forks. Letting a philosopher pick up both forks only if both are free (and putting the first back otherwise) removes hold-and-wait. Each fix buys progress by removing a different Coffman condition.
- Deadlock-free is not starvation-free. The asymmetric protocol below cannot deadlock, but an unlucky philosopher can still be repeatedly beaten to a fork — the fairness problem of Step 4 needs its own guarantee on top.
2 — Race conditions: the lost update
A race condition is any bug whose presence depends on the relative timing of threads. The canonical example fits in three lines. Incrementing a shared counter looks like one operation, but the machine does it in three: read the value into a register, add one, write it back. If two threads interleave inside that window, both read the same starting value, both write the same result — and one increment simply vanishes. No line is wrong. The schedule is wrong.
// executed by both threads, counter starts at 0 reg = counter; // READ reg = reg + 1; // ADD counter = reg; // WRITE
Step through the bad schedule below. Then tick protect with a mutex and step again: the same three lines now run inside a critical section, the second thread is forced to wait at the door, and both increments land. Figure titles track the schedule as you step.
Figure 1: No mutex, step 0 of 5: counter = 0
Why this generalises
- Check-then-act is the same shape:
if (x == null) x = make()races when two threads both pass the check. - The window is tiny but real. A context switch can land between any two machine instructions, so “it never happens in testing” means only that the bad schedule is rare.
- A data race is worse than a wrong answer. In C and C++ a data race is undefined behaviour; in Java it can tear a 64-bit write into two 32-bit halves. The fix is never “hope” — it is synchronisation or an atomic.
3 — Mutexes: the fix, and its price
A mutex (mutual exclusion lock) admits exactly one thread into a critical section at a time. Everyone else blocks at lock() until unlock(). That one guarantee — the three-line increment can no longer be split — is what repaired Figure 1. But serialising has a price: the critical section is, by definition, work that cannot be parallelised, and it caps your speedup no matter how many cores you buy. That cap is Amdahl’s law.
| Amdahl’s law: every step shown | |
|---|---|
| Worked check |
Drag both sliders and watch the bars. The practical lesson of every profiling session is in this picture: shrinking the critical section (smaller ) beats adding threads, every time. Keep locks fine-grained — one per data structure, or per shard — hold them for the shortest possible region, and never hold one across I/O or a call into code you do not control.
Figure 2: 8 threads, 10% serial: speedup 4.71× of a 10× ceiling
Rules of thumb that prevent most mutex bugs. Acquire with RAII / try-finally so an exception cannot leak a held lock. Never call unknown code while holding a lock. If a thread needs two locks, you have just met the next section.
4 — Deadlock: the circular wait
A deadlock is a set of threads each waiting for a resource held by the next, in a cycle, forever. Nobody is running, nobody will ever run, and no timeout inside the threads themselves can fire because no thread is executing. Coffman’s four conditions are each necessary — break any one and deadlock is impossible:
| 1. Mutual exclusion | A resource can be held by only one thread at a time. (Hard to remove; it is usually the point of the lock.) |
|---|---|
| 2. Hold and wait | A thread holds one resource while waiting for another. Removed by acquiring all locks at once, or by try-lock-and-release. |
| 3. No preemption | A held resource cannot be forcibly taken away; only the holder releases it. |
| 4. Circular wait | A cycle exists in the wait-for graph. Removed by a global lock order: every thread acquires locks in the same agreed order, so a cycle can never close. |
Step through the classic two-lock tangle, then tick the fix — a global order, lock A before lock B, always — and step again. The second thread now blocks on its very first lock instead of completing the cycle. Tick the wait-for graph layer on or off to see the deadlock as a graph property: a cycle.
Figure 3: Opposite lock orders, step 0 of 4: no locks held
Other ways to break the four conditions
- Timeouts and try-lock: if a thread cannot get a second lock within a deadline, it releases the first and retries — hold-and-wait is broken because the wait is bounded and the hold is surrendered.
- Lock hierarchy in real systems: the Linux kernel documents a global locking order and
lockdepproves at runtime that no code path violates it. - One lock to rule them: a single coarse lock cannot deadlock with itself — you pay Amdahl’s price from Step 2 instead. Choosing between deadlock risk and contention is the recurring trade of this whole page.
5 — Starvation: runnable, but never chosen
Starvation is quieter than deadlock: the system as a whole makes progress, most threads make progress — but one thread is perpetually passed over. A reader–writer lock that always prefers readers can starve a single writer under a steady stream of readers. An unfair mutex can re-grant the lock to the thread that just released it, because it is still hot in cache, while a waiting thread never gets scheduled onto the lock at all.
The simulator below runs 30 scheduling quanta shared by two “hog” threads and one low-demand thread, Low. Drag the scheduler’s bias toward the hogs and watch Low’s bar shrink to nothing — that is starvation, no cycle and no bug in Low’s code. Then tick the fair FIFO queue: the lock (and the CPU) is granted strictly in arrival order, Low is guaranteed a turn within two quanta, and starvation is impossible by construction.
Figure 4: Scheduler bias 50%: Low runs 5 of 30 quanta
The general fixes
- Fairness queues: FIFO-ordered locks and schedulers bound every wait by the number of threads ahead of you.
- Ageing: a waiting thread’s effective priority rises with time waited, so even a biased scheduler must eventually pick it — the same idea reappears in Step 6.
- Bounded bypass: reader–writer locks that stop admitting new readers once a writer is queued cap the writer’s wait at the current reader count.
6 — Livelock: busy, polite, and stuck
In a livelock nobody is blocked — that is what makes it insidious. Two threads keep reacting to each other, changing state constantly, burning CPU, and making zero progress. The everyday picture is two people in a corridor who both step left, then both step right, then both step left, forever. Code does the same thing when two threads each politely release a lock and retry in perfect lockstep, or when two network nodes retransmit in synchronised bursts after every collision.
Step through the corridor dance: the attempt counter climbs, the progress bar never moves. Then tick randomised backoff — each robot waits a random delay before retrying — and step again. Randomness breaks the symmetry: one robot happens to wait longer, the other walks through, and the system escapes. This is precisely why Ethernet, Wi-Fi, and TCP all back off exponentially and randomly after a collision.
Figure 5: Lockstep retries, attempt 0: progress 0%
7 — Priority inversion: the important thread waits on the wrong one
Real-time systems rank threads by priority and always run the highest-priority runnable thread. Now suppose the low-priority thread L holds a lock, and the high-priority thread H wakes and needs that lock. H blocks — correctly — waiting for L. But a medium-priority thread M, which needs nothing, is now the highest-priority runnable thread, so it preempts L. L cannot finish its critical section, so H cannot run. H, the most important thread in the system, is effectively waiting on M — a thread it outranks and that has nothing to do with the lock. Priority has been inverted, for as long as medium-priority work keeps arriving: potentially forever.
This bug nearly ended a Mars mission. In July 1997 the Mars Pathfinder lander began resetting itself, losing data, a few days after landing. Engineers traced it to exactly this pattern in the VxWorks real-time OS: a low-priority data-gathering task held a bus mutex, a high-priority bus task blocked on it, and medium-priority communications tasks kept preempting the low one. The fix, uploaded to Mars, was to turn on priority inheritance for that mutex.
Drag the time slider. Without inheritance, watch M’s long run push H’s start out to . Then tick priority inheritance: while H waits, L temporarily inherits H’s priority, M can no longer preempt it, L finishes at , and H’s wait shrinks from 8 time units to 3. Inheritance does not make H wait-free — it bounds H’s wait by one critical section, which is the best any lock can promise.
Figure 6: No priority inheritance, t = 0: L takes the lock
The alternatives
- Priority ceiling protocol: a lock’s holder is raised to the highest priority of any thread that might take the lock — decided in advance. It also prevents deadlock among those locks, at the cost of more blocking for others.
- Remove the lock: hand data between priority levels through a lock-free queue (Step 8) so the high-priority thread never blocks at all.
- What inheritance does not fix: chained blocking (H waits on L, who waits on a lock held by someone else) still adds up — inheritance propagates along the chain, but each critical section still costs time.
8 — Semaphores: counting permits, and the bounded buffer
A mutex answers “may I enter?” with yes or no. A semaphore (Dijkstra) keeps a count of permits. wait() (historically P()) decrements the count, blocking if it would go negative. signal() (V()) increments it, waking a waiter. A mutex is the special case where the count starts at 1; a semaphore starting at admits up to concurrent users of a pooled resource.
Two semaphores plus one mutex solve the classic bounded buffer (producer–consumer) problem with no busy-waiting anywhere: empty counts free slots (starts at capacity), full counts ready items (starts at 0), and the mutex protects the slot array itself for the brief moment of putting or taking. Step through a produce/consume cycle and watch the invariant that makes it correct:
| The invariant: checked at every step | |
|---|---|
| The protocol | Producer: wait(empty), then lock(mutex), put item, unlock(mutex), then signal(full). Consumer mirrors it with wait(full) and signal(empty). Ordering matters: acquiring the mutex before the counting semaphore can deadlock: a thread could hold the mutex while blocked on empty, while the consumer who would free a slot needs that same mutex. |
Figure 7: Bounded buffer, step 0 of 8: empty = 3, full = 0
wait() simply puts that thread to sleep — no spinning, no polling.Condition variables are the close cousin you will meet in pthread_cond_wait and Java’s wait/notify: a thread atomically releases a mutex and sleeps until another thread signals that a condition might now hold — then re-checks it in a loop, because wakeups can be spurious and conditions can be stolen by another waiter. Semaphore, condition variable, and mutex are three faces of one idea: sleep precisely until the state you need is possible.
9 — Lock-free tools: compare-and-swap and the retry loop
Every fix so far still blocks someone. Lock-free programming takes the other path: never hold anything, so nobody can be blocked, deadlocked, or inverted. The workhorse is one atomic hardware instruction, compare-and-swap (CAS): “if the value at this address still equals what I expect, replace it with my new value and tell me; otherwise just tell me.” Read, compute, CAS — and if the CAS fails, someone else won the race, so re-read and retry. The losing thread wastes a spin, but the system always progresses: a failed CAS is proof another thread succeeded. That is the definition of lock-free.
// lock-free increment: no lock taken, ever do { old = counter; // read } while (!CAS(&counter, old, old + 1)); // retry until our swap lands
Step through the two-thread increment rebuilt on CAS. Compare Figure 1: Thread 2’s stale read no longer corrupts anything, because its CAS checks the expected value and fails honestly instead of blindly writing.
Figure 8: CAS increment, step 0 of 6: counter = 10
| The ABA problem: CAS’s blind spot | A thread reads value A. Another thread changes A to B and back to A. The first thread’s CAS succeeds, the value “matches”, yet the world changed underneath it: pointers may have been freed and reused. Fixes: attach a version counter to the value and CAS both together (a tagged pointer), or use hazard pointers / epoch reclamation so memory is never reused while anyone might still hold it. |
|---|---|
| Progress guarantees, weakest to strongest | Obstruction-free: a thread running alone finishes. Lock-free: some thread finishes in any execution, an individual thread can still starve in the retry loop, so Step 4 has not entirely left the building. Wait-free: every thread finishes in a bounded number of steps: strongest, hardest, and what hard real-time code wants. |
| Where lock-free wins, where it loses | Wins: tiny updates (counters, flags, stack push/pop), read-mostly data, interrupt and signal contexts where blocking is forbidden. Loses: multi-field invariants (CAS guards one word, not a relationship between five), heavy contention (the retry storm can cost more than a lock queue), and anywhere a simple mutex is already fast enough: measure first. |
10 — Choosing the tool: a map of the whole page
Every problem above is a bad schedule, and every fix removes a class of schedules. This table is the page on one screen — problem, signature symptom, root cause, and the fix (or fixes) that actually address the cause.
| Problem | Symptom | Root cause | Worked fixes |
|---|---|---|---|
| Race condition | Wrong result, intermittently; heisenbug vanishes under a debugger | Non-atomic read–modify–write split by an interleaving | Mutex around the critical section (Fig. 1); atomic / CAS update (Fig. 8); confine data to one thread |
| Deadlock | Total freeze, zero CPU, threads blocked forever | Cycle in the wait-for graph (all four Coffman conditions) | Global lock order (Fig. 3); try-lock with timeout and back-off; lock hierarchy checking (lockdep); deadlock detection plus victim rollback |
| Starvation | System healthy, one thread never runs | Unfair granting: the same winners keep winning | FIFO fair locks and queues (Fig. 4); ageing; bounded bypass for writers |
| Livelock | 100% CPU, constant state changes, zero progress | Symmetric reactions: retries in perfect lockstep | Randomised exponential backoff (Fig. 5); jitter; one designated thread yields longer |
| Priority inversion | High-priority task misses deadlines behind unrelated medium work | Low-priority lock holder preempted by medium-priority threads | Priority inheritance (Fig. 6); priority ceiling; lock-free handoff queues |
| Tool | Guarantee | Blocks? | Reach for it when |
|---|---|---|---|
| Mutex | One thread in the critical section | Yes: waiters sleep | Default choice for protecting shared mutable state |
| Semaphore | At most permit holders | Yes: when permits run out | Resource pools, bounded buffers (Fig. 7), rate limiting |
| Condition variable | Sleep until a state predicate may hold | Yes: releases the mutex while asleep | Producer–consumer and state-machine waiting inside locked code |
| Atomic / CAS loop | Single-word update is indivisible | No: retries instead | Counters, flags, lock-free stacks and queues (Fig. 8) |
| Message passing | No shared mutable state at all | Only on an empty channel, by design | Actor systems and CSP (Go channels): “share memory by communicating” — most races become unrepresentable |
The discipline underneath every fix. Share as little as possible, lock as briefly as possible, order what you must nest, bound every wait you can, and let randomness break any symmetry you cannot remove. Concurrency does not forgive optimism — but it richly rewards small critical sections and boring, provable protocols.
