Priority Inversion

Introduction

In this codelab, we will learn what the priority inversion phenomenon is and experience it using a simple Mbed OS application. You will thus better understand the influence of shared resources on task scheduling.

What you’ll build

In this codelab, you’re going to program a simple program using multiple threads that demonstrates the problem of priority inversion.

What you’ll learn

How Mbed OS handles priority inversion, by experiencing the Priority Inheritance Protocol algorithm.
What the influence of shared resources can have on task scheduling.

What you’ll need

Mbed Studio for developing and debugging your program in C++.
The Multi-tasking under MbedOS codelab is a prerequisite to this codelab.

Shared Resources and Scheduling

In the preceding lectures and codelabs, when considering scheduling algorithms, we have always assumed that tasks are independent and do not share resources. This is of course rarely the case, since in multitasking programs tasks very often need to share resources (e.g. data) and are thus dependent from each other. With dependent tasks, some problems may arise:

Priority inversion: it is a situation where a task of higher priority must wait for tasks of lower priority. For preventing such situations, a protocol must be defined for a correct use of resources that allows the program to meet task deadlines. In any case, the task response time is modified.
Deadlock: it is a situation where two or more threads wait for each other to complete the task. In a deadlock situation, the threads will only hang up but never stop or finish their task.
Starvation: starvation is a phenomenon related to deadlock. A deadlock can cause starvation. In order to get out from a deadlock, one of the threads should have to give up a resource so that the other threads can use the resource. If this continuously happens and the same thread has to give up each time while letting other threads use the resource, then the selected thread, which gave up the resource, undergoes a situation called starvation.

The problem of deadlock has already been demonstrated in the multi-tasking codelab. In this codelab, we demonstrate the priority inversion situation with a simple example.

What is Priority Inversion?

The priority inversion phenomenon is illustrated in the figure below:

Priority Inversion Phenomenon (simplest form)

This figure illustrates the case where:

Task 2 is executing and entering the critical section a where it uses a shared resource.
Task 2 is preempted by Task 1, which has higher priority.
Task 1 is executing and after some time trying to enter the critical section a. However, this section is locked by Task 2. So Task 1 is moving from Running to Blocked/Waiting state.
Task 2 is executing again after Task 1 enters the Blocked state. At some point, it exits the critical section. At this point, Task 1 is signaled and preempts Task 2 again. Task 1 enters the critical section and terminates.
After Task 1 terminates, Task 2 executes again until it is finished.

This case is the simplest form of priority inversion. In this particular case, the additional delay caused to the completion of Task 1 is bounded by the time that Task 2 will spend in the execution of the critical section. However, in the most general scenario, this delay becomes unbounded. This is illustrated in the figure below:

Priority Inversion Phenomenon (unbounded form)

In the case illustrated above, the situation is similar to the previous one, except that another task Task 2 will preempt Task 3 before it releases the critical section. Since this can repeat for an unbounded number of times and for an unbounded time, the delay caused to the completion of Task 1, which is the task with the highest priority, becomes unbounded.

For preventing such situations, schedulers must implement mechanisms that force tasks to follow certain rules when requesting and releasing resources. These rules are usually called Resource access protocols. Most protocols have been developed for tasks with fixed priorities.

The goal of this codelab is not to study these protocols in details, but rather to we can mention a few of them:

Non-preemptive protocol: when entering a critical section with success, the task is assigned the highest priority and thus becomes non-preemptable. The task gets its original priority again when exiting the critical section. This protocol is also called Interrupt-Masking Protocol, since it implements a behavior where interrupts are masked.
Basic Priority Inheritance Protocol: whenever a task with lower priority blocks a task with higher priority, it inherits the priority of the blocked task.
Immediate Priority Inheritance Protocol: whenever a task enters a critical section, it inherits the highest priority of all tasks that uses the critical section. This priority can be calculated statically.

Non-preemptive Protocol

An illustration of how the Non-preemptive Protocol (NPP) prevents priority inversion is shown below:

In this example, we can observe that:

Task 3 gets the highest possible priority as soon as it enters the critical section.
Task 1 that should starts execution at time \(t_{1}\), but it cannot preempt Task 3 anymore. It rather starts at time \(t_{2}\) after Task 3 releases the critical section and is assigned its own original priority.
As soon as the critical section is release, Task 1 starts its execution. It can then lock the critical section and execute until completion.
Task 2 is ready for execution at time \(t_{3}\), but since Task 1 is already executing with higher priority, it has to wait until Task 1 completes (at time \(t_{4}\)).
When Task 2 completes, Task 3 with lower priority can resume.

Exercice

Exercice Priority Inversion/1

