vault

Real-Time Priorities and Priority Inversion

14 min read

Real-Time Priorities and Priority Inversion

Priority inversion is the failure mode of fixed-priority scheduling in which a high-priority task is blocked, not by higher-priority work, but indirectly by lower-priority work — defeating the entire point of having priorities. The kernel’s own design document defines it precisely: “Priority inversion is when a lower priority process executes while a higher priority process wants to run” (rt-mutex-design.rst, Linux 6.12). A bounded inversion (a high-priority task briefly waits for a low-priority task to release a lock) is unavoidable and usually fine; the dangerous case is unbounded priority inversion, where a medium-priority task preempts the low-priority lock holder, so the high-priority waiter is stalled “for an undetermined amount of time.” Linux solves this with priority inheritance implemented in kernel/locking/rtmutex.c: a low-priority task holding a contended rt_mutex temporarily inherits the priority of the highest-priority task waiting on it, so no medium-priority task can preempt it (rt-mutex.rst, Linux 6.12). Userspace gets the same guarantee through PI-futexes, which back pthread_mutex_t locks created with the PTHREAD_PRIO_INHERIT protocol. Verified against Linux 6.12 LTS source as of 2026-06-03.

This note is the companion to Real-Time Scheduling SCHED_FIFO and SCHED_RR: there we established that a higher-priority real-time task always wins; here we confront the case where a lock dependency makes that guarantee a lie, and how Linux restores it.

Mental Model

Three tasks, one lock. Picture a low-priority task L holding a lock, a high-priority task H that needs it, and a medium-priority task M that needs neither. H blocks waiting for L. Now M wakes up. Because M outranks L, M preempts L — and L cannot run to release the lock H is waiting for. So M, a task lower in priority than H, has effectively starved H, even though M never touches the lock. That is unbounded priority inversion: the duration is bounded only by how long M (and any other middle-priority task) chooses to run.

sequenceDiagram
    participant H as H (high prio)
    participant M as M (medium prio)
    participant L as L (low prio)
    L->>L: acquires lock K
    H->>H: wakes, tries lock K → blocks (waits for L)
    Note over L: With PI: L inherits H's priority here
    M->>M: wakes — wants to preempt L
    alt No priority inheritance
        M->>M: preempts L (M > L), runs arbitrarily long
        Note over H: H stalled for unbounded time (inversion!)
    else Priority inheritance enabled
        Note over L: L now runs at H's priority, M cannot preempt
        L->>L: finishes critical section, releases K, drops to own prio
        H->>H: acquires K, runs
    end

The priority-inversion scenario and the effect of priority inheritance. What it shows: the left branch is the bug — M preempts the lock-holding L and starves the high-priority H indefinitely; the right branch is the fix — the instant H blocks on L’s lock, L is boosted to H’s priority, so M can no longer preempt L, L quickly finishes and releases, and H proceeds. The insight to take: priority inheritance does not make the lock faster; it makes the holder temporarily as urgent as the most urgent waiter, eliminating the window in which a middle task can interpose.

The Canonical Example: Mars Pathfinder

The most-cited real-world instance is the 1997 Mars Pathfinder lander, whose flight software ran on the VxWorks real-time operating system and began experiencing total system resets shortly after landing. The architecture had three relevant tasks sharing an “information bus” protected by a mutex (Rapita Systems analysis; Mike Jones’ archived account):

  • A high-priority bus management task ran frequently and briefly, taking the bus mutex.
  • A low-priority meteorological (ASI/MET) task also took the bus mutex to publish data.
  • A medium-priority, long-running communications task touched neither but could preempt the meteorological task.

The failure sequence: the low-priority meteorological task acquired the mutex; the high-priority bus task then needed it and blocked; before the low-priority task could release it, the medium-priority communications task woke and preempted the low-priority task (legitimately — it was higher priority than it). With the lock holder frozen, the high-priority bus task stayed blocked. A watchdog timer noticed the high-priority bus task had not completed its expected cycle, concluded the system was wedged, and triggered a full reset — over and over.

