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, a waiting
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.

Perhaps the best illustration of a deadlock can be drawn from a law passed by
the Kansas legislature early in the 20th century. It said, in part: “When two trains
approach each other at a crossing, both shall come to a full stop and neither
shall start up again until the other has gone.”

Page 315 : Galvin 9th Edition, Chapter 7 Deadlock

In this chapter, we describe methods that an operating system can use to

prevent or deal with deadlocks.

System Model

A system consists of a finite number of resources to be distributed among a

number of competing processes. The resources may be partitioned into several
types (or classes), each consisting of some number of identical instances. CPU
cycles, files, and I/O devices (such as printers and DVD drives) are examples of
resource types. If a system has two CPUs, then the resource type CPU has two
instances. Similarly, the resource type printer may have five instances. Various
synchronization tools, such as mutex locks and semaphores. These tools are also
considered system resources, and they
are a common source of deadlock.

Resources:

Type: 1. Serially /Simultaneously Re-Usable

2. PreEmptive/ Non-PreEmptive

A process must request a resource before using it and must release the resource
after using it. A process may request as many resources as it requires to carry
out its designated task. Under the normal mode of operation, a process may
utilize a resource in only the following sequence:

1. Request. The process requests the resource. If the request cannot be

granted immediately (for example, if the resource is being used by another
process), then the requesting process must wait until it can acquire the
resource.

2. Use. The process can operate on the resource (for example, if the resource is
a printer, the process can print on the printer).

3. Release. The process releases the resource.

The request and release of resources may be system calls.

Examples are the system calls such as :

 request() and release() device,
  open() and close() file,
 allocate() and free() memory.

As we saw, the request and release of semaphores can be accomplished through

the wait() and signal() operations on semaphores or through acquire() and
release() of a mutex lock. For each use of a kernel-managed resource by a
process or thread, the operating system checks to make sure that the process
has requested and has been allocated the resource. A system table records
whether each resource is free or allocated. For each resource that is allocated,
the table also records the process to which it is
allocated. 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 deadlocked state when every process in the set is

waiting for an event that can be caused only by another process in the set. The
events with which we are mainly concerned here are resource acquisition and
release. The resources may be either physical resources (for example, printers,
tape drives, memory space, and CPU cycles) or logical resources (for example,
semaphores, mutex locks, and files). However, other types of events may result
in deadlocks (for example, the IPC facilities discussed in Chapter 3).

To illustrate a deadlocked state, consider a system with three CD RW drives.

Suppose each of three processes holds one of these CD RW drives. If each process
now requests another drive, the three processes will be in a deadlocked state.
Each is waiting for the event “CD RW is released,” which can be caused only by
one of the other waiting processes. This example illustrates a deadlock involving
the same resource type.
Deadlocks may also involve different resource types. For example, consider a
system with one printer and one DVD drive. Suppose that process Pi is holding the
DVD and process Pj is holding the printer. If Pi requests the printer and Pj requests
the DVD drive, a deadlock occurs.
Developers of multithreaded applications must remain aware of the possibility of
deadlocks. The locking tools presented in Chapter 5 are designed to avoid race
conditions. However, in using these tools, developers must pay careful attention
to how locks are acquired and released. Otherwise, deadlock can occur, as
illustrated in the dining-philosophers problem in Section 5.7.3.

Deadlock Characterization

Necessary Conditions

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 nonsharable

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. 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
P 0.

We emphasize that all four conditions must hold for a deadlock to occur. The
circular-wait condition implies the hold-and-wait condition, so the four conditions
are not completely independent. However, that it is useful to consider each
condition separately.

Resource-Allocation Graph

Deadlocks can be described more precisely in terms of a directed graph called a

system resource-allocation graph. This graph consists of a set of vertices V
and a set of edges E. The set of vertices V is partitioned into two different types
of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the
system, and R = {R1, R2, ..., Rm}, the set consisting of all resource types in the
system.
A directed edge from process Pi to resource type Rj is denoted by Pi → Rj; it
signifies that process Pi has requested an instance of resource type Rj and is
currently waiting for that resource. A directed edge from resource type Rj to
process Pi is denoted by Rj → Pi; it signifies that an instance of resource
type Rj has been allocated to process Pi. A directed edge Pi → Rj is called a
request edge; a directed edge Rj → Pi is called an assignment edge.

Pictorially, we represent each process Pi as a circle and each resource type Rj as

a rectangle. Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle. Note that a request
edge points to only the rectangle Rj, whereas an assignment edge must also
designate one of the dots in the rectangle.

When process Pi requests an instance of resource type Rj, 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. As a
result, the assignment edge is deleted.

Methods for Handling Deadlocks

Generally speaking, we can deal with the deadlock problem in one of three
ways:
• We can use a protocol to prevent or avoid deadlocks, ensuring that the system
will never enter a deadlocked state.
• We can allow the system to enter a deadlocked state, detect it, and recover.
• We can ignore the problem altogether and pretend that deadlocks never occur
in the system..

