A fundamental maxim in a real-time system is that the highest priority task that is ready to run must be given control of the processor. If this does not happen deadlines can be missed and the system can become unstable or worse. Priority inversion simply means that the priority you established for a task in your system is turned upside down by the unintended result of how priorities are managed and how system resources are assigned. It is an artifact of the resource sharing systems that are fundamental to RTOS operation.
Mutex (and/or Semaphore) objects are used to ensure that the various tasks can have exclusive access to system resources when they need them. Consider Task C that is writing to RAM. To protect against memory corruption which could occur if another higher priority task (Task A) preempts Task C and writes to the same block, Task C uses a Mutex to lock access to the RAM until the write is completed. However, Task A interrupts Task C before the operation can be completed and yet Task A needs to access the file system to complete its work. The result is a priority inversion. Task C must finish its work so that Task A can get access, but Task A has blocked Task C because Task A has a higher priority. Embedded gridlock! This scenario can be termed “bounded inversion.”
A variation of this is termed “unbounded inversion.” Task C has locked the RAM with a Mutex and is then preempted by Task B which is attempting to perform an unrelated, but higher priority operation. Highest priority Task A then preempts Task B but relinquishes control (blocks) since it cannot access the resource because of the Mutex claimed by task C. Task B then resumes operation and maintains control of the processor for as long as it needs it. Task A (the highest priority task) is unable to run during this unbounded period.
The simple solution is to let Task C finish what it was doing, uninterrupted, and then release the Mutex on the file system so that Task A can do what it needs to do. But the operating system objects are doing exactly what they were programmed to do and, without special logic to deal with these situations, the scheduler must honor the relative priorities of Tasks A, B and C and the inherent rules of the operating system.
So how does the developer avoid these situations or once in them, how does the system get out of the situation? A great deal of study has gone into this subject and space does not allow a detailed review of the research. Instead, let’s consider the two most common ways that RTOSes deal with priority inversion and how each approach affects the conditions of bounded or unbounded inversion. Both of these techniques are valid and both have their pros and cons.
- Priority Inheritance Protocol – Change the priority of Task C to the same as Task A. Task A has to wait for Task C to complete, but the assumption is that at the higher priority, Task C can get more cycles that are not pre-empted and can thus complete its critical region more quickly in real-time. When Task C completes its critical region, it returns to its original priority and ownership of the shared resource’s Mutex is then assigned to the waiting Task A.
- Priority Ceiling Protocol – This method is also called Instant Inheritance Protocol. If there is a set of n tasks that use a shared resource, a Mutex is assigned to the shared resource and given a priority that is at least as high as, if not higher than, the highest priority of the n tasks in the set. When any task attempts to acquire ownership of the shared resource’s Mutex, it will be granted and its priority instantly changed to the priority of the Mutex. This action prevents any possibility of preemption by another member of the set of the shared resource’s users because all other tasks in the set are, by definition, at a lower priority than that of the current owner. Thus, there can be no tasks that are waiting to get ownership of the Mutex because they cannot get scheduled. This method effectively prevents the possibility of a priority inversion. Notice that this method also effectively deals with unbounded inversion issue because no other task (such as Task B) that has a priority between that of the lowest priority task in the set and the highest priority members of the set can get scheduled. When the owner task completes its critical region, the Mutex is released and the task returned to its original priority.
The Priority Ceiling Protocol used by other RTOSes avoids the potential problem of dealing with unbounded inversions but, since all tasks that use the same resource are permanently given the same high priority, even if they are not essential tasks, this may starve other, more important tasks.
The RTXC Quadros RTOS uses Priority Inheritance Protocol. It addresses bounded inversions and avoids the potential problem of Priority Ceiling Protocol that can starve tasks which are not part of the set.