Products > Programming

The meaning of "priority inversion"

(1/3) > >>

peter-h:
I am trying to work out what this fancy term means in the embedded context.

I think it means this:

Let's say you write a replacement for memcpy(). For < 10 bytes you move one at a time (if your CPU supports unaligned data). For < 100 bytes you move 4 at a time and then use single byte transfers to tidy up the ends. For >=100 you use DMA. Now, DMA is obviously not thread-safe, so you mutex around that bit. And if some task with a priority of 0 is calling this to move 1000 bytes, and a task with a priority of 10 calls memcpy() to move some other 1000 bytes, the latter task will get locked out. But only upon making that call to memcpy(), and only with len>=100.

So to guard against this you need to know what is going on, no? There is no obvious other way, short of a complicated solution which looks at the priority of each task wanting that mutex and if the prio=10 one is detected, it stops the DMA, saves its state, sets it up for the new use, then restores its state and restarts it for the prio=0 task. Horrible... and very sensitive to undocumented hardware issues.

This is perhaps another example
https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643
which is more subtle but only because TCP/IP is complicated. But it refers to a mutex which "supports priority inversion".

DiTBho:
umm, the term "priority inversion" refers to a specific known problem with a specific class of schedulers.

brucehoult:
No.

First of all, DMA is a red herring. It's effectively a different (specialised) processor, and so is outside the scope of priority inversion.

The lock is relevant.

Priority inversion is nothing to do with interrupting a low priority task in order to run a high priority one. That is just normal operation.

Interrupting a low priority task that already has a lock in order to give the lock to a high priority task goes directly against what a lock is for. That's going to break things.

Priority inversion is when a high priority task is waiting for a lock that is held by a low priority task, and some intermediate task that doesn't care about that lock becomes runnable and preempts the low priority task, preventing progress towards releasing that lock. The "inversion" is that this medium priority task is getting to run when the high priority task can't.

The normal solution is to temporarily give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

Yes, I've written production quality schedulers.

tggzzz:

--- Quote from: brucehoult on February 04, 2023, 12:05:44 pm ---The normal solution is to give the task holding a lock the same priority as the highest priority task that is waiting for that lock, so it can finish its work and free up the lock as soon as possible. The medium priority task won't run because it has lower priority than the boosted low priority task that holds the lock. Once the lock is freed the high priority task will run immediately, not the medium priority task (and the low priority task will drop back to low priority).

--- End quote ---

I believe Microsoft Windows simply randomly changes priorities, in the hope that the thing will eventually become unjammed.

Given that completely uncontrolled and uncontrollable environment, it may even be the best workaround :(

Sherlock Holmes:

--- Quote from: peter-h on February 04, 2023, 11:03:48 am ---I am trying to work out what this fancy term means in the embedded context.

I think it means this:

Let's say you write a replacement for memcpy(). For < 10 bytes you move one at a time (if your CPU supports unaligned data). For < 100 bytes you move 4 at a time and then use single byte transfers to tidy up the ends. For >=100 you use DMA. Now, DMA is obviously not thread-safe, so you mutex around that bit. And if some task with a priority of 0 is calling this to move 1000 bytes, and a task with a priority of 10 calls memcpy() to move some other 1000 bytes, the latter task will get locked out. But only upon making that call to memcpy(), and only with len>=100.

So to guard against this you need to know what is going on, no? There is no obvious other way, short of a complicated solution which looks at the priority of each task wanting that mutex and if the prio=10 one is detected, it stops the DMA, saves its state, sets it up for the new use, then restores its state and restarts it for the prio=0 task. Horrible... and very sensitive to undocumented hardware issues.

This is perhaps another example
https://www.eevblog.com/forum/microcontrollers/anyone-here-familiar-with-lwip/msg4680643/#msg4680643
which is more subtle but only because TCP/IP is complicated. But it refers to a mutex which "supports priority inversion".

--- End quote ---

As the others say this is all to do with locks and scheduling or lock holders and lock waiters, here's how the Windows OS handles that.

Navigation

[0] Message Index

[#] Next page