1
$\begingroup$

I found this question in the exercise of Tanenbaum (operating systems):

Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the order $(1, 2, 3)$ and $B$ asks for them in the same order, deadlock is not possible. However, if B asks for them in the order $(3, 2, 1)$ then deadlock is possible. With three resources, there are $3!=6$ possible combinations each process can request resources. What fraction of all combinations is guaranteed to be deadlock free?

I haven't gotten any farther than that there are $6$ possible ways that $B$ can request: $(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$

Please help me out.

$\endgroup$
1
  • $\begingroup$ Do you understand the examples in the questions? $\endgroup$
    – Raphael
    Nov 18, 2018 at 11:24

1 Answer 1

0
$\begingroup$

Let's assume for simplicity that A and B take 5 seconds to request for the next resource and B starts requesting for resources 1 second after A's request.

  • If A requests for 1 first and B requests for either 2/3 first, it will create a deadlock. This happens because when A requests for either 2/3 it will be blocked and B will be blocked when it requests for 1. So both processes will block each other and in turn will be blocked by each other.

  • If A and B both request for 1, then A wins out and B will be blocked. So there will be no deadlock.

So the entire problems rests on B's choices. Therefore $\frac{1}{3}$rd of the cases will be deadlock free.

$\endgroup$
1
  • 2
    $\begingroup$ The question does not specify that $A$ have to retain resource 1 all along. So it is possible that for B (1,3,2) to enter a deadlock. So only B(1,2,3) is deadlock free. $\endgroup$
    – John L.
    Aug 20, 2018 at 10:58

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .