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.
|