Priority Inversion and How Bounded It Can Be

A high-priority task asks for a mutex, finds it held by a low-priority task, and blocks. That is expected. What is not expected is the high-priority task waiting for a medium-priority task that holds no lock at all: the low-priority holder was preempted by the medium one, and since the low one cannot run, it cannot release. The high-priority task now waits behind an unrelated task’s execution time, and if the medium task is long or repeats often, the wait is unbounded by any analysis of the high-priority task’s own work. This is priority inversion, and the protocols that address it all work by changing who is allowed to run while a lock is held.

The three-task shape and the size of the problem

The canonical scenario needs three tasks. Task L has the lowest priority and acquires mutex M. Task H has the highest and tries to acquire M while L holds it, so H blocks. Task M has a priority between L and H and becomes ready during that window, preempting L. L cannot release the mutex until it runs again, and it cannot run while M is runnable, so H’s blocking time is the whole execution time of M’s work, plus whatever else arrives at a middle priority before L resumes.

That last clause is what makes the naive case unbounded. Every medium-priority task that becomes ready during the window adds its own execution to H’s wait. In a system with a periodic middle-priority task, H can be delayed by an arbitrary number of periods, which is not a scenario any response-time bound survives. The situation is not exotic: a shared bus driver lock, a shared I2C transaction, a shared log buffer, or a flash write serialisation are all ordinary places where a low-priority task and a high-priority task share an object. The mechanics of the wait itself — how the task leaves the ready set and how it is put back — are covered in blocking primitives.

The inversion is not a bug in the scheduler. The scheduler is doing exactly what it was told: the highest ready task runs. The bug is in the interaction between mutual exclusion and priority, and it appears in every preemptive fixed-priority system that uses blocking locks, including general-purpose operating systems.

Priority inheritance: lending a priority while holding

The inheritance protocol changes one rule: a task that holds a lock inherited by a blocked higher-priority task executes at the priority of the highest waiter until it releases. In the three-task shape, H blocks on M, L is boosted to H’s priority, and M can no longer preempt L. L runs to the end of its critical section at H’s priority and releases M, at which point H is unblocked and L returns to its base priority.

The implementation cost is small. Each mutex records its owner, and each task records both a base priority and an effective priority. On a blocking take, the kernel walks the chain: the waiter’s priority is compared against the owner’s effective priority, and if higher, the owner is boosted and the owner’s position in the ready set is updated. The walk must continue if the owner is itself blocked on another mutex, because the boost has to propagate through the chain of ownership until it reaches a runnable task or a task with equal or higher effective priority. Chained inheritance is what makes the mechanism transitive, and the chain length is bounded by the nesting depth of mutex acquisitions, which the design should cap.

The unbounded case is gone but not all blocking. H still waits for L to finish the critical section, and that wait is now bounded by the critical section’s own execution time, which is a quantity the programmer controls and the analysis can use. That is the entire trade: inheritance converts an unbounded wait into a bound equal to the longest critical section in the system.

Inheritance has a cost that is easy to underestimate. The owner’s priority changes at run time, so the ready-set ordering changes inside the take path, and any code that caches a task’s priority for scheduling decisions must be invalidated. The boost has to be undone on release, and if the owner holds two mutexes and one waiter releases while another waits, the unboost must restore the highest remaining waiter’s priority rather than the base priority. Kernels that implement this store the current effective priority separately and recompute it on every change, which is a few instructions per operation but a real cost in the take path’s worst case.

The ceiling protocols and why they bound differently

The priority ceiling protocol avoids inheritance’s dynamic priority changes by putting the ceiling on the resource instead. Every mutex is assigned a priority ceiling equal to the highest priority of any task that can lock it, determined statically. A task may lock a mutex only if its own priority is higher than the ceilings of all mutexes currently held by other tasks. If it is not, the lock request blocks, even when the mutex itself is free.

The gain is that a task can be blocked by at most one lower-priority task, and that blocking happens before the critical section begins, which means the blocked task never holds a resource while waiting. What makes the protocol analysable is that a task can be blocked at most once per job, and only at the point where it requests a lock: the block is at most the duration of a single critical section belonging to a lower-priority task whose ceiling is at least the blocked task’s priority. The blocking term therefore enters the response-time equation once per task rather than once per resource, and no chain of blocking has to be resolved.

