Книга: Real-Time Concepts for Embedded Systems
16.3.4 Deadlock Avoidance
16.3.4 Deadlock Avoidance
Deadlock avoidance is an algorithm that the resource allocation system deploys. The algorithm predicts whether the current allocation request, if granted, can eventually lead to deadlock in the future.
Deadlock avoidance is similar to the deadlock detection algorithm outlined in the 'Multi-Instance Resource Deadlock Detection'. Each time a resource request is made, the system tests whether granting such a request might allow the remaining resources to be given to different tasks in subsequent allocations so that all tasks can run to completion. Revisiting the example given in 'Multi-Instance Resource Deadlock Detection' provides the following:
| N = | 4 | 6 | 2 | |
| A = | 1 | 2 | 0 | |
| C = | 0 | 2 | 0 | Task 1 |
| 1 | 1 | 0 | Task 2 | |
| 1 | 1 | 1 | Task 3 | |
| 1 | 0 | 1 | Task 4 | |
| D = | 2 | 2 | 2 | Task 1 |
| 1 | 1 | 0 | Task 2 | |
| 0 | 1 | 0 | Task 3 | |
| 1 | 1 | 1 | Task 4 |
If task 2 requests one unit of resource R1, granting such a request does not lead to deadlock because a sequence of resource allocations exists, i.e., giving the remaining resources to task 2, to task 3, followed by allocation to task 4, and finally to task 1, which allows all tasks to complete. This request from task 2 is safe and is allowed. If task 4 were to make the same request for R1 and if such a request were granted, this process would prevent task 2 from completing, which would result in a deadlock such that no task could resume execution. The request from task 4 is an unsafe request, and the deadlock avoidance algorithm would reject the request and put task 4 on hold while allowing other tasks to continue.
In order for deadlock avoidance to work, each task must estimate in advance its maximum resource requirement per resource type. This estimation is often difficult to predict in a dynamic system. For more static embedded systems or for systems with predictable operating environments, however, deadlock avoidance can be achieved. The estimations from all tasks are used to construct the demand table, D. This resource estimation only identifies the potential maximum resource requirement through certain execution paths. In the majority of cases, there would be overestimation. Overestimation by each task can lead to inefficient resource utilization in a heavily loaded system. This problem is caused because the system might be running with most of the resources in use, and the algorithm might predict more requests as being unsafe. This issue could result in many tasks being blocked, while holding resources that were already allocated to them.
Оглавление книги
- DEADLOCK TIMEOUT
- 3.5. DEADLOCKS IN DISTRIBUTED SYSTEMS
- 16.3.5 Deadlock Prevention
- 17.4.8. Debugging Deadlock Conditions
- 3.5.1. Distributed Deadlock Detection
- 3.5.2. Distributed Deadlock Prevention
- 16.3 Deadlocks
- 16.3.2 Deadlock Detection
- 16.3.3 Deadlock Recovery
- 8.1.3 Cooperate to avoid deadlocks
- Разделенные транзакции: уникальная возможность избежать Deadlock. Режим AutoCommit