Three concurrent processes X, Y, and Z execute three different code segments…
20132013
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)
Attempted by 110 students.
Show answer & explanation
Correct answer: B
Key idea: Prevent deadlock by ensuring every process acquires semaphores in the same global order (so circular wait cannot occur).
From X: P(b)P(a)P(c) we get b < a < c.
From Y: P(b)P(c)P(d) we get b < c < d.
From Z: P(a)P(c)P(d) we get a < c < d.
Combining these relations gives a consistent global order b < a < c < d. Because every process acquires semaphores in increasing order according to this global ordering, no circular wait can form and the system is deadlock-free for this ordering of P operations.
A video solution is available for this question — log in and enroll to watch it.