The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 votes

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

asked in Operating System by Veteran (59.8k points)
edited by | 7.5k views
Here process P1 will not get 2 units of R4 at the end of completion. which is the correct ans?
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.

5 Answers

+41 votes
Best answer

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 🙂

answered by Boss (17.4k points)
edited by

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

nice explanation @ sachin mittal sir
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
Sir can you please explain how can Process P1 release 1unit of R1 at t=5 if P1 has no instance of R1?
How can i  Show the Table Because some Entries Value I do not know How can i ? Explain Elaborted..

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.

Oh ok.thanku @shubhgupta

@Adwaith S

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

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?

 @  ma'am 

 A non-preemptive resource allocation policy is used.

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

+6 votes
The answer is A.

Can be solved by making respective tables for each process at different time instances.
answered by Boss (19.9k points)
how explain ??
+6 votes

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

answered by Active (2.9k points)
+4 votes
Here hold and wait voilated so there will not be deadlock
answered by (441 points)
+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 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 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. 
answered by Active (4k points)
Someone please give the solution on paper

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,403 questions
53,576 answers
70,852 users