How to use priority inheritance

Kyle Renwick and Bill Renwick

5/18/2004 1:00 PM EDT

A preemptive real-time operating system(RTOS) forms the backbone of most embedded systems devices, fromdigital cameras to life-saving medical equipment. The RTOS can schedulean application's activities so that they appear to occursimultaneously. By rapidly switching from one activity to the next, theRTOS is able to quickly respond to real-world events.

To ensure rapid response times, anembedded RTOS can use preemption, in which a higher-priority task caninterrupt a low-priority task that's running. When the high-prioritytask finishes running, the low-priority task resumes executing from thepoint at which it was interrupted. The use of preemption guaranteesworst-case performance times, which enable use of the application insafety-critical situations.

Unfortunately, the need to shareresources between tasks operating in a preemptive multitaskingenvironment can create conflicts. Two of the most common problems aredeadlock and priority inversion, both of which can result inapplication failure. In 1997, the Mars Pathfinder mission nearly failedbecause of an undetected priority inversion. When the rover wascollecting meteorological data on Mars, it began experiencing systemresets, losing data. The problem was traced to priority inversion. Asolution to the inversion was developed and uploaded to the rover, andthe mission completed successfully. Such a situation might have beenavoided had the designers of the rover accounted for the possibility ofpriority inversion.¹

This article describes in detail theproblem of priority inversion and indicates two common solutions. Alsoprovided are detailed strategies for avoiding priority inversion.Avoiding priority inversion is preferable to most other solutions,which generally require more code, more memory, and more overhead whenaccessing shared resources.

Priority inversion
Priorityinversion occurs when a high-priority task is forced to wait for therelease of a shared resource owned by a lower-priority task. The twotypes of priority inversion, bounded and unbounded, occur when twotasks attempt to access a single shared resource. A shared resource canbe anything that must be used by two or more tasks in a mutuallyexclusive fashion. The period of time that a task has a lock on ashared resource is called the task's critical section or criticalregion.

Figure 1: Bounded priority inversion

Bounded priority inversion, shownin Figure 1, occurs when low-priority Task L acquires a lock on ashared resource, but before releasing the resource is preempted byhigh-priority Task H.² Task Hattempts to acquire the resource but is forced to wait for Task L tofinish its critical section. Task L continues running until it releasesthe resource, at which point Task H acquires the resource and resumesexecuting. The worst-case wait time for Task H is equal to the lengthof the critical section of Task L. Bounded priority inversion won'tgenerally hurt an application provided the critical section of Task Lexecutes in a timely manner.

Figure 2: Unbounded priority inversion

Unbounded priority inversion, shown in Figure 2, occurs when an intervening task extends a bounded priority inversion, possibly forever.²In the previous example, suppose medium-priority Task M preempts Task Lduring the execution of Task L's critical section. Task M runs until itrelinquishes control of the processor. Only when Task M turns overcontrol can Task L finish executing its critical section and releasethe shared resource. This extension of the critical region leads tounbounded priority inversion. When Task L releases the resource, Task Hcan finally acquire the resource and resume execution. The worst-casewait time for Task H is now equal to the sum of the worst-caseexecution times of Task M and the critical section of Task L. Unboundedpriority inversion can have much more severe consequences than abounded priority inversion. If Task M runs indefinitely, neither Task Lnor Task H will get an opportunity to resume execution.

Figure 3: Chain of nested resource locks

Priority inversion can have an even more severe effect on an application when there are nested resource locks,as shown in Figure 3. Suppose Task 1 is waiting for Resource A.Resource A is owned by lower-priority Task 2, which is waiting forResource B. Resource B is owned by still lower-priority Task 3, whichis waiting for Resource C, which is being used by an even lowerpriority Task 4. Task 1 is blocked, forced to wait for tasks 4, 3, and2 to finish their critical regions before it can begin execution. Sucha chain of nested locks is difficult to resolve quickly andefficiently. The risk of an unbounded priority inversion is also highif many tasks intervene between tasks 1 and 4.

Figure 4: Deadlock

