Priority inversion

I found the inspiration for this article while working on a consultancy job: Priority inversion.

In computer science, priority inversion is a (potential) problematic scenario in scheduling in which a high priority task is indirectly preempted by a medium priority task effectively inverting the relative priorities of the two tasks.

(http://en.wikipedia.org/wiki/Priority_inversion)

To put it more clearly.

• We have a critical section called ‘CRIT’ in a portion of code.
• Both low priority task ‘LPT’ and high priority task ‘HPT’ need to access it.
• Medium priority task ‘MPT’ also needs to do some processing, however it does not access ‘CRIT’.

1. Suppose LPT is running in CRIT.
2. Then suddenly, HPT becomes runable. It will be scheduled to run until it reaches CRIT.
3. But then HPT has to wait until LPT finishes CRIT: the priorities have been inverted temporarily which is normal in the system design, however LPT should free the lock as soon as possible.
4. But it can even take longer for HPT to be able to continue, if MPT pops up.
5. MPT preempts LPT, which results in HPT waiting even longer before LPT leaves CRIT: a higher priority task (HPT)  is preempted by a lower priority one (MPT).

There are various methods to ‘solve’ priority inversion. We list a few potential solutions here.

Disable interrupts

Disabling all interrupts during CRIT: no interrupts, no rescheduling. If CRIT is very small, this approach is usable, fast and simple but very crude.

Disable the scheduler

Disabling the scheduler during CRIT: interrupts can still happen, but it is not allowed to schedule another thread. This is also a good simple solution, but like “disabling all interrupts” it defeats (temporarily disables) the real-time priority scheduling.

Change thread priorities

Now the one which triggered my desire to handle this subject for this article. Boost the priority of LPT or HPT to an even higher priority (than HPT originally had) when entering CRIT: When in CRIT, LPT cannot be preempted by HPT or MPT. This might sound like a good idea, but the performance of changing priorities on the fly is not very good in most (RT)OS: It locks the scheduler for a short period but it also needs to do some administration and potentially scan and change the order in the runnable list.

Priority ceiling

A priority ceiling mutex is a lot like the previous. But now the mutex has its own priority which must be higher than the priority of HPT for this to work well: The thread in CRIT will get the priority of the priority ceiling mutex.

Automatic priority boosting

Another feature some (RT)OS provide is priority inheritance. The thread in CRIT will get the priority of the highest priority thread waiting for CRIT. Let us take a look at our example again: Suppose LPT is running in CRIT. Then suddenly, HPT becomes runable. It will be scheduled to run until it reaches CRIT but then it has to wait until LPT finishes CRIT: LPT is now boosted to the priority of HPT. If MPT pops up, MPT can no longer preempt LPT. HPT will resume after LPT leaves CRIT. When HPT finishes, MPT will run. And when MPT finishes, LPT will resume.

Avoid CRIT, no LOCKS

Another possible solution is avoiding locks and critical sections for example by using lock-less queues.

Anyway, do not do the change thread priority thing unless you know what you are doing, and even then, it is usually not the best option.