Computer Systems Deadlocks
Dr. Mian M. Hamayun
m.m.hamayun@bham.ac.uk
Lecture Objective
The objective of this lecture is to
develop a basic understanding of deadlocks and the techniques used to deal with them.
Slide #2 of 49
Lecture Outline
Introduction
Reusable vs. Consumable Resources Deadlock Conditions
Resource Allocation Graphs
Deadlock Handling Deadlock Prevention Deadlock Avoidance Deadlock Detection
Summary
Slide #3 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 Alvin F. Harlow
Slide #4 of 49
What is a Deadlock?
Slide #5 of 49
Deadlock – How it can happen?
Slide #6 of 49
Deadlock – How it may not happen!
Slide #7 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 #8 of 49
Reusable Resources – Example#1
Slide #9 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 #10 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 #11 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 #12 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 #13 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 #14 of 49
Resource Allocation Graphs
Directed graph that depicts the state of a system of resources and processes
Slide #15 of 49
Resource Allocation Graphs
Slide #16 of 49
Resource Allocation Graphs
Slide #17 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 #18 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 #19 of 49
DEADLOCK PREVENTION
Slide #20 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 #21 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 #22 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 #23 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 #24 of 49
DEADLOCK AVOIDANCE
Slide #25 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 #26 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 #27 of 49
Deadlock Avoidance
Slide #28 of 49
Deadlock Avoidance
Properties of the Resource Matrix System
1) Rj =Vj + ∑iAij forallj
All resources are either allocated or available.
2) Cij ≤ Rj for all i,j
No process can claim more than the total system resource.
3) Aij ≤ Cij for all i,j
No process is allocated more than its claim.
Slide #29 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 #30 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 #31 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 ≤ Vj 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 #32 of 49
Deadlock Avoidance – Example # 1
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 # 2
Slide #38 of 49
Deadlock Avoidance – Example # 2
Don’t Grant this Request!
Slide #39 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 #40 of 49
DEADLOCK
DETECTION & RECOVERY
Slide #41 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 #42 of 49
Deadlock Detection – Example
Slide #43 of 49
Deadlock Detection – Example
Slide #44 of 49
Deadlock Detection – Example
Slide #45 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: Min Resources First i.e. processor time used, output produced, resources held etc.).
Slide #46 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 #47 of 49
Summary
Slide #48 of 49
References / Links
Chapter #7: Deadlocks, Operating System Concepts (9th Edition) by Abraham Silberschatz, Peter Baer Galvin and Greg Gagne
Chapter #6: Concurrency: Deadlocks and Starvation, Operating Systems: Internals and Design Principles (7th edition) by William Stallings
Slide #49 of 49