Deadlock
Deadlock, shown in Figure 4, is a special case of nestedresource locks, in which a circular chain of tasks waiting forresources prevents all the tasks in the chain from executing.²Deadlocked tasks can have potentially fatal consequences for theapplication. Suppose Task A is waiting for a resource held by Task B,while Task B is waiting for a resource held by Task C, which is waitingfor a resource held by Task A. None of the three tasks is able toacquire the resource it needs to resume execution, so the applicationis deadlocked.

Priority ceiling protocol
One way to solve priority inversion is to use the priority ceiling protocol,which gives each shared resource a predefined priority ceiling. When atask acquires a shared resource, the task is hoisted (has its prioritytemporarily raised) to the priority ceiling of that resource. Thepriority ceiling must be higher than the highest priority of all tasksthat can access the resource, thereby ensuring that a task owning ashared resource won't be preempted by any other task attempting toaccess the same resource. When the hoisted task releases the resource,the task is returned to its original priority level. Any operatingsystem that allows task priorities to change dynamically can be used toimplement the priority ceiling protocol.³

A static analysis of the application isrequired to determine the priority ceiling for each shared resource, aprocess that is often difficult and time consuming. To perform a staticanalysis, every task that accesses each shared resource must be knownin advance. This might be difficult, or even impossible, to determinefor a complex application.

The priority ceiling protocol provides agood worst-case wait time for a high-priority task waiting for a sharedresource. The worst-case wait time is limited to the longest criticalsection of any lower-priority task that accesses the shared resource.The priority ceiling protocol prevents deadlock by stopping chains ofnested locks from developing.

On the downside, the priority ceilingprotocol has poor average-case response time because of the significantoverhead associated with implementing the protocol. Every time a sharedresource is acquired, the acquiring task must be hoisted to theresource's priority ceiling. Conversely, every time a shared resourceis released, the hoisted task's priority must be lowered to itsoriginal level. All this extra code takes time.

By hoisting the acquiring task to thepriority ceiling of the resource, the priority ceiling protocolprevents locks from being contended. Because the hoisted task has apriority higher than that of any other task that can request theresource, no task can contend the lock. A disadvantage of the priorityceiling protocol is that the priority of a task changes every time itacquires or releases a shared resource. These priority changes occureven if no other task would compete for the resource at that time.

Medium-priority tasks are oftenunnecessarily prevented from running by the priority ceiling protocol.Suppose a low-priority task acquires a resource that's shared with ahigh-priority task. The low-priority task is hoisted to the resource'spriority ceiling, above that of the high-priority task. Any tasks witha priority below the resource's priority ceiling that are ready toexecute will be prevented from doing so, even if they don't use theshared resource.

Priority inheritance protocol
An alternative to the priority ceiling protocol is the priority inheritance protocol,a variation that uses dynamic priority adjustments. When a low-prioritytask acquires a shared resource, the task continues running at itsoriginal priority level. If a high-priority task requests ownership ofthe shared resource, the low-priority task is hoisted above therequesting task. The low-priority task can then continue executing itscritical section until it releases the resource. Once the resource isreleased, the task is dropped back to its original low-priority level,permitting the high-priority task to use the resource it has justacquired.³

Because the majority of locks inreal-time applications aren't contended, the priority inheritanceprotocol has good average-case performance. When a lock isn'tcontended, priorities don't change; there is no additional overhead.However, the worst-case performance for the priority inheritanceprotocol is worse than the worst-case priority ceiling protocol, sincenested resource locks increase the wait time. The maximum duration ofthe priority inversion is the sum of the execution times of all of thenested resource locks. Furthermore, nested resource locks can lead todeadlock when you use the priority inheritance protocol. That makes itimportant to design the application so that deadlock can't occur.

Nested resource locks should obviously beavoided if possible. An inadequate or incomplete understanding of theinteractions between tasks can lead to nested resource locks. Awell-thought-out design is the best tool a programmer can use toprevent these.

You can avoid deadlock by allowing eachtask to own only one shared resource at a time. When this condition ismet, the worst-case wait time matches the priority ceiling protocol'sworst-case wait. In order to prevent misuse, some operating systemsthat implement priority inheritance don't allow nested locks. It mightnot be possible, however, to eliminate nested resource locks in someapplications without seriously complicating the application.

