The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
1.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) | 1.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 (112k points)
0
But the number of resoruces are 3 only those are 1, 2 and 3. And from 3 res we have total 6 permutation. And for each Permutation of A, B also have 6 permutation. So total there are 36 order of request.

And among them only 12  does not leads to deadlock.
0
No, it is told like this

each process need 3 resource and resource are numbered
0

No matter how we select the minimum resources for deadlock-free execution from the total set of resources available we are going to have a deadlock-free selection?! Let say there are m resources in total and we need a minimum of n resources for a deadlock-free execution, then the number of possible ways to get a deadlock-free execution is: mCn

I am just trying to find a faster solution. Am I right?

0

MrPeppermint

1) If extra useless resources are available?

       let say R1 has 5 instances, R2 has 3 instances, R3 has 2 instances... but P1 and P2 just need only R1 and R2 then your formula going to be wrong...

2) if required useful resources are less than requirement?

 let say R1 has 3 instances, R2 has 4 instances, R3 has 10 instances... but P1 and P2 just need only R1-4 instances and R2-5 with then your formula going to be wrong...

3)  if R1 has m instances, P1 requires r resources of R1, P2 requires s resources of R2,....

   assume r+s-1 < m then your formula going to be wrong... actually it has only one possible way 

0

@Shaik I am talking about the combinations of the minimum number of resources required for a deadlock-free solution.

1) If there are extra useless resources available such that need <<< available, then there will be no deadlock and we can have more combinations.

2) I think you meant if required resources < available. Obviously, processes will never be executed.

3) How many resources does R2 have? P1 can complete its execution. P2 can complete its execution if s <= the instances of R2 . It'll never be a deadlock though since P1 and P2 need different resource types.

0

1) If there are extra useless resources available such that need <<< available, then there will be no deadlock and we can have more combinations.

   How there will be more combinations? how useless resources participate? i mean only useful resources are participated in the combination. 

2) I think you meant if required resources < available. Obviously, processes will never be executed.

  i know the process will never be executed. but your formula getting evaluated and give some no.

3) typing mistake in my comment on 3rd point ...  if R1 has m instances, P1 requires r resources of R1, P2 requires s resources of R1,....  assume r+s-1 < m then your formula going to be wrong... actually it has only one possible way  where r+s-1 is the minimum no.of resources needed for dead-lock free but your formula evaluating something else right?

0

1) Each process needs 2 resources:

P1: R11 R12

P2: R21 R22

Minimum number of resources for a deadlock-free execution = 1 + 1 + 1 = 3

Okay, I was wrong. The formula will be mCn where m = total requirement of the resources by the processes and n is the minimum resources needed for deadlock free execution. Also, check n <= total available resources.

Combinations:

R11....R21 R22

....R12 R21 R22

R11 R12...R22

R11 R12 R21.....

4C3 = 4

2) Obviously, one will not approach further with the question when one can see that the resource requirement itself fails.

Requirement = 4 + 5 = 9 < Available = 3 + 4 = 7

3) You can have only 2 combinations for the same resource types(obvious). Either P1 executes or P2 executes. Minimum resources for a deadlock-free execution is r+s-1. Here the combinations = number of processes available.

Thanks. I cleared my mistake.

0
According to me, there are 180 such Ways. Kindly cross check my answer.
+1

I read all the comments but I'm not come with the single solution and didn't know which answer is correct
In made-easy test series given that  "120" is correct answer
here I read many comments come with a  different ideas with different solution .

So, what is the correct answer of this ??

acc to me

let the Resources

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

Suppose A request the resources in the order (1,2,3)

and B can request the resources in any order (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,2,1) (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.

therefore there are (3! X 2) = 12  combination possibible

 

 

0

 

here's the solution

0
@srestha how can you assume that number of resources available are atleast 5 for a deadlock free execution? there could be 3 resources also that are present. Nothing is told in the question about the number of resources that are available in the system.
0
No, cannot be 3

because say P1 takes 2 resource and P2 takes 1 resource

then there is a possibility of deadlock

because min resource requirement of any process is 3
0

How is this question different from the question stated below in this link: https://gateoverflow.in/89309/consider-two-processes-p-and-q-each-need-three-records

What should be the solution if the question would have been the one that is specified in the link above?

0
that is totally different question of ordering
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 (25k 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,811 questions
54,530 answers
188,404 comments
75,484 users