gate zeal cse pdf

Question

Consider the four mutex locks L1, L2, L3, and L4. Two processes A and B request these four locks. Each process requests them in some (possibly different) pre programmed sequence. There are 24 possible sequences for requesting the locks making for 576 programming possibilities. How many of these can possibly result in a deadlock?

Answer 1

Approach: Trying this by negative approach, where we'll first count all the ways we can avoid deadlock and the subtract it from total cases.

Now, consider this scenario.
 

Process A

L1

X

X

X

 

 

Process B

L1

X

X

X

Note: X here means "don't care"

This is one of the instance of cases where deadlocks are avoided. This happens when, both the processes ensure that the first lock they have requested is the same one, as long as this is true, there will be no deadlock.
So this can be done in 4*3!*3! ways. How? For both the processes, first lock must be same henceforth. there are 4 ways to choose the first lock (L1,L2,L3,L4). Then the 3 remaining slots in both processes, can be filled by any permutation of the remaining 3 locks which gives the factor of 3!*3!.
Now, 4*3!*3! = 144.
and 576 - 144 = 432.
432 should be the answer.