Page 122 - DCAP403_Operating System

Unit 6: Process Synchronization

Resources Assigned Notes

Processes Tapes Plotters Printers Toasters
A 3 0 1 1
B 0 1 0 0
C 1 1 1 0
D 1 1 0 1
E 0 0 0 0
Total Existing 6 3 4 2
Total Claimed by Processes 5 3 2 2
Remaining Unclaimed 1 0 2 0

Resources Still Needed
Processes Tapes Plotters Printers Toasters
A 1 1 0 0
B 0 1 1 2
C 3 1 0 0
D 0 0 1 0
E 2 1 1 0
The vectors E, P and A represent Existing, Possessed and Available resources respectively:
E = (6, 3, 4, 2)
P = (5, 3, 2, 2)
A = (1, 0, 2, 0)
Notice that

A = E - P
Now, to state the algorithm more formally, but in essentially the same way as the example with
Andy, Barb, Marv and Sue:
1. Look for a row whose unmet needs don’t exceed what’s available, that is, a row where
P <= A; if no such row exists, we are deadlocked because no process can acquire the
resources it needs to run to completion. If there’s more than one such row, just pick one.

2. Assume that the process chosen in 1 acquires all the resources it needs and runs to
completion, thereby releasing its resources. Mark that process as virtually terminated and
add its resources to A.

3. Repeat 1 and 2 until all processes are either virtually terminated (safe state), or a deadlock
is detected (unsafe state).
Going thru this algorithm with the foregoing data, we see that process D’s requirements are
smaller than A, so we virtually terminate D and add its resources back into the available pool:
E = (6, 3, 4, 2)
P = (5, 3, 2, 2) - (1, 1, 0, 1) = (4, 2, 2, 1)
A = (1, 0, 2, 0) + (1, 1, 0, 1) = (2, 1, 2, 1)
Now, A’s requirements are less than A, so do the same thing with A:
P = (4, 2, 2, 1) – (3, 0, 1, 1) = (1, 2, 1, 0)
A = (2, 1, 2, 1) + (3, 0, 1, 1) = (5, 1, 3, 2)

At this point, we see that there are no remaining processes that can’t be satisfied from available
resources, so the illustrated state is safe.

LOVELY PROFESSIONAL UNIVERSITY 115