The NPP algorithm may lead to unnecessary blocking, meaning that it can block tasks with higher priorities even if those tasks do not require an access to a critical section. Illustrate with an example how this may happen.

Solution

In the scenario depicted below:

Task 2 is ready to execute while Task 3 still holds the critical section. However, Task 2 has a higher priority and does not require access to the critical section.

Exercice

Exercice Priority Inversion/2

Explain why with NPP the blocking time of a higher priority task is limited to the maximum length of any single critical section belonging to lower priority tasks.

Solution

Since a task that holds the critical section cannot be preempted, only one critical section can be locked at a given time. This means that as soon as the critical section will be released, then the task with higher priority will be able to run.

Priority-inheritance Protocol

The Priority Inheritance Protocol (PIP) can be defined as follows:

Tasks are scheduled based on their active priorities.
When a task tries to enter a critical section that is already held by a lower-priority task, then the task of higher priority is blocked. In this case, it transmits its active priority to the task of lower priority that holds the critical section.
Hence, the task of lower priority resumes and executes the rest of its critical section with a higher priority (the inherited priority). When this task exits the critical section, the highest-priority task that was blocked for entering the critical section preempts the lower-priority task. The priority of the task is set back to its nominal priority or to the highest priority of the tasks still blocked for entering the critical section.
Priority inheritance is transitive; that is, if a task Task 3 blocks a task Task 2, and Task 2 blocks a task Task 1, then Task 3 inherits the priority of Task 1 via Task 2.

The principle of PIP is illustrated in the figure below:

PIP preventing unbounded priority inversion

As you can see from this illustration, PIP prevents unbounded priority inversion, but it does not prevent unnecessary blocking - in this example, Task 2 is blocked by Task 1, while it does not require access to the critical section. However, with PIP, unnecessary blocking may not happen for tasks that have a higher priority than the task with highest priority accessing the critical section - remember that this was not the case with NPP.

Two other important advantages/characteritiscs of PIP are that:

the blocking time duration of a task is limited with a bound that depends on the number of critical sections used by this task and on the number of lower-priority tasks that can block this task;
there exists an (non-trivial) algorithm for computing the blocking time duration based on the number of critical sections used by the task and on the number of lower-priority tasks that can block this task.

However, PIP does not solve the following problems:

Deadlock is still possible.
Chained blocking is still possible. This happens when a task of higher priority is blocked by several tasks of lower priority, as illustrated below:

Exercice

Exercice Priority Inversion/3

PIP does not prevent deadlock situations. Draw a time diagram with two tasks accessing critical sections for illustrating this situation. Recall the Coffman conditions for deadlock!

Solution

Mbed OS and Priority Inversion

To prevent priority inversions, CMSIS-RTOS RTX implements a Priority Inheritance Protocol for the Mutexes. A lower-priority thread inherits the priority of any higher-priority thread that is waiting (with osMutexWait) on a shared resource. During the time the higher-priority thread is in WAITING state, the lower-priority thread runs at the same priority of the higher-priority pending thread. When the lower-priority thread stops to share a resource (with osMutexRelease), the original priority is assigned to this thread again.

For illustrating the protocol used for the Mutexes in Mbed OS, we can use the program below:

multi-tasking/priority_inversion.hpp

// Copyright 2022 Haute école d'ingénierie et d'architecture de Fribourg
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/****************************************************************************
 * @file priority_inversion.hpp
 * @author Serge Ayer <serge.ayer@hefr.ch>
 *
 * @brief Consumer class used for demonstrating priority inversion
 * @date 2022-09-01
 * @version 0.1.0
 ***************************************************************************/

#pragma once

#include "mbed.h"

#include "mbed_trace.h"

#if MBED_CONF_MBED_TRACE_ENABLE
#define TRACE_GROUP "PriorityInversion"
#endif // MBED_CONF_MBED_TRACE_ENABLE

namespace multi_tasking {

class PriorityInversion {
public:    
    // time that the threads should spend processing (e.g. wait in our case)
    static constexpr std::chrono::microseconds kProcessingWaitTime = 1000000us;

    PriorityInversion(osPriority priority, const char *threadName) :
        _thread(priority, OS_STACK_SIZE, nullptr, threadName) {
    }

    void start() {
        osStatus status = 
        _thread.start(callback(this, &PriorityInversion::execute));
        tr_debug("Thread %s started with status %d", _thread.get_name(), status);
    }

