Channels ▼

Eric Bruno

Dr. Dobb's Bloggers

What Is Priority Inversion (And How Do You Control It)?

June 13, 2011

In my recent article on real-time Java, which addresses the need to write low-latency applications that behave predictably, I mention the concept of priority inversion. In real-time system execution, this is something that needs to be avoided, as it can lead to a great deal of unpredictable behavior and unbounded latency. How? I’ll explain.

The priority-based model of execution states that a task can only be preempted by another task of higher priority. However, scenarios can arise where a lower priority task may indirectly preempt a higher priority task, in a sense inverting the priorities of the associated tasks, and violating the priority-based ordering of execution. This is called "priority inversion", and usually occurs when resource sharing is involved.

The classic example to explain priority inversion is to imagine a system with three active threads, each at three different thread priorities (see Figure 1 below). Assuming there are no other threads of higher priority in the system, thread T3, which has the highest priority, is meant to run as soon as it's released. No other thread should preempt it, nor should any other thread interfere with it since the others (T1 and T2) are all of lower priority.

Inversion

When the system begins execution, thread T1 is released and executes immediately since there are no other higher priority threads executing. Shortly after it starts, it acquires a lock on resource R1. At time t=1.5, thread T3 is released and preempts thread T1 since it's of higher priority. At time t=3, thread T2, a medium priority thread, is released but doesn't execute because higher priority thread T3 is still executing. Shortly afterward, however, thread T3 attempts to acquire a lock on resource R1, but cannot since thread T1 (a lower priority thread) still owns it. This allows thread T2 to execute in its place, which effectively violates the priority-order execution of the system, resulting in what we call priority inversion.

In this situation, thread T3 will continue to block on resource R1, for an unbounded and unknown amount of time, until thread T2 blocks (or terminates). For a real-time system, where thread T3 controls something time-critical (i.e. the ailerons on an airplane to maintain level flight), the result can be disastrous. When T2 finally does block, thread T1 will continue execution and release its lock on R1. At that point, thread T3 will preempt it, acquire its lock on R1, and continue. But it may be too late, and execution deadlines may have been missed.

Think this scenario is far fetched and unlikely to cause issues in the real world? Think again. If you do a quick search on the Mars Pathfinder, you'll discover how priority inversion nearly doomed the mission.

Priority Inheritance — A Practical Solution

There are a few solutions to the priority-inversion problem in real-time systems. One is to turn off all system interrupts, effectively halting thread preemption in the system, while critical tasks execute. However, to make this work, you cannot implement more than two thread priorities, and critical sections where resources are locked need to be very brief and tightly controlled.

Another solution is to implement priority ceilings, or priority boosting, where a lower priority thread that acquires a lock has its priority temporarily increased to help ensure that it will complete its execution, and release its lock, as quickly as possible. However, a more practical and less-invasive solution is to implement the priority inheritance protocol.

With priority inheritance, the system code that implements resource locking checks to see if a lower priority thread already owns a lock on the associated resource when a thread attempts to lock it. If one does, that owning thread's priority is temporarily increased to match that of the higher priority thread attempting to acquire the lock. As a result, the lock owner (once blocked at lower priority) will execute, release the lock, and then be restored to its original priority level.

Going back to our original example, priority inheritance would effectively boost thread T1's priority to equal that of thread T3, where thread T2 would continue to block, allowing T1 to release its lock sooner. In Figure 2, you can see how this allows thread T3 to resume sooner, without the unbounded latency caused by thread T2's unknown execution time. Once the lock on R1 is released by thread T1, its priority is restored to its original value and the system executes according to normal priority-based rules.

Inheritance

Let's take a look at how this problem can be avoided.

Priority Inheritance In Action

To illustrate priority inheritance in an actual system as it executes, let's examine a sample implementation in real-time Java, taken from my book Real-Time Java Programming with Java RTS. To run this example, you'll need a Java VM that's compliant with (or at least compatible with) the Real-Time Specification for Java (RTSJ) such as Oracle's Java Real-Time System, or IBM's WebSphere RT, running on a real-time capable OS that obeys thread priority execution. My development environment consists of Solaris 10 with the research version of Oracle's Java RTS installed. Recent Linux kernels can be used as well, so long as the RT_PREEMPT package is installed.

In my sample application, there are three classes named LowPriority, MedPriority, and HighPriority, each of which extends the RTSJ RealtimeThread (RTT) class. As their names imply, each RTT runs at low priority, medium priority, and high priority, respectively.

package priorityinversion;
import javax.realtime.*;
public class Main extends RealtimeThread {
    static public Object lock = new Object();
    class HighPriority extends RealtimeThread {
        public HighPriority() {
            // set priority to high
            int pri = PriorityScheduler.instance().getMaxPriority() - 1;
            PriorityParameters sched =
                new PriorityParameters(pri);
            this.setSchedulingParameters(sched);
        }
        public void run() {
            System.out.println("H\t\t\tGetting Lock");
            synchronized ( lock ) {
                for ( int i = 0; i < 100; i++ ) {
                    System.out.println("H\t\t\t*");
                }
                System.out.println("L\tReleasing Lock");
            }
            System.out.println("H\t\t\tTERM");
        }
    }
    
