The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.5k 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?

(A) $X:$ $P(a)P(b)P(c)$ $Y:$ $P(b)P(c)P(d)$ $Z:$ $P(c)P(d)P(a)$
(B) $X:$ $P(b)P(a)P(c)$ $Y:$ $P(b)P(c)P(d)$ $Z:$ $P(a)P(c)P(d)$
(C) $X:$ $P(b)P(a)P(c)$ $Y:$ $P(c)P(b)P(d)$ $Z:$ $P(a)P(c)P(d)$
(D) $X:$ $P(a)P(b)P(c)$ $Y:$ $P(c)P(b)P(d)$ $Z:$ $P(c)P(d)P(a)$

asked in Operating System by Veteran (346k points)
retagged by | 2.5k views

4 Answers

+33 votes
Best answer

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

answered by Veteran (346k points)
selected by
I think this link has moved to a different server.

Arjun Sir, Please check and replace the link.
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)
@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
@srestha I am finding that I will use your logic than no one has deadlock condition.
In option B, X can hold b and wait for a while Z can hold a and wait for c
+16 votes

Find crossings like above.

answered by Loyal (3.8k points)
There is no logic . Even in B there may be crosses

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.

 

+4 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.

answered by Boss (8.4k points)
+2 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.
answered by Junior (983 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,022 comments
38,389 users