Messages in this thread Patch in this message | | | Date | Thu, 09 Apr 2015 11:34:37 +0200 | From | Luca Abeni <> | Subject | Re: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability |
| |
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
| |