GATE 2018 CS Q.39: solution and answer

GATE 2018 · CSQ.39 · 2 marks · MCQ

In a system, there are three types of resources: $E$ , $F$ and $G$ . Four processes $P_{0}, P_{1}, P_{2}$ and $P_{3}$ execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, $Max [P_{2}, F]$ is the maximum number of instances of $F$ that $P_{2}$ 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.

Allocation: $P_{0} P_{1} P_{2} P_{3} E 1112 F 0100 G 1230$

Max: $P_{0} P_{1} P_{2} P_{3} E 4215 F 3134 G 1431$

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

GATE 2018 CS question 39: Two side-by-side 4x3 tables. — Figure from the GATE 2018 CS paper. It is part of the question.

(A)
The system is in safe state.
(B)
The system is not in safe state, but would be safe if one more instance of $E$ were available
(C)
The system is not in safe state, but would be safe if one more instance of $F$ were available
(D)
The system is not in safe state, but would be safe if one more instance of $G$ were available

Answer and solution

ANSWER

The system is in a safe state, with safe sequence $P_{0}, P_{2}, P_{1}, P_{3}$ . Option (A).

Official answer: ASource: Official answer key, GATE 2018 CS (IIT Guwahati)

The question says only 3 instances of $E$ and 3 instances of $F$ are available, so the available vector is $(E, F, G) = (3, 3, 0)$ .
Need $=$ Max $-$ Allocation: $P_{0} P_{1} P_{2} P_{3} E 3103 F 3034 G 0201$
Banker's safety check, starting with $Work = (3, 3, 0)$ . $P_{0}$ needs $(3, 3, 0) \leq (3, 3, 0)$ , so it can finish. Then $Work = (3, 3, 0) + (1, 0, 1) = (4, 3, 1)$ .
$P_{1}$ needs $(1, 0, 2)$ , but only 1 instance of $G$ is free, so it must wait. $P_{2}$ needs $(0, 3, 0) \leq (4, 3, 1)$ , so it finishes. Then $Work = (4, 3, 1) + (1, 0, 3) = (5, 3, 4)$ .
Now $P_{1}$ needs $(1, 0, 2) \leq (5, 3, 4)$ and finishes. Then $Work = (5, 3, 4) + (1, 1, 2) = (6, 4, 6)$ .
$P_{3}$ needs $(3, 4, 1) \leq (6, 4, 6)$ and finishes. Then $Work = (6, 4, 6) + (2, 0, 0) = (8, 4, 6)$ .
The safe sequence $P_{0}, P_{2}, P_{1}, P_{3}$ exists, so the state is safe. Option (A) is true. Options (B), (C) and (D) each say the state is not safe, so they are false.

KEY IDEA

Deadlock avoidance with the Banker's algorithm. Compute Need $=$ Max $-$ Allocation, then repeatedly pick any process whose Need is at most Work, let it finish and add its Allocation back. If every process can finish, the state is safe.

WATCH OUT FOR

Forgetting that no instance of $G$ is free, and treating Available as $(3, 3, 3)$ or reading the allocations as the available amounts. Another slip is starting with $P_{1}$ , whose need of 2 instances of $G$ cannot be met until $P_{0}$ releases its resources.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 6 Deadlock questions, with notes

GATE 2018 CS Q.39: solution and answer

Answer and solution

More Deadlock questions