The Linux scheduler: from runnable tasks to CPU time

A request has its data, and its worker has been woken, yet the response is late. Follow three questions: where may the task run, how much CPU service can it receive, and whose turn is it now?

This article focuses on ordinary fair scheduling. Linux began introducing EEVDF in 6.6; the teaching models are compared with local Linux 7.2 source, rather than presented as a complete kernel simulation.

1. Run queues identify tasks that can execute

Linux primarily maintains run queues per CPU. Both the current task and tasks waiting for CPU time can be TASK_RUNNING. A task sleeping for I/O or a condition cannot consume CPU merely because it has high priority. Wakeup updates state, selects a suitable CPU, and enqueues the task; it may request rescheduling if the new task should preempt the current one.

A rescheduling request is not an unconditional jump at any instruction. The kernel checks it at appropriate scheduling points, subject to interrupt state, disabled preemption, locks, and the preemption model. A scheduler invocation may select the current task again: calling schedule and switching between distinct tasks are different events.

Per-CPU queues reduce global contention, but remote wakeups, load pulling, and migration still coordinate CPUs and queue locks. Affinity, cpusets, and active scheduling policies constrain the candidates before balancing can improve their distribution.

2. Fair accounting: convert runtime to virtual service

Take two continuously runnable tasks A and B on one CPU. With weights 2:1 and 9 ms to distribute, their ideal allocation is 6 ms and 3 ms.

Dividing runtime by weight gives both tasks 3 virtual units. A heavier task's virtual clock advances more slowly, so equal virtual progress requires more actual runtime. With reference weight $w_0$:

$$\Delta v_i=\Delta t_i\frac{w_0}{w_i}$$

Nice 0 has base weight 1024; nice 5 has weight 335. If only those two tasks continuously compete on one CPU at the same fair-scheduling level, the former's ideal share is 1024 / (1024 + 335) ≈ 75.35%.

That share changes when a competitor blocks, another task arrives, or a cgroup hierarchy changes the competition. Nice expresses relative weight, not a fixed CPU percentage.

In the interactive figure, width represents weight and area represents actual CPU time. Move the allocation away from its weighted split, then change the weight: the height reveals which task has received more normalized service.

Classic CFS uses vruntime to identify tasks behind in normalized service. This explains long-run shares but does not fully express how promptly a short request should respond. EEVDF separates eligibility from ordering eligible requests.

3. EEVDF: eligibility and virtual deadlines do different jobs

Eligibility from lag

For a simplified fixed runnable set, let task runtime be $v_i$, weight $w_i$, and system virtual time $V$ their weighted mean:

$$V=\frac{{\sum }_i{w}_i{v}_i}{{\sum }_i{w}_i},{\mathrm{lag}}_i=w_i(V-v_i)$$

Positive lag means the task has received less service than the fair reference; zero lag is also eligible. Negative lag means it is ahead and should not obtain still more service merely by asking for a short request.

Order eligible requests by deadline

For a new request for actual service $r_i$, its virtual deadline is:

$$d_i=v_{i,\mathrm{start}}+r_i\frac{w_0}{w_i}$$

This uses the request's starting virtual position. As execution advances vruntime, an already assigned deadline does not continually slide forward with it. A new request establishes a new deadline. The example below takes a snapshot at request starts.

Among eligible entities, earlier virtual deadlines receive preference. These are service coordinates, not wall-clock instants or SCHED_DEADLINE completion guarantees.

Why B wins this snapshot

All three tasks have weight 1, with reference weight normalized to 1:

V = (98 + 99 + 103) / 3 = 100. Choosing the smallest vruntime alone gives A; choosing the smallest deadline alone gives C. EEVDF selects B here: C's short request does not erase its excess service, and B has the earlier eligible deadline.

Move C's service position to change eligibility, or B's request length to change its deadline. Shortening a request does not itself change the service already received. Each edit constructs a new snapshot.

This small executable model checks the arithmetic without modeling wakeups, hierarchy, or migration:

from fractions import Fraction as F

tasks = {
    "A": {"w": F(1), "v": F(98), "r": F(10)},
    "B": {"w": F(1), "v": F(99), "r": F(5)},
    "C": {"w": F(1), "v": F(103), "r": F(1, 4)},
}
V = sum(t["w"] * t["v"] for t in tasks.values()) / sum(
    t["w"] for t in tasks.values()
)
eligible = {}
for name, t in tasks.items():
    lag = t["w"] * (V - t["v"])
    deadline = t["v"] + t["r"] / t["w"]
    print(name, "lag=", lag, "deadline=", deadline)
    if lag >= 0:
        eligible[name] = deadline
