THE FOLD / BOSS / THE WALL / THE EARLIEST DEADLINE
THE EARLIEST DEADLINE
optimal says nothing about what happens when you are wrong
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Fixed priorities are decided once, by period. Earliest-deadline-first re-decides on every tick, by whoever is closest to being late. There is a band of load where that difference is the difference between meeting every deadline and missing them.
LIT verified live. Two periodic tasks, (period 5, cost 2) and (period 7, cost 4), utilisation 0.9714. That sits above the Liu–Layland bound for two fixed-priority tasks, 0.8284, and below EDF’s bound of 1. Over 1,400 ticks EDF misses 0 deadlines. Rate-monotonic, running the identical tasks on the identical machine, misses 40.
LIT verified live. Two periodic tasks, (period 5, cost 2) and (period 7, cost 4), utilisation 0.9714. That sits above the Liu–Layland bound for two fixed-priority tasks, 0.8284, and below EDF’s bound of 1. Over 1,400 ticks EDF misses 0 deadlines. Rate-monotonic, running the identical tasks on the identical machine, misses 40.
2 HOW IT WAS WEAVED · AI + HUMAN
The bounds are Liu and Layland (1973): EDF is optimal for uniprocessor scheduling up to 100% utilisation, fixed priority only up to n(21/n−1), which falls to about 69% as n grows.
AVAN (AI) first picked a task set at utilisation 0.75 — below the fixed-priority bound of 0.7798, so both schedulers met every deadline and the comparison demonstrated nothing. The gap only exists between the two bounds. A comparison has to be run where the thing being compared can differ.
AVAN (AI) first picked a task set at utilisation 0.75 — below the fixed-priority bound of 0.7798, so both schedulers met every deadline and the comparison demonstrated nothing. The gap only exists between the two bounds. A comparison has to be run where the thing being compared can differ.
3 ONE DIMENSION
The two bounds, and the band between them.
4 TWO DIMENSIONS · INTERACTIVE
Move the load and watch the deadlines.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: whoever is closest to late.
AVAN’s addition (the inverse-companion): the forward reading is that EDF is optimal and fixed priority is not. The inverse is that optimal means nothing about what happens when you are wrong. Push a fixed-priority set past its bound and the long-period tasks miss first, predictably, and the important short ones keep running. Push EDF past 1 and it has no opinion about who matters — everything is equally close to late, so everything fails together. Read backwards, the extra 17 points of utilisation are bought by giving up the ability to fail in a chosen order.
LIT two periodic tasks of (period 5, cost 2) and (period 7, cost 4) give a utilisation of 0.9714, which is above the Liu-Layland bound of 0.8284 for two fixed-priority tasks and below EDF's bound of 1, and over 1,400 ticks EDF misses 0 deadlines while rate-monotonic - identical tasks, identical machine - misses 40
FIG The bounds are Liu and Layland (1973): EDF is optimal for uniprocessor scheduling up to 100% utilisation, fixed priority only up to n(2^(1/n)-1), which falls to about 69% as n grows. AVAN first picked a task set at utilisation 0.75 - below the fixed-priority bound of 0.7798 - so both schedulers met every deadline and the comparison demonstrated nothing. The gap only exists between the two bounds, and a comparison has to be run where the thing being compared can differ.
FIG The bounds are Liu and Layland (1973): EDF is optimal for uniprocessor scheduling up to 100% utilisation, fixed priority only up to n(2^(1/n)-1), which falls to about 69% as n grows. AVAN first picked a task set at utilisation 0.75 - below the fixed-priority bound of 0.7798 - so both schedulers met every deadline and the comparison demonstrated nothing. The gap only exists between the two bounds, and a comparison has to be run where the thing being compared can differ.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN