Three tasks with different priorities run on one processor and share a resource. Walk through how the lowest-priority task can block the highest-priority one for an unbounded time, and explain what role the middle-priority task plays.
answer
- Three levels: L holds lock, H blocks, M preempts L
- Bounded = H waits one critical section; unbounded = H waits for M
- Scheduler runs highest-priority RUNNABLE task; it can't see the dependency
- Fix = transfer priority to the holder (inheritance or ceiling)
- M shares no resource with H — that's what makes it unbounded
basics
~20 sLow takes a lock, then High preempts and blocks on that lock. Now Low must finish to release it — but Medium, needing no lock, preempts Low because it outranks it. High waits on Low, Low waits for CPU behind Medium, so High is effectively blocked by Medium for as long as Medium runs.
solid answer
~60 sCall the tasks **L**, **M**, **H** (low, medium, high priority), sharing a mutex that only L and H use. 1. L runs and acquires the mutex. 2. H becomes runnable, preempts L, tries to acquire the mutex and blocks. H is now waiting on L — this alone is *bounded* inversion, acceptable and unavoidable when sharing a resource. 3. M becomes runnable. M needs no mutex, but it outranks L, so the scheduler preempts L and runs M. 4. L cannot run, therefore cannot release the mutex, therefore H cannot proceed. H is blocked behind M — a task it strictly outranks and does not even share a resource with. The delay is bounded only by how long M (and anything else between L and H) chooses to run, so with a stream of medium-priority work it is **unbounded priority inversion**. M is the essential ingredient: without it, L would finish its critical section promptly. Fixes raise L's effective priority while it holds the lock — priority inheritance (raise to the blocked waiter's priority) or priority ceiling (raise to the resource's declared ceiling on acquisition).
code
text · 7 linesprio | t0 t1 t2 t3 t4 t5
H | req-X(block)............ run
M | RUN RUN end
L | RUN ... preempted.... rel-X
^lock X ^unblocks H
H's delay = L's remaining critical section + ALL of M's executiongo deeper
Recall the three-task story in order — low holds the lock, high blocks, medium preempts low — and say the fix is to boost the lock holder.
Distinguish bounded from unbounded inversion, explain why the scheduler's local decision is correct, and name priority inheritance and priority ceiling.
Discuss detection and mitigation outside an RTOS: lock-wait telemetry, not sharing locks across latency classes, short critical sections, throttling and vCPU preemption as the modern medium-priority task.
Frame it as a dependency-versus-priority mismatch: urgency belongs to work, not tasks; design so latency-critical paths never depend on a resource that preemptible or throttled work can hold.
## The setup Priority inversion is a scheduling pathology: a higher-priority task is delayed by a lower-priority one, inverting the intended order. It needs three ingredients — a **priority-based scheduler**, a **shared non-preemptible resource** (a mutex, a device, an exclusive section), and at least **three priority levels**. Name the tasks by priority: L (low), M (medium), H (high). L and H share mutex X; M does not touch X at all. ## Bounded inversion Suppose only L and H exist. L acquires X. H becomes runnable, preempts L, requests X and blocks. H is now waiting for a lower-priority task — an inversion — but a *bounded* one: L is the highest-priority runnable task, so it runs, finishes its critical section and releases X. H's delay is at most the length of L's critical section. This is the unavoidable price of sharing a resource, and real-time analysis simply accounts for it as blocking time. ## Unbounded inversion Now add M. Sequence: ``` t0 L runs, acquires X t1 H wakes, preempts L, requests X -> blocks (H waiting on L) t2 M wakes; M > L, so scheduler preempts L and runs M t3 M runs ... and runs ... (H still blocked, L still holding X) t4 M finishes; L resumes, releases X t5 H finally acquires X and runs ``` Between t2 and t4, the highest-priority task in the system is blocked by a task it outranks and with which it shares nothing. The delay is not bounded by any critical section — it is bounded only by the total execution demand of every task with priority between L and H. If medium-priority work arrives repeatedly, H can miss deadlines indefinitely. That is the difference that matters: bounded inversion is a design cost; unbounded inversion is a bug. ## Why the scheduler cannot see the problem The scheduler makes a locally correct decision at every step: it always runs the highest-priority *runnable* task. The information it lacks is that L is standing in for H — L is, in effect, executing on H's behalf while holding X. Priority is attached to tasks, but the urgency really belongs to the *work* in the critical section. Every fix restores that missing information by temporarily transferring priority to whoever holds the resource. ## The two classic protocols - **Priority inheritance**: when H blocks on X, the holder L temporarily inherits H's priority, so M can no longer preempt it. L runs at H's priority until it releases X, then reverts. Reactive, needs no declarations, and bounds the inversion to the critical-section length. With nested locks, inheritance is transitive along the blocking chain. - **Priority ceiling**: each resource is statically assigned a ceiling equal to the highest priority of any task that may lock it. Under the immediate ceiling variant, a task's priority is raised to the ceiling as soon as it acquires the resource — proactively, before anyone blocks. This bounds each task to at most one block per activation and, as a bonus, makes deadlock among ceiling-protected resources impossible. Cost: you must know the full set of users of each resource up front. ## Where it appears in practice Though it is classically an RTOS topic, the same shape appears wherever priority-like asymmetry meets a shared exclusive resource: - A latency-critical request waiting on a lock or database row held by a background job that is itself starved of CPU by mid-priority work. - Thread pools with priority queues, where a low-priority task holds a shared resource and cannot get a worker to finish. - Containerised services where a CPU-throttled (cgroup-limited) process holds a lock that a non-throttled process needs — the throttling plays M's role. - Garbage-collected or interpreted runtimes where a background thread holding a global lock is descheduled. - Virtualised environments where the hypervisor deschedules a vCPU while it holds a guest lock (the "lock holder preemption" problem). ## Diagnosing and mitigating without an RTOS Most general-purpose systems do not offer priority ceilings out of the box, but the underlying rule is portable: **do not let anything preemptible or throttled sit between a resource holder and the task waiting on it**. Practical mitigations are to keep critical sections short and free of blocking calls; avoid sharing locks between latency-critical and background work at all (separate data or copies); use lock-free or wait-free structures for the shared point; ensure the holder cannot be starved (isolation, reserved capacity, priority inheritance if the platform's mutex supports it); and add timeouts plus telemetry on lock waits so the inversion shows up as a metric rather than an outage.
- Is every case of a high-priority task waiting on a low-priority one a bug?No. If the low-priority task merely holds a shared resource and can run to completion immediately, the high-priority task waits at most one critical section — bounded inversion, which is the normal, analysable cost of sharing. It becomes a defect only when unrelated medium-priority work can preempt the holder, making the delay depend on unrelated workload rather than on the critical section.
- Does priority inversion require a single processor?No, but multiprocessing changes the shape. On multiple cores the holder may keep running on another core, so a simple three-task inversion often resolves itself. Inversion still bites when the holder is descheduled, throttled, or when there are more runnable tasks than cores, and multiprocessor real-time systems need dedicated protocols such as MSRP or MPCP rather than the uniprocessor ceiling protocol.
- How would you detect priority inversion in a running system that is not an RTOS?Instrument lock acquisition with wait-time histograms tagged by workload class, and record whether the holder was runnable while a waiter waited. The signature is a latency-critical class showing long lock waits that correlate with CPU pressure or throttling of a background class, not with the length of the critical section. Scheduler tracing that shows the holder involuntarily descheduled while a higher-priority waiter is blocked confirms it.
A surgeon (H) is waiting for an operating theatre being cleaned by a junior (L). A mid-ranking administrator (M) pulls the junior away for paperwork. The theatre stays dirty, and the surgeon waits on the paperwork.
saying these in an interview costs you the question
- Describing it as a deadlock — nothing is in a circular wait; everything resolves once the medium-priority work finishes.
- Omitting the medium-priority task and claiming two priority levels alone create unbounded inversion.
- Saying the fix is to raise the high-priority task's priority; the priority that must be raised belongs to the lock holder.
- Claiming the scheduler is malfunctioning, when it is correctly running the highest-priority runnable task with the information it has.
- Believing it only happens in real-time operating systems, ignoring throttled containers, virtualised vCPUs and priority-queued thread pools.