Skip to main content

Problems with Lock-Based Concurrency

Adapted from: Jason Gregory, Game Engine Architecture, 3rd ed. (CRC Press, 2018), Chapter 4, Section 4.7 — rewritten and condensed for teaching.

Thread Synchronization Primitives covered how mutexes, condition variables, and semaphores make operations atomic and let threads coordinate. But eliminating data races is only part of writing correct concurrent software — a program where every shared access is perfectly locked can still hang forever, spin uselessly, starve one thread indefinitely, or let a low-priority thread block a high-priority one. This lesson works through the four classic lock-based failure modes: deadlock, livelock, starvation, and priority inversion — plus the field's favorite illustration of all of them at once, the dining philosophers.

Deadlock​

Deadlock is the situation where no thread in the system can make progress — every thread is blocked, waiting on some resource, but because nothing is runnable, none of those resources can ever be released. The whole program just hangs.

Deadlock needs at least two threads and two resources:

void Thread1() {
    g_mutexA.lock();   // holds Resource A
    g_mutexB.lock();   // sleeps, waiting for Resource B
    // ...
}

void Thread2() {
    g_mutexB.lock();   // holds Resource B
    g_mutexA.lock();   // sleeps, waiting for Resource A
    // ...
}

If Thread1 grabs g_mutexA right as Thread2 grabs g_mutexB, each thread now holds exactly the resource the other one needs next — and neither will ever release what it's holding, because doing so requires finishing the function, which requires the other lock first. Neither thread ever gets there.

You can spot this pattern visually with a dependency graph: draw a node per thread and per resource, a solid arrow from a resource to whichever thread currently holds it, and a dashed arrow from a thread to whichever resource it's waiting on. (You can even drop the resource nodes and draw dashed arrows directly thread-to-thread.) A cycle in this graph means deadlock.

The Coffman Conditions​

Strictly speaking, a cycle alone isn't quite sufinent — deadlock requires all four Coffman conditions to hold simultaneously:

  1. Mutual exclusion — a resource can only be held by one thread at a time.
  2. Hold and wait — a thread holds one lock while sleeping, waiting on another.
  3. No preemption — nobody (not even the kernel) can forcibly strip a lock away from a sleeping thread.
  4. Circular wait — a cycle exists in the wait-for graph.

Breaking condition #1 or #3 would generally defeat the purpose of having locks at all — so real fixes target #2 or #4:

  • Avoid hold-and-wait by reducing the number of distinct locks. If Resource A and Resource B in the example above were protected by a single lock, deadlock becomes structurally impossible — whichever thread gets the one lock first simply gets exclusive access to both resources while the other waits.
  • Avoid circular wait by imposing a global lock ordering. If every thread in the system agrees to always acquire Resource A's lock before Resource B's lock — never the other way around — no cycle can ever form, because one thread reaching for A first will always put any contending thread to sleep before it can reach for B out of order.

Check: deadlock​

Quiz

Deadlock and the Coffman conditions

1 / 3

In the classic two-thread, two-mutex deadlock example, what specifically causes the hang?

Pick an answer to see if you are right.

Livelock​

One tempting way to avoid deadlock is to never sleep waiting for a contested lock — instead try a non-blocking try_lock(), and if it fails, release whatever you already hold and retry after a short delay. That sidesteps deadlock, but opens the door to a different problem: livelock, where threads spend all their time trying (and failing) to resolve the very conflict their retry strategy created, making zero actual progress — the concurrent-programming equivalent of two people repeatedly stepping the same direction trying to get out of each other's way in a hallway.

Concretely: if Thread1 and Thread2 both back off and retry after the same fixed timeout whenever they collide, they can end up perfectly resynchronized every single time — colliding, backing off, and colliding again, forever, like a stalemate in chess.

The fix is asymmetry: make the retry strategy break the tie somehow — for example, only ever let one specific thread (chosen by priority, or at random) take the active steps to resolve a detected conflict, while others simply wait for it to succeed.

Starvation​

Starvation is any situation where one or more threads never get any CPU time at all. It commonly arises when higher-priority threads simply never yield the CPU long enough for lower-priority ones to run — and livelock is really a special case of starvation, where a deadlock-avoidance algorithm accidentally starves every thread of real work by keeping them all busy resolving conflicts instead.

The usual mitigation for priority-based starvation: keep high-priority threads short-lived. A healthy design generally has a pool of lower-priority threads sharing the CPU fairly most of the time, with occasional short bursts from higher-priority threads that finish quickly and hand control back.

Check: livelock and starvation​

Quiz

Livelock and starvation

1 / 3

How does livelock differ from deadlock, given that both result in a program failing to make real progress?

Pick an answer to see if you are right.

Priority Inversion​

Priority inversion is a subtler problem: a low-priority thread can end up effectively blocking a high-priority one, even though the scheduler is supposed to always prefer higher-priority work.

