vault

Virtual Runtime and the Fair Scheduling Invariant

14 min read

Virtual Runtime and the Fair Scheduling Invariant

Virtual runtime (vruntime) is the single number that makes Linux’s fair scheduler fair. It is a per-task clock, measured in nanoseconds, that advances not at wall-clock speed but at a rate inversely proportional to the task’s weight: a high-priority (low-nice) task’s vruntime ticks slower than real time, a low-priority task’s ticks faster. The scheduler’s core accounting routine update_curr() adds, on every accounting event, the real elapsed time scaled by NICE_0_LOAD / weight to the running task’s vruntime (per kernel/sched/fair.c, v6.12). Because the scaling factor is the only thing that differs between tasks, equal vruntime progress means CPU time received in proportion to weight — that is the fair-scheduling invariant. This note covers how vruntime is computed and the min_vruntime monotonic floor that anchors it; the question of which runnable task the scheduler then picks belongs to its sibling, Eligibility Lag and Virtual Deadlines in EEVDF, because the modern Earliest Eligible Virtual Deadline First (EEVDF) scheduler does not simply pick the lowest vruntime.

The invariant described here is shared machinery: it was the heart of the Completely Fair Scheduler (CFS) (Linux 2.6.23, 2007) and survives unchanged in EEVDF, the default for SCHED_OTHER tasks since kernel 6.6 (2023) (sched-eevdf). What changed in the move to EEVDF is the selection rule, not the clock. Everything below is verified against the 6.12 LTS and 6.18 LTS sources (the two current long-term branches as of 2026-06-03).

Mental Model — A Clock That Runs at a Task’s Fair Speed

Imagine an idealized “perfect multitasking CPU” that could run all n runnable tasks simultaneously, each at 1/n of full speed. On that fictional machine no task is ever ahead or behind; they all make progress in lockstep. This is the framing the CFS design document opens with: “CFS basically models an ideal, precise multi-tasking CPU on real hardware” (sched-design-CFS). Real hardware runs one task at a time per core, so the kernel needs a bookkeeping device to measure how far each task is from that ideal. That device is vruntime.

Think of every task as carrying a stopwatch. When the task is on the CPU, its stopwatch runs — but geared. A nice 0 task’s stopwatch runs at exactly real-time speed. A high-priority nice -5 task’s stopwatch runs slow (it accumulates less virtual time per real nanosecond), so it can run longer before its vruntime catches up to its peers. A low-priority nice +5 task’s stopwatch runs fast, so its vruntime shoots ahead and it stops being the favored choice sooner. The fair scheduler’s job is to keep all the stopwatches reading roughly the same value — and the gear ratio is precisely what converts “keep the stopwatches equal” into “give CPU time in proportion to weight.”

flowchart LR
  subgraph REAL["Real CPU time elapses: delta_exec nanoseconds"]
    D["delta_exec<br/>(wall-clock ns on CPU)"]
  end
  D --> SCALE["calc_delta_fair():<br/>multiply by NICE_0_LOAD / weight"]
  SCALE --> HIGH["nice -5 (weight 3121)<br/>vruntime += delta * 1024/3121<br/>≈ delta * 0.33 → slow clock"]
  SCALE --> ZERO["nice 0 (weight 1024)<br/>vruntime += delta * 1024/1024<br/>= delta → real-time clock"]
  SCALE --> LOW["nice +5 (weight 335)<br/>vruntime += delta * 1024/335<br/>≈ delta * 3.06 → fast clock"]

How one quantity of real CPU time (delta_exec) turns into three different amounts of virtual time. What it shows: the same 1 ms of real CPU time advances a nice -5 task’s vruntime by only ~0.33 ms, a nice 0 task’s by exactly 1 ms, and a nice +5 task’s by ~3.06 ms (weights from sched_prio_to_weight[] in core.c). The insight to take: because the scheduler tries to equalize vruntime, the slow-clocked high-priority task must run more real time to reach the same vruntime as a low-priority task — which is exactly how weight becomes proportional CPU share. The weight numbers themselves live in Nice Values Weights and Priority Scaling.

The Fair-Scheduling Invariant, Derived Symbol by Symbol

