Coupon Accepted Successfully!



In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a wait state. It may happen that waiting processes will never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock.
A system consists of finite number of resources to be distributed among a number of competing resources. The resources are partitioned into types each of which may have several instances.
A process must request a resource before using it and must release it after using it. A process can request as many resources for carrying out its task; obviously this number has to be less than total available resources. A system table records whether each resource is free or allocated, and, if a resource is allocated, to which process. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.
A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused by only another process in the set. The events with which we are mainly concerned here are resource acquisition and release. For example, consider a system with three tape drives. Suppose that there are three processes, each holding one of these tape drives. If each process now requests another tape drive, the three processes will be in a deadlock state. Each is waiting for the event "tape drive is released," which can be caused only by one of the other waiting processes. This example illustrates a deadlock involving processes competing for the same resource type. Deadlocks may also involve different resource types.

Necessary condition for deadlocks

A deadlock situation can arise if the following four conditions hold simultaneously in a system.
1. Mutual exclusion: At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular wait: There must exist a set {P1, P2, ..., Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2,..., Pn-1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Resource Allocation Graph

A deadlock can be described more precisely in terms of a directed graph called a system resource allocation graph. In this graph the vertices represent two different types of nodes, one for active processes and other for resources. A directed edge from process Pi to resource type Rj denoted by Pi —>Rj signifies that process Pi requested an instance of resource type Rj and is currently waiting for that resource. A directed edge from resource type Rj to process Pi denoted by Rj —> Pi signifies that an instance of resource type Rj has been allocated to process Pi. A directed edge Pi —> Rj is called, a request edge and a directed edge Rj —> Pi is called an assignment edge.
When process P, requests an instance of resource type R, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource it releases the resource, and as a result the assignment edge is deleted.
P1 P2 P3
If the graph contains no cycles, then no process in the system is deadlocked. If, on the other hand, the graph contains a cycle, then a deadlock may exist. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for existence of deadlock.
If each resource type has several instances, then a cycle does not necessarily imply that a deadlock occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock.
If a resource-allocation graph does not have a cycle, then the system is not in a deadlock state. On the other hand, if there is a cycle, then the system may or may not be in a deadlock state.

Methods for handling deadlocks

Principally, there are three different methods for dealing with the deadlock problem:
  • We can use a protocol to ensure that the system will never enter a deadlock state. To ensure this, the system can use either deadlock prevention or deadlock avoidance scheme. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions of deadlock cannot hold. Deadlock avoidance, on the other hand, requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, we can decide for each request whether or not the process should wait.
  • We can allow the system to enter a deadlock state and then recover. In this environment, the system can provide an algorithm that examines the state of the system to determine whether a deadlock has occurred, and an algorithm to recover (if a deadlock has indeed occurred) from the deadlock.
  • We can ignore the deadlock problem all together, and pretend that they never occur in the system. This solution is the one used by most operating systems, including UNIX. Although this method does not seem to be a viable approach to the deadlock problem, it is nevertheless used in some operating systems. In many systems, deadlocks occur infrequently (say, once per year); thus, it is cheaper to use this method instead of the costly deadlock prevention, deadlock avoidance, or deadlock detection and recovery methods that must be used constantly.

Deadlock Prevention

By ensuring that at least one of the necessary conditions cannot hold, deadlock can be prevented.
1) Mutual Exclusion – This condition must hold for non-sharable resources like printer, which cannot be used simultaneously by several processes. Thus, deadlocks cannot be prevented b denying mutual exclusion condition. Some resources are intrinsically non-sharable.
2) Hold and Wait – To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a process requests a resource, it does not hold any other resources. This can be done in 2 ways. First, a process should ask for all the resources it needs before it starts executing. Second, if it asks for a resource in between, it must release all the resources previously held by it and then ask again for all the resources it needs.
These protocols have 2 main disadvantages –
 Resource utilization is low, since many resources may be held for long time, even when required for less time.
 Starvation is possible. A process needing many resources may not get a chance to execute as getting many resources may not be possible.
