OS - CS - 403 Unit - 3.2 Deadlocks - 2020
OS - CS - 403 Unit - 3.2 Deadlocks - 2020
OS - CS - 403 Unit - 3.2 Deadlocks - 2020
2
Deadlocks
Resource-Allocation Graph 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
Example P1 Request (1,0,2) (Cont.)
Example P1 Request (1,0,2) (Cont.)
Check that:
Request Need (that is, (1,0,2) (1,2,2) true.
and Request Available (that is, (1,0,2) (3,3,2) true.
Allocation Need Available
ABC A B CA B C
P0 010743 230
P1 3 0 20 2 0
P2 3 0 26 0 0
P3 211011
P4 002431
Executing safety algorithm shows that sequence <P1, P3, P4,
P0, P2> satisfies safety requirement.
Try Yourself
1. Can request for (3,3,0) by P4 be granted?
Consider the following snap-shot of a system with current state: (P1, P2, P3,
P4, P5 are processes and A, B, C, D are resources)
Need
Process
A B C D
P1 0 0 0 0
P2 0 7 5 0
P3 6 6 2 2
P4 2 0 0 2
P5 0 3 2 0
(ii) Is the system in safe state? Justify.
Applying the Banker’s Algorithm,
Let Avail be a vector of length 4.
Let Avail = Available, Avail = (2, 1, 0, 0)
Iteration 1. Check all processes , starting from P1 .
P1 Need < Avail; so P1 is Marked.
Now Avail = Avail + Allocated [1] = (2, 1, 0, 0) + (0, 0, 1, 2) = (2, 1, 1, 2)
P2 Need > Avail; so P2 is Not Marked.
P3 Need > Avail; so P3 is Not Marked.
P4 Need < Avail; so P4 is Marked.
Now Avail = Avail + Allocated [4] = (2, 1, 1, 2) + (2, 3, 5, 4) = (4, 4, 6, 6)
P5 Need < Avail; so P5 is Marked.
Now Avail = Avail + Allocated [5] = (4, 4, 6, 6) + (0, 3, 3, 2) = (4, 7, 9, 8)
Iteration 2. Check only P2 and P3 which are still un- Marked.
P2 Need < Avail; so P2 is Marked.
Now Avail = Avail + Allocated [2] = (4, 7, 9, 8) + (2, 0, 0, 0) = (6, 7, 9, 8)
P3 Need < Avail; so P3 is Marked.
Now Avail= Avail+ Allocated [2]=(6, 7, 9, 8)+(0, 0, 3, 4)=(6, 7, 12, 12) = System Capacity
Since all processes got marked, no further iterations are required.
The sequence is P1, P4, P5, P2, P3.
Since a safe sequence exits, the system satisfies the safety criteria.
(iii) So there is no deadlock as justified above that system satisfied the safety criteria.
(iv)Granting of request (0, 1, 0, 0) from P3.
Since the request [3] <Need [3], it is valid request. Also since request [3] <Available[3],
We can examined whether it can be safely granted immediately, which follows as:
Step 1: The system state after making the tentative grant of the request:
New State:
Allocated Max Available Need
Process Process
A B C D A B C D A B C D A B C D
P1 0 0 1 2 0 0 1 2 2 0 0 0 P1 0 0 0 0
P2 2 0 0 0 2 7 5 0 P2 0 7 5 0
P3 0 1 3 4 6 6 5 6 P3 6 5 2 2
P4 2 3 5 4 4 3 5 6 P4 2 0 0 2
P5 0 3 3 2 0 6 5 2 P5 0 3 2 0
Step2: Applying the Banker’s Algorithm to determine whether the new state is safe or
not. If the state is safe, the request can be safely granted immediately, else, grant of the
request is to be deferred.
Question Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
Consider the following snap-shot of a system with current state: (P1, P2, P3,
P4, P5 are processes and A, B, C, D are resources)