1k views

Consider two processes P1 and P2, each needed 3 resources 1, 2 and 3 in a database. If each processes ask them in any order, then the number of ways  possible in which system is guaranteed to be deadlock free ________.

I am getting 12.

0
+1

This is totally absurd. Made Easy showed me a different answer and explanation for this question.

yes it will be 6

Given $2$ process, and each need $3$ resource and also given resource number $1,2,3$

Now, to get deadlock free execution of all $2$ process , we need minimum 2+2+1=5 resources

Say for process $1$ resource number $R_{11},R_{12},R_{13}$

and for process $2$ resource number $R_{21},R_{22},R_{23}$

So, number of ways possible

$R_{11},R_{12},......,R_{21},R_{22},R_{23}$

$R_{11},R_{12},R_{13},R_{21},R_{22},......$

$R_{11},......,R_{13},R_{21},R_{22},R_{23}$

$R_{11},R_{12},R_{13},R_{21},.......,R_{23}$

$.......,R_{12},R_{13},R_{21},R_{22},R_{23}$

$R_{11},R_{12},R_{13},.......,R_{22},R_{23}$

There 6 ways we can select 5 resource from total 6 resource
0
But the language of the question is the same. Can you please explain how are these two questions different? :(
0
See Akriti comment in that ques
0
Ok.. But here what does 1,2,3 indicate? Are these the resource numbers(like R1,R2,R3) or are they the total number of resources that are available?
0

Shaik Masthan  HOW THESE ORDERS ARE WRITTEN ???

0
I also didn't get this question !
0
OK
0

• A=(1,2,3);  B=(1,3,2)
• suppose A has finished executing 1 and holding 2 , now when A finished executing 1 then B came and finished executing 1 and then holding 3 and waiting for 2 .. so it leads to deadlock as A is now holding 2 and waiting for  3 and B is holding 3 and waiting for 2 ... correct me if wrong  !
0
Sir, How come there are 5 resources?

There are only 3 mentioned resource..
0

pls chk this also

case 1 : when p1 and p2 access resources in increasing order that is 1,2,3:-

ways = 6C3 = 20 ways

case2 : when p1 and p2 access resources in dec order that is 3,2,1

ways = 6C3 =20 ways

total ways =20+20=40 ways

0

case 1 : when p1 and p2 access resources in increasing order that is 1,2,3:-

ways = 6C3 = 20 ways

HOW , 6C3 plz explain in detail

120 is the right answer ,

since there are three resources but instances of resources is not given so we can't assume anything about instances .we can allocate them in$3!$=6 ways

so for deadlock free ,we have to give resources in same order to both process like ${P_1:R_1\; R_2\;R_3\;} and \; P_2:R_1\; R_2\;R_3\;$ both should be in same order then there is possibility of deadlock but we can permute them in $\frac{6!}{3!*3!}=20$

so we can run them in same order only so there are 5 more order in which we can allocate resources to processes

${P_1:R_2\; R_1\;R_3\;} and \; P_2:R_2\; R_1\;R_3\;$ so we permute this also in 20 ways

${P_1:R_2\; R_3\;R_1\;} and \; P_2:R_2\; R_3\;R_1\;$ so we permute this also in 20 ways

${P_1:R_3\; R_1\;R_3\;} and \; P_2:R_3\; R_1\;R_2\;$ so we permute this also in 20 ways

${P_1:R_3\; R_2\;R_1\;} and \; P_2:R_3\; R_2\;R_1\;$ so we permute this also in 20 ways

${P_1:R_1\; R_3\;R_2\;} and \; P_1:R_1\; R_3\;R_2\;$ so we permute this also in 20 ways

$total\; no.\; ways=120$
0
we can permute them in 6!3!∗3!=20

plz explain.....
0
total are 6 so 6! but  for p1 and p2 resources order can't be permute means r1-->r2-->r3 , we cant permute these ,they only can arrive in same order so we have to divide 3! for p1 and as well as for p2 also.

for example:r1-->(r1-->r2-->r3)-->r2-->r3. this is one permutation out of 20 ,in bracket p2 process there.
0

According to this solution which is true there should be $3*\frac{6!}{2!*2!}=540$. Think on this and please reply back.

0

i am not getting  3∗6!/2!∗2!=540

0
0
thanks , i got the point

why dividing with 3!3!.
+1 vote
Consider:
If P1 requests for R1, then P2 can only request for R2 or R3, for instance assume P2 requested for R3 first, then now P1 can only request for R2, and now both processes can acquire the remaining resources in the order they are released by the holding process,
therefore, when P1 requests for any of the 3 resources then there are two possibilities for P2 in each case.
total possibilities= 2+2+2=6

Two processes Pand P2, each needed 3 resources 1, 2 and 3 in a database.

Question asks " If each processes ask them $in \,\,any \,\,order$, then the number of ways  possible in which system is guaranteed to be deadlock free ".

Total Ways :

Though, There are $6!$ ways to ask for the three resources.

$(P_1,1),(P_1,2),(P_1,3),(P_2,1),(P_2,2),(P_2,3)$   // Where $(P_i,r)$ means process $P_i$ requests/asks for resource $r$.

Let's go step by step, in a well formed procedure :

1. When, in the first three requests, Exactly Three requests are of $P_1$ i.e. When $P_1$ requests all the three resources Before $P_2$ :

i.e. $(P1,1), (P1,2), (P1,3)$ before  $(P2,1), (P2,2), (P2,3)$

So, We have $3! \times 3! = 36 \,\,ways$. All will be Deadlock Free.

2. When, in the first three requests, Exactly Zero request is of $P_1$ i.e. When $P_2$ requests all the three resources Before $P_1$ :

Similar to case $1$, We again  have $3! \times 3! = 36 \,\,ways$. All will be Deadlock Free.

3. When, in the first three requests, Exactly one request is of $P_1$ :

($3_1$) : When the very first request is of $P_1$ :

In this Case ($3_1$), Deadlock will Definitely Occur. So, $0$ deadlock free way.

($3_2$) : When the very second request is of $P_1$ :

Say, $(P_1,x)$ is the second request. then, for deadlock free execution, $(P_2,x)$ has to be the first request. And the third request could be either $(P_2,y)$ or $(P_2,z)$. So, we will have $18$ different possible ways for Deadlock free execution.

($3_3$) : When the very third request is of $P_1$ :

In this case ($3_3$), Say, $(P_1,x)$ is the third request. then, for deadlock free execution, $(P_2,x)$ has to be either the first request or the second request. So, we will have $18$ different possible ways for Deadlock free execution for each possibility of $(P_2,x)$. Hence, $2 \times 18 = 36$ Ways for Deadlock free execution in this case.

3. When, in the first three requests, Exactly Two requests are of $P_1$ :

This is Equivalent to saying "When, in the first three requests, Exactly one request is of $P_2$" .. So, It will be similar to the $case 3$ and Total ways for Deadlock free execution will be $54$.

So, Adding all the ways for Deadlock free execution, We will have $36 + 36 + 54 + 54 = 180$ Ways.

0
minimum 3 resource can be there to be the system to be deadlock free, but that is not guaranteed.

So, we take min 5 resource to guaranteed to be deadlock free
0

and

In this Case (31), Deadlock will Definitely Occur. So, 0 deadlock free way.

why so?

0

Say, (P1,x) is the second request. then, for deadlock free execution, (P2,x) has to be the first request. And the third request could be either (P2,y) or (P2,z). So, we will have 18 different possible ways for Deadlock free execution.

P3 also can come first rt?

0

@Deepakk Poonia (Dee)
Can this be thought like this :
If $P_{1}$ will first finish using all the $3$ resources and after that $P_{2}$ then deadlock will not occur.
So, $P_{1}$ will request every resource before $P_{2}$ does.

$P_{1} \left (a \right ) \rightarrow P_{2} \left ( a\right)$
$i.e.$ request for resource $a$  by $P_{1}$ comes before $P_{2}$ in which ever ordering we choose and same for other resources.

Let the resources

(R1,R2,R3)=(1,2,3)(R1,R2,R3)=(1,2,3)

Suppose P1 requests the resources in the order (1,2,3)(1,2,3)

and P2 can request the resources in any order {(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,1,2)}{(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,1,2)}

• P1=(1,2,3) ; P2=(2,1,3)
• P2=(1,2,3);  P2=(2,3,1)
• P3=(1,2,3) ; P2=(3,1,2)
• P4=(1,2,3) ; P2=(3,2,1)

When there is NO possibility of Deadlock ?

• A=(1,2,3) ; B=(1,2,3)
• A=(1,2,3);  B=(1,3,2)

Hence, for 6 possible combinations for p1=(1,2,3), only 2 combinations are there which can never lead to Deadlock.

Also we can calculate similarly for next 6 combination of p1 answer wil be 12 or 36/3=12.

similar question ref

https://gateoverflow.in/89309/consider-two-processes-p-and-q-each-need-three-records

0

This is not a good practice!