Chapter 3

Deadlocks

Z H Shah BVM 1
• Deadlock can occur when processes have been
granted exclusive access to devices, files etc., also
referred as resources.

• A resource can be a hardware device or a piece of

information.
• A resource is anything that can be used by only a
single process at any instance of time.

• Resources come in two types:

1. Preemptable resource : One that can be taken away
from the process owning it with no side/ill effects. For
ex. Memory
2. Nonpreemtable resource: It is the one that cannot be
taken away from its current owner without causing the
computation to fail. For ex. CD-ROM.
Z H Shah BVM 2
Sequence of events required to use a resource:
1. Request the resource.
2. Use the resource.
3. Release the resource.
• If the resource is not available when it is requested,
the requesting process is forced to wait. It normally sit
in a tight loop requesting the resource, sleep, try again
and so on.
• Assumption: When a process is denied a resource
request, it is put to sleep.
• The Nature of requesting a resource is system
dependent. (it may be in form of system call like
request or if resource is file, it may be open system
call)
Z H Shah BVM 3
 Resource Acquisition

• For some kind of resources, such as records in database

system, it is up to the user processes to manage
resource usage themselves.

• Semaphore or mutex can be used for user management

of resources.

• The 3 steps listed above can be implemented as a down

on semaphore to acquire the resource, using the
resource and finally up on the resource to release it.

Z H Shah BVM 4
Resource Acquisition (Contd......)

Figure 6-1. Using a semaphore to protect resources.

(a) One resource. (b) Two resources.

Z H Shah BVM 5
(a) Deadlock free code. (b) Code with a potential deadlock.
Z H Shah BVM 6
 Introduction to Deadlock
Deadlock can be defined formally as follows:
A set of processes is deadlocked if each process in the
set is waiting for an event that only another process in
the set can cause.

Assumption: The processes have only a single thread and

there are no interrupts possible to wake up a blocked
process.

• In other words, each member of the set of deadlocked

processes 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.
Z H Shah BVM 7
 Conditions for 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 which 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 deadlock is possible.

Z H Shah BVM 8
 Deadlock Modeling
• Holt showed how these four conditions can be modeled
using directed graphs.
• The graph have two kinds of nodes:
processes :shown as circles
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.

• An arc from a process to a resource means that the

process is currently blocked waiting for that resource.

Z H Shah BVM 9
 Deadlock Modeling (Contd…..)

Resource allocation graphs

(a) Holding a resource. (b) Requesting a resource. (c) Deadlock.
Z H Shah BVM 10
An example of how deadlock occurs and how it
can be avoided.

Z H Shah BVM 11
Example (Contd…..)

Z H Shah BVM 12
Example (Contd…..)

Z H Shah BVM 13
 Strategies for dealing with deadlocks:

1. Just ignore the problem.

2. Detection and recovery. Let deadlocks occur, detect

them, take action.

3. Dynamic avoidance by careful resource allocation.

4. Prevention, by structurally negating one of the four

required conditions.

Z H Shah BVM 14
 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.

Z H Shah BVM 15
• Consider a system with 7 process, A through G, and 6
resources, R through W. The state of which resources
are currently owned and which ones are currently
being requested is as follows:

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.

The question is: Is this system deadlocked, and if so,

which processes are involved?
Z H Shah BVM 16
 Deadlock Detection with
One Resource of Each Type

(a) A resource graph. (b) A cycle extracted from (a).

Z H Shah BVM 17
 Algorithm for detecting deadlock
Algorithm uses one data structure L, a list of nodes.
During the algorithm, arcs will be marked to indicate
that they have already been inspected, to prevent
repeated inspections.
Steps:
1. For each node, N in the graph, perform the following
five steps with N as the starting node.
2. Initialize L to the empty list, designate all arcs as
unmarked.
3. Add current node to end of L, check to see if node now
appears in L two times. If it does, graph contains a
cycle (listed in L), algorithm terminates.
Z H Shah BVM 18
 Algorithm for detecting deadlock (Contd….)
4. From given node, see if 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 to a dead end. Remove it and
go back to previous node, that is, the one that was
current just before this one, make that one current
node, and go to step 3. If this is initial node, graph does
not contain any cycles, algorithm terminates.

Z H Shah BVM 19
 Deadlock Detection with
Multiple Resources of Each Type
• A matrix base algorithm is used for detecting deadlock among n
processes, p1 through pn. Let the no. of resource classes be m, with
E1 resource of class 1, E2 resources of class 2 and so on.

• E: existing resource vector. (It gives the total number of instances of

each resource in existence.)

• A: available resource vector. (Ai gives the number of instances of

resource i that are currently available.)

• Array C: Current allocation matrix. (the i-th row of C tells how many
instances of each resource class Pi currently holds. Thus Cij is the
no. of instances of resource j that are held by process i.)

• Array R: Request matrix. (Rij is the no. of instances of resource j

that Pi wants.)
Z H Shah BVM 20
 Deadlock Detection with
Multiple Resources of Each Type
Figure 6-6. The four data structures needed
by the deadlock detection algorithm.

Z H Shah BVM 21
 Deadlock Detection with
Multiple Resources of Each Type
Deadlock detection algorithm:
Each process is initially said to be unmarked. As the
algorithm progresses, processes will be marked,
indicating that they are able to complete and are thus
not deadlocked. After completion, any unmarked
processes are known to be deadlocked.
Steps:
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.
Z H Shah BVM 22
Deadlock Detection with Multiple
Resources of Each Type

