Guideline: Preventing Deadlock
There are four conditions that must be met for deadlock to occur. Breaking any of them will remove the possibility of deadlock.

Deadlock is all too common a situation. It occurs when four conditions are satisfied:

  • Mutual exclusion locking of resources
  • Resources are locked while other resources are requested
  • Preemption while resources are locked is permitted
  • A circular waiting condition exists

Legend (Priority Task 1 > Priority Task 2)
Step Description
A Task 2 runs with the intent of lock resource R1 and then R2
B Task 2 locks R1 and is about to lock R2
C Task 1 runs, preempting Task 2, with the intent of locking R2 and then R1
D Task 1 locks R2
E Task 1 needs to lock R1, however, R1 is already locked by Task 2. So Task 1 must block until Task 2 can release it, however, now Task 2 needs to lock R2, but it can't because Task 1 has locked it. Therefore, neither task can continue.

As mentioned, breaking any of the four conditions removes the possibility of deadlock. For example, using the Simultaneous Blocking Pattern, Task 2 would lock both resources at the same time; in this case Task 1 would be blocked, but Task 2 could complete, release its resources and then Task 1 could run. Alternatively, the Ordered Blocking Pattern could be used; in this pattern resources are assigned a unique scalar value. Locking resources can only be done in an ascending order (e.g. after resource 5, no resource with an order of less than 5 can be locked by that client until resource 5 is released). This prevents the circular waiting conditions.  See DOU02 for a more complete description of the patterns.

Relationships