251 views
0 votes
0 votes

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

1 Answer

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

Related questions

1 votes
1 votes
1 answer
1