Transcript Document

Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
主講人：虞台文
Content



Deadlocks with Reusable and Consumable Resources
Approaches to the Deadlock Problem
System Model
–
–
–

Deadlock Detection
–
–
–


Reduction of Resource Graphs
Special Cases of Deadlock Detection
Deadlock Detection in Distributed Systems
Recovery from Deadlock
Dynamic Deadlock Avoidance
–
–

Resource Graphs
State Transitions
Deadlock States and Safe States
Claim Graphs
The Banker’s Algorithm
Deadlock Prevention
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Deadlocks with
Reusable and
Consumable Resources
Deadlocks
Deadlocks

Informal definition: Process is blocked on
resource that will never be released.

Deadlocks waste resources

Deadlocks are rare:
–
Many systems ignore them

–
Resolved by explicit user intervention
Critical in many real-time applications

May cause damage, endanger life
Reusable/Consumable Resources

Reusable Resources
Number of units is “constant”
– Unit is either free or allocated; no sharing
– Process requests, acquires, releases units
Examples: (h/w) memory, devices (s/w) files, tables
–

Consumable Resources
Number of units varies at runtime
– Process may create new units
– Process may consume units (no releasing)
Examples: messages, signals
–
Reusable/Consumable Resources

Reusable Resources
Number of units is “constant”
– Unit is either free or allocated; no sharing
– Process requests, acquires, releases units
Examples: (h/w) memory, devices (s/w) files, tables
–

Consumable Resources
Main
topic
of at
the
lecture
Number
of units
varies
runtime
– Process may create new units
– Process may consume units (no releasing)
Examples: messages, signals
–
Reusable Resources
Example (File Sharing)
p1:
...
open(f1,w);
open(f2,w);
...
p2:
...
open(f2,w);
open(f1,w);
...
Deadlock when executed concurrently
Assume that send/recv are blocking operations.
Example (Message Passing)
p1:
...
if(C)send(p2,m);
while(1){
recv(p3,m);
...
send(p2,m);
}
p2:
...
while(1){
recv(p1,m);
...
send(p3,m);
}
p3:
...
while(1){
recv(p2,m);
...
send(p1,m);
}
Deadlock when C is not true
Deadlock and livelock will lead to starvation.
But, the inverse is not necessary true.
Deadlock, Livelock, and Starvation

Deadlock
–

Livelock
–
–

