The Gateway to Computer Science Excellence
+5 votes
1.2k 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.

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

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

4 Answers

+4 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 $
by Boss (10.5k 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!.
0
Why 3? Shouldn't it be 2*6!/3!∗3!=240? as 2 cases for P2 for 1 case of P1 for the system to be deeadlock free?
+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
by Veteran (116k 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.

+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

+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
by Active (2.3k points)
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

by Active (2.2k points)
0
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
50,666 questions
56,167 answers
193,838 comments
94,018 users