PowerPoint Presentation
Computer Systems
Deadlocks
Dr. Mian M. Hamayun
m.m. .uk
Slide #2 of 49
Lecture Objective
The objective of this lecture is to
develop a basic understanding of deadlocks and
the techniques used to deal with them.
Slide #3 of 49
Lecture Outline
Introduction
Reusable vs. Consumable Resources
Deadlock Conditions
Resource Allocation Graphs
Deadlock Handling
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection
Summary
Slide #4 of 49
A Treasury of the Railroad Folklore
“When two trains approach each other at a crossing,
both shall come to a full stop and neither shall start up
again until the other has gone.”
Statute passed by the Kansas State Legislature, early in
the 20th
century.
— A TREASURY OF RAILROAD FOLKLORE,
B. A. Botkin and . #5 of 49
What is a Deadlock?
Slide #6 of 49
Deadlock – How it can happen?
Slide #7 of 49
Deadlock – How it may not happen!
Slide #8 of 49
Reusable Resources
Used by only one process at a time and not depleted by
that use.
Processors, I/O channels, main and secondary memory,
devices, and data structures such as files, databases, and
semaphores
Processes obtain resources that they later release for
reuse by other processes
Deadlock occurs if each process holds one resource
and requests the other
Slide #9 of 49
Reusable Resources – Example#1
Slide #10 of 49
Reusable Resources – Example#2
Space is available for allocation of 200Kbytes, and the
following sequence of events occur
Deadlock occurs if both processes progress to their
second request
Slide #11 of 49
Consumable Resources
Created (produced) and destroyed (consumed)
Interrupts, signals, messages, and information in I/O buffers
For Example: Deadlock may occur if a Receive
message is blocking
May take a rare combination of events to cause deadlock
Slide #12 of 49
What is a Deadlock?
A deadlock is a permanent blocking of a set of
processes competing for resources
It is a circular resource conflict between a set of
processes
Each process currently holds a resource requested by another
process
Each process waits for another process to release its resource
Involve conflicting needs for resources by two or more
processes
No efficient solution!
Slide #13 of 49
Conditions for a Deadlock
There are 4 deadlock conditions that, when they all hold,
will necessarily lead to a deadlock
Three Preconditions:
1) Mutual Exclusion
Only one process may use a resource at a time
2) Hold-and-wait
Process can hold resources, while it is waiting for other
resources to become available.
3) No Preemption
Processes cannot be interrupted to free their resources by
force
Slide #14 of 49
Conditions for a Deadlock
Occurrence of a particular sequence of events that leads
to a Circular Wait
4) Circular Wait
Processes wait for each other to release resources they
want to acquire, they form a kind of “closed chain of
processes”
Slide #15 of 49
Resource Allocation Graphs
Directed graph that depicts the state of a system of
resources and processes
Slide #16 of 49
Resource Allocation Graphs
Slide #17 of 49
Resource Allocation Graphs
Slide #18 of 49
Deadlock Conditions
A deadlock occurs when a circular wait occurs and
cannot be resolved
A circular wait cannot be resolved when conditions 1 to
3 hold!
Therefore
If conditions 1 to 3 occur, then there is a possibility of a
deadlock
If conditions 1 to 4 occur, then there will necessarily be a
deadlock
Slide #19 of 49
Handling Deadlocks
Deadlock Prevention
Avoid at least one of the 4 deadlock conditions
Deadlock Avoidance
The reservation of resources that would lead to deadlock,
are not granted
Deadlock Detection
There is no restriction on resource allocation
There is a periodic check whether a deadlock is occurring
In case a deadlock is detected, recovery mechanisms are
employed
Slide #20 of 49
DEADLOCK
PREVENTION
Slide #21 of 49
Deadlock Prevention
The operating system is designed to prevent deadlocks
from occurring
Indirect deadlock prevention
Avoid occurrence of one of the conditions 1, 2, 3 i.e. Mutual
exclusion, hold and wait, no preemption
Direct deadlock prevention
Avoid Circular Waits (condition 4)
Slide #22 of 49
Indirect Deadlock Prevention
Mutual Exclusion Prevention
This cannot be avoided, as a lack of mutual exclusion may
lead to race conditions
Hold and Wait Prevention
Pre-allocation of all required resources in advance
Block a process until all resources become available
► Long delays for processes, low concurrency
► Inefficient utilization of resources
► A process may not know in advance what resources it will
require
Slide #23 of 49
Indirect Deadlock Prevention
No Preemption Prevention – May be implemented in
different ways.
If a process holding a resource is denied another resources
the first may also be preempted.
If a process needs a resource that is being used by another
process then preempt that resource.
Practically possible only when state of a resource can be
saved and restored, such as a processor (storing the
processor status word, context switch)
Slide #24 of 49
Direct Deadlock Prevention
Prevent Circular Wait from occurring
One way to prevent this is to associate an index with each
resource. Processes are then required to acquire resource
with lower index before acquiring resource of higher index
(resource ordering).
Consider two processes (A & B) competing for 2 resources
(Ri & Rj, where i < j). Suppose A acquires Ri first then it will
be able to proceed as B is not allowed to acquire Rj.
Usually Inefficient!
Slide #25 of 49
DEADLOCK
AVOIDANCE
Slide #26 of 49
Deadlock Avoidance
Assures that a deadlock never occurs!
A decision is made dynamically whether the current
resource allocation request will, if granted, potentially
lead to a deadlock?
Requires knowledge of future process requests
Slide #27 of 49
Deadlock Avoidance – Approaches
Allow the three necessary conditions but make intelligent
decisions while allocating resources.
1) Process Initiation Denial
Do not start a process if its demands might lead to deadlock
2) Resource Allocation Denial
Do not grant an incremental resource request to a process if
this allocation might lead to deadlock
Slide #28 of 49
Deadlock Avoidance
Slide #29 of 49
Deadlock Avoidance
Properties of the Resource Matrix System
1) Rj = Vj + ∑iAij for all j
All resources are either allocated or available.
2) Cij R≤ j for all i,j
No process can claim more than the total system resource.
3) Aij C≤ ij for all i,j
No process is allocated more than its claim.
Slide #30 of 49
Deadlock Avoidance
Process Initiation Denial
A new process P
(n+1)
is initiated, only if:
Rj C≥ (n+1)j + ∑iCij for all j
The process P
(n+1)
is started if the maximum claim of all
currently running processes i plus the claims of the new
process P
(n+1)
can be met.
This scheme assumes the worst i.e. it assumes that all
processes will demand the resources at the same time.
Slide #31 of 49
Deadlock Avoidance
Resource Allocation Denial (Banker’s Algorithm)
A process i is allocated a resource j only if the system
remains in safe state.
Safe State: A state in which there exists at least one
sequence of allocation to processes which does not
result in a deadlock.
State of system is reflected by the current allocation of
resources to processes
Slide #32 of 49
Finding a Safe Sequence?
Basic Question:
Can any of the participating processes run to completion
with the units of resources available?
Can the difference between the maximum requirement
and current allocation of any process be met with the
available resources?
Condition to be met by process i, using resource j:
Cij – Aij V≤ j for all j
The number of claimed units of resource j, minus the already allocated
units of resource j, must not be more than what is still available.
Slide #33 of 49
Deadlock Avoidance – Example # 1
Slide #34 of 49
Deadlock Avoidance – Example # 1
Slide #35 of 49
Deadlock Avoidance – Example # 1
Slide #36 of 49
Deadlock Avoidance – Example # 1
Slide #37 of 49
Deadlock Avoidance – Example # 1
Slide #38 of 49
Deadlock Avoidance – Example # 2
Slide #39 of 49
Deadlock Avoidance – Example # 2
Don’t Grant this Request!
Slide #40 of 49
Deadlock Avoidance – Summary
It is not necessary to preempt and rollback processes,
as in deadlock detection (coming later).
Less restrictive than deadlock prevention
Maximum resource requirement must be stated in
advance
Processes under consideration must be independent; no
synchronization requirements
There must be a fixed number of resources to allocate
No process may exit while holding resources
Slide #41 of 49
DEADLOCK
DETECTION & RECOVERY
Slide #42 of 49
Deadlock Detection (Algorithm)
1) Unmark (assume deadlocked (T)) all processes and define a
matrix Q representing future requests of each process.
2) Mark (not deadlocked (F)) all processes that have all zeros in
their allocation matrix A (means these have finished)
3) Initialize a temporary vector W (work vector) equal to V (available
resource vector)
4) Find an index i such that process i is unmarked (assumed
deadlocked) and where W such that Qik ≤ Wk for 1 k m≤ ≤ .
5) If such a row is found then update W as Wk = Wk + Aik for all 1 ≤
k m≤ and mark (not deadlocked) process i. Go to step 4 above.
6) If no row is found stop the algorithm.
7) All unmarked processes are the deadlocked processes.
Slide #43 of 49
Deadlock Detection – Example
Slide #44 of 49
Deadlock Detection – Example
Slide #45 of 49
Deadlock Detection – Example
Slide #46 of 49
Deadlock Recovery
1) Abort all processes involved in a deadlock.
2) Roll back each deadlocked process to some previous
state and then restart the processes
3) Abort deadlocked processes one by one until deadlock
exists no more.
4) Preempt the resources one by one until the deadlock
exists no more.
The preemption or aborting should be done on some criteria
and not at random (Ex: First i.e. processor time
used, output produced, resources held etc.).
Slide #47 of 49
Integrated Deadlock Strategy
It’s a Combination of Approaches. For example:
Group Resources (in resource classes)
Swappable Space: blocks of memory on secondary storage for
use in swapping processes
Process Resources: assignable devices, such as tape drives,
files (I/O) etc.
Main Memory: assignable to processes in pages or segments
Apply different strategies
Swappable space: deadlock prevention (all required resources
allocated at once, maximum storage requirements to be known)
Process resources: deadlock avoidance (processes declare
ahead of time the resources they will require). Prevention is also
possible by resource ordering.
Main memory: deadlock prevention by preemption.
Slide #48 of 49
Summary
Slide #49 of 49
References / Links
Chapter #7: Deadlocks, Operating System
Concepts (9th Edition) by ,
Galvin and
Chapter #6: Concurrency: Deadlocks and
Starvation, Operating Systems: Internals and
Design Principles (7th edition) by
Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46
Slide 47
Slide 48
Slide 49