Deadlock Detection Algorithm in Operating System

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.

Deadlock Detection Algorithm OS Operating System
DeadLock Avoidance Results

Please Login/Signup to comment