Priority Inversion

operating-systems concurrency

Definition

Priority Inversion

Priority inversion occurs when a high-priority thread is indirectly preempted by a lower-priority thread, typically when the high-priority thread waits for a resource held by a low-priority thread, and a medium-priority thread prevents the low-priority thread from releasing the resource.

Scenario

Consider three threads with priorities $H>M>L$:

1. $L$ acquires a mutex protecting a shared resource
2. $H$ attempts to acquire the same mutex and blocks, waiting for $L$ to release it
3. $M$ preempts $L$ (since $M>L$), running indefinitely
4. $H$ waits indefinitely because $L$ cannot complete while $M$ runs

The Inversion

$H$‘s priority is effectively reduced to $L$‘s level because it waits on $L$. $M$ — which should not affect $H$ — now determines when $H$ can proceed.

Solutions

Priority Inheritance

When $H$ blocks on a mutex held by $L$, temporarily raise $L$‘s priority to $H$‘s level. Now $L$ cannot be preempted by $M$. Once $L$ releases the mutex, its priority reverts.

Priority Ceiling

Each mutex is assigned a priority ceiling equal to the highest priority of any thread that may lock it. Any thread acquiring the mutex immediately inherits this ceiling priority until release.