EEVDF and Fairness

Almost everything written about the Linux scheduler before 2023 describes CFS, and the fair class has not been CFS since 6.6. It is now EEVDF — Earliest Eligible Virtual Deadline First — and the change was not cosmetic: it added a dimension (latency) that CFS could not express, and it deleted the tunables everyone had learned to reach for.

Three concepts in the six-part treatment: weighted fair sharing, EEVDF, and group scheduling and bandwidth.

Warning: This chapter is the most version-sensitive in the curriculum. Check every claim:

git log --oneline --grep -i "eevdf" -- kernel/sched/ | tail -20
rg -n "pick_eevdf|entity_eligible|avg_vruntime|vlag" kernel/sched/fair.c | head
ls /sys/kernel/debug/sched/

Concept 1: Weighted Fair Sharing

1. What problem it solves

Most tasks on a machine have no real-time requirement. They just want a share of the CPU, and "share" has to mean something precise when there are more runnable tasks than CPUs.

Strict priority is the wrong answer for this population: a high-priority task starves everything below it. What you want is proportional share — each task gets CPU time in proportion to a weight — plus a way to express "this one matters more" that does not become "this one is the only one that runs".

2. Where it exists in the kernel

rg -n "sched_prio_to_weight" -A 12 kernel/sched/core.c
rg -n "struct load_weight \{" -A 6 include/linux/sched.h
rg -n "update_curr\b" -A 30 kernel/sched/fair.c | head -40

3. Who owns or interacts with it

4. Weight and virtual runtime

Nice is a weight, not a priority. The table is geometric: each nice level is roughly a 1.25× weight ratio, which works out to about a 10% CPU difference per step between two tasks.

rg -n -A 14 "const int sched_prio_to_weight" kernel/sched/core.c

The elegance is in virtual runtime. Rather than tracking "how much CPU should this task get", the scheduler tracks a per-entity clock that advances at a rate inversely proportional to weight:

   vruntime += delta_exec * (NICE_0_LOAD / weight)

   A nice-0 task (weight 1024) : vruntime advances at real time.
   A nice-5 task (weight  335) : vruntime advances ~3x FASTER.
   A nice-(-5) task (weight 3121): vruntime advances ~3x SLOWER.

   So "give everyone equal vruntime" IS "give everyone their weighted share",
   and the scheduler only has to compare one number.

That is the whole idea, and it survives unchanged into EEVDF. What EEVDF changed is which entity you pick given those numbers.

5. Experiment

CLAIM. nice produces a proportion, and the proportion is predictable from the weight table.

METHOD. In the guest, pinned to one CPU so there is nowhere to spread:

run() { taskset -c 0 nice -n "$1" sh -c 'while :; do :; done' & echo $!; }
A=$(run 0); B=$(run 5)
sleep 10
ps -o pid,ni,pcpu,comm -p "$A","$B"
kill "$A" "$B"

PREDICT FIRST: from the table, nice 0 has weight 1024 and nice 5 has weight 335. What percentage should each get? Compute it (1024/(1024+335)) before you look.

Then repeat with nice 0 versus nice 19, and with nice −5 versus nice +5.

6. Failure mode

Concept 2: EEVDF

1. What problem it solves

CFS could answer "how much CPU does this task get" and could not answer "how soon does it get it". Those are different questions, and interactive workloads care about the second.

A video call and a compiler can want the same 50% share while wanting completely different scheduling patterns: the call wants many small slices with low delay, the compiler wants few long slices with low overhead. CFS had one global knob (sched_latency_ns) that traded these off for everyone.

EEVDF makes the slice a per-task property and adds a fairness invariant that makes short slices safe to grant.

2. Where it exists in the kernel

rg -n "pick_eevdf" -A 40 kernel/sched/fair.c
rg -n "entity_eligible|avg_vruntime|update_entity_lag|vlag" kernel/sched/fair.c | head -20
rg -n "sysctl_sched_base_slice|base_slice" kernel/sched/fair.c kernel/sched/debug.c | head
ls /sys/kernel/debug/sched/

