On Thu, Apr 09, 2015 at 11:34:37AM +0200, Luca Abeni wrote:> 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:>  [...]> >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}.ah, yes, you're right of course. Don't mind my inane ramblings here then :)> >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...").Ok. I understood runtime as the dynamic value being managed by the scheduler and should never exceed WCET (or being set to WCET upon release and task preemption when runtime==0).I'll read through the entire thing carefully methinks> 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)See! I'm not even consistent with my own naming. (aren't you glad you sent me these patches?)> >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).Hmm, could be, I was sure it was period - as long as we're consistent I don't really care. I'd just like a more concise way of describing tasks.Use it the same order as in struct sched_dl_entity perhaps? (which is runtime, deadline, period)?> >>+ 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?aaah, I read 't' as "a point in time", but 't' here is a _relative_ value, starting at offset X. *gah* this is getting messy.so, basically h(t) is defined as the length of the interval [0,t) (assuming we start at time 0..)Then I understand what you mean and then it makes more sense :)> >>+ 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).You're right, let's not add more text to this than absolutely needed.-- Henrik Austad