Skip to Content

Wiki source code of Deadlock Prevention

Version 2.1 by chrisby on 2023/11/26 19:30
Hide last authors
chrisby 1.1 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
chrisby 2.1 3 | ------------------------ | --------------- | ------------- | ----------- |
4 | **Condition** | **Description** | **Solutions** | **Dangers** |
5 | Mutual Exclusion / Mutex | | | |
6 | | | | |
7 | | | | |
8 | | | | |
chrisby 1.1 9
10 #### Lock & Wait
11
12 * Description:
13 * 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.
14 * Solutions:
15 * Before reservation of a resource, check its accessibility.
16 * If a resource is not accessible, release every resource and start from anew.
17 * Dangers:
18 * Starvation: A thread never achieves to reserve all required resources.
19 * Livelock: Thread gets tangled up.→ This approach is always applicable but inefficient as it causes a bad performance.
20
21 #### No preemption
22
23 * Description:
24 * A thread is unable to steal a resources reserved by another thread.
25 * Solution:
26 * 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.
27
28 #### Circular Waiting / Deadly Embrace
29
30 * Description:
31 * When two or more threads require a resource which is already reserved by another of these threads.
32 * Example:
33 * Thread T1 has resource R1 and waits for R2 to be released.
34 * Thread T2 has resource R2 and waits for R1 to be released.
35 * Solution:
36 * All threads reserve all resources in a the same order.
37 * Problems:
38 * 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.
39 * Unnecessarily long locked resources.
40 * Order can not always be specified.