Deadlock Avoidance

Deadlock prevention methods tend to be wasteful in terms of machine resources. Deadlock avoidance attempts to predict the possibility of a deadlock dynamically as each resource is made. The basic idea of deadlock avoidance is to grant only those requests for available resources that cannot possibly result in a state of deadlock. This strategy is usually implemented by checking the effect of granting a particular resource request by the resource allocator.  If granting of the resource cannot possibly lead to deadlock, the resource is granted to the requester. Otherwise, the requesting process is suspended until its pending request can be safely granted.

The most famous deadlock avoidance algorithm is Dijikstra’s Banker’s Algorithm. The algorithm is called by this name because it involves a banker who makes loan and receives payments from a given source of capital. The banker will only grant a loan if he can still meet the needs of other customers, based on their projected future loan requirements.

In order to evaluate the safety of the individual system states, deadlock avoidance algorithms generally require all processes to preclaim their maximum resource requirements prior to execution. Once its execution begins each process requests its resources as and when needed, up to the maximum preclaimed limit. Processes whose preclaimed resource requirements exceed the total capacity of the system are not admitted for execution.

The resource allocator keeps track of the number of the allocated and available resources of each type. The resource allocator also keeps track of the remaining number of resources preclaimed but not yet requested by each process.  A process that requests a temporarily unavailable resource is made to wait. If the requested resource is available for allocation, the resource allocator examines whether the granting of the request can lead to deadlock by checking whether each of the active processes could safely complete.

The resource allocation state at any instant is considered safe if resources can be allocated to each process, in some order, such that deadlock will not occur. An unsafe sate is a state in which a deadlock is possible.

As an example, consider a system with three processes P1, P2 and P3 and ten resources of the same type (e.g. magnetic tape). The maximum resource requirements and the current allocations are shown below:

PROCESS	MAX. NEED	CURRENT USAGE
P1	8	3
P2	5	1
P3	8	2

The state is safe because it is still possible for all three processes to finish. Process P2 could use the four available resources and finish its execution. This would release five resources, which could be taken up by process P1. This would produce eight resources, which would enable process P3 to finish. So the state is safe. Thus the key to a state being sage is that there is at least one way for all processes to finish.

Now consider the following state:

PROCESS	MAX. NEED	CURRENT USAGE
P1	9	3
P2	5	1
P3	8	2

This state is unsafe. Process P2 could use the four available resources and finish its execution. This would release five resources. But the available resources at this point cannot meet the maximum needs of either P1 or P3. So this state is unsafe. An unsafe state does not mean that a deadlock will happen, since the process may not in fact require their declared maximum needs, or some resources may be temporarily released. What an unsafe state does imply that some unfortunate sequence of events might lead to a deadlock.

After checking the effect of granting a request, the resource is allocated to the requesting process if the resource allocation can lead to a safe state; otherwise, the resource allocator suspends the requesting process until the desired resource can safely be granted.

The advantage of the deadlock avoidance is that it does not require the acquisition of all resources at once and it will not force preemption of resources. This eliminates the problem of resource idling due to premature acquisition.

The disadvantage of the deadlock avoidance is that process has to preclaim its maximum resource requirement. Preclaiming of resource need is not realistic for interactive systems and it has the tendency to overestimate the resource requirements. Another disadvantage of the deadlock avoidance is that the algorithm must be executed every time a resource request is made. For a multi-user system with a large number of user processes, the processing overhead would be severe.

 Next: Deadlock detection and recovery

Previous: Deadlock Prevention

Index:  Operating System