Skip to Content

Changes for page Deadlock Prevention

Last modified by chrisby on 2023/11/28 19:17
From version 4.6
edited by chrisby
on 2023/11/26 19:46
Change comment: There is no comment for this version
To version 3.1
edited by chrisby
on 2023/11/26 19:30
Change comment: Rollback to version 1.5

Summary

Details

Page properties
Content
... ... @@ -1,10 +1,40 @@
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 2  
3 -| ----------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
4 -| **Condition** | **Description** | **Solutions** | **Dangers / Problems** |
5 -| Mutual Exclusion / Mutex | When resources can't be shared between threads and there are fewer resources than threads. | 1) Use concurrently accessible resources such as AtomicInteger. 2) Increase the number of resources until it is greater than or equal to the number of competing threads. 3) Check if each required resource is accessible before starting the task. | |
6 -| Lock & Wait | Once a thread has acquired a resource, it will not release it until it has acquired all the other resources it needs and has completed its work. | Before reserving a resource, check its availability. If a resource is unavailable, release all resources and start over. | 1) Starvation: A thread never manages to reserve all the resources it needs. 2) Livelock: The thread gets tangled up. →These two approaches are always applicable, but inefficient because they cause bad performance. |
7 -| No Preemption | A thread is unable to steal a resources reserved by another thread. | 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. | |
8 -| Circular Waiting / Deadly Embrace | When two or more threads require a resource which is already reserved by another of these threads. Example: Thread T1 has resource R1 and waits for R2 to be released. Thread T2 has resource R2 and waits for R1 to be released. | All threads reserve all resources in a the same order. | 1) 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. 2) Unnecessarily long locked resources. 3) Order can not always be specified. |
3 +| ------------------------ | --------------- | ------------- | ----------- |
4 +| **Condition** | **Description** | **Solutions** | **Dangers** |
5 +| Mutual Exclusion / Mutex | | | |
6 +| | | | |
7 +| | | | |
8 +| | | | |
9 9  
10 -
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.