[lkml]   [2015]   [Apr]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [RFC 3/4] Documentation/scheduler/sched-deadline.txt: Some notes on EDF schedulability
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

 \ /
  Last update: 2015-04-09 12:41    [W:0.073 / U:0.184 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site