The fix, uploaded to the spacecraft as a patch that flipped a VxWorks initialization parameter from FALSE to TRUE, was to enable priority inheritance on the mutex: “the priority of the task that holds the semaphore inherits the priority of a higher priority task when the higher priority task requests the semaphore” (Rapita Systems analysis). The crucial engineering lesson, and the reason the story endures, is that priority inheritance was available but disabled by default — the same trap exists on Linux, where a plain pthread_mutex_t does not use PI unless explicitly configured.

Solutions to Priority Inversion

There are two classical protocols; Linux implements the first.

Priority inheritance (the dynamic protocol)

Under priority inheritance, the lock holder’s priority is raised on demand to match the highest-priority task currently waiting for the lock, and restored the instant the lock is released. The kernel doc captures the recursive heart of it: “A low priority owner of a rt-mutex inherits the priority of a higher priority waiter until the rt-mutex is released. If the temporarily boosted owner blocks on a rt-mutex itself it propagates the priority boosting to the owner of the other rt_mutex it gets blocked on. The priority boosting is immediately removed once the rt_mutex has been unlocked” (rt-mutex.rst, Linux 6.12). The recursion — boosting propagating up a chain of nested locks — is the subtle part and is what the chain walk below implements.

Priority ceiling (the static protocol)

The alternative, priority ceiling, assigns each lock a fixed ceiling equal to the highest priority of any task that will ever acquire it; a task that takes the lock is immediately raised to that ceiling for the duration. Because the boost is unconditional and static rather than triggered by an actual waiter, priority ceiling also prevents certain deadlocks (the “priority ceiling protocol” / PCP) and avoids the bookkeeping of tracking waiters, at the cost of needing the ceiling declared up front and of boosting even when no contention occurs. POSIX exposes this as PTHREAD_PRIO_PROTECT (with pthread_mutexattr_setprioceiling), distinct from PTHREAD_PRIO_INHERIT (pthread_mutexattr_setprotocol(3p)).

Uncertain

Verify: that the Linux/glibc pthread implementation provides a functional PTHREAD_PRIO_PROTECT (priority ceiling) backed by a kernel mechanism, as opposed to only PTHREAD_PRIO_INHERIT. Reason: the Linux kernel’s PI machinery (rt_mutex, PI-futexes) implements inheritance; whether ceiling is enforced in the kernel or emulated in glibc was not confirmed against a primary source in this pass. To resolve: check the glibc nptl source for PTHREAD_PRIO_PROTECT handling and whether a FUTEX_LOCK_PI-style ceiling futex exists. uncertain

How Linux Implements Priority Inheritance

The rt_mutex and its data structures

Linux’s PI primitive is the rt_mutex in kernel/locking/rtmutex.c. It is not the lock most kernel code uses — ordinary struct mutex has no PI — but it is the engine behind PI-futexes and is used pervasively inside PREEMPT_RT, where sleeping spinlocks become rt_mutexes. Each rt_mutex tracks its owner in a single pointer field whose low bit doubles as a “has waiters” flag, allowing an uncontended lock/unlock to be a single cmpxchg with no internal locking overhead (rt-mutex.rst, Linux 6.12). Two red-black trees carry the priority bookkeeping:

  • Each rt_mutex has a waiter tree ordered by (priority, deadline) — the waiters blocked on this lock. Same-priority waiters are kept in FIFO order (rt-mutex.rst, Linux 6.12).
  • Each task_struct has a pi_waiters tree: for every lock the task owns, the top waiter of that lock is enqueued here. The maximum over this tree is the priority the owner must inherit. “For each rtmutex, only the top priority waiter is enqueued into the owner’s priority waiters tree … Whenever the top priority waiter of a task changes … the priority of the owner task is readjusted” (rt-mutex.rst, Linux 6.12).

A task’s effective priority is then min(its own normal priority, the top of its pi_waiters tree) (in internal numbering where smaller is more urgent). This is computed by rt_mutex_adjust_prio() and pushed into the scheduler.

The PI chain walk

