# What fraction of all combinations is guaranteed to be deadlock free?

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.

• Do you understand the examples in the questions? – Raphael Nov 18 '18 at 11:24

## 1 Answer

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.

• 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. – Apass.Jack Aug 20 '18 at 10:58