3) No Preemption – To ensure this condition does not hold, following protocol is followed. If a process requests some resources, check whether they are available. If they are, allocate them. If they are not available, check whether they are allocated to some other process that is waiting for additional resources. If so, preempt the desired resources from the waiting process and allocate them to the requesting process. If the resources are not either available or held by a waiting process, the requesting process must wait. While it is waiting, some of its resources may be preempted, but only if another process requests them. This protocol cannot be applied to resources like printers and tape drives.
4) Circular Wait – To ensure that the circular-wait condition never holds, impose a total ordering of all resource types, and ensure that each process requests resources in an increasing order of enumeration. Example - assign to each resource type a unique integer number, which allows to compare two resources and to determine whether one precedes another in our ordering. Then the following protocol can be used to prevent deadlocks: Each process can request resources only in an increasing order of enumeration. That is, a process can initially request any number of instances of a resource type, say Ri. After that, the process can request instances of resource type Rj if and only if F(Rj) > F(Ri). If several instances of the same resource type are needed, a single request for all of them must be issued.
Let the set of processes involved in the circular wait be {P0, P1, … , Pn}, where Pi is waiting for a resource Rj, which is held by process Pi+1. (Modulo arithmetic is used on the indexes, so that Pn is waiting for a resource Rn held by P0.) Then, since process Pi+i is holding resource Ri, while requesting resource Ri+1, we must have F(Ri) < F(Ri+1), for all i. But this condition means that F(R0) < F(R1) < ... < F(Rn) < F(R0). By transitivity, F(R0) < F(R0), which is impossible. Therefore, there can be no circular wait.

Deadlock Avoidance

A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. The resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
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. A sequence of processes is a safe sequence for the current allocation state if, for each Pi, the resources that Pi can still request can be satisfied by the currently available resources plus the resources held by all the Pj with j< i.
Safe, unsafe and deadlock state spaces. A safe state is not a deadlock state. Conversely, a deadlock state is an unsafe state. However, not all unsafe states are deadlocks. An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe (and deadlock) state.
  • Unsafe
  • deadlock
  • Safe
If only a single instance of each resource is present in the system, then a variant of resource allocation graph can be used to avoid deadlocks.
In this variant, in addition to request and assignment edge, a new type of edge, called a claim edge is used. A claim edge Pi -> Rj indicates that process Pi may request resource Rj at some time in future. This edge is represented by a dashed line in the graph. When the actual request is made, this edge is converted to request edge and on fulfillment of the request to assignment edge.
Suppose a process Pi requests resource rj. The request can be granted only if converting the request edge Pi -> Rj to an assignment edge Rj -> Pi does not result in the formation of cycle in the graph. Cycle detection in a graph requires n2 operations, where n is the number of processes in the system.


In figure a, if P2 requests R2 and if the request is fulfilled, the edge R2 -> P2 is formed which results in the formation of the cycle. Thus, to avoid the deadlock, this request must not be accepted.
R1 R1
R2 R2
a. before assignment b. after assignment


Banker’s Algorithm

The resource-allocation graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type. So, a less efficient algorithm commonly known as the banker's algorithm is used.
P1 P2
When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources the system must determine the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise the process must wait until some other process releases enough resources.
Several data structures must be maintained to implement the banker's algorithm. These data structures encode the state of the resource-allocation system. Let n be the number of processes in the system and m be the number of resource types. We need the following data structures:
Available: A vector of length m indicates the number of available resources of each type.
If Available[j] = k, there are k instances of resource type Rj available.
Max: An n x m matrix defines the maximum demand of each process. If Max [i, j] = k, then Pi may request at most k instances of resource type Rj.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. If Allocation [i, j] = k, then process Pi is currently allocated k instances of resource type Rj.
Need: An n x m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then Pi may need k more instances of resource type Rj to complete its task. Note that Need [i, j] = Max [i, j] – Allocation [i, j].

Safety algorithm

1. Let Work and Finish be vectors of length m and n, respectively. Initialize
Work= Available and Finish[i]=false for i = 1, 2,..., n.
2. Find an i such that both
a. Finish[i] = false
b. Needi < Work
If no such i exists, go to step 4.
3. Work= Work + Allocationi
Finish[i] = true
go to step 2.
4. If Finish[i] = true for all i, then the system is in a safe state.
This algorithm may require an order of m x n2 operations to decide whether a state is safe.

