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

4 votes
4 votes

I will try to answer this in a very simple and short way, as most answer explained quiet beautifully and in details.

If you are familiar with the deadlock concept, then I will explain why the correct answer is B. Automatically you will understand why others cannot be correct answer.

GIVEN : Binary semaphore means value is 0 or 1. If P(s) has s=1, we proceed or else we are blocked. Here, in question all a,b,c,d is initialized as 1. X,Y and Z are concurrent process, so can run parallel to each other (we will use this).

Solution : See option B, For the process to complete all P operations should be passed.

  •  X:P(b) and Y:P(b) executed one after the other. Proceeds only when both executed.
  • Next, X:P(a) and Z:P(a) executed one after the other.
  • Next, X:P(c) and Y:P(c) executed one after the other.  [See, here X is completed]
  • Y:P(d) and Z:P(d) completed one after the other. [Y and Z completed]

So, as you can see how in option B, all the semaphores are executed one after the other and did not wait for any other semaphore to be be executed by any other process.

 

edited by
3 votes
3 votes
for no deadlock three condition must be satisfy in cs problem-

1-mutual exclusive-at a time only one process is execute its cs

2-progressing-means for eg 3 process in which 2 are not intrest to excute its cs and at same time  3rd is wants to enter then its excute cs.

3-bounded waiting-means waiting time for any process is finite no longer

all condition are satisfy only in B therefore option is B.
0 votes
0 votes

Correct Answer - Option 2 :X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)
Answer: Option 2

Explanation: 

Given

Process X will perform down operation on a, b, c
Process Y will perform down operation on b, c, d
Process Z will perform down operation on c, d, a

all the binary semaphores initialized to 1.

Option 1: X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)

Consider the following sequence 

X: P(a)    // a = 0
Y: P(b)   // b = 0
Z: P(c)   // c = 0
X: P(b)   // unsuccessful down operation hence X will be blocked.
Y: P(c)   // again unsuccessful down operation hence Y will be blocked.
Z: P(d)   // d=0
Z: P(a)   // unsuccessful down operation hence Z will be blocked.

Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 2: X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

In this Order, you execute in any sequence deadlock not possible. Hence this is the correct Option.

Option 3: X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)

X: P(b)   // b = 0 
Y: P(c)   // c = 0 
Z: P(a)   // a = 0 
X: P(a)   // unsuccessful down operation hence X will be blocked.
Y: P(b)   // again unsuccessful down operation hence Y will be blocked.
Z: P(c)   // unsuccessful down operation hence Z will be blocked.

Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 4: X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

X: P(a)   // a = 0
Y: P(c)   // c = 0
Z: P(c)   // unsuccessful down operation hence Z will be blocked.
X: P(b)   // b = 0
Y: P(b)   // unsuccessful down operation hence Y will be blocked.
X: P(c)   //  unsuccessful down operation hence X will be blocked. 

Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Answer:

Related questions