Priority Inversions
- Former user (Deleted)
- WES Admin
Priority inversion is a problem in real-time systems, and occurs only when using a priority-based preemptive kernel. The figure below illustrates a priority-inversion scenario. Task H (high priority) has a higher priority than Task M (medium priority), which in turn has a higher priority than Task L (low priority).
(1) Task H and Task M are both waiting for an event to occur and Task L is executing.
(2) At some point, Task L acquires a semaphore, which it needs before it can access a shared resource.
(3) Task L performs operations on the acquired resource.
(4) The event that Task H was waiting for occurs, and the kernel suspends Task L and start executing Task H since Task H has a higher priority.
(5) Task H performs computations based on the event it just received.
(6) Task H now wants to access the resource that Task L currently owns (i.e., it attempts to get the semaphore that Task L owns). Because Task L owns the resource, Task H is placed in a list of tasks waiting for the semaphore to be available.
(7) Task L is resumed and continues to access the shared resource.
(8) Task L is preempted by Task M since the event that Task M was waiting for occurred.
(9) Task M handles the event.
(10) When Task M completes, the kernel relinquishes the CPU back to Task L.
(11) Task L continues accessing the resource.
(12) Task L finally finishes working with the resource and releases the semaphore. At this point, the kernel knows that a higher-priority task is waiting for the semaphore, and a context switch takes place to resume Task H.
(13) Task H has the semaphore and can access the shared resource.
So, what happened here is that the priority of Task H has been reduced to that of Task L since it waited for the resource that Task L owned. The trouble begins when Task M preempted Task L, further delaying the execution of Task H. This is called an unbounded priority inversion. It is unbounded because any medium priority can extend the time Task H has to wait for the resource. Technically, if all medium-priority tasks have known worst-case periodic behavior and bounded execution times, the priority inversion time is computable. This process, however, may be tedious and would need to be revised every time the medium priority tasks change.
This situation can be corrected by raising the priority of Task L, only during the time it takes to access the resource, and restore the original priority level when the task is finished. The priority of Task L should be raised up to the priority of Task H. In fact, µC/OS-III contains a special type of semaphore that does just that and is called a mutual-exclusion semaphore.