1=============== 2EEVDF Scheduler 3=============== 4 5The "Earliest Eligible Virtual Deadline First" (EEVDF) was first introduced 6in a scientific publication in 1995 [1]. The Linux kernel began 7transitioning to EEVDF in version 6.6 (as a new option in 2024), moving 8away from the earlier Completely Fair Scheduler (CFS) in favor of a version 9of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information 10regarding CFS can be found in 11Documentation/scheduler/sched-design-CFS.rst. 12 13Similarly to CFS, EEVDF aims to distribute CPU time equally among all 14runnable tasks with the same priority. To do so, it assigns a virtual run 15time to each task, creating a "lag" value that can be used to determine 16whether a task has received its fair share of CPU time. In this way, a task 17with a positive lag is owed CPU time, while a negative lag means the task 18has exceeded its portion. EEVDF picks tasks with lag greater or equal to 19zero and calculates a virtual deadline (VD) for each, selecting the task 20with the earliest VD to execute next. It's important to note that this 21allows latency-sensitive tasks with shorter time slices to be prioritized, 22which helps with their responsiveness. 23 24There are ongoing discussions on how to manage lag, especially for sleeping 25tasks; but at the time of writing EEVDF uses a "decaying" mechanism based 26on virtual run time (VRT). This prevents tasks from exploiting the system 27by sleeping briefly to reset their negative lag: when a task sleeps, it 28remains on the run queue but marked for "deferred dequeue," allowing its 29lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag 30reset. Finally, tasks can preempt others if their VD is earlier, and tasks 31can request specific time slices using the new sched_setattr() system call, 32which further facilitates the job of latency-sensitive applications. 33 34REFERENCES 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/ 44