GATE CS 2018 Q.49 (CS Q.39): Deadlock Prevention, Avoidance and Detection

In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2,F] is the maximum number of instances of F that P2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.

Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.

Process	Allocation E	Allocation F	Allocation G	Max E	Max F	Max G
P0	1	0	1	4	3	1
P1	1	1	2	2	1	4
P2	1	0	3	1	3	3
P3	2	0	0	5	4	1

From the perspective of deadlock avoidance, which one of the following is true?

The system is in safe state.

The system is not in safe state, but would be safe if one more instance of E were available

The system is not in safe state, but would be safe if one more instance of F were available

The system is not in safe state, but would be safe if one more instance of G were available

Official answer and solution

Official answer: A
From: Official GATE 2018 answer key

Solution

Compute the Need matrix and execute Banker's safety algorithm to discover a valid execution sequence.

Calculate $\text{Need} = \text{Max} - \text{Allocation}$ for each process:

$\text{Need}(P_0) = [4 - 1, 3 - 0, 1 - 1] = [3, 3, 0]$
$\text{Need}(P_1) = [2 - 1, 1 - 1, 4 - 2] = [1, 0, 2]$
$\text{Need}(P_2) = [1 - 1, 3 - 0, 3 - 3] = [0, 3, 0]$
$\text{Need}(P_3) = [5 - 2, 4 - 0, 1 - 0] = [3, 4, 1]$

Currently Available resources: $\text{Available} = [3, 3, 0]$ .
Trace safety sequence:

Process $P_0$ requires $[3, 3, 0] \le [3, 3, 0]$ . $P_0$ can finish and release its allocation $[1, 0, 1]$ .
$\text{New Available} = [3, 3, 0] + [1, 0, 1] = [4, 3, 1]$ .
Process $P_2$ requires $[0, 3, 0] \le [4, 3, 1]$ . $P_2$ can finish and release its allocation $[1, 0, 3]$ .
$\text{New Available} = [4, 3, 1] + [1, 0, 3] = [5, 3, 4]$ .
Process $P_1$ requires $[1, 0, 2] \le [5, 3, 4]$ . $P_1$ can finish and release its allocation $[1, 1, 2]$ .
$\text{New Available} = [5, 3, 4] + [1, 1, 2] = [6, 4, 6]$ .
Process $P_3$ requires $[3, 4, 1] \le [6, 4, 6]$ . $P_3$ can finish.

Since a complete safe sequence $\langle P_0, P_2, P_1, P_3 \rangle$ exists, the system is in a safe state, matching option A.

Final answer

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

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 49 of 65, printed as CS Q.39
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