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

This page belongs to the parent topic. Before you start, make sure you are comfortable with a few words we will lean on:

A mutex (mutual-exclusion lock) — a token only one task may hold at a time. See Mutexes vs Semaphores.
A critical section (CS) — the stretch of code a task runs while holding a mutex. Nobody else may enter the same-mutex critical section until the holder releases.
Preemption — a higher-priority task instantly kicking a lower one off the CPU. See RTOS task states and context switching.
==Blocking time $B_{H}$ == — the total time a high task $H$ is forced to wait because a lower task holds a lock $H$ needs.

We will also use three protocol names repeatedly, so pin them down now:

Definition The three protocol acronyms used on this page

==PIP — Priority Inheritance Protocol==: a task that is blocking a higher one temporarily inherits (borrows) the higher task's priority, only while it holds the lock.
==PCP — Priority Ceiling Protocol==: every mutex carries a static ceiling (the priority of the highest task that will ever lock it); a task may take a lock only if its priority is strictly greater than ( $>$ ) the system ceiling (defined below). Ties ( $\geq$ ) are not enough — a strict " $>$ " is required. This adds a gate on top of inheritance.
==ICPP — Immediate Ceiling Priority Protocol==: the practical variant of PCP where a task is raised to a lock's ceiling the instant it acquires the lock, without waiting to actually block anyone.
==System ceiling==: at any moment, the highest ceiling among all mutexes currently locked by other tasks. It is the number PCP compares your priority against (strictly, with " $>$ ") before letting you take a new lock. If no other task holds a lock, the system ceiling is "below everything", so any task may lock.

Throughout, priority order is $H > M > L$ (H is most urgent). We write times in milliseconds (ms).

Level 1 — Recognition

Problem 1.1 (L1)

Three ingredients must all be present for priority inversion. From the list below, tick exactly the three that are required:

(a) preemptive priority scheduling, (b) a shared resource guarded by a mutex, (c) a network connection, (d) at least three priority levels, (e) a floating-point unit.

Recall Solution 1.1

The required three are (a), (b), (d).

(a) Without preemption, a running task can never be shoved aside — no inversion.
(b) Without a shared mutex there is no lock for a low task to hold hostage.
(d) You need three levels so a medium task (neither holder nor waiter) can slip in between and cause the unbounded case. (c) and (e) are irrelevant hardware details.

Problem 1.2 (L1)

Match each term to its one-line meaning:

Ceiling of a resource — 2. Priority inheritance — 3. Bounded inversion — 4. Unbounded inversion.

A. High waits only for a low task's critical section. B. A medium task hogs the CPU while low holds the lock, so the wait has no upper limit. C. The priority of the highest task that will ever lock the resource. D. A blocking low task temporarily borrows the waiter's priority.

Recall Solution 1.2

1↔C, 2↔D, 3↔A, 4↔B. Key sanity check: inheritance (D) is an action taken after a block; ceiling (C) is a static number computed before runtime.

Level 2 — Application

Problem 2.1 (L2)

$H$ , $L$ share mutex $R$ . $L$ 's critical section is $8$ ms. A medium task $M$ (needs no lock) runs for $40$ ms. With no protocol, and under the following timing assumptions — (i) $L$ has just acquired $R$ and executed none of its critical section yet, (ii) $H$ becomes ready immediately after $L$ acquires $R$ , and (iii) $M$ becomes ready right after $H$ blocks — how long does $H$ wait at minimum?

Recall Solution 2.1

Sequence: $L$ locks $R$ → (assumption ii) $H$ preempts immediately, tries $R$ , blocks → $L$ resumes → (assumption iii) $M$ becomes ready, preempts $L$ (M outranks L) → $M$ runs $40$ ms → $L$ finishes its remaining CS → releases $R$ → $H$ runs. Why L's whole $8$ ms CS is still pending: by assumption (i), $H$ preempted $L$ before $L$ had run any of its critical section, so when $M$ finally steps aside, $L$ still owes the entire $8$ ms — none of it was consumed earlier. (If $L$ had already run, say, $3$ ms of CS before $H$ arrived, only $5$ ms would remain; we take the worst case where all $8$ ms is left.) Wait $= M$ 's run $+$ $L$ 's remaining critical section $= 40 + 8 = 48$ ms (at minimum — more M activations make it worse). This is unbounded in principle: replace $40$ with any number and the wait grows.

Problem 2.2 (L2)

Same tasks, but now PIP is enabled on $R$ . How long is $H$ blocked?

Recall Solution 2.2

