Embedded Systems -> RTOSes, 'mutexes' fight priority inversion

Modern operating systems offer several ways to deal with this problem through the use of several types of "mutexes," which are specialized kinds of semaphores. The OSes offer this capability explicitly under the name m utex, or implicitly by giving programmers the ability to change task priority on the fly.

Two of the most commonly used mutex types are priority-inheritance mutexes and priority-ceiling mutexes. It is the job of the real-time software architect to determine which kind of mutex is appropriate in each application situation.

Nowadays, priority inversions do not occur because of errors in the design of the scheduler of an operating system. Operating- system task schedulers are pretty reliable these days. Instead, they occur when the operating system has marked a task as unready to run at a moment when the software designer would have wanted it to be running.

This might occur, for example, if a task of high priority wishes to process a message arriving at a certain queue. But if the message has been given to another (lower-priority) task instead, then that other task would be allowed to run. And the operating system would block the high-priority task from running, declaring it unready to run for lack of a message to process. In this case, the operating system might well be working as designed and instructed. Perhaps instructions are being given to the operating system without their ramifications fully understood. If the software designer would declare the situation to be "Message got stolen by the wrong task," or "The high-priority task should have executed instead," then it's a priority-inversion situation.

Priority inversions can have serious consequences in a critical real-time application. In particular, a high-priority task might be delayed before executing for an unexpectedly long time. These delays might cause missed time deadlines, gaps in data acquisition or time gaps in the control of external devices. In conjunction with a watchdog timer, these delays might even trigger system resets.

A software designer has a number of ways to solve problems of unbounded priority inversion. Two simple approaches might be to turn off interrupts, to turn off task pre-emption or both. While these would solve the problem, they would also have very undesirable side effects. Disabling pre-emption would stop the execution of all other tasks, including high-priority tasks totally unrelated to the problem. Disabling interrupts would totally disconnect the computer from the outside world. These might be called "brute force" methods. They'll solve the priority-inversion problem, but can also heavily damage the behavior of the application software. They should be avoided.

A more refined approach would be to simply prevent intermediate-priority tasks from running, when low- and high-priority tasks are competing for access to the same shared resource-in other words, to prevent Tasks B and C from running, when Tasks A and D are competing for access to the printer. This can be done by a mutex, by promoting the lower-priority task to a higher priority on a temporary basis while it is accessing the resource.

There are two ways a mutex can promote a lower-priority task to a higher priority on a temporary basis while it is "owned" by the lower-priority task. These are called priority inheritance and priority ceiling.

When using priority inheritance, the operating system dynamically changes the priority of the task that "owns" a mutex, depending on the priorities of other tasks that attempt to lock the mutex.

If several tasks are competing for ownership of a mutex, the current owner will be temporarily given the priority of the highest-priority task competin g for ownership. The net result is that intermediate-priority tasks will be prevented from slowing the release of ownership from the current owner to waiting new owners.

The other way to bound priority inversion is to assign each mutex a ceiling priority. This should be at least as high as the highest-priority task that ever works with this mutex. Whenever a task locks a mutex, its priority is automatically raised to the ceiling priority for that mutex.

In other words, when any task locks a mutex, its priority is raised to the level, or above that, of all tasks that may want to lock the mutex. The net result is, once again, that intermediate-priority tasks will be prevented from slowing the release of ownership from the current owner to waiting new owners.

Both kinds of mutexes elegantly solve the problem of unbounded priority inversion. But each has advantages and disadvantages.

Priority-inheritance mutexes adjust the priorities of tasks automatically, requiring no involvemen t from the application software developers. On the other hand, priority-ceiling mutexes require application software developers to identify the ceiling priority for the mutex when each mutex is created. If tasks change priorities dynamically, the required ceiling may not be easy to identify. It must be the highest priority at which any task may request to lock the mutex at any time.

Most multitasking applications do not change the priorities of tasks dynamically. For those applications, the priority ceiling should simply be the priority of the highest-priority task that may request to lock the mutex.

In many cases priority-inheritance mutexes may result in more task switches. The impact of this tendency depends on the application software; but in all cases lowering the number of task switches will lower operating-system overhead.

If multiple mutexes need to be locked by a given task, then mutual deadlocks may develop. These are circular relations between several tasks and several mute xes, which may cause some tasks to become blocked forever. Priority-inheritance mutexes are prone to mutual deadlocks. Priority-ceiling mutexes are immune to them. Hence, it is strongly recommended that priority-ceiling mutexes be used in applications where multiple mutexes need to be locked by a given task at the same time.

Another difference between the two kinds of mutexes relates to analysis of the timing behavior of a multitasking software system. There is no significant difference in the timing behavior of the operating-system services themselves for the two kinds of mutexes. But it is easier to make timing calculations for multitasking applications using priority-ceiling mutexes. That's because priority-inheritance mutexes change task priorities based upon dynamic situations as they develop, while priority-ceiling mutexes change a task's priority in a fixed way whenever it locks the mutex.

The complete version of this article will be presented at ESC.