Resource request algorithm

Let Requesti be the request vector for process Pi. If Requesti[j] = k, then process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken:
1. If Requesti <= Needi, go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.
2. If Requesti <= Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
Available = Available - Requesti
Allocation = Allocation + Requesti
Needi = Needi - Requesti
If the resulting resource-allocation state is safe, the transaction is completed and process Pj is allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti and the old resource-allocation state is restored.


Consider a system with five processes P0 through P5 and three resource types A, B and C. Resource type A, B and C has 10, 5 and 7 instances respectively. Suppose that, at time T0, the following snapshot of the system exist:
Allocation Max Need(Allocation - Max)
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
Resources still available are A = 3, B = 3 and C = 2 instances.

In this condition, the system is in a safe state as there is a sequence < P1, P3, P4, P2, P0 > which satisfies the safety criteria. Now, suppose that the process P1 one instance of A and 2 instance of C, i.e., Request1 = (1, 0, 2). Now, after fulfilling the request and running the safety algorithm, we find that a safe sequence < P1, P3, P4, P0, P2 > exists. Thus, this request can be fulfilled. But, had process P0 made a Request4 = (0, 2, 0), then after fulfilling this request, no safe sequence will be obtained and hence, this request must not be fulfilled to avoid the deadlock.

Deadlock Detection

These algorithms are needed when the system does not have mechanisms to prevent deadlock or avoid it. Thus, chances of deadlocks occurring in the system are increased and system ten employs algorithms to detect the deadlock and then recover from it. This detection and recovery scheme requires overhead that includes not only the run-time costs of maintaining the necessary information and executing algorithm but also potential losses inherent in recovering from the deadlock.
For single instance of resources:
When all the resources existing in the system have single instance, then a variant of resource allocation graph called wait-for graph can be used to detect deadlocks. A waitfor graph is obtained by removing the nodes of type resource and collapsing the appropriate edges from the resource-allocation graph. More precisely, an edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi —> Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi —> Rq and Rq —> Pj for some resource:
Rq. A deadlock exists in the system if and only if the wait-for graph contains a cycle.
(a) Resource Allocation graph (b) corresponding wait-for graph
R1 R3 R4
R2 R5
P2 P3
P1 P2 P3
For several instances of resource, an algorithm similar to banker’s algorithm is used to detect deadlock.
Available: A vector of length m indicates the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process.
Request: An n x m matrix indicates the current request of each process. If Request [i, j]=k then process Pi is requesting k more instances of resource of type Rj.
The algorithm works as follows:
1. Let Work and Finish be vectors of length m and n, respectively. Initialize
Work:=Available. For i = l, 2… n, if Allocationi != 0, Finish[i] = false; otherwise,
Finish[i] := true.

2. Find an index i such that both
a. Finish[i] = false.
b. Requesti < Work.
If no such i exists, go to step 4.
3. Work := Work + Allocationi
Finish[i] := true
go to step 2.
4. If Finish[i] = false, for some i, 1 <= i <= n, then the system is in a deadlock state.
Moreover, if Finish[i] =false, then process Pi is deadlocked.
It also requires m x n2 operations to detect whether the system is in a deadlocked state.

Recovery from deadlock

When a detection algorithm determines that a deadlock exist the system must recover from the 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.
Process Termination:
To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.
  • Abort all deadlocked processes: This method clearly will break the deadlock cycle, but at a great expense, since these processes may have computed for a long time, and the results of these partial computations must be discarded, and probably must be recomputed later.
  •  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 in the middle will leave that file in an incorrect state. Many factors may determine which process is chosen for abortion, 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 resources 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
Resource Preemption:
To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.
If preemption is required to deal with deadlocks, then three issues need to be addressed:
1. Selecting a victim: As in process termination, we must determine the order of preemption 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 has thus 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.
3. Starvation: How do we ensure that starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process? In a system where victim selection is based primarily on cost factors, it may happen that the same process is always picked as a victim. As a result, this process never completes its designated task, a starvation situation that needs to be dealt with in any practical system. Clearly, we must ensure that a process can be picked as a victim only a (small) finite number of times.

Test Your Skills Now!
Take a Quiz now
Reviewer Name