1. To ensure that deadlocks never occur, the system can use either a
deadlock prevention or a deadlock-avoidance scheme. Deadlock
prevention provides a set of methods to ensure that at least one of the
necessary conditions (Section 7.2.1) cannot hold. These methods prevent
deadlocks by constraining how requests for resources can be made.
2. Deadlock avoidance requires that the operating system be given
additional information in advance concerning which resources a process
will request and use during its lifetime. With this additional knowledge, the
operating system can decide for each request whether or not the process
should wait. To decide whether the current request can be satisfied or
must be delayed, the system must consider the resources currently
available, the resources currently
allocated to each process, and the future requests and releases of each
process. We discuss these schemes in Section 7.5.
3. If a system does not employ either a deadlock-prevention or a
deadlockavoidance algorithm, then a deadlock situation may arise. 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 from the deadlock (if a deadlock has indeed
occurred). We discuss these issues in Section 7.6 and Section 7.7.

Deadlock Prevention

As we noted in Section 7.2.1, 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
2. Hold and Wait
3. No PreEmption
4. Circular Wait

The fourth and final condition for deadlocks is the circular-wait condition. One
way to ensure that this condition never holds is to impose a total ordering of all
resource types and to require that each process requests resources in an
increasing order of enumeration. To illustrate, we let R = {R1, R2, ..., Rm} be the
set of resource types. We assign to each resource type a unique integer number,
which allows us to compare two resources and to determine whether one
precedes another in our ordering. Formally, we define a one-to-one function F: R
→ N, where N is the set of natural numbers. 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. Alternatively, we can require that a
process requesting an instance of resource type Rj must have released any
resources Ri such that F(Ri) ≥ F(Rj). Note also that if several instances of the
same resource type are needed, a single request for all of them must be issued.
If these two protocols are used, then the circular-wait condition cannot hold. 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. (Modulo arithmetic is used on the indexes, so that Pn is waiting for a
resource Rn held by P0.) 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 [Link] can accomplish
this scheme in an application program by developing an ordering among all
synchronization objects in the system. All requests for synchronization objects
must be made in increasing order. For example, if the lock ordering in the
Pthread program shown in Figure 7.4 was F (first mutex) = 1 F (second mutex) =
5
then thread two could not request the locks out of order. Keep in mind that
developing an ordering, or hierarchy, does not in itself prevent deadlock. It is up
to application developers to write programs that
follow the ordering. Also note that the function F should be defined according to
the normal order of usage of the resources in a system.

Deadlock Avoidance
Deadlock-prevention algorithms, as discussed in Section 7.4, prevent deadlocks
by limiting how requests can be made. The limits ensure that at least one of the
necessary conditions for deadlock cannot occur. 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, 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. Each
request requires that in making this decision the system consider the resources
currently available, the resources currently allocated to each process, and the
future requests and releases of each process. The various algorithms that use
this approach differ in the amount and type of information required. 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. A deadlock-avoidance algorithm dynamically
examines the resource-allocation state to ensure that a circular-wait condition
can never exist. The resourceallocation state is defined by the number of
available and allocated resources
and the maximum demands of the processes. In the following sections, we
explore two deadlock-avoidance algorithms.

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 if, for each Pi, the
resource requests that Pi can still make can be satisfied by the currently
available resources plus the resources held by all Pj, with j < i. In this situation, if
the resources that Pi needs are not immediately available, then Pi can wait until
all Pj have finished. When they have finished, Pi can obtain all of its needed
resources, complete its designated task, return its allocated resources,
and terminate. When Pi terminates, Pi+1 can obtain its needed resources, and so
on. If no such sequence exists, then the system state is said to be unsafe. A safe
state is not a deadlocked state. Conversely, a deadlocked state is an unsafe
state. Not all unsafe states are deadlocks, however (Figure 7.6).
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 behavior of the processes controls
unsafe states.
 To illustrate, we consider a system with twelve magnetic tape drives and three
processes: P0, P1, and P2. Process P0 requires ten tape drives, process P1 may
need as many as four tape drives, and process P2 may need up to nine tape
drives. Suppose that, at time t0, process P0 is holding five tape drives, process P1
is holding two tape drives, and process P2 is holding two tape drives. (Thus, there
are three free tape drives.)

At time t0, the system is in a safe state. The sequence <P1, P0, P2> satisfies the
safety condition. Process P1 can immediately be allocated all its tape drives and
then return them (the system will then have five available tape drives); then
process P0 can get all its tape drives and return them (the system will then have
ten available tape drives); and finally process P2 can get all its tape drives
and return them (the system will then have all twelve tape drives available). A
system can go from a safe state to an unsafe state. Suppose that, at time t1,
process P2 requests and is allocated one more tape drive. The system is no
longer in a safe state. At this point, only process P1 can be allocated all its tape
drives. When it returns them, the system will have only four available tape
drives. Since process P0 is allocated five tape drives but has a maximum of ten, it
may request five more tape drives. If it does so, it will have to wait, because they
are unavailable. Similarly, process P2 may request six additional tape drives and
have to wait, resulting in a deadlock. Our mistake was in granting the request
from process P2 for one more tape drive. If we had made P2 wait until either of
the other processes had finished and released its resources, then we could have
avoided the deadlock. Given the concept of a safe 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 requests 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 requests a resource that is currently available, it may still have to wait.
Thus, resource utilization may be lower than it would otherwise be.
Resource-Allocation-Graph Algorithm