    class MedPriority extends RealtimeThread {
        public MedPriority() {
            // set priority to mid-point
            int hi = PriorityScheduler.instance().getMaxPriority();
            int lo = PriorityScheduler.instance().getMinPriority();
            PriorityParameters sched =
                new PriorityParameters((hi-lo)/2);
            this.setSchedulingParameters(sched);
        }
        public void run() {
            for ( int i = 0; i < 100; i++ ) {
                System.out.println("M\t\t*");
            }
            System.out.println("M\t\tTERM");
        }
    }

    class LowPriority extends RealtimeThread {
        public LowPriority() {
            // set priority to lowest
            int pri = PriorityScheduler.instance().getMinPriority();
            //System.out.println("LowPriority at pri=" + pri);
            PriorityParameters sched =
                new PriorityParameters(pri);
            this.setSchedulingParameters(sched);
        }
        public void run() {
            System.out.println("L\tGetting Lock");
            synchronized ( lock ) {
                for ( int i = 0; i < 100; i++ ) {
                    System.out.println("L\t*");
                }
                System.out.println("L\tReleasing Lock");
            }
            System.out.println("L\tTERM");
        }
    }

    public Main() {
        // set priority to highest
        int pri = PriorityScheduler.instance().getMaxPriority();
        PriorityParameters sched =
            new PriorityParameters(pri);
        this.setSchedulingParameters(sched);
    }
    
    public void run() {
        LowPriority low = new LowPriority();
        MedPriority med = new MedPriority();
        HighPriority high = new HighPriority();

        low.start();
        System.out.println("Main: LowPriority STARTED");
        
        System.out.println("Main: Yielding for .5 milliseconds");
        RelativeTime abs = new RelativeTime(0,600000);
        try {this.sleep(abs);} catch( Exception e ) { }
        
        med.start();
        System.out.println("Main: MedPriority STARTED");
        
        high.start();
        System.out.println("Main: HighPriority STARTED");
    }
    
    public static void main(String[] args) {
        Main app = new Main();
        app.start();
    }
}

The classes HighPriority and LowPriority both share access to a shared resource (via synchronized) , named lock. For the sake of this example, the low-priority thread is created first in the application's run method and the application yields for 0.5 milliseconds before starting the medium- and high-priority threads. This gives the low-priority thread a chance to execute long enough to acquire a lock on the shared object and execute for a short time.

Next, when the remaining threads are started, the high-priority thread attempts to lock the shared object and is blocked. At this point in time, the priority inheritance protocol takes effect, and raises the low priority thread's priority to equal the high-priority thread. If the VM didn't do this, both the high-priority thread and the low-priority thread would have to wait for the medium-priority thread to run before further progress is made. Instead, the result is that the low-priority thread gets to release its lock on the shared object sooner, allowing the high-priority thread to run, and then the medium-priority thread, as priority-based execution rules suggest they should.

The output below demonstrates this code in action:

Main: LowPriority STARTED
Main: Yielding for .5 milliseconds
L    Getting Lock
L    *
L    *
L    *
L    *
L    *
L    *
L    *
L    *
Main: MedPriority STARTED
Main: HighPriority STARTED
H            Getting Lock
L    *
L    *
L    *
L    *
 ...
L    *
L    Releasing Lock
H            *
H            *
H            *
H            *
 ...
H            *
H            Releasing Lock
H            TERM
M        *
M        *
M        *
M        *
 ...
M        *
M        TERM
L    TERM

Note: Some lines have been omitted (indicated by an ellipsis).

Here, you can see the output for each thread preceded by a letter that represents its name: L = low-priority thread, M = medium-priority thread, and H = high-priority thread. An asterisk is printed with each iteration through each thread's run loop, and each thread's output is tabbed differently to help it line up appropriately. Threads H and L print a message when they attempt to acquire, and then release, a lock on the shared object. Finally, each thread outputs the message, "TERM," upon termination.

Here are the important steps in execution:

  1. L acquires a lock on the shared object immediately and executes a few times through its loop
  2. Threads M and H are released

  3. H begins execution (higher priority)

  4. H tries to get a lock on the shared object, but it cannot since L owns it

  5. Priority inheritance elevates L's priority to run at H's priority

  6. L continues to run to completion (some of the output has been truncated to save space), and then releases its lock

  7. Immediately afterward, H is unblocked, and runs to completion

  8. Finally, after H terminates, M runs to completion

  9. M and L both terminate in that order due to priority

And there you have the priority inheritance protocol helping to avoid the problem of priority inversion in a real-time system.

Happy coding!
-EJB

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video