Re: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability

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

Hi Henrik,

On 04/09/2015 11:06 AM, Henrik Austad wrote:
> On Wed, Apr 08, 2015 at 01:59:39PM +0200, Luca Abeni wrote:
>> Add a short discussion about sufficient and necessary schedulability tests,
>> and a simple example showing that if D_i != P_i then density based tests
>> are only sufficient.
>> Also add some references to scientific papers on schedulability tests for
>> EDF that are both necessary and sufficient, and on their computational
>> complexity.
>> ---
>>   Documentation/scheduler/sched-deadline.txt |   40 ++++++++++++++++++++++++++--
>>   1 file changed, 38 insertions(+), 2 deletions(-)
>>
>> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
>> index 39341d9..ffaf95f 100644
>> --- a/Documentation/scheduler/sched-deadline.txt
>> +++ b/Documentation/scheduler/sched-deadline.txt
>> @@ -171,8 +171,34 @@ CONTENTS
>>    If D_i != P_i for some task, then it is possible to define the density of
>>    a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
>>    of all the tasks running on a CPU if the sum sum_i WCET_i/min{D_i,P_i} of the
>> - densities of the tasks running on such a CPU is smaller or equal than 1
>> - (notice that this condition is only sufficient, and not necessary).
>> + densities of the tasks running on such a CPU is smaller or equal than 1:
>> +	sum_i WCET_i / min{D_i, P_i} <= 1
>
> I assume you mean sum {forall i in the set}
Yes

> but using 'sum_i' is confusing
> since we use this to denote a particular task
Sorry about that. I can use "sum" (without "_i") if this is more understandable (BTW,
"sum_i" is already used in other parts of the document; I'll change those "sum_i" too).

> Also, density is equivalent
> to 'utilization', right? (which is referred to in sec 4.1
No; the utilisation of task i (generally indicated as "U_i") is  WCET_i / P_i (this
is explained earlier in the document); its density is WCET_i / min{P_i,D_i}.

>
> So you could rewrite this to something like this
>
>     U_i = WCET_i ( min{D_i, P_i)
>     U = sum U_i
>
> (or use \delta which is the normal symbol for density iirc)
Well, I already defined "total utilisation" earlier in the document, but without associating
a symbol like "U" to it. I can add "U = sum U_i" and "\delta = sum WCET_i / min{D_i, P_i)" and
use these symbols instead of repeating the sum.


>> + It is important to notice that this condition is only sufficient, and not
>> + necessary: there are task sets that are schedulable, but do not respect the
>> + condition. For example, consider the task set {Task_1,Task_2} composed by
>> + Task_1 with period P_1=100ms, relative deadline D_1=50ms and worst case
>> + execution time WCET_1=50ms, and Task_2 with period P_2=100ms, relative
>> + deadline D_2=100ms and worst case execution time WCET_2=10ms.
>
> We need a better way of describing a set of tasks in this text.
Yes, after re-reading the sentence I agree :)


> what about adding something like this to the start of Sec. 2?
>
> @@ -43,7 +43,13 @@ CONTENTS
>    "deadline", to schedule tasks. A SCHED_DEADLINE task should receive
>    "runtime" microseconds of execution time every "period" microseconds, and
>    these "runtime" microseconds are available within "deadline" microseconds
> - from the beginning of the period.  In order to implement this behaviour,
> + from the beginning of the period.
> +
> + We can the describe a task in a concise manner:
> +
> +      T_i = {period, WCET, deadline}
> +
> + In order to implement this behaviour,
Notice that these "period" and "runtime" are different things respect to the
task period and WCET described in Section 3 (the relationship between them is
explained at the end of Section 3: "Finally, it is important to understand the
relationship...").

But at the beginning of Section 3, after defining WCET, P and D I can add a sentence
like the one you propose:
"A real-time task Task_i can be described concisely as
	Task_i = (WCET_i, D_i, P_i)
"
(I used "Task_i" instead of "T_i" in order to avoid the "T_i <-> P_i" confusion
mentioned in previous emails)


> Then you can rewrite the task-description to be much more concise (and less
> verbose):
>
>       T_1 = {100, 50,  50}
>       T_2 = {100, 10, 100}
Agreed (only, I think in literature it is more common to use the WCET as a first
element of the triplet).


>> + EDF is clearly able to schedule the two tasks without missing any deadline
>> + (Task_1 is scheduled as soon as it is released, and finishes just in time
>> + to respect its deadline; Task_2 is scheduled immediately after Task_1, hence
>> + its response time cannot be larger than 50ms + 10ms = 60ms) even if
>> +	50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1
>> + Of course it is possible to test the exact schedulability of tasks with
>> + D_i != P_i (checking a condition that is both sufficient and necessary),
>> + but this cannot be done by comparing the total utilisation or density with
>> + a constant. Instead, the so called "processor demand" approach can be used,
>> + computing the total amount of CPU time h(t) needed by all the tasks to
>> + respect all of their deadlines in a time interval of size t, and comparing
>> + such a time with the interval size t. If for all values of t h(t) < t, then
>
>   For all values of h(t'), t' < t ?
No, it is really "for all values of t, h(t) < t" (meaning that h(t) - the demanded
CPU time - should be smaller than t - the size of the time interval - for every
possible value of t). I realize the current text can be confusing and should
be reworded... Any suggestions?


>> + EDF is able to schedule the tasks respecting all of their deadlines. Since
>> + performing this check for all possible values of t is impossible, it has been
>> + proven[4,5,6] that it is sufficient to perform the test for values of t
>> + between 0 and a maximum value L. The cited papers contain all of the
>> + mathematical details and explain how to compute h(t) and L.
>> + In any case, this kind of analysis is too complex to be performed as an
>
> as well as too time-consuming to be perfomred on-line.
Ok.


> You could add a note stating that this can be computed offline for a small
> (and static) set of tasks, but I guess it doesn't really matter. Those with
> hard-rt requirements will (hopefully know what EDF is and is not capable
> of doing).
Well, my idea was that this text should be some kind of "quick introduction to
real-time scheduling" for people who do not know too much in advance... I'll
add a note about the fact that the admission test can be executed offline (for
static task sets).


				Thanks,
					Luca