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.
December 28, 2025
Deadlock Handling
Deadlock prevention
Deadlock avoidance
Deadlock detection and
recovery
December 28, 2025
Deadlock Prevention
Restrain the ways resource
allocation requests can be
made to insure that at least
one of the four necessary
conditions is violated.
December 28, 2025
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.
December 28, 2025
Deadlock Prevention
Hold and Wait – we must
guarantee that whenever a
process requests a
resource, it does not hold
any other resources.
December 28, 2025
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.
December 28, 2025
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.
December 28, 2025
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.
December 28, 2025
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.
December 28, 2025
Deadlock Prevention
We assign a unique number to
each resource type by using
function
F: R → N
and make sure that processes
request resources in an
increasing order of enumeration.
For example, tape drive = 1, disk
drive = 5, and printer = 12.
December 28, 2025
Deadlock Prevention
Proof
Let’s assume that there is a cycle
P0 → P 1 → P 2 → … → P k → P 0
R0 R1 R2 Rk R0
F(R0) < F(R1) < … F(Rk) < F(R0)
F(R0) < F(R0), which is impossible
There can be no circular wait.
December 28, 2025
Deadlock 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.
December 28, 2025
Deadlock 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.
December 28, 2025
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.
December 28, 2025
Safe State
Sequence <P1, P2, …, Pn> is safe if
for each Pi, the resources that Pi
can still request can be satisfied by
the currently available resources,
plus the resources held by all the
Pj, with j<i. In other words, a safe
sequence specifies the order in
which processes can be finished.
December 28, 2025
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.
December 28, 2025
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.
December 28, 2025
Safe, Unsafe, and
Deadlock States
December 28, 2025
Example
System with 12 tape drives and
three processes
Current system state:
Process Max Need Allocated
P0 10 5
P1 4 2
P2 9
December 28, 2025 2
Example
System is in a safe state with the
safe sequence <P1, P0, P2>
P2 requests and is allocated one
more tape drive.
Process Max Need Allocated
P0 10 5
P1 4 2
P2 9
December 28, 2025 2
Example
Assuming the the tape drive is
allocated to P2, the new system
state will be:
Process Max Need Allocated
P0 10 5
P1 4 2
P2 9 3
System gets into an unsafe state.
December 28, 2025
Recap of Lecture
Deadlock handling
Deadlock prevention
Deadlock avoidance
December 28, 2025