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 taskSorry 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.1No; the utilisation of task i (generally indicated as "U_i") is  WCET_i / P_i (thisis 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 associatinga symbol like "U" to it. I can add "U = sum U_i" and "\delta = sum WCET_i / min{D_i, P_i)" anduse 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 thetask period and WCET described in Section 3 (the relationship between them isexplained at the end of Section 3: "Finally, it is important to understand therelationship...").But at the beginning of Section 3, after defining WCET, P and D I can add a sentencelike 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" confusionmentioned 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 firstelement 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 demandedCPU time - should be smaller than t - the size of the time interval - for everypossible value of t). I realize the current text can be confusing and shouldbe 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 toreal-time scheduling" for people who do not know too much in advance... I'lladd a note about the fact that the admission test can be executed offline (forstatic task sets).				Thanks,					Luca