But remember that allowing tasks toacquire multiple priority inheritance resources can lead to deadlockand increase the worst-case wait time.

Priority inheritance is difficult toimplement, with many complicated scenarios arising when two or moretasks attempt to access the same resources. The algorithm for resolvinga long chain of nested resource locks is complex. It's possible toincur a lot of overhead as hoisting one task results in hoistinganother task, and another, until finally some task is hoisted that hasthe resources needed to run. After executing its critical section, eachhoisted task must then return to its original priority.

Figure 5 shows the simplest case of thepriority inheritance protocol in which a low-priority task acquires aresource that's then requested by a higher priority task. Figure 6shows a slightly more complex case, with a low-priority task owning aresource that's requested by two higher-priority tasks. Figure 7demonstrates the potential for complexity when three tasks compete fortwo resources.

Figure 5: Simple priority inheritance

1. Task L receives control of the processor and begins executing.
   • The task makes a request for Resource A.
2. Task L is granted ownership of Resource A and enters its critical region.
3. Task L is preempted by Task H, a higher-priority task.
   • Task H begins executing and requests ownership of Resource A, which is owned by Task L.
4. Task L is hoisted to a priority above Task H and resumes executing its critical region.
5. Task L releases Resource A and is lowered back to its original priority.
   • Task H acquires ownership of Resource A and begins executing its critical region.
6. Task H releases Resource A and continues executing normally.
7. Task H finishes executing and Task L continues executing normally.
8. Task L finishes executing.

Figure 6: Three-task, one-resource priority inheritance

1. Task 3 gets control of the processor and begins executing.
   • The task requests ownership of Resource A.
2. Task 3 acquires Resource A and begins executing its critical region.
3. Task 3 is preempted by Task 2, a higher-priority task.
   • Task 2 begins executing normally and requests Resource A, which is owned by Task 3.
4. Task 3 is hoisted to a priority above Task 2 and resumes executing its critical region.
5. Task 3 is preempted by Task 1, a higher-priority task.
   • Task 1 begins executing and requests Resource A, which is owned by Task 3.
6. Task 3 is hoisted to a priority above Task 1.
   • Task 3 resumes executing its critical region.
7. Task 3 releases Resource A and is lowered back to its original priority.
   • Task 1 acquires ownership of Resource A and begins executing its critical region.
8. Task 1 releases Resource A and continues executing normally.
9. Task 1 finishes executing. Task 2 acquires Resource A and begins executing its critical region.
10. Task 2 releases Resource A and continues executing normally.
11. Task 2 finishes executing. Task 3 resumes and continues executing normally.
12. Task 3 finishes executing.

Figure 7: Three-task, two-resource priority inheritance

1. Task 3 is given control of the processor and begins executing. The task requests Resource A.
2. Task 3 acquires ownership of Resource A and begins executing its critical region.
3. Task 3 is preempted by Task 2, a higher-priority task. Task 2 requests ownership of Resource B.
4. Task 2 is granted ownership of Resource B and begins executing its critical region.
   • The task requests ownership of Resource A, which is owned by Task 3.
5. Task 3 is hoisted to a priority above Task 2 and resumes executing its critical region.
6. Task 3 is preempted by Task 1, a higher-priority task.
   • Task 1 requests Resource B, which is owned by Task 2.
7. Task 2 is hoisted to a priority above Task 1.However, Task 2 still can't execute because it must wait for ResourceA, which is owned by Task 3.
   • Task 3 is hoisted to a priority above Task 2 and continues executing its critical region.
8. Task 3 releases Resource A and is lowered back to its original priority.
   • Task 2 acquires ownership of Resource A and resumes executing its critical region.
9. Task 2 releases Resource A and then releases Resource B. The task is lowered back to its original priority.
   • Task 1 acquires ownership of Resource B and begins executing its critical region.
10. Task 1 releases Resource B and continues executing normally.
11. Task 1 finishes executing. Task 2 resumes and continues executing normally.
12. Task 2 finishes executing. Task 3 resumes and continues executing normally.
13. Task 3 finishes executing.

