Questions
29 of 59
How do you detect a Deadlock using a Graph?
Difficulty: 4/10
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.
Follow-up Questions
- What is a wait-for graph?
- Why is a cycle insufficient with multiple resource instances?