CS345 - Concurrency

Report
Chapter 6
Concurrency:
Deadlock and Starvation
Objectives
Topics to Cover…










Resources
Deadlock
Joint Process Diagrams
Deadlock Conditions
Circular Wait
Resource Allocation Graph
Handling Deadlock
Avoidance
Detection
Recovery
BYU CS 345
Concurrency
2
Resources
Reusable Resources




Used by one process at a time and not
depleted by that use
Processes obtain resources that they later
release for reuse by other processes
Processor time, I/O channels, main and
secondary memory, files, databases, and
semaphores
Deadlock occurs if each process holds
one resource and requests the other
BYU CS 345
Concurrency
3
Resources
Consumable Resources




Created (produced) and destroyed
(consumed) by a process
Interrupts, signals, messages, and
information in I/O buffers
Deadlock may occur if a Receive
message is blocking
May take a rare combination of events to
cause deadlock
BYU CS 345
Concurrency
4
Deadlock
Deadlock

System Model



Process must request a resource before
using
Process must release the resource when
done
Deadlock

A set of processes is in a deadlock state
when every process in the set is waiting for
an event that can only be caused by another
process in the set.
BYU CS 345
Concurrency
5
Deadlock
Quiz 6.1

How could deadlock occur when




200K bytes of memory is available for
allocation by the system
Process 1 needs 140K in 80K, 60K blocks
Process 2 needs 150k in 70K, 80K blocks
Answer…
BYU CS 345
Process 1
Process 2
Request 80K bytes
…
…
Request 70K bytes
Request 60K bytes
…
…
Request 80K bytes
Concurrency
6
Deadlock
Quiz 6.2

How could deadlock occur when




Two processes need to communicate via
send/receive messages
Process 1 waits to hear from process 2 before
sending data
Process 2 proceeds after hearing from process 1
Answer…
BYU CS 345
Process 1
Process 2
Receive(P2)
…
…
Receive(P1)
Send(P2)
…
…
Send(P1)
Concurrency
7
Deadlock
Quiz 6.3

How is this deadlock??
BYU CS 345
Concurrency
8
Diagrams
Joint Process Diagram
Progress
of Q
2
1
Release A
A
Required
Both P and Q
have A
Release B
Get A
B
Required
5
?
P has B
Q has A
Both P and Q
have B
4
Get B
6
Fatal Region
P has A, Q has B
Deadlock!
Get A
Get B
3
Release A Release B
Progress
of P
A Required
B Required
BYU CS 345
Concurrency
9
Diagrams
Joint Process Diagram
P has A
Q has B
Ok!
Progress
of Q
1
2
P has A and B
Q wants A
Can’t get there!
Release B
B
Required
Both P and Q
have B
Release A
Get B
?
A
Required
Both P and Q
have A
4
Get A
3
Q has A wants B,
P wants A?
Can’t get there!
BYU CS 345
Get A
Get B
Release A Release B
Progress
of P
A Required
B Required
Concurrency
10
Diagrams
Joint Process Diagram
Progress
of Q
1
2
3
Release
A
A
Required
Release
B
6
Both
P and Q
have A
Get A
Both
P and Q
have B
B
Required
5
Get B
4
Get A
Release A Get B
A
Required
BYU CS 345
Concurrency
Release B
Progress
of P
B
Required
11
Necessary Conditions
Necessary Conditions

Mutual exclusion



Hold-and-wait


only one process may use a resource at a
time.
no process may access resource allocated to
another.
a process may hold allocated resources while
awaiting assignment of other resources.
No preemption

no resource can be forcibly removed from a
process holding it.
BYU CS 345
Concurrency
12
Necessary Conditions
Conditions for Deadlock

Circular wait




a closed chain of processes exists, such that
each process holds at least one resource
needed by the next process in the chain
consequence of the first three conditions
Other conditions are necessary but not
sufficient for deadlock - all four conditions
must hold for deadlock
Unresolvable circular wait is the definition
of deadlock!
BYU CS 345
Concurrency
13
Circular Wait
Circular Wait
Resource
A
Process
P1
Process
P2
Resource
B
BYU CS 345
Concurrency
14
Resource Allocation Graph
Describing Deadlock

Deadlocks can be described using
resource allocation graph

Vertices



Active processes {P1, P2, … }
Resources
{R1, R2, … }
Edges

A directed edge from Pi to Rj


A directed edge from Rj to Pi


