Thread A holds the process-table lock and requests the filesystem-cache lock. Thread B holds the filesystem-cache lock and calls a helper that requests the process-table lock. Both locks work exactly as designed: each excludes the other thread forever.
Safety mechanisms can destroy progress when their acquisition dependencies form a cycle. Liveness analysis asks not only whether state remains valid, but whether required operations retain a path to completion.
Classify the stalled system before repairing it
- Deadlock: a nonempty set of participants is permanently blocked because each waits for an event that only another participant in the set can cause.
- Starvation: one participant can remain unable to make progress while other participants continue completing work.
- Livelock: participants continue taking steps and changing protocol state, but the required operation never completes.
- Priority inversion: a higher-priority task is blocked, directly or transitively, by work owned by a lower-priority task; the inversion is unbounded when unrelated intermediate-priority work can extend that delay without a protocol bound.
- Deadlock: a nonempty set of participants is permanently blocked because each waits for an event that only another participant in the set can cause.
- Starvation: one participant can remain unable to make progress while other participants continue completing work.
- Livelock: participants continue taking steps and changing protocol state, but the required operation never completes.
- Priority inversion: a higher-priority task is blocked, directly or transitively, by work owned by a lower-priority task; the inversion is unbounded when unrelated intermediate-priority work can extend that delay without a protocol bound.
These categories overlap in symptoms, not definitions. “The service hung” supplies no diagnosis.
| Trace | Classification | Decisive evidence |
|---|---|---|
| A waits for L2 held by B; B waits for L1 held by A | deadlock | closed wait-for cycle; neither owner can release |
| reader-preferred lock admits a stream of readers while one writer waits | possible writer starvation | system completes reads; one enabled class is postponed indefinitely |
| two polite workers repeatedly release and retry in synchrony | livelock | both run and mutate state; neither commits |
| high-priority H waits for a mutex held by low-priority L while medium M preempts L | priority inversion | M delays the owner that could unblock H |
Prediction — answer before expanding. A low-priority thread is preempted for 2 ms while holding a mutex needed by a high-priority thread. Is that fact alone deadlock, starvation, or priority inversion? Predict the classification and required evidence before revealing the answer.
AnswerExpandCollapse
It is priority inversion during that interval. A finite delay does not establish deadlock or starvation. To claim an unbounded inversion, show that unrelated work can keep the owner from running without a protocol bound. To claim starvation, show an allowed infinite execution in which the waiting thread never completes while others do.
Classifying progress failures
Evaluate each statement regarding concurrency, deadlocks, and liveness failures:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Resource graphs expose ownership and demand
A resource-allocation graph has thread nodes and resource nodes. An edge means T requests R; an edge means an instance of R is assigned to T. For single-instance reusable resources, collapse each request through the current owner into a wait-for edge
In a wait-for graph where every resource has one instance and blocked requests cannot be withdrawn, a directed cycle is necessary and sufficient for deadlock among the cycle’s threads. With multiple interchangeable instances, a cycle is necessary but may not be sufficient: a thread outside the cycle can release another instance and satisfy a request. State the resource model before interpreting a cycle.
Worked trace: multi-instance wait-for graph. A holds one of two database connections and waits for a log slot. B holds the log slot and waits for a database connection. The graph contains A→B and B→A if edges are projected only through the currently observed connection owner. Yet a third thread C can return the second connection, allowing B to proceed. The projected cycle did not prove deadlock because the resource had another instance and another release path.
The four classical conditions describe a resource regime in which deadlock can arise:
- mutual exclusion: at least one resource cannot be shared simultaneously;
- hold and wait: a participant holds resources while requesting more;
- no forced preemption: resources are released by their owners rather than safely taken away; and
- circular wait: a closed chain of participants each waits for a resource held by the next.
All four are necessary for deadlock in that model. Their availability as system policies is not proof that a particular execution is deadlocked; construct the current ownership and wait relation.
A lock order is a proof, not a comment
Assign every lock a rank in a strict total order and require a thread to acquire locks only in increasing rank. Suppose a deadlock cycle exists:
Each thread holds one lock and requests the next, so the order rule implies
which is impossible for a strict order. The policy eliminates circular wait.
Worked transfer operation. To move a page from source cache bucket 9 to destination bucket 3, the semantic order “source then destination” conflicts with numeric rank. Acquire bucket 3 then bucket 9, regardless of transfer direction. Because the source was inspected before both locks were held, revalidate that the page remains in bucket 9 and that the destination does not already contain it. Lock order prevents deadlock; revalidation preserves correctness.
Counterexample: hidden acquisition. Code holds rank-20 lock L and invokes a callback supplied by another subsystem. The callback acquires rank-10 lock K. The local source file shows no descending acquisition, but the dynamic call graph violates the proof. Solutions include forbidding callbacks under L, splitting prepare/commit phases, passing immutable data, or making the callback’s lock contract explicit and mechanically checked.
Application. A recursive tree traversal acquires each child lock while retaining its parent lock. Does “parent before child” define a global order when another operation can rotate the tree?
AnalysisExpandCollapse
Only if parent/child relationships remain stable for the entire acquisition and no operation needs child-before-parent. Rotation changes topology, so a relation derived from mutable structure may cease to be acyclic or consistently observed. Stable object IDs, address/rank order, lock coupling with revalidation, or a coarser tree lock can supply a defensible order. The answer must include object lifetime: comparing addresses is unsafe if objects can be freed and reused while a contender waits.
Prevention, avoidance, and recovery solve different contracts
| Strategy | Required knowledge or power | Useful case | Boundary |
|---|---|---|---|
| prevent hold-and-wait | request all resources together or release before requesting more | small known resource set | lowers concurrency; all-or-nothing acquisition may be impossible |
| prevent circular wait | stable global rank | kernel lock hierarchies | hidden callbacks and dynamic resources complicate ranking |
| avoidance | declared maximum future demand; grant only if state remains safe | controlled batch/resource systems | inaccurate maximum claims make policy unusable or unsafe |
| detection and recovery | observable allocation state plus a victim/rollback mechanism | transactions, killable jobs | kernel locks and irreversible I/O may not be safely revoked |
| timeout | clock and abort path | bounds one caller’s wait when abort is valid | does not prove the cycle is gone; synchronized retries can livelock |
Avoidance asks whether there exists a safe completion sequence after a proposed grant. A state can be safe even when not every thread could complete next; at least one sequence lets all finish within declared maximum demands. Banker’s-style reasoning is meaningful only when maximum claims and resource counts are trustworthy.
Worked safe-state check. Two processes share three identical buffers. A holds one and may need at most one more; B holds one and may need at most two more. One buffer is free. Grant it to A: A can finish and release two, then B can obtain its remaining demand. Grant it to B: B would hold two and need one, A would hold one and need one, and none would be free; under the declared maxima, no completion sequence remains. The second grant is unsafe, though no one is deadlocked at the instant before either makes its next request.
Detection does not imply recovery. Killing a process that holds a user-space mutex may be acceptable if robust-mutex recovery marks protected state inconsistent. Killing a kernel thread halfway through device programming may leave hardware and memory in an unrepairable protocol state. Define the rollback boundary before choosing “detect and abort.”
Backoff can replace deadlock with livelock
Two transfer threads each trylock one account, fail on the second, release, wait exactly 1 ms, and retry. Their lockstep behavior can continue forever. There is no blocked cycle because each releases; there is no progress because both repeat the same collision.
Starvation requires a fairness argument. A test-and-set spin lock can repeatedly admit a nearby core while a remote core loses cache-line races. A reader-preferred reader/writer lock can admit an endless stream of readers ahead of a writer. FIFO admission bounds overtaking but can create convoying when the head waiter is descheduled. Liveness and throughput objectives can conflict.
Transfer. Define a test that distinguishes deadlock from livelock without declaring every slow run a failure.
Test designExpandCollapse
Instrument protocol state and completed operations. In a controlled schedule, deadlock reaches a stable wait-for cycle with no enabled participant that can release a required resource. Livelock continues producing state transitions or retries while a completion counter remains unchanged. Use a finite watchdog only to trigger capture; classify from the captured wait-for and transition evidence. A wall-clock timeout alone cannot distinguish load, preemption, deadlock, and livelock.
Priority inversion is a dependency-scheduling problem
Let H have high priority, M medium priority, and L low priority:
- L acquires mutex R.
- H becomes runnable, preempts L, then blocks on R.
- M becomes runnable. Because M outranks L, M runs.
- H is effectively delayed by M even though H and M share no lock.
Under priority inheritance, L temporarily inherits the highest priority of a waiter on R. If L itself blocks on a mutex owned by another task, the boost may propagate along that dependency chain. The boost is removed when the relevant dependency ends. This bounds interference from unrelated medium-priority work under the protocol’s scheduler assumptions; it does not shorten L’s critical section or cure a deadlock cycle.
A priority-ceiling protocol associates a ceiling with each resource based on the highest-priority task that may lock it. Variants can prevent certain deadlocks and bound a task’s blocking by restricting acquisitions according to active ceilings. Those guarantees assume fixed-priority scheduling, declared resource use, bounded critical sections, and the specified protocol. They are not inherited by an arbitrary mutex with a “priority” field.
Worked nested inversion. H waits for R1 held by L. L waits for R2 held by X. Boosting only L does not help because X remains preemptible by M. A transitive PI implementation propagates H’s effective priority through L to X; X releases R2, L resumes and releases R1, then H proceeds. The chain also shows why PI implementation needs cycle detection and careful priority restoration.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 3.4.1: Evaluating the Four Coffman Necessary Conditions
State the four Coffman conditions necessary for a system deadlock to arise. For each condition, describe how a concrete operating system mechanism directly invalidates that condition.
HintExpandCollapse
Recall mutual exclusion, hold and wait, no preemption, and circular wait.
Worked solutionExpandCollapse
The four necessary conditions established by Coffman, Elphick, and Shoshani (1971) are:
- Mutual exclusion: at least one resource must be held in a non-shareable mode. Invalidation: Use lock-free data structures (e.g., atomic compare-and-swap) or read-only shared access where multiple threads proceed concurrently without mutual exclusion.
- Hold and wait: a thread currently holding at least one resource may request additional resources. Invalidation: Require a thread to request all needed resources simultaneously in a single atomic operation, or release all held resources before requesting new ones.
- No preemption: resources cannot be forcibly confiscated from a thread; they can only be released voluntarily by the holding thread. Invalidation: Implement preemption protocols where the OS kernel or runtime revokes a resource (or aborts and restarts a transaction) if an additional request cannot be immediately satisfied.
- Circular wait: a closed chain of threads exists such that waits for a resource held by Invalidation: Impose a strict global partial or total ordering on all resource classes, mandating that resources are acquired only in increasing order.
Breaking any single condition renders deadlock mathematically impossible.
Exercise 3.4.2: Cycle Detection in Multi-Unit Resource Graphs
Construct a concrete resource-allocation graph with two thread nodes and two resource nodes where has 2 available units and has 1 available unit. Show that a directed cycle exists in the graph, yet the system is not deadlocked.
HintExpandCollapse
Give R1 two units held by different threads or an unallocated unit that allows one thread to finish.
Worked solutionExpandCollapse
Let resource possess 2 units and resource possess 1 unit. Introduce a third thread to illustrate the distinction between single-unit and multi-unit resource graphs:
- allocation edges: and (both units allocated).
- allocation edge: (its single unit allocated).
- Request edges: requests and requests
Notice the directed cycle:
However, thread holds a unit of and has no outstanding requests. Thread executes to completion and releases its unit of The newly freed unit of is allocated to satisfying ‘s request. completes and releases both its unit of and Finally, is allocated to allowing to complete.
Hence, while a cycle is necessary and sufficient for deadlock in single-unit resource graphs, in multi-unit graphs a cycle is merely necessary, not sufficient. A knot (or absence of reducible sinks) is required for deadlock in general graphs.
Exercise 3.4.3: Proving Deadlock Freedom via Global Lock Hierarchies
Let be a finite set of mutex locks with a strict total order defined over them. Suppose every thread acquires locks strictly in ascending order: if a thread holds lock and requests lock then Prove that circular wait cannot occur.
HintExpandCollapse
Assume a cycle of waiters exists and examine the ordering of the held locks.
Worked solutionExpandCollapse
Assume for contradiction that a circular wait exists among threads
For each thread let be the set of locks currently held by and let denote the maximum lock held by with respect to Suppose thread is blocked requesting lock which is held by thread
By the strict ordering protocol, because requests while holding we must have:
Furthermore, since by definition of the maximum element:
Combining these inequalities yields:
Chaining this strict inequality along the entire cycle from to
By transitivity of the strict total order this implies which violates the irreflexivity of strict orders.
Thus, no circular wait can form, proving that the system is guaranteed deadlock-free.
Exercise 3.4.4: Deterministic Retry Traps versus Randomized Exponential Backoff
Explain why two threads using non-blocking try_lock() with identical, deterministic sleep intervals can enter livelock. Explain how randomized exponential backoff breaks the synchronization lockstep.
HintExpandCollapse
Contrast deterministic phase alignment with probabilistic symmetry breaking.
Worked solutionExpandCollapse
When two threads attempt to acquire two locks and using try_lock():
- Thread acquires and Thread acquires
- Both attempt to
try_lock()the second lock and fail. - Both release their held lock to avoid deadlock and immediately execute a fixed deterministic sleep (e.g.,
sleep(1ms)). - Because both threads wake up at identical offsets, they repeat the acquisition in perfect lockstep: Thread gets Thread gets both fail on the second lock, both release, and both sleep again.
This is livelock: CPU cycles and state transitions occur continuously, but the aggregate operation makes zero forward progress.
Randomized exponential backoff breaks this deterministic symmetry by selecting a sleep duration uniformly at random from a dynamically doubling window: on the -th failure. With high probability, one thread draws a significantly shorter delay, awakens earlier, and acquires both locks uncontested before the other thread wakes up.
Exercise 3.4.5: Priority Inheritance Protocol Bounds on Priority Inversion Chains
Consider three threads with priorities Thread acquires mutex after which thread arrives and blocks requesting Thread becomes runnable and does not need
- Formalize the duration of priority inversion experienced by without priority inheritance.
- Formalize the maximum blocking time under the basic priority inheritance protocol.
HintExpandCollapse
Without inheritance, M can preempt L indefinitely. With inheritance, L runs at effective priority pi(H).
Worked solutionExpandCollapse
-
Without priority inheritance: Thread is blocked awaiting mutex held by However, thread has higher priority than and is ready to run. The scheduler preempts to execute If a set of medium-priority threads arrives, thread cannot execute until all threads in complete or block. The blocking time experienced by is:
where can be unbounded if new medium-priority tasks continue arriving. This is unbounded priority inversion (the classic Mars Pathfinder hazard).
-
Under basic priority inheritance protocol (PIP): When blocks on mutex held by the kernel elevates ‘s effective priority:
Now for all The scheduler cannot preempt with medium-priority work. executes its critical section without interference from releases restores its original priority and immediately unblocks The maximum blocking duration for is strictly bounded by the execution time of ‘s critical section:
References & Further Reading
- Edward G. Coffman Jr., M. J. Elphick, and Arie Shoshani, “System Deadlocks”, ACM Computing Surveys, 1971.
- Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”, IEEE Transactions on Computers, 1990.
- Linux kernel documentation, RT-mutex implementation design.
- The Open Group, POSIX.1-2024 mutex priority protocols.
- Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, deadlock chapter.