Operating System
Concepts
Lecture No. 11
Dead Lock
Handling
Agenda of Today’s
Lecture
Thedeadlock problem
Deadlock characterization
Deadlock handling
Deadlock prevention
Deadlock avoidance
Deadlock detection and Recovery
Deadlock is a situation where a set of
processes are blocked because each
process is holding a resource and waiting
for another resource acquired by some
other process.
The Deadlock Problem
A set of blocked
processes each holding a
resource and waiting to
acquire a resource held
by another process in the
set.
The Deadlock Problem
Example
System has 2 tape drives.
P1 and P2 each hold one
tape drive and each
needs another one.
The Deadlock Problem
Example: semaphores A
and B, initialized to 1
P0 P1
wait (A); wait(B);
wait (B); wait(A);
The Deadlock Problem
signal(A);
P0 P1
signal(B);
Bridge Crossing
Example
Traffic only in one direction.
Each section of a bridge can
be viewed as a resource.
Bridge Crossing
Example
If a deadlock occurs, it can be
resolved if one car backs up
(preempt resources and
rollback).
Several cars may have to be
backed up if a deadlock
occurs.
Starvation is possible.
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
Deadlock
Characterization
Deadlock can arise if four
conditions hold
simultaneously.
Mutual exclusion: only
one process at a time can
use a resource.
Deadlock
Characterization
Hold and wait: a
process holding at least
one resource is waiting to
acquire additional
resources held by other
processes.
Deadlock
Characterization
No preemption: a
resource can be released
only voluntarily by the
process holding it, after
that process has
completed its task.
Deadlock
Characterization
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 Pn is waiting for a resource
that is held by P0.
P0 → P1 → P2 → … → Pn → P0
Resource Allocation
Graph
A set of vertices V and a set of edges
E.
V is partitioned into two types:
P = {P1, P2, …, Pn}
R = {R1, R2, …, Rm}
E = {Request Edges, Assignment Edges}
Request Edge: P1 Rj
Assignment Edge: Rj Pi
Resource Allocation
Graph
Process
Resource Type with 4 instances
Pi
Pi requests instance of Rj
Pi
Pi is holding an instance of Rj
Example Graph
Graph with a Deadlock
Graph with a Cycle but
No Deadlock
Basic Facts
If graph contains no cycles no
deadlock.
If graph contains a cycle
if only one instance per
resource type, then deadlock.
if several instances per resource
type, possibility of deadlock.
Deadlock Handling
Ensure that the system will
never enter a deadlock
state.
Allow the system to enter a
deadlock state and then
recover.
Ignore the problem and
pretend that deadlocks
never occur in the system.
Deadlock Handling
Deadlock prevention
Deadlock avoidance
Deadlockdetection
and recovery
Deadlock Prevention
Restrain the ways
resource allocation
requests can be made
to insure that at least
one of the four
necessary conditions is
violated.
Deadlock Prevention
Mutual Exclusion
Cannot be prevented for
all resources. Some
resources are inherently
non-sharable because
their states cannot be
saved and restored
without ill effects, such as
a printer.
Deadlock Prevention
Hold and Wait – we
must guarantee that
whenever a process
requests a resource, it
does not hold any other
resources.
Deadlock Prevention
Require a process to
request and be allocated
all its resources before it
begins execution, or allow
a process to request
resources only when the
process has none.
Low resource utilization;
starvation possible.
Deadlock Prevention
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.
Deadlock Prevention
Preempted resources are
added to the list of
resources for which the
process is waiting for.
Process will be restarted
only when it can regain its
old resources as well as
the new ones that it has
requested.
Deadlock Prevention
Circular Wait – impose a
total ordering of all
resource types, and require
that each process requests
resources in an increasing
order of enumeration.
Dead Lock Avoidance
Requires that the system has
additional a priori information
available about the use of
resources by processes.
Simplest and most useful
model requires that each
process declare the maximum
number of resources of each
type that it may need.
Dead Lock Avoidance
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.
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 a safe state if
there exists a safe sequence
of all processes.
Safe State
If Pi resource needs are not
immediately available, then Pi can
wait until all Pj have finished.
When Pj are 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.
Some Basic Facts
If a system is in safe state no
deadlocks.
If a system is in unsafe state
possibility of deadlock due to
the behavior of processes.
Avoidance ensure that a
system never enters an unsafe
state.
Safe, Unsafe, and
Deadlock States
Dead Lock avoidance
Firstwe see the dead lock avoidance
in single instance of resource type
and then multiple instance of the
resource type.
Multiple instance resource type
dead lock avoidance
Use Banker’s Algorithm
Banker’s Algorithm
Multiple instances of resources.
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.
Data Structures for the
Banker’s Algorithm
n = number of processes
m = number of resource types
Available: Vector of length m.
If available[j] = k, there are k
instances of resource type Rj
available.
Data Structures for the
Banker’s Algorithm
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.
Data Structures for the
Banker’s Algorithm
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]
Banker’s Algorithm cont..
Resource-Request for Pi
Requesti = request vector for Pi.
If Requesti [j] = k then process Pi
wants k instances of resource type Rj.
1. If Requesti Needi go to step 2.
Otherwise, report error 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 – Requestj;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
Here the safety algorithm will call by the
banker’s algorithm. If the system state is safe,
resources will be allocated otherwise not and
restored previous state.
If safe the resources are allocated to Pi.
If unsafe Pi must wait, and the old resource-
allocation state is restored
Example System
Five processes: P0 … P4
Three resource types:
A (10 instances)
B (5 instances)
C (7 instances)
Example System
System state: Is it safe?
Process
P0
P1
P2
P3
P4
Example System
System state: Is it safe?
Max Allocation Available
Process A B C A B C A B C
P0 7 5 3 0 1 0 3 3 2
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 3 0 0 2
Example System
Needi = Maxi – Allocationi
Need matrix
Process A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Example System
Need Allocation Work
Process A B C A B C A B C
P0 7 4 3 0 1 0 3 3 2
P1 1 2 2 2 0 0
P2 6 0 0 3 0 2
P3 0 1 1 2 1 1
P4 4 3 1 0 0 2
Safe Sequence: <>
Example System
Need Allocation Work
Proces A B C A B C A B C
s
7 4 3 0 1 0 3 3 2
P0
1 2 2 2 0 0 5 3 2
P1
6 0 0 3 0 2
P2
0 1 1 2 1 1
P3
4 3 1 0 0 2
P4
Safe Sequence: < P1>
Example System
Need Allocation Work
Proces A B C A B C A B C
s
7 4 3 0 1 0 3 3 2
P0
1 2 2 2 0 0 5 3 2
P1
6 0 0 3 0 2 7 4 3
P2
0 1 1 2 1 1
P3
4 3 1 0 0 2
P4
Safe Sequence: < P1, P3>
Example System
Need Allocation Work
Proces A B C A B C A B C
s
7 4 3 0 1 0 3 3 2
P0
1 2 2 2 0 0 5 3 2
P1
6 0 0 3 0 2 7 4 3
P2
0 1 1 2 1 1 7 4 5
P3
4 3 1 0 0 2
P4
Safe Sequence: < P1, P3, P4 >
Example System
Need Allocation Work
Process A B C A B C A B C
P0 7 4 3 0 1 0 3 3 2
P1 1 2 2 2 0 0 5 3 2
P2 6 0 0 3 0 2 7 4 3
P3 0 1 1 2 1 1 7 4 5
P4 4 3 1 0 0 2 7 5 5
Safe Sequence: <P1, P3, P4, P0>
Example System
Final safe sequence:
<P1, P3, P4, P0, P2>
Not a unique sequence
Possible safe sequences for the this
example:
<P1,P3,P4,P0,P2>, <P1,P3,P4,P2,P0>,
<P1,P3,P2,P0,P4>, <P1,P3,P2,P4,P0>,
<P1,P3,P0,P2,P4>, <P1,P3,P0,P4,P2>
More Examples
Can request for (0,2,0) by P0 be
granted?
1. Is Request0 Need0?
(0,2,0) (7,4,3) true
2. Is Request1 Available?
(0,2,0) (3,3,2) true
Example
Need Allocation Available
Proces A B C A B C A B C
s
7 4 3 0 1 0 3 3 2
P0
1 2 2 2 0 0
P1
6 0 0 3 0 2
P2
0 1 1 2 1 1
P3
4 3 1 0 0 2
P4
Example
Need Allocation Work
Process A B C A B C A B C
P0 7 2 3 0 3 0 3 1 2
P1 1 2 2 2 0 0
P2 6 0 0 3 0 2
P3 0 1 1 2 1 1
P4 4 3 1 0 0 2
Safe Sequence: <?> and Tell whether P0 request
granted immediately or not?
More Examples
Can request for (3,3,0) by P4
be granted?
Do it yourself!
Deadlock Detection
Allow system to enter deadlock
state
Detection algorithm
Recovery scheme
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 2 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Finish Sequence: <>
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2 0 1 0
P2 3 0 2 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Finish Sequence: <P0>
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2 0 1 0
P2 3 0 2 0 0 0 3 1 2
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Finish Sequence: <P0, P2>
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2 0 1 0
P2 3 0 2 0 0 0 3 1 2
P3 2 1 1 1 0 0 5 2 3
P4 0 0 2 0 0 2
Finish Sequence: < P0, P2, P3>
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2 0 1 0
P2 3 0 2 0 0 0 3 1 2
P3 2 1 1 1 0 0 5 2 3
P4 0 0 2 0 0 2 5 2 5
Finish Sequence: < P0, P2, P3, P4 >
Example System State
Final finish sequence:
< P 0, P 2, P 3, P 4 , P 1 >
Other possible finish sequences:
< P 0, P 2, P 3, P 1 , P 4 >
< P 0, P 2, P 4, P 1 , P 3 >
< P 0, P 2, P 4, P 3 , P 1 >
…
Example System State
P requests an additional
2
instance of C. Process Request
Do we have a
A B C
finish sequence? P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 0 0 2
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 2 0 0 1
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Finish Sequence: <>
Example System State
Allocation Request Work
Process A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2 0 1 0
P2 3 0 2 0 0 1
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
Finish Sequence: <P0>
Example System State
P0’s request can be satisfied with
currently available resources, but
request for no other process can
be satisfied after that.
Deadlock exists, consisting of
processes P1, P2, P3, and
P4.
Recovery from Deadlock:
Process Termination
Abort all deadlocked
processes.
Abort one process at a time
until the deadlock cycle is
eliminated.