Deadlock Detection

Deadlock Detection

• Deadlock detection is the process of determining that a deadlock exists and identifing the processes and resources involved in the deadlock.

• If processes are blocked on resources for an inordinately long time, the detection algorithm is executed to determine whether the current state is a deadlock.

• Deadlock detection algorithms can incur significant runtime overhead.

Wait for Graph

• Any resource allocation graph with a single copy of resources can be transferred to a wait for graph.

• Fig. 3.6.1 shows resource allocation graph with corresponding wait for graph. The state of the system can be modeled by directed graph, called a wait for graph.

• Wait for graph is a graph where each node represents a process. An edge P_i → P_j means that process P_i is blocked and waiting for process P_j to release a resource.

• The wait for graph of a system is always smaller than the resource allocation graph of that same system. There is a deadlock in a system if and only if there is a loop in the wait for graph of that system.

Deadlock detection invloves two issuses:

1. Maintenance of the wait for graph.

2. Searching of the wait for graph for the presence of cycles.

• Deadlock detection requires overhead for run time cost of maintaining necessary information and executing the detection algorithm.

• For multiple instances of a resource type use an algorithm similar to banker's no algorithm.