docs: scheduler: Start documenting the EEVDF scheduler
v2 cover docs: scheduler: Start documenting the EEVDF scheduler
I was in the process of updating the CFS documentation, as Sergio proposed, when I realized we don't have any EEVDF documentation to point to. I have started it. I know it isn't a lot of info about EEVDF in the doc, but (1) I wanted to get the ball rolling, and (2) I prefer to keep it light until we have a solid idea of how EEVDF will actually end up. This could take a while. When or if it stops being an option, we can revisit it.
Sergio, if you’d like to update the Spanish translations of CFS and add one for this new EEVDF doc, please go for it! ;)
Thanks,
Carlos
P.S.: Jon, I have triple-checked for compilation warnings, but if you
encounter any, please LMK the versions of your tools so I can match them moving forward.
Carlos:
docs: scheduler: Start documenting the EEVDF scheduler
---
Changelog:
v2: Move file within scheduler index. Remove incorrect subsection
numbering.
--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-design-CFS.rst | 10 +++-- Documentation/scheduler/sched-eevdf.rst | 44 ++++++++++++++++++++ 3 files changed, 51 insertions(+), 4 deletions(-) create mode 100644 Documentation/scheduler/sched-eevdf.rst
PATCH v2 1/1 docs: scheduler: Start documenting the EEVDF scheduler
Add some documentation regarding the newly introduced scheduler EEVDF.
--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-design-CFS.rst | 10 +++-- Documentation/scheduler/sched-eevdf.rst | 44 ++++++++++++++++++++ 3 files changed, 51 insertions(+), 4 deletions(-) create mode 100644 Documentation/scheduler/sched-eevdf.rst
Documentation/scheduler/index.rst +1 -0
@@ -12,6 +12,7 @@ Scheduler sched-bwc sched-deadline sched-design-CFS + sched-eevdf sched-domains sched-capacity sched-energy
Documentation/scheduler/sched-design-CFS.rst +6 -4
@@ -8,10 +8,12 @@ CFS Scheduler 1. OVERVIEW ============ -CFS stands for "Completely Fair Scheduler," and is the new "desktop" process -scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the -replacement for the previous vanilla scheduler's SCHED_OTHER interactivity -code. +CFS stands for "Completely Fair Scheduler," and is the "desktop" process +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When +originally merged, it was the replacement for the previous vanilla +scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room +for EEVDF, for which documentation can be found in +:ref:`sched_design_EEVDF`. 80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.
Documentation/scheduler/sched-eevdf.rst new file +44 -0
44 lines not on this page · raw message
Signature · 1 line
2.43.0
Quoted 97 lines · Carlos Bilbao
Add some documentation regarding the newly introduced scheduler EEVDF.
Reviewed-by Randy Dunlap <[email protected]>Tested-by Randy Dunlap <[email protected]>Signed-off-by Carlos Bilbao <[email protected]>--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-design-CFS.rst | 10 +++-- Documentation/scheduler/sched-eevdf.rst | 44 ++++++++++++++++++++ 3 files changed, 51 insertions(+), 4 deletions(-) create mode 100644 Documentation/scheduler/sched-eevdf.rstDocumentation/scheduler/index.rst +1
-0@@ -12,6 +12,7 @@ Scheduler sched-bwc sched-deadline sched-design-CFS + sched-eevdf sched-domains sched-capacity sched-energyDocumentation/scheduler/sched-design-CFS.rst +6
-4@@ -8,10 +8,12 @@ CFS Scheduler 1. OVERVIEW ============ -CFS stands for "Completely Fair Scheduler," and is the new "desktop" process -scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the -replacement for the previous vanilla scheduler's SCHED_OTHER interactivity -code. +CFS stands for "Completely Fair Scheduler," and is the "desktop" process +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When +originally merged, it was the replacement for the previous vanilla +scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room +for EEVDF, for which documentation can be found in +:ref:`sched_design_EEVDF`. 80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.Documentation/scheduler/sched-eevdf.rst new file +44
-1@@ -0,0 +1,44 @@ +.. _sched_design_EEVDF: + +=============== +EEVDF Scheduler +=============== + +The "Earliest Eligible Virtual Deadline First" (EEVDF) was first introduced +in a scientific publication in 1995 [1]. The Linux kernel began +transitioning to EEVDF in version 6.6 (as a new option in 2024), moving +away from the earlier Completely Fair Scheduler (CFS) in favor of a version +of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information +regarding CFS can be found in :ref:`sched_design_CFS`. + +Similarly to CFS, EEVDF aims to distribute CPU time equally among all +runnable tasks with the same priority. To do so, it assigns a virtual run +time to each task, creating a "lag" value that can be used to determine +whether a task has received its fair share of CPU time. In this way, a task +with a positive lag is owed CPU time, while a negative lag means the task +has exceeded its portion. EEVDF picks tasks with lag greater or equal to +zero and calculates a virtual deadline (VD) for each, selecting the task +with the earliest VD to execute next. It's important to note that this +allows latency-sensitive tasks with shorter time slices to be prioritized, +which helps with their responsiveness. + +There are ongoing discussions on how to manage lag, especially for sleeping +tasks; but at the time of writing EEVDF uses a "decaying" mechanism based +on virtual run time (VRT). This prevents tasks from exploiting the system +by sleeping briefly to reset their negative lag: when a task sleeps, it +remains on the run queue but marked for "deferred dequeue," allowing its +lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag +reset. Finally, tasks can preempt others if their VD is earlier, and tasks +can request specific time slices using the new sched_setattr() system call, +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/[email protected]/ + +[3] https://lwn.net/Articles/969062/ + +[4] https://lwn.net/Articles/925371/ --
Quoted 2 lines
2.43.0
Quoted 85 lines · Carlos Bilbao
Add some documentation regarding the newly introduced scheduler EEVDF.
Reviewed-by Randy Dunlap <[email protected]>Tested-by Randy Dunlap <[email protected]>Signed-off-by Carlos Bilbao <[email protected]>--- Documentation/scheduler/index.rst | 1 + Documentation/scheduler/sched-design-CFS.rst | 10 +++-- Documentation/scheduler/sched-eevdf.rst | 44 ++++++++++++++++++++ 3 files changed, 51 insertions(+), 4 deletions(-) create mode 100644 Documentation/scheduler/sched-eevdf.rstDocumentation/scheduler/index.rst +1
-0@@ -12,6 +12,7 @@ Scheduler sched-bwc sched-deadline sched-design-CFS + sched-eevdf sched-domains sched-capacity sched-energyDocumentation/scheduler/sched-design-CFS.rst +6
-4@@ -8,10 +8,12 @@ CFS Scheduler 1. OVERVIEW ============ -CFS stands for "Completely Fair Scheduler," and is the new "desktop" process -scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the -replacement for the previous vanilla scheduler's SCHED_OTHER interactivity -code. +CFS stands for "Completely Fair Scheduler," and is the "desktop" process +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When +originally merged, it was the replacement for the previous vanilla +scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room +for EEVDF, for which documentation can be found in +:ref:`sched_design_EEVDF`. 80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.Documentation/scheduler/sched-eevdf.rst new file +34
-0@@ -0,0 +1,44 @@ +.. _sched_design_EEVDF: + +=============== +EEVDF Scheduler +=============== + +The "Earliest Eligible Virtual Deadline First" (EEVDF) was first introduced +in a scientific publication in 1995 [1]. The Linux kernel began +transitioning to EEVDF in version 6.6 (as a new option in 2024), moving +away from the earlier Completely Fair Scheduler (CFS) in favor of a version +of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information +regarding CFS can be found in :ref:`sched_design_CFS`. + +Similarly to CFS, EEVDF aims to distribute CPU time equally among all +runnable tasks with the same priority. To do so, it assigns a virtual run +time to each task, creating a "lag" value that can be used to determine +whether a task has received its fair share of CPU time. In this way, a task +with a positive lag is owed CPU time, while a negative lag means the task +has exceeded its portion. EEVDF picks tasks with lag greater or equal to +zero and calculates a virtual deadline (VD) for each, selecting the task +with the earliest VD to execute next. It's important to note that this +allows latency-sensitive tasks with shorter time slices to be prioritized, +which helps with their responsiveness. + +There are ongoing discussions on how to manage lag, especially for sleeping +tasks; but at the time of writing EEVDF uses a "decaying" mechanism based +on virtual run time (VRT). This prevents tasks from exploiting the system +by sleeping briefly to reset their negative lag: when a task sleeps, it +remains on the run queue but marked for "deferred dequeue," allowing its +lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag +reset. Finally, tasks can preempt others if their VD is earlier, and tasks +can request specific time slices using the new sched_setattr() system call, +which further facilitates the job of latency-sensitive applications. +
Documentation/scheduler/sched-eevdf.rst line 44
Quoted 10 lines
Documentation/scheduler/sched-eevdf.rst new file +10
-0+REFERENCES +========== + +[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564 + +[2] https://lore.kernel.org/lkml/[email protected]/ + +[3] https://lwn.net/Articles/969062/ + +[4] https://lwn.net/Articles/925371/
LGTM.
Signature · 2 lines
Thanks, Avadhut Naik
Jonathan Corbet
maintainerQuoted 1 line · Carlos Bilbao
Add some documentation regarding the newly introduced scheduler EEVDF.
A nit, but one I wish more people would make note of...
[...]
Quoted 6 lines
Documentation/scheduler/sched-design-CFS.rst +0
-0@@ -8,10 +8,12 @@ CFS Scheduler 1. OVERVIEW ============
Documentation/scheduler/sched-design-CFS.rst CFS Scheduler · line 16
Quoted 10 lines
Documentation/scheduler/sched-design-CFS.rst +6
-4-CFS stands for "Completely Fair Scheduler," and is the new "desktop" process -scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the -replacement for the previous vanilla scheduler's SCHED_OTHER interactivity -code. +CFS stands for "Completely Fair Scheduler," and is the "desktop" process +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When +originally merged, it was the replacement for the previous vanilla +scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room +for EEVDF, for which documentation can be found in +:ref:`sched_design_EEVDF`.
If, here, you just say "can be found in Documentation/scheduler/sched-eevdf.rst", the right cross-reference will be created and ...
Documentation/scheduler/sched-eevdf.rst line 1
Quoted 9 lines
Documentation/scheduler/sched-design-CFS.rst +0
-080% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.Documentation/scheduler/sched-eevdf.rst new file +1
-0@@ -0,0 +1,44 @@ +.. _sched_design_EEVDF:
...you can take out this unnecessary label.
Thanks,
jon
Quoted 27 lines · Jonathan Corbet
Quoted 1 line · Carlos Bilbao
Add some documentation regarding the newly introduced scheduler EEVDF.
A nit, but one I wish more people would make note of...
[...]
Quoted 6 lines
Documentation/scheduler/sched-design-CFS.rst +0
-0@@ -8,10 +8,12 @@ CFS Scheduler 1. OVERVIEW ============Documentation/scheduler/sched-design-CFS.rst CFS Scheduler · line 16
Quoted 10 lines
Documentation/scheduler/sched-design-CFS.rst +6
-4-CFS stands for "Completely Fair Scheduler," and is the new "desktop" process -scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. It is the -replacement for the previous vanilla scheduler's SCHED_OTHER interactivity -code. +CFS stands for "Completely Fair Scheduler," and is the "desktop" process +scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When +originally merged, it was the replacement for the previous vanilla +scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room +for EEVDF, for which documentation can be found in +:ref:`sched_design_EEVDF`.If, here, you just say "can be found in
Documentation/scheduler/sched-eevdf.rst", the right cross-reference will be created and ...
Quoted 10 lines
Documentation/scheduler/sched-eevdf.rst line 1
Quoted 9 lines
Documentation/scheduler/sched-design-CFS.rst +0
-080% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.Documentation/scheduler/sched-eevdf.rst new file +1
-0@@ -0,0 +1,44 @@ +.. _sched_design_EEVDF:...you can take out this unnecessary label.
Love it! Labels are a source of warnings.
Sending v3 now.
Quoted 4 lines
Thanks,
jon
Thanks,
Carlos