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