vault

CFS and EEVDF Group Scheduling

16 min read

CFS and EEVDF Group Scheduling

Once the scheduler nests run queues so a group competes as one entity (the topology described in Hierarchical Group Scheduling and Task Groups), a hard question remains: what weight should each group’s stand-in entity carry, on each CPU? A group’s configured weight, tg->shares, is a single global number — say “this cgroup gets twice the CPU of its sibling.” But the group is represented by a separate entity on every CPU, and the group’s tasks are spread unevenly across those CPUs. If the kernel naively gave every per-CPU group entity the full tg->shares, a group with tasks on eight CPUs would claim eight times its fair share. The fair scheduler therefore continuously redistributes the global tg->shares among the group’s per-CPU entities in proportion to where the group’s load actually is. The function that does this is calc_group_shares, called through update_cfs_group, and it is invoked on essentially every enqueue, dequeue, and tick. This note explains that weight math, the per-CPU load tracking it rests on (tg->load_avg), how virtual runtime and EEVDF eligibility behave across the nesting, and — carefully — what actually changed when the fair scheduler moved from CFS to EEVDF (default since 6.6). (Line references are Linux 6.12 LTS; calc_group_shares is byte-identical in 6.18 LTS, verified 2026-06-03.)

The companion note Hierarchical Group Scheduling and Task Groups owns the topology — struct task_group, se->my_q, the bottom-up enqueue and top-down pick walks. This note picks up exactly where that one stops: the weight recomputation that happens during those walks.

Mental Model

The configured weight tg->shares is a property of the whole group. But scheduling decisions happen per-CPU, on per-CPU run queues, against per-CPU group entities. So the kernel must answer, for each CPU: “of this group’s total weight, how much should the entity on this CPU claim?” The answer is “the fraction proportional to how much of the group’s load is on this CPU.” If a group has weight 1024 and all its work is on CPU 3, then CPU 3’s group entity should carry ~1024 and the others ~0 (clamped to a tiny floor). If the work is split evenly across two CPUs, each entity carries ~512.

flowchart TD
  SHARES["tg->shares = 1024<br/>(one global configured weight)"]
  LOAD["tg->load_avg<br/>(sum of per-CPU load_avg)"]
  SHARES --> CALC{"calc_group_shares() on CPU i:<br/>ge.weight ~= tg.shares * grq_load / tg_load"}
  LOAD --> CALC
  CALC --> GE0["se on CPU 0<br/>weight = 600 (most load here)"]
  CALC --> GE1["se on CPU 1<br/>weight = 400"]
  CALC --> GE2["se on CPU 2<br/>weight = MIN_SHARES (idle here)"]

How one global weight becomes many per-CPU weights. What it shows: the single configured tg->shares is divided among the group’s per-CPU entities in proportion to each CPU’s share of the group’s total tracked load (tg->load_avg). A CPU where the group is busy gets a large slice; a CPU where the group is idle gets the MIN_SHARES floor. The insight to take: the per-CPU entity weights are not configured — they are derived continuously from load, so they drift as tasks migrate and wake, which is why update_cfs_group runs on every enqueue/dequeue/tick. The sum of derived weights approximates (slightly over-estimates) tg->shares.

The Core Computation: calc_group_shares

The ideal, from the long comment block at fair.c:3942–4013 (6.12), is equation (1):

                    tg->shares * grq->load.weight
  ge->load.weight = -----------------------------
                      Sum over CPUs of grq->load.weight

where grq is the group’s run queue on this CPU and ge is the group entity on this CPU. In words: the per-CPU entity’s weight is the group’s configured weight scaled by this CPU’s fraction of the group’s total run-queue weight. The denominator — summing grq->load.weight across all CPUs on every recomputation — is “prohibitively expensive” (the comment’s words), so the kernel substitutes a slow-moving per-CPU load average for the instantaneous weight, giving equation (3):

                    tg->shares * grq->avg.load_avg
  ge->load.weight = ------------------------------
                          tg->load_avg

