0
$\begingroup$

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)
$\endgroup$

migrated from cstheory.stackexchange.com Feb 15 '14 at 14:25

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a very impressive answer.... I really need to appreciate ... Thanx.... $\endgroup$ – Đēēpak Shãrmã Feb 15 '14 at 14:10
  • $\begingroup$ Please read answer section of option 4 it should be a > c and c > a.... Please clear my doubt....is this a mistake $\endgroup$ – Đēēpak Shãrmã Feb 15 '14 at 14:21
  • $\begingroup$ Yes, I'll correct this. $\endgroup$ – M'vy Feb 16 '14 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.