Deadlock Management

B. Ramamurthy

Page 1 11/28/23
Topics
• Resource
• Introduction to deadlocks
• The ostrich algorithm
• Deadlock detection and recovery
• Deadlock avoidance
– Banker’s algorithm
• Deadlock prevention
• Other issues

Page 2 11/28/23
Introduction
• Parallel operation among many devices driven by
concurrent processes contribute significantly to high
performance. But concurrency also results in
contention for resources and possibility of deadlock
among the vying processes.
• Deadlock is a situation where a group of processes
are permanently blocked waiting for the resources
held by each other in the group.
• Typical application where deadlock is a serious
problem: Operating system, data base accesses, and
distributed processing.

Page 3 11/28/23
System Model
• Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
• Each resource type Ri has Wi instances.
• Each process utilizes a resource as
follows:
– request
– use
– release

Page 4 11/28/23
 Deadlock Characterization
eadlock can arise if four conditions hold simultaneously.
• Mutual exclusion: only one process at a time can use a
resource.
• Hold and wait: a process holding at least one resource is
waiting to acquire additional resources held by other
processes.
• No preemption: a resource can be released only
voluntarily by the process holding it, after that process has
completed its task.
• Circular wait: there exists a set {P0, P1, …, P0} of waiting
processes such that P0 is waiting for a resource that is held
by P1, P1 is waiting for a resource that is held by
P2, …, Pn–1 is waiting for a resource that is held by
Pn, and P0 is waiting for a resource that is held by P0.

Page 5 11/28/23
 Resource-Allocation Graph
A set of vertices V and a set of edges E.

• V is partitioned into two types:

– P = {P1, P2, …, Pn}, the set consisting of all the
processes in the system.

– R = {R1, R2, …, Rm}, the set consisting of all

resource types in the system.
• request edge – directed edge P1  Rj
• assignment edge – directed edge Rj  Pi

Page 6 11/28/23
Resource-Allocation Graph
(Cont.)
• Process

• Resource Type with 4 instances

• Pi requests instance of Rj
Pi
Rj

Pi
• Pi is holding an instance of Rj
Rj

Page 7 11/28/23
Resource Allocation Graph with a
Deadlock

Page 8 11/28/23
Resource Allocation Graph with a cycle but
No Deadlock

Page 9 11/28/23
Deadlock Modeling
A B C

Page 10 How deadlock occurs 11/28/23

Methods for Handling
Deadlocks
• Ensure that the system will never enter a
deadlock state. (pessimistic)
• Allow the system to enter a deadlock state
and then recover. Database systems;
• Ignore the problem and pretend that
deadlocks never occur in the system; Older
operating systems; (ostrich algorithm:
optimistic)

Page 11 11/28/23
Dealing with Deadlock
Strategies for dealing with Deadlocks
1. just ignore the problem altogether
2. detection and recovery
3. dynamic avoidance
• careful resource allocation
4. prevention
• negating one of the four necessary
conditions

Page 12 11/28/23
The Ostrich Algorithm
• Pretend there is no problem
• Reasonable if
– deadlocks occur very rarely
– cost of prevention is high
• UNIX and Windows takes this approach
• It is a trade off between
– convenience
– correctness

Page 13 11/28/23
Detection with One Resource of Each Type
(1)

• Note the resource ownership and requests

• A cycle can be found within the graph, denoting
deadlock
Page 14 11/28/23
Recovery from Deadlock (1)

• Recovery through preemption

– take a resource from some other process
– depends on nature of the resource
• Recovery through rollback
– checkpoint a process periodically
– use this saved state
– restart the process if it is found deadlocked

Page 15 11/28/23
 Recovery from Deadlock (2)

• Recovery through killing processes

– crudest but simplest way to break a deadlock
– kill one of the processes in the deadlock cycle
– the other processes get its resources
– choose process that can be rerun from the
beginning

Page 16 11/28/23
 Deadlock Avoidance
Requires that the system has some additional a priori information
available.
• Simplest and most useful model requires that each
process declare the maximum number of resources
of each type that it may need.

• The deadlock-avoidance algorithm dynamically

examines the resource-allocation state to ensure
that there can never be a circular-wait condition.

• Resource-allocation state is defined by the number

of available and allocated resources, and the
maximum demands of the processes.
Page 17 11/28/23
Safe State
• When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe state.

• System is in safe state if there exists a safe sequence of all

processes.

• Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that
Pi can still request can be satisfied by currently available
resources + resources held by all the Pj, with j<I.
– If Pi resource needs are not immediately available, then Pi can
wait until all Pj have finished.
– When Pj is finished, Pi can obtain needed resources, execute,
return allocated resources, and terminate.
– When Pi terminates, Pi+1 can obtain its needed resources, and
so on.

Page 18 11/28/23
Safe, Unsafe , Deadlock State

Page 19 11/28/23
Resource-Allocation Graph
Algorithm
• Claim edge Pi  Rj indicated that process Pj may
request resource Rj; represented by a dashed line.

• Claim edge converts to request edge when a process

requests a resource.

• When a resource is released by a process,

