Deadlock Detection Algorithm in Operating System

January 21, 2023

Deadlock Detection Algorithm

Deadlock Detection Algorithm in Operating System

Deadlock Detection Algorithm helps decide if in scenario of multi instance resources for various processes are in deadlock or not.

In cases of single resource instance we can create wait-for graph to check deadlock state. But, this we can’t do for multi instance resources system.

Algorithm Example

Do not confuse the deadlock detection algorithm with Banker’s algorithm which is completely different. Learn Banker’s Algorithm here.

The deadlock detection algorithm  uses 3 data structures –

  • Available
    • Vector of length m
    • Indicates number of available resources of each type.
  • Allocation
    • Matrix of size n*m
    • A[i,j] indicates the number of j th resource type allocated to i th process.
  • Request
    • Matrix of size n*m
    • Indicates request of each process.
    • Request[i,j] tells number of instance Pi process is request of jth resource type.

Steps

  • Step 1
  1. Let Work(vector) length = m
  2. Finish(vector) length = n
  3. Initialize Work= Available.
    1. For i=0, 1, …., n-1, if Allocationi = 0, then Finish[i] = true; otherwise, Finish[i]= false.
  • Step 2
  1. Find an index i such that both
    1. Finish[i] == false
    2. Requesti <= Work

If no such i exists go to step 4.

  • Step 3
  1. Work= Work+ Allocationi
  2. Finish[i]= true

Go to Step 2.

  • Step 4

If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process Pi is deadlocked.

OS dekstop gif
OS mobile gif

Deadlock Introduction

Deadlock Detection And Recovery

Deadlock detection Algorithm

Deadlock Avoidance and Prevention

Deadlock Detection Algorithm -1
Deadlock Avoidance Results
 
  • Step 1
In this, Work =[0,0,0] &
Finish = [false, false, false, false, false].
 
  • Step 2
i=0 is selected as both Finish[0]=false and [0,0,0] <=[0,0,0].
 
  • Step 3
Work = [0,0,0]+[0,1,0]=>[0,1,0] &
Finish = [true, false, false, false, false].
 
  • Step 4
i=2 is selected as both Finish[2] = false and [0,0,0]<=[0,1,0].
 
  • Step 5
Work = [0,1,0]+[3,0,3] = > [3,1,3] &
Finish = [true, false, false, false, false].
 
  • Step 6

i=1 is selected as both Finish[1] = false and [2,0,2] <=[3,1,3].

 
  • Step 7
Work=[3,1,3]+[2,0,0] => [5,1,3] &
Finish = [true, true, true, false, false].
 
  • Step 8
i=3 is selected as both Finish[3] =false and [1,0,0] <= [5,1,3].
 
  • Step 9
Work = [5,1,3] + [2,1,1] =>[7,2,4] &
Finish = [true, true, true, true, false].
 
  • Step 10
i=4 is selected as both Finish[4] = false and [0,0,2] <=[7,2,4].
 
  • Step 11
Work = [7,2,4] + [0,0,2] =>[7,2,6] &
Finish = [true, true, true, true, true].
 
 
Since Finish is a vector of all true it means there is no deadlock in this example.
 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

One comment on “Deadlock Detection Algorithm in Operating System”