Fair scheduling and EEVDF

Before you start#

Read scheduler core and tasks, fork, exit, and wait. This chapter describes the upstream v6.12 fair scheduling implementation, not a promise about your host's kernel or an enabled sched_ext scheduler. The arithmetic exercise is source-only. The optional host command increases the niceness of one short-lived child; it does not change the shell's priority or any host scheduler setting.

Learning goals#

Explain weighted virtual runtime, lag, eligibility and virtual deadlines; follow the v6.12 EEVDF pick and deadline update; interpret delayed dequeue and group hierarchy as conditional behavior; and use a small arithmetic model without predicting exact wall-clock scheduling on a real host.

Fairness is an accounting problem#

The fair scheduler attempts to distribute CPU service among competing scheduling entities according to weights, while considering latency and eligibility. A task's nice value influences its weight: a lower nice value normally means a larger share when otherwise comparable tasks compete. A weight is not an absolute priority like a real-time priority, and a share is not a reservation of a fixed number of milliseconds. An isolated task can use an available CPU regardless of the ratio it would receive under competition. CPU affinity, cgroups, other scheduling classes, capacity, configuration and whether the task is runnable all change the result.

A sched_entity represents a task or, in fair group scheduling, a group entity within a hierarchy. A cfs_rq holds fair-class state for a CPU or group context; despite the historical name, v6.12 fair selection uses EEVDF-related logic rather than the old explanation “always pick the leftmost virtual-runtime node.” The per-CPU runqueue lock and scheduler context protect the relevant structures. A task can sleep, migrate or be reweighted, and those transitions must preserve accounting invariants. An entity pointer taken from the tree cannot be retained arbitrarily after a dequeue or task exit.

Virtual runtime, vruntime, expresses received service in a weighted coordinate. In a simplified model, a physical execution interval Δt advances an entity's virtual runtime by approximately Δt × 1024 / weight. A nice-0 weight of 1024 therefore advances approximately one virtual unit per real unit; a smaller weight advances faster for the same service. Actual code uses integer arithmetic, scaling and architecture-dependent timing. Virtual runtime is not a wall-clock timestamp and cannot be compared meaningfully across unrelated runqueues without the relevant normalization and migration rules.

Source walkthrough#

In v6.12 kernel/sched/fair.c, update_curr includes this excerpt (SPDX GPL-2.0; checks and subsequent accounting omitted):

curr->vruntime += calc_delta_fair(delta_exec, curr);
resched = update_deadline(cfs_rq, curr);

delta_exec is the measured execution interval after the function has verified that there is a current entity and a positive interval. calc_delta_fair converts that service using the entity's weight; the first line advances its virtual runtime. The second updates its deadline when the current request has been consumed and can signal that rescheduling is appropriate. Other lines update runqueue state, task statistics, fair bandwidth accounting and related data. The excerpt does not say that a task is preempted at an exact wall-clock instant.

A virtual lag compares the service an entity has received with the service it would have received under an ideal weighted distribution. The source comments express it as lag_i = w_i × (V - v_i), where V is an aggregate virtual time and v_i the entity's virtual runtime. Nonnegative lag corresponds to eligibility in the simplified model: the entity has not received more than its weighted share at that point. entity_eligible and vruntime_eligible implement the test with scaled integer values and avoid a misleading rounding step in a simple divided average. Lag is not a queue length, a deadline miss or an application response-time measurement.

The same file's update_deadline contains this excerpt (SPDX GPL-2.0; slice-selection branch omitted):

se->deadline = se->vruntime + calc_delta_fair(se->slice, se);

The virtual deadline is computed from the current virtual runtime plus a weight-adjusted requested slice. It is a scheduler accounting coordinate, not a real-time SCHED_DEADLINE absolute deadline. The preceding code returns without creating a new request if the current virtual runtime has not reached its existing deadline. A task's slice can be a configured default or a custom value under supported interfaces and conditions. Weight affects virtual advancement and the deadline interval; it does not guarantee that this task will run for the full slice without interruption.

The tree is ordered by deadline#

pick_eevdf searches the fair runqueue's red-black tree. The source comment describes a tree ordered by virtual deadline with augmentation containing the minimum virtual runtime in a subtree. That augmentation allows the search to skip a subtree that cannot contain an eligible entity. If the leftmost deadline entity is eligible it can be a candidate; otherwise the search looks for the earliest eligible one using subtree information. The currently running entity is handled separately and can compete with the tree candidate. A single-entity fast path and scheduler features such as RUN_TO_PARITY and NEXT_BUDDY introduce additional branches. The basic EEVDF rule is therefore a teaching model of the actual decision, not a substitute for all branches of pick_eevdf and its caller.

