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.

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

1 Answer 1


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.

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.