DEADLOCKS

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 waiting state. Sometimes, awaiting process is never again
able to change state, because the resources it has requested are held by other waiting

processes. This situation is called a deadlock.

Fig3.14: Resource-allocation graph with a deadlock

Necessary and Sufficient Conditions for Deadlock

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 pre-emption. Resources cannot be pre-empted; that is, a resource can be released
only voluntarily by the process holding it, after that process has completed its task.
4.Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is
waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is
waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

Fig3.15 Deadlock

Deadlock Prevention
For a deadlock to occur, each of the four necessary conditions must hold. By ensuring
that at least one of these conditions cannot hold, we can prevent the occurrence of a
deadlock.
1. Mutual Exclusion:

The mutual exclusion condition must hold. That is, at least one resource must be non
sharable. Sharable resources, in contrast, do not require mutually exclusive access and
thus cannot be involved in a deadlock. Read-only files are a good example of a sharable
resource. If several processes attempt to open a read-only file at the same time, they can
be granted simultaneous access to the file. A process never needs to wait for a sharable
resource. In general, however, we cannot prevent deadlocks by denying the mutual-
exclusion condition, because some resources are intrinsically non sharable. For example,
a mutex lock cannot be simultaneously shared by several processes.
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.
One protocol that we can use requires each process to request and be allocated all its
resources before it begins execution.
An alternative protocol allows a process to request resources only when it has none. A
process may request some resources and use them. Before it can request any additional
resources, it must release all the resources that it is currently allocated.
To illustrate the difference between these two protocols, we consider a process that
copies data from a DVD drive to a file on disk, sorts the file, and then prints the results to
a printer.
If all resources must be requested at the beginning of the process, then the process
must initially request the DVD drive, disk file, and printer. It will hold the printer for its
entire execution, even though it needs the printer only at the end.
The second method allows the process to request initially only the DVD drive and disk
file. It copies from the DVD drive to the disk and then releases both the DVD drive and
the disk file. The process must then request the disk file and the printer. After copying the
disk file to the printer, it releases these two resources and terminates.
Both these protocols have main disadvantage.
First, resource utilization may be low, since resources may be allocated but unused for a
long period. In the example given, for instance, we can release the DVD drive and disk
file, and then request the disk file and printer, only if we can be sure that our data will
remain on the disk file.
3. No Pre-emption:
The third necessary condition for deadlocks is that there be no pre-emption of resources
that have already been allocated. To ensure that this condition does not hold, we can use
the following protocol. If a process is holding some resources and requests another
resource that cannot be immediately allocated to it (that is, the process must wait), then
all resources the process is currently holding are pre-empted. In other words, these
resources are implicitly released. The pre-empted resources are added to the list of
resources for which the process is waiting. The process will be restarted only when it can
regain it sold resources, as well as the new ones that it is requesting.
Alternatively, if a process requests some resources, we first check whether they are
available. If they are, we allocate them. If they are not, we check whether they are
allocated to some other process that is waiting for additional resources. If so, we preempt
the desired resources from the waiting process and allocate them to the requesting
process. If the resources are neither available nor held by a waiting process, the
requesting process must wait.
4. Circular Wait:

The fourth and final condition for deadlocks is the circular-wait condition. To
illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We assign to each
resource type a unique integer number,
For example, if the set of resource types R includes tape drives, disk drives, and printers,
then the function F might be defined as follows:
F(tape drive) = 1
F(disk drive) = 5
F(printer) = 12
We can now consider the following protocol 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 ).
For example, using the function defined previously, a process that wants to use the tape
drive and printer at the same time must first request the tape drive and then request the
printer.
We can demonstrate this fact by assuming that a circular wait exists (proof by
contradiction). Let the set of processes involved in the circular wait be {P0, P1, ..., Pn},
where Pi is waiting for a resource Ri, which is held by process Pi+1. Then, since process
Pi+1 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

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, the system might need to
know that process P will request first the tape drive and then the printer before releasing
both resources, whereas process Q will request first the printer and then the tape drive.
With this knowledge of the complete sequence of requests and releases for each process,
the system can decide for each request whether or not the process should wait in order to
avoid a possible future deadlock.
 The simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need. Given this a priori information, it is
possible to construct an algorithm that ensures that the system will never enter a
deadlocked state.
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<P1, P2, ..., Pn> is a safe sequence
for the current allocation state
A safe state is not a deadlocked state. Conversely, a deadlocked 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 deadlocked) states. In
an unsafe state, the operating system cannot prevent processes from requesting resources
in such a way that a deadlock occurs. The behaviour of the processes controls unsafe
states.