assignment edge reconverts to a claim edge.

• Resources must be claimed a priori in the system.

Page 20 11/28/23
Banker’s Algorithm
• Multiple instances.

• Each process must a priori claim maximum

use.

• When a process requests a resource it may

have to wait.

• When a process gets all its resources it must

return them in a finite amount of time.
Page 21 11/28/23
 Data Structures for the Banker’s
Algorithm
Let n = number of processes, and m = number of resources types.

• Available: Vector of length m. If available [j] = k, there

are k instances of resource type Rj available.
• Max: n x m matrix. If Max [i,j] = k, then process Pi may
request at most k instances of resource type Rj.
• Allocation: n x m matrix. If Allocation[i,j] = k then Pi is
currently allocated k instances of Rj.
• Need: n x m matrix. If Need[i,j] = k, then Pi may need k
more instances of Rj to complete its task.

Need [i,j] = Max[i,j] – Allocation [i,j].

Page 22 11/28/23
Safety Algorithm
1. Let Work and Finish be vectors of length m and n,
respectively. Initialize:
Work = Available
Finish [i] = false for i - 1,3, …, n.
2. Find and 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.

Page 23 11/28/23
Resource-Request Algorithm for
Process Pi
Request = 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

Page 24 11/28/23
Example of Banker’s Algorithm
• 5 processes P0 through P4; 3 resource types A
(10 instances),
B (5instances, and C (7 instances).
• Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433

Page 25 11/28/23
Example (Cont.)
• The content of the matrix. Need is defined to be Max –
Allocation.
Need
ABC
P0 743
P1 122
P2 600
P3 011
P4 431
• The system is in a safe state since the sequence < P1, P3,
P4, P2, P0> satisfies safety criteria.

Page 26 11/28/23
Example P1 Request (1,0,2) (Cont.)
• Check that Request  Available (that is, (1,0,2)  (3,3,2)  true.
Allocation Need Available
ABC ABC ABC
P0 010 743 230
P1 302 020
P2 301 600
P3 211 011
P4 002 431
• Executing safety algorithm shows that sequence < P1, P3, P4, P0,
P2> satisfies safety requirement.
• Can request for (3,3,0) by P4 be granted?
• Can request for (0,2,0) by P0 be granted?

Page 27 11/28/23
 Deadlock Prevention
Restrain the ways request can be made.
• Mutual Exclusion – not required for sharable
resources; must hold for nonsharable resources.

• Hold and Wait – must guarantee that whenever a

process requests a resource, it does not hold any
other resources.
– Require process to request and be allocated all
its resources before it begins execution, or allow
process to request resources only when the
process has none.
– Low resource utilization; starvation possible.

Page 28 11/28/23
Deadlock Prevention (Cont.)
• No Preemption –
– If a process that is holding some resources requests
another resource that cannot be immediately allocated to
it, then all resources currently being held are released.
– Preempted resources are added to the list of resources for
which the process is waiting.
– Process will be restarted only when it can regain its old
resources, as well as the new ones that it is requesting.

• Circular Wait – impose a total ordering of all resource

types, and require that each process requests resources in an
increasing order of enumeration.

Page 29 11/28/23
Deadlock Prevention
Attacking the Mutual Exclusion Condition
• Some devices (such as printer) can be
spooled
– only the printer daemon uses printer resource
– thus deadlock for printer eliminated
• Not all devices can be spooled
• Principle:
– avoid assigning resource when not absolutely
necessary
– as few processes as possible actually claim
the resource
Page 30 11/28/23
 Attacking the Hold and Wait
Condition
• Require processes to request resources before starting
– a process never has to wait for what it needs

• Problems
– may not know required resources at start of run
– also ties up resources other processes could be using

• Variation:
– process must give up all resources
– then request all immediately needed

Page 31 11/28/23
 Attacking the No Preemption Condition

• This is not a viable option

• Consider a process given the printer
– halfway through its job
– now forcibly take away printer
– !!??

Page 32 11/28/23
Attacking the Circular Wait Condition (1)

(a) (b)

• Normally ordered resources

• A resource graph

Page 33 11/28/23
Attacking the Circular Wait Condition (1)

Summary of approaches to deadlock prevention

Page 34 11/28/23
Other Issues
Two-Phase Locking
• Phase One
– process tries to lock all records it needs, one at a
time
– if needed record found locked, start over
– (no real work done in phase one)
• If phase one succeeds, it starts second phase,
– performing updates
– releasing locks
• Note similarity to requesting all resources at once
• Algorithm works where programmer can arrange
– program can be stopped, restarted

Page 35 11/28/23
Nonresource Deadlocks
• Possible for two processes to
deadlock
– each is waiting for the other to do some
task
• Can happen with semaphores
– each process required to do a down() on
two semaphores (mutex and another)
– if done in wrong order, deadlock results

Page 36 11/28/23
 Starvation
• Algorithm to allocate a resource
– may be to give to shortest job first
• Works great for multiple short jobs in a
system
• May cause long job to be postponed
indefinitely
– even though not blocked
• Solution:
– First-come, first-serve policy

Page 37 11/28/23