[PATCH v2 0/1] docs: scheduler: Start documenting the EEVDF scheduler

[PATCH v2 0/1] docs: scheduler: Start documenting the EEVDF scheduler

[Carlos Bilbao]

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

[Carlos Bilbao]

Add some documentation regarding the newly introduced scheduler EEVDF.

Reviewed-by: Randy Dunlap <rdunlap@infradead.org>
Tested-by: Randy Dunlap <rdunlap@infradead.org>
Signed-off-by: Carlos Bilbao <carlos.bilbao.osdev@gmail.com>
---
 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

diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst
index 43bd8a145b7a..1f2942c4d14b 100644
--- a/Documentation/scheduler/index.rst
+++ b/Documentation/scheduler/index.rst
@@ -12,6 +12,7 @@ Scheduler
     sched-bwc
     sched-deadline
     sched-design-CFS
+    sched-eevdf
     sched-domains
     sched-capacity
     sched-energy
diff --git a/Documentation/scheduler/sched-design-CFS.rst b/Documentation/scheduler/sched-design-CFS.rst
index bc1e507269c6..b703c6dcb3cd 100644
--- a/Documentation/scheduler/sched-design-CFS.rst
+++ b/Documentation/scheduler/sched-design-CFS.rst
@@ -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.
diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
new file mode 100644
index 000000000000..019327da333a
--- /dev/null
+++ b/Documentation/scheduler/sched-eevdf.rst
@@ -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/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/
+
+[3] https://lwn.net/Articles/969062/
+
+[4] https://lwn.net/Articles/925371/
-- 
2.43.0

Re: [PATCH v2 1/1] docs: scheduler: Start documenting the EEVDF scheduler

[Sergio González Collado]

On Sat, 13 Jul 2024 at 16:05, Carlos Bilbao
<carlos.bilbao.osdev@gmail.com> wrote:
>
> Add some documentation regarding the newly introduced scheduler EEVDF.
>
> Reviewed-by: Randy Dunlap <rdunlap@infradead.org>
> Tested-by: Randy Dunlap <rdunlap@infradead.org>
> Signed-off-by: Carlos Bilbao <carlos.bilbao.osdev@gmail.com>
> ---
>  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
>
> diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst
> index 43bd8a145b7a..1f2942c4d14b 100644
> --- a/Documentation/scheduler/index.rst
> +++ b/Documentation/scheduler/index.rst
> @@ -12,6 +12,7 @@ Scheduler
>      sched-bwc
>      sched-deadline
>      sched-design-CFS
> +    sched-eevdf
>      sched-domains
>      sched-capacity
>      sched-energy
> diff --git a/Documentation/scheduler/sched-design-CFS.rst b/Documentation/scheduler/sched-design-CFS.rst
> index bc1e507269c6..b703c6dcb3cd 100644
> --- a/Documentation/scheduler/sched-design-CFS.rst
> +++ b/Documentation/scheduler/sched-design-CFS.rst
> @@ -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.
> diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
> new file mode 100644
> index 000000000000..019327da333a
> --- /dev/null
> +++ b/Documentation/scheduler/sched-eevdf.rst
> @@ -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/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/
> +
> +[3] https://lwn.net/Articles/969062/
> +
> +[4] https://lwn.net/Articles/925371/
> --
> 2.43.0
>

Reviewed-by: Sergio González Collado <sergio.collado@gmail.com>

Re: [PATCH v2 1/1] docs: scheduler: Start documenting the EEVDF scheduler

[Naik, Avadhut]

On 7/13/2024 09:04, Carlos Bilbao wrote:
> Add some documentation regarding the newly introduced scheduler EEVDF.
> 
> Reviewed-by: Randy Dunlap <rdunlap@infradead.org>
> Tested-by: Randy Dunlap <rdunlap@infradead.org>
> Signed-off-by: Carlos Bilbao <carlos.bilbao.osdev@gmail.com>
> ---
>  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
> 
> diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst
> index 43bd8a145b7a..1f2942c4d14b 100644
> --- a/Documentation/scheduler/index.rst
> +++ b/Documentation/scheduler/index.rst
> @@ -12,6 +12,7 @@ Scheduler
>      sched-bwc
>      sched-deadline
>      sched-design-CFS
> +    sched-eevdf
>      sched-domains
>      sched-capacity
>      sched-energy
> diff --git a/Documentation/scheduler/sched-design-CFS.rst b/Documentation/scheduler/sched-design-CFS.rst
> index bc1e507269c6..b703c6dcb3cd 100644
> --- a/Documentation/scheduler/sched-design-CFS.rst
> +++ b/Documentation/scheduler/sched-design-CFS.rst
> @@ -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.
> diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
> new file mode 100644
> index 000000000000..019327da333a
> --- /dev/null
> +++ b/Documentation/scheduler/sched-eevdf.rst
> @@ -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/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/
> +
> +[3] https://lwn.net/Articles/969062/
> +
> +[4] https://lwn.net/Articles/925371/

LGTM.

Reviewed-by: Avadhut Naik <avadhut.naik@amd.com>

-- 
Thanks,
Avadhut Naik

Re: [PATCH v2 1/1] docs: scheduler: Start documenting the EEVDF scheduler

[Jonathan Corbet]

Carlos Bilbao <carlos.bilbao.osdev@gmail.com> writes:

> Add some documentation regarding the newly introduced scheduler EEVDF.

A nit, but one I wish more people would make note of...

[...]

> --- a/Documentation/scheduler/sched-design-CFS.rst
> +++ b/Documentation/scheduler/sched-design-CFS.rst
> @@ -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`.

If, here, you just say "can be found in
Documentation/scheduler/sched-eevdf.rst", the right cross-reference will
be created and ...

>  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.
> diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
> new file mode 100644
> index 000000000000..019327da333a
> --- /dev/null
> +++ b/Documentation/scheduler/sched-eevdf.rst
> @@ -0,0 +1,44 @@
> +.. _sched_design_EEVDF:

...you can take out this unnecessary label.

Thanks,

jon

Re: [PATCH v2 1/1] docs: scheduler: Start documenting the EEVDF scheduler

[Carlos Bilbao]

On 7/16/24 11:45, Jonathan Corbet wrote:

> Carlos Bilbao <carlos.bilbao.osdev@gmail.com> writes:
>
>> Add some documentation regarding the newly introduced scheduler EEVDF.
> A nit, but one I wish more people would make note of...
>
> [...]
>
>> --- a/Documentation/scheduler/sched-design-CFS.rst
>> +++ b/Documentation/scheduler/sched-design-CFS.rst
>> @@ -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`.
> If, here, you just say "can be found in
> Documentation/scheduler/sched-eevdf.rst", the right cross-reference will
> be created and ...
>
>>  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.
>> diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
>> new file mode 100644
>> index 000000000000..019327da333a
>> --- /dev/null
>> +++ b/Documentation/scheduler/sched-eevdf.rst
>> @@ -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.


>
> Thanks,
>
> jon


Thanks,

Carlos