recategorized by
19,575 views
34 votes
34 votes

Consider the resource allocation graph in the figure.

  1. Find if the system is in a deadlock state

  2. Otherwise, find a safe sequence

recategorized by

4 Answers

Best answer
45 votes
45 votes

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

edited by
13 votes
13 votes

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

b)  P2 P0 P1 Pis a safe sequence.

1 votes
1 votes

From the RAG, we can see that only 1(r3) is free. P0 and P2 are contesting for 1(r3).

Now we have 0(r1) and 0(r2) and 1(r3) available.

 

If we give 1(r3) to P0, it will be still waiting for 1(r2).

If we give 1(r3) to P2, it will execute and release 1(r2) and 1(r3).

 

P2 needs 1(r3), so it will execute and release 1(r2) additionally.

Now we have 0(r1) and 1(r2) and 1(r3) available.

 

P0 needs 1(r2) and 1(r3), so it will execute and release 1(r3) and 1(r1) additionally.

Now we have 1(r1) and 1(r2) and 2(r3) available.

 

No one wants any instance of r3.

 

P1 needs 1(r1), so it will execute and release 1(r1) and 1(r2) additionally.

Now we have 2(r1) and 2(r2) and 2(r3) available.

 

P3 needs 1(r1) and 2(r2), so it will execute and release 1(r2) additionally.

Now we have 2(r1) and 3(r2) and 2(r3) available.

 

As long as I am able to find a way to execute all the processes in some order without being stuck, I can say my system is in safe state, and there exists a safe sequence [for example P2=>P0=>P1=>P3 in this case]

0 votes
0 votes
The Banker’s algorithm is a systematic and time-consuming process. For this question, we can do it with observation through eyes only. The intuition should be that all the resources of each class are held by processes except one, which is still available at R3, for which 2 processes are competing. But if P0 acquires it, still P0 will not progress since one more resource of R2 is needed by it. So we can allocate this resource at r3 to P2 and if there’s a safe sequence then it must begin with P2. So let us simulate P2’s execution post which it will vacate one resource from R2. Like this, it can be solved through intuition rather than applying rigorous Banker’s algorithm which is time taking and prone to silly mistakes.

Related questions

3 votes
3 votes
1 answer
4
gatecse asked May 3, 2021
2,323 views
State whether the following statements are True or False with reasons for your answer:A two pass assembler uses its machine opcode table in the first pass of assembly.