Deadlock prevention algorithms
| Name | Coffman Conditions | Patented | Description |
|---|---|---|---|
| Banker's algorithm | Mutual Exclusion | N/A | The Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra. |
| Preventing Recursive Locks | Mutual Exclusion | No | This prevents a single thread form entering the same lock more than once. |
- Note-This page is under construction.
This page is for links to specific deadlock algorithms. Simple deadlock algorithms may be listed at the bottom of this page, while more complex ones are requested to be located in their own page.
The below needs migrated into the table above.
Distributed deadlock
Distributed deadlocks can occur in distributed systems when distributed transactions or concurrency control is being used. Distributed deadlocks can be detected either by constructing a global wait-for graph, from local wait-for graphs at a deadlock detector or by a distributed algorithm like edge chasing.
In a commitment ordering-based distributed environment (including the strong strict two-phase locking (SS2PL, or rigorous) special case) distributed deadlocks are resolved automatically by the atomic commitment protocol (like a two-phase commit (2PC)), and no global wait-for graph or other resolution mechanism is needed. Similar automatic global deadlock resolution occurs also in environments that employ 2PL that is not SS2PL (and typically not CO; see Deadlocks in 2PL). However, 2PL that is not SS2PL is rarely utilized in practice.
Phantom deadlocks are deadlocks that are detected in a distributed system due to system internal delays but no longer actually exist at the time of detection.
Deadlock prevention
There are many different ways to increase parallelism where recursive locks would otherwise cause deadlocks. But there is a price. And that price is either performance/overhead, allow data corruption, or both.
Some of examples include: lock reference-counting and preemption (either using versioning or allowing data corruption when preemption occurs); Wait-For-Graph (WFG) [1] algorithms, which track all cycles that cause deadlocks (including temporary deadlocks); and heuristics algorithms which don't necessarily increase parallelism in 100% of the places that deadlocks are possible, but instead compromise by solving them in enough places that performance/overhead vs parallelism is acceptable.