I have been faced with a problem where three concurrent processes X, Y ,Z execute three different code segments that access and update certain shared variables. Before entering the respective code segments :
Process X executes the P operation 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.
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 do I recognise a deadlock-free order of invoking the P operations by the processes ? For illustration, the given examples are the following
- X: P(a)P(b)P(c) Y:P(b)P(c)P(d) Z:P(c)P(d)P(a)
- X: P(b)P(a)P(c) Y:P(b)P(c)P(d) Z:P(a)P(c)P(d)
- X: P(b)P(a)P(c) Y:P(c)P(b)P(d) Z:P(a)P(c)P(d)
- X: P(a)P(b)P(c) Y:P(c)P(b)P(d) Z:P(c)P(d)P(a)