Deadlock detection, If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system must provide:
- An algorithm that examines the state of the system to determine whether a deadlock has occurred.
- An algorithm to recover from the deadlock.
According to a number of instances in each resource type, the Deadlock Detection algorithm can be classified into two categories as follows:
- Single Instance of Each Resource Type: If all resources have only a single instance, then it can define a deadlock detection algorithm that uses a variant of the resource-allocation graph (is called a wait-for graph). A wait–for the graph can be draw by removing the nodes of type resource and collapsing the appropriate edges from the resource-allocation graph.
An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi à Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi à Rq and Rq à Pj for some resource Rq. For Example:
((a) Resource-allocation graph. (b) Corresponding wait-for graph)
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 to invoke an algorithm that searches for a cycle in the graph. An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.
- Several Instances of a Resource Type: The following deadlock-detection algorithm is applicable to several instance of a resource type. The algorithm employs several time-varying data structures:
Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
Request: An n x m matrix indicates the current request of each process. If Request[i,j] = k, then process Pi is requesting k more instances of resource type Rj.
The detection algorithm is described as follows:
- Let Work and Finish be vectors of length m and n,
Initialize, Work := Available. For i = 1, 2, …, n,
if Allocationi != 0, then Finish[i] :=false; otherwise, Finish[i] := true.
- Find an index i such that both
- Finish[i] =false.
- Requesti < Work.
If no such i exists, go to step 4.
- Work := Work + Allocationi
Finish[i] := true
go to step 2.
- If Finish[i] = false, for some i, 1 < i < n, then the system is in a deadlock state.
if Finish[i] =false, then process Pi is deadlocked.
This algorithm requires an order of m x n2 operations to detect whether the system is in a deadlocked state.