OPERATING SYSTEM

LESSON 8 (DEADLOCKS)
DEADLOCKS

 Computer systems are full of resources that can

only be used by one process at a time. Common
examples include printers, tape drives, and slots
in the system’s internal tables. Having two
processes simultaneously writing to the printer
leads to rubbish.
 Consequently, all operating systems have the
ability to (temporarily) grant a process exclusive
access to certain resources. For many
applications, a process needs exclusive access to
not one resource, but several.
2
 Suppose, for example, two processes each want to
record a scanned document on a CD. Process A
requests permission to use the scanner and is
granted it. Process B is programmed differently
and requests the CD recorder first and is also
granted it. Now A asks for the CD recorder, but
the request is denied until B releases it.
Unfortunately, instead of releasing the CD
recorder B asks for the scanner. At this point
both processes are blocked and will remain so
forever. This situation is called a deadlock.

3
RESOURCES
 A resource can be a hardware device (e.g., a tape
drive) or a piece of information (e.g., a locked
record in a database). For some resources, several
identical instances may be available, such as
three tape drives. When several copies of a
resource are available, any one of them can be
used to satisfy any request for the resource. In
short, a resource is anything that can be used by
only a single process at any instant of time.

4
PREEMPTABLE AND NONPREEMPTABLE
RESOURCES
 Resources come in two types: preemptable and
nonpreemptable.
 A preemptable resource is one that can be taken
away from the process owning it with no negative
effects. Memory is an example of a preemptable
resource. Consider, for example, a system with 32
MB of user memory, one printer, and two 32-MB
processes that each want to print something.
Process A requests and gets the printer, then
starts to compute the values to print. Before it
has finished with the computation, it exceeds its
time quantum and is swapped out. 5
 Process B now runs and tries, unsuccessfully, to
acquire the printer. Potentially, we now have a
deadlock situation, because A has the printer and
B has the memory, and none of them can proceed
without the resource held by the other.
Fortunately, it is possible to preempt (take away)
the memory from B by swapping it out and
swapping A in. Now A can run, do its printing,
and then release the printer. No deadlock occurs.
 In contrast, a nonpreemptable resource is one
that cannot be taken away from its current
owner process. If a process has begun to burn a
CD-ROM, suddenly taking the CD recorder away
from it and giving it to another process will result
in a garbled CD, CD recorders are not
preemptable at an arbitrary moment. 6
 In general, deadlocks involve nonpreemptable
resources. Potential deadlocks that involve preemptable
resources can usually be resolved by reallocating
resources from one process to another. Thus our
treatment will focus on nonpreemptable resources.
 The sequence of events required to use a resource is
given below in an abstract form.
 Request the resource.
 Use the resource.
 Release the resource.
 If the resource is not available when it is requested, the
requesting process is forced to wait. In some operating
systems, the process is automatically blocked when a
resource request fails, and awakened when it becomes
available. In other systems, the request fails with an
error code, and calling process waits a little while and
try again.
7
RESOURCE ACQUISITION
 For some kinds of resources, such as records in a
database system, it is up to the user processes to
manage resource usage themselves. One possible
way of allowing user management of resources is
to associate a semaphore with each resource. The
three steps listed above are then implemented as a
down on the semaphore to acquire the resource,
using the resource, and finally an up on the
resource to release it.
 Sometimes processes need two or more resources.
They can be acquired sequentially.
8
As long as only one process is involved, everything
works fine. Because there is no competition for
resources.
9
 Now let us consider a situation with two processes,
A and B, and two resources.

(No Deadlock) (DeadLock May Occur)

10
DEADLOCK DEFINITION

 Each member of the set of deadlocked process is

waiting for a resource that is owned by a
deadlocked process. None of the processes can
run, none of them can release any resources, and
none of them can be awakened. The number of
processes and the number of resources possessed
and requested are unimportant. This result holds
for any kind of resource, including both hardware
and software.

11
CONDITIONS FOR DEADLOCK
 Four conditions must hold to be a deadlock:
1. Mutual exclusion condition. Each resource is either
currently assigned to exactly one process or is
available.
2. Hold and wait condition. Processes currently holding
resources granted earlier can request new resources.
3. No preemption condition. Resources previously
granted cannot be forcibly taken away from a process.
They must be explicitly released by the process
holding them.
4. Circular wait condition. There must be a circular chain
of two or more processes, each of them is waiting for a
resource held by the next member of the chain.
 All four of these conditions must be present for a
deadlock to occur. If one of them is absent, no 12
deadlock is possible.
DEADLOCK MODELING
 Four conditions (cause deadlock) can be modeled
