How do you detect a Deadlock using a Graph?

Difficulty: 6/10

wait-for graph, cycle detection, resource allocation

Deadlock Detection with Graphs

A Resource Allocation Graph models processes and resources. A directed edge from a process to a resource represents a request, while an edge from a resource to a process represents an allocation. A cycle can indicate deadlock; for single-instance resources, a cycle is sufficient, while with multiple instances additional analysis is required.

javascript

1
Request edge: Process -> Resource.
2
Assignment edge: Resource -> Process.
3
For single-instance resources, a cycle indicates deadlock.
4
For multiple resource instances, a cycle alone may not prove deadlock.
5
Wait-for graphs can simplify process-to-process dependency analysis.

Scenario Questions

0-2 years experience

2-5 years experience

1During a code review you notice that a new feature adds a lock acquisition order that might create a cycle. How would you use a graph to verify whether this introduces a deadlock?

Follow-up Questions