[PATCH] sched/docs: Rewrite sched-eevdf.rst

[PATCH] sched/docs: Rewrite sched-eevdf.rst

[Kayra Cizmeci]

The current sched-eevdf.rst doesn't explain most of
the concepts in EEVDF.

Describe the concepts (V, vruntime, deadline, eligibility,
lag, etc.).

Signed-off-by: Kayra Cizmeci <kayracizmeci@gmail.com>
---
Hi!

I tried to rewrite this whole sched-eevdf.rst thing.

The current sched-eevdf.rst doesn't explain most of the concepts as
the commit says too.

There are some other little issues too, like the second link shows a
random reply instead of the cover letter.

Hope I did not miss anything :-).

 Documentation/scheduler/sched-eevdf.rst | 194 +++++++++++++++++++-----
 1 file changed, 155 insertions(+), 39 deletions(-)

diff --git a/Documentation/scheduler/sched-eevdf.rst b/Documentation/scheduler/sched-eevdf.rst
index 83efe7c0a30d..5c74e3b5672a 100644
--- a/Documentation/scheduler/sched-eevdf.rst
+++ b/Documentation/scheduler/sched-eevdf.rst
@@ -1,43 +1,159 @@
+.. SPDX-License-Identifier: GPL-2.0
+
 ===============
 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
-Documentation/scheduler/sched-design-CFS.rst.
-
-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/
+Earliest Eligible Virtual Deadline First, or EEVDF for short, was
+first introduced in a scientific article that was written by Ion Stoica
+and Hussein Abdel-Wahab in 1995 [1]_.
+
+Then Peter Zijlstra suggested it as a replacement for CFS
+(Completely Fair Scheduler) [2]_. First parts of it got merged into Linux in 6.6.
+
+Our objective is to select the task with the earliest
+deadline from the tasks that are eligible.
+
+
+Core Basics
+============
+
+Every task has its own *weight*, derived from its nice value.
+
+The bigger the *weight*, the slower the *vruntime* increases.
+The slower the *vruntime* increases, the easier it is for a task to be eligible.
+
+
+Formula for virtual runtime is::
+
+   (delta * NICE_0_LOAD) / weight
+
+*delta* is calculated by this formula::
+
+    now - exec_start
+
+*exec_start* is the last time that we accounted the task.
+
+And every runqueue has its own average virtual runtime. We'll call it *V*.
+
+Formula for *V* is::
+
+     Sum(weight * vruntime) / Sum(weight)
+
+
+Eligibility
+~~~~~~~~~~~~
+
+For a task to be considered eligible, its vruntime must be smaller than or
+equal to *V*.
+
+
+Deadline
+~~~~~~~~~~~~
+
+Deadline is like a point on vruntime. We calculate it by::
+
+    vruntime + ((slice * NICE_0_LOAD) / weight)
+
+*slice* is usually equal to sysctl_sched_base_slice,
+which is 0.70 ms by default. It's the time the task requested to run.
+
+However, a task doesn't have to run exactly as its *slice* says.
+It can get preempted, it can sleep, etc.
+But we will reschedule when the task's *vruntime* gets equal to its *deadline*,
+or passes it. Or at least when we realize it did.
+
+Examples
+~~~~~~~~
+
+==== ====== ======== ========
+Task weight vruntime deadline
+==== ====== ======== ========
+TA    1     7        8
+TB    2     5        10
+TC    3     6        9
+==== ====== ======== ========
+
+Here, *V* is equal to 5.83.
+
+The only task that is eligible is TB. It has the farthest deadline
+but the other competitors T{A,C} are not eligible, so TB gets picked.
+
+Sleep Handling
+==============
+
+The problem with sleeping tasks is that their runqueue's *V* continues to increase/decrease
+while they are sleeping. Normally, sleeping tasks leave the runqueue, so we need
+to save their *vruntime*'s position relative to *V* in order to place them correctly.
+
+(Delayed Dequeue is an exception to that, as explained below.)
+
+We call that *lag*::
+
+    V - vruntime
+
+Example:
+
+==== ====== ========
+Task weight vruntime
+==== ====== ========
+TA    1     1
+TB    1     3
+==== ====== ========
+
+Right now, *V* is 2, TA's *lag* is 1, TB's *lag* is -1.
+
+Now let's say TB sleeps and in the meantime TA's *vruntime* gets to 12.
+If we try to place TB with::
+
+    V - lag
+
+It equals 13, so *V* gets to 12.5. So now TB's *lag* is -0.5 instead of -1.
+
+So to fix this, we use a formula while placing lag::
+
+    ((Sum(weight) + weight) * lag) / Sum(weight)
+
+
+Here, *weight* is our own weight, and Sum(weight) is the sum of all of the tasks weights in the runqueue,
+in our case both are equal to 1.
+
+Now let's try the same case with this formula:
+
+*lag* equals -2, *vruntime* of TB equals 14, so now *V* equals 13
+and both TB's lag and TA's *lag* are correct.
+
+Delayed Dequeue
+~~~~~~~~~~~~~~~~
+
+Negative *lag* means that the task is in debt to its runqueue.
+We don't want to carry a task's negative *lag* until eternity.
+
+Because while a task sleeps, the other tasks in the runqueue work.
+And if the task were not sleeping its *lag* would increase since
+it was paying its debt by not working.
+
+Sleep is similar to this, the only problem is that normally while sleeping
+we wouldn't be on the runqueue. Since we are sleeping and we don't want
+to be chosen. So our debt wouldn't be paid.
+
+With Delayed Dequeue, if a task has a negative lag and if it's going to sleep,
+we don't immediately dequeue it.
+
+It stays in the runqueue, as if it's not sleeping. However, because it has negative lag
+it's not eligible.
+
+A delayed dequeue of a task can end in 2 ways:
+
+1. When the task's debt is paid fully, (*lag* >= 0) it becomes eligible. So it can get picked.
+   When a delayed task gets picked, we really remove it from the runqueue.
+
+2. If the delayed task wakes up before it gets picked, we just clear the delayed
+   status and the task stays in the runqueue.
+
+
+References
+============
+
+.. [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564
+.. [2] https://lore.kernel.org/lkml/20230328092622.062917921@infradead.org/
-- 
2.53.0