Virtual Runtime and Weighted Fair Queuing

Round-robin over a run queue gives every thread the same number of slices. That is equal treatment and it is not the same as fair treatment, because threads have different weights: some are interactive and should get the CPU promptly, some are background and should get whatever is left. Weighted fair queuing gives each thread a share proportional to an assigned weight, and it does so by scheduling on a fictitious clock that advances at a rate determined by the weight rather than by wall time.

The idea is borrowed from network packet scheduling, where it has a precise formulation: tag each packet with the time at which it would depart under a hypothetical fluid server that divides bandwidth in proportion to weights, then transmit in tag order. Applied to CPU time, the “packet” is a slice and the “bandwidth” is the processor. The tag is the thread’s virtual runtime, and the scheduler picks the runnable thread with the smallest one.

The virtual clock

Let a thread have weight w and let W be the sum of weights of all runnable threads. If the thread runs for a wall-clock interval dt, its virtual runtime advances by dt · w₀ / w, where w₀ is any fixed reference weight. Two threads with equal weights therefore advance at the same rate, and the one that has run less has the smaller virtual runtime and is chosen next. A thread with twice the weight of another advances at half the rate, so it can run twice as long before its virtual runtime catches up. The selection rule, always run the minimum, produces the intended share automatically, without any explicit division of the CPU.

The choice of reference weight only sets the units. It is convenient to pick one that makes the common case advance at approximately wall-clock rate, so virtual runtime and elapsed time are comparable for default-priority threads. It has no effect on the shares.

The property that makes this work is that the difference between any two threads’ virtual runtimes stays bounded while both are runnable. If thread A’s virtual runtime falls behind B’s by more than one slice’s worth of advance, A must be selected, so the gap cannot grow beyond roughly one slice. That bound, expressed in virtual units, is the fairness guarantee: over any interval, each thread receives its weighted share to within one slice.

/* Weighted fair selection with a red-black tree keyed by vruntime.
   Slice length scales with weight so that a heavier thread runs longer
   per turn; the vruntime delta is then equal for all threads per turn. */
static void charge(struct thread *t, uint64_t delta_ns)
{
    /* scale by reference weight over thread weight */
    t->vruntime += delta_ns * REF_WEIGHT / t->weight;
}

static struct thread *pick_next(struct rbtree *runq)
{
    struct thread *t = rb_first(runq);   /* minimum vruntime */
    if (t) rb_erase(&t->node, runq);
    return t;
}

The rb_first call is O(log n) on a tree of runnable threads, which for realistic queue lengths is a handful of pointer dereferences. The alternative, a sorted list, makes insertion O(n) and is fine for queues of a few threads but degrades on a machine with thousands of runnable tasks. A min-heap has the same asymptotics as the tree with a smaller constant for insertion and a larger one for arbitrary removal, and arbitrary removal matters because a thread that blocks must be taken out of the middle of the structure.

Nice values as weights

The user-visible knob is the nice value, an integer in the range −20 to +19 where higher means less CPU. The mapping from nice to weight is what turns a relative preference into a ratio. The traditional Unix mapping was a simple shift: each nice step changed the share by a fixed factor. Modern implementations use a table whose ratio between adjacent steps is roughly constant, so that the share of nice 0 relative to nice 1 is about the same as nice 10 relative to nice 11. Linux’s table makes each step close to a factor of 1.25, so moving one step changes a share by a quarter while moving ten steps changes it by more than eight times, and the spread between the two ends of the 40-step range runs to several thousand.

That spread is enormous, and it is deliberate. Nice 19 is not “slightly less” than nice 0; it is a background priority that should yield to everything else and consume the machine only when nothing wants it. Nice −20 is the reverse. Systems that use the knob as a mild preference and expect a factor of two or three find the actual ratio surprising, which is why the scheduler’s documentation is worth reading before trusting the numeric distance between two priorities.

The weight enters two places: the virtual clock rate, and the slice length. If only the rate were scaled, a heavy thread would be selected more often but each selection would be a default-length slice, so the number of switches would grow with the weight ratio. Scaling the slice length as well, with longer slices for heavier threads, keeps the number of switches per unit of virtual time roughly constant, at the cost of longer latency for whoever is waiting behind a heavy thread’s slice.

Granularity and the latency target

A scheduler that always runs the minimum-vruntime thread to the end of its slice has a latency problem. If thirty threads are runnable and each takes a 6 millisecond slice, a newly woken thread waits up to 180 milliseconds before its first turn, no matter how small its virtual runtime. That is unacceptable for an interactive process and it is why the slice length is not fixed but derived from a target.

