Skip to content
GATETECH
Official PYQ · 2018Q39DeadlockMCQ2 marks

GATE CS 2018 Q39 — Deadlock

Explain with AI

In a system, there are three types of resources: E,FE, F and GG. Four processes P0P_0, P1P_1, P2P_2 and P3P_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[P2,FP_2, F] is the maximum number of instances of FF that P2P_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 33 instances of EE and 33 instances of FF are only resources available.

AllocationEFGP_0101P_1112P_2103P_3200MaxEFGP_0431P_1214P_2133P_3541\begin{array}{|l|}\hline \textbf{Allocation} \\ \hline & \text{E} & \text{F} & \text{G} \\ \hline \text{$P\_0$} & \text{1} & \text{0} & \text{1} \\ \hline \text{$P\_1$} & \text{1} & \text{1} & \text{2}\\ \hline \text{$P\_2$} & \text{1} & \text{0} & \text{3}\\ \hline \text{$P\_3$} & \text{2} & \text{0} & \text{0}\\ \hline \end{array} \begin{array}{|l|}\hline \textbf{Max} \\ \hline & \text{E} & \text{F} & \text{G} \\ \hline \text{$P\_0$} & \text{4} & \text{3} & \text{1} \\ \hline \text{$P\_1$} & \text{2} & \text{1} & \text{4}\\ \hline \text{$P\_2$} & \text{1} & \text{3} & \text{3}\\ \hline \text{$P\_3$} & \text{5} & \text{4} & \text{1}\\ \hline \end{array}

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

Choose one option
View worked solution

Answer: A

To determine if the system is in a safe state, we first calculate the Need matrix using the formula:

Need=Max−Allocation\text{Need} = \text{Max} - \text{Allocation}

Let's compute the Need for each process:

  • Need[P0]=[4,3,1]−[1,0,1]=[3,3,0]\text{Need}[P_0] = [4, 3, 1] - [1, 0, 1] = [3, 3, 0]
  • Need[P1]=[2,1,4]−[1,1,2]=[1,0,2]\text{Need}[P_1] = [2, 1, 4] - [1, 1, 2] = [1, 0, 2]
  • Need[P2]=[1,3,3]−[1,0,3]=[0,3,0]\text{Need}[P_2] = [1, 3, 3] - [1, 0, 3] = [0, 3, 0]
  • Need[P3]=[5,4,1]−[2,0,0]=[3,4,1]\text{Need}[P_3] = [5, 4, 1] - [2, 0, 0] = [3, 4, 1]

The initial available resources are: Available=[3,3,0]\text{Available} = [3, 3, 0].

We can find a safe sequence by checking which processes can satisfy their needs with the current available resources:

  1. Step 1: Both P0P_0 and P2P_2 have needs that can be satisfied by the available resources [3,3,0][3, 3, 0]. Let's execute P0P_0 first.
    After P0P_0 finishes and releases its resources: Available=[3,3,0]+[1,0,1]=[4,3,1]\text{Available} = [3, 3, 0] + [1, 0, 1] = [4, 3, 1]
  2. Step 2: Now, only P2P_2 can be satisfied because Need[P2]=[0,3,0]≤[4,3,1]\text{Need}[P_2] = [0, 3, 0] \le [4, 3, 1].
    After P2P_2 finishes and releases its resources: Available=[4,3,1]+[1,0,3]=[5,3,4]\text{Available} = [4, 3, 1] + [1, 0, 3] = [5, 3, 4]
  3. Step 3: Now, P1P_1 can be satisfied because Need[P1]=[1,0,2]≤[5,3,4]\text{Need}[P_1] = [1, 0, 2] \le [5, 3, 4].
    After P1P_1 finishes and releases its resources: Available=[5,3,4]+[1,1,2]=[6,4,6]\text{Available} = [5, 3, 4] + [1, 1, 2] = [6, 4, 6]
  4. Step 4: Finally, P3P_3 can be satisfied because Need[P3]=[3,4,1]≤[6,4,6]\text{Need}[P_3] = [3, 4, 1] \le [6, 4, 6].
    After P3P_3 finishes and releases its resources: Available=[6,4,6]+[2,0,0]=[8,4,6]\text{Available} = [6, 4, 6] + [2, 0, 0] = [8, 4, 6]

Since a complete safe sequence ⟨P0,P2,P1,P3⟩\langle P_0, P_2, P_1, P_3 \rangle exists, the system is in a safe state.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Deadlock questions