Concretely: threads L (low priority) and H (high priority) share a lock. L takes the lock, then gets preempted by H. If H now also wants that same lock, H goes to sleep waiting for L — which means L gets to keep running (to finish and release the lock) even though a higher-priority thread is sitting there ready to run. For that stretch, L is effectively behaving as if it were the highest-priority thread in the system.

It gets worse with a third, medium-priority thread M in the mix: if M preempts L while L still holds the lock H needs, L can't run (because M is running instead) and therefore can't release the lock — so now H is blocked not by L directly, but transitively by M, a thread with lower priority than H. M's priority has effectively been inverted with H's.

Consequences range from negligible (if L releases the lock almost immediately) to severe — in the worst case, priority inversion has caused real high-priority threads to miss hard deadlines. Common fixes:

  • Avoid locks shared between low- and high-priority threads entirely (often not realistic).
  • Priority ceiling / priority inheritance — temporarily boost the priority of whoever holds the lock up to the priority of the highest-priority thread waiting on it, so it can't be preempted by anything in between.
  • Random priority boosting — periodically and randomly boost the priority of threads that are actively holding locks until they release them; this is the general approach the Windows scheduler uses.

Check: priority inversion​

Quiz

Priority inversion

1 / 3

In the basic two-thread priority inversion scenario, why does the high-priority thread H end up waiting on the low-priority thread L?

Pick an answer to see if you are right.

Practice: avoid deadlock with a global lock order​

Here's the classic real-world instance of the deadlock pattern: transferring funds between two accounts, each guarded by its own mutex. If Transfer(A, B, ...) always locks A then B, but some other thread calls Transfer(B, A, ...) at the same time (locking B then A), you have the exact circular-wait shape from earlier in this lesson.

Fix Transfer() below so it locks the two accounts' mutexes in a consistent global order — by comparing their id fields — regardless of which account is passed as from and which is to. That way, no matter which order two concurrent transfers name their accounts in, every thread agrees on which lock to take first.

What this exercise can (and can't) verify

This sandbox runs your code single-threaded, so it can't literally trigger or detect a live deadlock the way two real concurrent threads calling Transfer() in opposite orders would. What it can verify is that Transfer() still computes the correct balances — and the source check confirms you actually compare the two accounts' ids to decide lock order, rather than always locking in call-argument order (which is exactly the pattern that deadlocks once a second thread calls the function with the arguments reversed).

The Dining Philosophers​

The dining philosophers problem packs deadlock, livelock, and starvation into one famous scenario: five philosophers sit around a circular table, one chopstick between each adjacent pair (five chopsticks total). Each philosopher alternates between thinking (needs no chopsticks) and eating (needs the two chopsticks on either side of their plate). The puzzle: define behavior so every philosopher can keep alternating between thinking and eating forever, without deadlock, livelock, or starvation. (Philosophers are threads; chopsticks are mutexes.)

If every philosopher always picks up their left chopstick first, then reaches for their right, you get the textbook circular-wait deadlock — every philosopher ends up holding one chopstick, and permanently waiting on their neighbor. A few well-known fixes:

  • Global order — number the chopsticks, and require every philosopher to always pick up the lower-numbered one first, regardless of which side it's on. This is exactly the global-lock-ordering fix from earlier in this lesson, applied to five resources arranged in a circle.
  • Central arbiter — a "waiter" hands out chopsticks and only ever grants a philosopher both at once (or none) — directly preventing the "hold and wait" condition, since no philosopher can ever be left holding just one.
  • Chandy–Misra — chopsticks are marked clean/dirty, and philosophers explicitly request them from each other via messages; worth reading about separately if you want the full algorithm.
  • N−1 philosophers — with 5 philosophers and 5 chopsticks, use a semaphore to ensure at most 4 philosophers are ever allowed to pick up chopsticks simultaneously. This guarantees at least one of the five will always be able to complete a pair — solving deadlock and livelock — though it can still let one unlucky philosopher starve unless you add an explicit fairness rule on top.

Check: dining philosophers​

Quiz

The dining philosophers problem

1 / 3

Why does "every philosopher always picks up their left chopstick first" lead to guaranteed deadlock?

Pick an answer to see if you are right.

Key takeaways
  • Deadlock requires all four Coffman conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) — practical fixes target hold-and-wait (fewer locks) or circular wait (a consistent global lock order).
  • Livelock happens when threads actively avoid deadlock but end up doing nothing but retry/backoff forever — fixed by breaking the symmetry in how conflicts get resolved.
  • Starvation means a thread never gets CPU time at all; keeping high-priority threads short-lived is the standard mitigation, and livelock is really starvation caused by a conflict-avoidance algorithm itself.
  • Priority inversion lets a low- (or even medium-, transitively) priority thread block a high-priority one through a shared lock; priority inheritance/ceiling protocols and random priority boosting (used by Windows) are the standard fixes.
  • The dining philosophers problem packs all of the above into one scenario, and its classic solutions (global order, central arbiter, Chandy-Misra, N-1 philosophers) map directly onto the general deadlock/starvation-avoidance techniques covered in this lesson.

Further Reading​