The rule is to choose the slice so that the time to cycle through all runnable threads is approximately a target latency, subject to a minimum slice that keeps switch overhead bounded. With n runnable threads, slice = max(min_slice, target_latency / n). At n = 4 and a target of 6 milliseconds the slice is one and a half milliseconds; at n = 30 the division would give 200 microseconds, but a minimum slice floor of around a millisecond overrides it and the cycle time stretches to thirty milliseconds. The floor exists because below a certain slice length the switch cost dominates: a 1 millisecond slice costing a couple of microseconds to switch spends a small fraction of a percent of the CPU in the switch, while a 50 microsecond slice spends several percent there.

Linux’s formulation of this relation names the two constants sched_latency_ns, the target period, and sched_min_granularity_ns, the floor, and resolves a wakeup decision with a third, sched_wakeup_granularity_ns, which is the virtual-distance margin a waking thread must clear before it is allowed to preempt the current one. The three are tunables exposed under /proc/sys/kernel/, and the third exists because the first two alone would preempt for advantages too small to pay for the switch.

The floor is therefore a hard limit on the latency guarantee. Once the runnable count exceeds target_latency / min_slice, the cycle time grows linearly with n and the target is unachievable by this mechanism alone. Preemption and wakeup placement can shave the worst case, since a waking thread with a much smaller virtual runtime can be allowed to preempt the current one, but the fundamental relationship stands: latency is bounded below by the product of runnable threads and minimum slice.

Where virtual time stops being fair

Three situations break the equivalence between virtual runtime and actual service.

The first is a thread that blocks frequently. Its virtual runtime does not advance while it is blocked, so on wakeup it may be far behind and will be selected immediately. That is usually the desired behaviour, since it is how interactive threads get low latency, but it also means a thread that blocks every microsecond can accumulate an unbounded credit and then, when it stops blocking, monopolise the CPU until its virtual runtime catches up. The credit is the problem: virtual runtime is a position, not a debt, and a thread that has been absent has not earned the right to run for a long stretch.

Implementations bound this by clamping a waking thread’s virtual runtime to no less than the current minimum minus some allowance, typically on the order of one slice’s worth of virtual advance. The thread still gets prompt service, but it cannot cash in an arbitrarily large accumulated lag.

The second is a change of weight. If a thread’s weight is raised, its virtual runtime is not retroactively adjusted, so it starts from wherever it was and the new rate applies going forward. The shares over the interval before the change are not corrected, and a thread that raises its own weight repeatedly can exploit the discontinuity. Systems that expose weight changes to unprivileged processes usually restrict them to a downward direction or require privilege to raise.

The third is migration between CPUs with separate run queues. Each queue’s virtual clock has its own notion of “now”, and a thread moved between them arrives with a virtual runtime that is not comparable to its new neighbours’. The fix is to normalise on migration: adjust the thread’s virtual runtime by the difference between the source and destination queues’ reference clocks. Without that adjustment, a thread migrating from a lightly loaded CPU, whose virtual clock has advanced slowly, arrives looking far ahead of its new peers and is starved until they catch up. This is the fairness cost of per-CPU queues, and it is the reason the balancing logic in Load Balancing and Thread Migration on Symmetric Multiprocessors must be aware of the accounting, not just the counts.

Fairness between groups, not threads

Weighted fair queuing as described equalises service between individual threads. Real systems need fairness between users or containers, each of which contains many threads, so that one user running fifty processes does not get fifty times the CPU of a user running one. Applying weights per thread cannot express that: the fifty-process user’s threads each get a fair share, and the aggregate is fifty shares.

The solution is to apply the same mechanism hierarchically, with each level of the hierarchy having its own virtual clock. A group’s virtual runtime advances at a rate set by the group’s weight and by the sum of the weights of the groups competing at that level; a thread’s position is determined within its group. Selection walks from the root down, picking the minimum-vruntime group, then the minimum-vruntime thread within it. The guarantee then holds at every level, which is a strictly stronger property and a strictly more expensive one to maintain. The structure and its costs are the subject of Hierarchical Fair Share and Lag Accounting.

The last thing to note about the single-level version is that it provides no latency guarantee at all. A thread with a tiny weight on a machine full of heavy threads receives a tiny share and waits a long time between turns; virtual runtime bounds the error in the share, not the magnitude of the wait. Converting a share into a deadline requires a different mechanism, one that reasons about when service must be delivered rather than how much, the concern of deadline-based scheduling and the servers that implement it.