Preemption and multilevel queues

Why it matters

A good scheduler makes a text editor feel instant while a compile hogs every core. It cannot ask threads whether they are interactive; it has to infer it. The multilevel feedback queue is the classic answer, and its ideas (separate classes of work, demote what uses a lot, boost what has waited, prevent gaming) reappear whenever you design a system that serves both latency-sensitive and bulk work.

The idea

Preemption

A non-preemptive scheduler only switches when the running thread blocks or finishes, so one compute-heavy thread can hold a core indefinitely. A preemptive scheduler uses a timer interrupt to take the core back when a time slice expires, or when a more urgent thread becomes runnable. Every general-purpose operating system today is preemptive; it is what keeps a runaway loop from freezing the machine. Within the kernel, preemption points are more limited, and a configurable kernel can trade some throughput for lower latency by allowing preemption in more places.

Multiple queues by urgency

Instead of one run queue, keep several, ranked by urgency: system threads above interactive ones above batch ones. Always run from the most urgent non-empty queue; within a queue, round robin. This serves the important work first, and it introduces the risk that lower queues starve if the upper ones are never empty. Fixed classes also require someone to classify each thread in advance, which is rarely possible.

The multilevel feedback queue

The MLFQ classifies threads automatically by watching them.

1. 1

   Start at the top

   A new thread enters the most urgent queue, assuming it might be interactive.
2. 2

   Demote heavy users

   If a thread uses its entire slice, it is probably compute-bound, so it moves down a queue. Lower queues get longer slices, which suits batch work's need for long, cache-friendly runs.
3. 3

   Keep the interactive at the top

   A thread that blocks for I/O before its slice ends stays where it is, so editors, shells and request handlers stay in the urgent queues.
4. 4

   Boost periodically

   Every so often, move every thread back to the top. This prevents starvation of batch threads and lets a thread whose behaviour changed (a compiler that becomes interactive) be reclassified.
5. 5

   Account for total use, not per-slice use

   If demotion only looked at single slices, a thread could game the scheduler by sleeping just before each slice ends. Tracking total CPU used at a level closes that loophole.

Aging

Aging is the general fix for starvation in any ranked scheduler: the longer a thread has waited, the more its effective urgency rises, until it eventually runs. MLFQ's periodic boost is a coarse form of aging; job systems and network schedulers use continuous versions. Unix's traditional scheduler, and Windows', raise the urgency of threads that have waited and lower it for those that have used a lot of CPU, which is MLFQ in spirit.

User influence

Systems also let users bias the scheduler. Unix nice values (from −20 to 19) mark a process as more or less deserving of CPU; batch jobs run with a high nice value so they yield to everything else. Windows has scheduling classes and a foreground boost for the active window. In containers and cgroups, CPU shares and quotas do the same per group.

Trade-offs

Preemption buys responsiveness and robustness against runaway threads at the cost of switches and harder kernel design. Ranked queues serve urgent work first and need aging to avoid starvation. MLFQ adapts to behaviour without hints but has many tuning knobs (number of queues, slice lengths, boost interval) and was historically gameable. Simpler policies are easier to predict; adaptive ones fit mixed workloads better.

In an interview

Apply the pattern to application queues: "Interactive requests and bulk exports share a worker fleet, so we use two queues with the interactive one served first, a cap on how long bulk work can wait (aging), and demotion of any tenant that consumes more than its share in a window, which is a multilevel feedback queue at the application layer."