Skip to contentSkip to conversation

docs: scheduler: Start documenting the EEVDF scheduler

PATCH Superseded Carlos Bilbao 4 participants 6 messages Jul 13, 2024 – Jul 20, 2024 Documentation

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 43bd8a145b7a..1f2942c4d14b 100644
@@ -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
index bc1e507269c6..b703c6dcb3cd 100644
@@ -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
Reviewed-by on v2 1/1
#2 lore raw
Quoted 97 lines · Carlos Bilbao

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
index 43bd8a145b7a..1f2942c4d14b 100644
@@ -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
index bc1e507269c6..b703c6dcb3cd 100644
@@ -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
new file mode 100644
index 000000000000..019327da333a
@@ -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

Reviewed-by Avadhut Naik on v2 1/1
#3 lore raw
In reply to Carlos Bilbao
Quoted 85 lines · Carlos Bilbao

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
index 43bd8a145b7a..1f2942c4d14b 100644
@@ -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
index bc1e507269c6..b703c6dcb3cd 100644
@@ -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
new file mode 100644
index 000000000000..019327da333a
@@ -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
maintainer
#4 lore raw
In reply to Carlos Bilbao
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 ...

Documentation/scheduler/sched-eevdf.rst line 1

Quoted 9 lines
Documentation/scheduler/sched-design-CFS.rst +0 -0
 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 +1 -0
new file mode 100644
index 000000000000..019327da333a
@@ -0,0 +1,44 @@
+.. _sched_design_EEVDF:

...you can take out this unnecessary label.

Thanks,

jon

#5 lore raw
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 -0
 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 +1 -0
new file mode 100644
index 000000000000..019327da333a
@@ -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