If we have a resource-allocation system with only one instance of each resource

type, we can use a variant of the resource-allocation graph defined in Section
7.2.2 for deadlock avoidance. In addition to the request and assignment edges
already described, we introduce a new type of edge, called a claim edge.
A claim edge Pi → Rj indicates that process Pi may request resource Rj at
some time in the future. This edge resembles a request edge in direction but is
represented in the graph by a dashed line. When process Pi requests resource Rj,
the claim edge Pi → Rj is converted to a request edge. Similarly, when a
resource Rj is released by Pi, the assignment edge Rj → Pi is reconverted to a
claim edge Pi → Rj.

Note that the resources must be claimed a priori in the system. That is,
before process Pi starts executing, all its claim edges must already appear in
the resource-allocation graph. We can relax this condition by allowing a claim
edge Pi → Rj to be added to the graph only if all the edges associated with
process Pi are claim edges.

R1 R2
P2
P1
Figure 7.7 Resource-allocation graph for deadlock avoidance.

Now suppose that 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 a cycle in the resource-allocation
graph. We check for safety by using a cycle-detection algorithm. An algorithm
for detecting a cycle in this graph requires an order of n2 operations, where n
is the number of processes in the system.
If no cycle exists, then the allocation of the resource will leave the system
in a safe state. If a cycle is found, then the allocation will put the system in
an unsafe state. In that case, process Pi will have to wait for its requests to be
satisfied.
To illustrate this algorithm, we consider the resource-allocation graph of
Figure 7.7. Suppose that P2 requests R2. Although R2 is currently free, we
cannot allocate it to P2, since this action will create a cycle in the graph (Figure
7.8). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1
requests R2, and P2 requests R1, then a deadlock will occur.
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. The name was chosen because the
algorithm could be used in a banking system to ensure that the bank never
allocated its available cash in such a way that it could no longer satisfy the
needs of all its customers.

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. If Available[j] equals k, then k instances of resource type Rj
are available.

• 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. If Allocation[i][j] equals k, then
process
Pi is currently allocated k instances of resource type Rj.

• Need. An n × m matrix indicates the remaining resource need of each

process. If Need[i][j] equals k, then process Pi may need k more instances
of resource type Rj to complete its task. Note that Need[i][j] equals Max[i]
[j]
− Allocation[i][j].

These data structures vary over time in both size and value.
To simplify the presentation of the banker’s algorithm, we next establish
some notation. Let X and Y be vectors of length n. We say that X ≤ Y if and
only if X[i] ≤ Y[i] for all i = 1, 2, ..., n.
For example, if X = (1,7,3,2) and Y =
(0,3,2,1), then Y ≤ X.
In addition, Y < X if Y ≤ X and Y = X.
We can treat each row in the matrices Allocation and Need as vectors
and refer to them as Allocationi and Needi. The vector Allocationi specifies
the resources currently allocated to process Pi; the vector Needi specifies the
additional resources that process Pi may still request to complete its task.
[Link] Safety Algorithm
We can now present the algorithm for finding out whether or not a system is
in a safe state. This algorithm can be described as follows:
1. Let Work and Finish be vectors of length m and n, respectively. Initialize
Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.
2. Find an index 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 × n2 operations to determine whether
a state is safe.
[Link] Resource-Request Algorithm
Next, we describe the algorithm for determining whether requests can be safely
granted.
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 ;
Allocationi = Allocationi + Requesti;
Needi = Needi –Requesti ;
If the resulting resource-allocation state is safe, the transaction is completed,
and process Pi 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.

An Illustrative Example
To illustrate the use of the banker’s algorithm, consider a system with five
processes P0 through P4 and three resource types A, B, and C. Resource type A
has ten instances, resource type B has five instances, and resource type C has
seven instances. Suppose that, at time T0, the following snapshot of the system
has been taken:
The content of the matrix Need is defined to be Max − Allocation and is as
follows:

We claim that the system is currently in a safe state. Indeed,

the sequence
<P1, P3, P4, P2, P0> satisfies the safety criteria. Suppose now that process
P1 requests one additional instance of resource type A and two instances of
resource type C, so Request1 = (1,0,2). To decide whether this request can be
immediately granted, we first check that Request1 ≤ Available—that is, that
(1,0,2) ≤ (3,3,2), which is true. We then pretend that this request has been
fulfilled, and we arrive at the following new state:

We must determine whether this new system state is safe. To do so, we

execute our safety algorithm and find that the sequence <P1, P3, P4, P0, P2>
satisfies the safety requirement. Hence, we can immediately grant the request
of process P1.
You should be able to see, however, that when the system is in this state, a
request for (3,3,0) by P4 cannot be granted, since the resources are not
available.
Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the
resources are available, since the resulting state is unsafe.
LAB EXERCISE: Programming exercise for students to implement
the
banker’s algorithm.