Deadlock Recovery Techniques

Introduction:

The deadlock prevention and deadlock avoidance techniques or strategies solve the deadlock problem in a system by imposing restrictions on processes. Both of these techniques may affect the performance of the system.

Another approach may be that we do not use deadlock prevention and avoidance techniques in a system, and allow deadlocks to occur in a system. After the appearance of deadlocks, we can use;

1. An algorithm to detect a deadlock.
2. An algorithm to recover the system from the deadlock.

Deadlock detection and recovery is another technique used to handle deadlocks in a system. This technique does not limit resource access or restrict process execution. The requested resources are granted to the required processes whenever possible in a system. In this environment,  The operating system periodically performs algorithms to detect the circular system automatically recovers the deadlock by performing another recovery algorithm.

Deadlock Detection:

Deadlock detection is the activity of finding and detecting a deadlock that occurred in a system. It also identifies the multiple processes and resources involved in the deadlock in a computer network system. This algorithm determines if a circular wait exists in a system. If so, a deadlock exists in the system. Different techniques are used to detect deadlock with single instances and multiple instances of resource types.

Deadlock Detection with Single Instances of a Resource Type in a system:

Deadlock can easily be detected from a system having a single instance of each resource type. 

Suppose a system has only one printer, one plotter, and one tape drive. For such a system, we can define a deadlock detection algorithm by using a wait-for graph. A wait-for graph is obtained from the required resource allocation graph by removing the required resources nodes in the network computer system and collapsing the appropriate edge.

Deadlock Detection with Multiple Instances of a Resource Type in a system:

If some of the resource types of a system have multiple instances, then a different approach is needed to detect deadlock. It means that in this case, the wait-for graph scheme is not applicable. In this case, a matrix-based algorithm is used for detecting deadlocks. The data structure of this algorithm is similar to as used in Banker's Algorithm.

Recovery from deadlock:

Once a deadlock has been detected from a system, some strategy is needed to recover from it to accurate a system. There are various ways of recovering from deadlock. Two suitable ways are commonly used to break the deadlock in a system.

1. Recovery through process termination
2. Recovery through resource preemptions

Recovery through Process Termination:

The simplest way to break a deadlock system is to kill one or more deadlocked processes. There are three possibilities to terminate deadlocked processes. These are as follows;

Terminate all deadlocked processes:

It is a very simple method to break the deadlock cycle in the system, but this method slows down the progress of the system. It is because; the deadlocked processes may run for a long time and are terminated without giving their final results. So these processes might be run again and again.

Terminate one Process at a time:

Termination one process at a time, until the cycle, is broken. In this case, the other processes will be able to continue. This method to break down the cycle also slows down the system because after each process is terminated, a deadlock detection algorithm must be executed again to determine whether any processes are still deadlocked.

Termination of a process not in a cycle:

A process not in a cycle can be terminated to release its resources. In this approach, the process to be terminated is carefully chosen because it is holding resources that some process in the cycle needs. For example; one process might hold a printer and needs a CD-ROM drive, and another process holding a CD-ROM drive and waiting for a printer. These two processes are deadlocked. A third process outside the cycle may hold both these resources. Terminating the third process will break the deadlock.

Priority for Terminating Processes:

Some priority must be defined when terminating processes; otherwise, serious problems may be created. To terminate a process, the following things are considered;

• How many resources a process is currently holding?
• How many resources it needs to complete its task?
• How long a process has been executing?
• How long process has been executed?
• How my processes would be affected?

Recovery through Resource Preemption:

This method is used to break the deadlock by temporarily taking resources from the waiting process and allocating them to other processes until the deadlock cycle is broken. We must consider the following three major issues before implementing this strategy:

Selection of Victim:

When resources from which process are to be presented? It is the most important decision. The factors in making the decision could include;

• How many resources a process is currently holding?
• How long a process has been executing?
• How long process has been executed?
• How my processes would be affected?

Rollback:

If a resource is preempted If a resource is preempting from a process then it cannot continue with its normal execution. In this case, we must rollback the process to some safe state and re-start it from that state. This method may have the following side effects:

Rolling a process back to its starting state may not be practical in a system network. Some input data may be unrecoverable.

The process is reset to an earlier state where it does have no resources, which is now assigned to one of the deadlock processes. If the restarted process tries to acquire again. it will have to wait till it becomes available.

Starvation

How do we ensure that the starvation will not occur the same process may be repeatedly selected as the victim process for preemption. In this case, Starvation to this process may occur and the process will not be able to continue its execution. To handle this problem, we must ensure that a process can be selected as a victim only for a limited number of times. The most common solution to this problem is to use a preempting counter. Each time a process is rolled back, the preempting counter is incremented. In this way, no resources would be preempted from the process with the highest preempting counter value.