where tg->load_avg is the cheaply-maintained sum of every CPU’s grq->avg.load_avg (more on how it stays summed below). This is stable but has a transient: when a previously-idle group starts one task, that CPU’s avg.load_avg takes time to build up, so the entity is briefly under-weighted, hurting latency. The kernel patches the formula to approach the correct single-CPU answer (tg->weight) in that boundary case, arriving at equation (6) — and that is exactly what the code computes (fair.c:4015–4047):

static long calc_group_shares(struct cfs_rq *cfs_rq)
{
	long tg_weight, tg_shares, load, shares;
	struct task_group *tg = cfs_rq->tg;
 
	tg_shares = READ_ONCE(tg->shares);
	/* this CPU's load: at least the instantaneous weight, at least the avg */
	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
 
	tg_weight = atomic_long_read(&tg->load_avg);
	/* swap this CPU's stale contribution for its fresh 'load' */
	tg_weight -= cfs_rq->tg_load_avg_contrib;
	tg_weight += load;
 
	shares = (tg_shares * load);
	if (tg_weight)
		shares /= tg_weight;
 
	return clamp_t(long, shares, MIN_SHARES, tg_shares);
}

Walk it symbol by symbol. tg_shares is the configured group weight (the cpu.weight-derived number). load is this CPU’s contribution to the group, taken as the max of the instantaneous run-queue weight (scale_load_down(cfs_rq->load.weight)) and the tracked average (cfs_rq->avg.load_avg) — the max biases toward responsiveness when a task has just been added but the average has not caught up. tg_weight starts as the global sum tg->load_avg, then has this CPU’s last-published contribution (tg_load_avg_contrib) subtracted and the fresh load added — this de-stales the denominator without re-summing all CPUs. Then shares = tg_shares * load / tg_weight is exactly equation (6). Finally clamp_t(..., MIN_SHARES, tg_shares):

  • Lower bound MIN_SHARES (1UL << 1, i.e. 2, from sched.h:503): a group entity on a CPU where the group is idle still gets a tiny non-zero weight, never 0 — which keeps the entity schedulable and avoids divide-by-zero downstream. The comment notes the floor is unscaled so that a small-shares group partitioned across many CPUs gets a sensible sub-MIN_SHARES-scaled slice rather than over-claiming.
  • Upper bound tg_shares: no single CPU’s entity may claim more than the whole group’s configured weight. As the comment admits, the approximation “consistently overestimates,” so the sum of per-CPU entity weights is >= tg->shares — the clamp keeps any one of them bounded.

Uncertain

Verify: the precise rounding/overestimation behavior — specifically that Sum(ge->load.weight) >= tg->shares holds in all cases. Reason: this is asserted in the in-tree comment (“hence icky!”) but I have not seen a formal proof or test; it is a self-described approximation. Treat the direction (overestimate) as documented, the exact magnitude as workload-dependent. To resolve: the comment block at fair.c:3942–4013 is the authority; a tighter bound would need the PELT analysis in the load-tracking docs. uncertain

update_cfs_group: applying the recomputed weight

calc_group_shares only computes a number; update_cfs_group applies it (fair.c:4054–4072, 6.12):

static void update_cfs_group(struct sched_entity *se)
{
	struct cfs_rq *gcfs_rq = group_cfs_rq(se);   /* se->my_q, the child rq */
	long shares;
 
	if (!gcfs_rq)            /* se is a task, not a group -> nothing to do */
		return;
	if (throttled_hierarchy(gcfs_rq))            /* throttled -> leave it */
		return;
#ifndef CONFIG_SMP
	shares = READ_ONCE(gcfs_rq->tg->shares);     /* UP: no redistribution */
#else
	shares = calc_group_shares(gcfs_rq);         /* SMP: the formula above */
#endif
	if (unlikely(se->load.weight != shares))
		reweight_entity(cfs_rq_of(se), se, shares);
}

Two things to note. First, the UP vs SMP split: on a uniprocessor there is only one CPU, so there is nothing to redistribute — the entity simply gets the full tg->shares. The whole calc_group_shares machinery exists only because SMP spreads a group across CPUs. Second, update_cfs_group returns early for a task entity (!gcfs_rq) — only group entities get reweighted, because only they stand in for an aggregate whose composition changes.

