Weekly edition Kernel Security Distributions Contact Us Search Archives Calendar Subscribe Write for LWN LWN.net FAQ Sponsors

 From: Raistlin To: Bjoern Brandenburg Subject: Re: periods and deadlines in SCHED_DEADLINE Date: Sat, 10 Jul 2010 09:08:26 +0200 Cc: Peter Zijlstra , linux-kernel , Song Yuan , Dmitry Adamushko , Thomas Gleixner , Nicola Manica , Luca Abeni , Claudio Scordino , Harald Gustafsson , bastoni-AT-cs.unc.edu, Giuseppe Lipari Archive-link: Article, Thread

```On Fri, 2010-07-09 at 16:51 +0200, Bjoern Brandenburg wrote:
> > Happen to have a paper handy that explains all this in a concise way?
> >
>
> Sounds confusing, but this is actually not that complicated.
>
> - If the period exceeds the deadline of a task, then it is said to have a constrained deadline,
and is said to be a constrained task.
>
> - The density of a task is the ratio budget/min(period, relative deadline). The density of a task
is at most its utilization (budget/period).
>
> - There exists a simple *sufficient* (but not necessary) test for uniprocessor EDF for
constrained tasks: if the sum of all task densities is at most one (on each processor), then all
jobs will meet their deadlines. (Of course, this assumes that the budget is only replenished at the
beginning at each period and does not take self-suspensions due to I/O etc. into account.)
>
Right, I think Bjoern made it much more clear than how you can find it
in many of the existing papers! :-)

Just to make a simple UP example, if you have two tasks with the
following parameters (where T_i=(C_i, P_i, D_i)):

T_1 = (4, 10, 5)
T_2 = (4, 10, 5)

Then the test Sum_i(C_i/P_i)<1 will say "go!" (4/10+4/10<1), but
one of the tasks can miss its deadline by 3 time units in the worst case
(if, and if yes which one, depends on the order with witch they arrive).

Using D_i instead of P_i in the test will make things better in this
case (4/5+4/5>1 ==> "no go!"), but its overly pessimistic (i.e., only
sufficient). In fact for this task set:

T_1 = (1, 10, 2)
T_2 = (2, 20, 4)
T_3 = (3, 50, 6)

which has small utilization (Sum_i(C_i/P_i)=.26) and *is schedulable*,
even if 1/2+2/4+3/6=1.5>1.

Hope this helped in clarifying things even more! :-D
Btw, another nice survey about schedulability tests for global EDF I
know (and you'll forgive me if I point you to something from my
institution :-)) is this http://retis.sssup.it/~marko/papers/ICPP09.pdf.

> As a side note, almost all global EDF hard real-time admission tests can handle tasks with
constrained deadlines transparently. However, as far as I can tell, they do not apply to
>
This is the only part I am not sure I got... Can you explain me what do
you mena by "they do not apply" ?

> PS: My responses will be delayed, I'm off to the airport...
>
Yep, so will be mine one, including this one! :-P

Thanks and regards,
Dario

--
<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / raistlin@ekiga.net /
dario.faggioli@jabber.org

```