in Operating System recategorized by
19,469 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

in Operating System recategorized by
19.5k views

2 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.
5
5
You can start by comparing indegrees and outdegrees of resource nodes.
0
0

4 Answers

45 votes
45 votes
Best answer

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

4 Comments

A valuable information.
0
0

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

0
0
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’s 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.
1
1
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 vote
1 vote

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