Skip to main content
edited body
Source Link
M'vy
  • 164
  • 1
  • 5

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 > b$$c > a$ (from Y) contradicts the transitivity.

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

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 > b$ (from Y) contradicts the transitivity.

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

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.

Post Migrated Here from cstheory.stackexchange.com (revisions)
Source Link
M'vy
  • 164
  • 1
  • 5

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 > b$ (from Y) contradicts the transitivity.

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