Manage resource ownership
Most RTOSes that support priority inheritance require resource locks tobe properly nested, meaning the resources must be released in thereverse order to that in which they were acquired. For example, a taskthat acquired Resource A and then Resource B would be required torelease Resource B before releasing Resource A.

Figure 7 provides an example of priorityinheritance in which two resources are released in the opposite orderto that in which they were acquired. Task 2 acquired Resource A beforeResource B; Resource B was then released before Resource A. In thisexample, Task 2 was able to release the resources in the proper orderwithout adversely affecting the application.

Many operating systems require resourcesto be released in the proper order because it's difficult to implementthe capability to do otherwise. However, situations occur in whichreleasing the resources in the proper order is neither possible nordesirable. Suppose there are two shared resources: Resource B can't beacquired without first owning Resource A. At some point during theexecution of the critical region with Resource B, Resource A is nolonger needed. Ideally, Resource A would now be released.Unfortunately, many operating systems don't allow that. They requireResource A to be held until Resource B is released, at which pointResource A can be released. If a higher-priority task is waiting forResource A, the task is kept waiting unnecessarily while the resource'scurrent owner executes.

Figure 8: Managing resource ownership (example 1)

1. Task L is given control of the processor and begins executing. Task L requests Resource A.
2. Task L acquires ownership of Resource A and begins executing its critical region.
   • Task L requests Resource B.
3. Task L acquires ownership of Resource B and continues executing its critical region.
4. Task L is preempted by Task H, a higher-priority task.
   • Task H requests ownership of Resource A, which is owned by Task L.
5. Task L is hoisted above Task H and continues executing its critical region.
6. Task L releases Resource A even though it was acquired before Resource B.
   • Task L is lowered to its original priority level.
   • Task H acquires Resource A and begins executing its critical region.
   • Note that low-priority Task L no longer prevents Task H from running, even though Task L still owns Resource B.
7. Task H releases Resource A and continues executing normally.
8. Task H finishes executing and Task L continues executing its critical region.
9. Task L releases Resource B and continues executing normally.
10. Task L finishes executing.

In Figure 8, Task L releases itsresources in the same order they were acquired, which most priorityinheritance implementations wouldn't allow. Upon releasing Resource A,Task L drops to its original priority level. This allows Task H toacquire Resource A, ending the priority inversion. After Task H hasreleased the resource and stopped executing, Task L can continueexecuting with Resource B, on which it has an uncontested lock. If TaskL had been required to release Resource B before releasing Resource A,Task H would have been prevented from running until Task L had releasedboth resources. This would have unnecessarily lengthened the durationof the bounded priority inversion.

Figure 9: Managing resource ownership (example 2)

1. Task 3 is given control of the processor and begins executing. Task 3 requests Resource A.
2. Task 3 acquires ownership of Resource A and begins executing its critical region.
   • Task 3 requests Resource B.
3. Task 3 acquires ownership of Resource B and continues executing its critical region.
4. Task 3 is preempted by Task 2, a higher-priority task.
   • Task 2 requests ownership of Resource A, which is owned by Task 3.
5. Task 3 is hoisted above Task 2 and continues executing its critical region.
6. Task 3 is preempted by Task 1, a higher-priority task.
   • Task 1 requests Resource B, which is owned by Task 3.
7. Task 3 is hoisted above Task 1 and continues executing its critical region.
8. Task 3 releases Resource A and continues executing with Resource B.
   • Note that Task 3 is not dropped to either its previouspriority or its original priority. To do so would immediately produce apriority inversion that requires Task 3 to be hoisted above Task 1because Task 3 still owns Resource B.
9. Task 3 releases Resource B and is lowered to its original priority level.
   • Task 1 acquires Resource B and continues executing its critical region.
10. Task 1 releases Resource B and continues executing normally.
11. Task 1 finishes executing and Task 2 acquires Resource A. Task 2 begins executing its critical region.
12. Task 2 releases Resource A and continues executing normally.
13. Task 2 finishes executing and Task 3 continues executing normally.
14. Task 3 finishes executing.

