Priority inversion and inheritance

Priority inversion happens when a high-priority thread waits for a lock that a low-priority one holds. The wait itself is expected, since the holder only has to finish its critical section. The inversion comes from a third thread, of medium priority, that needs no lock at all: it preempts the holder, the holder cannot release the lock while it is off the CPU, and so the high-priority thread waits for the medium one, for as long as that one runs. The best-known case is the Mars Pathfinder lander in 1997, which kept resetting because a high-priority task waited on a lock held by a low-priority task that medium-priority tasks kept off the CPU.

Priority inheritance bounds the wait. While a thread holds a lock a higher-priority thread waits for, it runs at the waiter's priority, so no medium thread can preempt it, and it drops back to its own priority when it releases the lock. The priority ceiling protocol is the static alternative: each lock carries the priority of its highest-priority user, and any thread that takes the lock runs at that priority while it holds it.

The trap is undoing the boost correctly. Inheritance is transitive, since the holder may itself wait on a lock held by a third thread, which then has to inherit too, and a thread holding several locks has to fall back to the highest priority still owed to it, not to its base, when it releases one of them. The order in which a lock hands itself over matters as well: a lock that serves its waiters first come, first served can pass to a low-priority waiter while a high-priority one is queued behind it.

In Cosmos the kernel Mutex keeps its waiters in a FIFO and, on release, hands ownership directly to the head waiter, without boosting the holder while others wait: fair, but open to inversion under a fixed-priority policy. Under the default Stride policy priority is a share, so a holder keeps receiving its share and a high-priority waiter's wait stays bounded, only longer. The hook an inheritance protocol would use is SetPriority, reached through SchedulerManager.SetPriority; nothing in the kernel calls it, and no policy implements inheritance. See Mutex and Real-time notes.