Methods for Handling Deadlocks: Recovery from Deadlock

 

Recovery from Deadlock:

 

When a detection algorithm determines deadlock exists, several alternatives exist.

 

One possibility is to inform the operator that a deadlock has occurred and to let the operator deal with the deadlock manually.

 

Other possibility is to let the system recover from the deadlock automatically. There are two options for breaking a deadlock. One solution is simply to abort one or more processes to break the circular wait. The second option is to preempt some resources from one or more of the deadlocked processes.

 

1.    Process Termination:

 

To eliminate deadlocks by aborting a process, we use one of two methods.  In both methods the system reclaims all resources to the terminated process.

 

1.    Abort all deadlocked processes: This method clearly will break the deadlock cycle but at a great expense.  These processes may have completed for a long time and the results of the partial computations must be discarded and probably recomputed later.

2.    Abort one process at a time until the deadlock cycle is eliminated: This method incurs considerable overhead since after each process is aborted a deadlock detection algorithm must be invoked to determine whether any processes are still deadlocked.

 

Aborting a process may not be easy. If the process was in the midst of updating a file, terminating it will leave that file in an incorrect state.

 

Similarly, if the process was in the midst of printing data on the printer, the system must reset the printer to a correct state before printing the next job.

 

If the partial termination method is used, then given a set of deadlocked processes, we must determine which process or processes should be terminated in an attempt to break the deadlock. This determination is a policy decision similar to CPU scheduling problems.

 

And if the question is basically economic one, we should abort those processes, the termination of which will incur the minimum cost. Unfortunately the term minimum-cost is not a precise one. Many factors determine which process is chosen including:

 

1.    What the priority of the process is?

2.    How long the process has computed and how much longer the process will compute before completing its designated task?

3.    How many and what type of resource is the process has used for example whether the resources are simple to preempt?

4.    How many more resources the process needs in order to complete?

5.    How many processes will need to be terminated?

6.    Whether the process is interactive or batch?

 

2.    Resource Pre-emption:

 

To eliminate deadlocks using resource pre-emption successfully, we successfully preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.

 

If pre-emption is required to deal with deadlocks then 3 issues need to be addressed:

 

1.    Selecting a victim: Which resources and which processes are to be pre-empted? As in process termination, we must determine the order of pre-emption to minimize cost. Cost factors may include such parameters as the number of resources a deadlock process is holding, and the amount of time a deadlocked process so far consumed during its execution.

 

2.    Rollback: If we preempt a resource from a process, what should be done with that process? Clearly it cannot continue with its normal execution, it is missing some needed resource. We must roll back the process to some safe state and restart it from that state. The simplest solution is a total rollback in which a process is aborted and then it is restarted. However, it is more effective to roll back the process only as far as necessary to break the deadlock. On the other hand, this method requires the system to keep more information about the state of all the running processes.

3.    Starvation: How do we ensure that starvation will not occur? That is how can we guarantee that resources will not always be pre-empted from the same process? In a system where victim selection is based primary on cost factors, it may happen that the same process is always picked as a victim. As a result, this process may not complete its designated task; a starvation situation that needs to be dealt with. Clearly we must ensure that a process can be picked as a victim only a finite number of times.