Process Pi requested an instance of resource Rj
Resource Rj has been allocated to process Pi
Process are circles, resources are rectangles
BYU CS 345
Concurrency
15
Resource Allocation Graph
Resource Allocation Graph
R1
P1
R2
P2
Process are circles,
resources are rectangles
A directed edge from Pi to
Rj indicates process Pi
has requested an instance
of resource Rj
P3
A directed edge from Rj to Pi
indicates resource Rj has
been allocated to process Pi
R3
R4
BYU CS 345
Concurrency
16
Resource Allocation Graph
Resource Allocation Graph
R1
P1
R2
P2
Is there a cycle?
P3
If a graph contains no
cycles, then no
process in the system
is deadlocked
If the graph contains
a cycle, deadlock MAY
exist
R3
Is there deadlock?
R4
BYU CS 345
Concurrency
17
Resource Allocation Graph
Deadlock?
P2
Is there a cycle?
Yes
R1
P1
P3
Is there deadlock?
Maybe
R2
P4
BYU CS 345
Concurrency
18
Handling Deadlock
Handling Deadlock

Ensure the system will never deadlock

deadlock prevention



avoidance algorithms
Recover from deadlock


eliminate a condition
detect deadlock and eliminate it
Ignore deadlock


system may hang
so
BYU CS 345
Concurrency
19
Handling Deadlock
Prevention by Elimination

Mutual Exclusion



non-sharable resources
We can’t eliminate this condition
Hold and wait


guarantee that when a process requests a
resource, it does not hold any other resources
two protocols



system calls requesting resources precede all others
a process can only request resources when it has
none
low resource utilization?
BYU CS 345
Concurrency
20
Handling Deadlock
Eliminate No Preemption

If a process holds resources and requests
more that cannot be allocated, all its other
resources are preempted



If you can’t hold all, you can’t hold any
process is restarted only when it can have all
This works for resources whose state can
be easily saved and restored later


registers
memory
BYU CS 345
Concurrency
21
Handling Deadlock
Eliminate Circular Wait


Impose a total ordering of all resources
Require that all processes request
resources in increasing order.

Whenever a process requests a resource,
it must release all resources that are lower

These two protocols eliminate circular wait
BYU CS 345
Concurrency
22
Avoidance
Deadlock Avoidance


Allow general requests, but grant only when safe
Assume we know the maximum requests (claims) for each
process

Process must state it needs


Do not need to use its max claims



Ie. max of 5 A objects, 3 B objects, 2 C objects.
Ie. Ok to set max=5 and only use 3
Can make requests at any time and in any order
Process Initiation Denial



Track current allocations
Assume all processes may make maximum requests at the same
time
Only start process if it can’t result in deadlock regardless of
allocations
BYU CS 345
Concurrency
23
Avoidance
Resource Allocation Denial

Safe State – We can finish all processes by some
scheduling sequence


Banker’s Algorithm (Dijkstra)



Reject a request if it exceeds the processes’ declared maximum
claims
Grant a request if the new state would be safe
Determining if a state is safe




Example: Finish P1, P4, P2, P5, P3
Find any process Pi for which we can meet it’s maximum requests
 Don't forget already allocated resources
Mark Pi as “done”, add its resources to available resource pool
State is safe if we can mark all processes as “done”
Block a process if the resources are not currently available
or the new state is not safe
BYU CS 345
Concurrency
24
Avoidance
Avoidance Example
Claim
Allocation
A
B
C
P1
3
2
2
P1
P2
6
3
4
1
1
2
3
4
2
P2
P3
P4
Resource

