Methods for Handling Deadlocks: Deadlock Avoidance

 

Deadlock Avoidance:

 

Deadlock prevention algorithms prevent deadlocks by restraining how requests can be made. Possible side effects of preventing deadlocks by this method however are low device utilization and reduced system throughput.

 

An alternative method for avoiding deadlocks is to require additional information about how resources are to be requested. For example in a system with one tape drive and one printer, we might be told that process ‘P’ will request first the tape drive, and later the printer, before releasing  both resources. Process ‘Q’, on the other hand, will request first the printer and then the tape drive.

 

With this knowledge of the complete sequence of request and release for each process we can decide for each request whether or not the process should wait.

 

Each request requires that the system consider the resources currently available, the resources currently allocated to each process, and the future request and releases of each process, to decide whether the current request can be satisfied or must wait to avoid a possible future deadlock.

 

The simplest and most useful model requires that each process declared the maximum number of resources of each type that it may need.

 

Given a priori information about the maximum number of resources of each type that may be requested for each process, it is possible to construct an algorithm that ensures that the system will never enter a deadlock state.

 

This algorithm defines the deadlock avoidance approach. A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that the circular wait condition can never exist.

 

The resource allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

 

1.    Safe State: A state is safe if the system can allocate resources to each process up to its maximum in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence.

 

A sequence of processes <P₁,P₂,...,P_n> is a sequence for the current allocation state if, for  each P_i  the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all the P_j with j<i. If no such sequence exists then the system state is said to be unsafe.

(Safe, unsafe and deadlock state spaces)

A safe state is not a deadlock state. Conversely, a deadlock state is an unsafe state.

 

Not all unsafe states are deadlocks; however an unsafe state may lead to a deadlock.

 

As long as the state is safe, the operating system can avoid unsafe and deadlock states.

 

In an unsafe state, the operating system cannot prevent the processes from requesting resources such that a deadlock occurs.

 

Given the concept of unsafe state, we can define avoidance algorithms that ensure that the system will never deadlock. The idea is simply to ensure that the system will always remain in a safe state.

 

Initially, the system is in a safe state. Whenever a process request a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait. The request is granted only if the allocation leaves the system in a safe state.

 

In this scheme, if a process request resource that is currently available, it may still have to wait. Thus, resource utilization may be lower than it would be without a deadlock avoidance algorithm.

 

 

 

2.    Resource Allocation Graph Algorithm:

 

If we have a resource allocation system with only one instance of each resource type, a variant of the resource allocation graph can be used for deadlock avoidance.

 

In addition to the request and assignment edges, we introduce a new type of edge called claim edge.

 

A claim edge P_i ->R_j indicates that process P_i may request resource R_j at some time in the future. This edge resembles request edge in direction, but it is separated by a dashed line.

 

When process P_i request resource R_j, the claim edge P_i ->R_j is converted to request edge.

 

Similarly, when a resource R_j is released by P_i, the assignment edge R_j->P_i is already converted to a claim edge P_i ->R_j.

 

Note that the resources must be claimed a priori in the system i.e. before process P_i   starts executing, all its claim edges must already appeared in the resource allocation graph.

 

An algorithm for detecting a cycle in the graph acquires an order of n² operations, where ‘n’ is the number of processes in the system.

(Resource allocation graph for deadlock avoidance)

If no cycle exists then the allocation of the resource will leave the system in a safe state.

 

If cycle is found, then the allocation will put the system in an unsafe state.