Priority scheduling makes a simple promise: when an urgent task is ready, it runs. Priority inversion is the case where that promise quietly breaks. A high-priority task ends up waiting behind a medium-priority task that has nothing to do with it, because of a lock held by a low-priority task. It’s an advanced interview topic because it sits exactly where scheduling and locking meet, and because the classic fix only works for one kind of lock.
Three tasks and one lock
The setup needs one CPU, strict priority scheduling and three tasks:
- L (low priority) runs first and takes a lock to update some shared data.
- H (high priority) wakes up and needs the same lock. It blocks, because L holds it.
- M (medium priority) wakes up. It doesn’t use the lock at all. It’s just ready to run and outranks L.
The scheduler now picks M over L, which is correct by the rules. But L can’t release the lock until it runs, and H can’t run until L releases the lock. So H, the most important task in the system, is effectively waiting for M to finish. Raise M’s run time and H’s wait grows with it.
The cleanest way to see this is a tiny simulation, one character per tick showing which task holds the CPU. L arrives at tick 0 and needs the lock for 4 ticks of work; H arrives at tick 2 and needs the lock for one tick; M arrives at tick 3 with 10 ticks of plain CPU work:
# One CPU, strict priority scheduling, 1 tick per step. Higher number = more urgent.
# Each task is a list of steps: "cpu" (plain work), "lock", "cs" (work inside the lock), "unlock".
def simulate(inherit):
tasks = {
"L": dict(prio=1, arrive=0, steps=["lock"] + ["cs"] * 4 + ["unlock"] + ["cpu"]),
"H": dict(prio=3, arrive=2, steps=["lock", "cs", "unlock"]),
"M": dict(prio=2, arrive=3, steps=["cpu"] * 10),
}
owner, timeline, done = None, [], {}
for t in range(40):
ready = [n for n, k in tasks.items() if k["arrive"] <= t and k["steps"]]
if not ready:
break
def eff(n): # effective priority
p = tasks[n]["prio"]
if inherit and owner == n:
waiting = [w for w in ready if tasks[w]["steps"][0] == "lock" and w != n]
p = max([p] + [tasks[w]["prio"] for w in waiting])
return p
runnable = [n for n in ready if not (tasks[n]["steps"][0] == "lock" and owner not in (None, n))]
run = max(runnable, key=eff)
step = tasks[run]["steps"].pop(0)
if step == "lock": owner = run
if step == "unlock": owner = None
timeline.append(run)
if not tasks[run]["steps"]: done[run] = t + 1
return "".join(timeline), donewithout inheritance LLLMMMMMMMMMMLLLHHHL H finished at t=19 (arrived t=2), M at t=13, L at t=20
with inheritance LLLLLLHHHMMMMMMMMMML H finished at t=9 (arrived t=2), M at t=19, L at t=20Read the first line left to right. L runs for three ticks and takes the lock. H arrives at tick 2 but is blocked, so L keeps going. At tick 3, M arrives and preempts L, then runs all ten of its ticks. Only then does L get back on the CPU, finish its critical section and release the lock, and H finally runs at tick 16. H waited 17 ticks for a one-tick job, and 10 of those ticks were M, a task with lower priority than H.
Bounded and unbounded inversion
It helps to separate two parts of H’s wait, because only one of them is a bug.
H waiting for L to finish its critical section is bounded inversion. It’s inherent to sharing a lock: if a low-priority task holds it, someone has to wait for the rest of that critical section. You control the bound by keeping critical sections short.
H waiting for M is unbounded inversion. Its length depends on how much medium-priority work happens to show up, which has nothing to do with the lock. Add more medium tasks, or make M longer, and H waits arbitrarily long. That’s the part every fix targets.
The fix that needs an owner
Priority inheritance says: while a task holds a lock that a higher-priority task is waiting for, the holder temporarily runs at the waiter’s priority. That’s the second line of the output. At tick 2, H blocks on L’s lock, so L inherits priority 3. When M arrives at tick 3 it can’t preempt L anymore. L finishes its critical section by tick 5, drops back to priority 1 as it releases the lock, and H runs immediately. H finished at tick 9 instead of 19. M still completed, just after H, which is the order the priorities asked for.
Priority ceiling is the alternative. Each lock is assigned a ceiling, the priority of the most urgent task that ever uses it, and any task that takes the lock runs at that ceiling right away. It’s simpler to reason about in hard real-time systems and also prevents some deadlocks, but you must know every lock’s users ahead of time.
POSIX exposes both as mutex protocols: PTHREAD_PRIO_INHERIT and PTHREAD_PRIO_PROTECT, set with pthread_mutexattr_setprotocol. They aren’t on by default. On this Mac, a fresh mutex attribute reported PTHREAD_PRIO_NONE, and setting PTHREAD_PRIO_INHERIT returned 0 (success). On Linux, priority-inheriting pthread mutexes are built on PI futexes and the kernel’s rt_mutex, which the PREEMPT_RT patches also use for most locks inside the kernel.
Notice what both fixes need: the system must know which thread holds the lock, so it knows whose priority to raise. A mutex has an owner. A semaphore doesn’t, because any thread may post it, so there’s nobody to boost. That’s a strong answer to “why not just use a binary semaphore?” Apple’s os_unfair_lock header makes the same point from the other side: the lock stores ownership information that the system may use to resolve priority inversions.
Mars Pathfinder
The case interviewers like to hear about is NASA’s Mars Pathfinder lander in 1997. A few days after landing, it began resetting itself. The spacecraft ran the VxWorks real-time OS. A high-priority task managing the information bus needed a mutex that a low-priority meteorological task sometimes held. A medium-priority communications task would preempt the meteorological task while it held the mutex, the bus task couldn’t run in time, and a watchdog concluded something had gone badly wrong and reset the system. The engineers reproduced it on a ground replica, and the fix was to enable priority inheritance on that mutex, done by changing a setting remotely on the lander. Three tasks and one lock, exactly as in the simulation.
Where you meet it outside spacecraft
On a desktop or server with normal time-sharing threads, inversion is softer: Linux’s default scheduler gives lower-priority threads a smaller share of CPU rather than none, so L eventually runs. It becomes sharp with real-time scheduling classes (SCHED_FIFO, SCHED_RR), and in places with deadlines measured in milliseconds:
- Audio. The audio callback runs at real-time priority and must fill a buffer every few milliseconds. If it takes a lock that the UI thread holds, and the UI thread is preempted, you hear a click.
- Mobile UI. On Apple platforms, the main thread waiting on a lock or semaphore held by a low-QoS background thread causes visible stutter, and Xcode’s Thread Performance Checker flags these as priority inversions.
- Kernels. Many kernels disable preemption around short spinlock sections so a lock holder can’t be preempted at all, which removes the problem for those locks.
The design-level fix is often better than any lock protocol: don’t share locks across priority levels. Hand data to the urgent thread through a lock-free single-producer, single-consumer queue, or publish settings with an atomic pointer swap, so the urgent thread never waits on anyone.
Interview practice: clicks in the audio thread
A music app’s audio callback runs on a real-time thread every 5 ms. To read the current effect settings, it locks a mutex that the UI thread also locks while the user drags a slider. Testers hear occasional clicks, mostly while dragging sliders with other apps busy. Explain the cause and propose a fix.
Answer
It’s priority inversion. While the user drags a slider, the UI thread frequently holds the settings mutex. If the audio callback arrives during that window, it blocks. That alone would be bounded and short. The trouble is that the UI thread runs at normal priority, so while it holds the mutex it can be preempted by any other normal-priority work, which is why the clicks get worse when other apps are busy. The real-time thread’s wait is now set by unrelated load, it misses its 5 ms deadline, and the audio buffer underruns.
A priority-inheritance mutex would help: the UI thread would run at the audio thread’s priority while holding the lock, so other apps couldn’t preempt it. But the UI thread might still allocate memory or take a page fault inside the critical section, so the wait isn’t truly bounded. The better fix is to remove the lock from the real-time path. Keep the settings in an immutable object, have the UI thread build a new one and publish it with an atomic pointer store, and have the audio thread read the pointer with an atomic load. Small scalar parameters can each be an atomic float. If the audio thread must ever touch a lock, use try_lock and fall back to the previous settings when it’s busy, so the worst case is one slightly stale buffer rather than silence.
Related scheduling and locking notes
- Operating Systems interview questions
- Operating Systems MCQs
- Mutexes Versus Semaphores and Resource Ownership
- Deadlock Conditions and Lock Ordering
- Linux kernel documentation: RT-mutex subsystem with PI support, on how the kernel implements priority inheritance