How can you detect a deadlock using a resource allocation graph?
Draw processes and resources as nodes, with request and assignment edges. A cycle means deadlock if every resource has a single instance; with multiple instances a cycle is necessary but not enough.
Explain it simply
A resource allocation graph shows who holds what and who is waiting for what. Draw circles for processes, boxes for resources (dots inside for instances), an arrow from a process to a resource when it requests it, and an arrow from the resource to a process when it is assigned.
Then look for a cycle.
Example
Single instance per resource. P1 holds R1 and requests R2. P2 holds R2 and requests R1.
P1 -> R2 -> P2 -> R1 -> P1 (cycle)Both wait on each other forever. A cycle here means deadlock.
Multiple instances. Suppose R1 has two instances. P1 holds one and requests R2. P2 holds R2 and requests R1. P3 holds the other R1 instance and is not waiting for anything. There is still a cycle P1 -> R2 -> P2 -> R1 -> P1, but P3 will finish and release its R1 instance, P2 will get it, finish, and release R2 for P1. No deadlock.
So with multiple instances, run a reduction: repeatedly remove processes that can finish and release their resources. If processes remain stuck, they are deadlocked. In practice, OSes also use a wait-for graph, which drops the resource nodes and keeps only process-to-process edges.
What to say in the interview
"I model it as a graph with request and assignment edges. For single-instance resources a cycle means deadlock. With multiple instances a cycle is only necessary, so I check whether any process can finish and release resources, using a reduction similar to the Banker's safety check."
Common mistakes
- Saying every cycle means deadlock regardless of the number of instances.