Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 8, Arpaci-Dusseau & Arpaci-Dusseau

Scheduling: The Multi-Level Feedback Queue

MLFQ (Corbató et al., CTSS, 1962) is one of the classic schedulers. Many modern systems still use a relative of it.

Goals (without knowing job length up front):

Goal	Classic approach	Problem
Good turnaround	SJF / STCF (short jobs first)	OS rarely knows length — see Scheduling Introduction
Good response time	Round robin	Terrible turnaround for long jobs

Crux: how to schedule without perfect knowledge — learn from how jobs behave?

Learn from history

MLFQ predicts the future from the past (like caches and branch predictors). Works when jobs have phases — and can be wrong when they don’t.

Basic structure

Many queues, each a priority. A ready job sits on exactly one queue.

• Rule 1: Higher priority runs; lower does not.
• Rule 2: Same priority → round-robin with that queue’s time slice.

Priority is not fixed: MLFQ raises/lowers it from observed behavior (interactive vs CPU hog).

Attempt #1: how priority changes

Workload mix: short/interactive + long CPU-bound.

• Rule 3: New job → top queue (assume it might be short).
• Rule 4a (old): Uses full time slice → demote one level.
• Rule 4b (old): Gives up CPU early → stay at same level.

Effects:

1. Long job — enters top, burns slices, sinks to bottom, stays there.
2. Short job arrives — starts high, finishes before sinking far → approximates SJF.
3. I/O-heavy interactive — often yields early → stays high → good response time.

Quiz

Rank the sequence

1 / 1

Order what happens to a long, CPU-bound job under the original MLFQ rules (Rules 3/4a/4b), from arrival onward.

OrderDrag the handle to rearrange — top should be first.

1. ⋮⋮1It settles at the bottom queue, sharing the CPU round-robin with other long jobs
2. ⋮⋮2It repeatedly uses its full time slice and gets demoted one level each time
3. ⋮⋮3It arrives and is placed in the topmost queue

Drag items into the correct order (or use ↑↓), then check.

Flaws

Problem	Why
Starvation	Too many interactive jobs → long jobs never run
Gaming	Fake I/O just before slice ends → stay high forever
Phase change	CPU-bound job becomes interactive but is stuck low

Scheduling policy is also a security concern in shared systems.

Attempt #2: priority boost

• Rule 5: Every period S, move all jobs to the topmost queue.

Fixes starvation and gives reformed interactive jobs a second chance. S is a classic “voo-doo constant” (Ousterhout): too large → starve; too small → interactive share suffers.

Attempt #3: better accounting

Replace 4a/4b with:

• Rule 4: Once a job uses up its CPU allotment at a level (one burst or many), demote — I/O games don’t reset the meter.

Tuning

Typical extras:

• Shorter quanta at high priority; longer at low (batch efficiency)
• Solaris TS: configurable tables (~60 queues, boost ~1 s)
• Some systems: decay-usage formulas (BSD), reserve top for OS, user advice (nice)

Avoid voo-doo constants

Hard in practice — defaults + admin knobs are common. Prefer learning parameters when you can.

Refined MLFQ rules

1. Higher priority runs.
2. Same priority → RR with that queue’s quantum.
3. New jobs start at the top.
4. Exhaust allotment at a level → demote (cumulative CPU).
5. Periodically boost everyone to the top.

Result: learn job type online → short/interactive get good service; long jobs still make progress.

Interactive: watch the queues

Try: long demotion · short arrival (SJF-like) · I/O interactive · priority boost · anti-gaming.

Check your understanding

Quiz

Multi-level feedback queue

1 / 4

MLFQ places a newly arrived job…

Pick an answer to see if you are right.

Coding challenges

Python helpers that mirror how you reason about mlfq.py.

Homework lab: mlfq.py

Use the OSTEP MLFQ simulator (mlfq.py). Predict traces before -c. Notes/screenshots save in this browser.

Lab

Homework: mlfq.py

0/6 started

Loading lab…

Summary

Idea	Role
Multiple priority queues	Who is eligible
Feedback / history	Learn short vs long vs interactive
Boost every S	No starvation; phase changes
Cumulative allotment	Resist gaming
Varying quanta	Latency high, throughput low

Next: Proportional Share — lottery, stride, and Linux CFS.

Previous: Scheduling Introduction — FIFO, SJF, STCF, RR.

Further Reading

• Remzi & Andrea Arpaci-Dusseau — Operating Systems: Three Easy Pieces Ch. 8
• OSTEP mlfq homework
• Corbató et al. — CTSS (1962); Solaris TS / BSD decay-usage variants