The invariant is a one-line consequence of the scaling formula. Let a task i have weight w_i (an integer derived from its nice value — nice 0 maps to weight 1024). Suppose it runs for delta nanoseconds of real CPU time. The kernel updates its virtual runtime as

vruntime_i  +=  delta * (NICE_0_LOAD / w_i)

where NICE_0_LOAD is the weight of a nice 0 task. Rearranged, the real time a task accumulates per unit of virtual time is

delta  =  Δvruntime_i * (w_i / NICE_0_LOAD)

Now apply the fairness goal: the scheduler steers all runnable tasks toward the same vruntime. If two tasks a and b end up having advanced their vruntime by the same amount Δv over some interval, then

real_time_a / real_time_b  =  (Δv * w_a / NICE_0_LOAD) / (Δv * w_b / NICE_0_LOAD)  =  w_a / w_b

The Δv and NICE_0_LOAD cancel, leaving real CPU time received in the exact ratio of the weights. That is the fair-scheduling invariant: equalizing virtual runtime is equivalent to distributing real CPU time in proportion to weight. A nice -5 task (weight 3121) gets 3121/1024 ≈ 3.05× the CPU time of a nice 0 task over any interval in which their vruntimes stay aligned. This is why Linux’s fair scheduler is, at its core, a weighted fair queueing scheduler (Corbet, “An EEVDF CPU scheduler for Linux”, LWN 925371).

Uncertain

Verify: that under EEVDF (not CFS), tasks’ vruntimes are actually driven toward equality in steady state. Reason: EEVDF’s selection rule targets bounded lag and earliest virtual deadline, not literal vruntime equality (see Eligibility Lag and Virtual Deadlines in EEVDF); the invariant above is exact for the clock, but the claim “the scheduler equalizes vruntime” is a CFS-era simplification. The weighted-share outcome still holds because lag is bounded, but the mechanism is lag-driven, not equality-driven. To resolve: read the steady-state lag-bound analysis in fair.c (entity_lag clamp) and the 1995 Stoica/Abdel-Wahab EEVDF paper. uncertain

Mechanical Walk-through — update_curr() and calc_delta_fair()

The clock is wound forward in exactly one place: update_curr() in kernel/sched/fair.c. It is called on every event that could change which task should run — the periodic scheduler tick, a task blocking or being enqueued, an explicit yield, or any path that needs the running task’s accounting brought up to date. The accounting half (computing the elapsed time) lives in update_curr_se():

static s64 update_curr_se(struct rq *rq, struct sched_entity *curr)
{
	u64 now = rq_clock_task(rq);          /* monotonic per-rq clock, excludes IRQ-stolen time */
	s64 delta_exec = now - curr->exec_start;   /* real ns since this task last accounted */
	if (unlikely(delta_exec <= 0))
		return delta_exec;
	curr->exec_start = now;                /* reset the window start */
	curr->sum_exec_runtime += delta_exec;  /* lifetime real CPU ns, used by /proc, getrusage */
	...
	return delta_exec;
}

Line by line: rq_clock_task() reads the per-run-queue task clock — a monotonic nanosecond counter that deliberately excludes time stolen by interrupt handlers, so a task is not charged vruntime for IRQ work that ran while it was nominally “on CPU.” delta_exec is the real wall-clock nanoseconds the task has run since the last accounting point (exec_start). The <= 0 guard handles clock non-monotonicity and the case where no time has passed. exec_start is advanced so the next call measures a fresh window, and sum_exec_runtime accumulates the task’s lifetime real CPU time (this is the unscaled number surfaced to userspace).

Then update_curr() converts that real delta_exec into virtual time and advances the clock:

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	...
	delta_exec = update_curr_se(rq, curr);
	if (unlikely(delta_exec <= 0))
		return;
 
	curr->vruntime += calc_delta_fair(delta_exec, curr);   /* THE virtual-time update */
	resched = update_deadline(cfs_rq, curr);               /* EEVDF: did it use up its slice? */
	update_min_vruntime(cfs_rq);                            /* advance the monotonic floor */
	...
}

The load-bearing line is curr->vruntime += calc_delta_fair(delta_exec, curr). That is the entire virtual-clock advance. update_deadline() then asks whether the task has exhausted its requested time slice (the deadline machinery is EEVDF’s, covered in Eligibility Lag and Virtual Deadlines in EEVDF and Time Slices and Request Sizes in EEVDF), and update_min_vruntime() advances the floor described in the next section. (In 6.12/6.18, update_curr also feeds the per-rq fair_server deadline accounting and cgroup CPU accounting via update_curr_task(), but those are orthogonal to the clock itself.)

