Question

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?
1. X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)
2. X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)
3. X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)
4. X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

Answer 1

Correct Answer - Option 2 : X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

Answer: Option 2

Explanation: 

Given

Process X will perform down operation on a, b, c

Process Y will perform down operation on b, c, d

Process Z will perform down operation on c, d, a

all the binary semaphores initialized to 1.

Option 1: X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)

Consider the following sequence 

X: P(a)    // a = 0

Y: P(b)   // b = 0

Z: P(c)   // c = 0

X: P(b)   // unsuccessful down operation hence X will be blocked.

Y: P(c)   // again unsuccessful down operation hence Y will be blocked.

Z: P(d)   // d=0

Z: P(a)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 2: X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

In this Order, you execute in any sequence deadlock not possible. Hence this is the correct Option.

Option 3: X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)

X: P(b)   // b = 0 

Y: P(c)   // c = 0 

Z: P(a)   // a = 0 

X: P(a)   // unsuccessful down operation hence X will be blocked.

Y: P(b)   // again unsuccessful down operation hence Y will be blocked.

Z: P(c)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 4: X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

X: P(a)   // a = 0

Y: P(c)   // c = 0

Z: P(c)   // unsuccessful down operation hence Z will be blocked.

X: P(b)   // b = 0

Y: P(b)   // unsuccessful down operation hence Y will be blocked.

X: P(c)   //  unsuccessful down operation hence X will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.