Races, deadlocks, starvation and cancellation

Why it matters

Concurrency bugs pass tests for months and then fail under production load, during a deploy or on a machine with more cores. They are expensive because they are hard to reproduce, and fixes often create new ones: a lock that removes a race introduces a deadlock, and a timeout that breaks the deadlock introduces a livelock. Interviewers use them to see whether you reason systematically: classify the bug, find the invariant that was violated, and choose a fix with known costs. The same thinking applies to async code, agent pipelines and distributed systems, where cancellation and shutdown are frequent sources of leaks and hangs.

Core ideas

Race condition versus data race. A race condition is a semantic bug: the result depends on timing. A data race is a language-level property: two threads access the same location, at least one writes, and nothing orders the accesses. The two overlap but differ. A bank account whose balance() and withdraw() are each locked has no data race, yet still has a race condition if the check and the withdrawal are separate critical sections. A data race in C or C++ is undefined behavior even when it looks harmless; the compiler may hoist a load out of a loop and spin forever.

The two big non-deadlock patterns. Studies of real bugs find that most non-deadlock bugs are atomicity violations, where code assumed a sequence was indivisible (check-then-act, read-modify-write), or order violations, where code assumed one thread's action happened before another's (using an object before its initialization is published). Fix atomicity violations by widening the critical section or using an atomic operation that covers the whole step; fix order violations with an explicit happens-before edge such as a condition variable, a join or a future.

Deadlock requires four conditions at once: mutual exclusion, hold-and-wait, no preemption and circular wait. Break any one:

• Circular wait: impose a global lock order (by rank, or by address for dynamic pairs) and never call unknown code such as callbacks while holding a lock. This is the usual practical answer.
• Hold-and-wait: acquire all needed locks up front, or under one guard lock.
• No preemption: use try-lock and, on failure, release everything and retry. Add randomized backoff, or two threads can retry in lockstep forever, which is livelock.

Databases take another route: they detect cycles in a wait-for graph and abort a victim transaction.

Deadlocks without obvious locks. A bounded thread pool whose tasks block waiting for other tasks queued behind them; an async handler that blocks the event-loop thread on a future that needs that same loop to complete; a child created by fork() in a multithreaded program inheriting a mutex held by a thread that does not exist in the child.

Starvation and priority inversion. Unfair locks, reader-preferring readers-writer locks and strict priorities can starve a thread indefinitely. Priority inversion occurs when a low-priority thread holds a lock that a high-priority thread needs while medium-priority work keeps the holder off the CPU; priority inheritance is the standard fix.

Cancellation. Killing a thread asynchronously can leave locks held and invariants half-updated, which is why asynchronous pthread_cancel is almost never safe. Cooperative cancellation passes a token or deadline down the call chain: blocking operations accept it, code checks it at safe points, and cleanup runs in finally, defer or destructors. Structured concurrency (task groups, nurseries) guarantees that child tasks finish or are cancelled before their parent scope exits, so nothing leaks. Never swallow a cancellation signal, and make cleanup idempotent.

Common misconceptions

• "No data races means no race conditions." Separately locked steps can still interleave badly.
• "A deadlocked process burns CPU." Deadlocked threads usually sleep at zero CPU; high CPU without progress suggests livelock or spinning.
• "Timeouts fix deadlocks." They turn a hang into failures and retries, can cause livelock, and leave the lock-order bug in place.
• "Killing the thread is a clean way to stop work." It skips cleanup and can corrupt shared state; cancel cooperatively.
• "Tests passed, so there are no races." Rare interleavings need race detectors, stress runs and schedule perturbation; absence of failure is weak evidence.
• "Some data races are benign." In C and C++ every data race is undefined behavior; use relaxed atomics if you need an access that looks unsynchronized.

How to approach it

When you meet a bug, first name its class (atomicity, order, deadlock, livelock, starvation, leak on cancellation), then the invariant that broke, then the fix and its cost. For hangs, take two thread dumps a few seconds apart and draw who holds what and who waits for what. Run code under ThreadSanitizer or your language's race detector as a habit. Graduate interviews focus on the deadlock conditions and dining philosophers; mid-level ones on diagnosis and lock ordering in real code; senior ones on cancellation and shutdown design across services and on hangs involving thread pools or async runtimes.