using directed graphs. The graphs have two kinds of
nodes: processes, shown as circles, and resources,
shown as squares.
 An arc from a resource node (square) to a process
node (circle) means that the resource has previously
been requested by, granted to, and is currently held
by that process (Fig. a). An arc from a process to a
resource means that the process is currently blocked
waiting for that resource (Fig. b).

13
 In Fig. (c) we see a deadlock: process C is waiting
for resource T, which is currently held by process
D. Process D is not about to release resource T
because it is waiting for resource U, held by C.
Both processes will wait forever. A cycle in the
graph means that there is a deadlock involving
the processes and resources in the cycle. In this
example, the cycle is C–T–D–U–C

14
 Imagine that we have three processes, A, B, and C,
and three resources R, S, and T.

15
 If the operating system knew about the how to
handle deadlocks, it could suspend B instead of
granting it S.

16
 In general, four strategies are used for dealing with
deadlocks.

1. Just ignore the problem altogether. Maybe if

you ignore it, it will ignore you.
2. Detection and recovery. Let deadlocks occur,
detect them, and take action.
3. Dynamic avoidance by careful resource
allocation.
4. Prevention, by structurally negating one of the
four conditions necessary to cause a deadlock.

17
1.THE OSTRİCH ALGORİTHM
 The simplest approach is the ostrich algorithm: stick
your head in the sand and pretend there is no problem
at all. Different people react to this strategy in different
ways.
 Mathematicians find it totally unacceptable and say
that deadlocks must be prevented at all costs.
Engineers ask how often the problem is expected, how
often the system crashes for other reasons, and how
serious a deadlock is. If deadlocks occur on the average
once every five years, but system crashes due to
hardware failures, compiler errors, and operating
system bugs occur once a week, most engineers would
not be willing to pay a large penalty in performance or
18
convenience to eliminate deadlocks.
 Most operating systems, including UNIX and
Windows, just ignore the problem on the
assumption that most users would prefer an
occasional deadlock to a rule restricting all users.

 If deadlocks could be eliminated for free, there

would not be much discussion. The problem is that
the price is high, mostly in terms of putting
inconvenient restrictions on processes. Thus we are
faced with an unpleasant trade-off between
convenience and correctness.

19
2.DEADLOCK DETECTION AND
RECOVERY

 When this technique is used, the system does not

attempt to prevent deadlocks from occurring.
Instead, it lets them occur, tries to detect when
this happens, and then takes some action to
recover after the fact.

20
1.DEADLOCK DETECTION WITH ONE
RESOURCE OF EACH TYPE

 Let us begin with the simplest case: only one

resource of each type exists. Such a system might
have one scanner, one CD recorder, one plotter,
and one tape drive, but no more than one of each
class of resource.
 For such a system, we can construct a resource
graph. If this graph contains one or more cycles,
a deadlock exists. Any process that is part of a
cycle is deadlocked. If no cycles exist, the system
is not deadlocked.
21
As an example:
1. Process A holds R and wants S.

2. Process B holds nothing but wants T.

3. Process C holds nothing but wants S.

4. Process D holds U and wants S and T.

5. Process E holds T and wants V.

6. Process F holds W and wants S.

7. Process G holds V and wants U.

22
 The algorithm:
1. For each node, N in the graph, perform the following 5
steps with N as the starting node.
2. Initialize L to the empty list, and designate all the arcs as
unmarked.
3. Add the current node to the end of L and check to see if
the node now appears in L two times. If it does, the graph
contains a cycle (listed in L) and the algorithm
terminates.
4. From the given node, see if there are any unmarked
outgoing arcs. If so, go to step 5; if not, go to step 6.
5. Pick an unmarked outgoing arc at random and mark it.
Then follow it to the new current node and go to step 3.
6. We have now reached a dead end. Remove it and go back
to the previous node, that is, the one that was current just
before this one, make that one the current node, and go to
step 3. If this node is the initial node, the graph does not
contain any cycles and the algorithm terminates.
L is a data structure keeps a list of nodes. 23
 What this algorithm does is take each node, in
turn, as the root of a tree, and does a depth-first
search on it. If it ever comes back to a node it has
already encountered, then it has found a cycle. If
it exhausts all the arcs from any given node, it
backtracks to the previous node. If it backtracks
to the root and cannot go further, the subgraph
reachable from the current node does not contain
any cycles. If this property holds for all nodes, the
entire graph is cycle free, so the system is not
deadlocked.

24
 We start at R and initialize L to the empty list. L =
[R, A, S]. S has no outgoing arcs, so it is a dead end,
forcing us to backtrack to A, L = [R, A ]. Since A has
no unmarked outgoing arcs, we backtrack to R,
completing our inspection of R.
 Now we restart the algorithm starting at A,
