A computer system uses the Banker’s Algorithm to deal with deadlocks. Its…
1996
A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.
a) Show that the system can be in this state. b) What will the system do on a request by process P0 for one unit of resource type R1?
- A.
The current state is safe; one safe sequence is P1 → P2 → P0. If P0 requests one unit of R1, the request should not be granted immediately because the tentative state is unsafe.
- B.
The current state is safe; one safe sequence is P1 → P2 → P0. If P0 requests one unit of R1, the request can be granted immediately and the same safe sequence still works.
Attempted by 7 students.
Show answer & explanation
Correct answer: A
Treat the left table as the maximum-claim matrix. The current allocation matrix and available vector are given in the table.
Need = Maximum − Allocation:
P0: (4, 1, 2) − (1, 0, 2) = (3, 1, 0)
P1: (1, 5, 1) − (0, 3, 1) = (1, 2, 0)
P2: (1, 2, 3) − (1, 0, 2) = (0, 2, 1)
Initially, Available = (2, 2, 0). Since P1's need (1, 2, 0) is at most Available, P1 can finish and release (0, 3, 1), giving Available = (2, 5, 1). Now P2 can finish and release (1, 0, 2), giving Available = (3, 5, 3). Finally P0 can finish. Hence the current state is safe, with safe sequence P1 → P2 → P0.
Now suppose P0 requests one unit of R1, i.e. Request0 = (0, 1, 0). This request is within P0's remaining need and is also available, so we test the resulting state. After tentative allocation:
Available = (2, 1, 0)
Need(P0) = (3, 0, 0)
Need(P1) = (1, 2, 0)
Need(P2) = (0, 2, 1)
With Available = (2, 1, 0), none of P0, P1, or P2 can complete. Therefore the tentative state is unsafe, so the Banker's Algorithm will not grant P0's request immediately.