update_cfs_group is called at every level of the hierarchy during the second loop of enqueue_task_fair (fair.c:7024) and dequeue_entities (fair.c:7148), on every tick via entity_tick → update_cfs_group (fair.c:5673), and whenever the configured weight changes via __sched_group_set_shares (fair.c:13452). So as tasks migrate, wake, and sleep, every affected group entity’s weight is continuously nudged toward the load-proportional ideal.

The Load Sum: tg->load_avg and tg_load_avg_contrib

calc_group_shares’s denominator is atomic_long_read(&tg->load_avg) — a single global running sum of every CPU’s contribution. Keeping that sum current cheaply is the job of update_tg_load_avg (fair.c:4187, 6.12):

static inline void update_tg_load_avg(struct cfs_rq *cfs_rq)
{
	long delta;
	u64 now;
	if (cfs_rq->tg == &root_task_group)   /* root's load_avg is unused */
		return;
	if (!cpu_active(cpu_of(rq_of(cfs_rq))))
		return;
	now = sched_clock_cpu(cpu_of(rq_of(cfs_rq)));
	if (now - cfs_rq->last_update_tg_load_avg < NSEC_PER_MSEC)
		return;                       /* rate-limit: at most once per ms */
	delta = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;
	if (abs(delta) > cfs_rq->tg_load_avg_contrib / 64) {
		atomic_long_add(delta, &cfs_rq->tg->load_avg);   /* publish delta */
		cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
		cfs_rq->last_update_tg_load_avg = now;
	}
}

The pattern is a classic published-contribution scheme. Each CPU’s cfs_rq remembers the last value it added to the global sum in tg_load_avg_contrib. When its local avg.load_avg drifts far enough (more than 1/64th) from what it last published, and at least a millisecond has passed, it atomically adds the delta to tg->load_avg and records the new contribution. This keeps tg->load_avg ≈ Sum(per-CPU avg.load_avg) without any CPU ever reading another CPU’s state. The double guard — 1ms rate limit and 1/64th hysteresis — exists because, as the comment says, “for migration heavy workloads, access to tg->load_avg can be unbound”: every task migration would otherwise bounce this atomic across cores. This is the cache-line hotspot called out in Hierarchical Group Scheduling and Task Groups, and why tg->load_avg is ____cacheline_aligned.

The PELT (Per-Entity Load Tracking) signals themselves — how avg.load_avg is the geometrically-decayed average of an entity’s runnable+running history — are propagated up the hierarchy by update_load_avg(cfs_rq, se, UPDATE_TG) during the same enqueue/dequeue walks, and the load of a child group is folded into its parent entity’s load via update_tg_cfs_load. The full PELT decay math is a topic of its own; here the relevant fact is that avg.load_avg is a smoothed load, which is what gives calc_group_shares its stability (and its boundary-condition transients).

Virtual Runtime, Eligibility, and Lag Across the Nesting

Inside any one run queue — root or a group’s child run queue — the picking rule is the ordinary fair-scheduler rule applied to whatever entities sit there, tasks and group-entities alike. Under EEVDF (see The EEVDF Scheduler and Eligibility Lag and Virtual Deadlines in EEVDF) each entity carries a virtual runtime vruntime, a per-run-queue weighted-average virtual time V (avg_vruntime), a lag vlag = V - v_i (how far ahead or behind its fair share the entity is), and a virtual deadline derived from its requested slice and weight. The per-level pick is: among eligible entities (those with non-negative lag, entity_eligible), choose the one with the earliest virtual deadline. update_curr charges the running entity’s vruntime by calc_delta_fair(delta_exec, curr) — wall-clock time scaled inversely by the entity’s weight (fair.c:1230, 289) — so a heavier entity’s virtual clock advances more slowly and it is picked more often.