The difficulty of implementing locks thataren't properly nested becomes apparent when three tasks compete fortwo resources, as seen in Figure 9. When Resource A is released at Time8, low-priority Task 3 remains hoisted to the highest priority. Animproperly designed priority inheritance protocol would lower Task 3 toits original priority level, which was the task's priority beforeacquiring Resource A. Task 3 would then have to be immediately hoistedabove Task 1 to avoid a priority inversion, because of the contentionfor access to Resource B. Unbounded priority inversion could occurwhile Task 3 is momentarily lowered. A medium-priority task couldpreempt Task 3, extending the priority inversion indefinitely.

The example in Figure 8 shows why it'ssometimes desirable to release nested resources "out of order," or notthe reverse of the order in which they were acquired. Although such acapability is clearly advantageous, many implementations of thepriority inheritance protocol only support sequentially nested resourcelocks.

The example in Figure 9 helps show whyit's more difficult to implement priority inheritance while allowingresources to be released in any order. If a task owns multiple sharedresources and has been hoisted several times, care must be taken whenthe task releases those resources. The task's priority must be adjustedto the appropriate level. Failure to do so may result in unboundedpriority inversion.

Avoid inversion
The best strategy for solving priority inversion is to design thesystem so that inversion can't occur. Although priority ceilings andpriority inheritance both prevent unbounded priority inversion, neitherprotocol prevents bounded priority inversion. Priority inversion,whether bounded or not, is inherently a contradiction. You don't wantto have a high-priority task wait for a low-priority task that holds ashared resource.

Prior to implementing an application,examine its overall design. If possible, avoid sharing resourcesbetween tasks at all. If no resources are shared, priority inversion isprecluded.

If several tasks do use the sameresource, consider combining them into a single task. The sub-tasks canaccess the resource through a state machine in the combined taskwithout fear of priority inversion. Unless the competing sub-tasks arefairly simple, however, the state machine might be too complex tojustify.

Another way to prevent priority inversionis to ensure that all tasks that access a common resource have the samepriority. Although one task might still wait while another task usesthe resource, no priority inversion will occur because both tasks havethe same priority. Of course, this only works if the RTOS provides anon-preemptive mechanism for gracefully switching between tasks ofequal priority.

If you can't use any of these techniquesto manage shared resources, consider giving a "server task" solepossession of the resource. The server task can then regulate access tothe resource. When a "client task" needs the resource, it must callupon the server task to perform the required operations and then waitfor the server to respond. The server task must be at a prioritygreater than that of the highest-priority client task that will accessthe resource. This method of controlling access to a resource issimilar to the priority ceiling protocol and requires static analysisto determine the priority of the server task. The method relies on RTOSmessage passing and synchronization services instead of resource locksand dynamic task-priority adjustments.

Prioritize
Priorityinversion is a serious problem that, if allowed to occur, can cause asystem to fail. It's generally simpler to avoid priority inversion thanto solve it in software. If possible, eliminate the need for sharedresources altogether, avoiding any chance of priority inversion. If youcan't avoid priority inversion, at least make sure it's bounded.Unbounded priority inversions can leave high-priority tasks unable toexecute, resulting in application failure. Two common methods ofbounding priority inversion are the priority ceiling protocol and thepriority inheritance protocol. Neither protocol is perfect for allsituations. Hence, good analysis and design are always necessary tounderstand which solution, or combination of solutions, is needed foryour particular application.

W.L. (Bill) Renwick is the founderand chief engineer of KADAK Products Ltd. He has over 40 yearsexperience in RTOS design and real-time embedded software. He earned aBS in electrical engineering from University of Waterloo, Canada, andan MS in control theory from University of London, UK. Bill can bereached at amxtech@kadak.com.

Kyle Renwick researched andauthored this article while working at KADAK as a student of SystemsEngineering at University of Waterloo. Kyle can be reached at amxtech@kadak.com.

References

1. Jones, Michael. "What really happened on Mars?"Redmond, Washington: Microsoft: 1997. http://research.microsoft.com/~mbj/Mars_Pathfinder/
2. Douglass, Bruce Powel. Design Patterns for Real-Time Systems. Boston: Addison-Wesley Professional: 2002.
3. Sha, L., R. Rajkumar, and S. Sathaye. "Priority inheritance protocols: An approach to real-time synchronization." IEEE Transactions on Computers, 39 (9), 1175-1185: 1990.