Three concurrent processes, X, Y and Z execute three different

Home » Operating Systems » Operating systems miscellaneous » 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)

Correct Option: B

Three concurrent processes X, Y and Z execute three different code segments that access and update certain shared variables.

(a) X : P(a) P(b) P(c)
Y : P(b) P(c) P(d)
Z : P(c) P(d) P(a)
Suppose X first executes P(a) and P(b) and then switches to process Z, where P(c) and P(d) are executed and wait for P(a), Then again process switches to X and then wait for P(c).
∴ Process X is waiting for C which is occupied by Z and Z is waiting for a which is occupied by process X. So, neither can execute and deadlock occurs. (Not Acceptable)
(b) X : P(b) P(a) P(c)
Y : P(b) P(c) P(d)
Z : P(a) P(c) P(d)

Execution can be carried out in a proper way without deadlock occurance and no wait for any variable in the processer. (Acceptable)
(c) X : P(b) P(a) P(c)
Y : P(c) P(b) P(d)
Z : P(a) P(c) P(d)

The sequence of variable P(b) and P(c) are reverse and opposite [i.e., P(b) P(c) P(a) and P(a) P(b) P(c)] So, deadlock may occurs in X and Y respectively (Not Acceptable)
(d)
X : P(a) P(b) P(c)
Y : P(c) P(b) P(d)
Z : P(c) P(d) P(a)

The sequence of variable P(c) and P(a) are opposite in Z and X. So, deadlock may occur (Not Acceptable) Hence, the answer is (b).