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

Before we can even state the priority-inversion problem cleanly, we need a small toolbox of ideas. The parent note throws around words like preemptive, mutex, critical section, priority, bounded, and symbols like $B_H$ and ${\text{CS}}_{j,k}$. This page builds every one of them from nothing, in an order where each idea rests on the one before it.

1. A task — the thing that wants to run

The picture: imagine three people (three tasks) and a single chair (the processor). Only the person in the chair is running. Others stand in line — that's ready. Someone who has stepped away to wait for a delivery is blocked — they can't sit even if the chair is free.

Why the topic needs it: priority inversion is a story about which task is in the chair at each moment, so we must first agree on what a task is and what state it's in. See RTOS task states and context switching for the full state machine.

2. Priority — the number that decides who sits

The picture: think of a "VIP rank" tag on each person. When two people both want the single chair, the one with the higher rank gets it.

Look at the figure: the taller the bar, the higher the priority. H towers over M, M over L. Keep this height-picture in your head — every timeline later is just these three heights taking turns in the chair.

3. Preemption — kicking someone out of the chair

The picture: a VIP walks in; security immediately lifts the current sitter out of the chair (gently, saving their place) and seats the VIP. That lift-and-swap is called a context switch.

Why the topic needs it: this is rule #1 of the two clashing rules. It says "urgency alone decides the chair." Priority inversion happens because a second rule (the mutex, next) is allowed to break this one.

4. Shared resource & mutual exclusion — the one-key door

The picture: a phone booth (the resource) with exactly one key. Whoever holds the key is inside the booth = inside their critical section. Anyone else who wants in must wait outside the locked door, blocked.

Why the topic needs it: this is rule #2, and it contradicts rule #1. The mutex says "whoever grabbed the key first stays, regardless of rank." So a low-rank task holding the key can make a high-rank task wait — priority temporarily upside-down. That contradiction is the seed of inversion. (For the difference between a mutex and its cousin the semaphore, see Mutexes vs Semaphores.)

5. Blocking — waiting on someone below you

The picture: the VIP (H) stands frozen outside the phone booth while an ordinary person (L) chats inside holding the only key. The VIP's rank is useless at the door — the key, not the rank, decides entry.

Why the topic needs it: every solution in the parent note is measured by how long this backwards wait can last. That length gets its own symbol next.

6. Bounded vs unbounded — does the wait have a ceiling in time?

The picture: bounded = a wait with a wall you can measure to (say "at most 5 ms"). Unbounded = a hallway that keeps getting longer every time task M decides to run more.

Read the figure top-to-bottom as time. In the bounded row H waits only while L finishes its short critical section. In the unbounded row, M keeps stealing the chair from L, so L can't return the key, so H's wait stretches with M's runtime — no wall in sight.

Why the topic needs it: bounded inversion is unavoidable and fine. Unbounded inversion is the actual bug (it crashed Mars Pathfinder). The whole point of priority inheritance and priority ceiling is to convert unbounded into bounded. To turn "bounded" into a real deadline guarantee you feed it into Schedulability analysis & response-time analysis.

7. The symbols: $B_H$ and ${\text{CS}}_{j,k}$

Now that the ideas exist, the parent note's math symbols are just shorthand.

Why we need $B_H$ specifically: a hard real-time task must always finish before its deadline. Its response time = its own work plus whatever it's forced to wait for. That forced wait is exactly $B_H$. If $B_H$ is bounded, we can add it in and prove the deadline is met; if it's unbounded, no proof is possible — the system is unsafe by design. This is why every protocol is judged by the size of $B_H$. (Estimating each task's own run-time is a separate craft — see Worst-Case Execution Time (WCET) analysis.)

Prerequisite map

Read it bottom-up: tasks and priorities feed preemption; resources feed the mutex; those two streams meet at blocking, which is what makes a wait bounded or unbounded, which is what the symbols measure — and all of it pours into the priority-inversion topic itself.

Equipment checklist

Self-test — cover the right side and say the answer aloud before revealing.

Next page (D2) builds the priority ceiling number and proves why the ceiling rule forbids deadlock. Back to the hub: parent topic.