THE FOLD / RESPAWN / SECOND WIND / THE MULTILEVEL FEEDBACK
THE MULTILEVEL FEEDBACK
a fee levied on evidence, not a conclusion drawn from it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Shortest-job-first needs to know how long each job will run, which nothing does. The multi-level feedback queue guesses instead: start everything at the top, and demote anything that uses its whole slice. A job that keeps running proves it is long.
LIT verified live. 300 jobs, 238 short and the rest long. FIFO gives a mean turnaround of 6,484.6. An oracle running true shortest-first gives 1,480.2. The feedback queue — three levels, quanta 4/16/64, and no knowledge of any job’s length — gives 2,867.5: 2.26× better than FIFO, and 1.94× off the oracle it cannot see.
LIT verified live. 300 jobs, 238 short and the rest long. FIFO gives a mean turnaround of 6,484.6. An oracle running true shortest-first gives 1,480.2. The feedback queue — three levels, quanta 4/16/64, and no knowledge of any job’s length — gives 2,867.5: 2.26× better than FIFO, and 1.94× off the oracle it cannot see.
2 HOW IT WAS WEAVED · AI + HUMAN
MLFQ is the scheduler in the classic Unix lineage; the demotion rule is the whole idea, and Corbató’s CTSS had it in 1962.
AVAN (AI) published the oracle column because without it “2.26× better than FIFO” sounds like the end of the story. The gap to the oracle is 1.94×, and that gap is the standing price of not knowing — the thing the technique is designed around rather than the thing it removes.
AVAN (AI) published the oracle column because without it “2.26× better than FIFO” sounds like the end of the story. The gap to the oracle is 1.94×, and that gap is the standing price of not knowing — the thing the technique is designed around rather than the thing it removes.
3 ONE DIMENSION
Three schedulers, one of which is not allowed to look.
4 TWO DIMENSIONS · INTERACTIVE
Change the quanta and watch jobs fall through the levels.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: falling through the levels.
AVAN’s addition (the inverse-companion): the forward reading is that the feedback queue learns which jobs are short. The inverse is that it learns nothing — it charges for the answer. A job is demoted for having run, which is a fee levied on evidence, not a conclusion drawn from it, and the scheduler never holds a belief about anything. Read backwards, that is exactly why it cannot be fooled by a job lying about its length, and exactly why a long job that turns interactive stays punished for a past it has already left.
LIT 300 jobs of which 238 are short give a FIFO mean turnaround of 6,484.6 and an oracle running true shortest-first 1,480.2, while a three-level feedback queue with quanta 4/16/64 and no knowledge of any job's length gives 2,867.5 - 2.26 times better than FIFO and 1.94 times off the oracle it cannot see
FIG MLFQ is the scheduler in the classic Unix lineage; the demotion rule is the whole idea, and Corbato's CTSS had it in 1962. AVAN published the oracle column because without it 2.26 times better than FIFO sounds like the end of the story. The gap to the oracle is 1.94, and that gap is the standing price of not knowing - the thing the technique is designed around rather than the thing it removes.
FIG MLFQ is the scheduler in the classic Unix lineage; the demotion rule is the whole idea, and Corbato's CTSS had it in 1962. AVAN published the oracle column because without it 2.26 times better than FIFO sounds like the end of the story. The gap to the oracle is 1.94, and that gap is the standing price of not knowing - the thing the technique is designed around rather than the thing it removes.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN