Deadlock Detection And Recovery

Deadlock:

A process requests the resources, but the resources aren’t available at that time, the process enters into the waiting state. The requesting resources are held by another process, it is waiting for some other resource. Then both processes are in waiting for the state, with no work in progress. This situation is called a Deadlock.

Conditions for Detecting Deadlock:

A deadlock system should satisfy the following 4 conditions:

Mutual Exclusion:

Mutual Exclusion means that resources are in non-shareable mode only which means only one process at a time can use a resource. If some other process requests that resource, the requesting process must wait until the resources have been released.

Hold and Wait:

Each process in the deadlock state must be held at least one resource and it is waiting for additional resources that are currently being held by other processes.

hold-and-wait

No Preemption:

It means that the resources aren’t released in the middle of the work, they are released only after the process has completed its task.

Circular Wait:

In the following figure: P1 is waiting for a resource R1 and R1 is held by P2, P2 is waiting for R2 and R2 is held by P3, P3 is waiting for a resource R4 and R4 held by P2, P2 waiting for a resource R3 and R3 is held is by P1.

circular wait
It is said to be a Circular Wait.

Deadlock Recovery Methods:

There are two methods for Deadlock Recovery:

    1. Process Termination
    2. Resource Preemption

Process Termination:

Process Termination is one method to recover from deadlock. We can use two methods for Process Termination and these are :
i. Abort all deadlocked processes
ii. Abort one by one process until the deadlock cycle is eliminated

Abort all deadlocked processes:

It is a great expensive method. It means that release all processes in the deadlocked state and starting the allocation from the starting point.

Abort one by one process until the deadlock cycle is eliminated:

In this method, first abort one of the processes in the deadlocked state and allocate the resources to some other process in the deadlock state then check whether the deadlock broke or not. If not abort another process from the deadlock state. Continue this process until we recover from the deadlock.

Resource Preemption:

There are three methods to eliminate deadlocks using resource preemption and these are:

  • Selecting a victim
  • Rollback
  • Starvation

Selecting a victim:

Select a victim resource from the deadlock state and preempt that one.

Rollback:

Roll back the processes and resources up to some safe state and result in it from that state. This method requires the system to keep more information about the state of all the running processes.

Starvation:

A process or a resource can be picked as a victim a finite number of times, it is said to be starvation. The most common solution is to include the number of rollbacks in the cost factor.