Multi-Level Feedback Queues and Priority Decay

Shortest-job-first is optimal for average waiting time and unimplementable, because it requires the scheduler to know each job’s total service demand before it starts. Multi-level feedback queuing is the standard approximation: it infers a job’s length from how it has behaved so far and adjusts its priority to match the guess. The inference is wrong often enough that the design has to be defended against its own conclusions, and the defences, which are decay rules, periodic boosts, and gaming countermeasures, are where most of the real complexity sits.

The structure itself is simple. Instead of one run queue there are several, each with a distinct priority, and each thread belongs to exactly one of them at a time. A thread that uses its whole slice without blocking is demoted to the next queue down; a thread that blocks before its slice expires keeps its level or is promoted. The scheduler always picks from the highest non-empty queue. A thread’s level is thus a decaying record of its recent CPU appetite, and CPU-bound threads sink while interactive ones float.

Why demotion approximates shortest-first

Consider a mix of one long compute job and a stream of short interactive requests. At the top level, the interactive requests consume a fraction of a slice, block, and return to the same level. The compute job burns its full slice and is demoted. Once demoted, it only runs when no interactive thread is runnable, which is exactly the ordering shortest-job-first would have chosen: the short jobs are served at high priority because they are short, and the long job absorbs the leftovers.

The approximation degrades when a thread’s behaviour is not stationary. A batch job that starts with a long compute phase and later becomes interactive is penalised for the first phase for as long as its demotions persist. A thread that is genuinely CPU-bound but only needs a few milliseconds per wakeup looks interactive and keeps its high priority, which is correct from a latency standpoint and unfair from a throughput one, since it may crowd out a compute thread that has been waiting longer.

The level count matters. With n levels and a rule that demotes one level per expired slice, a thread reaches the bottom after n slices. The top level therefore serves threads that block within one slice, the next serves those that need up to two, and the bottom serves everything else. A level count in the range of a handful to a few dozen covers the useful range; more levels only stretch the tail, and the difference between level 40 and level 41 is not a meaningful distinction.

The slice per level

Queues are usually not just different priorities; they also carry different slice lengths. The classic arrangement gives the top queue the shortest slices and lengthens them downwards. The reasoning is that a high-priority thread is expected to block quickly, so a short slice is enough to let it finish and costs little if the expectation is wrong, while a low-priority thread is expected to be a compute job, so a long slice amortises the switch cost over more work and refills the cache before the next switch throws it away.

This creates a tension with the demotion rule. A level’s slice length sets how much service a thread gets before the demotion question is asked, so the same thread is classified differently depending on which level it is at. A thread needing 8 milliseconds per burst exceeds a 4 millisecond slice and is demoted on its first expiry, then exceeds the next level’s slice too if that one is also short; the same burst fits inside a 16 millisecond slice and costs it nothing. The mapping from behaviour to level therefore depends on the slice schedule as much as on the thread, which makes the policy sensitive to the exact constants chosen and is why the level assignment in real systems is often a formula over measured CPU use rather than a strict per-slice countdown.

/* One selection pass over a level array. Levels 0..n-1, higher index = lower
   priority. Threads at level i have slice_ms[i] to spend. */
struct thread *pick(struct rq *q)
{
    for (int i = 0; i < q->nlevels; i++) {
        if (!list_empty(&q->level[i]))
            return list_first_entry(&q->level[i], struct thread, link);
    }
    return &q->idle;
}

/* Called when the running thread's slice expires without it blocking. */
void expire(struct rq *q, struct thread *t)
{
    if (t->level + 1 < q->nlevels)
        t->level++;                     /* demote one step */
    t->slice_left = q->slice_ms[t->level];
    list_move_tail(&t->link, &q->level[t->level]);
}

Note the list_move_tail. Threads at the same level are ordered by arrival, so a demoted thread goes behind its peers at the new level rather than ahead of them. Without that detail, a thread that is repeatedly demoted could still run first at each level it reaches, and the round-robin property within a level would be lost.

