Deadlocks

Chapter 5
Deadlocks

5.1 Definition
In a multiprogramming system, processes request resources. If those resources are being
used by other processes then the process enters a waiting state. However, if other
processes are also in a waiting state, we have deadlock.

The formal definition of deadlock is as follows:

Definition: A set of processes is in a deadlock state if every process in the set is waiting
for an event (release) that can only because of by some other process in the same set.

Example 5.1

Process-1 requests the printer, gets it

Process-2 requests the tape unit,getsit Process-1and
Process-1 requests the tapeunit,waits Process-2 are
Process-2 requests theprinter,waits deadlocked!

In this chapter, we shall analyze deadlocks with the following assumptions:

 A process must request a resource before using it. It must release the resource
after using it.
• Request
• Use
• release

 A process cannot request a number more than the total number of resources available
in the system.

For the resources of the system, a resource table shall be kept, which shows whether each
process is free or if occupied, by which process it is occupied. For every resource, queues
shall be kept, indicating the names of processes waiting for that resource.

A deadlock occurs if and only if the following four conditions hold in a system
simultaneously:

1. Mutual Exclusion: At least one of the resources is non-sharable (that is; only a
limited number of processes can use it at a time and if it is requested by a process
while it is being used by another one, the requesting process has to wait until the
resource is released.).

1
 Deadlocks

2. Hold and Wait: There must be at least one process that is holding at least one
resourceandwaitingforotherresourcesthatarebeingholdbyotherprocesses.

3. No Preemption: No resource can be preempted before the holding process

completes its task with thatresource.

4. Circular Wait: There exists a set of processes: {P 1,P2,...,Pn} such that

P1 is waiting for a resource held byP2

P2 is waiting for a resource held by P3
...
Pn-1 is waiting for a resource held by
PnPn is waiting for a resource held by
P1

Methods for handling deadlocks are:

 Deadlockprevention
 Deadlockavoidance
 Deadlock detection and recovery.

5.2 Resource Allocation Graphs

Resource allocation graphs are drawn in order to see the allocation relations of processes
and resources easily. In these graphs, processes are represented by circles and resources
are represented by boxes. Resource boxes have some number of dots inside indicating
available number of that resource, that is number of instances.
pi ●

Process pi is waiting for ●resourceProcessp

rj iiswaitingforresourcerj

pi ●

Process pi has alocated● resource rj

Processp ihasallocatedresourcer j

 If the resource allocation graph contains no cycles then there is no deadlock in the
system at thatinstance.

 Iftheresourceallocationgraphcontainsacyclethenadeadlockmayexist.

 If there is a cycle, and the cycle involves only resources which have a single
instance, then a deadlock hasoccurred.

2
 Deadlocks

Example 5.2

● r1 r3

p2

p1
p3
r2
●

There are three cycles, so a deadlock may exists. Actually p1, p2 and p3 are deadlocked

Example 5.3

p1

r1 r2
● ●

p2
p4
p3

There is a cycle, however there is no deadlock. If p4 releases r2, r2 may be allocated to

p3, which breaks the cycle.

5.3 DeadlockPrevention
To prevent the system from deadlocks, one of the four discussed conditions that may
create a deadlock should be discarded. The methods for those conditions are as follows:

Mutual Exclusion:

In general, we do not have systems with all resources being sharable. Some resources like
printers, processing units are non-sharable. So it is not possible to prevent deadlocks by
denying mutual exclusion.

Hold and Wait:

One protocol to ensure that hold-and-wait condition never occurs says each process must
request and get all of its resources before it begins execution.

Another protocol is “Each process can request resources only when it does not occupy any
resources.”

3
 Deadlocks

The second protocol is better. However, both protocols cause low resource utilization and
starvation. Many resources are allocated but most of them are unused for a long period of
time. A process that requests several commonly used resources causes many others to
wait indefinitely.

No Preemption:

One protocol is “If a process that is holding some resources requests another resource and
that resource cannot be allocated to it, then it must release all resources that are currently
allocated to it.”

Another protocol is “When a process requests some resources, if they are available,
allocate them. If a resource it requested is not available, then we check whether it is being
used or it is allocated to some other process waiting for other resources. If that resource is
not being used, then the OS preempts it from the waiting process and allocate it to the
requesting process. If that resource is used, the requesting process must wait.” This
protocol can be applied to resources whose states can easily be saved and restored
(registers, memory space). It cannot be applied to resources likeprinters.

Circular Wait:

One protocol to ensure that the circular wait condition never holds is “Impose a linear
ordering of all resource types.” Then, each process can only request resources in an
increasing order of priority.

For example, set priorities for r1 = 1, r2 = 2, r3 = 3, and r4 = 4. With these priorities, if

process P wants to use r1 and r3, it should first request r1, then r3.