When $H$ blocks on $R$ , $L$ inherits $H$ 's priority. Now $L$ outranks $M$ , so $M$ cannot preempt $L$ . $L$ finishes its $8$ ms critical section, releases $R$ , drops back down; $H$ runs. $H$ 's blocking $= L$ 's critical section $= 8$ ms. Bounded — independent of $M$ 's $40$ ms. ✅

Problem 2.3 (L2)

Two mutexes $R_{1}$ and $R_{2}$ . $R_{1}$ is locked at some point by tasks with priorities ${H, L}$ ; $R_{2}$ is locked by ${M, L}$ . Give the ceiling of each mutex.

Recall Solution 2.3

Ceiling = priority of the highest task that ever locks it.

$ceiling (R_{1}) = max (H, L) = H$ .
$ceiling (R_{2}) = max (M, L) = M$ . Note $R_{2}$ 's ceiling is only $M$ , even though $L$ also locks it — the ceiling tracks the highest locker, not the lowest.

Level 3 — Analysis

Problem 3.1 (L3)

Study the timeline in the figure below. Tasks $H, M, L$ ; $H$ and $L$ share $R$ . No protocol is running. Identify (i) the instant unbounded inversion begins, and (ii) which task is unrelated to $R$ yet dominates $H$ 's delay.

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

How to read this figure: three horizontal lanes, one per task, labelled on the left (bottom = L low, middle = M medium, top = H high). Time runs left→right in ms, with dotted vertical guides at events $t_{0}, t_{1}, t_{3}, t_{4}, t_{5}$ . A blue bar = $L$ actively holding/running $R$ ; a pink bar on the H lane = $H$ blocked (frozen, waiting for $R$ ); a pink bar on the M lane = $M$ running its unrelated work; a yellow bar = a task finally running normally. The yellow arrow marks the unbounded gap.

Recall Solution 3.1

(i) Unbounded inversion begins at $t_{3}$ — the moment $M$ preempts $L$ while $L$ still holds $R$ . Before $t_{3}$ , $H$ was only waiting for $L$ 's critical section (bounded); at $t_{3}$ the wait becomes hostage to $M$ 's runtime. (ii) $M$ is unrelated to $R$ (needs neither lock) yet its runtime dominates $H$ 's delay — that is the signature of the bug. Look at the long pink $M$ bar between $t_{3}$ and $t_{4}$ : nothing in it touches $R$ , yet $H$ (blocked, top lane) is frozen the whole time.

Problem 3.2 (L3)

Compare the same three tasks under PIP (figure below). Explain, using the figure, why the medium bar disappears from between $L$ 's critical section.

How to read this figure: same three lanes and time axis as before. The dashed yellow vertical line marks the instant $L$ is boosted — it jumps from the bottom (L) lane up to the top (H) lane. The hatched blue bar sitting in the top lane is $L$ running its critical section while boosted to H's priority. The dotted "release" line marks where $L$ frees $R$ and drops back down; the yellow bar is $H$ finally running, and the pink bar on the M lane is $M$ , now pushed to after the release.

Recall Solution 3.2

At the instant $H$ blocks on $R$ , $L$ 's priority is boosted to $H$ 's (the dashed yellow line shows $L$ jumping to the top lane). While boosted, $L$ outranks $M$ , so when $M$ becomes ready it is not allowed to preempt — $M$ waits its turn. Therefore $L$ runs its critical section to completion uninterrupted, releases $R$ (yellow "release" tick), and instantly drops back to its low lane. Only then can $H$ run. The medium bar is pushed to after the release, so it no longer sits inside $L$ 's critical section — the unbounded gap is gone.

Problem 3.3 (L3)

Under PIP with nested mutexes: $H$ needs $R_{1}$ (held by $M$ ), and $M$ needs $R_{2}$ (held by $L$ ). Trace how the priority boosts propagate. This is called chained (transitive) blocking — explain the name.

Recall Solution 3.3

Chain of dependence: $H \to R_{1} \to M \to R_{2} \to L$ .

$H$ blocks on $R_{1}$ (held by $M$ ) → $M$ inherits $H$ 's priority.
But $M$ is itself blocked on $R_{2}$ (held by $L$ ) → $L$ inherits $M$ 's (now $= H$ 's) priority.
The boost has propagated down the chain to $L$ . $L$ runs at $H$ 's level, finishes CS on $R_{2}$ , releases it; $M$ un-blocks, finishes CS on $R_{1}$ , releases it; finally $H$ runs. "Chained" = $H$ 's wait is the sum of $L$ 's CS plus $M$ 's CS — two critical sections stacked, because the block travelled through a chain of holders. PIP bounds each link but adds them up.

Level 4 — Synthesis

Problem 4.1 (L4)

