</>EmbeddedInterview

How do priority inheritance and priority ceiling solve priority inversion?

HardRTOS & Real-Time Systems

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.