System Programming - II Deadlocks
System Programming - II Deadlocks
System Programming - II Deadlocks
Chapter 8
Deadlocks
Deadlocks
• Objective
• System Model
• Deadlock Characterization
• Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection
• Recovery from Deadlock
• Combined Approach to Deadlock Handling
2
Chapter Objectives
7
An example of Deadlock
8
Bridge Crossing Example
9
Resource-Allocation Graph
• A graph consist of set of vertices V and a set of edges E.
11
Resource-Allocation Graph (Cont.)
• Process
• Pi requests instance of Rj
Pi
Rj
• Pi is holding an instance of Rj
Pi
Rj
12
Example of a Resource Allocation Graph
R3 Assigned to P3
P2 Requests R3
13
Resource -Allocation Graph (Cont.)
Basic Facts
14
Resource-Allocation Graph (Cont.)
15
Cycle is Necessary, But….
16
Resource-Allocation Graph (Cont.)
17
Basic Facts
19
Deadlock Prevention
There are Four (4) Methods for Deadlock Prevention
(3) No Preemption:
– If a process that is holding some resources requests
another resource that cannot be immediately allocated
to it, then all resources currently being held are
released.
23
Deadlock Avoidance
24
Deadlock Avoidance (Contd.)
25
Safe State
• When a process requests an available resource, system must
decide if immediate allocation leaves the system in a safe
state.
• Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources
that Pi can still request can be satisfied by currently
available resources + resources held by all the Pj, with j<i.
26
Safe State (Contd.)
– When Pj is finished, Pi can obtain needed resources,
execute, return allocated resources, and terminate.
28
Safe and Unsafe States (2)
29
Safe State (Example)
Suppose p2 requests P1 4 2 2
and is given one more
tape drive. What P2 9 2 7
happens then?
30
Safe, Unsafe , Deadlock State
Deadlock
31
Avoidance algorithms
33
Resource-Allocation Graph For Deadlock
Avoidance
34
Unsafe State In Resource-Allocation Graph
35
Banker’s Algorithm
• Multiple instances.
38
Resource-Request Algorithm
Request = request vector for process Pi. If Requesti [j] = k then
process Pi wants k instances of resource type Rj.
1. If Requesti Needi go to step 2. Otherwise, raise error
condition, since process has exceeded its maximum claim.
2. If Requesti Available, go to step 3. Otherwise Pi must
wait, since resources are not available.
3. Pretend to allocate requested resources to Pi by modifying
the state as follows:
Available = Available = Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
•If safe the resources are allocated to Pi.
•If unsafe Pi must wait, and the old resource-allocation state
is restored
39
The Banker's Algorithm for a Single Resource
41
Example (Cont.)
• The content of the matrix. Need is defined to be Max –
Allocation.
Need
ABC
P0 7 4 3
P1 122
P2 600
P3 011
P4 431
• The system is in a safe state since the sequence < P1, P3, P4,
P2, P0> satisfies safety criteria.
42
Example P1 Request (1,0,2) (Cont.)
• Check that Request Available (that is, (1,0,2) (3,3,2) true.
Allocation Need Available
A B C A B CA B C
P0 010743 230
P1 3 0 20 2 0
P2 301600
P3 211011
P4 002431
• Executing safety algorithm shows that sequence <P1, P3, P4,
P0, P2> satisfies safety requirement.
• Can request for (3,3,0) by P4 be granted?
• Can request for (0,2,0) by P0 be granted?
43
Deadlock Detection
44
Single Instance of Each Resource Type
46
Several Instances of a Resource Type
47
Detection Algorithm
48
Detection Algorithm (Cont.)
49
Example of Detection Algorithm
• Five processes P0 through P4; three resource types
A (7 instances), B (2 instances), and C (6 instances).
• Snapshot at time T0:
Allocation Request Available
ABC ABC ABC
P0 0 1 0 000 000
P1 2 0 0 202
P2 303 000
P3 2 1 1 100
P4 0 0 2 002
• Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
for all i. 50
Example (Cont.)
• P2 requests an additional instance of type C.
Request
ABC
P0 0 0 0
P1 2 0 1
P2 001
P3 1 0 0
P4 002
• State of system?
– Can reclaim resources held by process P0, but insufficient
resources to fulfill other processes; requests.
– Deadlock exists, consisting of processes P1, P2, P3, and P4.
51
Detection-Algorithm Usage
• When should we invoke the detection algorithm?
52
Recovery from Deadlock:
Process Termination
• Abort all deadlocked processes.
55