Concurrency problems: races, deadlocks, and the fixes

Table of Contents

Algorithms — running many things at once

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, translatedPhilosopher → 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 protocolthink(); 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 wrongDeadlock 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

How to read this. A solid line means a philosopher holds that fork; a dashed red line means they are waiting for it. A fork chip on the table is gold while it is free and takes its holder’s colour once taken. In the panel, “holds” lists the forks in each philosopher’s hands — deadlock is the state where every row reads “holds 1 fork, waiting” and the waiting lines form a complete ring.

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

Click a philosopher to select them.
How to read this. The selected philosopher is ringed in ink, and the two forks they can reach — their left fork and their right fork — are outlined with a dashed border. A solid line means a philosopher holds that fork. A fork chip on the table is gold while it is free and takes its holder’s colour once taken. The panel lists what each philosopher holds and how many meals they have begun.

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

How to read this. Blue is Thread 1, orange is Thread 2, the centre box is shared memory. A thread’s register is private — that privacy is exactly what makes the stale read possible. With the mutex on, the lock badge shows who holds the critical section and who is blocked outside it.

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 showntotal time on 1 core=Tserial fraction=sparallel fraction=1−stime onncores=sT+(1−s)Tnspeedup=TsT+(1−s)Tn=1s+1−snasn→∞:speedup→1s
Worked checks=0.10,n=8speedup=10.10+0.908=10.10+0.1125=10.2125≈4.71and even with infinitely many cores the ceiling is10.10=10×

Drag both sliders and watch the bars. The practical lesson of every profiling session is in this picture: shrinking the critical section (smaller s) 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

How to read this. The teal bar is the real speedup from Amdahl’s law; the outline bar is the naive hope (one extra core, one extra unit of speed). The gap between them is time threads spend queued at the mutex.

Contention explorer

4.71×actual speedup
10.0×ceiling as threads → ∞
59%core efficiency

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 exclusionA 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 waitA thread holds one resource while waiting for another. Removed by acquiring all locks at once, or by try-lock-and-release.
3. No preemptionA held resource cannot be forcibly taken away; only the holder releases it.
4. Circular waitA 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

How to read this. Solid arrows mean holds; dashed arrows mean waiting for. In the wait-for graph at the right, an arrow T1 → T2 means “T1 waits for a lock T2 holds”. A cycle there is a deadlock — this is also exactly how deadlock detectors in databases work: build the graph, look for a cycle, abort one victim transaction and roll it back.

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 lockdep proves 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

How to read this. Each bar is quanta actually run out of 30. Starvation is not “slow” — it is the limiting case where a runnable thread’s share tends to zero while the system looks healthy.

Starvation simulator

5quanta run by Low
5longest wait for Low
At riskstarvation verdict

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%

Deadlock vs livelock vs starvation. Deadlock: threads blocked, no progress, no CPU burn. Livelock: threads running, no progress, CPU burning. Starvation: the system progresses, one thread does not. The fixes differ accordingly — ordering, symmetry-breaking, and fairness.

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 t=10. Then tick priority inheritance: while H waits, L temporarily inherits H’s priority, M can no longer preempt it, L finishes at t=5, 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

How to read this. Each row is one task; a filled segment is time actually running, a hatched segment is H blocked on the lock. The dashed marker is the time you have dragged to. The lock badge follows L until it releases.

Timeline explorer

Running (L)who runs now
8 unitsH total blocked time
t = 11H finally runs

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 N admits up to N 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 stepempty+full=capacity3+0=3at the start (Figure 7, step 0)1+2=3at the fullest point below (step 3)
The protocolProducer: 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

How to read this. Slots fill left to right and drain oldest-first (a queue). The two counters are the semaphores; whenever the producer faces a full buffer or the consumer an empty one, the corresponding 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

How to read this. Each thread carries its expected value — what it read. CAS succeeds only when memory still matches the expectation. A failure is not an error; it is the mechanism working, and the retry loop is the price of admission.
The ABA problem: CAS’s blind spotA 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 strongestObstruction-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 losesWins: 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.

ProblemSymptomRoot causeWorked fixes
Race conditionWrong result, intermittently; heisenbug vanishes under a debuggerNon-atomic read–modify–write split by an interleavingMutex around the critical section (Fig. 1); atomic / CAS update (Fig. 8); confine data to one thread
DeadlockTotal freeze, zero CPU, threads blocked foreverCycle 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
StarvationSystem healthy, one thread never runsUnfair granting: the same winners keep winningFIFO fair locks and queues (Fig. 4); ageing; bounded bypass for writers
Livelock100% CPU, constant state changes, zero progressSymmetric reactions: retries in perfect lockstepRandomised exponential backoff (Fig. 5); jitter; one designated thread yields longer
Priority inversionHigh-priority task misses deadlines behind unrelated medium workLow-priority lock holder preempted by medium-priority threadsPriority inheritance (Fig. 6); priority ceiling; lock-free handoff queues
ToolGuaranteeBlocks?Reach for it when
MutexOne thread in the critical sectionYes: waiters sleepDefault choice for protecting shared mutable state
SemaphoreAt most N permit holdersYes: when permits run outResource pools, bounded buffers (Fig. 7), rate limiting
Condition variableSleep until a state predicate may holdYes: releases the mutex while asleepProducer–consumer and state-machine waiting inside locked code
Atomic / CAS loopSingle-word update is indivisibleNo: retries insteadCounters, flags, lock-free stacks and queues (Fig. 8)
Message passingNo shared mutable state at allOnly on an empty channel, by designActor 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.

Concurrency Problems in Algorithms — an interactive explainer. All simulations run in your browser: the race, deadlock, livelock, bounded-buffer and CAS steppers execute the exact schedules described in their notes, and the starvation, contention and priority-inversion figures compute their readouts from the slider values shown.