Two or more processes (threads) are blocked
indefinitely, waiting for each other.
Processes (threads) run but make no progress
An `active’ form of deadlock.
Starvation
–
–
Some Processes (threads) get deferred forever.
E.g., one process dominates, not allowing other
processes to progress.
Deadlock and livelock will lead to starvation.
But, the inverse is not necessary true.
Examples:
Starvation Not Due to Deadlock or Livelock

Higher-Priority Process dominates:
–

ML scheduling where one queue is never empty
Starvation on Memory Blocks:
–
–
Total memory is 200MB
Unbounded stream of 100MB requests may
starve a 200MB request
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Approaches to the
Deadlock Problem
Approaches to Deadlock Problem
1.
Detection and Recovery
–
2.
Avoidance (dynamic)
–
3.
Allow deadlock to happen and eliminate it
Runtime checks disallow allocations
that might lead to deadlocks
Prevention (static)
–
Restrict type of request and acquisition
to make deadlock impossible
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
System Model
Resource Graph
Process = Circle
Resource = Rectangle with small circles for each unit
Resource Request = Edge from process to resource class
Resource Allocation = Edge from resource unit to process
The state transition diagram described below is not complete.
The actual number of states depends on possible operations of
processes.
State Transitions by p1 Process
p1
p1
R
p2
S0
p1
R
p2
Request R
(by p1)
S1
p1
R
p2
Acquire R
(by p1)
S2
R
p2
Release R
(by p1)
S3
Process Operations on Resources
Request: Create new request edge piRj
–
–
pi has no outstanding requests
number of edges between pi and Rj  units in Rj
Acquisition: Reverse request edge to piRj
–
–
All requests of pi are satisfied
pi has no outstanding requests
p1
p1
p1
p1
Release: Remove edge piRj
R
p2
S0
R
p2
Request R
(by p1)
S1
R
p2
Acquire R
(by p1)
S2
R
p2
Release R
(by p1)
S3
Deadlock States and Safe States

A process is blocked in state S if it cannot cause a
transition to a new state, i.e.,
–



it cannot request, acquire, or release any resource.
A Process is Deadlocked in state S if it blocked now and
remains blocked forever.
Deadlock State
A state contains a deadlocked process.
Safe State
No deadlock state can ever be reached using request,
acquire, release.
Example
p1 and p2 both need R1 and R2.
p1
R1
p1:
Request(R1);
Request(R2);
p2:
Request(R2);
Request(R1);
Release(R2);
Release(R1);
Release(R1);
Release(R2);
R2
p2
Example
p1:
Request(R1);
Request(R2);
p2:
Request(R2);
Request(R1);
Release(R2);
Release(R1);
Release(R1);
Release(R2);
Example
p1:
Request(R1);
Request(R2);
p2:
Request(R2);
Request(R1);
Release(R2);
Release(R1);
Release(R1);
Release(R2);
Example
p1:
Request(R1);
Request(R2);
p2:
Request(R2);
Request(R1);
Release(R2);
Release(R1);
Release(R1);
Release(R2);
Example
p1:
Request(R1);
Request(R2);
p2:
Request(R2);
Request(R1);
Release(R2);
Release(R1);
Release(R1);
Release(R2);
Example
p1
R1
R2
p2
Example
p1 is blocked.
p2 is blocked.
No state is safe since the deadlock
state is always reachable.
Example
A deadlock state.
Necessary Condition for Deadlock
A cycle in the resource graph is
a necessary condition for
deadlock.
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Deadlock
Detection
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges

Deadlock  Graph not completely reducible.

All reduction sequences lead to the same result.
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges
p1
p2
R1
p3
R2
p4
R3
p5
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges
p1
p2
R1
p3
R2
p4
R3
p5
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges
p1
p2
R1
p3
R2
p4
R3
p5
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges
p1
p2
R1
p3
R2
p4
R3
p5
Graph Reduction Technique

Graph Reduction:
Repeat the following:
1. Select unblocked process p
2. Remove p and all request and allocation edges
Special Cases of Deadlock Detection

Testing for specific process p

Continuous deadlock detection

Immediate allocations

Single-unit resources




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Testing for specific process

Testing for specific process p:
– Reduce until p is removed or graph irreducible




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Continuous Deadlock Detection


Testing for specific process p:
– Reduce until p is removed or graph irreducible
Continuous deadlock detection:
1. Current state not deadlocked
2. Next state T deadlocked only if:
a. Operation was a request by p and
b. p is deadlocked in T
3. Try to reduce T by p
Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources




Immediate Allocations

All satisfiable requests granted immediately

Expedient state = no satisfiable request edges
Non-Expedient State
p1
p2
R1
Satisfiabl
e
p3
p1
Granted
R3 immediately
R2
p4
Expedient State
p5
p2
R1
p3
R2
p4
R3
p5




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Immediate Allocations

All satisfiable requests granted immediately

Expedient state = no satisfiable request edges

Knot K:
–
Every node in K reachable from any other node in K
–
No outgoing edges (only incoming)

Knot in expedient state  Deadlock

Intuition:
–
All processes must have outstanding requests in K
–
Expedient state   requests not satisfiable




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Immediate Allocations
Expedient State
p1
p2
R1
p3
R2
p4
R3
p5




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Immediate Allocations
Expedient State
p1
p2
R1
p3
R2
p4
R3
p5
Knot
Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources




Single-Unit Resources

For single-unit resource, cycle  deadlock
–
–
–
Every p must have a request edge to R
Every R must have an allocation edge to p
R is not available and thus p is blocked
p1
R1
p2
p1
R2
Not Deadlocked
R1
p2
R2
Deadlocked




Testing for specific process p
Continuous deadlock detection
Immediate allocations
Single-unit resources
Single-Unit Resources

Wait-For Graph (wfg): Show only processes
Deadlock Detection in Distributed Systems

Central Coordinator Approach

Distributed Approach
Central Coordinator Approach

Central Coordinator (CC)
–
–
–

Each machine maintains a
local wfg
Changes reported to CC
CC constructs and
analyzes global wfg
Problems
–
–
Coordinator is a
performance bottleneck
Communication delays may
cause phantom deadlocks
M1
M2
p2
p3
p1
p4
Deadlock
Due to timeout, p3 cancel the request.
But, the message passed to CC is
delayed
Phantom Deadlocks

Central Coordinator (CC)
M1
Each machine maintains a
local wfg
– Changes reported to CC
p1 requesting
the resource
– CC constructs
and
holding
by p4 causes
phantom
analyzes
global
wfg
–
M2
p2

p3
p1
p4
deadlock.

Problems
–
–
Coordinator is a
performance bottleneck
Communication delays may
cause phantom deadlocks
M1
M2
p2
p1
phantom
edge
p3
p4
Distributed Approach




Detect cycles using probes.
If process pi blocked on pj , it launches probe pi  pj
pj sends probe pi  pj  pk along all request edges, etc.
When probe returns to pi, cycle is detected
p1  p2  p3  p4  p5  p1
M1
p1
M3
M2
p1 p2
p2
p1  p2  p3
p3
p1  p2  p3  p7
p7
p1  p2  p3  p4
p4
p1  p2  p3  p4  p5
p1  p2  p3  p4  p5  p6 p4
p5
p1  p2  p3  p4  p5  p6
M4
p6
Distributed Approach




Detect cycles using probes.
If process pi blocked on pj , it launches probe pi  pj
Deadlock
pj sends
probe pi  pj  pk along all request edges, etc.
detected
by Mreturns
1.
When
probe
to pi, cycle is detectedDeadlock
detected by M4.
p1  p2  p3  p4  p5  p1
M1
p1
M3
M2
p1 p2
p2
p1  p2  p3
p3
p1  p2  p3  p7
p7
p1  p2  p3  p4
p4
p1  p2  p3  p4  p5
p1  p2  p3  p4  p5  p6 p4
p5
p1  p2  p3  p4  p5  p6
M4
p6
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Recovery from
Deadlock
Recovery from Deadlock

Process termination
–
–
Kill all processes involved in deadlock or
Kill one at a time. In what order?




By priority: consistent with scheduling or
By cost of restart: length of recomputation or
By impact on other processes: CS, producer/consumer
Resource preemption
–
–
Direct: Temporarily remove resource (e.g., Memory)
Indirect: Rollback to earlier “checkpoint”
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Dynamic
Deadlock Avoidance
Deadlock Avoidance

Deadlock Detection & Recovery
–
–

The resources requested by processes are
granted as long as they are available.
OS resolves deadlock if detected.
Deadlock Avoidance
–
–
Prevent deadlocks from developing by delaying
acquisition of resources that might cause
deadlock in the future.
Deadlock cannot occur.
The Prior Knowledge for Deadlock Avoidance



Deadlock avoidance requires some future
knowledge of requests for resources from each of
the participating processes.
The precise knowledge is usually not available in
advance.
Processes specify maximum claim, i.e., the largest
number of units of each resource needed at any
one time.
Maximum Claim Graph (MCG)



Process indicates maximum resources needed
Potential request edge: piRj (dashed)
May turn into real request edge
p1
R
p2
State Transition Using MCG



Process indicates maximum resources needed
Potential request edge: piRj (dashed)
May turn into real request edge
p1
p1
R
R
p2
S0
p1
R
p2
Request R
(by p2)
S1
p1
R
p2
Acquire R
(by p2)
S2
p1
R
p2
Request R
(by p1)
S3
p2
Acquire R
(by p1)
S4
Testing for safety algorithm (Dijkstra 1968)
The Banker’s Algorithm


Theorem: Prevent acquisitions from producing a
irreducible claim graph  All state are safe.
Banker’s algorithm:
–
Given a satisfiable request, pR, temporarily grant
request: changing pR to Rp
–
Reduce new claim graph
–
If it is completely reducible, proceed
else reverse acquisition.
The Banker’s Algorithm
p1
p2
R1
p3
R2
Can p1R1 be safely be granted?
Can p2R1 be safely be granted?
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
R1
p3
R2
Which of the requests can safely be granted?
Can p1R1 be safely be granted?
Can p2R1 be safely be granted?
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
p3
Temporarily
grant
R1
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted?
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
p3
Temporarily
grant
R1
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted?
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
p3
granted
R1
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted?
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
R1
p3
R2
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
Temporarily
grant p2
R1
p3
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted?
The Banker’s Algorithm
not
p
granted 2
p1
R1
p3
R2
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
R1
p3
R2
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted?
The Banker’s Algorithm
p1
p2
R1
Temporarily
grant
p3
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted? 
The Banker’s Algorithm
p1
p2
R1
Temporarily
grant
p3
R2
Can such an RAG be completely reducible?
Can p1R1 be safely be granted? 
Can p2R1 be safely be granted? 
Can p3R1 be safely be granted? 
The Banker’s Algorithm
p1
p2
R1
p3
granted
R2
Special Case: Single-Unit Resource

Check for cycles after
tentative acquisition
–

Disallow if cycle is found
If claim graph contains
no undirected cycles,
all states are safe
–
No directed cycle can
ever be formed. 
Operating Systems Principles
Process Management and Coordination
Lecture 6: Deadlocks
Deadlock
Prevention
Deadlock Prevention

Deadlock Detection & Recovery
–
–

Deadlock Avoidance
–
–

Granted resources as long as they are available.
OS resolves deadlock if detected.
Os performs runtime checks to ensure the system
never enters unsafe state.
Deadlock cannot occur.
Deadlock Prevention
–
–
All processes must follow certain rules for requesting
and releasing resources.
Deadlock is impossible to occur.
Eliminating any of these conditions would
make deadlock impossible.
Conditions for a Deadlock

Mutual exclusion:
Resources are not sharable.

Hold and wait:
Process must be holding one resource while requesting another.

No preemption:
No resource is preemptable.

Circular wait:
A closed chain of processes exists, such that each process
holds at least one resources needed by the next process in
the chain.

Eliminating any of



Mutual exclusion
Hold and wait
No preemption
Circular wait
Deadlock Prevention

Eliminating the `Mutual Exclusion’ Condition
–
Not possible in most cases

E.g., data files and databases for write access are not
sharable.
–
Spooling makes I/O devices sharable

Virtual devices

Eliminating any of



Mutual exclusion
Hold and wait
No preemption
Circular wait
Deadlock Prevention


Eliminating the `Hold and Wait’ Condition
–
Request all resources at once
–
Release all resources before a new request
Eliminating the `No preemption’ Condition
–
Release all resources if current request blocks

Eliminating any of



Mutual exclusion
Hold and wait
No preemption
Circular wait
Deadlock Prevention

Eliminating the `Circular Wait’ Condition
–
Impose a total ordering of all resource types,
and require that each process requests
resources in an increasing order of enumeration.
Fact: A cycle in the resource graph can develop only
when processes request the same resources in the
different order.
Comparisons