Another protocol is “Whenever a process requests a resource r j, it must have released all
resources rk with priority(rk) ≥ priority (rj).

5.4 Deadlock avoidance

Given some additional information on how each process will request resources, it is
possible to construct an algorithm that will avoid deadlock states. The algorithm will
dynamically examine the resource allocation operations to ensure that there won't be a
circular wait on resources.

When a process requests a resource that is already available, the system must decide
whether that resource can immediately be allocated or not. The resource is immediately
allocated only if it leaves the system in a safe state.

A state is safe if the system can allocate resources to each process in some order avoiding
a deadlock. A deadlock state is an unsafe state.

It is possible to go from a safe state to an unsafe state:

Banker's Algorithm (Dijkstra and Habermann)

It is a deadlock avoidance algorithm. The following data structures are used in the

algorithm: m = number ofresources

n = number ofprocesses

4
 Deadlocks

Available[m] : One dimensional array of size m. It indicates the number of available

resources of each type. For example, if Available [i] is k, there are k instances of resource r i.

Max [n,m] : Two dimensional array of size n*m. It defines the maximum demand of each
process from each resource type. For example, if Max [i,j] is k, process p i may request at
most k instances of resource type rj.

Allocation [n,m] : Two dimensional array of size n*m. It defines the number of resources of
each type currently allocated to each process.

Need [n,m] : Two dimensional array of size n*m. It indicates the remaining need of each
process, of each resource type. If Need [i,j] is k, process pi may need k more instances of
resource type rj. Note that Need [i,j] = Max [i,j] - Allocation [i,j].

Request[n,m]:Two dimensional array of size n*m. It indicates the pending requests of each
process, of each resourcetype.

Now, take each row vector in Allocation and Need as Allocation(i) and Need(i).
(Allocation(i) specifies the resources currently allocated to process p i.)
Define the relation between two vectors X and Y , of equal size = n as :

XY X [ i ]Y [ i ] , i = 1,2, ...,n

X!Y X [ i ] > Y [ i ] for some i

The algorithm is as follows:

1. Process pi makes requests for resources. Let Request(i) be the corresponding

request vector. So, if pi wants k instances of resource type rj, then Request(i)[j]=k.

2. If Request(i) !Need(i), there is an error.

3. Otherwise, if Request(i) !Available, then pi must wait.

4. Otherwise, modify data structures as follows:

Available = Available -Request(i)

Allocation(i) = Allocation(i) + Request(i)
Need(i) = Need(i) - Request(i)

5. Check whether the resulting state is safe. (Use the safety algorithm presented below.)

6. If the state is safe, do the allocation. Otherwise, p i must wait for Request(i).

Safety Algorithm to perform Step 5:

Let Work and Finish be vectors of length m and n, respectively.

1. Initialize Work = Available, Finish [j] = false, for allj.

2. Find an i such that Finish[i] = false and Need(i)Work If

no such i is found, go to step4.

3. If an i is found, then for that i, do:

5
 Deadlocks

Work = Work + Allocation(i)

Finish [i] = true

Go to step 2.

4. If Finish [j] = true for all j, then the system is in a safe state.

Banker's algorithm is O(m (n2)).

6
 Deadlocks

Example 5.6: (Banker's algorithm)

Given

Now, apply the safety algorithm:

Work = [ 0 2 1 ]

i=1:

Need(1) = [ 0 1 1 ] Work ? Yes.

Work = Work + Allocation(1) = [ 1 4 1]
Finish (1) = true

i=2:

Need(2) = [ 1 4 1 ] Work ? Yes.

Work = Work + Allocation(2) = [ 1 4 1 ]
Finish (2)=true

7
 Deadlocks

System is in a safe state, so do the allocation. If the algorithm is repeated for Request(2),
the system will end up in an unsafe state.

5.5 Deadlock Detection

If a system has no deadlock prevention and no deadlock avoidance scheme, then it needs
a deadlock detection scheme with recovery from deadlock capability. For this, information
should be kept on the allocation of resources to processes, and on outstanding allocation
requests. Then, an algorithm is needed which will determine whether the system has
entered a deadlock state. This algorithm must be invoked periodically.

Recovery From Deadlock

If the system is in a deadlock state, some methods for recovering it from the deadlock state
must be applied. There are various ways for recovery:

 Allocate one resource to several processes, by violating mutual exclusion.

 Preempt some resources from some of the deadlocked processes.
 Abort one or more processes in order to break the deadlock.

If preemption is used:

1. Select a victim. (Which resource(s) is/are to be preempted from which process?)

2. Rollback: If we preempt a resource from a process, roll the process back to some safe
state and make it continue.

To avoid starvation, ensure that a process can be picked as a victim for only a small
number of times. So, it is a wise idea to include the number of rollbacks as a parameter.