Single Instance of Each Resource Type

• If all resources have only a single instance, then we can define a deadlock-detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph.
• This graph is obtained from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges.
• More precisely, an edge from $P_i$ to $P_j$ in a wait-for graph implies that process $P_i$ is waiting for process $P_j$ to release a resource that $P_i$ needs.
• For example, in Fig. 7.11, a resource-allocation graph and the corresponding wait-for graph are presented.

  Figure 7.11: (a) Resource-allocation graph. (b) Corresponding wait-for graph.

  
• As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle.
• To detect deadlocks, the system needs to maintain the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph.
• If this graph contains one or more cycles (knots), a deadlock exists. Any process that is part of a cycle is deadlocked. If no cycles exist, the system is not deadlocked.

  Figure 7.12: (a) A resource graph. (b) A cycle extracted from (a).

  
• Consider a system with seven processes, $A$ though $G$, and six resources, $R$ through $W$. The state of which resources are known and the the resource graph is given in Fig. 7.12. The question is: ``Is this system deadlocked, and if so, which processes are involved?''
• From this cycle, we can see that processes $D$, $E$, and $G$ are all deadlocked. Processes $A$, $C$, and $F$ are not deadlocked because $S$ can be allocated to any one of them, which then finishes and returns it. Then the other two can take it in turn and also complete.