The recursive boosting is the PI chain walk, implemented by rt_mutex_adjust_prio_chain(). A PI chain is, per the design doc, “an ordered series of locks and processes that cause processes to inherit priorities from a previous process that is blocked on one of its locks” (rt-mutex-design.rst, Linux 6.12). Because a task can block on only one mutex at a time, “a chain would never diverge” — it is a simple path, walked one hop at a time:

When task H blocks on a lock owned by L, task_blocks_on_rt_mutex() enqueues H’s waiter on the lock’s waiter tree, updates L’s pi_waiters, and if H is now L’s top waiter calls into the chain walk. The walk (annotated in the source as steps [1]–[13]) repeatedly: takes the blocked task’s pi_lock, reads what it is blocked on (pi_blocked_on), checks exit conditions, requeues the waiter in the lock’s waiter tree with the new priority, moves to the lock’s owner, requeues the owner’s pi_waiters, readjusts the owner’s priority, and — if that owner is itself blocked on another lock — loops to propagate further up (rtmutex.c rt_mutex_adjust_prio_chain, Linux 6.12). Each hop drops the previous lock’s wait_lock before taking the next, so the walk acquires locks in a strict, deadlock-free order (rtmutex->wait_lock then task->pi_lock, per the comment block in the source).

The walk terminates on several conditions: the chain reaches a runnable (unblocked) owner; the priority no longer changes (no further propagation needed); the walk’s max_lock_depth bound is exceeded (the chain walk increments a depth counter and bails out with if (++depth > max_lock_depth), rtmutex.c, Linux 6.12); or a deadlock is detected. Deadlock detection is folded into the same walk: if the chain loops back to the originating lock or task, the holder is trying to acquire a lock it (transitively) already holds, and the call returns -EDEADLK (rtmutex.c, Linux 6.12).

On unlock, the owner hands the lock to the top waiter, removes that waiter from its pi_waiters tree, and recomputes its own priority via rt_mutex_adjust_prio() — dropping the inherited boost “immediately … once the rt_mutex has been unlocked” (rt-mutex.rst, Linux 6.12). Note that a boosted task does not necessarily fall all the way back to its base priority if it still owns other contended locks — it falls to the max of whatever remains in pi_waiters.

PI-futexes — extending inheritance to userspace

Userspace cannot manipulate task_struct.prio or red-black trees directly, so PI for pthread_mutex_t is delivered through PI-futexes: the FUTEX_LOCK_PI, FUTEX_UNLOCK_PI, and FUTEX_TRYLOCK_PI operations of the futex(2) syscall. The futex word in shared memory holds the owner’s thread ID (TID); in the uncontended case lock and unlock are pure userspace atomic operations on that word with no kernel involvement at all — “in the user-space fastpath a PI-enabled futex involves no kernel work … just pure fast atomic ops in userspace” (pi-futex.rst, Linux 6.12). Only on contention does the waiter call FUTEX_LOCK_PI, at which point the kernel materialises an internal rt_mutex whose owner is the task identified by the TID in the futex word, attaches the waiter, and runs exactly the chain walk above — so the userspace lock holder is boosted just as a kernel rt_mutex holder would be. This is the path glibc takes for a pthread_mutex_t created with PTHREAD_PRIO_INHERIT. The kernel doc motivates it directly: PI is “pretty much the only technique that currently enables good determinism for userspace locks (such as futex-based pthread mutexes)” (pi-futex.rst, Linux 6.12). The general futex mechanism is covered in Futex and OS Synchronization Primitives; this note’s contribution is the PI variant layered on top.

Configuration / Code

Enabling priority inheritance on a pthread mutex

#include <pthread.h>
 
pthread_mutexattr_t attr;
pthread_mutex_t     lock;
 
pthread_mutexattr_init(&attr);
/* Without this line the mutex is PTHREAD_PRIO_NONE — NO inheritance,
   exactly the Mars Pathfinder default that caused the resets. */
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&lock, &attr);
pthread_mutexattr_destroy(&attr);

