1 =============== 1 ===============
2 EEVDF Scheduler 2 EEVDF Scheduler
3 =============== 3 ===============
4 4
5 The "Earliest Eligible Virtual Deadline First" 5 The "Earliest Eligible Virtual Deadline First" (EEVDF) was first introduced
6 in a scientific publication in 1995 [1]. The L 6 in a scientific publication in 1995 [1]. The Linux kernel began
7 transitioning to EEVDF in version 6.6 (as a ne 7 transitioning to EEVDF in version 6.6 (as a new option in 2024), moving
8 away from the earlier Completely Fair Schedule 8 away from the earlier Completely Fair Scheduler (CFS) in favor of a version
9 of EEVDF proposed by Peter Zijlstra in 2023 [2 9 of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information
10 regarding CFS can be found in 10 regarding CFS can be found in
11 Documentation/scheduler/sched-design-CFS.rst. 11 Documentation/scheduler/sched-design-CFS.rst.
12 12
13 Similarly to CFS, EEVDF aims to distribute CPU 13 Similarly to CFS, EEVDF aims to distribute CPU time equally among all
14 runnable tasks with the same priority. To do s 14 runnable tasks with the same priority. To do so, it assigns a virtual run
15 time to each task, creating a "lag" value that 15 time to each task, creating a "lag" value that can be used to determine
16 whether a task has received its fair share of 16 whether a task has received its fair share of CPU time. In this way, a task
17 with a positive lag is owed CPU time, while a 17 with a positive lag is owed CPU time, while a negative lag means the task
18 has exceeded its portion. EEVDF picks tasks wi 18 has exceeded its portion. EEVDF picks tasks with lag greater or equal to
19 zero and calculates a virtual deadline (VD) fo 19 zero and calculates a virtual deadline (VD) for each, selecting the task
20 with the earliest VD to execute next. It's imp 20 with the earliest VD to execute next. It's important to note that this
21 allows latency-sensitive tasks with shorter ti 21 allows latency-sensitive tasks with shorter time slices to be prioritized,
22 which helps with their responsiveness. 22 which helps with their responsiveness.
23 23
24 There are ongoing discussions on how to manage 24 There are ongoing discussions on how to manage lag, especially for sleeping
25 tasks; but at the time of writing EEVDF uses a 25 tasks; but at the time of writing EEVDF uses a "decaying" mechanism based
26 on virtual run time (VRT). This prevents tasks 26 on virtual run time (VRT). This prevents tasks from exploiting the system
27 by sleeping briefly to reset their negative la 27 by sleeping briefly to reset their negative lag: when a task sleeps, it
28 remains on the run queue but marked for "defer 28 remains on the run queue but marked for "deferred dequeue," allowing its
29 lag to decay over VRT. Hence, long-sleeping ta 29 lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag
30 reset. Finally, tasks can preempt others if th 30 reset. Finally, tasks can preempt others if their VD is earlier, and tasks
31 can request specific time slices using the new 31 can request specific time slices using the new sched_setattr() system call,
32 which further facilitates the job of latency-s 32 which further facilitates the job of latency-sensitive applications.
33 33
34 REFERENCES 34 REFERENCES
35 ========== 35 ==========
36 36
37 [1] https://citeseerx.ist.psu.edu/document?rep 37 [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564
38 38
39 [2] https://lore.kernel.org/lkml/a79014e6-ea83 39 [2] https://lore.kernel.org/lkml/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/
40 40
41 [3] https://lwn.net/Articles/969062/ 41 [3] https://lwn.net/Articles/969062/
42 42
43 [4] https://lwn.net/Articles/925371/ 43 [4] https://lwn.net/Articles/925371/
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.