Deadlock detection

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:


  1. 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.


  1. 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:

  1. 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.

  1. Find an index i such that both
  2. Finish[i] =false.
  3. Requesti < Work.

If no such i exists, go to step 4.

  1. Work := Work + Allocationi

                       Finish[i] := true

go to step 2.

  1. 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.




A Computer Science Study for IT students and people of IT community


  • February 27, 2019 at 2:06 pm

    I really like your blog.. very nice colors& theme. Did you make this website yourself or did you hire someone to do it for you? Plz reply as I’m looking to design my own blog and would like to find out where u got this from.


Leave a Reply