Priority Inversion and Inheritance

A scheduler orders threads by priority, and a lock makes that order irrelevant. Thread H has the highest priority in the system, thread L the lowest, and thread M something in between. H needs a lock that L holds. L cannot run because M is runnable and outranks it. So H waits for M, a thread with no relationship to the lock, to finish a slice it had no business delaying. If M keeps getting work, H waits arbitrarily long. This is priority inversion, and it is a scheduling failure produced entirely by the interaction between two mechanisms that are each correct in isolation.

The inversion is not a bug in the lock or in the scheduler. It is a consequence of a lock creating a dependency that priority does not express. L is not just a low-priority thread when it holds the lock; it is the thread on which H’s progress depends, and no priority assignment reflects that until the dependency exists. The repairs all work by making the dependency visible to the scheduler at the moment it forms.

The three-thread example, precisely

The canonical scenario needs exactly three priorities and one lock. H is blocked on the mutex. L holds it. M becomes runnable and is higher priority than L, so the scheduler, correctly following its policy, runs M. H remains blocked for the entire duration of M’s execution, and if M is a long compute job the delay is unbounded from H’s perspective.

The unboundedness is the part that matters. In a fixed-priority system, a thread’s response time is supposed to be a function of the higher-priority work it must wait behind. Priority inversion adds a term that depends on unrelated medium-priority work, which can be arbitrarily large and is not accounted for by any response-time analysis that ignores locking. A system that passed its schedulability test without considering locks can fail in operation with no change to the workload’s priority structure.

The duration also has a bound in one specific case: if the critical section is short, L will release the lock quickly once it runs, so the inversion lasts at most the length of L’s critical section plus the time to schedule L. That bound is what inheritance tries to restore: it does not eliminate waiting, it makes the waiting proportional to the critical section rather than to unrelated load.

Inheritance: lending the priority

Priority inheritance raises L’s effective priority to H’s while L holds the lock that H needs. L now outranks M, so the scheduler runs L, L finishes its critical section, releases the lock, and its priority drops back. H acquires the lock and proceeds. The medium-priority thread’s interference is eliminated by construction, and the delay H experiences is the critical section length plus scheduling overhead.

The mechanism has to be precise about three things: what “effective priority” means, when it is recomputed, and what happens when several threads inherit.

Effective priority is the maximum of the thread’s own priority and the priorities of all threads it is currently blocking, transitively. A thread that holds two locks wanted by two threads inherits the higher of the two. A chain, H blocked on L1 held by M and M blocked on L2 held by L, propagates: L inherits M’s effective priority, which is already H’s, so L inherits H’s.

The recomputation happens at every blocking and every wakeup on the lock, not only at acquisition. When H blocks on a lock held by L, L’s priority is raised at that instant. When L releases, L’s priority is recomputed from the set of threads still waiting on locks it holds, which may be empty or may still contain another waiter. A thread’s effective priority therefore changes without any explicit request, which is why it cannot live in a field the thread sets itself.

/* Simplified inheritance on a mutex. Real implementations fold the
   waiting set into a single value to avoid walking a list per unlock. */
void mutex_lock_inherit(struct mutex *m, struct thread *self)
{
    while (m->owner) {
        if (self->prio > m->owner->prio)
            m->owner->prio = self->prio;   /* lend priority to the owner */
        enqueue_waiter(m, self);
        block(self);                       /* rescheduled at self->prio */
    }
    m->owner = self;
}

void mutex_unlock_inherit(struct mutex *m, struct thread *self)
{
    m->owner = NULL;
    self->prio = self->base_prio;          /* drop the loan */
    if (m->waiters)
        wake_highest(m->waiters);
}

The self->prio = self->base_prio line is the simplification that makes this code wrong for anything but a single lock per thread. A thread holding two locks, having inherited a high priority through one of them, must not drop to its base priority when it releases the other. Correct implementations track the maximum inherited priority across all held locks, either by maintaining a per-thread value updated on every acquire and release or by deferring the recomputation until the thread is next scheduled. The result is that the ordering key the scheduler sees is no longer the priority the thread was configured with, which is why a policy built on a coarse priority class, such as the fixed-priority levels in POSIX Real-Time Priority Classes and the Bandwidth Cap, must define what inheritance does to a thread that is already at the top of its class.

The cost: extra switches and chained blocking

Inheritance is not free, and its costs are specific.

The first is added context switches. Every inheritance event is a potential reschedule: L’s priority rises above M’s, so the scheduler may need to preempt M to run L. In a system where locks are taken frequently and priorities are mixed, this can multiply the switch count, and the switch itself costs microseconds plus cache disturbance. The benefit, bounded inversion, must be weighed against a higher steady-state switch rate.

