Transcript Implementing Processes, Threads, and Resources

Slide 10-1
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-2
Deadlock
Copyright © 2004 Pearson Education, Inc.
10
Operating Systems: A Modern Perspective, Chapter 10
Deadlock
• System Model
• Deadlock Characterization
• Methods for Handling Deadlocks
– Deadlock Prevention
– Deadlock Avoidance
– Deadlock Detection & Recovery
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-3
Slide 10-4
Example
Process 1
Process 2
Resource 1
Resource 2
Process holds the resource
Process requests the resource
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Three Deadlocked Processes
Process 1
Process 2
Process 3
Resource 1
Resource 2
Resource 3
Process holds the resource
Process requests the resource
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-5
A Model
•
•
•
•
P = {p1, p2, …, pn} be a set of processes
R = {R1, R2, …, Rm} be a set of resources
cj = number of units of Rj in the system
S = {S0, S1, …} be a set of states
representing the assignment of Rj to pi
– State changes when processes take action
– This allows us to identify a deadlock situation
in the operating system
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-6
State Transitions
Slide 10-7
• The system changes state because of the
action of some process, pi
• There are three pertinent actions:
– Request (“ri”): request one or more units of a
resource
– Allocation (“ai”): All outstanding requests from
a process for a given resource are satisfied
– Deallocation (“di”): The process releases units
of a resource
Sj
Copyright © 2004 Pearson Education, Inc.
xi
Sk
Operating Systems: A Modern Perspective, Chapter 10
Properties of States
Slide 10-8
• Want to define deadlock in terms of patterns
of transitions
• Define: pi is blocked in Sj if pi cannot cause
a transition out of Sj
a1
Sj
r3
r1
p2 is blocked in Sj
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Properties of States (cont)
• If pi is blocked in Sj, and will also be
blocked in every Sk reachable from Sj, then
pi is deadlocked
• Sj is called a deadlock state
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-9
Example
Slide 10-10
• One process, two units of one resource
• Can request one unit at a time
d
S0
Copyright © 2004 Pearson Education, Inc.
r
S1
d
a
S2
r
S3
a
Operating Systems: A Modern Perspective, Chapter 10
S4
Slide 10-11
Extension
of
Example
d
d
0
S00
r0
r1
S01
r0
d1
a1
S02
r1
r0
S10 a0
S20
r1 d0
S11 a0
d1
a1 d
0
S a0
r1
r1 d0
r1
12
r0 S
a0
S03
13
a1 d1 a1 d1
r0 S
S
04
Copyright © 2004 Pearson Education, Inc.
0
S21
a1
S22
S23
r0
r0
d1
r0
S30 a0
S40
r1 d
0
r1
S31 a0
d1
a
1
S32
r1
r0
S33
14
Operating Systems: A Modern Perspective, Chapter 10
S41
Resource Allocation Graph
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-12
Slide 10-13
Resource Allocation Graph (cont.)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
A Simple Process-Resource
Model Instance
P1
P2
P3
R1
R2
R3
Process holds resource
Process requests resource
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-14
Example of a graph with no
cycles
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-15
Example of a graph with a cycle
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-16
Basic Facts
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-17
Figure 10-10: A Model of a State with a Circular Wait
R
Ri
Slide 10-18
P
P holds R
Pi
P
R
P requests R
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Dining Philosophers Revisited
Slide 10-19
philosopher(int i){
while (TRUE) {
// Think
// Eat
P(fork[i]);
/* Pick up left fork */
P(fork[(i+1) mod 5]); /* Pick up right fork */
eat();
V(fork[(i+1) mod 5]);
V(fork[i]);
}
}
philosopher4(){
while (TRUE) {
// Think
// Eat
P(fork[0]);
/* Pick up right fork */
P(fork[4]);
/* Pick up left fork */
eat();
V(fork[4]);
semaphore fork[5];
V(fork[0]);
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1;
}
fork(philosopher, 1, 0);
}
fork(philosopher, 1, 1);
fork(philosopher, 1, 2);
fork(philosopher, 1, 3);
fork(philosopher4, 0);
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Addressing Deadlock
Slide 10-20
• Prevention: Design the system so that
deadlock is impossible
• Avoidance: Construct a model of system
states, then choose a strategy that will not
allow the system to go to a deadlock state
• Detection & Recovery: Check for deadlock
(periodically or sporadically), then recover
• Manual intervention: Have the operator
reboot the machine if it seems too slow
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Prevention
• Necessary conditions for deadlock
–
–
–
–
Mutual exclusion
Hold and wait
Circular waiting
No preemption
• Ensure that at least one of the necessary
conditions is false at all times
– Mutual exclusion must hold at all times
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-21
Hold and Wait
Slide 10-22
• Need to be sure a process does not hold one
resource while requesting another
• Approach 1: Force a process to request all
resources it needs at one time
– Used in batch processing systems
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Hold and Wait
Slide 10-23
• Approach 2: If a process needs to acquire a
new resource, it must first release all
resources it holds, then reacquire all it needs
– Used in interactive systems
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Circular Wait
Slide 10-24
• Have a situation in which there are K
processes holding units of K resources
R
Ri
P
P holds R
Pi
P
R
P requests R
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Circular Wait (cont)
Slide 10-25
• There is a cycle in the graph of processes
and resources
• Choose a resource request strategy by
which no cycle will be introduced
• Total order on all resources, then can only
ask for Rj if Ri < Rj for all Ri the process is
currently holding
• This is how we noticed the easy solution for
the dining philosophers
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Allowing Preemption
• Allow a process to time-out on a blocked
request -- withdrawing the request if it fails
ru
Si
dv
Copyright © 2004 Pearson Education, Inc.
wu
Sk
Sj
ru
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-26
Avoidance
Slide 10-27
• Define a model of system states, then
choose a strategy that will guarantee that the
system will not go to a deadlock state
• Requires extra information, e.g., the
maximum claim for each process
• Allows resource manager to see the worst
case that could happen, then to allow
transitions based on that knowledge
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-28
Safe vs Unsafe States
• Safe state: one in which the system can assure
that any sequence of subsequent transitions
leads back to the initial state
– Even if all exercise their maximum claim, there is an
allocation strategy by which all claims can be met
• Unsafe state: one in which the system cannot
guarantee that the system will transition back to
the initial state
– Unsafe state can lead to a deadlock state if too many
processes exercise their maximum claim at once
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
More on Safe & Unsafe States
Slide 10-29
Likely to be in a safe state
Normal
Execution
Request No
Max Claim
Yes
Execute, then
release
Probability of being in unsafe state increases
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
More on Safe & Unsafe States
Slide 10-30
I
Disallow
Safe States
Unsafe States
Deadlock States
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Basic Facts
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-31
Banker's Algorithm
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-32
Banker’s Algorithm
Slide 10-33
• Let maxc[i, j] be the maximum claim for Rj
by pi
• Let alloc[i, j] be the number of units of Rj
held by pi
• Can always compute
– avail[j] = cj - S0i< nalloc[i,j]
– Then number of available units of Rj
• Should be able to determine if the state is
safe or not using this info
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Banker’s Algorithm
• Copy the alloc[i,j] table to alloc’[i,j]
• Given C, maxc and alloc’, compute avail
vector
• Find pi: maxc[i,j] - alloc’[i,j]  avail[j]
for 0  j < m and 0  i < n.
– If no such pi exists, the state is unsafe
– If alloc’[i,j] is 0 for all i and j, the state is safe
• Set alloc’[i,j] to 0; deallocate all resources
held by pi; go to Step 2
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-34
Slide 10-35
Example
Maximum Claim
Process
p0
p1
p2
p3
p4
R0
3
0
5
1
3
R1
2
2
1
5
0
R2
1
5
0
3
3
R3
4
2
5
0
3
Allocated Resources
Process
p0
p1
p2
p3
p4
Sum
R0
2
0
4
0
1
7
Copyright © 2004 Pearson Education, Inc.
R1
0
1
0
2
0
3
R2
1
2
0
1
3
7
R3
1
1
3
0
0
5
C = <8, 5, 9, 7>
•Compute total allocated
•Determine available units
avail = <8-7, 5-3, 9-7, 7-5>
= <1, 2, 2, 2>
•Can anyone’s maxc be met?
maxc[2,0]-alloc’[2,0] = 5-4 = 11 = avail[0]
maxc[2,1]-alloc’[2,1] = 1-0 = 12 = avail[1]
maxc[2,2]-alloc’[2,2] = 0-0 = 02 = avail[2]
maxc[2,3]-alloc’[2,3] = 5-3 = 22 = avail[3]
•P2 can exercise max claim
avail[0] = avail[0]+alloc’[2,0] = 1+4 = 5
avail[1] = avail[1]+alloc’[2,1] = 2+0 = 2
avail[2] = avail[2]+alloc’[2,2] = 2+0 = 2
avail[3] = avail[3]+alloc’[2,3] = 2+3 = 5
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-36
Example
Maximum Claim
Process
p0
p1
p2
p3
p4
R0
3
0
5
1
3
R1
2
2
1
5
0
R2
1
5
0
3
3
R3
4
2
5
0
3
Allocated Resources
Process
p0
p1
p2
p3
p4
Sum
R0
2
0
0
0
1
3
Copyright © 2004 Pearson Education, Inc.
R1
0
1
0
2
0
3
R2
1
2
0
1
3
7
R3
1
1
0
0
0
2
C = <8, 5, 9, 7>
•Compute total allocated
•Determine available units
avail = <8-3, 5-3, 9-7, 7-2>
= <5, 2, 2, 5>
•Can anyone’s maxc be met?
maxc[4,0]-alloc’[4,0] = 5-1 = 45 = avail[0]
maxc[4,1]-alloc’[4,1] = 0-0 = 02 = avail[1]
maxc[4,2]-alloc’[4,2] = 3-3 = 02 = avail[2]
maxc[4,3]-alloc’[4,3] = 3-0 = 35 = avail[3]
•P4 can exercise max claim
avail[0] = avail[0]+alloc’[4,0] = 5+1 = 6
avail[1] = avail[1]+alloc’[4,1] = 2+0 = 2
avail[2] = avail[2]+alloc’[4,2] = 2+3 = 5
avail[3] = avail[3]+alloc’[4,3] = 5+0 = 5
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-37
Example
Maximum Claim
Process
p0
p1
p2
p3
p4
R0
3
0
5
1
3
R1
2
2
1
5
0
R2
1
5
0
3
3
R3
4
2
5
0
3
R2
1
2
0
1
0
4
R3
1
1
0
0
0
2
Allocated Resources
Process
p0
p1
p2
p3
p4
Sum
R0
2
0
0
0
0
2
Copyright © 2004 Pearson Education, Inc.
R1
0
1
0
2
0
3
C = <8, 5, 9, 7>
•Compute total allocated
•Determine available units
avail = <8-2, 5-3, 9-4, 7-2>
= <6, 2, 5, 5>
•Can anyone’s maxc be met?
•p1
•Can anyone’s maxc be met?
(Yes, any of them can)
Operating Systems: A Modern Perspective, Chapter 10
Detection & Recovery
• Check for deadlock (periodically or
sporadically), then recover
• Can be far more aggressive with allocation
• No maximum claim, no safe/unsafe states
• Differentiate between
– Serially reusable resources: A unit must be
allocated before being released
– Consumable resources: Never release acquired
resources; resource count is number currently
available
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-38
Reusable Resource Graphs
(RRGs)
Slide 10-39
• Micro model to describe a single state
• Nodes = {p0, p1, …, pn}  {R1, R2, …, Rm}
• Edges connect pi to Rj, or Rj to pi
– (pi, Rj) is a request edge for one unit of Rj
– (Rj, pi) is an assignment edge of one unit of Rj
• For each Rj there is a count, cj of units Rj
• Number of units of Rj allocated to pi plus
the number requested by pi cannot exceed cj
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
State Transitions due to Request
Slide 10-40
• In Sj, pi is allowed to request qch units of
Rh, provided pi has no outstanding requests.
• Sj  Sk, where the RRG for Sk is derived
from Sj by adding q request edges from pi to
Rh
q edges
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi request q units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
State Transition for Acquire
Slide 10-41
• In Sj, pi is allowed to acquire units of Rh, iff
there is (pi, Rh) in the graph, and all can be
satisfied.
• Sj  Sk, where the RRG for Sk is derived
from Sj by changing each request edge to an
assignment edge.
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi acquires units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
State Transition for Release
Slide 10-42
• In Sj, pi is allowed to release units of Rh, iff
there is (Rh, pi) in the graph, and there is no
request edge from pi.
• Sj  Sk, where the RRG for Sk is derived
from Sj by deleting all assignment edges.
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi releases units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-43
Single Instance of Each Resource
Type
• Maintain a resource allocation graph
• Periodically invoke algorithm that searches
for cycles in the graph
• If there is a cycle ==> set of processes in
cycle are in deadlock
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Example
R
p
P holds one unit of R
P requests one unit of R
p
R
A Deadlock State
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-44
Slide 10-45
Example
Not a Deadlock State
Copyright © 2004 Pearson Education, Inc.
No Cycle in the Graph
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-46
Example
p0
p1
S00
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-47
Example
Copyright © 2004 Pearson Education, Inc.
p0
p0
p1
p1
S00
S01
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-48
Example
Copyright © 2004 Pearson Education, Inc.
p0
p0
p0
p1
p1
p1
S00
S01
S11
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-49
Example
Copyright © 2004 Pearson Education, Inc.
p0
p0
p0
p0
p1
p1
p1
p1
S00
S01
S11
S21
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-50
Example
Copyright © 2004 Pearson Education, Inc.
p0
p0
p0
p0
p0
p1
p1
p1
p1
p1
S00
S01
S11
S21
S22
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-51
Example
p0
p0
p0
p0
p0
p0
...
Copyright © 2004 Pearson Education, Inc.
p1
p1
p1
p1
p1
p1
S00
S01
S11
S21
S22
S33
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-52
Graph Reduction
• Deadlock state if there is no sequence of
transitions unblocking every process
• A RRG represents a state; can analyze the
RRG to determine if there is a sequence
• A graph reduction represents the (optimal)
action of an unblocked process. Can reduce
by pi if
– pi is not blocked
– pi has no request edges, and there are (Rj, pi) in
the RRG
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Graph Reduction (cont)
• Transforms RRG to another RRG with all
assignment edges into pi removed
• Represents pi releasing the resources it
holds
pi
Reducing by pi
pi
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-53
Graph Reduction (cont)
Slide 10-54
• A RRG is completely reducible if there a
sequence of reductions that leads to a RRG
with no edges
• A state is a deadlock state if and only if the
RRG is not completely reducible.
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-55
Example RRG
p0
p1
p0
p2
p1
p0
p1
Copyright © 2004 Pearson Education, Inc.
p2
p0
p2
p1
Operating Systems: A Modern Perspective, Chapter 10
p2
Example RRG
p0
p1
Copyright © 2004 Pearson Education, Inc.
p2
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-56
Consumable Resource Graphs
(CRGs)
Slide 10-57
• Number of units varies, have
producers/consumers
• Nodes = {p0, p1, …, pn}  {R1, R2, …, Rm}
• Edges connect pi to Rj, or Rj to pi
– (pi, Rj) is a request edge for one unit of Rj
– (Rj, pi) is an producer edge (must have at least
one producer for each Rj)
• For each Rj there is a count, wj of units Rj
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
State Transitions due to Request
Slide 10-58
• In Sj, pi is allowed to request any number of
units of Rh, provided pi has no outstanding
requests.
• Sj  Sk, where the CRG for Sk is derived
from Sj by adding q request edges from pi to
Rh
q edges
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi request q units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-59
State Transition for Acquire
• In Sj, pi is allowed to acquire units of Rh, iff
there is (pi, Rh) in the graph, and all can be
satisfied.
• Sj  Sk, where the CRG for Sk is derived
from Sj by deleting each request edge and
decrementing wh.
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi acquires units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-60
State Transition for Release
• In Sj, pi is allowed to release units of Rh, iff
there is (Rh, pi) in the graph, and there is no
request edge from pi.
• Sj  Sk, where the CRG for Sk is derived
from Sj by incrementing wh.
pi
Rh
State Sj
Copyright © 2004 Pearson Education, Inc.
pi releases 2 units
of Rh
pi
Rh
State Sk
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-61
Example
Copyright © 2004 Pearson Education, Inc.
p0
p0
p0
p0
p0
p1
p1
p1
p1
p1
Operating Systems: A Modern Perspective, Chapter 10
Deadlock Detection
• May have a CRG that is not completely
reducible, but it is not a deadlock state
• For each process:
– Find at least one sequence which leaves each
process unblocked.
• There may be different sequences for
different processes -- not necessarily an
efficient approach
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-62
Slide 10-63
Deadlock Detection
• May have a CRG that is not completely
reducible, but it is not a deadlock state
• Only need to find sequences, which leave
each process unblocked.
p0
p1
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-64
Deadlock Detection
• May have a CRG that is not completely
reducible, but it is not a deadlock state
• Only need to find a set of sequences, which
leaves each process unblocked.
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
General Resource Graphs
• Have consumable and reusable resources
• Apply consumable reductions to
consumables, and reusable reductions to
reusables
• See Figure 10.29
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-65
GRG Example (Fig 10.29)
p3
Slide 10-66
p2
R0
R2
R1
p0
p1
Reusable
Consumable
Not in Fig 10.29
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-67
GRG Example (Fig 10.29)
p3
p2
Reduce by p3
R0
R2
R1
p0
p1
Reusable
Consumable
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-68
GRG Example (Fig 10.29)
p3
p2

R1
R0
p0
R2
p1
Reduce by p0
Reusable
Consumable
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Recovery
• No magic here
–
–
–
–
Choose a blocked process
Preempt it (releasing its resources)
Run the detection algorithm
Iterate it until the state is not a deadlock state
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-69
Recovery From Deadlock
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-70
Deadlock Detection-- Usage
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 10
Slide 10-71