[PATCH v3 5/5] Documentation: sched/deadline: Update GRUB description

Vineeth Pillai
2023-05-15T02:57:59Z

Update the details of GRUB to reflect the updated logic.

Signed-off-by: Vineeth Pillai (Google) <vineeth@bitbyteword.org>
---
Documentation/scheduler/sched-deadline.rst | 28 ++++++++++++++--------
1 file changed, 18 insertions(+), 10 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.rst b/Documentation/scheduler/sched-deadline.rst
index 9d9be52f221a..b45c9dde6671 100644
--- a/Documentation/scheduler/sched-deadline.rst
+++ b/Documentation/scheduler/sched-deadline.rst
@@ -195,11 +195,15 @@ Deadline Task Scheduling
its utilization is added to the active utilization of the runqueue where
it has been enqueued.

- For each runqueue, the algorithm GRUB keeps track of two different bandwidths:
+ For each runqueue, the algorithm GRUB keeps track of three different bandwidths:

- Active bandwidth (running_bw): this is the sum of the bandwidths of all
tasks in active state (i.e., ActiveContending or ActiveNonContending);

+ - Active bandwidth of SCHED_FLAG_RECLAIM tasks(reclaim_bw): this is the sum of
+ bandwidth of all tasks in active state which participates in GRUB. This is a
+ subset of running_bw and is needed for reclaimable bandwidth calculation.
+
- Total bandwidth (this_bw): this is the sum of all tasks "belonging" to the
runqueue, including the tasks in Inactive state.

@@ -208,21 +212,25 @@ Deadline Task Scheduling
It does so by decrementing the runtime of the executing task Ti at a pace equal
to

- dq = -max{ Ui / Umax, (1 - Uinact - Uextra) } dt
+ dq = -(max{Ui, (Umax_reclaim - Uinact - Uextra)} / Umax_reclaim) dt

where:
-
- Ui is the bandwidth of task Ti;
- Umax is the maximum reclaimable utilization (subjected to RT throttling
limits);
+ - Umax_reclaim is the maximum allowable bandwidth for all reclaimable tasks
+ in the runqueue. If there are only SCHED_FLAG_RECLAIM tasks, then
+ Umax_reclaim = Umax;
+ Otherwise Umax_reclaim = (Umax - running_bw + reclaim_bw);
- Uinact is the (per runqueue) inactive utilization, computed as
- (this_bq - running_bw);
+ (this_bw - running_bw);
- Uextra is the (per runqueue) extra reclaimable utilization
- (subjected to RT throttling limits).
+ (subjected to RT throttling limits);

- Let's now see a trivial example of two deadline tasks with runtime equal
- to 4 and period equal to 8 (i.e., bandwidth equal to 0.5)::
+ Let's now see a trivial example of two SCHED_FLAG_RECLAIM tasks with runtime
+ equal to 4 and period equal to 8 (i.e., bandwidth equal to 0.5). Tasks are
+ allowed to use the whole cpu(Umax = Umax_reclaim = 1)::

A Task T1
|
@@ -244,7 +252,7 @@ Deadline Task Scheduling
0 1 2 3 4 5 6 7 8

- A running_bw
+ A reclaim_bw
|
1 ----------------- ------
| | |
@@ -272,7 +280,7 @@ Deadline Task Scheduling

This is the 0-lag time for Task T1. Since it didn't woken up in the
meantime, it enters the Inactive state. Its bandwidth is removed from
- running_bw.
+ running_bw and reclaim_bw.
Task T2 continues its execution. However, its runtime is now decreased as
dq = - 0.5 dt because Uinact = 0.5.
Task T2 therefore reclaims the bandwidth unused by Task T1.
@@ -280,7 +288,7 @@ Deadline Task Scheduling
- Time t = 8:

Task T1 wakes up. It enters the ActiveContending state again, and the
- running_bw is incremented.
+ running_bw and reclaim_bw are incremented.

2.3 Energy-aware scheduling
--
2.40.1