In v6.12 kernel/sched/fair.c, SPDX GPL-2.0, vruntime_eligible is the whole function (no lines omitted):

static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
	struct sched_entity *curr = cfs_rq->curr;
	s64 avg = cfs_rq->avg_vruntime;
	long load = cfs_rq->avg_load;

	if (curr && curr->on_rq) {
		unsigned long weight = scale_load_down(curr->load.weight);

		avg += entity_key(cfs_rq, curr) * weight;
		load += weight;
	}

	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
}

The test is a cross-multiplication, avg >= (vruntime - min_vruntime) × load, so it stays in integers and does not divide the weighted sum. The running entity joins the average only while it is on the runqueue, which is why eligibility can depend on which entity is current. The excerpt does not show how avg_vruntime and avg_load are updated on enqueue and dequeue, so it does not establish the complete lag bookkeeping.

This is why a diagram of the old CFS model with a tree sorted only by vruntime and an unconditional leftmost pick is wrong for this version. The augmented value is not itself the sort key. Nor should “earliest deadline” be stated without eligibility: an entity with an earlier virtual deadline can be ineligible because it has already received more than its proportional service. The v6.12 EEVDF documentation describes the high-level rule; the source controls the precise implementation.

In pick_eevdf in the same file, the leftmost fast path reads (SPDX GPL-2.0; the single-entity, RUN_TO_PARITY and current-entity branches that come earlier are not part of this block):

	/* Pick the leftmost entity if it's eligible */
	if (se && entity_eligible(cfs_rq, se)) {
		best = se;
		goto found;
	}

If the leftmost deadline entity is eligible, it is chosen without a tree search. An ineligible leftmost entity sends the code to the heap search, which this excerpt does not show, and the final comparison with curr happens after the found label, also outside the block.

A numerical pick, with explicit assumptions#

Consider a deliberately simplified single cfs_rq with two runnable task entities, no current entity outside the tree, no buddy or run-to-parity shortcut, no throttling and no other tasks. Treat virtual times as real numbers for teaching; the kernel uses scaled integer arithmetic. Let A have nice 0 and weight 1024, virtual runtime 8.000, and requested slice 2 ms. Let B have nice 5 and weight 335, virtual runtime 4.000, and the same requested slice. These are recognizable entries from the nice-weight table, but the values and initial state here are invented for the example.

The weighted aggregate virtual time is approximately (1024 × 8 + 335 × 4) / (1024 + 335) = 7.014. A has negative lag because its vruntime 8.000 is above that average; B is eligible because 4.000 is below it. Using the simplified normalized formula, A's deadline is 8 + 2 × 1024 / 1024 = 10.000; B's is about 4 + 2 × 1024 / 335 = 10.113. A has the earlier virtual deadline, but it is ineligible. Under the stated simple conditions, the pick is B, the earliest eligible candidate. This demonstrates why ordering by deadline alone is insufficient.

If B runs for one millisecond with the same simplified weight and no changing population, its virtual runtime advances by about 1 × 1024 / 335 = 3.057 to 7.057. The aggregate and eligibility must then be recalculated; it is invalid to leave V fixed while pretending the system has evolved. The model omits scheduler tick timing, current-entity special handling, integer rounding, group hierarchy, PELT, preemption and competing classes. It does not forecast when B will run on your machine or imply that either task gets an exact 2 ms uninterrupted interval.

Arrival, sleep and delayed dequeue#

An entity's virtual position cannot simply be reset to an arbitrary fresh value every time it wakes. place_entity and related code handle placement and lag preservation under applicable feature flags. update_entity_lag computes and clamps lag when the entity is on the runqueue; the clamp bounds extreme accounting states under the code's assumptions. Enqueue and dequeue update load, tree membership and other accounting under the runqueue's locking rules. Reweighting, migration and changes in the set of runnable entities alter the aggregate, so a single saved lag is not a promise of future latency.

The v6.12 source also contains delayed-dequeue behavior. In dequeue_entity, when DELAY_DEQUEUE is enabled, the dequeue is for sleep, the path is not marked special, and the entity is ineligible, the code can set sched_delayed and postpone the normal dequeue. Special states are excluded by the shown conditions because that mechanism relies on behavior such as spurious wakeups. When a delayed entity is subsequently selected, the source can finish the delayed dequeue and specifically warns not to reference that entity again on that path. This is a conditional mechanism, not a statement that all sleeping tasks stay runnable or all configurations enable the feature. It illustrates why tree membership, task state and object lifetime cannot be deduced from one flag in isolation.

