Ordered Locks

Intent: Avoid DeadLock between concurrent tasks.

A DeadLock can arise between two concurrent tasks when one task holds resource A and is waiting for resource B, and another task holds resource B and is waiting for resource A. For more than two tasks, deadlocks can arise whenever there is a cycle in a directed graph representing which tasks are waiting on resources held by others.

Therefore, establish an ordering of the resources, and require tasks to acquire locks on the resources in order. This prevents the possibility of a dependency cycle.

In a concurrent program with many locks (especially ones hidden from the user), enforcing this can be very difficult. Determining whether or not a locking order violation occurs via static analysis is undecideable--computationally equivalent to the GeneralHaltingProblem. You could use "order aware" sempahores (or whatever locking primitive you like) that can check at runtime if they are taken out of order, but this is a) expensive; and b) what do you do when the locking order is violated?

While maintaining a locking order will indeed prevent DeadLock; this technique does not scale well, unfortunately. OrderedLocks are useful; but far from a SilverBullet

See also: DeadLock SynchronizationStrategies

CategoryPattern | CategoryConcurrencyPatterns