Priority inversion — problem and solutions (priority inheritance, priority ceiling): Worked examples

Intuition What this page is

The parent note told you the rules of priority inversion and the two fixes. This page is the drill hall: we hunt down every kind of situation these rules can produce — every combination of tasks, locks, protocols, and degenerate edge case — and we time each one on a stopwatch, step by step.

Before we start, one reminder of the vocabulary, because we will use it on line one:

A task = a unit of work the CPU runs. Each has a priority (a number saying how urgent). We use H (high), M (medium), L (low), highest wins the CPU.
A mutex (see Mutexes vs Semaphores) = a lock. Only one task may be inside the guarded region (the critical section, "CS") at a time. Others must block (wait, not running).
Blocking time $B$ = how long the urgent task is forced to wait for something less urgent. This whole page is about measuring $B$ .

Definition Notation glossary — read this first, every symbol is defined here

Everything on this page is a duration in milliseconds. There are exactly four symbols; we never use any other:

$CS_{t, R}$ = the length of the critical section that task $t$ runs while holding resource $R$ . Read the subscript as "who is inside, which lock". Example: $CS_{L, R_{1}}$ = "how long L stays inside the region guarded by $R_{1}$ ". When there is only one lock and one holder, we drop the second subscript and write $CS_{L}$ — "L's critical section".
$run (t)$ = the total CPU time task $t$ needs to finish its work — its whole run, not just a critical section. Example: $run (M)$ = "how long the medium task keeps the CPU busy overall". This is the symbol that can be arbitrarily large.
$B_{H}$ = H's worst-case blocking time — how long the high task is forced to wait for lower tasks. This is the number every example computes.
$W$ = watchdog limit — the deadline after which a supervisor timer resets the system if H has not run (used only in Ex 9).

One rule to remember: $CS$ values are bounded (a critical section is short and known); $run (M)$ is not — and that difference is the whole story of this page.

The scenario matrix

Every case this topic can throw at you falls into one of these cells. Each worked example below is tagged with the cell it covers.

#	Case class	What varies	Example
C1	Bounded inversion (baseline)	H waits only for L's CS	Ex 1
C2	Unbounded inversion (the bug)	M sneaks in, no protocol	Ex 2
C3	PIP fix — single lock	boosting removes M	Ex 3
C4	PIP limit — chained/nested locks	blocking sums	Ex 4
C5	PCP — nested locks, blocked once	ceiling gate	Ex 5
C6	Deadlock case: PIP allows it, PCP forbids	two locks, opposite order	Ex 6
C7	Degenerate: only 2 priority levels / no shared lock	no inversion possible	Ex 7
C8	Limiting value: CS length → 0 and M runtime → ∞	where the bound lives	Ex 8
C9	Real-world word problem (Mars Pathfinder numbers)	apply to a story	Ex 9
C10	Exam twist: ICPP timing — blocked before it starts	immediate ceiling	Ex 10

We compute $B_{H}$ (blocking of H) in each cell. Every worked example that has geometry-in-time (a schedule on a clock) gets its own timeline figure, so you see the blocking, never just read a number.

Ex 1 — C1: Bounded inversion (the acceptable baseline)

Worked example Statement

Priorities $H > L$ . Only two tasks, sharing mutex $R$ . L's critical section = $4$ ms. There is no medium task. What is H's worst-case blocking $B_{H}$ ?

Forecast: guess before reading — is H stuck for a little, a lot, or forever?

Steps: (follow the timeline figure below — the red hatched band is exactly $B_{H}$ )

L locks $R$ and enters its CS. Why this step? Someone must be inside the lock for H to have anything to wait on — an empty lock never blocks.
H becomes ready, preempts L, tries to lock $R$ → blocks, because mutual exclusion beats priority inside the CS. Why this step? This is the moment inversion begins; the clock on $B_{H}$ starts here (start of the red band in the figure).
L is the only one who can release $R$ , so the scheduler runs L. There is no M to interrupt L. L runs its remaining CS. Why this step? Because no higher-than-L task is ready (H is blocked, no M exists), the scheduler has exactly one runnable task — L — so it runs uninterrupted; this is precisely why the wait stays bounded.
L releases $R$ after finishing its $4$ ms CS. H immediately unblocks and runs. Why this step? Release ends the CS; the highest ready task (H) now wins the CPU (end of the red band).

$B_{H} = CS_{L} = 4 ms$

Verify: Units are ms (a duration) ✓. The wait equals exactly one critical section and depends on nothing outside it — no unbounded quantity anywhere. This is bounded inversion: unavoidable but safe.

Figure — Priority inversion — problem and solutions (priority inheritance, priority ceiling)

Ex 2 — C2: Unbounded inversion (no protocol, the bug)

Worked example Statement

