5.5.14 · D5Embedded Systems & Real-Time Software
Question bank — Priority inversion — problem and solutions (priority inheritance, priority ceiling)
Before you start, three words we lean on constantly:
True or false — justify
Priority inversion can happen with only two priority levels
False — you need at least three levels, because unbounded inversion requires a Medium task (unrelated to the lock) to preempt Low; with only H and L there is no third task to inject unbounded delay.
Priority inversion is a bug in the scheduler's code
False — it's an emergent interaction between two correct rules (priority picks the CPU, the mutex picks the critical section); each rule alone is fine, they simply disagree.
Bounded priority inversion must always be eliminated
False — bounded inversion is unavoidable and acceptable: H must wait for L to finish its critical section because mutual exclusion is doing its job; only the unbounded part is the dangerous bug.
Priority Inheritance (PIP) prevents deadlock
False — PIP only boosts priority so Medium can't preempt Low; it does nothing about lock-ordering, so two tasks grabbing R1 and R2 in opposite order can still deadlock (see Deadlock — conditions and prevention).
Priority Ceiling Protocol (PCP) prevents deadlock
True — the ceiling gate imposes an acyclic ordering on lock acquisition, so the circular-wait condition for deadlock can never form.
Under PIP a high task can be blocked by several lower tasks in sequence
True — each lower task holding a relevant critical section can block H once, so worst-case blocking is a sum over lower tasks; this is chained/transitive blocking.
Under PCP a high task can be blocked at most once per activation
True — the ceiling gate stops the nested tangle from ever forming, so H waits for a single (longest relevant) critical section, not a sum.
In PIP, the low task keeps its boosted priority forever after being boosted
False — the boost is temporary: L drops back to its original priority the instant it releases the mutex.
ICPP (immediate ceiling) has a worse worst-case blocking bound than original PCP
False — ICPP gives the same worst-case bound; it just raises priority immediately on lock rather than only when a block actually occurs.
Priority inversion means the CPU is idle while H waits
False — the CPU is busy (running Low or Medium); the problem is that the busy work is not the most urgent work, which is why "CPU utilised" metrics hide the bug.
A task under ICPP can be blocked after it has already started running
False — because ICPP raises a task to the resource ceiling the moment it locks, a task can only be blocked before it begins; once running it cannot be preempted by a task that shares a lock with it.
Rate-Monotonic schedulability analysis can ignore priority inversion
False — blocking time must be added into the response-time equation; ignoring it can make an "un-schedulable" set look schedulable and miss deadlines.
Spot the error
"To fix inversion, just give the low task a permanently high priority." — what breaks?
That defeats priority scheduling entirely: Low would now preempt genuinely urgent work all the time; the boost must be temporary and conditional on actually holding a needed lock.
"PIP boosts the medium task so it stops interfering." — what's wrong?
PIP boosts Low (the lock holder) to H's priority, not Medium; boosting Low is what makes Medium unable to preempt it — Medium's priority is never touched.
"The ceiling of a resource is the priority of whoever currently holds it." — correct it.
The ceiling is static: it's the priority of the highest-priority task that will ever lock that resource, computed offline — not a runtime property of the current holder.
"Under original PCP, a task may lock a resource if its priority is at least the system ceiling." — fix it.
It must be strictly higher than the system ceiling (the highest ceiling among resources locked by other tasks); "at least" would let the tangle form and break the once-only guarantee.
"Priority inversion only affects hard real-time systems." — what's overstated?
It affects any preemptive priority system with shared mutexes; hard real-time systems merely notice it more because a missed deadline is catastrophic (e.g., Mars Pathfinder's watchdog reset).
"Using a semaphore instead of a mutex avoids the problem." — why is this misleading?
A counting semaphore has no owner, so there is no task whose priority you can boost — inheritance/ceiling protocols need an owned lock (a mutex); switching to a semaphore removes the fix, not the problem.
"PCP requires no offline analysis, unlike PIP." — reverse it.
It's the opposite: PCP needs static computation of every resource's ceiling before runtime; PIP needs no such analysis (it reacts purely at runtime when a block occurs).
Why questions
Why does raising Low's priority (PIP) specifically stop unbounded delay?
Because Medium can no longer preempt a boosted Low, Low finishes its critical section without interruption; H's wait shrinks to Low's critical-section length — a bounded, analyzable quantity independent of Medium's runtime.
Why does the worst-case bound under PCP contain a instead of a ?
The ceiling gate guarantees H is blocked at most once total, so we take the single longest relevant critical section (a max), whereas PIP allows one block per lower task (a sum).
Why is ICPP popular in real RTOSes despite PCP's tighter theory?
ICPP is far simpler to implement — raise to ceiling on lock, restore on unlock, no runtime tracking of the system ceiling or who's blocked — while delivering the same worst-case blocking bound (it's
PTHREAD_PRIO_PROTECT).Why does priority inheritance need the mutex to have an owner?
Boosting means "give the holder H's rank"; you can only do that if the lock records which task holds it — a mutex tracks its owner, an unowned semaphore does not.
Why does adding blocking time matter for Rate-Monotonic feasibility?
A high-priority task's response time now includes time spent waiting on lower tasks, which RM's basic utilisation test ignores; forgetting under-estimates response time and can certify a set that actually misses deadlines.
Why can chained (transitive) blocking make PIP costly even though it's bounded?
If H waits on R1 held by Mid, and Mid waits on R2 held by Low, boosts chain through the hierarchy and H's blocking accumulates across every nested critical section — bounded, but the sum can be large and hard to analyse.
Why is the WCET of each critical section the key input to these bounds?
Both formulas are expressed purely in critical-section durations, so you must know each critical section's worst-case length to compute the guaranteed blocking bound — a loose WCET makes the whole schedulability guarantee loose.
Edge cases
What happens if H and L never actually share a resource — can H still be inversion-blocked by L?
No — inversion requires a shared mutex; if their critical sections are disjoint, L's lock is irrelevant to H and priority scheduling behaves normally.
If Medium never becomes ready during Low's critical section, is there still inversion?
There is still bounded inversion (H waits for L's critical section), but no unbounded inversion, since the unbounded case needs Medium to actually preempt Low — the danger is latent, not triggered.
Two tasks, both under ICPP, both want the same single resource with ceiling = higher of the two — can they deadlock?
No — a single resource has no second lock to form a cycle, and ICPP's immediate raise means whoever locks first runs to completion of its critical section without the other preempting; deadlock needs at least two resources acquired in conflicting order.
Under PCP, a task tries to lock a resource whose ceiling equals its own priority — allowed?
The rule compares its priority to ceilings of resources held by other tasks; locking your own first resource is always allowed since no other task holds anything with a blocking ceiling at that moment.
A low task holds the lock and then a higher-than-H task (call it VH) becomes ready but needs no lock — does inversion affect VH?
No — VH shares no resource, so it simply preempts and runs; inversion only ever delays a task that must wait on a lock a lower task holds.
If a system has priority levels but no preemption (cooperative scheduling), can unbounded inversion occur?
No — unbounded inversion needs Medium to preempt Low; without preemption a running task yields voluntarily, so Medium cannot force Low off the CPU mid-critical-section.
What if the low task, while boosted under PIP, is itself blocked on a second mutex held by an even lower task?
The boost propagates transitively down the chain (the second holder gets boosted too); this is exactly the transitive/chained blocking PIP permits but PCP prevents — see RTOS task states and context switching for how the blocked→ready transitions cascade.
Recall Two-line self-check
The single sentence that separates PIP from PCP is? ::: PIP reacts by boosting the holder after a block occurs (bound = sum over lower tasks, deadlock still possible); PCP pre-empts the tangle with a static ceiling gate (bound = single max, deadlock impossible). The single reason inversion is "invisible" on a CPU-usage graph is? ::: The CPU stays fully busy running Low or Medium — utilisation looks healthy while the most urgent task starves.