At any instant your machine has hundreds of runnable-or-sleeping tasks and a handful of CPUs. The scheduler’s job sounds like an optimization problem, but the kernel’s actual definition is simpler and stranger: model an ideal CPU that runs all N runnable tasks simultaneously at 1/N speed each, then keep reality as close to that fiction as possible. Everything else — nice values, latency, interactivity — falls out of how that fiction gets enforced.

CFS: Fairness as a Sort Key

The Completely Fair Scheduler (2007–2023) tracked, per task, a virtual runtime: actual CPU nanoseconds consumed, scaled by the task’s weight. Runnable tasks sat in a red-black tree ordered by vruntime, and the scheduler’s core decision was almost embarrassingly simple: run the leftmost task — the one that has received the least weighted CPU so far.

text
            vruntime tree (per CPU)
                 [ 201ms ]
                /         \
          [ 187ms ]     [ 214ms ]
          /                     \
   [ 180ms ] ◀── leftmost: runs next

The elegance is in what emerges:

  • Nice values are just weights. Each nice step scales weight by ~1.25×; nice 0 = weight 1024. A nice -5 task’s vruntime advances slower, so it drifts left and gets more real CPU — precisely proportionally, no special cases.
  • Sleepers get service, not bonuses. A task waking from I/O has a stale low vruntime; CFS clamps it near the current minimum — it goes to the front of the line, but can’t cash in hours of sleep as a CPU windfall (that clamping is what killed the fork-bomb-friendly “interactivity heuristics” of the old O(1) scheduler).
  • Timeslices aren’t fixed. A target latency (~6 ms-ish, scaled by load) is divided among runnable tasks by weight. Two tasks: ~3 ms each. Twenty: ~1 ms each, floored by minimum granularity so context-switch overhead doesn’t eat the machine.

Group scheduling stacks the same mechanism: cgroups form a tree, fairness is applied between groups, then recursively within — this is what cpu.weight in your container runtime actually turns. Your Kubernetes CPU shares are nested vruntime arithmetic.

The Crack in CFS

CFS answers “who deserves CPU” but not “who needs it soon.” Two tasks with equal weight get equal throughput — but one might be a video decoder that needs 2 ms every 10 ms, the other a batch compiler that couldn’t care less. CFS had no vocabulary for the difference, and a decade of band-aids (sched_min_granularity, wakeup preemption heuristics, the out-of-tree latency-nice patches) tried to fake one. Desktop stutter under compile load and tail latency in overcommitted servers were the visible symptoms.

EEVDF: Deadlines Join the Party

Kernel 6.6 (late 2023) replaced CFS’s pick-leftmost with EEVDF — Earliest Eligible Virtual Deadline First, from a 1995 paper that sat in the literature for 28 years. Each task now has two numbers:

  • Lag: how far its received CPU deviates from its ideal fair share. Positive lag = owed CPU. Only tasks with non-negative lag are eligible — you can’t get ahead of your entitlement.
  • Virtual deadline: eligible-time + slice/weight. Shorter-slice tasks get nearer deadlines.

Pick rule: among eligible tasks, earliest virtual deadline wins. Fairness is preserved by eligibility (lag is even carried across sleep/wake so you can’t game it by napping), while latency becomes controllable: a task that requests a small slice (via sched_setattr’s sched_runtime, the realized form of latency-nice) gets frequent short turns; a batch task takes rare long ones. Same throughput share, different granularity — the distinction CFS couldn’t express. A pile of scheduler heuristics died in the process, which kernel developers celebrated as much as the feature itself.

Watching It

Theory is checkable in an afternoon: perf sched record + perf sched latency shows per-task wakeup-to-run delays; /proc/<pid>/sched exposes vruntime, lag and slice; hackbench vs a cyclictest thread demonstrates the EEVDF difference directly. And when “the scheduler is unfair” gets blamed in prod, the boring truth is usually cgroup weights or CPU affinity — check /sys/fs/cgroup/.../cpu.weight before filing the kernel bug.

Takeaways

  • Linux schedules by emulating an ideal fair CPU; nice values are weights on virtual time, not priorities in the classic sense.
  • CFS = run the smallest weighted-runtime task; simple, fair, latency-blind.
  • EEVDF adds eligibility (lag) + virtual deadlines: fairness unchanged, latency finally a first-class, per-task request.
  • cgroup CPU weights are the same fairness math applied recursively — that’s what container “CPU shares” mean.
  • perf sched, /proc/<pid>/sched, and cgroup weights before conspiracy theories.