Re: [PATCH v3 1/4] Documentation/scheduler/sched-deadline.txt: fix terminology and improve clarity

Henrik Austad
2014-09-02T21:10:28Z

On Thu, Aug 28, 2014 at 11:00:26AM +0100, Juri Lelli wrote:
> From: Luca Abeni <luca.abeni@unitn.it>
>
> Several small changes regarding SCHED_DEADLINE documentation that fix
> terminology and improve clarity and readability:
>
> - "current runtime" becomes "remaining runtime"
>
> - readablity of an equation is improved by introducing more spacing
>
> - clarify when admission control will certainly fail
>
> - new URL for CBS technical report
>
> - substitue "smallest" with "closest"

I'm tempted to say "earliest" (being part of the algorithm's name and all
;)

>
> Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
> Signed-off-by: Juri Lelli <juri.lelli@arm.com>
> Cc: Randy Dunlap <rdunlap@infradead.org>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Henrik Austad <henrik@austad.us>
> Cc: Dario Faggioli <raistlin@linux.it>
> Cc: Juri Lelli <juri.lelli@gmail.com>
> Cc: linux-doc@vger.kernel.org
> Cc: linux-kernel@vger.kernel.org
> ---
> Documentation/scheduler/sched-deadline.txt | 32 ++++++++++++++++--------------
> 1 file changed, 17 insertions(+), 15 deletions(-)
>
> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
> index 18adc92..dce6d63 100644
> --- a/Documentation/scheduler/sched-deadline.txt
> +++ b/Documentation/scheduler/sched-deadline.txt
> @@ -45,14 +45,14 @@ CONTENTS
> every time the task wakes up, the scheduler computes a "scheduling deadline"
> consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then
> scheduled using EDF[1] on these scheduling deadlines (the task with the
> - smallest scheduling deadline is selected for execution). Notice that this
> + closest scheduling deadline is selected for execution). Notice that this
> guaranteed is respected if a proper "admission control" strategy (see Section
> "4. Bandwidth management") is used.
>
> Summing up, the CBS[2,3] algorithms assigns scheduling deadlines to tasks so
> that each task runs for at most its runtime every period, avoiding any
> interference between different tasks (bandwidth isolation), while the EDF[1]
> - algorithm selects the task with the smallest scheduling deadline as the one
> + algorithm selects the task with the closest scheduling deadline as the one
> to be executed first. Thanks to this feature, also tasks that do not

s/first/next/

Also, next sentence does not make much sense, I would drop the also;

"Thanks to this feature, tasks that do not strictly comply with the ..."

> strictly comply with the "traditional" real-time task model (see Section 3)
> can effectively use the new policy.
> @@ -64,45 +64,45 @@ CONTENTS
> "deadline", and "period" parameters;
>
> - The state of the task is described by a "scheduling deadline", and
> - a "current runtime". These two parameters are initially set to 0;
> + a "remaining runtime". These two parameters are initially set to 0;
>
> - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
> the scheduler checks if
>
> - current runtime runtime
> - ---------------------------------- > ----------------
> - scheduling deadline - current time period
> + remaining runtime runtime
> + ---------------------------------- > ---------
> + scheduling deadline - current time period
>
> then, if the scheduling deadline is smaller than the current time, or
> this condition is verified, the scheduling deadline and the
> - current budget are re-initialised as
> + remaining runtime are re-initialised as
>
> scheduling deadline = current time + deadline
> - current runtime = runtime
> + remaining runtime = runtime
>
> - otherwise, the scheduling deadline and the current runtime are
> + otherwise, the scheduling deadline and the remaining runtime are
> left unchanged;
>
> - When a SCHED_DEADLINE task executes for an amount of time t, its
> - current runtime is decreased as
> + remaining runtime is decreased as
>
> - current runtime = current runtime - t
> + remaining runtime = remaining runtime - t
>
> (technically, the runtime is decreased at every tick, or when the
> task is descheduled / preempted);
>
> - - When the current runtime becomes less or equal than 0, the task is
> + - When the remaining runtime becomes less or equal than 0, the task is
> said to be "throttled" (also known as "depleted" in real-time literature)
> and cannot be scheduled until its scheduling deadline. The "replenishment
> time" for this task (see next item) is set to be equal to the current
> value of the scheduling deadline;
>
> - When the current time is equal to the replenishment time of a
> - throttled task, the scheduling deadline and the current runtime are
> + throttled task, the scheduling deadline and the remaining runtime are
> updated as
>
> scheduling deadline = scheduling deadline + period
> - current runtime = current runtime + runtime
> + remaining runtime = remaining runtime + runtime
>
>
> 3. Scheduling Real-Time Tasks
> @@ -147,6 +147,8 @@ CONTENTS
> and the absolute deadlines (d_j) coincide, so a proper admission control
> allows to respect the jobs' absolute deadlines for this task (this is what is
> called "hard schedulability property" and is an extension of Lemma 1 of [2]).
> + Notice that if runtime > deadline the admission control will surely reject
> + this task, as it is not possible to respect its temporal constraints.
>
> References:
> 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
> @@ -156,7 +158,7 @@ CONTENTS
> Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
> Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
> 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
> - Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps
> + Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
>
> 4. Bandwidth management
> =======================
> --
> 2.0.4

Apart from the minor nitpick, it looks good!

--
Henrik