Extending Fair Scheduling: Inside Linux’s New EEVDF Algorithm

In the previous post we covered the CFS fair‑scheduling classes (SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE). This article continues the series by describing EEVDF (Earliest Eligible Virtual Deadline First), the scheduler that fully replaces CFS starting with Linux 6.6.

Traditional CFS parameters such as sysctl_sched_latency, sysctl_sched_min_granularity and sysctl_sched_wakeup_granularity determine each task’s time slice. For a task i the slice t_i is calculated as:

where weight_i is the task’s weight, total_weight is the sum of weights of all runnable tasks, and sched_period (the scheduling period) is derived from sched_latency_ns and sched_min_granularity_ns.

EEVDF (Earliest Eligible Virtual Deadline First) keeps the fairness goal of CFS but adds a stronger focus on interactivity. CFS selects the task with the smallest virtual runtime (the one that “owes” the most CPU). EEVDF instead selects the task with the smallest virtual deadline (the one that is most urgently eligible). Both algorithms still weight tasks by their nice value.

The scheduler introduces a new metric called lag . A positive lag means the task has not yet received its entitled CPU quota and is therefore eligible to run; a negative lag indicates the task has already consumed more than its share.

For example, five tasks with identical nice values each receive roughly 20 % of the CPU, demonstrating that EEVDF can still achieve equal distribution while respecting urgency.

The virtual deadline is computed by the formula shown below:

Because the deadline depends on the task’s lag, a task that has been waiting a long time (e.g., “Mr. Jack”) may have to wait many scheduling periods before becoming eligible again.

Applications can suggest a custom slice via sched_attr::sched_runtime. The value must be chosen carefully: a very small slice causes frequent pre‑emptions, while a very large slice increases latency. The kernel clamps the value to a range that depends on the timer frequency (e.g., 0.1 ms at HZ=1000 equals 1/10 of the period, while 10 ms at HZ=100 is ten times larger).

The default base slice is derived from the former CFS parameter sysctl_sched_min_granularity and is calculated as 0.75 ms × (1 + ilog(ncpus)). On an 8‑core system this yields a base slice of 3 ms.

To illustrate urgency, the article uses a salary analogy: a weekly‑paid task, a monthly‑paid task, and a yearly‑paid task all have the same nice value, but their slices differ so that the weekly task must finish its quota each week, the monthly task each month, and the yearly task only once per year. This shows how sched_attr::sched_runtime can encode different timing requirements without changing the weight.

A detailed timeline with two clients (client 1 and client 2) demonstrates EEVDF’s decision process. Both clients have weight 2 and request lengths of 2 and 1, respectively. The article walks through points A, B, C, D, E, and F, showing how virtual time advances, when each client becomes eligible, how pre‑emptions occur, and how virtual deadlines are updated after each slice. The diagrams below capture each step:

Through this example the article shows that EEVDF enforces a “first‑to‑shout‑first‑served” rule while still guaranteeing overall fairness (the “common prosperity” effect). Short tasks may be scheduled frequently with short slices, whereas long tasks receive fewer but longer slices.

Overall, the article provides a step‑by‑step analytical view of EEVDF’s algorithmic changes, parameter defaults, and practical implications for Linux kernel scheduling.