Z H Shah BVM 23
 Recovery from Deadlock

Following are the ways of recovering from deadlock:

• Recovery through preemption
• Recovery through rollback
• Recovery through killing processes

Z H Shah BVM 24
 Recovery through preemption

• Temporarily take a resource away from its current owner

and give it to another process.

• It is highly dependent on the nature of the resource.

• Recovering this way is frequently difficult or impossible.

Z H Shah BVM 25
 Recovery through rollback
• Arrangement can be done 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, to do the recovery, a process that

owns a needed resource is rolled back to a point.

• In a sense, 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.

• If the restarted process tries to acquire the resource again, it will

have to wait until it becomes available.

Z H Shah BVM 26
 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,

other processes will be able to continue. If this does not help, it can
be repeated until the cycle is broken.

• Alternatively, a process not in the cycle (holding a resource that

some process in cycle needs) can be chosen as the victim in order
to release its resources.

• Where possible, it is best to kill a process that can be rerun from the
beginning with no ill effects.

Z H Shah BVM 27
 Deadlock avoidance

• In deadlock detection, it has been assumed that when a

process asks from resources, it asks for them all at once.

• In most systems, 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 if it
safe.

• Deadlock can be avoided by careful resource allocation

but only if certain information is available in advance.

Z H Shah BVM 28
 Deadlock Avoidance
Resource Trajectories

Z H Shah BVM 29
 Safe and Unsafe States

• At any instant of time, there is a current state consisting

of E,A,C, and R.

• 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 no of resources immediately.

Z H Shah BVM 30
Safe and Unsafe States

Demonstration that the state in (a) is safe.

Z H Shah BVM 31
 Safe and Unsafe States

Demonstration that the state in (b) is not safe.

Z H Shah BVM 32
• It is worth noting that unsafe state is not a deadlocked
state.

• 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 be given.

Z H Shah BVM 33
The Banker’s Algorithm
for a Single Resource

Z H Shah BVM 34
The Banker’s Algorithm
for Multiple Resources

Z H Shah BVM 35
 The Banker’s Algorithm
for Multiple Resources
Algorithm for checking to see if a state is safe:
1. Look for row, R, whose unmet resource needs are ≤ A. If no such
row exists, system will eventually deadlock since no process can
run to completion.

2. Assume process of row chosen requests all resources it needs

and finishes. Mark process as terminated, add all its resources to
the A vector.

3. Repeat steps 1 and 2 until either all processes marked

terminated (initial state was safe) or no process left whose
resource needs can be met (there is a deadlock).

Z H Shah BVM 36
 Deadlock Prevention
• Deadlock avoidance is essentially impossible because it requires
information about future requests, which is not known, how do
real systems avoid deadlock?

• The answer is if we can ensure that at least one of these

following conditions is never satisfied, then deadlocks will be
structurally impossible.
• Attacking the mutual exclusion condition
• Attacking the hold and wait condition
• Attacking the no preemption condition
• Attacking the circular wait condition

Z H Shah BVM 37
 Attacking the mutual exclusion condition

• If no resource were ever assigned exclusively to a single process,

we would never have deadlocks.
• For ex., 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 the devices can be spooled. For ex., process
table.

• Frequently applicable idea is to avoid assigning a resource when

that is not absolutely necessary, and try to make sure that as few
processes as possible may actually claim the resource.

Z H Shah BVM 38
 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 otherwise
it has to wait.

• An immediate problem with this approach is that many processes do

not know their need until they start running. (If they know, banker’s
algorithm can be used.)

• Another problem is that resources will not be used optimally with

this approach.

• A slightly different way to break the hold and wait condition is to

require a process requesting a resource to first temporarily release
all the resources it currently holds. Then it tries to get everything it
needs all at once.
Z H Shah BVM 39
 Attacking the no preemption condition

• Attacking the third condition is less promising than attacking the

second one.

• If a process has been assigned the printer and is in the middle of

printing its output, forcibly taking away the printer because needed
plotter is not available is worst.

Z H Shah BVM 40
 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.

• Another way to avoid the circular wait is to provide a global

numbering of all the resources. The rule is: processes can request
resources whenever they want to, but all requests must be made in
numerical order.

Z H Shah BVM 41
 Two-Phase Locking
• For specific application like in database systems, an operation that
occurs frequently is requesting locks on several records and then
updating all the locked records.

• The approach often used is called Two-Phase Locking.

• In the first phase, the process tries to lock all the records it needs,
one at a time. If it succeeds, it begins the second phase, performing
all its updates and releasing the locks. No real work is done in the
first phase.

• If during the first phase, some needed record is already locked,

process just releases all its locks and starts the first phase all over.

• It is not applicable in general. It can work only in those situations

where program can be stopped at any point and restarted.

Z H Shah BVM 42
 Non resource Deadlocks

• Deadlock can occur in other situations, including those not involving

resources at all.

• For ex., it can happen that two processes deadlock each waiting for
the other one to do something. This often happens with
semaphores.

Z H Shah BVM 43
 Starvation

• In a dynamic system, requests for resources happen all the time.

Some policy is needed to make a decision about who gets which
resource when. This policy may lead to some processes never
getting service even though they are not deadlocked.

• Allocation should be in a manner, no one should starve to death.

• It can be avoided by first come first serve resource allocation policy.

Z H Shah BVM 44