The cost is that the ceiling must be known at design time, and the protocol can block a task that would not have blocked under inheritance. A high-priority task that never contends for a given mutex can still be made to wait because it tries to lock another mutex while a lower task holds one with a higher ceiling. The rule is “priorities above the ceiling of anything held,” and it applies to every lock request, contended or not.

The immediate ceiling protocol is the variant that raises a task’s priority to the ceiling of the mutex it acquires, for the duration of the hold, regardless of whether anyone is waiting. That turns the “priority above all held ceilings” test into a simple priority comparison, at the cost of running every critical section at ceiling priority, which is higher than necessary when no waiter exists. Both variants remove the transitive chain: because the block happens at the request rather than at the section, an owner is never prevented from running by a task between the owner’s and the waiter’s priority.

Choosing between them

Inheritance is what most general-purpose kernels and the POSIX PTHREAD_PRIO_INHERIT attribute provide, because it needs no static information and degrades to something usable when ceilings are unknown. Ceiling protocols are what safety-certified and automotive kernels provide, because they are analysable in advance: the blocking term comes out of a static table and the ceiling values are checked when the configuration is built, not discovered at run time.

A static ceiling table also lets a configuration tool prove that no task locks a mutex whose ceiling is below its own priority, which is a configuration error in the ceiling protocol and would otherwise show up as an unexpected block only under load. The AUTOSAR OS specification formalises this: internal resources carry a ceiling value and the configuration is validated.

The two protocols on the same task set

The difference between them shows up in what the analysis has to count. Under inheritance, a task’s blocking term is the sum, over every lower-priority task that can lock a resource it needs, of that task’s longest critical section on the resource. With nested locks between tasks, the term can chain: H waits for L, L waits for a task below it, and the chain’s total length enters H’s response time. The number is computable only if the lock graph is known, so inheritance moves the difficulty from run time to configuration review.

Under the ceiling protocol the same task’s blocking term is a single critical section: the longest one, among lower-priority tasks, whose ceiling is at least H’s priority. The difference is not a constant factor but a change in the formula’s shape. This is why the protocol’s analysis is described in terms of one blocking per task and why a ceiling-based system can be analysed with a table of numbers instead of a graph.

What neither protocol fixes

Neither protocol bounds the case where a task is preempted inside a critical section by a higher-priority task that does not use the same lock. That is normal preemption and it is accounted for in response-time analysis. What is not accounted for is a critical section that itself blocks on another resource: a task holding M that then waits on a queue or a semaphore can be delayed by anything that wakes it, and the chain of holders and waiters is not what the protocol’s bound assumes. The practical rule is that a critical section must not block, and a design that cannot avoid it needs the analysis to be redone with the inner wait treated as part of the section’s worst case.

Interrupt handlers that take locks create a second problem. A handler runs above every task priority, so a task holding a lock that the handler needs will block the handler, and the inversion is between the handler and every task in the system. Kernels that support this either forbid mutex use in handlers, offer a special interrupt-safe lock, or require the handler to defer the work to a task. The deferral approach keeps the lock discipline inside the task world and is why deferred processing is the common pattern in real drivers.

Multi-core systems break the analysis entirely. A lock held by a task on one core can block a task on another, and the holder’s priority has no meaning on the waiter’s core; inheritance across cores means reaching into the holder’s scheduling state from the waiter’s core and forcing a reschedule there, which is considerably more expensive than the single-core case and is why multicore protocols usually replace inheritance with a different discipline rather than extending it. Memory shared between cores without cache coherence needs its own barriers and is a separate problem from the scheduling one.

The blocking a task can experience also depends on how many distinct mutexes it can be blocked by, and a set of tasks that each use a long chain of nested locks can produce blocking terms that dominate the whole response time even with the protocol in place. A lock-nesting bound in the coding standard is worth more than a cleverer protocol.

The blocking term is only one of the numbers that has to fit; response-time analysis for fixed-priority task sets shows where it enters the recurrence and how the total is compared against the deadline.