in Operating System edited by
11,580 views
21 votes
21 votes

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?

  1. The system is in $safe$ state
  2. The system is not in $safe$ state, but would be $safe$ if one more instance of $E$ were available
  3. The system is not in $safe$ state, but would be $safe$ if one more instance of $F$ were available
  4. The system is not in $safe$ state, but would be $safe$ if one more instance of $G$ were available
in Operating System edited by
by
11.6k views

4 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>$

2
2
Safe.
0
0
edited by

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.$

2
2
P1's need should be 1 0 2
0
0

3 Answers

26 votes
26 votes
Best answer
$$ \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$
edited by

4 Comments

Thanks!!
1
1
you can do the TOPOLOGICAL sorting of the DFST to find the number of possible sequences.
0
0
Please elaborate how to find number of possible sequences here?
0
0
0 votes
0 votes
A is correct ans
0 votes
0 votes

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.

edited by
Answer:

Related questions