3 ms·
Let’s say your GUI thread is holding a shared lock when the audio callback runs. In order for your audio callback to return the buffer on time it first needs to
by CamperBob2 7y ago
Let’s say your GUI thread is holding a shared lock when the audio callback runs. In order for your audio callback to return the buffer on time it first needs to wait for your GUI thread to release the lock. Your GUI thread will be running with a much lower priority than the audio thread, so it could be interrupted by pretty much any other process on the system, and the callback will have to first wait for this other process, and then the GUI thread to finish and release the lock before the audio callback can finish computing the buffer — even though the audio thread may have the highest priority on the system. This is called priority inversion.
I guess I fundamentally don't understand priority inversion. I've done a lot of realtime programming but have never had to confront that particular buzzword.
If my realtime-priority I/O completion routine tries to take a lock that might be held by an idle-priority GUI thread, why is that a problem? If I'm waiting on a lock, then by definition I'm not running at realtime priority while I'm doing so. Thread priorities should apply only to threads that are actually doing stuff. It would be crazy for the kernel to fail to schedule any other threads while I'm waiting for one of them to release the lock I need. My realtime thread is effectively suspended during that wait, so it can't keep any others from running.
Yes, I might have to wait for other threads and even other processes to be scheduled. Too bad. If I didn't want that to happen, I shouldn't have tried to take a lock in a realtime thread. What exactly should I have expected to happen?
- saagarjha 7y agoSomething else might start running instead of your realtime-priority thread or GUI thread.
- CamperBob2 7y agoYes, that's an occupational hazard when you're waiting on a lock. Someone else might do something. In fact, someone else had better do something, or you won't get your lock. IMHO, if your system is designed such that a GUI or other low-priority thread is contending for the same resources as a realtime I/O thread, in a situation where the lock might be held for so long that the I/O thread starves, then you have made a really elementary mistake... one so fundamental that it doesn't deserve an abstract-sounding term like "priority inversion." I still feel like there's something I'm missing here. I mean, I understand that the GUI thread in question might be heavily pre-empted by medium-priority threads, but eventually the GUI thread is going to be given enough time to finish whatever it was doing with my lock, and life will go on. Is this behavior somehow unexpected or counterintuitive? If kernels are designed such that lower-priority threads never get a time slice until higher-priority threads block on something or explicitly sleep or yield, well, that seems like a really foolish call on the part of the kernel designer. You literally might as well have a cooperative-multitasking OS at that point.
- midnightclubbed 7y agoIf the gui thread is holding the lock that the audio thread needs then even a few ms before the gui thread gets a slice (and hands back the gui lock) can cause the audio to starve and click. I've seen kernels that only time-slice to a lower priority thread if all the high priority threads are sat in a lock. Not ideal but simplifies the kernel code. I've also seen kernels that only context switch when a thread becomes locked or when a (relatively) low resolution timer ticks. (I'm talking non-specifically about the kernels running on video game consoles).
- fourthark 7y agoYep, IIUC it's just an explanation for why priorities won't help you when you get in that mess. I sometimes get offended when there is a fancy term for something I think is common sense. But there's nothing I can do about it.
- scoutt 7y agoIt is an elementary mistake done by the programmer of the audio application. I think that's the reason the author wrote this article. Kernel designers solve that by temporarily boosting the priority of the lower (blocking) thread to be equal or higher than the priority of the blocked thread (https://docs.microsoft.com/en-us/windows/win32/procthread/priority-inversion https://docs.microsoft.com/en-us/windows/win32/procthread/pr...). It's called priority inheritance.
- Khoth 7y ago> I mean, I understand that the GUI thread in question might be heavily pre-empted by medium-priority threads, but eventually the GUI thread is going to be given enough time to finish whatever it was doing with my lock, and life will go on. Is this behavior somehow unexpected or counterintuitive? The mistake people make is, they think "my high-priority thread has to be active every 10ms, and the low-priority thread doesn't do much work with the lock held, 1ms max, so I'm totally fine, there's 9ms of safety factor there". Priority inversion is why that logic is wrong.
- jayshua 7y agoMy understanding is that you are absolutely correct. That's why you shouldn't use locks on the real-time audio thread.
- klodolph 7y ago> If my realtime-priority I/O completion routine tries to take a lock that might be held by an idle-priority GUI thread, why is that a problem? This is a problem because you miss I/O deadlines. You say that “by definition” you’re not running at realtime priority, but that’s just switching around definitions, it’s not changing the problem—which is that you’re missing I/O deadlines. > If I didn't want that to happen, I shouldn't have tried to take a lock in a realtime thread. What exactly should I have expected to happen? Agreed that you shouldn’t try to lock in a realtime thread—which is exactly the advice of the article. But blocking until the other thread leisurely completes its work is not the only outcome. You can have the lower-priority thread inherit the priority of the highest-priority thread waiting for mutexes that it owns. This, by the way, is one of the big reasons why mutexes on most systems aren’t just single words like they could be. This is also a very sensible way to do things. If your critical sections are short, it works well. It’s also a lot easier than doing lock-free synchronization. See: https://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutexattr_setprotocol.html https://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mu...
- jlokier 7y agoIf 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.