3. The three ideas

  LAG          How much CPU this entity is OWED, relative to perfectly fair
               service. Positive = it has had less than its share.
               Stored as se->vlag; conceptually  lag = ideal - actual.

  ELIGIBLE     An entity is eligible when its lag >= 0 -- i.e. it has NOT
               already had more than its fair share. Equivalently, its
               vruntime is at or behind the runqueue's weighted average
               (avg_vruntime).

               THIS IS THE NEW PART. An entity that has run ahead of its
               share is INELIGIBLE and cannot be picked, however short its
               deadline. That is what makes granting short slices safe.

  VIRTUAL      vruntime + (requested slice, scaled by weight).
  DEADLINE     "This entity's current request should be finished by here."

  THE PICK:  among ELIGIBLE entities, the one with the EARLIEST VIRTUAL
             DEADLINE.  Hence Earliest Eligible Virtual Deadline First.

Compare with what it replaced:

4. What this deleted

The most concrete consequence, and the one that breaks old tuning guides: the CFS tunables are gone.

# These no longer exist:
ls /proc/sys/kernel/sched_latency_ns             2>/dev/null || echo "gone"
ls /proc/sys/kernel/sched_min_granularity_ns     2>/dev/null || echo "gone"
ls /proc/sys/kernel/sched_wakeup_granularity_ns  2>/dev/null || echo "gone"

# What exists instead:
ls /sys/kernel/debug/sched/
cat /sys/kernel/debug/sched/base_slice_ns 2>/dev/null

They were replaced by a single base slice plus per-task requests. A task asks for a shorter slice through sched_setattr(2):

struct sched_attr attr = {
        .size          = sizeof(attr),
        .sched_policy  = SCHED_OTHER,
        .sched_runtime = 1 * 1000 * 1000,   /* request a ~1 ms slice */
};
syscall(SYS_sched_setattr, 0, &attr, 0);

A shorter slice means an earlier virtual deadline, so this task is picked sooner when it wakes — but it also runs for less time before being preempted, so it pays in context switches. Its share is unchanged. That decoupling of share from latency is the entire point of the change.

rg -n "struct sched_attr \{" -A 25 include/uapi/linux/sched/types.h
$EDITOR Documentation/scheduler/sched-eevdf.rst 2>/dev/null || \
  ls Documentation/scheduler/

5. Experiment

CLAIM. Slice length and share are now independent: a task can get better wakeup latency without getting more CPU.

METHOD. Two busy loops on one CPU, one requesting a short slice:

# Baseline: two nice-0 loops on CPU 0. Measure the share and the
# context-switch rate of each.
taskset -c 0 sh -c 'while :; do :; done' & A=$!
taskset -c 0 sh -c 'while :; do :; done' & B=$!
sleep 10
grep -E 'voluntary|nonvoluntary' /proc/$A/status /proc/$B/status
ps -o pid,pcpu -p $A,$B
kill $A $B

PREDICT FIRST: now suppose one of them requests a 1 ms slice via sched_setattr while the other uses the default. Predict, before writing the program:

Then write the sched_setattr version and check. The row most people get wrong is the share: they expect the low-latency task to get more CPU, and it does not — that is exactly what eligibility prevents.

Also watch the mechanism directly:

sudo bpftrace -e '
  tracepoint:sched:sched_switch {
    @slices[args.prev_comm] = hist(nsecs - @start[args.prev_pid]);
    @start[args.next_pid] = nsecs;
  }'

6. Failure mode

Concept 3: Group Scheduling and Bandwidth

1. What problem it solves

Weights between tasks are not enough when the machine is shared between tenants. A container that spawns 100 threads should not get 100× the CPU of a container with one. And a paying customer should be capped at what they paid for, even when the machine is otherwise idle.

Group scheduling makes the fair class hierarchical; bandwidth control adds a hard ceiling.

2. Where it exists in the kernel