The second is chained blocking. Inheritance propagates along a chain, so a thread may have to wait for a sequence of critical sections held by different threads, each of which must be allowed to run. The worst case for a thread is the sum of the critical sections along the longest chain it depends on, not the length of a single section. This is better than unbounded inversion and worse than the single-lock case, and it is the reason response-time analysis for locking systems computes a blocking term from the chain rather than from one section.

The third is deadlock amplification. Inheritance does not prevent deadlock; it makes deadlock more likely to be observed because threads that would otherwise be starved now run and reach the point where they deadlock. A system with a lock-order bug can appear to work under inversion, because the low-priority thread holding the first lock never gets to acquire the second; with inheritance it does, and the cycle closes. The fix is lock ordering, not inheritance.

Ceiling protocols and the blocking they remove

The alternative to inheritance is the priority ceiling. Each lock is assigned a ceiling equal to the highest priority of any thread that may lock it. A thread may acquire a lock only if its priority is higher than the ceilings of all locks currently held by other threads. The effect is that a thread holding a lock cannot be preempted by any thread that might want one of the locks it holds. The condition that produces inversion cannot arise, so no inheritance is needed.

The original ceiling protocol, as formulated by Sha, Rajkumar, and Lehoczky, guarantees that a thread can be blocked by at most one critical section of a lower-priority thread per job, regardless of how many locks exist. That is a strong bound: the blocking term in response-time analysis becomes the length of the longest critical section rather than the sum of a chain. The immediate ceiling protocol, which raises a thread to a lock’s ceiling at the moment of acquisition, preserves that single-blocking bound and is simpler to implement, at the cost of blocking a thread even when no higher-priority thread actually contends for the lock it holds; the original only raises priority when blocking is observed and so avoids that spurious blocking, at the cost of a system-wide ceiling check on every acquisition.

The cost of ceilings is that the assignment is static. A lock’s ceiling is a property of the set of threads that may use it, which must be known in advance. In a general-purpose system where any thread may take any lock, every lock’s ceiling is the maximum priority in the system and the protocol degenerates: the first thread to acquire any lock blocks everyone else. Ceilings are therefore a real-time design technique, applicable when the lock usage graph is known and priorities are fixed by analysis, and not a general-purpose kernel feature.

Ceilings also change the failure mode. Where inheritance degrades gracefully with longer blocking, a ceiling violation is a protocol error: a thread that tries to acquire a lock above its ceiling is refused or must be handled specially. That is a design-time discipline rather than a run-time recovery.

Where inheritance is not enough

Inheritance assumes priorities are static and known. Three common situations violate that.

The first is a fair-share scheduler where priority is a function of consumed service. A thread’s priority changes continuously as it runs, so the priority it lends to a lock holder is a snapshot that may be stale by the time the holder is scheduled. Implementations that combine inheritance with weighted fair scheduling usually do it by lending a boost rather than a priority: the holder is temporarily placed at the front of the run queue or given a bounded slice at high weight, which achieves the same effect without a stable priority to inherit.

The second is a lock whose holder is not runnable at all, because it is blocked on I/O. No priority assignment can make a thread that cannot run make progress, and inheritance simply propagates the problem down the chain until it reaches a thread that is runnable. This is a structural property: inheritance bounds inversion caused by scheduling, not inversion caused by blocking outside the scheduler’s control.

The third is the case that made the problem famous: a low-priority periodic task holding a mutex, an intermittent medium-priority task that preempts it, and a high-priority task that waits for the lock until its watchdog deadline expires. The mechanism can be tuned on a real POSIX system through pthread_mutexattr_setprotocol, which selects between PTHREAD_PRIO_NONE, PTHREAD_PRIO_INHERIT, and PTHREAD_PRIO_PROTECT; the third option is the ceiling protocol, whose ceiling is set separately with pthread_mutexattr_setprioceiling.

The repair is to change the mutex’s protocol attribute, which the standard makes a per-mutex property rather than a per-thread one. That placement reflects where the problem lives: inversion is created by the lock, so it is the lock that carries the policy. With PTHREAD_PRIO_INHERIT, the owning thread’s execution priority becomes the maximum of its own priority and the priorities inherited from every mutex it owns, and the effect propagates recursively when the owner blocks on another inheriting mutex. With PTHREAD_PRIO_PROTECT, the owner runs at the highest priority ceiling among the mutexes it holds, whether or not anyone is blocked on them. The attribute is set on a mutex attribute object before the mutex is initialised, and the ceiling is set separately through pthread_mutex_setprioceiling.

For systems where a latency bound must hold regardless of lock behaviour, inheritance and ceilings are insufficient on their own, because both bound the delay in terms of critical section lengths that are not themselves bounded. What is needed is a mechanism that limits how long any thread can hold a CPU while others wait, applied on top of the priority scheme rather than instead of it. A bandwidth cap does part of that job for a real-time class, and a deadline server does it for an arbitrary thread, as described in POSIX Real-Time Priority Classes and the Bandwidth Cap and Deadline Servers and Admission Control.