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.
Relationships
Main Description

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.