The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x

Deadlock

+5 votes
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 ________.

Given answer is 6.

I am getting 12.

asked in Operating System by Active (1.5k points) | 1k views
0
+1

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

5 Answers

+3 votes
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
answered by Veteran (111k points)
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

@magma how this combination will not lead to deadlock

  • 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

@srestha

@Shaik Masthan

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

+3 votes
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 $
answered by Boss (10.1k points)
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
now check hyperlinked 'this.'
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
answered by Active (2.2k points)
0 votes

Answer : 180 Ways

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

Ways which lead to Deadlock Free Execution :

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.

answered by Boss (24.9k points)
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.

0 votes

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

When Deadlock May Occur ?

  • 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

answered by Active (2.1k points)
0

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,576 questions
54,182 answers
187,506 comments
71,144 users