GATE CSE 2018 | Question: 39

Question

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 only resources available.

$$ \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?

• 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

Comments

CESS	ALLOCATION	MAXIMUM	NEED	AVAILABLE
P0	1           0          1	4          3           1	3            3             0	3        3           0
P1	1           1          2	1          1           2	2             0            2	4        3           1
	1           0          3	1           0          3	0             3            0	5         3          4
P3	2          0           0	2           0          0	3             4            1	6         4         6

 

Safe State: $<P0, P2, P1, P3>$

---

Safe.

---

Available$:<E,F,G> = \:<3,3,0>$

Total number of safe sequences$:$

• Start with $P_{0}:$ Safe sequences$:\:<P_{0},P_{2},P_{1},P_{3}>$
• Start with $P_{1}:$ Can not be possible, because $'G'$ needs $2$ resources and initially, we have $0$ resources.
• Start with $P_{2}:$  Safe sequences$:\:<P_{2},P_{1},P_{0},P_{3}>,\:<P_{2},P_{1},P_{3},P_{0}>$ and $<P_{2},P_{0},P_{1},P_{3}>$
• Start with $P_{3}:$ Can not be possible, because $'F'$ needs $4$ resource and initially we have only $3$ resources and $'G'$ needs $1$ resources and initially, we have $0$ resources.

So, the total number of safe sequences possible $= 4.$

---

P1's need should be 1 0 2

Answer 1

$$ \begin{array}{|l|}\hline \textbf{Allocation}   \\\hline\text{Process}  & \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{Process}& \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} \begin{array}{|l|}\hline \textbf{Need=Max-Allocation}   \\\hline\text{Process}& \text{E} & \text{F} & \text{G}  \\\hline  \text{$P_0$} & \text{3} & \text{3} & \text{0} \\\hline  \text{$P_1$} & \text{1} & \text{0}  & \text{2}\\\hline  \text{$P_2$} & \text{0} & \text{3}  & \text{0}\\\hline  \text{$P_3$} & \text{3} & \text{4}  & \text{1}\\\hline \end{array}$$

Available Resource $[E,F,G] = $  $(3,3,0)$
With $(3,3,0)$ we can satisfy the request of either $P_0$ or $P_2$.

Let's assume request of $P_0$  satisfied.
After execution, it will release resources.
Available Resource $=(3,3,0) + (1,0,1) = (4,3,1)$

Give $(0,3,0)$ out of $(4,3,1)$ unit of resources to $P_2$ and $P_2$ will completes its execution.
After execution, it will release resources.
Available Resource $=(4,3,1)+(1,0,3) =(5,3,4)$

Allocate $(1,0,2)$ out of $(5,3,4)$ unit of resources to $P_1$ and $P_1$ will completes its execution.
After execution, it will release resources.
Available Resource $=(5,3,4)+(1,1,2) = (6,4,6)$
And finally, allocate resources to $P_3$.

So, we have one of the possible safe sequence: $P_0\longrightarrow P_2\longrightarrow P_1\longrightarrow P_3$

Correct Answer: $A$

Comments

Sir, Available Resource =(5,3,4)+(1,1,2)=(6,4,6)

---

done :)

---

If they ask number of safe sequences possible, how can we find it??

---

Where was the available resource given in this question?

---

@chirudeepnamini

@Satbir

@ankitgupta.1729

hey,

With $(5,3,4)$ the needs of $\mathbf{P_1}\;\text{and}\;\mathbf{P_2}$ both can be completed.

So, what to choose between them.

Can I choose anyone or is there any rule for this??

---

@`JEET

I think there is no strict rule on how to select a process but i have read some where that we scan the table from top to bottom and satisfy the requirement of first process we encounter which can be satisfied by available resources.

---

Thanks!!

---

you can do the TOPOLOGICAL sorting of the DFST to find the number of possible sequences.

---

Please elaborate how to find number of possible sequences here?

Answer 2

A is correct ans

Answer 3

PROCESS	ALLOCATION	MAXIMUM	NEED	AVAILABLE
P0	1           0          1	4          3           1	3            3              0	3        3            0
P1	1           1          2	1          1           2	2             0             2
P2	1           0          3	1           0          3	0             3             0
P3	2          0           0	2           0          0	3             4             1

---

 (3,3,0) we can satisfy the request of either P0 or P2.

If we take P0 then 
we have (4,3,1)

---

 now, take P2  then we have (5, 3, 4)

---

now, take  P1 then we have (6, 4,6) 

---

now, allocate all resources to P3

---

execution order will be P0----->P2------.>P1-------->P3

and given system is in the safe state 

option a is the correct answer.