How to write deadlock free operation using Semaphore P(S) and V(S)

Question

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.

How to write deadlock-free order of invoking the P operations by the processes if options are not there.?

https://gateoverflow.in/1438/gate2013-16

 

Answer 1

Trial and error. I tried this:

X: P(a), P(b), P(c)

Y: P(b), P(d), P(c)

Z: P(a), P(d), P(c)

Check the above. I didn't find any error in it.

Now as per Arjun Sir's answer let's examine option B there:

X: P(b), P(a), P(c)

Y: P(b), P(c), P(d)

Z: P(a), P(c), P(d)

He said to try to access the semaphores in the same order in X, Y and Z. See the semaphores common in X and Y: b & c. See that P(b) occurs first then P(c) in both of them. Check X & Z: a &c. See that P(a) occurs first then P(c). Check Y & Z: c & d. See that P(c) occurs first then P(d). Now check the ordering in my solution. I did it using trial and error basically. Arjun Sir's explanation comes to rescue.

Comments

On second thought. Consider this situation:

X:  P(b) , P(a) ,   P(c)

Y:  P(b) , P(c) , P(d)

Z:  P(a)  , P(d) ,   P(c)

The conditions are satisfied for X & Y and X & Z but not for Y & Z. You'll have to check all three of them to be sure. I overlooked this yesterday. :)

---

Yes I was trying to say the same thing yesterday : ). Anyway I'm clear with the concept now .

But one more thing I like to ask you regarding progress, bounded waiting and deadlock

Progress -> No deadlock

Deadlock -> Starvation and no progress

Starvation -> No bounded waiting

 

I have made this after reading  a lot of discussion . Is it the right as per your knowledge?

Correct me if something wrong in it

---

All correct.