GATE CSE 1994 | Question: 28

Question

Consider the resource allocation graph in the figure.

• A. Find if the system is in a deadlock state

• B. Otherwise, find a safe sequence

Comments

Important point to note:

For single resource system cycle in resource allocation graph is necessary and sufficient condition for deadlock.

For multi resource system, cycle in resource allocation graph is necessary (else there will be no circular wait) but not sufficient condition for deadlock. We need to apply Banker's algorithm to see if we can get a safe sequence.

---

You can start by comparing indegrees and outdegrees of resource nodes.

Answer 1

From the RAG we can make the necessary matrices.

$$\overset{\text{Allocation}}{\begin{array}{|l|l|l|l|}\hline \text{} & r_1 &r_2 & r_3 \\ \hline P_0 & \text{1} & \text{0} & \text{1} \\\hline  P_1 & \text{1} & \text{1} & \text{0} \\\hline  P_2 & \text{0} & \text{1} & \text{0} \\\hline   P_3& \text{0} & \text{1} & \text{0} \\\hline \end{array}}\qquad \overset{\text{Future Need}}{\begin{array}{|l|l|l|l|}\hline \text{} &r_1 & r_2 & r_3 \\ \hline P_0 & \text{0} & \text{1} & \text{1} \\\hline  P_1 & \text{1} & \text{0} & \text{0} \\\hline  P_2 & \text{0} & \text{0} & \text{1} \\\hline  P_3 & \text{1} & \text{2} & \text{0} \\\hline \end{array}}$$

• $\text{Total}=(2\quad 3\quad 2)$
• $\text{Allocated}=(2\quad 3\quad 1)$
• $\text{Available}=\text{Total} -\text{Allocated} =(0\quad 0\quad 1)$

$P_2's$ need $(0\quad 0\quad 1 )$ can be met

And it releases its held resources after running to completion

$A=(0\quad 0\quad 1)+(0\quad 1\quad 0)=(0\quad 1\quad 1)$

$P_0's$ need $(0\quad 1\quad 1 )$ can be met

and it releases
$A=(0\quad 1\quad 1)+(1\quad 0\quad 1)=(1\quad 1\quad 2)$

$P_1's$ needs can be met $(1\quad 0\quad 0)$ and it releases
$A=(1\quad 1\quad 2)+(1\quad 1\quad 0)=(2\quad 2\quad 2)$

$P_3's$ need can be met
So, the safe sequence will be $P_2-P_0- P_1- P_3.$

Comments

@hira If no process meets requirement then we are in an unsafe state. An unsafe state may lead to deadlock.

(deadlock is subset of unsafe state). Sometimes it may not lead to deadlock.  But if there is a safe sequence we are sure that it will never lead to deadlock.

https://defuse.ca/blog/why-unsafe-state-deadlock.html

---

A valuable information.

---

@Hira Thakur If deadlock then state has to be unsafe but not the other way. Deadlock is subset of unsafe state.

Answer 2

a) The system is not in deadlock state as there exists a safe sequence.

b)  P₂ P₀ P₁ P₃  is a safe sequence.