The scaling: calc_delta_fair and __calc_delta

calc_delta_fair() is the function that does the gearing:

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
	return delta;
}

The fast path is the common case: a nice 0 task has load.weight == NICE_0_LOAD, so the gear ratio is exactly 1 and delta passes through unscaled — its vruntime advances at real-time speed. Only when the weight differs does it call __calc_delta() to compute delta * NICE_0_LOAD / weight.

The header comment on __calc_delta states the contract precisely: it computes delta_exec * weight / lw.weight. As calc_delta_fair calls it with weight = NICE_0_LOAD and lw = se->load, the result is delta_exec * NICE_0_LOAD / se->load.weight — exactly the gear ratio in the derivation. But the kernel cannot afford a 64-bit division on this hot path, so it uses a reciprocal multiply: for each weight it precomputes inv_weight = 2^32 / weight once and caches it, then computes

delta * NICE_0_LOAD / weight  ≈  (delta * NICE_0_LOAD * inv_weight) >> 32

turning a division into a multiply and a shift. The actual code (WMULT_SHIFT == 32, WMULT_CONST == ~0U) carefully handles overflow by progressively shifting down the intermediate fact when its high 32 bits are non-zero, decrementing the final shift to compensate, so the 64-bit product never overflows. The precise overflow dance (fls, mul_u32_u32, mul_u64_u32_shr) is an implementation detail; the meaning is “multiply by the reciprocal of the weight.” The reciprocal table and the weight values themselves are the subject of Nice Values Weights and Priority Scaling.

Note

A subtle fixed-point point: the nice 0 → 1024 mapping in sched_prio_to_weight[] is the userspace-visible weight. Internally the kernel scale_load()s weights up by SCHED_FIXEDPOINT_SHIFT (10 bits) for extra precision, so on 64-bit NICE_0_LOAD == 1L << 20 == 1048576, and the vruntime math scale_load_down()s back where needed. The ratios are identical either way (1024/3121 == 1048576/3196... etc.), so the derivation above is unaffected — only the absolute magnitudes change. Treat NICE_0_LOAD as “the weight of a nice-0 task” and defer the fixed-point details to Nice Values Weights and Priority Scaling.

The min_vruntime Monotonic Floor

vruntime is a free-running u64 that only ever increases for a given task, but different tasks have wildly different vruntime values: a CPU-bound task that has been running for hours has an enormous vruntime, while a task that just woke from a long sleep has a stale, tiny one. If a freshly-woken task were placed with its old, tiny vruntime, it would look infinitely behind and would monopolize the CPU for a long time — the classic “sleeper hogs the CPU on wakeup” bug. The kernel needs a reference point that tracks “roughly where the runnable tasks are now,” so new and woken tasks can be placed sensibly relative to it. That reference is cfs_rq->min_vruntime.

min_vruntime is monotonically non-decreasing — it never moves backward — and it serves as the origin (v0) for the relative encoding the scheduler uses internally. Each task’s position is stored as entity_key = vruntime − min_vruntime, a small signed delta rather than a giant absolute number, which keeps the weighted-average arithmetic from overflowing (the comment in fair.c notes the max measured key * weight was ~44 bits). The update routine:

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *se = __pick_root_entity(cfs_rq);  /* augmented-tree root */
	struct sched_entity *curr = cfs_rq->curr;
	u64 vruntime = cfs_rq->min_vruntime;
 
	if (curr) {
		if (curr->on_rq)
			vruntime = curr->vruntime;     /* candidate: the running task */
		else
			curr = NULL;
	}
	if (se) {
		if (!curr)
			vruntime = se->min_vruntime;            /* smallest in tree */
		else
			vruntime = min_vruntime(vruntime, se->min_vruntime);
	}
	/* ensure we never gain time by being placed backwards. */
	cfs_rq->min_vruntime = __update_min_vruntime(cfs_rq, vruntime);
}