resetting L to the empty list. L = [A, S]. So we start
again at B. L=[B, T, E, V, G, U, D, T]

25
2. DEADLOCK DETECTION WITH
MULTIPLE RESOURCE OF EACH TYPE
 When multiple copies of some of the resources
exist, a different approach is needed to detect
deadlocks. We will now present a matrix-based
algorithm for detecting deadlock among n
processes, P1 through Pn. m resource classes, E is
the existing resource vector of m resources.
For example, if resource1 is tape drive, then E1 =
2 means the system has two tape drives.
 A is the available resource vector, with Ai
giving the number of instances of resource i that
are currently available. If both of our two tape
drives are assigned, A1 will be 0. 26
 C, the current allocation matrix, and R, the
request matrix. The i-th row of C tells how many
instances of each resource class Pi currently holds.
Thus Cij is the number of instances of resource j
that are held by process i. Similarly, Rij is the
number of instances of resource j that Pi wants.

27
 As an example of how the deadlock detection algorithm
works, consider following Fig. Here we have three
processes and four resource classes, which we have
arbitrarily labeled tape drives, plotters, scanner, and
CD-ROM drive. Process 1 has one scanner. Process 2
has two tape drives and a CD-ROM drive. Process 3 has
a plotter and two scanners. Each process needs
additional resources, as shown by the R matrix.

28
 To run the deadlock detection algorithm, we look
for a process whose resource request can be
satisfied. The first one cannot be satisfied because
there is no CD-ROM drive available. The second
cannot be satisfied either, because there is no
scanner free. Fortunately, the third one can be
satisfied, so process 3 runs and eventually returns
all its resources, giving A = (2 2 2 0)
 At this point process 2 can run and return its
resources, giving A = (4 2 2 1)
 Now the remaining process can run. There is no
deadlock in the system.
 Suppose that process 2 needs a CD-ROM drive as
well as the two tape drives and the plotter. None of
the requests can be satisfied, so the entire system
is deadlocked. 29
The deadlock detection algorithm can now be given,
as follows.
1. Look for an unmarked process, Pi, for which the i-
th row of R is less than or equal to A.
2. If such a process is found, add the i-th row of C to
A, mark the process, and go back to step 1.
3. If no such process exists, the algorithm
terminates.
When the algorithm finishes, all the unmarked
processes, if any, are deadlocked.

30
RECOVERY FROM DEADLOCK
 Suppose that our deadlock detection algorithm has
succeeded and detected a deadlock. What is next?

1. RECOVERY THROUGH PREEMPTION

 In some cases it may be possible to temporarily take a
resource away from its current owner and give it to
another process.
 For example, to take a laser printer away from its
owner, the operator can collect all the sheets already
printed and put them in a pile. Then the process can
be suspended . At this point the printer can be
assigned to another process. When that process
finishes, the pile of printed sheets can be put back in
the printer’s output tray and the original process 31
restarted. Recovering this way is so difficult.
2. RECOVERY THROUGH ROLLBACK
 If the system designers and machine operators
know that deadlocks are likely, they can arrange
to have processes checkpointed periodically.
Checkpointing a process means that its state is
written to a file so that it can be restarted later.
 When a deadlock is detected, it is easy to see
which resources are needed. To do the recovery, a
process that owns a needed resource is rolled
back to its earlier checkpoints. All the work done
since the checkpoint is lost. In effect, the process
is reset to an earlier moment when it did not
have the resource, which is now assigned to one
of the deadlocked processes. 32
3.RECOVERY THROUGH KILLING
PROCESSES
 The crudest, but simplest way to break a
deadlock is to kill one or more processes. One
possibility is to kill a process in the cycle. With a
little luck, the other processes will be able to
continue. If this does not help, it can be repeated
until the cycle is broken.
 It is best to kill a process that can be rerun from
the beginning with no ill effects.

33
3.DEADLOCK AVOIDANCE
 In the discussion of deadlock detection, we
assumed that when a process asks for resources,
it asks for them all at once. In most systems,
however, resources are requested one at a time.
The system must be able to decide whether
granting a resource is safe or not and only make
the allocation when it is safe. Thus the question
arises: Is there an algorithm that can always
avoid deadlock by making the right choice all the
time? The answer is a qualified yes—we can
avoid deadlocks, but only if certain information is
available in advance. 34
SAFE AND UNSAFE STATES
 A state is said to be safe if it is not deadlocked and
