edited by
33,674 views
67 votes
67 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

edited by

10 Answers

94 votes
94 votes

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.$$\small \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 by
49 votes
49 votes

Answer A is correct but the method by which people (in other answers on this question) have gotten A is Not correct.


People are NOT even considering this statement in the question : "Three processes P1, P2, P3 request the resources as follows if executed independently."

In question it is given that If Each Process executed Independently (independent of other processes) then those processes will execute and request resources as given by the given sequence for each process.  

What this means is that : Say In the system, Only P1 is executing, then P1 will do these things : At $t=0,$ it will request 2 instances of resource $R2$ ;  At $t=1,$ it will request 1 instances of resource $R3$ ; At $t=3,$ it will request 2 instances of resource $R1$ ; then After using $R1$ for $two$ time units and after using $R2$ for $five$ units of time, At $t=5,$ it will release 1 instance of resource $R1$ and 1 instance of resource $R2.$ And so on.... 

Hence, according to question, The Given sequence of resource request/release for a process is followed by that process $if \,\, it \,\, executed \,\, independently.$ 

So, If $P1$ acquires two instances of  resource $R1$ at time $t$ then It will release one instance of $R1$ at time $t+2 $ After using $R1$ for two time units.  

Now, we can proceed to solve the question :


Since at any instance of time, three processes are concurrently running, We can assume that there are three processors ($C1,C2,C3$) in the system and Process $Pi$ is executing on processor/core $Ci.$ (This assumption is only for making things easy to understand and It is without loss of generality so even if one doesn't want to assume it then also fine, answer and method won't change .)


In the beginning, $R1 = 3, R2 = 2, R3 = 3, R4 = 2$

Now, Processes are executing (their given sequence of resource/relases) concurrently.

At $t=0 :$ 

$P1,P2,P3$ will without any problem acquire what they requested, so after $t=0$, we have  $R1 = 3, R2 = 0, R3 = 1, R4 = 1$

At $t=1 :$  

$P1$ will acquire what it requested, so after $t=1$, we have  $R1 = 3, R2 = 0, R3 = 0, R4 = 1$

At $t=2 :$ 

$P2,P3$ will without any problem acquire what they requested, so after $t=2$, we have  $R1 = 1, R2 = 0, R3 = 0, R4 = 0$

At $t=3 :$ 

$P1$ requests two units of $R1$ But we only have one unit of $R1$ free in the system, so this request can't be satisfied completely, so $P1$ will have to wait and it will be blocked when two instances of $R1$ becomes available. 

It is worth noting that whenever $P1$ will acquires these two units of $R1$, It will use them for 2 units of time and then after that it will release one instance of $R1.$

So, After $t=3$, we have  $R1 = 1, R2 = 0, R3 = 0, R4 = 0$

At $t=4 :$ 

$P2$ will without any problem acquire what it requested, so after $t=4$, we have  $R1 = 0, R2 = 0, R3 = 0, R4 = 0$

At $t=5 :$ 

$P3$ will put an instruction to release two units of $R1$, at this moment, system will assign these two units of $R1$ to $P1$ and wake it up. So after $t=5$, we have  $R1 = 0, R2 = 0, R3 = 0, R4 = 0$

Now, Since $P1$ has gotten two units of $R1$ at time $t=5,$ It will execute its next instruction of resource request/release at time $t=7$ (after using $R1$ for two units of time as It would have done if it executed independently because that is how the program of the process has been written)   So, whole code/sequence of resource request/release of process $P1$ has shifted/delayed by 2 units of time. So, at this moment, we must consider that what it was doing at $t=5$ if it was executing independently, now it will do that at $t=7$ when executing concurrently. 

At $t=6 :$ 

$P2$ releases one unit of $R3$, so after $t=6$, we have  $R1 = 0, R2 = 0, R3 = 1, R4 = 0$

At $t=7 :$ 

$P1$ release one unit of $R1,R2$, And $P3$ requests one unit of $R2$ which it will be granted since $P1$ has released one unit of $R2$ (No matter P1 runs first(slightly..in nano-seconds maybe) or P3 runs first... P3 will get what it requested after t=7.  If P1 releases R2 slightly before P3 requests then P3 will get it.. But if P3 requests slightly before P1 releases then P3 will block for some fraction of time unit and then p1 will put an instruction to release R2 so system will assign it to blocked P3 and wake it up )

So after $t=7$, we have  $R1 = 1, R2 = 0, R3 = 1, R4 = 0$

At $t=8 :$ 

$P3$ will without any problem acquire what it requested,  and $P2$ will finish so it will release all its acquired resources, So after $t=8$, we have  $R1 = 2, R2 = 0, R3 = 1, R4 = 1$

At $t=9 :$ 

$P3$ will finish and $P1$ will release 1 unit of $R3$, So after $t=9$, we have  $R1 = 2, R2 = 1, R3 = 3, R4 = 2$

At $t=10 :$ 

$P1$ will without any problem acquire what it requested, so after $t=10$, we have  $R1 = 2, R2 = 1, R3 = 3, R4 = 0$

At $t=11 :$ 

Something internal happening of P1.

At $t=12 :$ 

$P1$ will finish, so after $t=12$, we have  $R1 = 3, R2 = 2, R3 = 3, R4 = 2$


Hence, All Processes will execute/finish without any deadlock. Answer is A.


PS :

1. Many are giving argument that  "No hold and wait so there will not be deadlock" ..This is wrong. Nowhere in the question it is mentioned that Hold and wait isn't there. Some students are wrongly inferring that No Hold and wait from this line in the question "At any given instance, a request is not entertained if it cannot be completely satisfied." This statement only wants to say that If process $P1$ requested 2 instances of $R1$ at any point of time and say only one instance is available then the system won't assign one instance that is free to $P1$ because Unless the request is $completely$ satisfies, it won't be entertained. 

Hold and wait condition says "A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes." Clearly there is Hold and wait in this system because When $P1$ requested 2 units of $R1,$ one instance of $R1$ was being held by $P3$ so $P1$ was waited for $R1$ to become available. 

2. If you disagree with any part in this answer, let me know and we'll discuss that in comments.

19 votes
19 votes

using resource allocation graph

P1's request isn't fulfilled. P1 goes to blocked state for R1=1. at this point P1 wont release any resources as well. P1 can continue only when 1 instance of R1 is available

P2's request isn't fulfilled so it can't proceed. P2 goes to blocked state. P2 waits for R1=1
at T=4, both P1 and P2 are in blocked/wait state

P3 releases 2 instances of R1. Both P1 ad P2 were waiting for R1=1 and R1=1. Now both the processes can be allocated resources. P1 and P2 both goes to ready state

When P1 goes to ready state, it'll simultaneously release one instance of R1 and 1 instance of R2

P2 finishes and releases its resources. P3's request is fulfilled. P1 goes to blocked/wait state for R4=1

P3 finishes and releases the resources it held. Now P1 will come out of blocked state(P1 was waiting for R4=1)

P1 continues execution

at T=10, P1 finishes execution and releases all the resources it held

R1=3, R2=2, R3=3, R4=2
the system is in safe state and there is no deadlock

sequence of execution of process is P2->P3->P1

edited by
8 votes
8 votes

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

Answer:

Related questions