edited by
4,335 views
12 votes
12 votes
  • Consider two processes, P and Q, each need three records, R1, R2. and R3, in a database. If P asks for them in any order R1, R2, R3, and Q asks for them in any order, What fraction of all the combinations are guaranteed to be deadlock free?
    1.   $\frac{1}{3}$
    2.   $\frac{2}{3}$
    3.   $\frac{1}{6}$
edited by

3 Answers

Best answer
16 votes
16 votes

Let the resources 

$\left ( R1,R2,R3 \right ) = \left ( 1,2,3 \right )$

Suppose A requests the resources in the order $\left ( 1,2,3 \right )$

and B can request the resources in any order $\left \{\left ( 1,2,3 \right ) (1,3,2) (2,1,3)(2,3,1)(3,1,2)(3,1,2) \right \}$

When Deadlock May Occur ?

  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 2,1,3 \right )$
  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 2,3,1 \right )$
  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 3,1,2 \right )$
  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 3,2,1 \right )$

When there is NO possibility of Deadlock ?

  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 1,2,3 \right )$
  • $A=\left ( 1,2,3 \right )$ ; $B=\left ( 1,3,2 \right )$

Hence, for 6 possible combinations for $A=\left ( 1,2,3 \right )$ , only 2 combinations are there which can never lead to Deadlock.

So, Required Fraction = $\frac{2}{6}$ = $\frac{1}{3}$

selected by
7 votes
7 votes

process A requests the records in the order 1, 2, 3. If process B also asks for a first, one of them will get it and the other will block. This situation is always deadlock free since the winner can now run to completion without interference. Of the four other combinations, some may lead to deadlock and some are deadlock free.

The six cases are as follows:

123: deadlock free

132: deadlock free

213: possible deadlock

231: possible deadlock

312: possible deadlock

321: possible deadlock

Since four of the six may lead to deadlock, there is a 1/3 chance of avoiding a deadlock and a 2/3 chance of getting one

https://www.doc.ic.ac.uk/~etheresk/deadlocks-tutorial-sol.pdf

2 votes
2 votes

Please lemme know where I'm wrong. 

  • P has 3! ways to request. Q has 3! ways to request. Therefore total request combinations for the system = 36. 
  • Out of 36, deadlock isn't possible when the combinations are alike. e.g (R1,R2,R3) for both P & Q. Such combinations are = 6. 
  • Therefore fraction = 6/36 = 1/6. 
edited by

Related questions

5 votes
5 votes
4 answers
2
Prateek Dwivedi asked Jun 27, 2015
31,399 views
This is a question from Operating System concepts by Silberschatz, Gagne and Galvin. On very first go I could make that in such a situation deadlock can never occur. But ...
0 votes
0 votes
2 answers
3
Himani Srivastava asked Oct 10, 2015
1,387 views
P0wait(s); wait(q);Signal (s); signal(q);...P1[wait(q);wait(s);}signal(q);signal(s);....whether progress is guarnteed or not ???