assert V == 100
assert min(eligible, key=eligible.get) == "B"

What the implementation adds

A shorter request can affect response order without increasing long-term weight. The kernel must also prevent a task from running ahead, briefly sleeping, and waking with undeserved fresh credit. Preserved and decaying lag, including deferred-dequeue accounting, maintain this constraint. An entity retained for accounting does not imply that a task still waiting for its event may execute user code.

In local kernel/sched/fair.c, the relevant tree is organized by deadline and uses subtree vruntime information to prune eligibility searches. pick_eevdf() also handles protection of the current request. Group entities, enqueue/dequeue adjustments, and integer precision make maintaining V more involved than averaging a fixed set. Read the eligibility and deadline decisions first, then these implementation details. EEVDF, CFS design

4. Policies and scheduling classes

Ordinary tasks normally use SCHED_OTHER, also called SCHED_NORMAL inside the kernel. EEVDF operates within fair scheduling; applications do not need a generic SCHED_EEVDF policy to enable it.

Deadline normally precedes real-time, which precedes fair scheduling. Internal classes such as stop and the active sched_ext mode also matter; three rows are not the entire implementation.

For runtime=2 ms, deadline=10 ms, period=10 ms, a task declares its CPU demand and scheduling deadline. Constraints include runtime ≤ deadline ≤ period, with admission checking. This does not automatically invoke an application function every 10 ms: work release, execution demand, and blocking still need analysis.

These quantities cannot substitute for each other. SCHED_DEADLINE, sched_ext

5. cgroups: relative shares and an absolute allowance

Allocate to groups, then to tasks

Suppose sibling groups A:B have weights 2:1 on one CPU, without quota. A contains two equal, continuously runnable workers; B contains one. A receives about 2/3, split in half internally, so each worker receives about 1/3. Adding a third worker to A leaves its group share about 2/3: each A worker receives about 2/9, while B's worker keeps about 1/3. Creating threads need not directly steal another group's share.

Multiple CPUs spend one budget

cpu.weight is neither a reservation nor a strict cap. cpu.max limits total CPU time per period. 50000 100000 permits 50 ms of CPU time per 100 ms period. Two threads running concurrently on two CPUs can spend that combined budget in about 25 ms, then be throttled until replenishment. Each CPU does not get its own 50 ms allowance.

Move wall-clock time across a period boundary while changing parallelism. The budget is shared by every active lane:

An idle CPU elsewhere does not give this group more allowance. Compare cpu.stat throttling increments, cpu.max, and request latency over the same interval; application locks, I/O, and upstream queues still require separate investigation. cgroup v2 CPU controller

6. Placement: even load is not always fastest

Migration can lose a warm cache or move a task farther from its NUMA memory. SMT siblings share execution resources and are not independent full cores. Placement balances spare capacity, locality, topology, and energy rather than merely equalizing task counts.

PELT summarizes recent running and runnable behavior. Utilization, runnable load, and weighted load are different quantities: waiting for CPU can indicate pressure without representing CPU service already consumed. A brief 100% sample neither proves migration will help nor identifies the whole-system bottleneck.

Wakeup placement, periodic balancing, and idle-CPU pulling operate in different situations. First establish the task's allowed CPUs, cpuset, and relevant capacity constraints. Adding CPUs outside a task's allowed set cannot automatically remove its queueing.

7. Repeatable read-only observation

This queries the current Python process without changing policy or configuration. /proc/self/sched fields depend on kernel configuration; do not parse it as a fixed-column format.

import os
from pathlib import Path

print("policy:", os.sched_getscheduler(0))
print("nice:", os.getpriority(os.PRIO_PROCESS, 0))
print("allowed CPUs:", sorted(os.sched_getaffinity(0)))
try:
    for line in Path("/proc/self/sched").read_text().splitlines():
        if any(key in line for key in (
            "se.sum_exec_runtime", "nr_switches", "nr_voluntary_switches",
            "nr_involuntary_switches", "se.load.weight", "policy", "prio"
        )):
            print(line)
except OSError as exc:
    print("sched statistics unavailable:", exc)

Separate the event time, sched_wakeup, and the task's appearance as next in sched_switch. Wakeup-to-run includes CPU waiting and related scheduling paths; executing the request includes application work. Neither isolates register and address-space handoff cost. The next article, context switching, follows that handoff directly.