4.3k views

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 | 4.3k views

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.

selected by
0
I think this link has moved to a different server.

0
+3
this question is a deadlock question based on semaphore, rt?

a,b,c,d are initialized to 1 , we can think like

A)X        Y          Z

P(a)       P(b)       P(c)

P(b)       P(c)       P(d)

P(c)        P(d)      P(a)

V(a)         V(b)     V(c)

V(b)         V(c)      V(d)

V(c)         V(d)       V(a)
0
@Arjun Sir, Please explain in more detail.. I am not understanding this concept of deadlock in semaphores. Please suggest a book or online source for learning this concept. The link u have shared is broken.

As in above question, in all options, processes X, Y, Z are performing P() operation on all the three mutexes. So deadlock should occur in all. Isnt? Then how difference in ordering will make difference? Please explain in more detail
0
@srestha I am finding that I will use your logic than no one has deadlock condition.
0
In option B, X can hold b and wait for a while Z can hold a and wait for c

Find crossings like above.

0
There is no logic . Even in B there may be crosses
+6

Since ,all semaphores are binary.

And we have to check possiblity of deadlock.

Deadlock will occur when we have some resource and waiting for other resource held by other process and that too is waiting for our resource.

In above example,finding crossing means there is cycle and if there is cycle there will be deadlock because all resources have only one instance (here resource means binary semaphores).

In fig.for example in 1. option, a acquire lock X ,and c Acquire lock z,now c is waiting for x and a is waiting for z.

so ,there is deadlock.similarly in other examples except 2.

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.

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.

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

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
+1
Thqq all

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

1