Sleeping can change the number and weights of competitors, moving the aggregate virtual time. A short sleep is not an unlimited credit generator; the implementation's placement, lag handling and delayed-dequeue rules matter. A wakeup can prompt a preemption decision, but interrupts, preemption settings, higher classes and current runqueue state affect when the scheduler actually runs. A fair scheduler manages CPU service; it does not guarantee an application's I/O completion or a hard real-time response bound.

Groups, quotas and measurement#

With fair group scheduling, group entities compete in parent cfs_rq instances while tasks compete within child queues. A task's effective result depends on both levels and the weights of the competing groups. Comparing only two task nice values while ignoring their cgroups can give the wrong prediction. Fair bandwidth control can throttle a cgroup after it consumes configured quota until runtime is replenished. A runnable task in a throttled group can wait despite having a favorable local virtual deadline. The cgroup v2 documentation describes CPU controls; whether they are enabled and delegated is environment-specific.

PELT and utilization estimates help other scheduler decisions but are not identical to EEVDF lag. CPU utilization can reflect recent running activity, while lag describes weighted service relative to the relevant virtual-time model. yield voluntarily changes the scheduling situation under its class's implementation; it is not a guarantee that a particular competitor runs next. A low nice value or a short requested slice is also not a substitute for measuring an application's end-to-end latency under a stated workload.

Practice#

Source-only route: reproduce the A/B calculation above with a calculator or a short script. Record each input, the weighted average, each eligibility decision and the two virtual deadlines. Then change only B's virtual runtime and recalculate the average before deciding eligibility again. The deliverable is the table and its assumptions; do not compare the model's numbers to wall-clock measurements as if they were kernel trace events.

Own-child host route: inspect your shell and start one short-lived child with a positive niceness adjustment. nice -n 5 requests a relative increase, which normally reduces the child's weight; inherited niceness and limits can affect the result. It does not improve priority or alter the parent. Use an ordinary Linux shell and do not use sudo:

printf 'parent nice: '
ps -o ni= -p "$$"
nice -n 5 sh -c 'printf "child pid=%s nice=" "$$"; ps -o ni= -p "$$"; head -12 "/proc/$$/sched" 2>/dev/null || :'
printf 'parent nice after child: '
ps -o ni= -p "$$"

The child should normally show a higher numeric nice value than the parent, up to the system's limit, and the parent should retain its own value. If the parent is already near the maximum or a policy prevents the request, the difference may be smaller or absent; record the actual result. /proc/.../sched fields and accessibility vary. A reported weight or runtime is an observation under the host kernel and cgroup, not proof that it used v6.12 EEVDF or that the child received a particular CPU share. Avoid publishing process and scheduling details without reviewing them. The child exits after its commands; no cleanup or host setting reversal is needed.

For a counterexample to a simplistic claim, a higher numeric nice value does not mean an idle CPU must remain unused, and one proc sample does not establish a 1024:335 measured throughput ratio. To test proportional shares experimentally would require controlled competing workloads, placement, duration, cgroup and policy evidence; this exercise intentionally makes no such measurement.

Knowledge check#

1. Why can the earliest virtual-deadline entity be skipped by pick_eevdf?
2. What does calc_delta_fair contribute to runtime accounting and deadline construction?
3. How does the tree's deadline ordering differ from its min_vruntime augmentation?
4. Under what conditions can v6.12 delay dequeue of a sleeping entity, and why is that not universal?
5. Why can't the nice values of two tasks alone establish their actual CPU shares?

Answers#

1. It may be ineligible because its weighted virtual service is ahead of the aggregate. The search seeks the earliest eligible candidate, with current-entity and feature-specific branches.
2. It scales service or requested slice according to entity weight in virtual time. Integer scaling and the surrounding state matter; the result is not a wall-clock completion promise.
3. Deadline orders candidates in the tree, while subtree minimum virtual runtime supports eligibility pruning. The augmentation is not a claim that the tree is ordered by virtual runtime.
4. The source checks the feature, a sleep dequeue that is not special, and ineligibility before marking the entity delayed. Other configurations, states and paths use different behavior.
5. They may belong to different cgroups or classes, have different allowed CPUs or runnable periods, or be limited by quota and competing work. A sched_ext scheduler can also change class assignment.

Checkpoint#

Deliver the arithmetic table with assumptions and either the child nice observation or a source-only analysis of delayed dequeue. Pass when you correctly reject the earlier but ineligible deadline, explain the tree augmentation, and identify a group or runtime condition that defeats a simple nice-ratio prediction. If uncertain, recalculate V and trace entity_eligible, pick_eevdf and update_deadline in v6.12. This is not certification.

Sources#

• v6.12 fair scheduler: eligibility, tree pick, runtime, deadline and delayed dequeue.
• v6.12 scheduler core: policy and weight handling.
• v6.12 task and scheduling entities.
• EEVDF documentation.
• cgroup v2 CPU controls.