A mutex implementing the priority inheritance mutex algorithm is an essential feature of an RTOS. But this algorithm is complex and this article presents the algorithm used by AdAstra-RTK. It also exposes some information that must be known to use a mutex wisely, and to evaluate a mutex implementation.
In what follows, we will talk about tasks and their priorities. By convention, the name given to these tasks gives their priority, for example task T3 with priority 3, which is higher than the priority of T1.
Why using a mutex?
In a real-time kernel, the execution of tasks is subject to preemption: the highest priority task ready to execute is always chosen to execute. This is the absolute rule for an RTOS with task priority management and a preemptive scheduler.
This means that a T1 priority task can be interrupted at any time to allow a higher priority task T3 which becomes ready to run. If task T1 has an R resource shared with task T3, this becomes problematic: the state of the R resource is unknown to task T3 when it activates. To manage this, we make the use of the resource exclusive with a mutex M.
A task must request and obtain the M mutex before it can use the R resource exclusively. If M cannot be obtained, because it is already held by another task, the task is put in a waiting state until the mutex is assigned to it (or the expiry of a timeout, but this is another story…). As soon as the use of the R resource is finished the M mutex is released, and the highest priority task waiting for that mutex gets it.
How a mutex works
Example of how mutex works in the case of 2 tasks which share a single resource.
- T1 gets the mutex (Take) et continue its execution.
- T3 se wake up, preempt T1 and runs.
- T3 takes the mutex. As it is already held by T1, T3 is put in a waiting state, and T1 resumes execution.
- T1 releases the mutex (Give). T3 obtains it immediately (Take) and preempt T1.
- T3 releases the mutex (Give) and continue to execute.
- T3 goes in a waiting state and T1 resumes execution.
We see that between 3 and 4 the task T3 is forced to wait for T1 to release the mutex. This is a sort of priority reversal since T3 is ready to execute but T1 is preventing it since it own the mutex. This is inevitable and the mutex is there to handle these situations. Note that the wait is limited since T3 is executed as soon as T1 releases the mutex in 4. Here we see why it is recommended to minimize the duration of the exclusive region by acquiring the mutex as late as possible and releasing it as soon as possible.
Priority reversal
Consider the case of two tasks T1 and T3 which share a resource protected by the mutex M, and a third task T2 unrelated to the resource.
- T1 gets the mutex (Take) and continue to run.
- T3 wakes up, preempt T1 and runs.
- T2 becomes ready but cannot be executed since it has a lower priority than the active task T3.
- T3 requests the mutex. Since it is already owned by T1, T3 is put in waiting state. T2 which is ready at this time resumes execution.
- T2 falls asleep and T1 resumes execution.
- T1 releases the mutex (Give). T3 obtains it immediately (Take) and preempt T1.
- T3 releases the mutex (Give) and continues its execution
We can see that the wait time of T3 is extended from the execution time of T2. Task T2 prevented T3 from running even though it has a lower priority than T3, and is not using the resource requested by T3. This can become serious for the application because several lower priority tasks can prevent a task from running for an indefinite period of time.
This is a violation of the principle of running an RTOS with priority management and a preemptive scheduler. This is called a priority reversal.
There are methods to avoid the priority reversal phenomenon, for example:
- Design the application so that there is no possibility of reversing priorities. For example by making all the tasks which use the same resource has the same priority. In practice, this is often not possible because the analysis of the application can be very complex, and it is difficult to prove that there will not be priority reversal.
- The priority ceiling algorithm. This consists of raising the priority of the task that owns the mutex to a predefined priority while the mutex is held. This predefined priority must be higher than the priority of all tasks that may use the mutex. Here too you have to do a detailed analysis of the application and know in advance the priority of all the tasks.
- The priority inheritance algorithm. It is this algorithm that we will present now.
The principle of priority inheritance
This method uses a task priority dynamic adjustment. When the task T1 gets a mutex, it continues to run with its base priority. When a higher priority T3 task tries to get the mutex, the priority of T1 is raised to the level of T3, this is called priority inheritance. The T3 priority is inherited by T1 until the mutex is released by T1 and therefore obtained by T3. At this time T1 returns to its basic priority. This speeds up the execution of T1, and prevents a medium priority task from executing.
A task L inherits a higher priority only if another task H of higher priority waits for a resource owned by L, until the resource is released by L.
Consider the case of two tasks T1 and T3 which share a resource protected by the mutex M, and a third task T2 unrelated to the resource. The mutex uses priority inheritance.
- T1 gets the mutex (Take) and continues its execution.
- T3 wakes up, preempt T1 and resumes execution.
- T3 requests the mutex. Since it is already owned by T1, T3 is put in waiting state. The priority of T1 is increased to that of T3 and T1 resumes its execution: T1 inherits the T3 priority.
- T2 becomes ready, but is put in waiting state since T1 is running with the priority of T3.
- T1 releases the mutex (Give), T1 returns to its basic priority. T3 immediately obtains the mutex (Take) and preempt T1.
- T3 releases the mutex (Give) and continues its execution.
- T3 falls asleep and T2 resumes execution.
- T2 falls asleep and T1 resumes execution.
Note that the timing of T1 and T3 when they are in possession of the mutex are exactly the same as when there are only T1 and T3. The T2 execution cannot be inserted between.
The priority inheritance mutex algorithm
The principle of priority inheritance is simple, but its implementation is very complex. This is why some implementations only consider a subset of the possibilities. We will try to gradually introduce the cases to be managed.
The simple case
First, the case of 3 tasks using a single resource, and therefore a single mutex.
- T1 gets the mutex (Take) and continue to execute
- T2 wakes up, preempt T1 and continue to exucute.
- T2 requests the mutex which is already owned by T1 so T2 goes in waiting state. The priority of the task which owns the mutex must be recalculated: T1 takes the highest priority among the tasks waiting for the mutex, therefore T2. T1 resumes execution with inherited priority 2.
- T3 wakes up, preempt T1 and resumes execution.
- T3 requests for the mutex which is already owned by T1 so T3 goes in waiting state. The priority of the task that owns the mutex must be recalculated: T1 takes the highest priority among the tasks waiting for the mutex, therefore T3. T1 resumes execution with priority 3.
- T1 releases the mutex (Give), and returns to its basic priority. The mutex is assigned to the highest priority task waiting for the mutex, therefore T3, so T3 becomes ready to run. T3 preempts T1 and resumes execution.
- T3 releases the mutex (Give). The mutex is assigned to the highest priority task waiting for the mutex so T2 becomes ready to run and recovers its basic priority 2. T2 cannot run because higher priority T3 continues to run
- T3 falls asleep and T2 resumes execution.
- T2 releases the mutex which is not expected by anyone, T2 continues its execution.
- T2 falls asleep, and T1 resumes execution.
The algorithm in this case consists of 2 phases:
- When requesting the mutex, if the task cannot obtain it, the priority of the task that owns the mutex must be re-evaluated.
- When the task that owns the mutex releases it, it gives it to the waiting task with the highest priority if there is one. Then it gets its basic priority back if it had inherited a higher priority.
Additional points:
- If the priority of a task waiting for a mutex is changed, the priority of the task owning this mutex must be re-evaluated: If the new priority is higher than the priority of the mutex owning task, it will therefore be necessary for the mutex owning task to inherits the new priority. Conversely, if the new priority has dropped, the inherited priority may no longer be the correct one.
- If the wait for the mutex ends with a timeout, the priority of the mutex owning task must be re-evaluated. The owner task could have inherited the priority of the task in timeout.
- If a task waiting for a mutex is destroyed, and the mutex owner task has inherited the priority of the destroyed task, the priority of the owner task must be re-evaluated.
The general case
We have seen the simple case where a single mutex can be acquired by several tasks. Fortunately, this is the most common case, which can be treated quickly.
In the general case, the tasks can each acquire several mutexes: for example to acquire the exclusivity of two resources to be used simultaneously.
In this general case, determining the priority inherited by a task owning more than one mutexe is more complex. In fact, we must ensure that at all times each task has exactly the priority it should have.
The algorithms that handle this use the following resources:
- Each task maintains a list of owned mutexes
- Each mutex maintains a list of tasks waiting for that mutex
The mutex request
Consider the task T3 which tries to get the mutex M1, which is owned by the task T2. The task T2 has a lower priority than T3, so T2 inherits its priority from T3.
The task T2 can itself be waiting for the mutex M2 owned by a task T1. It is therefore necessary to consider whether the priority of T3 must also be propagated to T1: this must be done if the priority of T1 is lower than the pririty of T3. Then look if T1 is waiting for a mutex… And so on.
We thus walk through a chain of tasks to propagate the priority of T3 until we find a task whose priority is higher than that of T3 or which does not wait for a mutex.
Changing the priority of a task is not easy: you have to move the task to the ordered by priority list in which it may be placed (waiting for mutex, or semaphore or message queue), or place it in the new priority ready list.
The acquisition of a mutex can lead to the change of priority of several tasks, and therefore involve many list manipulations.
The mutex release
When a task releases a mutex, there is no longer any reason for it to inherit the priority of another task waiting for this mutex. A priori it must regain its basic priority.
However, if the task own other mutexes expected by other tasks, it may need to inherit the priority of one of these waiting tasks.
To determine the priority of a task that releases a mutex, you must :
- Browse the list of owned mutexes
- For each of them determine if some tasks await this mutex
- Select the highest priority of these waiting tasks.
- If the selected priority is higher than the base priority of the task releasing the mutex, this task inherits the selected priority. Otherwise it takes its base priority
It is obvious that determining the priority of a task releasing a mutex is not easy, and again involves many list manipulations.
Additional points
Priority inheritance does not only affect the Take and Give functions of the mutex. Other features are impacted.
Changing the priority of a task
RTOS often have a feature that allows you to change the priority of a task. To change the priority of a task you must:
- Recalculate the inherited priority of the task, because some other tasks may be waiting for the mutexes it own (Algorithm for releasing mutexes).
- If the task is waiting for a mutex, it may be necessary to propagate its priority to the task owning the mutex (Mutex acquisition algorithm).
Timout
If a task awaiting mutex times out, and therefore wakes up without acquiring the mutex, there is no longer any reason for the task that owns the mutex to inherit the priority of the task that is timed out. The same algorithm as for the release of the mutex is used.
Destroying a task
If a task waiting for a mutex is destroyed, and the mutex owner task has inherited the priority of the destroyed task, the priority of the owner task must be re-evaluated. The same algorithm as for the release of the mutex is used
There is also the case of destroying an active task which own a mutex. It’s not a good thing to do this: what happens to the mutex? Should we release it? So what is the state of the resource protected by the mutex? Each RTOS has different answers.
Conclusion
A mutex implementing the priority inheritance algorithm is a very complex object, which has implications for code size and RTOS performance. However, be aware that nothing is free, so the security provided by this algorithm comes at a price.
Some RTOS claim that they implement the full algorithm, while they only implement the simple version (for owning a single mutex). Check out what’s actually being done before you start. It’s not a mistake to implement part of the algorithm (some well-known RTOS have done this for a long time), but it must be said.
The algorithm presented here is a minimum. For example, it could be improved to detect deadlock cases: two tasks each wait for a mutex owned by the other. But again we would have to deal with the general case (the size of the loop is not limited to two tasks), and go through chains of tasks. Another improvement would be to implement the “Priority ceiling” algorithm. All this is a compromise between the code size, the determinism, the performance and the service provided.
The priority inheritance algorithm is not a panacea. It has drawbacks that you should be aware of, and this post gives a glimpse of them. The links below will allow you to deepen the subject.
On the other hand the programmer has the possibility of limiting the risks by making a good design of the application, therefore by applying the well-known rules:
- Carefully choose the priorities of the tasks
- Limit interactions between tasks as much as possible
- Only use one mutex at a time. Otherwise all tasks must acquire mutexes in the same order and release them in the reverse order
- Only hold the mutex for a very short time. And avoid using any blocking function inside the critical section. If we apply this last rule we cannot acquire two mutexes, because acquiring the second has a risk of blocking the task!
- Use timeouts (not infinite) to detect deadlocks, knowing that it is often difficult to know what to do next. But at least the problem can be detected during the development and test phase
- etc
Links
I especially like the real story of what happened to Mars Pathfinder. How a serious issue regarding the use of a mutex was resolved on Mars Pathfinder. And some tips to remember for embedded software (in particular “test what you fly and fly what you test”).
The long version and the short version
An article dedicated to priority reversal which presents its effects (Fatal embraces, deadlocks, and obscure bugs), then the advantages and disadvantages of the various methods to avoid it:
How to use priority inheritance – Embedded.com
An introduction to priority-inheritance mutexes and priority-ceiling mutexes:
RTOSes, ‘mutexes’ fight priority inversion | EE Times
Mutexes vs. Other Semaphores – Priority Inheritance Ceiling Kernel (smxrtos.com)
A text from Victor Yodaiken, project leader for RTLinux , against the use of the priority inheritance mutex:
yodaiken-july02.pdf