Fig3.17: Safe, unsafe, and deadlocked state spaces

2. Banker’s Algorithm:

The resource-allocation-graph algorithm is not applicable to a resource allocation system

with multiple instances of each resource type. The deadlock avoidance algorithm that we
describe next is applicable to such a system but is less efficient than the resource-
allocation graph scheme. This algorithm is commonly known as the banker’s algorithm.
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 whether 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. We need the following
data structures, where n is the number of processes in the system and m is the number of
resource types:
• Available :A vector of length m indicates the number of available resources of each
type.
• Max. An n × m matrix defines the maximum demand of each process.
If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj.
• Allocation. An n × m matrix defines the number of resources of each type currently
allocated to each process
• Need. An n × m matrix indicates the remaining resource need of each process. Note that
Need[i][j] equals Max[i][j]− Allocation[i][j].
Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work
= Available Finish [i] = false for i = 0, 1, …,n- 1
2. Find an i such that both:
(a) Finish [i] = = false
(b) Need i <= Work
If no such i exists, go to step 4

3. Work = Work + Allocation i

Finish[i] = true
go to step 2
 4. If Finish [i] == true for all i, then the system is in a safe state

Resource-Request Algorithm for Process Pi

Let Requesti be the request vector for process Pi. If Requesti [j] = = k then process Pi

wants k instances of resource type Rj

1. If Requesti <= Needi go to step 2. Otherwise, raise error condition, since process has
exceeded its maximum claim

2. If Requesti <= Available, go to step 3. Otherwise Pi must wait, since resources are
not available

3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Available = Available –Requesti;

Allocationi =Allocationi + Requesti;

Needi =Needi – Requesti;

 If safe the resources are allocated to Pi
 If unsafe Pi must wait, and the old resource-allocation state is restored
If the resulting resource-allocation state is safe, the transaction is completed, and process
Pi is allocated its resources.

Deadlock Detection

If a system does not employ either a deadlock-prevention or a deadlock avoidance

algorithm, then a deadlock situation may occur. In this environment, the system may
provide:
• An algorithm that examines the state of the system to determine whether a deadlock has
occurred
• An algorithm to recover from the deadlock

1. Single Instance of Each Resource Type:

If all resources have only a single instance, then we can define a deadlock
detection algorithm that uses a variant of the resource-allocation graph, called a wait-for
graph. We obtain this graph from the resource-allocation graph by removing the resource
nodes and collapsing the appropriate edges.
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.

Fig3.18: (a) Resource-allocation graph. (b) Corresponding wait-for graph

2. Several Instances of a Resource Type:

The wait-for graph scheme is not applicable to a resource-allocation system with
multiple instances of each resource type. We turn now to a deadlock detection algorithm
that is applicable to such a system.
• Available: A vector of length m indicates the number of available resources of each
type.
• Allocation. An n × m matrix defines the number of resources of each type currently
allocated to each process.
• Request. An n × m matrix indicates the current request of each process .If Request[i][j]
equals k, then process Pi is requesting k more instances of resource type Rj.
3. Detection-Algorithm Usage:

When should we invoke the detection algorithm? The answer depends on two factors:
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it happens? If deadlocks occur
frequently, then the detection algorithm should be invoked frequently. Resources
allocated to deadlocked processes will be idle until the deadlock can be broken. In
addition, the number of processes involved in the deadlock cycle may grow.
Deadlocks occur only when some process makes a request that cannot be granted
immediately.
If there are many different resource types, one request may create many cycles in the
resource graph, each cycle completed by the most recent request and “caused” by the one
identifiable process.

Recovery from Deadlock

When a detection algorithm determines that a deadlock exists, several alternatives

are available. One possibility is to inform the operator that a deadlock has occurred and to
let the operator deal with the deadlock manually. Another possibility is to let the system
recover from the deadlock automatically. There are two options for breaking a deadlock.
One is simply to abort one or more processes to break the circular wait. The other is to
pre-empt 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 allocated to the terminated processes.

• Abort all deadlocked processes. This method clearly will break the deadlock cycle, but
at great expense. The deadlocked processes may have computed for a long time, and the
results of these partial computations must be discarded and probably will have to 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.
2. Resource Pre-emption:

To eliminate deadlocks using resource pre-emption, we successively 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 three 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 deadlocked process is
holding and the amount of time the process has thus far consumed.
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 pre-empted from the same process?