duplicate of https://gateoverflow.in/220031/deadlock

The Gateway to Computer Science Excellence

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

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

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.

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.

+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

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

And among them only 12 does not leads to deadlock.

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: ^{m}C_{n}

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 R_{2} have? P1 can complete its execution. P2 can complete its execution if s <= the instances of R_{2} . 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: R_{11} R_{12}

P2: R_{21} R_{22}

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

Okay, I was wrong. The formula will be ^{m}C_{n} 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:

R_{11}....R_{21} R_{22}

....R_{12} R_{21} R_{22}

R_{11} R_{12}...R_{22}

R_{11} R_{12} R_{21}.....

^{4}C_{3} = 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

@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

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

But the language of the question is the same. Can you please explain how are these two questions different? :(

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

@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 !

+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

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

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

0

you copied Kapil's Answer from https://gateoverflow.in/89309/consider-two-processes-p-and-q-each-need-three-records

This is not a good practice!

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,838 comments

94,018 users