How to build/recognise a deadlock-free order of resources

Question

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

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)

Answer 1

Preventing deadlocks can be achieve by removing one of the Coffman condition, one being the circular wait condition.

For this we need to build a partial ordering of the resources.

From Wikipedia a partial ordered (poset) set is :

A (non-strict) partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all a, b, and c in P:

• a ≤ a (reflexivity);
• if a ≤ b and b ≤ a then a = b (antisymmetry);
• if a ≤ b and b ≤ c then a ≤ c (transitivity).

For the processes, there is no interest in the first two clauses, resources are distinct and unique. All we care about is the transitivity. Assuming a given order of resources, we then must ensure that each process never claims a lower resource before a higher one.

Building a deadlock free order is as simple as ordering the resources. This choice is arbitrary.

To solve your examples, we need to find what order has been chosen, if one exists, and verify it is a poset.

1. is not a poset since $a > c$ (from X) and $c > a$ (from Z) contradicts the transitivity.
2. is a poset since $b > a > c > d$ in all groups.
3. is not a poset since $b > c$ (from X) and $c > b$ (from Y) contradicts the transitivity.
4. is not a poset since $a > c$ (from X) and $c > a$ (from Y) contradicts the transitivity.

Conclusion, only 2 is a deadlock free order as the circular wait condition is removed.