Design assignment. Tasks $H, M, L$ . Resources $R_{1}$ (ceiling $H$ ), $R_{2}$ (ceiling $H$ ). Under PIP, $H$ can be blocked on $R_{1}$ and $R_{2}$ separately, CS lengths $6$ ms and $4$ ms. Under PCP (Priority Ceiling Protocol), show that $H$ is blocked at most once, and give the worst-case blocking under each protocol.

Recall Solution 4.1

Under PIP — walk the timeline to see why the two critical sections sum:

$L$ locks $R_{1}$ and starts its $6$ ms CS. $L$ is preempted (say by $H$ 's activation), so $L$ is stopped inside $R_{1}$ 's CS.
Separately, $L$ (on an earlier or interleaved run) locks $R_{2}$ — OR a second lower task $L_{2}$ holds $R_{2}$ for $4$ ms. Either way there is a $4$ ms CS on $R_{2}$ that $H$ will also need.
$H$ starts. It needs $R_{1}$ first → blocks for the $6$ ms until $R_{1}$ 's holder finishes and releases. That is one block.
$H$ resumes, runs, then later needs $R_{2}$ → it finds $R_{2}$ still held → blocks again for the $4$ ms until $R_{2}$ is released. That is a second, separate block. Because PIP has no gate stopping the second lock from ever being taken, both critical sections can independently be "in progress" and each costs $H$ a full block, one after the other. Nothing merges them. Hence they add: $B_{H}^{PIP} = 6 + 4 = 10 ms (sum — chained/multiple blocking) .$ Under PCP: suppose $L$ locks $R_{1}$ . The system ceiling (the highest ceiling among currently-locked mutexes) becomes $H$ . Now if any task tries to lock $R_{2}$ , its priority must be strictly greater than the system ceiling $H$ — impossible, since no task strictly outranks $H$ . So the second lock is denied until $R_{1}$ is free: the situation where both $R_{1}$ and $R_{2}$ are simultaneously locked-and-blocking can never form. $H$ is blocked by at most one critical section — the longest relevant one: $B_{H}^{PCP} = max (6, 4) = 6 ms .$ PCP saves $10 - 6 = 4$ ms of worst-case blocking here, and guarantees "at most once".

Problem 4.2 (L4)

Five tasks lock a mutex $R$ : their priorities are $H = 5, T_{2} = 4, T_{3} = 3, T_{4} = 2, L = 1$ (bigger = higher). What is $ceiling (R)$ ? Under ICPP (Immediate Ceiling Priority Protocol — a task is raised to a lock's ceiling the moment it acquires the lock), to what priority is $T_{4}$ raised the instant it locks $R$ , and can any task preempt $T_{4}$ while it holds $R$ ?

Recall Solution 4.2

$ceiling (R) = max (5, 4, 3, 2, 1) = 5$ (which is $H$ ). Under ICPP, the moment $T_{4}$ locks $R$ it is immediately raised to the ceiling $= 5$ . While holding $R$ , $T_{4}$ runs at priority $5$ — the top. Can $H$ (priority $5$ ) preempt it? By our scheduler's tie-breaking rule (stated at the top of the page), preemption requires a strictly higher priority. $H$ and boosted- $T_{4}$ are equal at $5$ , so $H$ does not preempt: $T_{4}$ , already running, keeps the CPU. Every other task ( $T_{2}, T_{3}, L$ ) has priority $< 5$ , so none can preempt either. Therefore no task can preempt $T_{4}$ while it holds $R$ . $T_{4}$ runs its critical section to completion, releases $R$ , drops back to $2$ . This is why ICPP tasks are "never blocked after they start": they either hold the top rank or were stopped at the door.

Common mistake L4 trap — "PCP denies the lock, so that's the same as deadlock."

Why it feels right: a task being refused entry looks like it's stuck forever. The catch: the denial is temporary and ordered — it can never form a cycle. Here is the precise reason PCP is deadlock-free. Deadlock requires a circular wait: task $A$ waits for a lock held by $B$ , while $B$ waits for a lock held by $A$ . For $A$ to be inside a critical section at all, $A$ 's priority had to be strictly above the system ceiling at the moment $A$ locked. That system ceiling is $\geq$ the ceiling of every lock $B$ (or anyone) currently holds. So while $A$ holds its lock, no task whose priority is $\leq$ that ceiling can grab a new lock that would trap $A$ — in particular, the very task $A$ might later wait on cannot simultaneously be waiting on $A$ , because one of them would have failed the strict-" $>$ " gate at lock time. The gate enforces a total order on lock acquisition by ceiling value, and a total order has no cycles. No cycle ⇒ no circular wait ⇒ no deadlock. The denied task simply waits for the one current holder to finish, then proceeds. See Deadlock — conditions and prevention. Fix: deadlock needs a circular wait; PCP's strict ceiling gate makes lock acquisition acyclic, so the circle can never close.

Level 5 — Mastery

Problem 5.1 (L5)

Response-time flavour. Task $H$ has execution time $C_{H} = 12$ ms and worst-case blocking $B_{H}$ . Two lower tasks can each block it once under PIP: their relevant critical sections are $7$ ms and $5$ ms. There is no medium interference in this window. Using the response-time idea (see Schedulability analysis & response-time analysis), the response time of $H$ in this simplified window is $R_{H} = C_{H} + B_{H}$ . Compute $R_{H}$ under PIP and under PCP.

Recall Solution 5.1

PIP (blocked at most once per lower task → sum): $B_{H}^{PIP} = 7 + 5 = 12 ms, R_{H} = 12 + 12 = 24 ms .$ PCP (blocked at most once total → the single longest): $B_{H}^{PCP} = max (7, 5) = 7 ms, R_{H} = 12 + 7 = 19 ms .$ PCP tightens the worst case by $5$ ms — the tighter bound is exactly what hard real-time WCET/response-time budgets prize.

Problem 5.2 (L5)

Full formula application. Lower tasks and their relevant critical-section lengths (relevant to $H$ ) are: $L_{1} : {9, 3}$ ms, $L_{2} : {6}$ ms, $L_{3} : {8, 8}$ ms. (a) Under PIP, worst-case $B_{H} = \sum_{lower j} max_{k} CS_{j, k}$ . Compute it. (b) Under PCP, worst-case $B_{H} = max_{j, k} CS_{j, k}$ over the same set. Compute it.

Recall Solution 5.2

First, each lower task's longest relevant CS:

$L_{1}$ : $max (9, 3) = 9$
$L_{2}$ : $max (6) = 6$
$L_{3}$ : $max (8, 8) = 8$

(a) PIP — sum of those maxima: $B_{H}^{PIP} = 9 + 6 + 8 = 23 ms .$ (b) PCP — the single largest critical section across everything: $B_{H}^{PCP} = max (9, 3, 6, 8, 8) = 9 ms .$ Ratio $23/9 \approx 2.56$ : PIP's bound is over $2.5 \times$ larger here. As the number of lower tasks grows, PIP's sum grows while PCP's max stays put — that scaling is the deep reason PCP dominates for many nested resources.

Problem 5.3 (L5)

Reasoning synthesis. A colleague proposes: "Just use ICPP everywhere and forget PIP." Give one true advantage and one honest cost of that choice, tying back to the comparison table.

Recall Solution 5.3

Advantage: ICPP gives the tightest blocking bound ("at most once total"), deadlock-freedom, no chained blocking, and low runtime cost (raise-on-lock is one assignment) — a task is never blocked after it starts. Honest cost: ICPP needs static offline analysis — you must know every task that will ever lock every resource to compute ceilings, and any change to the task set forces recomputation. A task also gets boosted the instant it locks (even if nobody would have blocked it), which can slightly delay unrelated higher tasks that weren't going to touch that resource. PIP needs no static analysis and only boosts when a real block occurs — simpler to deploy in a system whose task set changes often.

Common mistake L5 trap — "bigger blocking formula means the protocol is worse in

every case." Why it feels right: PIP's worst-case sum is always $\geq$ PCP's max, so PIP looks strictly inferior. The catch: the formulas are worst-case bounds, not typical runtime. With a single resource and no nesting, PIP and PCP give the same bound (exactly one critical section of blocking), and in that case PIP needs no offline ceiling analysis — often the pragmatic winner. The gap between the two formulas only opens up when locks are nested or numerous. Fix: choose the protocol by system shape: single or rarely-nested locks → PIP is fine and cheaper to deploy; deeply nested hard-real-time → PCP/ICPP for the tight bound and deadlock-freedom. See the comparison table in the parent note and Real-Time Scheduling — Rate Monotonic & EDF.

Quick self-check

Recall Reveal the numeric answers

Prob 2.1 wait ::: $48$ ms Prob 2.2 wait ::: $8$ ms Prob 2.3 ceilings ::: $R_{1} = H, R_{2} = M$ Prob 4.1 PIP vs PCP ::: $10$ ms vs $6$ ms Prob 4.2 ceiling / raise ::: $5$ and $5$ Prob 5.1 $R_{H}$ PIP vs PCP ::: $24$ ms vs $19$ ms Prob 5.2 $B_{H}$ PIP vs PCP ::: $23$ ms vs $9$ ms