The subtle point for group scheduling: a group entity’s vruntime advances according to the group entity’s weight — the load-derived per-CPU weight that update_cfs_group just computed — not the sum of its members’ weights and not its configured tg->shares. When a member task runs, the time is charged at the member’s level inside the child run queue (advancing the member’s vruntime relative to the child run queue’s V), and separately the group entity’s vruntime advances at the parent level relative to the parent’s V. The two levels each run their own independent EEVDF accounting; they are coupled only through (a) which entity is picked descends level by level, and (b) the load propagation that feeds calc_group_shares. This is why fairness composes: a group gets its weight-proportional slice at its level, and within that slice its members get their weight-proportional sub-slices.

What Actually Changed: CFS → EEVDF

This is the most misunderstood part, so be precise. The share-distribution machinery is essentially unchanged from the pre-EEVDF CFS era. calc_group_shares, update_cfs_group, the tg->load_avg/tg_load_avg_contrib propagation, and the equation-(6) derivation in the comment block all predate EEVDF and survive verbatim into 6.12 and 6.18 — the per-CPU weight redistribution problem is identical whether the per-level pick is CFS’s leftmost-vruntime or EEVDF’s earliest-eligible-deadline. The PELT load tracking that feeds them is likewise shared.

What EEVDF changed is the per-level selection rule and the handling of weight changes:

  1. The pick at each level. CFS picked the leftmost entity in the run queue’s red-black tree (smallest vruntime). EEVDF picks the earliest-deadline among eligible entities, where eligibility means non-negative lag (V - v_i >= 0). This applies at every level of the group hierarchy uniformly — a group entity is selected by the same eligibility+deadline test as a task. (Per the EEVDF design doc and Corbet’s LWN write-up.)

  2. Reweighting now preserves lag. This is the concrete code-level change that touches group scheduling most, because update_cfs_group reweights group entities constantly. Under CFS, changing an entity’s weight required renormalizing its vruntime. Under EEVDF, reweight_entity (fair.c:3874) routes through reweight_eevdf (fair.c:~3770, with the proof at 3790–3872), which adjusts both vruntime and the virtual deadline to keep the entity’s lag invariant across the weight change. The on-queue path rescales at the zero-lag-preserving point:

    /* in reweight_eevdf, for an on-rq entity (fair.c:3851) */
