EEVDF Scheduler — The Linux Kernel documentation

The Linux Kernel

7.2.0-rc1

Quick search

Contents

Development process

Submitting patches

Code of conduct

Maintainer handbook

All development-process docs

Core API

Driver APIs

Subsystems<br>Core subsystems<br>Core API Documentation

Driver implementer’s API guide

Memory Management Documentation

Power Management

Scheduler

Timers

Locking

Human interfaces

Networking interfaces

Storage interfaces

Other subsystems

Locking

Licensing rules

Writing documentation

Development tools

Testing guide

Hacking guide

Tracing

Fault injection

Livepatching

Rust

Administration

Build system

Reporting issues

Userspace tools

Userspace API

Firmware

Firmware and Devicetree

CPU architectures

Unsorted documentation

Translations

This Page

Show Source

English

Spanish

EEVDF Scheduler¶

The “Earliest Eligible Virtual Deadline First” (EEVDF) was first introduced<br>in a scientific publication in 1995 [1]. The Linux kernel began<br>transitioning to EEVDF in version 6.6 (as a new option in 2024), moving<br>away from the earlier Completely Fair Scheduler (CFS) in favor of a version<br>of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information<br>regarding CFS can be found in<br>CFS Scheduler.

Similarly to CFS, EEVDF aims to distribute CPU time equally among all<br>runnable tasks with the same priority. To do so, it assigns a virtual run<br>time to each task, creating a “lag” value that can be used to determine<br>whether a task has received its fair share of CPU time. In this way, a task<br>with a positive lag is owed CPU time, while a negative lag means the task<br>has exceeded its portion. EEVDF picks tasks with lag greater or equal to<br>zero and calculates a virtual deadline (VD) for each, selecting the task<br>with the earliest VD to execute next. It’s important to note that this<br>allows latency-sensitive tasks with shorter time slices to be prioritized,<br>which helps with their responsiveness.

There are ongoing discussions on how to manage lag, especially for sleeping<br>tasks; but at the time of writing EEVDF uses a “decaying” mechanism based<br>on virtual run time (VRT). This prevents tasks from exploiting the system<br>by sleeping briefly to reset their negative lag: when a task sleeps, it<br>remains on the run queue but marked for “deferred dequeue,” allowing its<br>lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag<br>reset. Finally, tasks can preempt others if their VD is earlier, and tasks<br>can request specific time slices using the new sched_setattr() system call,<br>which further facilitates the job of latency-sensitive applications.

REFERENCES¶

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564

[2] https://lore.kernel.org/lkml/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/

[3] https://lwn.net/Articles/969062/

[4] https://lwn.net/Articles/925371/

©The kernel development community.

Powered by Sphinx 5.3.0<br>& Alabaster 0.7.16

Page source