3 ms·
If you know when a lock may be held by a low-priority thread, and take that into account when coding, then it's fine for the high-priority task to use that and
by jlokier 7y ago
If you know when a lock may be held by a low-priority thread, and take that into account when coding, then it's fine for the high-priority task to use that and wait. You get a kind of priority drop, but you're expecting it so it's ok.
But you have to know, and often you don't, which is when priority inversion is a problem.
An example of a class of PI problems occurs when you take a lock on something that everyone agrees is only to be locked for a bounded time, for example, always updating a structure with several fields by taking a lock, updating the fields together, then immediately unlocking it.
Then, your high priority task uses that lock, assuming the delay when doing so is within the bounded time multiplied by the amount of contention at that priority and higher. Often the multiple is exactly 1, for a high priority RT task.
Perhaps the lock is private to a module or library, without it being known to the author of the high priority task.
For example, imagine a hash table library which internally, and briefly takes a lock when updating the table, or maybe global table statistics in some circumstances, and advertises itself as taking O(1) time for inserts and deletes. Or a tree library, etc.
Due to the wonder of modularity and encapsulation, the high priority task author reasonably presumes they can use the library without hidden gotchas. And the hash table library author neglects to mention that it briefly takes a lock sometimes, because it seems like an implementation detail that should not be public.
(An even more minimal "library" is something that simulates atomic operations on a variable (such as atomic_add), by taking a lock around each operation.)
It's a bit of a disaster if that "O(1)" update blocks the high priority task forever, or a very long time, because the idle task is also updating a hash table, and then the idle task gets pre-empted constantly by mid-priority tasks.
This bug could be avoided if the hash table library author documented in their API "this table is not suitable for real-time use". Or if the high priority task author avoids using libraries.
But those are extreme and very unclean, unmodular things to require - and that's why it's a problem, priority inversion.
Another good way to avoid the bug, which doesn't break encapsulation (as much) and meets ordinary expectations in a lot of code, is to have locks that implement priority inheritance (boosting) when needed. Since that fixes a large class of unexpected starvation and unexpected slowness problems, it's useful in RT kernels.