if (avruntime != se->vruntime) {
    vlag = entity_lag(avruntime, se);
    vlag = div_s64(vlag * old_weight, weight);   /* lag_i = w_i*(V - v_i) */
    se->vruntime = avruntime - vlag;
}
/* and the deadline, since the virtual-time slope changed (3869): */
vslice = (s64)(se->deadline - avruntime);
vslice = div_s64(vslice * old_weight, weight);
se->deadline = avruntime + vslice;

    And for an off-queue entity, reweight_entity rescales the stored lag directly (fair.c:3897): se->vlag = div_s64(se->vlag * se->load.weight, weight) — because the kernel stores se->vlag = V - v_i while the true lag is w_i*(V - v_i), so when w_i changes the stored value must be scaled to keep the real lag constant. The comment at 3894–3896 says exactly this. The proof block (corollaries #1 and #2) establishes that reweighting does not perturb the run queue’s weighted-average vruntime V. This lag-preserving reweight is the EEVDF-specific behavior that the constant update_cfs_group churn relies on — without it, every load-driven reweight of a group entity would jolt its fair position.

    The lag-preserving reweight is genuinely an EEVDF-era behavior: lag itself is an EEVDF concept (CFS had no per-entity lag), so reweighting “at the !0-lag point” to keep lag invariant only exists because EEVDF tracks lag. The named helper reweight_eevdf (fair.c:3768 in 6.12) is a later refactor extracted from reweight_entity — the fair.c history on git.kernel.org shows it being touched by a cluster of sched/eevdf: fixes dated 2024-04-22 (e.g. “Prevent vlag from going out of bounds in reweight_eevdf()”), confirming the helper and its vlag-bounds handling are EEVDF-specific. The underlying lag/vruntime adjustment in reweight_entity arrived with the EEVDF merge in 6.6 (Peter Zijlstra’s series).

  3. Field renames, same structure (6.18). Between 6.12 and 6.18 the hierarchical counter h_nr_running was renamed h_nr_queued (reflecting EEVDF’s “delayed dequeue,” where a task can be off the pick-tree but still accounted), but the group enqueue/dequeue structure and calc_group_shares are unchanged. Treat 6.12 and 6.18 group scheduling as the same mechanism.

The Userspace End: cpu.weight ↔ shares

The number you write into a cgroup’s cpu.weight is mapped to tg->shares by a fixed round-trip (sched.h:263–273): sched_weight_from_cgroup(w) = DIV_ROUND_CLOSEST(w * 1024 / CGROUP_WEIGHT_DFL) with the cgroup range being MIN/DFL/MAX = 1/100/10000. So cpu.weight = 100 (the default) maps to shares = 1024 = NICE_0_LOAD, and the conversion is lossless over the range. cpu_weight_write_u64 (core.c:9797) takes the cpu.weight value, converts it, and calls sched_group_set_shares. There is also a cpu.weight.nice interface mapping nice values [-20,19] through sched_prio_to_weight[]. The cgroup v2 cpu controller interface itself — including cpu.max bandwidth — is documented in The cgroup v2 CPU Controller; this note only covers the weight path into the fair scheduler.

Failure Modes and Subtleties

  • Load-average lag on bursty groups. Because calc_group_shares uses smoothed PELT load and tg->load_avg updates at most once per millisecond per CPU, a group that suddenly becomes busy on a fresh CPU is briefly under-weighted — its entity’s load has not propagated yet. The max(load.weight, avg.load_avg) in calc_group_shares and the equation-(6) UP-correction both exist to soften this, but a latency-sensitive task in a freshly-woken deep group can still see a short fairness dip.
  • Overestimation by design. The sum of per-CPU entity weights exceeds tg->shares. This is intentional and bounded by the per-entity clamp, but it means a heavily-spread group can momentarily out-claim its nominal share against siblings concentrated on fewer CPUs.
  • MIN_SHARES granularity floor. The clamp’s lower bound is unscaled precisely so a group with a small configured shares partitioned across many CPUs can have its per-CPU entity weight legitimately drop below scale_load(MIN_SHARES) (the in-tree example: 15*1024/8 = 1920 rather than the 2*1024 a scaled floor would impose), while still guaranteeing a non-zero MIN_SHARES = 2 when a CPU has no runnable task in the group. The floor trades exactness for never-zero schedulability without coarsening fine partitioning.
  • Throttled groups are skipped. update_cfs_group bails on a throttled hierarchy, so a cpu.max-throttled group’s weights freeze until it is unthrottled (see CPU Bandwidth Control cpu.max and Throttling).

Alternatives and When to Choose Them

  • Flat CFS/EEVDF (CONFIG_FAIR_GROUP_SCHED=n). No per-CPU weight redistribution at all — every task carries its own weight directly. Simpler and slightly cheaper, but no hierarchical proportional control.
  • SCHED_DEADLINE (The Constant Bandwidth Server and Admission Control). When you want guaranteed CPU bandwidth with admission control instead of best-effort weighted shares, the deadline class’s CBS replaces this weight math entirely.
  • sched_ext (sched_ext and BPF-Defined Schedulers). When the load-proportional share model is wrong for your workload and you want to compute group weights yourself in BPF.

Production Notes

This machinery is what makes a Kubernetes node’s CPU-share isolation actually work: pod and container cpu.weight values become tg->shares, and calc_group_shares is what ensures a container spread across cores still gets only its weighted share rather than a per-core multiple. The tg->load_avg atomic was a measured scalability bottleneck on large NUMA machines with migration-heavy workloads — the 1ms/64th rate-limiting and cache-line alignment in update_tg_load_avg are direct responses to that, and the topic recurs in scheduler scalability discussions. The CFS-era foundations of this code — the equation-(6) share derivation and the tg->load_avg propagation — predate EEVDF and are preserved verbatim in 6.12/6.18 (the in-tree comment block at fair.c:3942–4013 is the authority). The EEVDF transition that layered the lag-preserving reweight on top is covered in Corbet’s EEVDF article.

See Also

Graph View

Backlinks