How do priority inheritance and priority ceiling solve priority inversion?
Short answer: With priority inheritance, a task that holds a mutex temporarily runs at the priority of the highest-priority task waiting for it, so medium-priority tasks cannot pre-empt it; when it releases the mutex, it drops back to its own priority. With the priority ceiling protocol, each mutex has a ceiling equal to the highest priority of any task that uses it, and a task that takes the mutex immediately runs at that ceiling. Inheritance is automatic and needs no configuration; ceiling also prevents deadlock and bounds blocking but requires knowing which tasks use each mutex.
How a mutex with priority inheritance works (sketch)
typedef struct { tcb_t *owner; wait_list_t waiters; } pi_mutex_t;
void pi_lock(pi_mutex_t *m)
{
enter_critical();
while (m->owner != NULL) {
if (current->prio > m->owner->prio)
set_effective_prio(m->owner, current->prio); /* boost the holder (also re-sorts it) */
block_on(&m->waiters, current); /* sorted by priority */
/* critical section re-entered after wake-up; loop re-checks ownership */
}
m->owner = current;
exit_critical();
}
void pi_unlock(pi_mutex_t *m)
{
enter_critical();
m->owner = NULL;
restore_prio(current); /* back to base priority, or the highest of other held mutexes' waiters */
wake_highest(&m->waiters); /* may trigger a context switch */
exit_critical();
}
Details real kernels handle: transitive inheritance (H waits for L1, which waits for L2: L2 must also be boosted), a task holding several mutexes (its priority is the maximum of all their waiters), and timeouts (a waiter giving up must lower the boost).
Comparison
| Priority inheritance | Priority ceiling (immediate) | |
|---|---|---|
| When the holder is boosted | only when a higher task actually waits | as soon as it takes the mutex |
| Configuration | none | a ceiling per mutex |
| Deadlock prevention | no | yes (for single-processor, correct ceilings) |
| Blocking bound | can be chained through several mutexes | at most one critical section |
| Run-time overhead | when contention happens | on every lock/unlock |
| Used by | FreeRTOS, Zephyr, POSIX PTHREAD_PRIO_INHERIT, Linux rt_mutex |
OSEK/AUTOSAR OS (resources), POSIX PTHREAD_PRIO_PROTECT, Ada |
Limits of both: they do not help if the lock holder runs for a long time; keep critical sections short. Neither works for semaphores used as signals.