MLFQ & Priority Scheduling

Round-robin is fair and fairness is not enough. The job you're waiting on (a keystroke handler) and the job nobody's waiting on (a 6-hour batch encode) get identical treatment. SJF fixes that on paper — run short jobs first — but requires knowing the future. The Multi-Level Feedback Queue is the classic answer, still recognizable inside Windows and macOS today: predict the future from the past, and let jobs sort themselves.

The structure

Take round-robin and stack it:

Q2 (high)   quantum  2ms   ← new jobs start here
Q1 (mid)    quantum  4ms
Q0 (low)    quantum  8ms

Rules of the game:

1. Always run from the highest non-empty queue. Q0 runs only when Q1 and Q2 are empty.
2. Within a queue: plain round-robin.
3. New jobs enter the top queue.
4. Use your entire quantum → get demoted one level. Yield the CPU before it expires (typically by blocking on I/O) → stay put.
5. Lower queues get longer quanta — if you're clearly a long-running job, fewer, bigger slices waste less on switching.

Rule 4 is the feedback that gives the algorithm its name. The scheduler learns each job's nature by watching it: interactive jobs (short bursts, frequent blocking) never exhaust a quantum, so they stay high-priority and get the CPU the instant they want it. CPU-hogs chew through quantum after quantum and sink to the bottom, where they duke it out round-robin style with the other heavyweights. MLFQ approximates SJF without asking anyone anything.

Trace it by hand

One CPU-bound job J (needs 10ms) in the three-queue setup above, alone:

t=0   J starts in Q2, runs 2ms (full quantum) → demoted to Q1
t=2   J runs 4ms in Q1 (full quantum)         → demoted to Q0
t=6   J runs 4ms of Q0's 8ms quantum          → done at t=10

Now drop an interactive job in at t=3 — it lands in Q2, and by Rule 1 it preempts J instantly, runs its 1ms burst, blocks, and J resumes. The batch job never blocks the keystroke; the keystroke barely delays the batch job. That's the whole pitch, visible in a 10-millisecond trace.

Your exercise is this machine, distilled: CPU-bound batch jobs, configurable queues and quanta, Rules 1–5, no I/O and no boost (below) — the deterministic core. Get the demotion bookkeeping exact; almost every wrong answer is a job demoted one quantum too early or late.

The two classic failure modes

Starvation. Enough interactive traffic in Q2 and the bottom queue never runs. Real MLFQs add a priority boost: every second or so, throw every job back into the top queue. Long-running jobs get periodic sips of CPU no matter what.

Gaming. A hostile job could run 99% of its quantum, issue a trivial 1-byte I/O to "block," and stay high-priority forever. The fix: charge by total CPU used at a level, not per-burst — once you've consumed a level's allowance, you're demoted, however cleverly you sliced it.

Both fixes are one sentence each, and both are exactly the kind of policy patch you can now reason about because the mechanism is yours.

Where the real world landed

Windows and macOS run recognizable descendants of MLFQ (priority bands + feedback + boosting). Linux went a different way: CFS tracked each task's virtual runtime and always ran the task that had gotten the least, turning "priority" into a continuous fairness metric rather than discrete queues (its successor, EEVDF, refines the same idea with deadlines). Different math, same problem — and having built MLFQ, you can read either design doc and recognize every tradeoff they're arguing about.