Unit 2.5 · about 3 h
244 / 324Deadlock, livelock, starvation and priority inversion
Programming's hazards unit staged a lock-order deadlock in Python. This unit proves why order works: wait-for graphs, the four conditions and the three standard preventions, each run and timed. It assumes that unit as background and replaces its single demo with a proof.
- derive
- explain
You can now
- State the four Coffman conditions and break one deliberately in code.
- Draw a wait-for graph for a two-lock program and prove whether deadlock is possible.
- Separate deadlock, livelock, starvation and priority inversion by the evidence each leaves.
Covers
- Deadlock conditions, wait-for graphs and lock-order proofs
- Livelock, starvation, fairness and priority inversion vocabulary
Study, in this order
6 steps
- Deadlock bugs and their preventionOperating Systems: Three Easy Pieces - concurrency
Section 32.3: the four conditions, attacking circular wait with a total order, hold-and-wait and try-and-back-off
- Dining philosophersOperating Systems: Three Easy Pieces - concurrency
Section 31.6: the cyclic solution that deadlocks and the total-order repair
- DeadlockAlgoMaster Concurrency lessons
Coffman's Four Conditions; How to Prevent Deadlock: lock ordering, try-lock with timeout, all-or-nothing acquisition
- LivelockAlgoMaster Concurrency lessons
Why Livelock Happens; Backoff Strategies; How to Prevent Livelock
- StarvationAlgoMaster Concurrency lessons
Why Starvation Happens; Fair vs Unfair Locks; How to Prevent Starvation
Depth · Read the fairness cases; the ticket lock that fixes spin-lock unfairness is OSTEP 28.11 in the atomics unit.
- Priority InversionAlgoMaster Concurrency lessons
The Classic Scenario; Case Study: Mars Pathfinder (1997); Solutions to Priority Inversion
Depth · OSTEP has no priority-inversion locator; this lesson is the vocabulary source.
Focus on
- Deadlock needs all four conditions at once. The prevention you can prove is a global lock order: it deletes the wait-for cycle structurally, not statistically.
- Draw threads waiting on locks as directed edges; a cycle means deadlock is possible, and no cycle means it is impossible for that state. The two-mutex opposite-order program has a two-node cycle by construction.
- Try-and-back-off breaks hold-and-wait but can livelock: six runs of
vector-try-waitretried 0.8 to 3.1 million times each. Backoff calms the storm; ordering removes it. - Starvation is unfair scheduling over time with no cycle and no progress for one thread. Priority inversion is a low-priority holder blocking a high-priority waiter, as in the lesson's Mars Pathfinder case. Livelock is active retry with no progress.
Reproduce closed-book
-O2 -pthread): show it hangs past a 5 s timeout (four of four reference runs on an i9-12900K with Linux 7.0). Draw its two-node wait-for cycle. Then impose one global order (always \(A\) before \(B\)) and show both threads print and exit 0. State compiler, flags, timeout and repeats.Traps
- A timeout does not prove deadlock. A hang with spinning CPU suggests livelock; a silent hang with futex-blocked threads (gdb shows
__lll_lock_wait) suggests deadlock. Inspect thread state before naming it. - Lock ordering must cover every path, including callbacks and repeated keys. The executor practice fails if equal keys lock twice on a non-reentrant mutex.
- POSIX offers
PTHREAD_PRIO_INHERIT, and Linux implements it with priority-inheritance futexes, but it only matters when threads run under real-time scheduling. Check the scheduling policy before claiming the inversion fix.
Practice
OSTEP deadlock homework: hang it, then fix it
threads-bugs folder: make, then ./vector-deadlock -d -l 5000 -n 2 hangs (four of four reference runs, killed by a 5 s timeout); ./vector-global-order with the same flags finishes
Then read vector-try-wait.c and vector-avoid-hold-and-wait.c to name which condition each breaks.
AlgoMaster: Design a Deadlock-Free Two-Key Executor
execute() acquires distinct keys in global order and a repeated key once; the judge runs opposite-order pairs such as (1, 3) and (3, 1) with disjoint pairs allowed to overlap
A throwing callback must still release both locks and propagate the failure.
Self-test
-
\(T_1\) holds \(A\) and wants \(B\); \(T_2\) holds \(B\) and wants \(A\). Draw the graph and name the broken condition for each standard fix.
Cycle \(T_1\) to \(B\) to \(T_2\) to \(A\) to \(T_1\), so deadlock is possible. A global order breaks circular wait; try-and-release breaks hold-and-wait; timeouts break no-preemption. -
How do you tell deadlock from livelock from the outside?
Deadlock: threads blocked (futex waits, gdb__lll_lock_wait), near-zero CPU. Livelock: threads running and retrying, high CPU, no progress. Starvation: others progress while one thread does not. -
Why does acquiring the smaller key first prevent deadlock for any pair order?
Every thread acquires in the same global order, so each wait edge runs from a lower-numbered held lock toward a higher-numbered wanted lock. Edges strictly ascend in key id, so no cycle can form. -
What goes wrong if
execute(1, 1)locks key 1 twice?A non-reentrant mutex deadlocks on the second acquire by the same thread. The problem statement requires acquiring a repeated key once.
Completion criterion
Stop when
You force the hang, draw its cycle, repair it twice (order and try-release), and pass the executor judge.
Mark passed, then open 2.6 Only mark this when you can do it without notes.Leads to
- 2.6 Bounded queues, admission and backpressure Lock ordering keeps the queue's two conditions live under many producers.
- 2.7 Cancellation, deadlines and shutdown state machines Shutdown is the planned requested wait; deadlock is the unplanned one.
Comes after
- 2.4 Data races, lost updates and lost wakeupsRaces break safety one access at a time; deadlock breaks liveness for the whole program.
Resources for this unit
- Operating Systems: Three Easy Pieces - concurrency Read Chapters 26-33 in order: threads, thread API, locks, locked data structures, condition variables, semaphores, bugs and event-based concurrency. Write the safety and liveness invariant before reading each worked pattern.
- AlgoMaster Concurrency lessons Use the named lessons only: Processes vs Threads, Race Conditions and Critical Sections, Mutex, Condition Variables, Compare-And-Swap, Atomic Operations, Semaphores, Producer-Consumer Pattern, Bounded Buffer, Design Thread-Safe Blocking Queue, Barriers and Latches, Read-Write Locks, Coarse-grained vs Fine-grained Locking, Deadlock, Livelock, Starvation, Priority Inversion, Lost Signal/Wakeup, Spurious Wakeup, Concurrency Models and Thread Pool Pattern. Each unit names its lessons; read no other chapter for this section.
Also in this section
- OSTEP concurrency homework and code Use x86.py and the main, vector, condition-variable and semaphore exercises to enumerate schedules. Preserve one lost update, one deadlock and one lost wakeup as minimized tests, then repair each invariant.
- AlgoMaster Concurrency - four bounded contracts Attempt Design a Closable Bounded Queue, Design Thread-Safe Rate Limiter, Design a Deadlock-Free Two-Key Executor, Design an Atomic Maximum With Compare-and-Swap, Design Deferred Callback Executor and Design Task Scheduler with Dependencies. For each, add a changed input, a deterministic failure schedule and an independent stress test outside the platform.
- MIT 6.1810 - locks and parallelism Use Lectures 12-14 and one lock-lab exercise only after the user-space bounded queue passes. Measure the contention change and explain the invariant preserved by the revised locking scheme.
- Linux man-pages: pthreads and futex Look up the exact pthread mutex, condition variable, barrier, cancellation and timed-wait contracts plus futex(2) and pthreads(7). Read the stated pages; do not browse the whole manual.
- cppreference: C atomic operations Read
atomic_compare_exchangefor success and failure semantics and the expected-pointer update rule, andmemory_orderfor the six orderings and what relaxed permits. Stop before lock-free-property macros. - GCC __atomic builtins Read
__atomic_compare_exchange,__atomic_loadand__atomic_storefor the expected-pointer update rule and the__ATOMIC_RELAXEDconstant used by the CAS reproduce step. - The Little Book of Semaphores Use the rendezvous, barrier and reader-writer puzzles as extra semaphore practice after OSTEP Chapter 31. Skip the Python event material; this section works in C with pthreads.