Most embedded RTOSes facilitate a multitasking- or multithreading-capable environment. Many challenging design problems arise when developing embedded applications in multitasking systems.
The nature of this environment is that multiple threads of execution share and contend for the same set of resources. As such, resource sharing requires careful coordination to ensure that each task can eventually acquire the needed resource or resources to continue execution.
In a preemptive multitasking environment, resource sharing is a function of task priority. The higher the priority of a task, the more important the task is. Higher priority tasks have precedence over lower priority tasks when accessing shared resources. Therefore, resource sharing cannot violate this rule. On the other hand, if higher priority tasks always take resources from lower priority tasks, this sharing scheme is not fair and can prevent lower priority tasks from ever completing. This condition is called starvation. Maximization of resource utilization is yet another conflicting requirement.
Two of the most common design problems facing embedded developers are the deadlock and the priority inversion problem.
Specifically, this chapter focuses on:
· resource classification,
· resource request models,
· definition of deadlocks,
· deadlock detection, recovery, avoidance and prevention,
· definition of priority inversion, and
· solutions to priority inversion.
In embedded systems, resources are shared among various concurrently executing tasks. Examples of these shared resources include I/O devices, machine registers, and memory regions. These shared resources are categorized as either preemptible or nonpreemptible .
A preemptible resource can be involuntarily and temporarily removed from a task without affecting the task's execution state or result. The machine registers set that is shared among multiple tasks is an example. When kernel scheduling preempts a current task, the content of the machine registers, including the execution state of the current task, is saved into main memory. The registers are reinitialized to execute another task. When that other task completes, the execution state is restored to the register set, and the preempted task is resumed. The scheduler guarantees that the register set contains the execution state from a single task even though the registers are shared among multiple tasks throughout the system's lifetime.
A non-preemptible shared resource must be voluntarily relinquished by the owning task, or unpredictable results can occur. A shared memory region belongs to this category. For example, one task should not be allowed to write to a shared memory region before another task completes its read or write operation.
The types of resources a task holds are important when deciding on what solutions to take when the task is involved in deadlock situations. Section 16.3.3 discusses the relationship between the resource types and deadlock recovery mechanisms in detail.
Deadlock is the situation in which multiple concurrent threads of execution in a system are blocked permanently because of resource requirements that can never be satisfied.
A typical real-time system has multiple types of resources and multiple concurrent threads of execution contending for these resources. Each thread of execution can acquire multiple resources of various types throughout its lifetime. Potential for deadlocks exist in a system in which the underlying RTOS permits resource sharing among multiple threads of execution. Deadlock occurs when the following four conditions are present:
Mutual exclusion - A resource can be accessed by only one task at a time, i.e., exclusive access mode.
No preemption - A non-preemptible resource cannot be forcibly removed from its holding task. A resource becomes available only when its holder voluntarily relinquishes claim to the resource.
Hold and wait - A task holds already-acquired resources, while waiting for additional resources to become available.
Circular wait - A circular chain of two or more tasks exists, in which each task holds one or more resources being requested by a task next in the chain.
Given that each resource is nonpreemptible and supports only exclusive access mode, Figure 16.1 depicts a deadlock situation between two tasks.
Figure 16.1: Deadlock situation between two tasks.
Figure 16.1 is a resource graph. An arrow labeled holds going from a resource to a task indicates that the task currently holds (or owns) the resource. An arrow labeled wants going from a task to a resource indicates that the task currently needs this resource to resume execution.
In this example, task #1 wants the scanner while holding the printer. Task #1 cannot proceed until both the printer and the scanner are in its possession. Task #2 wants the printer while holding the scanner. Task #2 cannot continue until it has the printer and the scanner. Because neither task #1 nor task #2 is willing to give up what it already has, the two tasks are now deadlocked because neither can continue execution.
Deadlocks can involve more than two tasks.
As shown in Figure 16.2, task T1 currently holds resource R1 (a printer), and T1 wants resource R2 (a scanner). Task T2 holds resource R2 and wants resource R3 (a memory buffer). Similarly, task T3 holds resource R3 and wants resource R1. It is easy to see the cycle, i.e., the circular-wait condition in this system. Tasks T1, T2, and T3, and resources R1, R2, and R3 comprise the deadlocked set. Note that in the system in Figure 16.2, one instance per resource type exists, i.e., there is one instance of R1, one instance of R2, and one instance of R3. A later section, 'Multi-Instance Resource Deadlock Detection' on page 266, discusses deadlock situations that involve multiple instances of a resource type.
Figure 16.2: Deadlock situation among three tasks.
In this example, each task requires a single instance of a single resource type at any given time. Many situations exist in which a task might require multiple instances of multiple types of resources. The formation of deadlocks depends on how a task requests resources (formally known as a resource request model). The deadlock detection algorithms are constructed according to the resource request models.
When tasks ask for resources, the way the task makes the requests can be classified into these request models:
· the Single resource request model,
· the AND resource request model,
· the OR resource request model, and
· the AND-OR resource request model.
In the Single resource request model, exemplified in both Figure 16.1 and Figure 16.2, a task can have at most one outstanding resource request at any given time. In the request model, a task asks for resources as in 'wants a printer.'
In the AND resource request model, a task can have multiple simultaneous requests outstanding at any given time. For example, a task can request resources as (R1 and R2) or (R1 and R2 and R3). A task is blocked until all of the requested resources are granted. In this request model, a task asks for resources as in "wants both a printer and a scanner." The task resumes execution only when it successfully acquires both the printer and the scanner.
In the OR resource request model, a task can request a set of resources, but the task can resume execution as soon as any one of the resources from the request set becomes available. For example, a task can request resources as (R1 or R2) or (R1 or R2 or R3). In this request model, a task asks for resources as in "wants either a printer or a scanner." The task resumes execution when it acquires either the printer or the scanner.
In the AND-OR resource request model, a task can make resource requests in any combination of the AND and OR models. For example, a task can request a set of resources as (R1 or R2 and (R3 or R4)). In this request model, the task asks for resources as in "wants either a printer or a scanner, and wants either a memory buffer or a message queue." The task can resume execution when it acquires both the printer and the memory buffer, when it acquires both the printer and the message queue, when it acquires the scanner and the memory buffer, or when it acquires the scanner and the message queue. A generalization of the AND-OR model is the C(n,k) model. In this model, a task can make n resource requests and can resume execution as soon as k resources are granted, where k ≤ n.
A deadlock condition is called a stable deadlock when no task in the deadlocked set expects a timeout or an abort that can eliminate the deadlock. A stable deadlock is permanent and requires external influence to eliminate. The external influence is the deadlock detection and recovery by the underlying RTOS.
Deadlock detection is the periodic deployment of an algorithm by the RTOS. The algorithm examines the current resource allocation state and pending resource requests to determine whether deadlock exists in the system, and if so, which tasks and resources are involved.
The deadlock detection algorithm that the RTOS deploys is a global algorithm because it is used to detect deadlocks in the entire system. In general, each task of the deadlocked set is not aware of the deadlock condition. As a result, the recovery algorithm is more intrusive on the normal execution of the tasks belonging to the deadlocked set. The recovery algorithms and reasons why these algorithms are intrusive on the execution of the tasks involved in the deadlock are discussed shortly.
A temporal deadlock is a temporary deadlock situation in which one or more tasks of the deadlocked set either times out or aborts abnormally due to timing constraints. When the task times out or aborts, it frees the resources that might have caused the deadlock in the first place, thus eliminating the deadlock. This form of detection and recovery is localized to an individual task, and the task has deadlock awareness.
A system that is capable of deadlock detection is more efficient in terms of resource utilization when compared to a system without deadlock detection. A system capable of deadlock detection is not conservative when granting resource allocation requests if deadlock is allowed to occur. Therefore, resources are highly utilized. A system without deadlock detection is conservative when granting resource allocation requests. A resource request is denied if the system believes there is a potential for deadlock, which may never occur. The conservatism of the system results in idle resources even when these resources could be used.
Deadlock detection does not solve the problem; instead, the detection algorithm informs the recovery algorithm when the existence of deadlock is discovered.
For deadlock in the Single resource request model, a cycle in the resource graph is a necessary and sufficient condition.
For deadlock in the AND resource request model, a cycle in the resource graph is a necessary and sufficient condition. It is possible for a task to be involved in multiple deadlocked sets.
For deadlock in the OR request model, a knot is a necessary and sufficient condition.
Therefore, deadlock detection involves finding the presence of a cycle in the resource graph for both the Single and the AND resource request models. Deadlock detection involves finding the presence of a knot in the resource graph for the OR resource request model.
For deadlock in the AND-OR model, no simple way exists of describing it. Generally, the presence of a knot after applying the algorithm to the OR model first and then subsequently applying the algorithm to the AND model and finding a cycle is an indication that deadlock is present.
The following sections present two deadlock detection algorithms-one for the single resource request model and one for the AND resource request model-to illustrate deadlock detection in practice.
For node A in the resource graph, the reachable set of A is the set of all nodes B, such that a directed path exists from A to B. A knot is the request set K, such that the reachable set of each node of K is exactly K.
The deadlock detection algorithm for systems with a single instance of each resource type, and tasks making resource requests following the single resource request model, is based on the graph theory. The idea is to find cycles in the resource allocation graph, which represents the circular-wait condition, indicating the existence of deadlocks.
Figure 16.3 shows the resource allocation graph. The graph represents the following:
· a circle represents a resource,
· a square represents a task or thread of execution,
· an arrow going from a task to a resource indicates that the task wants the resource, and
· an arrow going from a resource to a task indicates that the task currently holds the resource.
Figure 16.3: Current state of resource allocations and requests.
In the following discussions, node refers either to the circle (resource) or the square (task) in Figure 16.3. Arc refers to the arrow. The deadlock detection algorithm can be stated in these seven steps:
1. Make a list of all the nodes, N, from the graph.
2. Pick a node from N. Create another list, L, initially empty, which is used for the graph traversal.
3. Insert the node into L and check if this node already exists in L. If so, a cycle exists; therefore, a deadlock is detected, and the algorithm terminates. Otherwise, remove the node from N.
4. Check whether any un-traversed outgoing arcs from this node exist. If all of the arcs are traversed, go to step 6.
5. Choose an un-traversed outgoing arc originating from the node and mark the arc as traversed. Follow the chosen arc to the new node and return to step 3.
6. At this stage, a path in the graph terminates, and no deadlocks exist. If more than one entry is in L, remove the last entry from L. If more than one entry remains in L, make the last entry of L the current node and go to step 4.
7. If the list N is not empty, go to step 2. Otherwise, the algorithm terminates, and no deadlocks exist in the system.
The actual implementation from step 3 to step 6 translates into a depth first search of the directed graph.
Applying this algorithm to the system depicted in Figure 16.3 provides the following:
Step 1: N = {R1, T1, R2, T2, R3, T3, R4, T4, T5, R5, T6}
Step 2: L = {‹empty›}; pick node R1
Step 3: L = {R1}; no cycles are in L; N = {T1, R2, T2, R3, T3, R4, T4, T5, R5, T6}
Step 4: R1 has one outgoing arc
Step 5: Mark the arc; reaches node T1; go back to step 3
Step 3: L = {R1, T1}; N = {R2, T2, R3, T3, R4, T4, T5, R5, T6}; no cycles are in L
The algorithm continues from step 3 to step 5 and reiterates until it reaches node T3, in which the list L = {R1, T1, R2, T2, R4, T3} and the list N = {R3, T4, T5, R5, T6}. Two outgoing arcs are at node T3. When the downward arc is picked, L = {R1, T1, R2, T2, R4, T3, R5}. Two outgoing arcs are at node R5. When the rightward arc is picked, L = {R1, T1, R2, T2, R4, T3, R5, T6}.
Step 4: T6 does not have any outgoing arcs; continue to step 6
Step 6: Remove T6 from the list L; L = {R1, T1, R2, T2, R4, T3, R5}; return to step 4
Step 4: Pick the unmarked leftward arc at R5
Step 5: Mark the arc; reaches node T5; return to step 3
Step 3: L = {R1, T1, R2, T2, R4, T3, R5, T5}; N = {R3, T4}; no cycles are in L
Step 4: Pick the only outgoing arc at T5
Step 5: Mark the arc; reaches node R3; go back to step 3
Step 3: L = {R1, T1, R2, T2, R4, T3, R5, T5, R3}; N = {T4}; still no cycles are in L
Step 4: Pick the only outgoing arc at R3
Step 5: Mark the arc; reaches node T1; go back to step 3
Step 3: L = {R1, T1, R2, T2, R4, T3, R5, T5, R3, T1}; Node T1 already exists in L. A cycle is found in the graph, and a deadlock exists. The algorithm terminates.
The deadlock set is comprised of the entire nodes enclosed by the two occurrences of node T1 inclusively. Therefore, the discovered deadlock set is {T1, R2, T2, R4, T3, R5, T5, R3}. One thing worth noting is that the algorithm detects deadlocks if any exist. Which deadlock is detected first depends on the structure of the graph. Closer examination of the resource graph reveals that another deadlock exists. That deadlock set is {R2, T2, R4, T3}. At node T3 if the upward arc is chosen first instead of the downward arc, this later deadlock occurrence would be discovered, and the algorithm would terminate much sooner.
The deadlock detection algorithm takes a different approach for systems with multiple instances of each resource type, and tasks make resource requests following the AND model. An underlying assumption is that a resource allocation system is present. The resource allocation system is comprised of a set of different types of resources, R1, R2, R3,…, Rn. Each type of resource has a fixed number of units. The resource allocation system maintains a resource allocation table and a resource demand table.
Each row of tables C and D represents a task T. Each column of tables C and D is associated with a resource type. C is the resource allocation table representing resources already allocated. D is the resource demand table representing additional resources required by the tasks.
| N = Total System Resources Table | N1 | N2 | N3 | … | Nk |
where Ni is the number of units of resource type Ri for all i where {1 ≤ i ≤ k }.
| A = Available System Resources Table | A1 | A2 | A3 | … | Ak |
where Ai the number of units remaining for resource type Ri available for allocation.
| C = Tasks Resources Assigned Table | C11 | C12 | C13 | … | C1k |
| C21 | C22 | … | C2k | ||
| … | … | ||||
| Cm1 | … | Cmk | |||
| D = Tasks Resources Demand Table | D11 | D12 | D13 | … | D1k |
| D21 | D22 | … | D2k | ||
| … | … | ||||
| Dm1 | … | Dmk |
For example in table C, there are C11 units of resource R1, C12 units of resource R2, and so on, which are allocated to task T1. Similarly, there are C21 units of resource R1, C22 units of resource R2, and so on, which are allocated to task T2. For example in table D, task T1 demands additional D11 units of resource R1, additional D12 units of resource R2, and so on, in order to complete execution.
The deadlock detection algorithm is as follows:
1. Find a row i in table D, where Dij ‹ Aj for all 1 ≤ j ≤ k. If no such row exists, the system is deadlocked, and the algorithm terminates.
2. Mark the row i as complete and assign Aj = Aj + Dij for all 1 ≤ j ≤ k.
3. If an incomplete row is present, return to step 1. Otherwise, no deadlock is in the system, and the algorithm terminates.
Step 1 of the algorithm looks for a task whose resource requirements can be satisfied. If such a task exists, the task can run to completion. Resources from the completed task are freed back into the resource pool, which step 2 does. The newly available resources can be used to meet the requirements of other tasks, which allow them to resume execution and run to completion.
When the algorithm terminates, the system is deadlocked if table T has incomplete rows. The incomplete rows represent the tasks belonging to the deadlocked set. The algorithm is illustrated in the following example.
| 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 |
Step 1: Task 1 cannot continue because the available resources do not satisfy its requirements.
Task 2 can continue because what it needs can be met.
| Step 2: | A = 2 | 3 | 0 |
Step 3: Task 1, task 3, and task 4 remain. Return to step 1.
Step 1: Task 1 still cannot continue. The requirement from task 3 can be met.
| Step 2: | A = 3 | 4 | 1 |
Step 3: Task 1 and task 4 remain. Return to step 1.
Step 1: Task 1 still cannot continue, but task 4 can.
| Step 2: | A = 4 | 4 | 2 |
Step 3: Task 1 remains. Return to step 1.
Step 1: Task 1 can continue.
| Step 2: | A = 4 | 6 | 2 |
Step 3: No more tasks remain, and the algorithm terminates. No deadlock is in the system.
Now if the resource requirement for task 3 were [0 1 1] instead of [0 1 0], task 1, task 3, and task 4 cannot resume execution due to lack of resources. In this case, these three tasks are deadlocked.
It is worth noting that executing a deadlock detection algorithm takes time and can be non-deterministic.
After deadlock is detected, the next step is to recover from it and find ways to break the deadlock. No one magic solution exists to recover from deadlocks. Sometimes it is necessary to execute multiple recovery methods before resolving a deadlock, as illustrated later.
For preemptible resources, resource preemption is one way to recover from a deadlock. The deadlocked set is transferred to the recovery algorithm after the detection algorithm has constructed the set. The recovery algorithm can then exercise preemption by taking resources away from a task and giving these resources to another task. This process temporarily breaks the deadlock. The latter task can complete execution and free its resources. These resources are used in turn to satisfy the first task for its completion. Resource preemption on preemptible resources does not directly affect the task's execution state or result, but resource preemption can affect a task's timing constraints. The duration of resource preemption can cause the preempted task to abort, which results in an incomplete execution and indirectly affects the result of a task.
For non-preemptible resources, resource preemption can be detrimental to the preempted task and can possibly affect the results of other tasks as well. For example, consider the situation in which one task is in the midst of writing data into a shared memory region, while at the same time a second task requests read access from the same memory region. The write operation is invalidated, when another task causes a deadlock, and the system recovers from the deadlock by preempting the resource from the writing task. When the second task gets the resource and begins accessing the shared memory, the data read is incoherent and inconsistent. For this reason, a shared memory region is classified as a non-preemptible resource. The preempted task writes the remaining data when the access to the shared memory is returned. The data is no longer useful, and the write operation is wasted effort. Sometimes this type of resource preemption is as good as eliminating the preempted task from the system altogether.
On the other hand, the effects of non-preemptible resource preemption can be minimized if a task has a built-in, self-recovery mechanism. A task can achieve self-recovery by defining checkpoints along its execution path. As soon as the task reaches a checkpoint, the task changes a global state to reflect this transition. In addition, the task must define a specific entry point to be invoked by the deadlock recovery algorithm after the task is allowed to resume execution. The entry point is nothing more than the beginning of the task's built-in, self-recovery routine. In general, the recovery involves rolling back and restarting execution from the beginning of the previous checkpoint. The concept is illustrated in Listing 16.1.
Listing 16.1: Checkpoints and recovery routine.
<code> recovery_entry()
... {
<code> switch (state)
... {
/* reached checkpoint #1 */ case CHECKPOINT_1:
state = CHECKPOINT_1; recovery_method_1();
... break;
<code> case CHECKPOINT_2:
... recovery_method_2();
/* reached checkpoint #2 */ break;
state = CHECKPOINT_2; ...
}
... }
In Listing 16.1, a resource preemption is performed on a writer task and the preempted resource is given to the reader task. The writer task's self-recovery involves returning to the previous checkpoint and perhaps repeating the write operation, followed by a broadcast notification to all other tasks that the shared memory region has just been updated. This process can reduce the impact on other tasks.
The reassignment target of the preempted resource plays an important role in breaking the deadlock. For example, assume the deadlocked set {T1, R2, T2, R4, T3, R5, T5, R3} has been discovered, as shown in Figure 16.3. In addition, suppose resource R2 is preempted from T2 as the first recovery step. Figure 16.4 shows the resource graph if R2 were reassigned to T3.
Figure 16.4: Resource preemption with a new deadlock.
The problem is not solved because a new deadlock is formed by this resource assignment. Instead, if R2 were given to T1 first, the deadlock is broken as shown in Figure 16.5.
Figure 16.5: Deadlock eliminated by proper resource reassignment.
Consequently, T1 can complete and then frees R1, R2, and R3. This process in term enables T5 to complete and releases R5. Now, both R2 and R5 are available to T2, which allows it to run to completion. Finally, T2 is given a second chance to execute, and the deadlock is eliminated by proper resource reassignment.
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 prevention is a set of constraints and requirements constructed into a system so that resource requests that might lead to deadlocks are not made. Deadlock prevention differs from deadlock avoidance in that no run-time validation of resource allocation requests occurs. Deadlock prevention focuses on structuring a system to ensure that one or more of the four conditions for deadlock i.e., mutual exclusion, no preemption, hold-and-wait, and circular wait is not satisfied.
This set of constraints and requirements placed on resource allocation requests is as follows:
· Eliminating the hold-and-wait deadlock condition. A task requests at one time all resources that it will need. The task can begin execution only when every resource from the request set is granted.
This requirement addresses the hold-and-wait condition for deadlock. A task that obtains all required resources before execution avoids the need to wait for anything during execution. This approach, however, has limited practicality and several drawbacks. In a dynamic system, tasks have difficulty predicting in advance what resources will be required. Even if all possible resource requirements could be accurately predicted, this prediction does not guarantee that every resource in this predicted set would be used. Execution paths, which external factors affect, determine which resources are used.
One major drawbacks to this approach is the implicit requirement that all resources must be freed at the same time. This requirement is important because a resource can be needed in multiple code paths; it can be used and later be reused. So, the resource must be kept until the end of task execution. Some of the resources, however, might be used once or used only briefly. It is inefficient for these resources to be kept for a long time because they cannot be reassigned to other tasks.
· Eliminating the no-preemption deadlock condition. A task must release already acquired resources if a new request is denied. The task must then initiate a new request including both the new resource and all previously held resources.
This requirement addresses the no-preemption condition for deadlock. This approach is slightly more dynamic than the previous method in that resources are acquired on an as-needed basis and only those resources needed for a particular execution path, instead of all possible resources, are acquired.
This approach, however, is not much better than the previous one. For tasks holding non-preemptible resources, this requirement means that each task must restart execution either from the beginning or from well-defined checkpoints. This process nullifies partially complete work. Potentially, a task might never complete, depending on the average number of tasks existing in the system at a given time and depending on the overall system scheduling behavior.
· Eliminating the circular-wait deadlock condition. An ordering on the resources must be imposed so that if a task currently holds resource Ri, a subsequent request must be for resource Rj where j › i. The next request must be for resource Rk where k › j, and so on.
This imposition addresses the circular-wait condition for deadlock. Resources are organized into a hierarchical structure. A task is allowed to acquire additional resources while holding other resources, but these new resources must be higher in the hierarchy than any currently held resources.
Priority inversion is a situation in which a low-priority task executes while a higher priority task waits on it due to resource contentions.
A high task priority implies a more stringent deadline. In a priority-based, preemptive scheduling system, the kernel schedules higher priority tasks first and postpones lower priority tasks until either all of the higher priority tasks are completed or the higher priority tasks voluntarily relinquish the CPU. In real-time embedded systems, the kernel strives to make the schedulability of the highest priority task deterministic. To do this, the kernel must preempt the currently running task and switch the context to run the higher priority task that has just become eligible, all within a known time interval. This system scheduling behavior is the norm when these tasks are independent of each other. Task interdependency is inevitable when tasks share resources and synchronizing activities. Priority inversion occurs when task interdependency exists among tasks with different priorities.
Consider the situation shown in Figure 16.6, in which a higher priority task shares a resource with a lower priority task. The higher priority task must wait when the lower priority task has locked the resource, even though the higher priority task is eligible to run.
Figure 16.6: Priority inversion example.
As shown in Figure 16.6, at time t1 the low-priority task (LP-task) locks the shared resource. The LP-task continues until time t2 when the high-priority task (HP-task) becomes eligible to run. The scheduler immediately preempts the LP-task and context-switches to the HP-task. The HP-task runs until time t3 when it requires the shared resource. Because the resource is in the locked state, the HP-task must block and wait for its release. At this point, the scheduler context-switches back to the LP-task. Priority inversion begins at time t3. At time t4, the LP-task releases the shared resource, which triggers preemption and allows the HP-task to resume execution. Priority inversion ends at time t4. The HP-task completes at time t5, which allows the LP-task to resume execution and finally complete at time t6.
The priority inversion shown in Figure 16.6 is a bounded priority inversion. The duration of the low-priority task's holding time on the shared resource is known. It is possible for a medium-priority task to preempt the low-priority task for an undetermined amount of time, which would cause the high-priority task to wait indefinitely. This priority inversion scenario is called unbounded priority inversion and is shown in Figure 16.7.
Figure 16.7: Unbounded priority inversion example.
As in the previous example, priority inversion takes place at time t3. The low-priority task (LP-task) executes until time t4 when an unrelated medium-priority task (MP-task) preempts it. Because the MP-task does not share resources with either the HP-task or the LP-task, the MP-task continues execution until it completes at time t5. The duration between t4 and t5 is unknown because the duration depends on the nature of the MP-task. In addition, any number of unrelated medium-priority tasks can execute during this period. These unknown factors affect the interval and translate into unbounded priority inversion.
When priority inversion occurs, the execution times for some tasks are reduced, while others are elongated. In Figure 16.7, consider the case in which the high-priority task (HP-task) takes the guarding semaphore before the low-priority task (LP-task). The medium-priority task (MP-task) must wait until the HP-task completes. However, when the MP-task executes first, it is preempted by the HP-task. Again, the MP-task resumes execution after the HP-task completes. In both cases, the overall execution times for the MP-task are longer than the execution time to complete the MP-task during the priority inversion. Although some tasks are completed early, other tasks, such as the HP-task, might miss their deadlines. This issue is called timing anomaly introduced by priority inversion.
Priority inversion results from resource synchronization among tasks of differing priorities. Priority inversion cannot be avoided, but it can be minimized using resource access control protocols.
A resource access control protocol is a set of rules that defines the conditions under which a resource can be granted to a requesting task and governs the execution scheduling property of the task holding the resource.
Access control protocols are discussed in the following sections. These access control protocols eliminate the unbound priority inversion, and two of these protocols reduce the inversion time.
The Priority Inheritance Protocol is a resource access control protocol that raises the priority of a task, if that task holds a resource being requested by a higher priority task, to the same priority level as the higher priority task. This access control protocol follows the rules in Table 16.1 when a task T requests a resource R.
Table 16.1: Priority Inheritance Protocol rules.
| 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.
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 priority ceiling is the highest priority of all possible tasks that might require the resource.
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.
Similarly to the ceiling priority protocol, the priority of every task is known in the priority ceiling protocol. The resources that every task requires are also known before execution. The current priority ceiling for a running system at any time is the highest priority ceiling of all resources in use at that time.
For example, if four resources are in use and if R1 has a priority ceiling of 4, R2 has a priority ceiling of 9, R3 of a priority ceiling 10, and R4 of a priority ceiling 8, the current priority ceiling of the system is 10. Note that different tasks can hold these resources.
This access control protocol follows the rules in Table 16.3 when a task T requests a resource R.
Table 16.3: Priority ceiling protocol rules.
| Rule # | Description |
|---|---|
| 1 | If R is in use, T is blocked. |
| 2 | If R is free and if the priority of T is higher than the current priority ceiling, R is allocated to T. |
| 3 | If the current priority ceiling belongs to one of the resources that T currently holds, R is allocated to T, and otherwise T is blocked |
| 4 | The task that blocks T inherits T's priority if it is higher and executes at this priority until it releases every resource whose priority ceiling is higher than or equal to T's priority. The task then returns to its previous priority. |
In the priority ceiling protocol, a requesting task can be blocked for one of three causes. The first cause is when the resource is current in use, which is direct resource contention blocking, and is the result of rule #1. The second cause is when the blocking task has inherited a higher priority and its current execution priority is higher than that of the requesting task. This cause is priority inheritance blocking and is the result of rule #4. A task can be blocked when its priority is lower than the current priority ceiling even when the requested resource is free. This cause is priority ceiling blocking and is a direct consequence of the 'otherwise' clause of rule #3. Rule #3 prevents a task from blocking itself if it holds a resource that has defined the current priority ceiling.
One of the deadlock prevention strategies in the 'Deadlock Prevention' on section 16.3.5, is to impose ordering on the resources. The resource ordering can be realized by using the priority ceilings of the resources. Rule #2 says if the priority of T is higher than the current priority ceiling, T does not require any resources that are in use. This issue occurs because otherwise the current priority ceiling would be either equal to or higher than the priority of T, which implies that tasks with a priority higher than T's do not require the resources currently in use. Consequently, none of the tasks that are holding resources in use can inherit a higher priority, preempt task T, and then request a resource that T holds. This feature prevents the circular-wait condition. This feature is also why deadlock cannot occur when using the priority ceiling protocol as an access control protocol. The same induction process shows that the condition in which a task blocks another task but is in turn blocked by a third task, transitive blocking, does not occur under the priority ceiling protocol.
The priority ceiling protocol has these characteristics:
· A requesting task can be blocked by only one task; therefore, the blocking interval is at most the duration of one critical section.
· Transitive blocking never occurs under the priority ceiling protocol.
· Deadlock never occurs under the priority ceiling protocol.
Some points to remember include the following:
· Resources can be classified as either preemptible or non-preemptible resources.
· Deadlock occurs when all four of these conditions are true: mutual exclusion, no preemption, hold-and-wait, and circular wait.
· Resource requests can be classified into Single, AND, OR, and AND-OR request models.
· Strategies exist for dealing with deadlocks: deadlock detection and recovery, deadlock avoidance, and deadlock prevention.
· Access control protocols exist for dealing with priority inversion: priority inheritance protocol, ceiling priority protocol, and priority ceiling protocol.
· Deadlock never occurs under the priority ceiling protocol.