The idea: let a job's past decide its priority
A scheduler would like to run short jobs first (that gives the best turnaround) and to answer interactive programs quickly (that gives the best response). But it does not know how long a job will run, or whether it is interactive. The multi-level feedback queue (MLFQ) does not ask. It watches how each job uses the CPU and moves it between several queues. Corbató's CTSS used it in 1962, and Unix, Solaris and Windows schedulers are built on the same idea.
The page runs one CPU with three queues and up to three jobs, one tick per step. Above: the queues (the head is on the left), the CPU and the jobs that have not arrived, are blocked on I/O or have finished. Below: a Gantt chart. A coloured cell means the job ran in that tick, and the digit in it is the queue it ran from, so you can watch a job sink. On the right of each row: the job's queue, its counter and its CPU ticks so far.
The five rules
These are the rules as the OSTEP textbook states them. The page uses quanta of 2, 4 and 8 ticks, and the allotment of a queue (how much CPU a job may use there before it moves down) equals its quantum.
- Rule 1. If A is in a higher queue than B, A runs. A job that becomes ready in a higher queue preempts the running job at the next tick.
- Rule 2. Jobs in the same queue take turns, round robin, with that queue's quantum.
- Rule 3. A new job enters the top queue, Q0.
- Rule 4a/4b (the first try). A job that uses its whole quantum moves down one queue. A job that gives up the CPU before that, for example to wait for I/O, stays where it is, and its count starts again at 0.
Rule 4 (the fix). Count all the CPU a job uses in its queue, across I/O waits. Once it has used its allotment, in one go or in pieces, it moves down. - Rule 5. Every S ticks, move every job back to Q0 (the priority boost).
The quanta grow downwards: jobs at the top are short and interactive, so a short quantum keeps the response quick; jobs at the bottom are long, so a long quantum saves context switches.
A long job sinks, a short job finishes fast
A needs 14 ticks of CPU. It runs 2 ticks in Q0, 4 in Q1, then sits in Q2. At tick 8, B arrives with 3 ticks of work. B enters Q0, so it preempts A at once, runs 2 ticks, drops to Q1 and is done at tick 11: turnaround 3. A is done at tick 17. The scheduler never knew that B was short; it just gave every new job a turn at the top, and short jobs finish before they sink. So MLFQ behaves like shortest job first without knowing job lengths (Demo: a long job sinks, a short one is quick).
I/O-bound jobs stay on top
I runs 1 tick, then waits 3 ticks for I/O, seven times. It always gives up the CPU before its quantum of 2 is up, so under Rule 4b it stays in Q0, and every time its I/O ends it preempts A at the next tick. In the demo, I waits 0 ticks in a queue in all 7 bursts: an editor or a shell that runs this way feels instant. A, in Q2, gets every tick that I does not want and is done at tick 21 (Demo: an I/O-bound job stays on top).
Starvation and the priority boost
Rules 1 to 4 have a hole. With two interactive jobs, I1 and I2, that run 1 tick and wait 1 tick, there is always a job ready in Q0, and the CPU-bound A in Q1 never runs again. In the demo A gets 4 ticks of CPU and then waits 36 ticks and counting (Demo: starvation of a CPU-bound job).
Rule 5 fixes it. With a boost every 10 ticks, A is back in Q0 at ticks 10, 20 and 30, gets one quantum of 2 ticks each time, and is done at tick 32 (Demo: priority boost ends the starvation). The boost also helps a job that changes its behaviour: a long computation that turns interactive gets back to the top at the next boost. The cost is choosing S. Too long and CPU-bound jobs starve; too short and interactive jobs keep sharing the top with jobs that do not need it. OSTEP calls such values "voo-doo constants".
Gaming the scheduler, and the accounting fix
Rule 4b can be exploited. G wants the CPU all the time, but it does a tiny I/O after 1 tick, just before its quantum of 2 ends. To Rule 4b it looks interactive, so it stays in Q0 for ever. In 40 ticks G gets 18 CPU ticks, A 14 and B 8, when a fair share would be about 13 each (Demo: a job games the scheduler).
Rule 4 closes the hole by keeping the count across I/O. G's 1-tick pieces add up: after 2 ticks in Q0 and 4 in Q1 it is in Q2, and over 40 ticks it gets 7 CPU ticks while A gets 19 and B 14 (Demo: the accounting fix stops the gamer). An honest I/O-bound job also sinks slowly under Rule 4; the boost brings it back. With all five rules and a boost every 10 ticks, A and B get 16 ticks each and G 8 (Demo: all five rules together). G gets less than a third because it only wants the CPU every other tick.
The demos in numbers
| Demo | Rule 4 | Boost | Result |
|---|---|---|---|
| a long job sinks | 4a/4b | off | B turnaround 3, A 17; average 10 |
| I/O-bound job | 4a/4b | off | I stays in Q0, waits 0 ticks; A done at 21 |
| starvation | 4a/4b | off | A runs 4 ticks, then waits 36 and is not done at tick 40 |
| boost | 4a/4b | every 10 | A done at 32 |
| gaming | 4a/4b | off | CPU ticks in 40: G 18, A 14, B 8 |
| accounting fix | 4 | off | G 7, A 19, B 14; G ends in Q2 |
| all five rules | 4 | every 10 | A 16, B 16, G 8 |
MLFQ in real systems
- CTSS (MIT, 1962) had several priority levels; a job that used its whole quantum went down a level and got a longer quantum there.
- Solaris time-sharing class: 60 levels, set by a table the administrator can change. Quanta go from 20 ms at the top to a few hundred ms at the bottom, and priorities are boosted about once a second.
- FreeBSD's ULE scheduler does not move jobs one level at a time. It computes an interactivity score from how long a thread slept compared with how long it ran, and threads with a good score go into a queue that runs first.
- Windows boosts a thread's priority for a short time when its I/O completes or its window comes to the front, and the boost decays as it runs.
- Linux moved away from this: the O(1) scheduler (2.6.0) guessed interactivity with heuristics; CFS (2.6.23) and EEVDF (6.6) share the CPU by weights instead of queue levels. See CPU Scheduling for FCFS, SJF, round robin, priority and CFS on the same workloads.
Fixed real-time priorities, where a job never moves between levels, are on Real-Time Scheduling and Priority Inversion. The timer interrupt that lets Rule 1 take the CPU away is on Preemptive vs Cooperative scheduling, and what each switch costs is on Linux Context Switch.
See also Lottery and Stride Scheduling, which shares the CPU by tickets instead of priority levels.
What the page leaves out
- One CPU, whole ticks, and the scheduler acts only at tick boundaries. A real kernel switches the moment a job blocks, and context switches cost time.
- The allotment equals the quantum. OSTEP and real schedulers can give a queue a larger allotment than its quantum, so a job takes several turns there before it moves down.
- I/O takes a fixed number of ticks and there is no I/O queue. When jobs arrive, finish I/O and get preempted in the same tick, the page uses one fixed order: boost, I/O done, arrivals, then preemption.
- No nice values, no user-set priorities and no multi-CPU load balancing.