# How Linux Decides What Runs Next: CFS to EEVDF

> For 15 years Linux picked the next task with a red-black tree of virtual runtimes. In 6.6 that changed for the first time since 2007. What fairness actually means, how nice values work, and why latency-sensitive tasks forced a redesign.

URL: https://harshith.in/blog/cfs-and-eevdf-scheduling/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: kernel, linux, systems

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.