| Rule # | Description |
|---|---|
| 1 | If R is in use, T is blocked. |
| 2 | If R is free, R is allocated to T. |
| 3 | When a task of a higher priority requests the same resource, T's execution priority is raised to the requesting task's priority level. |
| 4 | The task returns to its previous priority when it releases R. |
This access control protocol is shown in Figure 16.8.
Figure 16.8: Priority inheritance protocol example.
With the priority inheritance protocol, when the LP-task blocks the HP-task at time t3, the execution priority is raised to that of the HP-task. This process ensures that unrelated medium-priority tasks cannot interfere while the LP-task executes, which results in the elimination of the unbounded priority inversion. When the LP-task releases control of the shared resource, the priority is immediately lowered to its previous level, which allows the HP-task to preempt its execution. This action ends the priority inversion at time t4. The HP-task continues its execution, however, even when it releases the resource at t5. This is the nature of the priority-based, preemptive scheduling scheme. The HP-task runs because it has the highest priority in the system.
The priority inheritance protocol is dynamic because a task does not have its priority raised until a higher- priority task makes a request on the shared resource. An unrelated higher-priority task can still preempt the task, which is the nature of the priority-based, preemptive scheduling scheme. The priority promotion for a task during priority inversion is transitive, which means the priority of a promoted task continues to rise even if higher-priority tasks make requests on the same shared resource while priority inversion is taking place, as shown in Figure 16.9.
Figure 16.9: Transitive priority promotion example.
In this example, three tasks with differing priorities share a resource. The LP-task acquires the resource first at time t1. At time t2, the MP-task preempts the LP-task and executes until t3 when it needs the resource. The MP-task is blocked. At that point, the LP-task inherits the priority from the MP-task and resumes execution at that level. The HP-task preempts the LP-task when it readies at t4. The HP-task is blocked at t5 when it also needs access to the shared resource. Once more, the LP-task inherits its priority from HP-task and resumes execution at the highest level. As soon as the LP-task completes at time t6, its priority is immediately lowered to the level originally assigned.
In this example, the MP-task can hold some additional resource required by the HP-task. The HP-task can also acquire some other resources needed by the MP-task before the HP-task blocks. When the LP-task releases the resource and the HP-task immediately gets to run, it is deadlocked with the MP-task. Therefore, priority inheritance protocol does not eliminate deadlock.
16.4.2 Ceiling Priority Protocol
In the ceiling priority protocol, the priority of every task is known, as are the resources required by every task. For a given resource, the
For example, if a resource R is required by four tasks (T1 of priority 4, T2 of priority 9, T3 of priority 10, and T4 of priority 8), the priority ceiling of R is 10, which is the highest priority of the four tasks.
This access control protocol follows the rules in Table 16.2 when a task T requests a resource R.
Table 16.2: Ceiling priority protocol rules.
| Rule # | Description |
|---|---|
| 1 | If R is in use, T is blocked. |
| 2 | If R is free, R is allocated to T. T's execution priority is raised to the priority ceiling of R if that is higher. At any given time, T's execution priority equals the highest priority ceiling of all its held resources. |
| 3 | T's priority is assigned the next-highest priority ceiling of another resource when the resource with the highest priority ceiling is released. |
| 4 | The task returns to its assigned priority after it has released all resources. |
This access control protocol is shown in Figure 16.10.
Figure 16.10: Ceiling priority protocol example.
With the ceiling priority protocol, the task inherits the priority ceiling of the resource as soon as the task acquires the resource even when no other higher priority tasks contend for the same resource. This rule implies that all critical sections from every sharing task have the same criticality level. The idea is to finish the critical section as soon as possible to avoid possible conflicts.
16.4.3 Priority Ceiling Protocol
Similarly to the ceiling priority protocol, the priority of every task is known in the priority ceiling protocol.
