Hierarchical Fair Share and Lag Accounting

Weighted fair queuing equalises service between threads. That is the wrong unit when threads belong to groups with a shared budget. A container running fifty worker threads and a container running one should, in most deployment models, receive comparable shares of the CPU rather than shares in the ratio 50:1. Per-thread weighting cannot express that preference, because the container’s aggregate is the sum of its threads’ shares and nothing in the per-thread accounting knows the threads belong together.

Hierarchical scheduling solves this by applying the same proportional-share mechanism at each level of a tree. Threads compete within their group; groups compete with each other; and the share a thread receives is the product of the shares along its path from the root. The mechanism is a straightforward generalisation of the single-level algorithm. Its guarantees are subtler than they look, and the cost of maintaining the tree is where implementations differ most.

The tree and the two clocks

Each node in the hierarchy, whether a group or a leaf thread, has a weight and a virtual clock. The rule is the same at every level: among the runnable children of a node, run the child with the smallest virtual runtime. The child’s virtual runtime advances while it is selected, at a rate scaled by the ratio of the reference weight to the child’s own weight, and also by the number of children competing.

The second scaling factor is what makes the hierarchy work, and it is the part that a naive implementation omits. A group’s virtual clock must advance at a rate that reflects not only its own weight but how much service it is actually receiving, which is the service of its currently running descendant. If a group has ten runnable threads and its child’s virtual clock advances at the unmodified rate, the group appears to receive ten times the virtual time for the same wall time, and it is penalised ten times over. The correct formulation normalises by the group’s own weight relative to the siblings at its level, and by the sum of weights of the active children beneath it.

The consequence is that virtual runtime is not comparable across different parts of the tree. A thread deep in one subtree and a thread deep in another have virtual runtimes measured in different units, and subtracting them is meaningless: node clocks are only comparable with those of their own siblings, since each one is scaled by the weight of its own node and by the activity beneath it. This is the property that makes the algorithm implementable, since each selection decision reduces to a local comparison at one node, and it is also the property that makes debugging a misconfigured hierarchy hard, because the numbers that appear in diagnostics are not on a common scale.

/* Selection walks down the tree, one comparison per level. Each node's
   key is its own virtual runtime; children are compared only with siblings. */
struct node *pick(struct node *root)
{
    struct node *n = root;
    while (!n->is_leaf) {
        n = min_vruntime_child(n);      /* local comparison only */
        if (!n) return NULL;            /* no runnable descendant */
    }
    return n;
}

/* Charge is applied on the way up: a leaf's service advances its own
   clock, and each ancestor's clock advances by the leaf's service scaled
   by the ancestor's weight and by the active children beneath it, so a
   group with ten runnable children does not appear to receive ten times
   the service of a group with one. The normalisation is shown as a call
   rather than an inline formula because the exact divisor is a property
   of the chosen weighting scheme. */
static void charge_path(struct node *leaf, uint64_t delta_ns)
{
    leaf->vruntime += delta_ns * REF_W / leaf->weight;
    for (struct node *g = leaf->parent; g; g = g->parent)
        g->vruntime += charge_parent(g, delta_ns);
}

The walk is O(depth) and the depth is bounded by configuration, at a handful of levels in any sane deployment. The charge_path loop is the expensive part: it touches one node per level on every accounting update, and if accounting happens on every tick or every switch, that is a fixed multiplier on the scheduler’s per-switch cost. Implementations reduce it by charging only the leaf on the hot path and recomputing ancestor clocks when the selection changes, trading accuracy for cost.

What lag actually bounds

Lag is the difference between the service a node should have received under an ideal fluid scheduler and the service it has received. Formally, for a node with weight w, sharing a processor with a set of total weight W, over an interval of length t, the ideal service is t · w / W; the actual service is the sum of the intervals during which the node ran. Lag is the difference, positive when the node is behind.

The single-level algorithm bounds lag by roughly one slice: the minimum-vruntime rule ensures that a node cannot fall more than about a slice’s worth of virtual time behind its siblings. The hierarchical version bounds lag at each level separately, and the bound along a path is the sum of the per-level bounds rather than their product, because each level’s bound is a quantity of time at that level. A thread that can be one slice behind within its group, inside a group that can be one slice behind at the root, is up to two slices behind in absolute terms, and a deeper tree adds one term per level.

This is a weaker guarantee than it appears at first. The error bound is expressed in slices, and the slice length is itself a function of the number of runnable threads, as described in Virtual Runtime and Weighted Fair Queuing. A group whose slice is short has a bound measured in short slices; a thread inside it that is many slices behind is still behind by a small amount of time. The bound is also an error bound on the share, not a bound on latency: a group with a small weight receives its correct small share, and its threads still wait a long time between turns.

Lag accounting has a second use beyond analysis. Because lag is signed, a node that has been starved has positive lag, and the scheduler can use the magnitude to decide when a group deserves a turn even if another group has a smaller virtual runtime. Some implementations expose the accumulated lag directly and let a group accumulate credit while it has no runnable threads, so that it can catch up later. That is a deliberate departure from strict proportional share, and it is the hierarchical analogue of the waking-thread credit problem: unbounded accumulation allows a group to monopolise the CPU after a long absence.

Group weights and the meaning of a share