Line by line: pthread_mutexattr_setprotocol with PTHREAD_PRIO_INHERIT is what makes glibc request a PI-futex (FUTEX_LOCK_PI) on contention instead of an ordinary futex. The default protocol is PTHREAD_PRIO_NONE — no inheritance — so a real-time program that shares a default mutex between threads of different priority is vulnerable to exactly the unbounded inversion described above (pthread_mutexattr_setprotocol(3p)). For the priority-ceiling protocol you would instead set PTHREAD_PRIO_PROTECT and call pthread_mutexattr_setprioceiling (subject to the uncertainty flagged above).

Observing inheritance from outside

There is no clean /proc field that prints “currently boosted to N,” but you can observe the effect: under contention a low-priority RT task that owns a PI mutex will be scheduled as if it had the waiter’s priority. chrt -p <tid> shows the base (static) priority, not the transient inherited one; tracing the boost uses the sched:sched_pi_setprio tracepoint (trace-cmd record -e sched_pi_setprio), which is defined in include/trace/events/sched.h (confirmed present at tag v6.12) and fires each time a task’s effective priority changes due to PI, recording the old and new priority.

Failure Modes and Common Misunderstandings

  • “My pthread_mutex_t has priority inheritance.” Not by default. Unless you set PTHREAD_PRIO_INHERIT, the mutex is PTHREAD_PRIO_NONE and offers no protection — the single most common real-time mistake, and the literal Mars Pathfinder bug.
  • PI does not fix lock convoys or long critical sections. Inheritance bounds the inversion (the time a middle task can interpose), not the critical section itself. If L holds the lock for 10 ms, H waits ~10 ms regardless. The kernel doc is blunt: PI “is not a magic bullet for poorly designed applications” (rt-mutex.rst, Linux 6.12). Keep critical sections short.
  • Deadlock still possible, but detected. PI does not prevent lock-ordering deadlocks; the chain walk detects a cycle and returns -EDEADLK to the caller of FUTEX_LOCK_PI, so a buggy program gets an error rather than a silent hang.
  • Boost is per top-waiter, and can cascade. A long chain of nested PI mutexes can require many chain-walk hops; the depth is capped by the walk’s max_lock_depth bound to keep it bounded. Deeply nested PI locking is itself a design smell.
  • Non-RT (fair) tasks and PI. The boost machinery raises a holder’s scheduling priority; for a SCHED_OTHER holder boosted by an RT waiter, the holder is effectively promoted into the RT class for the duration. This is correct and intended, but means a careless fair-class lock holder can briefly run at RT priority.

Alternatives and When to Choose Them

  • Priority inheritance (PTHREAD_PRIO_INHERIT) — the default choice on Linux; no need to pre-declare ceilings, boosts only on actual contention. Use it for any lock shared across RT priority levels.
  • Priority ceiling (PTHREAD_PRIO_PROTECT) — when you can statically declare the highest user of each lock and want the (small) additional benefit of deadlock avoidance via consistent ceiling ordering, at the cost of boosting even uncontended takes. (See uncertainty flag on Linux support.)
  • Avoid the shared lock entirely — lock-free / per-CPU data, or a single dedicated thread that owns the resource and serves requests via a queue, sidesteps inversion altogether. Often the most robust answer for hard-real-time paths.
  • SCHED_DEADLINE with careful design — deadline scheduling does not by itself solve inversion (it has the same lock-holder problem), but its admission control and per-task bandwidth make the consequences more contained. See SCHED_DEADLINE and Earliest Deadline First.

Production Notes

PI-futexes are load-bearing far beyond niche real-time apps. The entire PREEMPT_RT kernel rests on rt_mutex: when PREEMPT_RT converts spinlock_t and struct mutex into sleeping locks, they become PI-aware rt_mutexes so that a high-priority task blocked on a kernel lock boosts the holder — without this, making the kernel preemptible would introduce unbounded inversion everywhere. In userspace, audio engines (JACK, PipeWire) and robotics middleware (ROS 2’s real-time executors) use PTHREAD_PRIO_INHERIT on any mutex shared between an RT processing thread and a non-RT helper. The recurring production lesson mirrors Pathfinder: the bug is almost never the inheritance algorithm — it is forgetting to turn it on, or holding a PI mutex for too long and discovering that PI bounds the inversion but not the holder’s own critical section.

See Also

Graph View

Backlinks