Documentation/scheduler/sched-eevdf.rst

   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/