Multiple choice

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 initialised 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)$
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Suppose X performs P(2) and preempts, Y gets chance, but cannot do its first wait, i.e. P(2), so waits for X, now Z gets the chance and performs P(1) and preempts, next X gets chance. X cannot continue as wait on ‘a’ is done by Z already, so X waits for Z. At this time, Z can continue its operations as down on c and d. Once Z finishes, X can do its operations and so Y. In any of the execution orders of X, Y and Z, one process can continue and finish, such that waiting is not circular. In options (1), (3) and (4), we can easily find circular wait and thus, deadlock.

Keep practicing — related questions