edited by
16,989 views
57 votes
57 votes

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)$
edited by

8 Answers

Best answer
66 votes
66 votes

For deadlock-free invocation, $X, Y$ and $Z$ must access the semaphores in the same order so that there won't be a case where one process is waiting for a semaphore while holding some other semaphore. This is satisfied only by option B. 

In option A, $X$ can hold a and wait for $c$ while $Z$ can hold $c$ and wait for $a$
In option C, $X$ can hold $b$ and wait for $c,$ while $Y$ can hold $c$ and wait for $b$
In option D, $X$ can hold $a$ and wait for $c$ while $Z$ can hold $c$ and wait for $a$

So, a deadlock is possible for all choices except B. 

http://www.eee.metu.edu.tr/~halici/courses/442/Ch5%20Deadlocks.pdf

edited by
57 votes
57 votes

Find crossings like above.

9 votes
9 votes

Explanation: Option A can cause deadlock. Imagine a situation process X has acquired a, process Y has acquired b and process Z has acquired c and d. There is circular wait now.

Option C can also cause deadlock. Imagine a situation process X has acquired b, process Y has acquired c and process Z has acquired a. There is circular wait now.

Option D can also cause deadlock. Imagine a situation process X has acquired a and b, process Y has acquired c. X and Y circularly waiting for each other.

See http://www.eee.metu.edu.tr/~halici/courses/442/Ch5%20Deadlocks.pdf

Consider option A) for example here all 3 processes are concurrent so X will get semaphore a, Y will get b and Z will get c, now X is blocked for b, Y is blocked for c, Z gets d and blocked for a. Thus it will lead to deadlock.

Similarly one can figure out that for B) completion order is Z,X then Y.

4 votes
4 votes

A) 

cycle- 'a' is held by X. X requests for 'b' which is held by Y. Y requests for 'd' which is held by Z. Z requests for 'a' which is held by X

similarly option C, D will have cycle but not option B

Answer:

Related questions