Question 16 on Deadlock

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

(A) X : P(a) P(b) P(c)    Y : P(b) P(c) P(d)   Z : P(c) P(d) P(a)
(B) X : P(b) P(a) P(c)    Y : P(b) P(c) P(d)   Z : P(a) P(c) P(d)
(C) X : P(b) P(a) P(c)    Y : P(c) P(b) P(d)   Z : P(a) P(c) P(d)
(D) X : P(a) P(b) P(c)    Y : P(c) P(b) P(d)   Z : P(c) P(d) P(a)

Answer: (B)

Explanation :
To solve this problem, we need to go through each of the options and check if they can create a deadlock at any point of their executions.

(A) X : P(a) P(b) P(c)    Y : P(b) P(c) P(d)   Z : P(c) P(d) P(a)
Lets assume X starts the process and executes P(a) and then Y executes P(b) and Z executes P(c). Now, X can not go forward because Y has a lock on b, and Y cannot go forward and execute P(c) because Z holds a lock on c. Now, the only process that can go forward is Z, so it executes P(d). But it cannot go further and execute P(a) because X holds the lock a. Now all the three processes cannot go ahead as they dependency on each other. Thus this method of access creates deadlocks.

(C) X : P(b) P(a) P(c)    Y : P(c) P(b) P(d)   Z : P(a) P(c) P(d)
Lets assume X starts processing with P(b) and then executes P(a). And then Y picks up P(c) and then waits on b to execute P(b) because b is locked by X -- where as X cannot go forward because it needs to execute P(c) but it was locked by Y. So, there is cleat cycle of dependencies between X and Y causing a deadlock situation.

We can also find a deadlock situation involving all of three processes as well. X executes P(b), Y executes P(c) and Z executes P(a). X cannot go forward now because Z holds the lock on a. Z cannot go forward and execute P(c) because Y holds lock on c. Similarly, Y cannot go ahead and execute P(b) because X holds lock c. As you can see, this is a deadlock situation. Also, clearly it also has circular cycle of dependencies.

(D) X : P(a) P(b) P(c)    Y : P(c) P(b) P(d)   Z : P(c) P(d) P(a)
Similar to option C, this also has a deadlock problem. X executes P(a) and P(b) and Y executes P(c). X cannot go forward now because c is locked by Y and Y cannot go forward because b is already locked by X, thus causing a deadlock situation between X & Y.

Apart from this other deadlock situations can also be found (e.g., X & Z in the circular loop waiting for lock on c and a respectively).

(B) X : P(b) P(a) P(c)    Y : P(b) P(c) P(d)   Z : P(a) P(c) P(d)
In this situation, we cannot find any deadlock. So, this is our answer.

Topics to revise
Semaphores
Deadlocks

References