Gaming the rule

Any policy that rewards a behaviour can be triggered deliberately. The classic exploit against multi-level feedback is to yield just before the slice expires. A thread that does so is never demoted, keeps its high priority, and consumes as much CPU as it wants while appearing interactive. The scheduler’s inference, “blocks early, therefore short”, is satisfied by a thread that blocks artificially.

Several countermeasures exist and they are all approximations of the same idea: judge a thread by total consumption over a window, not by the shape of each individual burst.

The first is to measure CPU use per wall-clock period rather than per slice. A thread that yields constantly still accumulates the same total time, so once its accumulated use in the current period crosses a threshold it is demoted regardless of how the time was chopped up.

The second is to charge the yielding thread for a minimum quantum. If a yield costs a full slice’s worth of accounting credit, yielding early buys nothing. This is blunt but effective, and it makes the yield system call’s cost proportional to the policy’s needs rather than to the work actually done.

The third is a periodic boost: every so often, all threads are moved to the top level regardless of history. The boost erases accumulated demotions, which bounds the damage a misclassification can do, and it also prevents the starvation that pure demotion would otherwise cause: a low-priority compute thread is guaranteed to reach the top level eventually, at which point it runs ahead of the long-lived CPU hogs that were demoted alongside it.

The boost’s period is the policy’s worst-case latency bound. If the interval is one second, no thread can wait more than roughly one second plus the time to drain the higher levels before it gets a high-priority turn. That is a weak bound but a real one, and it is the only latency guarantee the structure offers.

Priority inversion inside the levels

The level is not the only ordering signal. A thread that holds a lock another thread needs must be allowed to run, and a demoted lock holder can block a high-priority thread indefinitely. The inheritance machinery that fixes this operates on the scheduler’s notion of priority, which in a multi-level structure is the level plus any explicit priority the thread was given. The interaction is uncomfortable: inheritance raises a thread’s effective level, but the demotion rule can lower it again at the next slice expiry, undoing the fix while the lock is still held. Implementations handle this by suppressing demotion for a thread with an inherited priority, which means the level is no longer a pure function of observed behaviour. The general problem is treated in Priority Inversion and Inheritance.

A similar conflict appears when the structure is used as the base for a fair-share scheduler. Level membership is a coarse, hysteretic quantity, while fair share needs a continuous measure of consumed service. Systems that want both typically keep the levels for latency-sensitive classification and add a separate weighted accounting layer within each level, so that two threads at the same level still split the CPU by weight. The accounting that makes that work is virtual runtime, and it composes with levels only if the weight is applied consistently across demotions.

Decay without a boost

A design that relies on decay alone, with demotion on slice expiry, promotion on blocking, and no periodic reset, has a specific failure mode: the level distribution collapses to the bottom over time under sustained load. Every thread eventually exhausts enough slices to reach the lowest level, at which point the levels carry no information and the policy degenerates into round-robin among all threads at the bottom, with the high levels idle. The system still functions, but the latency advantage that justified the structure is gone, and it is gone silently, because no counter reports “the levels have flattened”.

The countermeasure is the boost, and its cost is that it periodically destroys the information the structure spent effort accumulating. After a boost, every thread is at the top level, so the first slice after the boost is a round-robin among all threads, and the classification has to be rebuilt from scratch. Choosing the boost period is therefore a direct trade between the quality of the inference and the strength of the starvation bound, and there is no value that optimises both.

This trade is why the structure survives mostly as a component rather than as a whole scheduler. It is excellent at separating a small number of latency-critical threads from a mass of background work with almost no computation, and it is poor at providing any quantitative fairness guarantee, because its notion of priority is ordinal and its history is deliberately forgetful. Where a numeric guarantee is required, such as a specified share of the CPU or a specified response time, the accounting has to be explicit, as in Hierarchical Fair Share and Lag Accounting.