    void wait() {
        _thread.join();
    }

private:
    void execute() {
        tr_debug("Thread %s about to start processing with priority %d", 
                 _thread.get_name(), _thread.get_priority());

        // perform some operations
        wait_us(kProcessingWaitTime.count());

        tr_debug("Thread %s about to enter critical section with priority %d", 
                 _thread.get_name(), _thread.get_priority());

        // enter the critical section
        _mutex.lock();

        tr_debug("Thread %s entered critical section, priority %d",
                 _thread.get_name(), _thread.get_priority());

        // perform some operations
        wait_us(kProcessingWaitTime.count());

        tr_debug("Thread %s about to exit critical section, priority %d", 
                 _thread.get_name(), _thread.get_priority());

        // exit the critical section
        _mutex.unlock();

        tr_debug("Thread %s exited critical section, priority %d",
                 _thread.get_name(), _thread.get_priority());
    }

    Thread _thread;
    // the mutex must be declared as static for being a class instance
    static Mutex _mutex;
};

} // namespace multi_tasking

multi-tasking/main_priority_inversion.cpp

// Copyright 2022 Haute école d'ingénierie et d'architecture de Fribourg
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/****************************************************************************
 * @file main.cpp
 * @author Serge Ayer <serge.ayer@hefr.ch>
 *
 * @brief main function for demonstrating Priority Inversion
 * @date 2022-09-01
 * @version 0.1.0
 ***************************************************************************/

#include "mbed.h"
#include "mbed_trace.h"
#include "priority_inversion.hpp"
#if MBED_CONF_MBED_TRACE_ENABLE
#undef TRACE_GROUP
#define TRACE_GROUP "main"
#endif  // MBED_CONF_MBED_TRACE_ENABLE

// declare static variables
Mutex multi_tasking::PriorityInversion::_mutex;

int main() {
    // use trace library for console output
    mbed_trace_init();

    tr_debug("Priority inversion program started");

    // create a PriorityInversion instance with normal priority
    multi_tasking::PriorityInversion priorityNormal(osPriorityNormal, "NPThread");
    priorityNormal.start();

    // wait for normal priority thread to enter the critical section
    wait_us(multi_tasking::PriorityInversion::kProcessingWaitTime.count() * 2);

    // create a PriorityInversion instance with higher priority
    multi_tasking::PriorityInversion priorityAboveNormal(osPriorityAboveNormal,
                                                         "HPThread");
    priorityAboveNormal.start();

    // wait for both threads to terminate
    priorityNormal.wait();
    priorityAboveNormal.wait();

    return 0;
}

Priority inversion program

[DBG ][main]: Priority inversion program started
[DBG ][PriorityInversion]: Thread NPThread started with status 0
[DBG ][PriorityInversion]: Thread NPThread about to start processing with priority 24
[DBG ][PriorityInversion]: Thread NPThread about to enter critical section with priority 24
[DBG ][PriorityInversion]: Thread NPThread entered critical section, priority 24
[DBG ][PriorityInversion]: Thread HPThread about to start processing with priority 32
[DBG ][PriorityInversion]: Thread HPThread about to enter critical section with priority 32
[DBG ][PriorityInversion]: Thread NPThread about to exit critical section, priority 32
[DBG ][PriorityInversion]: Thread HPThread entered critical section, priority 32
[DBG ][PriorityInversion]: Thread HPThread about to exit critical section, priority 32
[DBG ][PriorityInversion]: Thread HPThread exited critical section, priority 32
[DBG ][PriorityInversion]: Thread NPThread exited critical section, priority 24
[DBG ][PriorityInversion]: Thread HPThread started with status 0

From this output, we can observe that the normal priority thread enters the critical section with priority 24 but then runs at the same priority (32) as the higher priority thread, when this higher priority thread tries to acquire the critical section. It then moves again to its original priority (24) when it exits the critical section. Note as well that the main thread (running at normal priority) only gets scheduled when all other threads are done.

Summary

Priority inversion is an important problem, especially when programming real-time systems. This is the reason why resource access protocols have been developed. The main objectives of these protocols are:

bound the blocking time;
prevent chained blocking;
prevent deadlock situations.

In addition, preferred protocols are the ones that:

do not cause unnecessary blocking;
block only on access to the critical section rather than on preemption/task arrival;
are transparent to implement, meaning that they can be used without changing RTOS primitives like Mutex;
are easy to implement.

All resource access protocols are designed to bound the blocking time. But they differ when compared on other properties. The table below summarizes the characteristics of the resource access protocols presented in the lecture and in this codelab:

Algorithm	Chained blocking	Unnecessary Blocking	Blocking instant	Deadlock prevention	Transparency	Implementation
*NPP*	no	yes	on arrival	yes	yes	easy
*PIP*	yes	limited	on access	no	yes	medium
*HLP*	no	yes	on arrival	yes	no	medium

Without going into more details on the priority inversion phenomenon, it is important to point out that the delay caused to higher priority tasks by lower priority tasks depends on the execution time of the critical sections. This is one more motivation for keeping critical sections as short as possible.