Circular Wait and Resource Dependency Graphs

Resource dependency graphs model which threads hold resources and which resources they are waiting for. A cycle can reveal a possible deadlock, especially when each dependency in the cycle represents a blocking wait.

A resource-allocation graph represents threads and resources as nodes. An edge from a thread to a resource means the thread is requesting that resource; an edge from a resource to a thread means the resource is currently assigned to that thread.

A circular wait occurs when threads form a closed dependency chain: each thread is waiting for something held by the next thread. For example, thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1. Neither can make progress.

A wait-for graph simplifies this representation by using only threads as nodes. An edge from thread A to thread B means A is waiting for a resource currently held by B. A directed cycle in a wait-for graph indicates a deadlock when the waits are blocking and the relevant resources cannot be forcibly taken away.

For Java backend interviews, distinguish detecting a cycle from proving a deadlock. A cycle in a general dependency graph may indicate circular dependency, but whether execution is actually deadlocked depends on the synchronization semantics, resource availability, and whether another event can break the cycle.

Key points

• Model ownership and waiting relationships explicitly.
• A circular wait is a closed chain of blocking dependencies.
• A wait-for graph contains threads and edges between waiting threads.
• A directed cycle in a wait-for graph can indicate deadlock.
• Graph analysis helps diagnose deadlocks but must be interpreted with resource semantics.

Interview questions

What is a wait-for graph?

A wait-for graph represents threads as nodes and waiting relationships as directed edges. If thread A needs a resource held by thread B, the graph contains an edge from A to B. A directed cycle means the participating threads depend on one another in a loop. This makes the graph useful for reasoning about deadlock.

What is a circular wait condition?

Circular wait means a set of threads forms a closed chain of dependencies. Each thread is waiting for a resource held by another thread in the same chain. Because every participant is waiting, none can proceed. This pattern is a classic ingredient of deadlock.

How would you prevent circular-wait deadlocks in Java?

A common technique is to impose a global ordering on locks and always acquire multiple locks in that order. This prevents threads from acquiring the same locks in conflicting sequences. Another approach is to reduce lock scope or use timed acquisition such as `tryLock` where appropriate. The right strategy depends on the application's concurrency requirements.

Does every cycle in a resource-allocation graph prove a deadlock?

Not universally. For a single-instance resource type, a cycle can correspond to deadlock under the usual blocking assumptions. With multiple instances of resource types, a cycle may exist without making the system permanently unable to progress because another instance can satisfy a request. Therefore, the graph must be interpreted together with resource counts and synchronization behavior.