Questions: Priority Scheduling and Priority Inversion

Question 1

Three tasks: L (low priority) holds a mutex, H (high priority) needs the mutex, and M (medium priority) is ready but does not need the mutex. Without any fix, in what order do these tasks run?

• A. H runs first, acquires the mutex from L by force, then L runs, then M
• B. L runs to completion, releases mutex, H runs, M runs last
• C. M preempts L (since M > L in priority), while H waits, then L runs and releases mutex, then H runs
• D. H and M run concurrently, since H is blocked and M is ready

Answer: (C)

This is the classic priority inversion scenario. H needs the mutex, but L holds it, so H blocks. The scheduler then looks for the highest-priority ready task: that's M (not L). M preempts L and runs to completion. Only then does L resume, finish its critical section, and release the mutex — finally unblocking H. Result: H waited behind M even though H has higher priority than M. If many medium-priority tasks exist, H's wait is unbounded. Option A is wrong — an OS does not forcibly take locks from running tasks.

Question 2

Priority inheritance and priority ceiling are both solutions to priority inversion. What is the key difference in when the lock-holder's priority is raised?

• A. Priority inheritance raises priority when the lock is created; priority ceiling raises it when a waiter appears
• B. Priority inheritance raises priority when a higher-priority task blocks on the lock; priority ceiling raises priority immediately when the lock is acquired
• C. Both methods raise priority at the same time but use different priority values
• D. Priority inheritance is used for mutexes; priority ceiling is used for semaphores only

Answer: (B)

Priority inheritance is reactive: when H tries to acquire a lock held by L, the OS detects the blockage and boosts L to H's priority. The boost only happens if and when a higher-priority task is actually waiting. Priority ceiling is proactive: when any task acquires the lock, its priority is immediately raised to the pre-assigned ceiling (the maximum priority of any task that might ever acquire the lock), regardless of whether anyone is waiting. This makes priority ceiling more predictable but requires knowing which tasks use which locks in advance.

Question 3

Without a solution like priority inheritance, priority inversion can cause a high-priority task to wait indefinitely.

• T. True
• F. False

Answer: True

This is 'unbounded priority inversion.' While H waits for L to release the mutex, any medium-priority task M can preempt L (since M > L in priority). If there is an indefinite supply of medium-priority tasks, L may never get scheduled, and H may wait forever. This was the real behavior observed in the 1997 Mars Pathfinder mission, where repeated system resets were traced to exactly this pattern. Priority inheritance bounds the wait by ensuring L runs at H's effective priority, preventing any M from preempting it.

Question 4

Priority inheritance permanently changes a task's base priority for the duration of its execution.

• T. True
• F. False

Answer: False

Priority inheritance is temporary and scoped to the lock. When L holds a lock that H is waiting for, L's priority is boosted to H's level only while it holds that lock. As soon as L releases the lock (exiting the critical section), its priority drops back to its original low value. The boost is also transitive — if L itself is waiting on another lock held by an even lower-priority task, the boost propagates down the chain. The key design goal is minimal intervention: elevate just enough, just long enough, to prevent inversion.

Question 5

Why is priority-based scheduling alone not sufficient to prevent priority inversion, and what additional mechanism is required?

Model answer: Priority scheduling guarantees that among all currently runnable (ready) tasks, the highest-priority one executes. But when a high-priority task blocks on a mutex held by a low-priority task, the high-priority task is no longer runnable — it is waiting. The scheduler cannot help it, because it can only choose among ready tasks. A medium-priority task that needs no lock is ready and therefore gets scheduled instead, preempting the low-priority lock holder. Priority scheduling has no concept of why a task is blocked or who is waiting for whom. Preventing inversion requires the OS to track lock-holder and waiter relationships and actively adjust priorities based on that dependency graph — which is what priority inheritance and priority ceiling do.

The fundamental issue is that priority scheduling operates on the ready queue and ignores blocking dependencies. Priority inversion emerges precisely from the interaction between two subsystems (the scheduler and the lock manager) that, in isolation, each behave correctly. The fix requires linking them: the lock manager must notify the scheduler about priority-inversion situations so that priorities can be adjusted. This cross-subsystem coupling is why priority inversion was a subtle bug in deployed real-time systems for years before standard solutions emerged.