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

[Henrik Austad]

On Thu, Aug 28, 2014 at 11:00:26AM +0100, Juri Lelli wrote:
> From: Luca Abeni <luca.abeni@xxxxxxxx>
> 
> 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@xxxxxxxx>
> Signed-off-by: Juri Lelli <juri.lelli@xxxxxxx>
> Cc: Randy Dunlap <rdunlap@xxxxxxxxxxxxx>
> Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> Cc: Ingo Molnar <mingo@xxxxxxxxxx>
> Cc: Henrik Austad <henrik@xxxxxxxxx>
> Cc: Dario Faggioli <raistlin@xxxxxxxx>
> Cc: Juri Lelli <juri.lelli@xxxxxxxxx>
> Cc: linux-doc@xxxxxxxxxxxxxxx
> Cc: linux-kernel@xxxxxxxxxxxxxxx
> ---
>  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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/