Skip to Content

Wiki source code of Deadlock Prevention

Version 3.6 by chrisby on 2023/11/26 19:34
Show last authors
1 Deadlocks can only occur if all four specific conditions are met. Therefore, strategies to prevent deadlocks focus on negating one of these conditions.
2
3 | ------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
4 | **Condition** | **Description** | **Solutions** | **Dangers** |
5 | Mutual Exclusion / Mutex | When resources can't be used by mutual thread and there are less resources than threads. | 1) Use concurrently accessible resources like AtomicInteger. 2) Increase the number of resources until its greater or equal to the number of competing threads. 3 ) Check if every required resource is accessible before the task starts. | |
6 | Lock & Wait | Once a thread acquires a resource, it will not release the resource until it has acquired all of the other resources it requires and has completed its work. | Before reservation of a resource, check its accessibility. If a resource is not accessible, release every resource and start from anew. |
7
8 1) Starvation: A thread never achieves to reserve all required resources. 2) Livelock: Thread gets tangled up.
9
10 These two approach are always applicable but inefficient as it causes a bad performance. |
11 | | | | |
12 | | | | |
13
14 #### Lock & Wait
15
16 * Description:
17 * Once a thread acquires a resource, it will not release the resource until it has acquired all of the other resources it requires and has completed its work.
18 * Solutions:
19 * Before reservation of a resource, check its accessibility.
20 * If a resource is not accessible, release every resource and start from anew.
21 * Dangers:
22 * Starvation: A thread never achieves to reserve all required resources.
23 * Livelock: Thread gets tangled up.→ This approach is always applicable but inefficient as it causes a bad performance.
24
25 #### No preemption
26
27 * Description:
28 * A thread is unable to steal a resources reserved by another thread.
29 * Solution:
30 * A thread is allowed to ask another thread to release all of its resources (including the required one) and starting from anew. This approach is similar to the 'Lock & Wait' solution but has a better performance.
31
32 #### Circular Waiting / Deadly Embrace
33
34 * Description:
35 * When two or more threads require a resource which is already reserved by another of these threads.
36 * Example:
37 * Thread T1 has resource R1 and waits for R2 to be released.
38 * Thread T2 has resource R2 and waits for R1 to be released.
39 * Solution:
40 * All threads reserve all resources in a the same order.
41 * Problems:
42 * The order of reservation doesn't necessarily have to be the same as the order of usage. This leads to inefficiencies like reserving a resource at the beginning which is just required at the end of the task.
43 * Unnecessarily long locked resources.
44 * Order can not always be specified.