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 (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 (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?

Accepted Answer

The correct answer is (B) X: P(b)P(a)P(c)   Y: P(b)P(c)P(d)   Z: P(a)P(c)P(d). Deadlock is avoided (Havender's ordering technique) if there's a single global order of the 4 semaphores such that every process acquires its needed semaphores in an order consistent with it. Option B's acquisition orders — X: b<a<c, Y: b<c<d, Z: a<c<d — are all simultaneously consistent with the single global order b<a<c<d, so no circular wait can form. The other options each require contradictory relative orderings between some pair of semaphores across two processes (e.g. option A needs both a<b<c<d from X/Y and a>d from Z's c,d,a order), so a global consistent order doesn't exist for them — permitting a circular wait/deadlock.

Explanation