there is some scheduling order in which every process
can run to completion even if all of them suddenly
request their maximum number of resources
immediately. It is easiest to illustrate this concept by an
example using one resource. In Fig., we have a state in
which A has 3 instances of the resource but may need
as many as 9 eventually. B currently has 2 and may
need 4 altogether, later. Similarly, C also has 2 but may
need an additional 5. A total of 10 instances of the
resource exist, so with 7 resources already allocated,
there are 3 still free.

35
 The state of Fig. (a) is safe because there exists a
sequence of allocations that allows all processes to
complete. Namely, the scheduler could simply run B
exclusively, until it asked for and got two more
instances of the resource, leading to the state of Fig.
(b). When B completes, we get the state of Fig. (c).
Then the scheduler can run C leading eventually to
Fig. (d). When C completes, we get Fig. (e). Now A
can get the six instances of the resource it needs and
also completes. Thus the state of Fig. (a) is safe
because the system, by careful scheduling, can avoid
deadlock. 36
 Now suppose we have the initial state shown in Fig. (a),
but this time A requests and gets another resource,
giving Fig. (b). Can we find a sequence that is
guaranteed to work? Let us try. The scheduler could run
B until it asked for all its resources, as shown in Fig. (c).
Eventually, B completes and we get the situation of
Fig.(d). At this point we are stuck.
 It is possible that A might release a resource before
asking for any more, allowing C to complete and
avoiding deadlock altogether. Thus the difference
between a safe state and an unsafe state is that from a
safe state the system can guarantee that all processes
will finish; from an unsafe state, no such guarantee can 37
be given.
1.THE BANKER’S ALGORITHM FOR A
SINGLE RESOURCE
 It is modeled on the way a small-town banker might deal with a
group of customers to whom he has granted lines of credit. What the
algorithm does is check to see if granting the request leads to an
unsafe state. If it does, the request is denied. If granting the request
leads to a safe state, it is carried out. In Fig. (a) we see four
customers. A, B, C and D, each of whom has been granted a certain
number of credit units . The banker knows that not all customers will
need their maximum credit immediately, so he has reserved only 10
units rather than 22 to service them. (In this analogy, customers are
processes, units are, say, tape drives, and the banker is the operating
system.)

38
2.THE BANKER’S ALGORITHM FOR
MULTIPLE RESOURCES
 The banker’s algorithm can be generalized to
handle multiple resources. Figure shows how it
works.

39
4.DEADLOCK PREVENTION
Go back to the four conditions:
 Mutual Exclusion Condition

 Hold and Wait Condition

 No Preemption Condition

 Circular Wait Condition

If we can ensure that at least one of these

conditions is never satisfied, then deadlocks will be
structurally impossible.

40
1. ATTACKING THE MUTUAL EXCLUSION
CONDITION
 If no resource were ever assigned exclusively to a
single process, we would never have deadlocks.
However, it is equally clear that allowing two
processes to write on the printer at the same time
will lead to chaos. By spooling printer output,
several processes can generate output at the
same time. In this model, the only process that
actually requests the physical printer is the
printer daemon. Since the daemon never requests
any other resources, we can eliminate deadlock
for the printer.
 Unfortunately, not all resources can be spooled
(the process table does not lend itself well to 41
being spooled).
2. ATTACKING THE HOLD AND WAIT
CONDITION
 If we can prevent processes that hold resources from
waiting for more resources, we can eliminate
deadlocks. One way to achieve this goal is to require
all processes to request all their resources before
starting execution. If everything is available, the
process will be allocated whatever it needs and can
run to completion. If one or more resources are busy,
nothing will be allocated and the process would just
wait.
 We have some problem in this model. As an example,
a process that reads data from an input tape,
analyzes it for an hour, and then writes an output
tape as well as plotting the results. If all resources
must be requested in advance, the process will tie up
42
the output tape drive and the plotter for an hour.
3. ATTACKING THE NO PREEMPTION
CONDITION

 If a process has been assigned the printer and is

in the middle of printing its output, forcibly
taking away the printer is tricky at best and
impossible at worst.

43
4. ATTACKING THE CIRCULAR WAIT
CONDITION
 The circular wait can be eliminated in several ways. One way
is simply to have a rule saying that a process is entitled only
to a single resource at any moment. If it needs a second one,
it must release the first one. For a process that needs to copy
a huge file from a tape to a printer, this restriction is
unacceptable.
 Another way to avoid the circular wait is to provide a global
numbering of all the resources, as shown in Fig. (a). Now the
rule is this: processes can request resources whenever they
want to, but all requests must be made in numerical order. A
process may request first a printer and then a tape drive, but
it may not request first a plotter and then a printer.

44
ANY QUESTION?

45