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

[Henrik Austad]

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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/