Deadlock Handling

There are three strategies for dealing with deadlock:

·        Deadlock Prevention

·        Deadlock Avoidance

·        Deadlock Detection and Recovery

Deadlock Prevention

Since four conditions are required to produce a deadlock, one can infer that if one or more of the conditions is negated, then deadlock can be prevented. Thus, the basic idea of deadlock prevention is to deny at least one of the four necessary conditions for deadlock. The mutual exclusion condition cannot be disallowed, so it is customary to prevent one or more of the remaining three conditions. Deadlock prevention methods tend to be wasteful in terms of machine resources.

Denying Hold and Wait

The hold and wait condition can be eliminated by requiring or forcing a process to release all resources held by it whenever it request a resource that is not available. In other words deadlocks are prevented because waiting processes are not holding any resources. There are basically two possible implementations of this strategy:

·        The process requests all needed resources at one time prior to the commencement of the execution

·        The process requests resources incrementally in the course of execution but release all its resource holding upon encountering a denial.

To requests all needed resources at one time prior to the commencement of the execution, a process must preclaim all of its resource needs. If the set of resources needed by a process is available, then the system may granted all of those resources to the process at one time and the process will be allowed to proceed. If the complete set of resources needed by a process is not currently available, then the process must wait until the complete set is available. While the process waits, however, it may not hold any resources. Thus the hold and wait condition is denied and deadlock simply cannot occur.

Deadlock prevention in means by means of advanced acquiring of all estimated resources can result in low resource utilization and in a corresponding reduction of the level of concurrency possible in the system.

An alternative approach to deny the hold and wait condition is to acquire resources incrementally, as needed, and to prevent deadlocks by releasing all resources held by a process when it requests a temporarily unavailable resource. This strategy avoids the disadvantages of preclaiming and of holding all resources from the inception of a process. The drawback of this strategy is that some resources cannot easily be relinquished and reacquired at a later time. For example, some irreversible changes made to memory or to files may corrupt the system if not carried to completion.

Denying No Preemption

The no preemption deadlock condition can be denied by allowing preemption, that is, by authorizing the system to revoke ownership of certain resources from blocked processes. Preemption requires that when a process holding resources is denied a request for additional resources, that process must release its held resources and, if necessary, request them again together with additional resources. Since preemption is involuntary from the point of view of the affected processes, the operating system must save the state of the preempted process and restore it when the process later resumed. This makes the preemption of process more difficult than voluntary release and resumption of resources. Preemption is possible for certain type of resources, such as CPU and main memory, since CPU states can be saved by process switch operation and the contents of the preempted memory pages can be swapped out to secondary storage. However, some types of resources, such as partially updated files, cannot be preempted without corrupting the system. since some resources cannot be safely preempted, this approach alone cannot provide complete deadlock prevention. 

Denying Circular Wait

This strategy denies the possibility of a circular wait by linear ordering of system resources. In this approach, system resources are divided into different classes Cj, where j=1,2,3,……,n. Deadlock are prevented by requiring all processes to request and acquire their resources within a given class must be made with a single request, and not  incrementally. Thus once a process acquires a resource belonging to the class Cj, it can only request resource of class j+1 or higher thereafter. Linear ordering of resource in classes eliminates the possibility of circular waiting, since a process holding a resource in class Ci cannot possibly wait for any process that is itself waiting for resource in a class Ci or lower.

For example, a system could order the following resources as shown:

1.     Printer

2.     Tape drive

3.     disk drive

Each process would first have to acquire all printers, then all tape drives and finally all the disk drives. If a process holds the printer, it can be allocated the tap drive or disk drive. If a process holds the disk drive, it cannot request any other resources; to do so, it would be requested to relinquish the drive, then request the printer and disk drive in that order.

A disadvantage of  this approach is that resources must be acquired in the prescribed order, as opposed to being requested when actually needed. This may cause some resources to be acquired well in advanced of their actual use, thus lowering the degree of concurrency by making unused resources unavailable for allocation to other processes.

Next: Deadlock avoidance

Previous: Deadlock and conditions for deadlock

Index: Operating System