Priority Inversion

Priority Inversion

Priority inversion is a scheduling hazard where a high priority thread is forced to wait on a low priority thread, effectively inverting their intended ordering. It famously contributed to a fault on the Mars Pathfinder mission.

The setup involves three threads and a shared lock. A low priority thread acquires the lock. A high priority thread then needs the same lock and blocks waiting for it. So far this is normal. The problem arises when a medium priority thread, which does not need the lock, preempts the low priority thread because it ranks higher. Now the low priority thread cannot run to release the lock, the high priority thread stays blocked, and the medium thread runs ahead of both. The high priority work is stalled by unrelated medium priority work.

The standard remedies temporarily boost the lock holder:

• Priority inheritance While a high priority thread waits on a lock, the holder inherits the waiter higher priority until it releases the lock. The medium thread can no longer preempt it.
• Priority ceiling Each lock has a ceiling priority equal to the highest priority of any thread that may take it, and a holder runs at that ceiling. This also prevents certain deadlocks.

Both schemes ensure the low priority holder runs long enough to release the lock quickly, restoring the intended priority order.

Key idea

Priority inversion lets unrelated medium priority work stall a high priority thread, and priority inheritance or a priority ceiling fixes it by boosting the lock holder so it releases promptly.