P3
P4
A
B
C
9
3
6
C -A
A
B
C
1
5
2
0
0
1
1
0
0
1
1
2
Available
P1
P2
P3
P4
A
B
C
2
1
1
4
2
0
0
2
2
2
3
0
A
B
C
1
1
2
Are we in a safe state? Yes!
BYU CS 345
Concurrency
25
Avoidance
Quiz 6.4a
Carpentry Company XYZ has 4 employees, 9
clamps, 2 drills, and 2 bottles of glue.
Chair
Desk
Picture Frame
Book Case
BYU CS 345
4 clamps, 1 drill
6 clamps, 1 drill, 1 glue
4 clamps, 1 drill, 1 glue
6 clamps, 1 drill, 1 glue
Concurrency
26
Avoidance
Quiz 6.4a
Claim
Allotted
Clamp
Drill
Glue
P1
4
1
0
P2
6
4
6
1
1
1
1
1
1
P3
P4
Resource
Needed
Clamp
Drill
Glue
P1
1
0
0
P1
P2
2
2
2
0
1
0
1
0
0
P2
P3
P4
Clamp
Drill
Glue
9
2
2
Available
P3
P4
A
B
C
3
4
2
4
1
1
0
1
0
0
1
1
Clamp
Drill
Glue
2
1
1
P1 needs a drill. Is it OK to give it to him (ie. would
we still be in a safe state)?
Yes!
BYU CS 345
Concurrency
27
Avoidance
Quiz 6.4b
Claim
Allotted
Clamp
Drill
Glue
P1
4
1
0
P2
6
4
6
1
1
1
1
1
1
P3
P4
Resource
Needed
Clamp
Drill
Glue
P1
1
1
0
P1
P2
2
2
2
0
1
0
1
0
0
P2
P3
P4
Clamp
Drill
Glue
9
2
2
Available
P3
P4
A
B
C
3
4
2
4
0
1
0
1
0
0
1
1
Clamp
Drill
Glue
2
0
1
P4 needs a glue. Would you give it to him (still safe
state)?
No!
BYU CS 345
Concurrency
28
Avoidance
Quiz 6.4c
Claim
Allotted
Clamp
Drill
Glue
P1
4
1
0
P2
6
4
6
1
1
1
1
1
1
P3
P4
Resource
Needed
Clamp
Drill
Glue
P1
1
1
0
P1
P2
2
2
2
0
1
0
1
0
1
P2
P3
P4
Clamp
Drill
Glue
9
2
2
Available
P3
P4
A
B
C
3
4
2
4
0
1
0
1
0
0
1
0
Clamp
Drill
Glue
2
0
0
If you give P4 the glue, are we then deadlocked?
No!
BYU CS 345
Concurrency
29
Detection
Deadlock Detection



Avoidance methods tend to limit access to resources
Instead, grant arbitrary requests and watch for deadlock
Can vary how often we check


Early detection vs. overhead of checks
Algorithm (Stallings, Figure 6.9)




Preparation:
 Create table of process requests, current allocations
 Note available resources
Mark processes with no resources
Mark any process whose requests can be met (requests  available
resources)
 Include resources from that process as ‘available’ (this process
can finish)
 If multiple processes available, pick any
If any processes cannot be marked, they are part of a deadlock
BYU CS 345
Concurrency
30
Detection
Detection Example
Request
A
B
Allocation
C
D
A
E
D
E
P3
P4
0 0 0 0 0
0 1 0 0 1
P1
P2
0 0 1 0 1
0 0 0 0 1
1 0 1 0 1
P2
P4
C
1 0 1 1 0
1 1 0 0 0
0 0 0 1 0
P1
P3
B
Resource
A
B
C
D
A
B
C
D
E
2 1 1 2 1
Available
A
B
C
D
E
0 0 0 0 1
E
Temporary Available 0 0 0 1
0 1



Mark P4 (not holding anything someone else wants)
Mark P3, new available: 0 0 0 1 1
Cannot mark P1 or P2, so we are deadlocked
BYU CS 345
Concurrency
31
Detection
Quiz 6.4
Requests
P1
P2
P3
P4
P5
Allocation
A
B
C
0
2
0
1
0
0
0
0
0
0
0
2
0
0
2
P1
P2
P3
P4
P5
Temporary Available
Resource
A
B
C
A
B
C
0
2
3
1
0
0
0
0
3
7
2
6
2
0
1
0
1
2
A
B
C
0
0
0
Available
A
B
C
0
0
0
Are we deadlocked?
BYU CS 345
Concurrency
32
Detection
Deadlock Detection Questions?




Does it really work?
How often should you run a detection
process?
How often is deadlock likely to occur?
How expensive is the detection process?
BYU CS 345
Concurrency
33
Recovery
Deadlock Recovery


Several possible approaches
Abort all deadlocked processes


Back up processes to a previously saved checkpoint, then
restart




Simple but common
Assumes we have checkpoints and a rollback mechanism
Runs risk of repeating deadlock
 Assumes that the deadlock has enough timing dependencies it
won’t happen
Selectively abort processes until deadlock broken
Preempt resources until deadlock broken

Must roll back process to checkpoint prior to acquiring key
resource
BYU CS 345
Concurrency
34
Recovery
Deadlock Recovery

Process Termination






Kill them all
One at a time
Consider priority
Time computing
Who has most resources
Resource Preemption


Who gets preempted
Do you consider process rollback and
starvation
BYU CS 345
Concurrency
35
Recovery
Mixed Strategy

May group resources into classes, have a different
deadlock strategy for each class




Swap Space
 Prevent deadlocks by requiring all space to be allocated at
once
 Avoidance also possible
Tapes/Files
 Avoidance can be effective here
 Prevention by ordering resources also possible
Main Memory
 Preemption a good approach
Internal Resources (channels, etc.)
 Prevention by ordering resources
Can use linear ordering between classes

BYU CS 345
Concurrency
36
BYU CS 345
Concurrency
37

similar documents