Re: [RFC 4/4] Documentation/scheduler/sched-deadline.txt: add some references

[Luca Abeni <luca.abeni@unitn.it>]

Hi Henrik,

On 04/09/2015 11:39 AM, Henrik Austad wrote:
[...]
>> - SCHED_DEADLINE can be used to schedule real-time tasks guaranteeing that
>> - the jobs' deadlines of a task are respected. In order to do this, a task
>> - must be scheduled by setting:
>> + utilisations or densities: it can be shown that even if D_i = P_i task
>> + sets with utilisations slightly larger than 1 can miss deadlines regardless
>> + of the number of CPUs.
>
> + \newline (add som breathing space)
Ok

>
>> + For example, consider a M tasks {Task_1,...Task_M} scheduled on M - 1
>
> Please consider rewriting this to
>
> "Consinder a set of M+1 tasks on a system with M CPUs [...]"
>
> As 'M' is normally used to denote the number of cores available and it is
> much easier to grasp the context of "<some number> + 1" rather than "<some
> number - 1"-CPUs.
Yes, this is what I originally wrote (and is the example I teach to students:
http://disi.unitn.it/~abeni/RTOS/multiprocessor.pdf, slide 7). But then I
re-read the original paper, and I see Dhall used m tasks (and n CPUs, just to
confuse people :). So I rewrote the example in this way... Also because in this
way the last task is Task_M, instead of Task_{M+1} which would make the notation
more complex (because of the _{M+1}). But I can rewrite using M+1 tasks and M CPUs.


>> + CPUs, with the first M - 1 tasks having a small worst case execution time
>> + WCET_i=e and period equal to relative deadline P_i=D_i=P-1. The last task
>
> Normally, 'e' is used to denote an _arbitrarily_ small value, and I suspect
> that this is indeed the case here as well
Right. This was a \epsilon in the original paper (actually, Dhall used  2\epsilon
and I decided to simplify things a little bit).

> (you're going to describe
> Dhall's effect, right?). Perhaps make that point explicit?
>
>       T_i = {P_i, e, P_i}
>
>> + (Task_M) has period, relative deadline and worst case execution time
>> + equal to P: P_M=D_M=WCET_M=P.
>
>        T_M = {P, P, P}
Ok


>> + If all the tasks activate at the
>> + same time t, global EDF schedules the first M - 1 tasks first (because
>> + their absolute deadlines are equal to t + P - 1, hence they are smaller
>> + than the absolute deadline of Task_M, which is t + P). As a result, Task_M
>> + can be scheduled only at time t + e, and will finish at time t + e + P,
>> + after its absolute deadline t + P. The total utilisation of the task set
>                                  ^^^^^^
>   Drop this, the text is full of equations as it is.
Ok

>
>> + is (M - 1) · e / (P - 1) + P / P = (M - 1) · e / (P - 1) + 1, and for
>> + small values of e this can become very close to 1. This is known as "Dhall's
>> + effect"[7].
>
> This gives the impression that 'e' must be constant, but all it really
> means is that e is an 'arbitrarily small value which can be *almost* 0'
Right. The original paper uses "\lim_{\epsilon -> 0} ...", but I decided to
simplify the description (maybe I oversimplified?). A constant and small e
should be ok to give an intuition of Dhall's effect: if e becomes very small,
the utilisation becomes very near to 1. But if you think this confuses the reader,
I can add a note about \lim_{e -> 0}

> and that they will be picked _before_ the heavy task by EDF.
Right. This is because these tasks have period (and relative deadline) equal to P-1.


>> + More complex schedulability tests for global EDF have been developed in
>> + real-time literature[8,9], but they are not based on a simple comparison
>> + between total utilisation (or density) and a fixed constant. If all tasks
>> + have D_i = P_i, a sufficient schedulability condition can be expressed in
>> + a simple way:
>> +	sum_i WCET_i / P_i <= M - (M - 1) · U_max
>
> sum_i; as stated in another comment, just juse 'sum' (IMHO)
Ok; if other people agree, I'll add a patch to the patchset to convert all the
"sum_" into "sum".


>> + where U_max = max_i {WCET_i / P_i}[10]. Notice that for U_max = 1,
>> + M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition
>> + just confirms the Dhall's effect. A more complete survey of the literature
>> + about schedulability tests for multi-processor real-time scheduling can be
>> + found in [11].
>> +
>> + As seen, enforcing that the total utilisation is smaller than M does not
>> + guarantee that global EDF schedules the tasks without missing any deadline
>> + (in other words, global EDF is not an optimal scheduling algorithm). However,
>> + a total utilisation smaller than M is enough to guarantee that non real-time
>> + tasks are not starved and that the tardiness of real-time tasks has an upper
>> + bound[12] (as previously noticed). Different bounds on the maximum tardiness
>> + experienced by real-time tasks have been developed in various papers[13,14],
>> + but the theoretical result that is important for SCHED_DEADLINE is that if
>> + the total utilisation is smaller or equal than M then the response times of
>> + the tasks are limited.
>> +
>> + Finally, it is important to understand the relationship between the
>> + scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
>> + described above (which represent the real temporal constraints of the task).
>
> What about simething like
>
> "
> Finally, it is important to understand the relationship between the
> scheduling deadlines assigned by SCHED_DEADLINE and the tasks' deadlines
> described above.
>
> The task itself supplies a _relative_ deadline, i.e. an offset after the
> release of the task at which point it must be complete whereas
> SCHED_DEADLINE assigns an _absolute_ deadline (a specific point in time) on
> the form
>
>       D_i = r_i + d_i
> "
> Or somesuch? I may be overdoing this.
This is not the point I wanted to make... Absolute deadlines (equal to r + D)
have been previously defined in the document for real-time tasks too.
The difference between SCHED_DEADLINE's deadlines and tasks' deadlines is not
"absolute vs relative". The difference is that SCHED_DEADLINE cannot know the
"real" tasks' deadlines, so it uses "scheduling deadlines" that are generated
according to the CBS rules (described in Section 2).
Now, if a task is developed according to the Liu&Layland model (does not block
before the end of the job) and the SCHED_DEADLINE parameters are properly assigned
(runtime >= WCET, period <= P) then the task's absolute deadlines and the scheduling
deadlines coincides, so it is possible to guarantee the respect of the task's temporal
constraints.
This is the tricky (and confusing :) thing about SCHED_DEADLINE.
I'll see if I can reword this paragraph to make it more clear.


			Thanks,
				Luca