GATE CS 2014 Set 1 Q.41 (CS Q.31): Deadlock Prevention, Avoidance and Detection

An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.

Process	Alloc X	Alloc Y	Alloc Z	Max X	Max Y	Max Z
P0	0	0	1	8	4	3
P1	3	2	0	6	2	0
P2	2	1	1	3	3	3

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

Only REQ1 can be permitted.

Only REQ2 can be permitted.

Both REQ1 and REQ2 can be permitted.

Neither REQ1 nor REQ2 can be permitted.

Official answer and solution

Official answer: B
From: Official GATE 2014 answer key

Solution

Apply Banker's Resource-Request algorithm to test whether REQ1 and REQ2 leave the system in a safe state.

Initial State:

Available: $X = 3, Y = 2, Z = 2$
Allocation:
- $P_0: (0, 0, 1)$
- $P_1: (3, 2, 0)$
- $P_2: (2, 1, 1)$
Max:
- $P_0: (8, 4, 3)$
- $P_1: (6, 2, 0)$
- $P_2: (3, 3, 3)$
Need = Max - Allocation:
- $\text{Need}(P_0) = (8, 4, 2)$
- $\text{Need}(P_1) = (3, 0, 0)$
- $\text{Need}(P_2) = (1, 2, 2)$

Test REQ1: $P_0$ requests $(0, 0, 2)$ :

$\text{Request} \le \text{Need}(P_0)$ : $(0, 0, 2) \le (8, 4, 2)$ (valid).
$\text{Request} \le \text{Available}$ : $(0, 0, 2) \le (3, 2, 2)$ (valid).
Tentative state:
- $\text{Available} = (3, 2, 2) - (0, 0, 2) = (3, 2, 0)$
- $\text{Need}(P_0) = (8, 4, 0)$ , $\text{Alloc}(P_0) = (0, 0, 3)$
Check safety:
- $\text{Need}(P_1) = (3, 0, 0) \le (3, 2, 0) \implies P_1$ finishes.
  $\text{Available} = (3, 2, 0) + (3, 2, 0) = (6, 4, 0)$ .
- Next, check $P_2$ : $\text{Need}(P_2) = (1, 2, 2) \not\le (6, 4, 0)$ because Available has $Z = 0$ .
- Check $P_0$ : $\text{Need}(P_0) = (8, 4, 0) \not\le (6, 4, 0)$ because Available has $X = 6 < 8$ .
  No other process can finish! System is in an unsafe state.
  Thus REQ1 CANNOT be permitted.

Test REQ2: $P_1$ requests $(2, 0, 0)$ :

$\text{Request} \le \text{Need}(P_1)$ : $(2, 0, 0) \le (3, 0, 0)$ (valid).
$\text{Request} \le \text{Available}$ : $(2, 0, 0) \le (3, 2, 2)$ (valid).
Tentative state:
- $\text{Available} = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)$
- $\text{Need}(P_1) = (1, 0, 0)$ , $\text{Alloc}(P_1) = (5, 2, 0)$
Check safety:
- $\text{Need}(P_1) = (1, 0, 0) \le (1, 2, 2) \implies P_1$ finishes.
  $\text{Available} = (1, 2, 2) + (5, 2, 0) = (6, 4, 2)$ .
- $\text{Need}(P_2) = (1, 2, 2) \le (6, 4, 2) \implies P_2$ finishes.
  $\text{Available} = (6, 4, 2) + (2, 1, 1) = (8, 5, 3)$ .
- $\text{Need}(P_0) = (8, 4, 2) \le (8, 5, 3) \implies P_0$ finishes.
  A safe sequence $\langle P_1, P_2, P_0 \rangle$ exists!
  Thus REQ2 CAN be permitted.

Therefore, only REQ2 can be permitted.

Final answer

Common trap

Testing requests together instead of treating them as independent requests from the initial state.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 41 of 65, printed as CS Q.31
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source