Scheduling Metrics and the Multi-Level Feedback Queue
In your undergraduate
CPU scheduling
course you met round-robin, FCFS, and the clairvoyant favourite Shortest-Job-First (SJF),
which minimises average turnaround — if you know each job's length in advance. That "if" is the
whole problem. A real scheduler standing at the head of the run queue has no idea whether the process it is
about to dispatch will compute for three microseconds or three hours. It cannot see the future, and yet it
must decide, thousands of times a second, who runs next.
This lesson is about scheduling under uncertainty. First we sharpen the two metrics that pull
against each other — turnaround time (good for batch throughput) and response
time (good for interactivity) — and add the softer goal of fairness. Then we
build the Multi-Level Feedback Queue (MLFQ): a scheduler that, without any oracle, watches
how each job behaves and uses that history to approximate SJF while keeping interactive jobs snappy.
Variants of MLFQ have shipped in every serious OS — from Corbató's 1962 CTSS (which won him a Turing Award)
through Solaris, FreeBSD, and the Windows NT scheduler.
The two clocks: turnaround versus response
Every metric is a difference of timestamps. Let a job i arrive at time
T^{\text{arr}}_i, first get the CPU at
T^{\text{first}}_i, and complete at
T^{\text{comp}}_i. Then
T^{\text{turnaround}}_i \;=\; T^{\text{comp}}_i - T^{\text{arr}}_i,
\qquad T^{\text{response}}_i \;=\; T^{\text{first}}_i - T^{\text{arr}}_i.
Turnaround measures the whole lifetime — how long until the job is done. Response measures only the
wait to be first heard — how long until the cursor blinks, the keystroke echoes, the window
redraws. A batch compile cares about turnaround; a shell prompt cares about response. The tragedy is that
the same policy cannot be great at both. SJF and FCFS run a job to completion, giving superb turnaround but
catastrophic response for anything queued behind a long job (the convoy effect).
Round-robin, with a short quantum, gives lovely response but drags out turnaround by time-slicing everyone.
MLFQ's whole reason for existing is to be good at both at once — to give interactive jobs
round-robin-like response while letting CPU-bound jobs finish with near-SJF turnaround, all without knowing
any job's length ahead of time.
Worked example: why order matters
Three jobs arrive together at t=0 with run lengths
A=10,\; B=4,\; C=2. Under FCFS in the order A, B, C:
| Job | Completes at | Turnaround | First runs at | Response |
|---|
| A | 10 | 10 | 0 | 0 |
| B | 14 | 14 | 10 | 10 |
| C | 16 | 16 | 14 | 14 |
Average turnaround = (10+14+16)/3 = 13.3, average response
= (0+10+14)/3 = 8. Now run shortest first (C, B, A): turnarounds
become 2, 6, 16, averaging 8, and response averages
(0+2+6)/3 = 2.7. Shortest-first crushes both averages — the short jobs stop
"hiding" behind the long one. MLFQ's trick is to discover which jobs are short by watching them,
not by being told.
The mechanism: priority queues plus feedback
MLFQ keeps several run queues, each at a distinct priority. The dispatch rule is trivial:
run a job from the highest-priority non-empty queue; among jobs at the same priority, round-robin. The
cleverness is entirely in how a job moves between queues — the "feedback". The diagram shows the
three-level version: new work lands at the top with a short quantum, and jobs sink as they prove themselves
CPU-hungry.
- Rule 1 — if \text{priority}(A) > \text{priority}(B), run
A. Higher queue always wins;
- Rule 2 — if they are equal, round-robin them within the queue;
- Rule 3 — a new job enters at the highest priority (assume it is short and
interactive until proven otherwise);
- Rule 4 — once a job uses up its time allotment at a level (whether in one
slice or several), demote it one level. Jobs that yield early (for I/O) stay put;
- Rule 5 — every S milliseconds, boost all jobs
back to the top queue, to prevent starvation and adapt to changed behaviour.
How MLFQ learns to approximate SJF
Watch what the rules do to two kinds of job. A short, interactive job (a keystroke handler, a shell) does a
little work, then blocks on I/O before exhausting its quantum. By Rule 4 it never gets demoted, so
it lives in the top queue and is dispatched almost immediately whenever it wakes — excellent response. A
long, CPU-bound job (a compile, a video encode) keeps consuming full quanta, so Rule 4 marches it steadily
down to the bottom queue, where it runs in long, efficient slices out of the interactive jobs' way —
near-SJF turnaround.
No one told MLFQ which job was short. It inferred length from observed behaviour: "how much CPU has
this job been demanding lately?" is a running estimate of its remaining burst, and the queues sort jobs by
that estimate. This is the deep idea — using past behaviour to predict future behaviour,
which is exactly the assumption SJF needs but cannot obtain directly.
// A compact MLFQ simulator. Three queues (index 2 = top/short-quantum, 0 = bottom).
// Interactive jobs yield before their quantum (block for I/O); CPU-bound jobs run full quanta.
interface Job { name: string; work: number; interactive: boolean; prio: number; }
const quantum = [40, 20, 10]; // ms at priority levels 0,1,2 (top has the SHORT quantum)
const jobs: Job[] = [
{ name: "compile", work: 120, interactive: false, prio: 2 },
{ name: "shell", work: 30, interactive: true, prio: 2 },
];
let now = 0;
// Run until all work is done. Always pick the highest-priority job with work left.
while (jobs.some((j) => j.work > 0)) {
const runnable = jobs.filter((j) => j.work > 0).sort((a, b) => b.prio - a.prio);
const j = runnable[0];
const q = quantum[j.prio];
// Interactive jobs run a short burst then block; CPU-bound jobs use the whole quantum.
const burst = j.interactive ? Math.min(5, j.work) : Math.min(q, j.work);
now += burst;
j.work -= burst;
const usedFullQuantum = !j.interactive && burst === q;
console.log(`t=${now}ms ran "${j.name}" for ${burst}ms at Q${j.prio}` +
(usedFullQuantum ? " -> demote" : ""));
if (usedFullQuantum && j.prio > 0) j.prio--; // Rule 4: demote on full-quantum use
}
console.log("all jobs finished at t=" + now + "ms");
Yes — and this is a classic exam trap. The naive Rule 4 says "demote only if you use a full
quantum in one slice." A malicious job can exploit that: run for 99% of its quantum, then issue a
pointless \texttt{read()} on something that returns instantly, yielding the CPU
just before the timer fires. It never gets demoted, so it stays in the top queue and monopolises
the machine while behaving, on paper, like an interactive job. The fix (used in real systems) is
better accounting: track the total CPU a job has consumed at a level across
all its slices, and demote once that allotment is spent — regardless of how it was
chopped up. Rule 4 above is already written this way ("time allotment", not "one slice"), precisely to close
this hole.
Students often read Rule 5 (periodic boost) as a nice-to-have. It is load-bearing. Without it, a steady
stream of interactive jobs at the top can starve the CPU-bound jobs stuck at the bottom
forever — they never get to run, never finish, and the system livelocks its background work. The
boost also fixes a second problem: a job whose behaviour changes (a compute job that becomes
interactive) would otherwise be trapped at the wrong priority. Boosting periodically re-examines everyone.
The tuning knob S is delicate — too large and starvation bites; too small and
long jobs keep floating back up and never make progress at the bottom. As Ousterhout quipped, such constants
are best set by voodoo.
Where MLFQ lives today
MLFQ is not a museum piece. The Solaris time-sharing class ships a literal MLFQ with 60
priority levels and a tunable dispatch table (\texttt{ts\_dptbl}) mapping
priority to quantum and demotion rules. Windows and older FreeBSD
schedulers are feedback-priority designs in the same family, with interactivity boosts for threads that wake
from I/O. Even Linux's older O(1) scheduler used priority arrays with dynamic bonuses. When we meet
the
Completely Fair Scheduler and
proportional-share
scheduling, notice that they attack the same tension — response versus turnaround versus
fairness — but replace MLFQ's pile of hand-tuned rules with a single clean invariant.