7.5k views

Consider a system with $4$ types of resources $R1$ ($3$ units), $R2$ ($2$ units), $R3$ ($3$ units), $R4$ ($2$ units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes $P1$, $P2$, $P3$ request the resources as follows if executed independently.

$$\begin{array}{|l|l|l|}\hline \textbf{Process P1:} & \textbf{Process P2:} & \textbf{Process P3:} \\ \hline \text{t=0: requests 2 units of R2} & \text{t=0: requests 2 units of R3} & \text{t=0: requests 1 unit of R4} \\ \text{t=1: requests 1 unit of R3} & \text{t=2: requests 1 unit of R4} & \text{t=2: requests 2 units of R1}\\\text{t=3: requests 2 units of R1} & \text{t=4: requests 1 unit of R1} & \text{t=5: releases 2 units of R1} \\ \text{t=5: releases 1 unit of R2} & \text{t=6: releases 1 unit of R3} & \text{t=7: requests 1 unit of R2} \\ \text{and 1 unit of R1}& \text{t=8: Finishes} & \text{t=8: requests 1 unit of R3}\\ \text{t=7: releases 1 unit of R3} && \text{t=9: Finishes} \\ \text{t=8: requests 2 units of R4} & \text{} \\ \text{t=10: Finishes} & \text{} \\ \hline \end{array}$$
Which one of the following statements is TRUE if all three processes run concurrently starting at time $t = 0$?

1. All processes will finish without any deadlock

2. Only $P1$ and $P2$ will be in deadlock

3. Only $P1$ and $P3$ will be in deadlock

4. All three processes will be in deadlock

edited | 7.5k views
0
Here process P1 will not get 2 units of R4 at the end of completion. which is the correct ans?
0
It means sir there are 2 type of resource allocation graph .1. preemptive resource alloction. 2 .Non preemptive resource allocation

I solved it like and got a wrong solution.

R1  R2  R3  R4(allocation)             R1  R2  R3   R4 (request)

P1  0      1    1      0                               3     2      1       2

P2  0      0     1    0                                1       0      2     1

P3  2     0     0     0                                 2      1       1    1

R1 ,R2,R3,R4 have  3,2,3,2 units of resources and 2,1,2,0 are allocated now available are 1,1,1,2 and with the help of 1,1,1,2 we can not fulfill requirment of any request.

At $t = 3$, the process $P1$ has to wait because available $R1=1$, but $P1$ needs $2 \ R1$. so $P1$ is blocked.

Similarly, at various times what is happening can be analyzed by the table below.

$$\begin{array}{l|l|l|l|l|l} \text{} & \text{} & \text{R1(3)} & \text{R2(2)} & \text{R3(3)} & \text{R4(2)} \\\hline \text{} & \text{t=0} & \text{3} & \text{0} & \text{1} & \text{1}\\ \text{} & \text{t=1} & \text{3} & \text{0} & \text{0} & \text{1} \\ \text{} & \text{t=2} & \text{1} & \text{0} & \text{0} & \text{0}\\ \ \text{Block P1} & \text{t=3} & \text{1} & \text{0} & \text{0} & \text{0}\\ \text{} & \text{t=4} & \text{0} & \text{0} & \text{0} & \text{0}\\ \text{Unblock P1} & \text{t=5} & \text{1} & \text{1} & \text{0} & \text{0} \\ \text{} & \text{t=6} & \text{1} & \text{1} & \text{1} & \text{0}\\ \text{} & \text{t=7} & \text{1} & \text{0} & \text{2} & \text{0}\\ \text{Block P1} & \text{t=8} & \text{2} & \text{0} & \text{2} & \text{1}\\ \text{Unblock P1} & \text{t=9} & \text{2} & \text{1} & \text{3} & \text{0}\\ \text{} & \text{t=10} & \text{} & \text{} & \text{} & \text{} \\\hline \end{array}$$
There are no processes in deadlock, hence (A) is right choice 🙂

edited
0

For those who have doubt that how would $P_1$ get $2$ units of resource $R_4 \Rightarrow$

$\text{ At t=8 and t=9, P1 and P2 will be completed and hence will release R4 automatically}$

$\text{i.e 1 unit of R4 will be released from P2 and 1 unit from P2 and hence there is no deadlock }$

+1
nice explanation @ sachin mittal sir
+1
at t=2 p2 is requesting 1R4 that requirnment is not full fill till end so how p2 can finish its execution before fullfilling his requirnment
+1
Sir can you please explain how can Process P1 release 1unit of R1 at t=5 if P1 has no instance of R1?
+1
How can i  Show the Table Because some Entries Value I do not know How can i ? Explain Elaborted..
+2

Bhagyashree Mukherje, because at t=5 p3 is also releasing 2 units of r1. by which p1 can up and release one unit of r1 after acquiring 2 unit.

@Vijay Dulam, at each time what is happening with resources we are just writing those in table and each time information is availabel in question.

+1
Oh ok.thanku @shubhgupta
0

"Non-preemptive resource allocation policy is used". It means processes can be preempted but resources cannot. And here resources are not being preempted at any instance of time.

0
And here in this qstn , No Hold and Wait condition .. so P1 hold some resorce and wait for some is not possible so no deadlock

how? why not hold and wait?
0

@  ma'am

A non-preemptive resource allocation policy is used.

i think this line make it not use hold and wait.

Can be solved by making respective tables for each process at different time instances.
0
how explain ??

"At any given instance, a request is not entertained if it cannot be completely satisfied", means no wait. so, deadlock isn't possible.

Here hold and wait voilated so there will not be deadlock
+1 vote
At=3,available R1=1,but P1 needs 2 R1.
so,P1 is blocked.
At t=5, 3R1 are released,but previously blocked P1 takes 2 R1
to unblock it.so available R1=1.
At t=8, P2 finishes,so it will releases what it grabbed.
From the process P2 column in question we can
see it releases 1 R1,1R3 and 1R4,but at the same time P1 wants
2 R4 but available is just 1.so P1 is blocked.P3 wants 1 R3 ,it can
be fulfilled.
At t=9,P3 finishes ,it releases 1 R2,1 R3,1 R4.So now previously blocked P1
can be unblocked
At t=10,All finishes.

So at last none of the processes are blocked.
So,All processes will finish without deadlock.
0
Someone please give the solution on paper

1
2