DEADLOCKS
DEFINITION OF DEADLOCK
A set of two or more processes are deadlocked if
they are blocked (i.e., in the waiting state) each
holding a resource and waiting to acquire a
resource held by another process in the set.
Or
A process is deadlocked if it is waiting for an
event which is never going to happen.
Deadlocks can occur via system calls, locking, etc.
2
EXAMPLE OF DEADLOCK
Semaphores A and B, each initialized to 1:
P_0 P_1
---------- ----------
A.wait(); B.wait();
B.wait(); A.wait();
A.signal(); B.signal();
B.signal(); A.signal();
3
SYSTEM MODEL
System consists of resources
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
4
DEADLOCK CHARACTERIZATION
Deadlock 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, …, Pn} 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.
5
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 Pi → Rj
assignment edge – directed edge Rj → Pi
6
RESOURCE-ALLOCATION GRAPH
(CONT.)
Process
Resource Type with 4 instances
Pi requests instance of Rj
P
i
Rj
Pi is holding an instance of Rj
P
i
Rj 7
EXAMPLE OF A RESOURCE ALLOCATION GRAPH
8
RESOURCE ALLOCATION GRAPH WITH A
DEADLOCK
9
GRAPH WITH A CYCLE BUT NO DEADLOCK
10
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
11
METHODS FOR HANDLING
DEADLOCKS
Ensure that the system will never enter a
deadlock state:
⚫ Deadlock prevention
⚫ Deadlock avoidence
Allow the system to enter a deadlock state and
then recover
Ignore the problem and pretend that deadlocks
never occur in the system; used by most
operating systems, including UNIX
12
DEADLOCK PREVENTION
Restrain the ways request can be made
Mutual Exclusion – not required for
sharable resources (e.g., read-only files); must
hold for non-sharable 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 allocated to it.
⚫ Low resource utilization; starvation possible
13
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
14
enumeration
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 15
BASIC FACTS
If a system is in safe state ⇒ no deadlocks
If a system is in unsafe state ⇒ possibility
of deadlock
Avoidance ⇒ ensure that a system will
never enter an unsafe state.
16
SAFE, UNSAFE, DEADLOCK STATE
17
AVOIDANCE ALGORITHMS
Single instance of a resource type
⚫ Use a resource-allocation graph
Multiple instances of a resource type
⚫ Use the banker’s algorithm
18
RESOURCE-ALLOCATION GRAPH
19
UNSAFE STATE IN RESOURCE-ALLOCATION
GRAPH
20
RESOURCE-ALLOCATION GRAPH
ALGORITHM
Suppose that process Pi requests a resource Rj
The request can be granted only if converting
the request edge to an assignment edge does
not result in the formation of a cycle in the
resource allocation graph
21
DEADLOCK DETECTION
Allow system to enter deadlock state
Detection algorithm
Recovery scheme
22
RESOURCE-ALLOCATION GRAPH AND
WAIT-FOR GRAPH
Resource-Allocation Corresponding wait-for
Graph graph
23
DETECTION-ALGORITHM USAGE
When, and how often, to invoke depends on:
⚫ How often a deadlock is likely to occur?
⚫ How many processes will need to be rolled
back?
one for each disjoint cycle
If detection algorithm is invoked arbitrarily,
there may be many cycles in the resource graph
and so we would not be able to tell which of the
many deadlocked processes “caused” the
deadlock.
24
RECOVERY FROM DEADLOCK: PROCESS
TERMINATION
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
In which order should we choose to abort?
1. Priority of the process
2. How long process has computed, and how much longer to
completion
3. Resources the process has used
4. Resources process needs to complete
5. How many processes will need to be terminated
6. Is process interactive or batch?
25
RECOVERY FROM DEADLOCK: RESOURCE
PREEMPTION
Selecting a victim – minimize cost
Rollback – return to some safe state, restart
process for that state
Starvation – same process may always be picked
as victim, include number of rollback in cost factor
26
