THE FOLD / RESPAWN / HARD RESET / THE PRIORITY INVERSION
THE PRIORITY INVERSION
the highest waits on the lowest
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The highest-priority task is waiting for a lock held by the lowest. A middle-priority task, holding no lock and wanting nothing, preempts the low one — and the highest-priority task in the system now waits on the one thing it outranks.
LIT verified live. a low task holds a critical section of 10 ticks; a medium task runs for m ticks; a high task needs the lock. Without priority inheritance the high task’s delay is 10 + m — sweeping m from 0 to 100 gives a straight line of slope 1, ending at 110. With inheritance the low task temporarily runs at high priority, the medium task cannot preempt it, and the delay is 10 at every point on the sweep — flat, bounded by the critical section alone. Across all 50 medium-runtimes tested, 50 are inverted without inheritance and 0 with it.
LIT verified live. a low task holds a critical section of 10 ticks; a medium task runs for m ticks; a high task needs the lock. Without priority inheritance the high task’s delay is 10 + m — sweeping m from 0 to 100 gives a straight line of slope 1, ending at 110. With inheritance the low task temporarily runs at high priority, the medium task cannot preempt it, and the delay is 10 at every point on the sweep — flat, bounded by the critical section alone. Across all 50 medium-runtimes tested, 50 are inverted without inheritance and 0 with it.
2 HOW IT WAS WEAVED · AI + HUMAN
Priority inversion and the priority-inheritance and priority-ceiling protocols are Sha, Rajkumar and Lehoczky, 1990. The famous instance is Mars Pathfinder, July 1997: the lander kept resetting on Mars and the cause was an inversion on a shared information bus, fixed by enabling inheritance on an already-shipped mutex.
AVAN (AI) reports the shape rather than the anecdote. The number that matters is the slope: without inheritance the high-priority task’s delay is a function of a task it has nothing to do with, so the bound is not merely large, it is not a bound at all — it is whatever the middle of the system happens to be doing.
AVAN (AI) reports the shape rather than the anecdote. The number that matters is the slope: without inheritance the high-priority task’s delay is a function of a task it has nothing to do with, so the bound is not merely large, it is not a bound at all — it is whatever the middle of the system happens to be doing.
3 ONE DIMENSION
Bounded by the lock, or bounded by a stranger.
4 TWO DIMENSIONS · INTERACTIVE
Give the medium task more work and watch who pays for it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that inheritance fixes the inversion. The inverse is that priority was never a property of a task — it is a property of a task and everything it happens to be waiting on. A scheduler assigns numbers to threads; the lock silently rewrites them, so the effective priority of the high task becomes the priority of whoever holds what it needs. Read backwards, inheritance does not repair a broken scheduler; it makes the scheduler’s numbers mean what they already claimed to mean, and a system without it has a priority ordering that is decorative below the first shared resource.
LIT a low task holds a critical section of 10 ticks, a medium task runs for m ticks, and a high task needs the lock: without priority inheritance the high task's delay is 10 + m, so sweeping m from 0 to 100 gives a straight line of slope 1 ending at 110, while with inheritance the low task temporarily runs at high priority, the medium task cannot preempt it, and the delay is 10 at every point on the sweep - and across all 50 medium-runtimes tested, 50 are inverted without inheritance and 0 with it
FIG Priority inversion and the inheritance and ceiling protocols are Sha, Rajkumar and Lehoczky, 1990. The famous instance is Mars Pathfinder, July 1997: the lander kept resetting on Mars, the cause was an inversion on a shared information bus, and the fix was enabling inheritance on an already-shipped mutex. AVAN reports the shape rather than the anecdote. The number that matters is the SLOPE: without inheritance the delay is a function of a task it has nothing to do with, so the bound is not merely large, it is not a bound at all.
FIG Priority inversion and the inheritance and ceiling protocols are Sha, Rajkumar and Lehoczky, 1990. The famous instance is Mars Pathfinder, July 1997: the lander kept resetting on Mars, the cause was an inversion on a shared information bus, and the fix was enabling inheritance on an already-shipped mutex. AVAN reports the shape rather than the anecdote. The number that matters is the SLOPE: without inheritance the delay is a function of a task it has nothing to do with, so the bound is not merely large, it is not a bound at all.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HARD RESET · David Lee Wise (ROOT0), with AVAN