Find the cycle behind a deadlock

Prerequisites: Locks, threads, and resource ownership.

Learning objectives

• Construct a wait-for graph for exclusive resources.
• Distinguish deadlock, starvation, and livelock.
• Apply a global lock order and explain its limitations.

A deadlock is a dependency with no enabled escape

Consider two threads and two non-preemptible exclusive locks. Thread A owns X and waits for Y. Thread B owns Y and waits for X. Neither can reach its release operation. Scheduling them more frequently does not supply the missing resource; each requires progress from the other first.

A wait-for graph represents threads as vertices. Draw an edge from a waiting thread to the thread whose resource it needs. The example has A→B and B→A. Under the stated single-owner lock model, that cycle identifies a deadlock. With multiple interchangeable resource instances or operations that can time out and release ownership, graph interpretation requires more care.

Four conditions explain the classic failure: exclusive use, holding one resource while requesting another, no forced resource removal, and a circular chain of waiting. Preventing one condition can prevent this class of deadlock, but the chosen policy may reduce concurrency or complicate recovery.

Break the circular order deliberately

Assign every lock a global rank and require acquisition only in increasing order. If X has rank one and Y rank two, both threads must acquire X before Y whenever they need both. A cycle would require ranks to increase around the cycle and return to the starting rank, which is impossible.

The rule must cover every relevant path, including error handling and helper functions. A function that silently acquires a lower-ranked lock can violate a caller’s assumptions. Acquiring only the locks needed, documenting ownership, and avoiding callbacks under locks make the policy easier to enforce.

An alternative is to attempt a group of locks and release all acquired locks if the whole group cannot be obtained. This can avoid deadlock but introduce livelock, where threads repeatedly act yet make no useful progress. Randomized backoff can help contention patterns but is not a proof of fairness.

Similar symptoms need different remedies

Starvation means a thread waits indefinitely while other work continues. Livelock means participants keep changing state without completing useful work. Deadlock means a set cannot proceed because of its own waiting dependencies under the available operations. A timeout detects that progress was too slow; it does not by itself undo partial state safely.

For recovery, specify which operations can be rolled back and which resources can be released without violating invariants. Database transactions may support abort and retry; a thread holding arbitrary in-memory state may not. Capture lock ownership and waiting edges during diagnosis, then reproduce the acquisition order. A screenshot of idle threads is evidence of waiting, not yet a proof of the cause.

Primary reading

• Common Concurrency Problems (Arpaci-Dusseau and Arpaci-Dusseau, OSTEP).

Practice problem

Three threads hold locks as follows: A owns X and waits for Y, B owns Y and waits for Z, and C owns Z and waits for X. Draw the wait-for edges and identify a global rank policy that would forbid the trace. Explain why killing one thread is not automatically a safe recovery operation.

Worked solution

The edges are A→B because B owns Y, B→C because C owns Z, and C→A because A owns X. They form a directed cycle under the exclusive non-preemptible lock assumptions. Choose ranks X=1, Y=2, and Z=3 and require every thread to acquire locks in increasing rank order. The trace then fails at C’s attempt to acquire X while holding Z, because that would decrease the rank. Terminating C might leave protected data only partially updated and may not automatically release the lock in a way the runtime or application can safely recover from. Recovery needs a defined invariant-restoration or rollback mechanism. Merely removing a waiting participant does not prove the shared state remains valid.

Check your understanding

Which policy rules out circular wait among ranked locks?

• Acquire locks in any order if they have short names.
• Acquire every needed lock in a shared increasing rank order.
• Increase the thread count.
• Log the deadlock after it occurs.

Explanation

Strictly increasing ranks cannot form a cycle.

Threads repeatedly release and retry locks but never complete work. What is the best description?

• Livelock.
• Successful mutual exclusion proves progress.
• A cache hit.
• A completed transaction.

Explanation

The system is active but fails to make useful progress, unlike a fully blocked deadlock.

Primary reading

• Common Concurrency Problems: Arpaci-Dusseau and Arpaci-Dusseau, OSTEP

Open the study and save your work →