Priorities $H > M > L$ . H & L share $R$ ; M shares nothing. L's CS = $5$ ms. M's total runtime $run (M) = 50$ ms, and M becomes ready right after H blocks. No protocol. Find H's blocking.

Forecast: will $B_{H}$ be $5$ ms (just L's CS) or something larger?

Steps: (see the timeline figure — watch the orange M bar stretch the red band)

L locks $R$ , enters CS. Why? Establishes the held lock.
H preempts, tries $R$ , blocks. Scheduler falls back to L. Why? Only L can release $R$ .
M becomes ready. M does not need $R$ , and $prio (M) > prio (L)$ , so M preempts L. Why this step? This is the poison: the scheduler obeys priority (M > L) and has no idea L is holding something H needs.
M runs its full $run (M) = 50$ ms. L is frozen mid-CS. H is still blocked. Why? Nothing forces M to yield to a lower task.
M finishes, L resumes, finishes its remaining CS, releases $R$ , H runs.

$B_{H} = CS_{L} + run (M) = 5 + 50 = 55 ms$

Verify: $55$ ms — but the " $50$ " is the value of $run (M)$ , M's arbitrary runtime. Replace it with $500$ and $B_{H} = 505$ . The bound tracks an unrelated task → unbounded. Compare with the picture below.

Ex 3 — C3: PIP fixes the single-lock case

Worked example Statement

Same numbers as Ex 2 ( $CS_{L} = 5$ , $run (M) = 50$ ), but priority inheritance is enabled on $R$ . Find $B_{H}$ .

Forecast: does the $50$ ms of M still count?

Steps: (in the figure, M's bar is now pushed to the right — it can't touch the red band)

L locks $R$ , enters CS. H preempts, blocks on $R$ .
PIP kicks in: because L is blocking H, L's priority is boosted to H's for as long as it holds $R$ . Why this step? "If you block someone important, borrow their rank." Now L outranks M.
M becomes ready — but $prio (M) < prio (L_{boosted}) = prio (H)$ , so M cannot preempt L. M waits. Why? The boost makes the scheduler treat L as urgent, closing the gap M exploited.
L finishes its $5$ ms CS, releases $R$ , drops back to its own low priority. H unblocks and runs; M runs afterwards. Why? Release ends the inheritance; normal priorities resume.

$B_{H} = CS_{L} = 5 ms$

Verify: The $run (M) = 50$ term vanished from the formula — exactly what we wanted. $5$ ms = one critical section = the bounded floor from Ex 1. PIP converted C2 back into C1. ✓

Ex 4 — C4: PIP's limit — chained (nested) blocking sums up

Worked example Statement

Tasks $H > M > L$ . Two mutexes $R_{1}, R_{2}$ . Under PIP: L holds $R_{1}$ (so $CS_{L, R_{1}} = 3$ ms) and, separately, M holds $R_{2}$ (so $CS_{M, R_{2}} = 4$ ms). H needs both $R_{1}$ and $R_{2}$ during its run. What is H's worst-case blocking under PIP?

Forecast: one CS or both?

Steps: (see the figure — two separate red bands, one per lock)

H tries $R_{1}$ (held by L). L is boosted to H, runs its $3$ ms CS, releases. That's block #1. Why? H can be blocked by each distinct lower holder it must wait for.
H proceeds, later needs $R_{2}$ (held by M). M is boosted to H, runs its $4$ ms CS, releases. That's block #2. Why this step? PIP bounds each block to a CS but does not limit the number of distinct blocks across nested/different locks.
Total blocking is the sum of the relevant critical sections:

$B_{H} \leq CS_{L, R_{1}} + CS_{M, R_{2}} = 3 + 4 = 7 ms$

Why this step (why they add)? The two blocks happen at different moments of H's run — first when H grabs $R_{1}$ , then later when it grabs $R_{2}$ . Because they never overlap, H sits in the "blocked" state during each separately, so the total wait is their arithmetic sum, not a max. PIP has no mechanism to prevent a second lower task from being caught mid-CS the way M is here.

Verify: $7$ ms. It is bounded (no $run (M)$ term) — PIP still works — but H paid twice. This is the "chained/transitive blocking" weakness the parent note warned about. ✓

Ex 5 — C5: PCP — nested locks, blocked at most once

Worked example Statement

Same setup as Ex 4 ( $CS_{L, R_{1}} = 3$ ms; $CS_{M, R_{2}} = 4$ ms), both locks with ceiling $= H$ (since H is the highest task that ever locks them). Now use the Priority Ceiling Protocol. Find $B_{H}$ .

Forecast: still $7$ , or less?

Steps: (in the figure, M is refused at the door, so only ONE red band survives)

Suppose L locks $R_{1}$ first. The system ceiling (highest ceiling among locks held by others) becomes $H$ . Why this step? PCP's extra gate: it records the ceiling of every held lock.
M now tries to lock $R_{2}$ . PCP rule: you may lock only if your priority is strictly above the system ceiling. $prio (M) < H = system ceiling$ → M is denied entry, even though $R_{2}$ is free. Why? Denying here prevents the tangle where H would later have to wait on two holders.
So at most one lower task can be holding a relevant lock when H arrives. H waits for exactly one CS — the single longest relevant one:

$B_{H} \leq max (CS_{L, R_{1}}, CS_{M, R_{2}}) = max (3, 4) = 4 ms$

Verify: $4$ ms vs PIP's $7$ ms — strictly tighter. PCP replaced a sum with a max. This "blocked at most once" property is why hard real-time systems love it (feeds directly into Schedulability analysis & response-time analysis). ✓

Ex 6 — C6: The deadlock case — PIP allows it, PCP forbids it

Worked example Statement

Tasks $H$ and $L$ . Two mutexes $A, B$ . L locks in order $A$ then $B$ ; H locks in order $B$ then $A$ (opposite order — the classic circular-wait setup from Deadlock — conditions and prevention). Ceilings: both $= H$ . Does PIP deadlock? Does PCP?

Forecast: which protocol saves you?

Steps (PIP): (see the figure — the two arrows form a circle = deadlock)

L locks $A$ . H preempts, locks $B$ . Why? Nothing stops either lock individually.
H now needs $A$ (held by L) → H blocks; L (boosted) needs $B$ (held by H) → L blocks. Each waits for the other → deadlock. Why this step? PIP only boosts priorities; it does nothing about lock ordering, so the circular wait forms.

Steps (PCP):

L locks $A$ → system ceiling $= H$ . Why this step? PCP records the ceiling of the held lock (see the System-ceiling definition above).
H tries to lock $B$ : is $prio (H)$ strictly above the system ceiling $H$ ? $H > H$ is false → H is blocked at the door, before acquiring $B$ . Why this step? The ceiling gate prevents H from ever grabbing $B$ while L holds $A$ , so the two locks can never be split between the tasks. No circular wait can form.
L runs (boosted), finishes with both $A$ and $B$ in order, releases; then H acquires both cleanly.

Verify (count): PIP → 1 deadlock possible; PCP → 0. PCP's acyclic ordering is a proof, not luck. This matches the comparison table's "Deadlock possible?" row. ✓

Ex 7 — C7: Degenerate inputs — when inversion is impossible

Worked example Statement

Two separate degenerate systems. (a) Only two priority levels $H > L$ with a shared lock. (b) Three levels $H > M > L$ but no shared resource at all. In each, can unbounded priority inversion occur?

Forecast: you need all three ingredients — which one is missing in each?

Steps: (see the figure — two "ingredient checklists", each with one box unticked)

Recall the three necessary ingredients: (i) preemptive priority scheduling, (ii) a mutex-guarded shared resource, (iii) at least three priority levels. Why? Unbounded inversion needs a third task (M) to hog the CPU while L holds the lock.
(a) With only $H$ and $L$ , there is no M to preempt L. Worst case is Ex 1: $B_{H} = CS_{L}$ , bounded. Number of unbounded scenarios $= 0$ . Why this step? Ingredient (iii) fails.
(b) With no shared lock, H never blocks on L — it just preempts freely. $B_{H} = 0$ . Why? Ingredient (ii) fails; blocking requires a lock to wait on.

Verify: (a) $B_{H} = CS_{L}$ (bounded), unbounded count $= 0$ ; (b) $B_{H} = 0$ . Both confirm: remove any one ingredient and the bug cannot appear. ✓

Ex 8 — C8: Limiting values — where the bound really lives

Worked example Statement

No protocol, setup of Ex 2. Push two knobs to extremes: (a) let L's CS $\to 0$ ; (b) let M's runtime $run (M) \to \infty$ . Track $B_{H} = CS_{L} + run (M)$ in each limit.

Forecast: which knob makes the danger, the tiny lock or the giant M?

Steps: (see the figure — $B_{H}$ plotted against M's runtime, a straight line that never flattens)

(a) As $CS_{L} \to 0$ : even a microscopic critical section is enough for H to block at that instant, letting M sneak in. Then $B_{H} \to 0 + run (M) = run (M)$ . Why this step? Shrinking the lock does not save you — the danger isn't the lock's size, it's the mere existence of the window in which H blocks and M can seize the CPU.
(b) As $run (M) \to \infty$ : $B_{H} = CS_{L} + run (M) \to \infty$ . Why this step? This is the literal meaning of "unbounded": the blocking has no upper limit because it inherits $run (M)$ 's divergence.
Contrast under PIP: $B_{H} = CS_{L}$ always, so as $run (M) \to \infty$ , $B_{H}$ stays at $CS_{L}$ (finite). Why this step? The protocol deletes the $run (M)$ term entirely, making $B_{H}$ independent of the diverging quantity.

Conclusion: the danger lives entirely in $run (M)$ , never in $CS_{L}$ . Shrinking the lock is useless; deleting the $run (M)$ term (what PIP does) is the cure.

Verify: No-protocol limit diverges ( $B_{H} \to \infty$ ); PIP limit stays at $CS_{L} = 5$ ms (finite). The unbounded-ness lives entirely in $run (M)$ , and PIP is precisely the surgery that removes that term. ✓

Ex 9 — C9: Real-world word problem (Mars Pathfinder, with numbers)

Worked example Statement

Model the 1997 rover. Tasks: bc_dist = H (bus manager), comms = M (communications), ASI/MET = L (weather data). H & L share the pipe mutex. Suppose $CS_{L} = 8$ ms and comms runs bursts of $run (M) = 200$ ms. The watchdog timer resets the system if H is starved for more than $W = 100$ ms. (a) Does the system reset without a protocol? (b) After uploading priority inheritance, does it survive?

Forecast: will $8$ ms or $200$ ms decide the rover's fate?

Steps: (see the figure — two bars against the red $W = 100$ ms watchdog line)

(a) No protocol: by Ex 2's logic, $B_{H} = CS_{L} + run (M) = 8 + 200 = 208$ ms. Why? comms (M) preempts ASI/MET (L) while it holds pipe; the unbounded term is $run (M) = 200$ .
Compare to the watchdog: $208 > 100 = W$ → watchdog fires, reset. Why this step? Starving H past the deadline is exactly the fault observed on Mars.
(b) With PIP: $B_{H} = CS_{L} = 8$ ms. Compare: $8 < 100 = W$ → no reset, survives. Why? The boost stops comms from preempting ASI/MET, deleting the $run (M) = 200$ ms term — literally the fix uploaded to Mars.

Verify: No protocol → $208 > 100$ (reset ✓, matches history); PIP → $8 < 100$ (survives ✓). Same watchdog, opposite outcome, decided entirely by removing the $run (M)$ term. ✓

Ex 10 — C10: Exam twist — ICPP blocks you before you start

Worked example Statement

ICPP is on. Resource $R$ has ceiling $= H$ . At time $t = 0$ , L locks $R$ (so L is immediately raised to $H$ 's priority). CS length $CS_{L, R} = 6$ ms. H is released at $t = 2$ ms. When does H actually get to run, and is it ever blocked after it has started executing?

Forecast: in plain PIP H starts, then blocks. Does ICPP differ?

Steps: (see the figure — H's release at $t = 2$ sits inside L's boosted CS)

At $t = 0$ , L locks $R$ and is instantly boosted to priority $H$ — ICPP doesn't wait for someone to actually block. Why this step? "Immediate" = raise on acquire, not on collision.
At $t = 2$ , H is released but L is currently running at H's priority. Ties go to the running task, so H stays ready but not running — blocked before it ever begins executing. Why this step? ICPP's signature guarantee: a task is only ever blocked at the start, never mid-execution.
L finishes its CS at $t = 0 + 6 = 6$ ms, drops to low, releases $R$ . H starts running at $t = 6$ ms and, once started, runs to completion without further blocking on $R$ . Why this step? All lower locks that could block H were already held-and-boosted before H began; none can appear later.

$H starts at t = 6 ms, B_{H} = 6 - 2 = 4 ms$

Verify: H starts at $6$ ms; blocking $= 4$ ms (from its release at $2$ to its start at $6$ ), which equals the remaining CS L still had to run ( $6 - 2 = 4$ ). H is blocked 0 times after starting. Same worst-case bound as PCP, simpler mechanism. ✓

Recall

Recall Test yourself on the matrix

Which cell? For each, name the answer.

Two tasks, one lock, no M — bounded or unbounded? ::: Bounded, $B_{H} = CS_{L}$ (C1)
What single term makes Ex 2 unbounded? ::: M's runtime $run (M)$ , unrelated to the lock (C2)
PIP on Ex 2: what is $B_{H}$ ? ::: $5$ ms — just L's critical section (C3)
Nested locks under PIP vs PCP: sum or max? ::: PIP sums the CSs; PCP takes the max (C4/C5)
Which protocol prevents deadlock? ::: PCP (acyclic ceiling ordering); PIP does not (C6)
Shrinking the critical section to near-zero — does it fix unbounded inversion? ::: No; the danger is the blocking window, not CS size (C8)
ICPP: when can a task be blocked? ::: Only before it starts running, never after (C10)

See also: Real-Time Scheduling — Rate Monotonic & EDF, RTOS task states and context switching, Worst-Case Execution Time (WCET) analysis.