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 :

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

The Inversion

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

Solutions

Priority Inheritance

When blocks on a mutex held by , temporarily raise ‘s priority to ‘s level. Now cannot be preempted by . Once 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.