grep -E 'CONFIG_(FAIR_GROUP_SCHED|CFS_BANDWIDTH|RT_GROUP_SCHED)=' ~/kernel/build/.config
rg -n "struct task_group \{" -A 30 kernel/sched/sched.h
rg -n "throttle_cfs_rq|unthrottle_cfs_rq|__account_cfs_rq_runtime" kernel/sched/fair.c | head
ls /sys/fs/cgroup/                        # cgroup v2
$EDITOR Documentation/admin-guide/cgroup-v2.rst   # the "cpu" section

3. How it works

This is why sched_entity is a separate structure from task_struct. A sched_entity can represent a group rather than a task, and a group has its own cfs_rq full of entities.

   root cfs_rq
     ├── se(task A)              weight 1024
     └── se(GROUP "container1")  weight 1024
            └── cfs_rq
                 ├── se(task B)  weight 1024
                 └── se(task C)  weight 1024

   Task A gets 50% of the CPU.
   The group gets 50%, which B and C then split -> 25% each.
   Adding a hundred more tasks to container1 does not take anything from A.

The knobs, on cgroup v2:

4. The throttling trap

Bandwidth control is a common and badly-understood source of latency in containers, and it is worth understanding precisely because the symptom looks like something else entirely.

   cpu.max = "10000 100000"      → 10 ms of CPU per 100 ms period

   A multi-threaded app with 8 runnable threads burns the whole 10 ms quota
   in 1.25 ms of wall-clock time -- then EVERY thread in the group is
   THROTTLED for the remaining 98.75 ms of the period.

   The symptom: p99 latency spikes of ~100 ms, with the CPU mostly idle.
   The cause is not the scheduler being unfair. It is the quota being
   consumed in parallel and the throttle applying to the whole group.

# The measurement that identifies it immediately:
cat /sys/fs/cgroup/<path>/cpu.stat
#   nr_throttled and throttled_usec being nonzero IS the answer.

5. Experiment

CLAIM. Group weights compose hierarchically, and quota throttling is visible in cpu.stat.

METHOD. In the guest, with cgroup v2 mounted:

cd /sys/fs/cgroup
mkdir -p lab/g1 lab/g2
echo "+cpu" > cgroup.subtree_control
echo "+cpu" > lab/cgroup.subtree_control

echo 100 > lab/g1/cpu.weight
echo 100 > lab/g2/cpu.weight

# Two busy loops in g1, ONE in g2, all pinned to one CPU.
for i in 1 2; do taskset -c 0 sh -c 'while :; do :; done' & echo $! > lab/g1/cgroup.procs; done
taskset -c 0 sh -c 'while :; do :; done' & echo $! > lab/g2/cgroup.procs
sleep 10
ps -o pid,pcpu,comm --sort=-pcpu | head -5

PREDICT FIRST: equal group weights, two tasks in one group and one in the other. What does each of the three tasks get?

Then the throttle:

echo "10000 100000" > lab/g1/cpu.max      # 10% of one CPU
sleep 10
cat lab/g1/cpu.stat

PREDICT FIRST: will nr_throttled be roughly 10 per second, 100 per second, or zero? And what happens to the latency of a task in g1, as opposed to its throughput?

6. Failure mode

Validation / Self-check

1. Why is proportional share the right model for most tasks, and strict priority the wrong one?
2. What is nice actually setting? Compute the split for nice 0 versus nice 5 from the weight table.
3. Explain virtual runtime in one sentence, and say why "equal vruntime" equals "weighted fair share".
4. Define lag, eligibility, and virtual deadline. Which of the three is the genuinely new idea?
5. State the EEVDF pick rule, and contrast it with CFS's.
6. Why does eligibility make it safe to grant a task a very short slice?
7. Which three sysctls disappeared in 6.6, and what replaced them?
8. A task requests a 1 ms slice. What improves, what gets worse, and what is unchanged?
9. Why is sched_entity a separate structure from task_struct?
10. Two cgroups with equal cpu.weight, one containing two busy tasks and one containing eight. What does each task get?
11. Describe the multi-threaded quota-throttling failure precisely, including the symptom and the one file that diagnoses it.
12. You read a 2019 article explaining the Linux scheduler. Name two things in it that are now wrong.

Next: Placement, Balancing, and Power — which CPU, at what frequency, and why those are one question.