Configuring a hierarchy requires deciding what a weight means, and there are two incompatible readings.

Under a relative reading, weights are normalised among the active siblings. If group A has weight 100 and group B has weight 100, they split the CPU evenly. If group B becomes idle, group A gets everything. Adding a group C with weight 100 changes A’s share from 100 percent to 50 percent, even though nothing about A changed. This is the model that most hierarchical schedulers implement, and it is the model that makes weights easy to reason about locally.

Under an absolute reading, a weight names a fraction of the CPU that the group is entitled to whether or not other groups are active. A group with an absolute share of 30 percent gets 30 percent when the machine is otherwise idle, and the remaining 70 percent is available to others. This model requires the shares to sum to no more than 100 and requires admission control when a new group is created, which is a strictly stronger contract and one that general-purpose kernels generally do not offer.

The difference matters for capacity planning. A deployment that assigns each tenant a relative weight and expects a fixed fraction will be surprised when the number of active tenants changes. The fraction is a function of the whole active set, and the only way to obtain a fixed fraction is a mechanism that reserves capacity, such as a quota or a reservation, rather than one that divides proportionally.

/* A relative-share tree can be reconfigured by changing one weight; the
   effect propagates to every sibling's effective share. Printing the
   effective share requires the sum of active sibling weights, which
   changes as groups go idle. */
static double effective_share(struct node *n)
{
    double s = 1.0;
    for (; n->parent; n = n->parent) {
        uint64_t total = sum_active_weights(n->parent);
        if (total == 0) return 0.0;
        s *= (double)n->weight / (double)total;
    }
    return s;
}

sum_active_weights is the operation that makes the result dynamic: a group’s effective share is not a property of the group but of the tree’s current state, and it can change without any configuration change. Any tooling that reports “this group gets 40 percent” must recompute rather than cache.

Enforcement points and the cost of the tree

The hierarchy must be consulted at every scheduling decision, and the decision points are not uniformly cheap.

The selection path is O(depth) per switch, which is acceptable. The harder cost is that a change in one part of the tree can invalidate the selection elsewhere. When a group goes from having no runnable threads to having one, its ancestors become runnable and must be inserted into their parents’ selection structures; when the last thread in a group blocks, the group must be removed. Each insertion and removal is a tree operation at every level, so the cost of a thread waking is proportional to the depth of its group, not constant. On a machine with thousands of threads waking frequently, this shows up as scheduler overhead that scales with hierarchy depth.

The second cost is that the per-CPU run queues and the hierarchy interact awkwardly. A group’s threads may be spread across CPUs, and the group’s virtual clock is a single value that all of them advance. Two CPUs running two threads of the same group both charge the group’s clock, so the clock advances at twice the rate it would on one CPU, which is correct if the group is receiving twice the service, but the group’s share is defined against a single CPU’s capacity in the single-level analysis. On m CPUs, a group’s entitlement is m times a single CPU’s, and the accounting must be scaled accordingly or every group will appear to be far ahead of schedule.

This is the point where hierarchy meets the balancing problem, and the interaction is the least well-specified part of the design. Moving a thread between CPUs changes the service rate of two groups at once, and the normalisation that makes virtual runtimes comparable across queues must be applied to the group clocks as well as the thread clocks. The machinery that does this is the same machinery described in Load Balancing and Thread Migration on Symmetric Multiprocessors, extended to a second dimension.

Where hierarchy stops helping

A hierarchy divides a resource that is already being shared. It cannot create capacity, and it cannot prevent a group from being starved by a mechanism outside the tree.

The first limit is that the leaf weight is only meaningful if the leaf is runnable. A group with a large weight but no runnable threads contributes nothing and, under the relative model, its weight disappears from the denominator, which inflates every other group’s share. A workload that alternates between activity and idleness therefore has a share that varies with its own activity pattern, a feedback loop that is stable but unintuitive.

The second is that the hierarchy does not bound latency. It bounds share error. A group receiving its exact entitlement can still have a thread that waits many slices for its turn, because within the group the same proportional mechanism applies and proportional share has no latency guarantee. The mechanisms that do provide latency bounds operate on a different axis, namely deadlines and budgets, and they compose with a hierarchy only through a server node that reserves capacity rather than a weight that divides it, as described in Deadline Servers and Admission Control.

The third is that the tree is a policy structure, and policy structures are only as good as their configuration. A hierarchy with a default weight at every node behaves exactly like no hierarchy at all, because equal weights at every level divide equally and the tree’s only effect is added cost. The structure earns its complexity when the weights encode a real preference, and the hard part of operating one is deciding what those preferences should be, a question the scheduler cannot answer.

This is also why the two controls a group usually gets are not interchangeable. A weight is a divider: it acts only while a sibling is runnable, it needs no total to be conserved, and its effect changes whenever the sibling set changes. A quota or bandwidth limit is a ceiling: it caps what a group may consume, holds when the machine is idle, and needs no cooperation from neighbours. Neither one produces a floor, so a deployment that needs “at least this much” and writes it as a large weight will find the guarantee evaporating as soon as the machine fills up. A floor requires a reservation, which is a different node type: it holds capacity away from the proportional pool and hands it to one group on a schedule of its own. Mixing the three in one tree is possible, and it is the point at which the arithmetic of the denominators stops being something an operator can compute by hand.