It computes a candidate — the minimum of the currently-running task’s vruntime and the smallest vruntime in the run-queue tree (se->min_vruntime here is the augmented-tree minimum, cached at each node) — and then __update_min_vruntime() advances cfs_rq->min_vruntime toward that candidate only if the candidate is larger (the open-coded max_vruntime: delta = candidate − min_vruntime; if (delta > 0) min_vruntime = candidate). The comment says it plainly: “ensure we never gain time by being placed backwards.” The floor follows the slowest-but-runnable task forward and never retreats. This monotonicity is what lets a newly woken task be anchored to min_vruntime (or, in EEVDF, to the weighted average V, which itself is computed relative to this floor) without either being penalized for its absence or being handed a windfall — the placement logic lives in Eligibility Lag and Virtual Deadlines in EEVDF.

A second subtlety: when the floor advances by delta, __update_min_vruntime also calls avg_vruntime_update(cfs_rq, delta) to keep the run-queue’s weighted-average virtual time (avg_vruntime, the EEVDF eligibility reference V) consistent with the new origin. That is the seam between this note (the floor) and its sibling (the average that drives eligibility).

Configuration and Observation

There are no vruntime knobs per se — the clock is mechanism, not policy — but you can observe and influence it:

  • sum_exec_runtime (real CPU ns) is exposed per-thread in /proc/<pid>/schedstat (first field) and via getrusage(2). This is the unscaled time, not vruntime.
  • vruntime, min_vruntime, and avg_vruntime are visible under /sys/kernel/debug/sched/debug (requires CONFIG_SCHED_DEBUG), per-cfs_rq. The nr_running, load, and the per-task vruntime columns let you watch the invariant in action.
  • /sys/kernel/debug/sched/base_slice_ns (also CONFIG_SCHED_DEBUG) tunes the request size that feeds the deadline (not the clock); see Time Slices and Request Sizes in EEVDF.
  • nice(2) / setpriority(2) / sched_setattr(2) change a task’s weight and therefore its vruntime gear ratio — the only userspace lever on the clock.

A quick experiment that makes the invariant concrete: pin two CPU-bound loops to one isolated CPU, set one to nice 0 and one to nice 5, and watch top. The nice 0 task gets weight 1024, the nice 5 task weight 335; over time the CPU split converges to 1024 : 335 ≈ 75% : 25%. That ratio is the fair-scheduling invariant, observed directly.

Common Misunderstandings

  • “vruntime is the time a task has run.” No — sum_exec_runtime is. vruntime is weighted, scaled virtual time; only for a nice 0 task do the two advance together. Conflating them produces wrong reasoning about priority.
  • “The scheduler picks the lowest vruntime.” That was CFS (it picked the leftmost node of a vruntime-ordered red-black tree, per sched-design-CFS). EEVDF picks the earliest-deadline eligible task; vruntime feeds eligibility, not selection. See Eligibility Lag and Virtual Deadlines in EEVDF and The EEVDF Scheduler. Carrying the CFS rule into EEVDF reasoning is the single most common error.
  • “min_vruntime is the average / the minimum.” It is a monotonic floor that approximately tracks the minimum runnable vruntime; it can lag slightly and never decreases. The weighted average V (the eligibility line) is a different quantity, avg_vruntime(), computed relative to this floor. Keeping the two apart is essential.
  • “Sleeping accrues vruntime.” A sleeping task’s clock is stopped — it accrues no vruntime while off the run queue. On wake it is re-placed relative to the current floor/average (with its lag remembered), not advanced as if it had been running. This is why a process that sleeps for a day does not return with a colossal vruntime.

Version Notes (6.12 LTS / 6.18 LTS, as of 2026-06-03)

The vruntime/calc_delta_fair/update_curr/min_vruntime machinery in this note is identical between 6.12 and 6.18 — same code, same formulas (curr->vruntime += calc_delta_fair(delta_exec, curr) at fair.c:1230 in 6.12, fair.c:1227 in 6.18). The relevant difference is downstream in the slice/deadline tunable, not the clock: sysctl_sched_base_slice defaults to 750000 ns (0.75 ms) in 6.12 and 700000 ns (0.7 ms) in 6.18 (fair.c v6.12 line 76; v6.18 line 79). That value feeds the virtual deadline, not vruntime; it is detailed in Time Slices and Request Sizes in EEVDF.

See Also

Graph View

Backlinks