Re: [PATCH 08/16] sched: add period support for -deadline tasks.

[Tommaso Cucinotta <tommaso.cucinotta@sssup.it>]

Il 11/04/2012 21:32, Steven Rostedt ha scritto:
> On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
>
>> @@ -293,7 +293,11 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se)
>>    * assigned (function returns true if it can).
>>    *
>>    * For this to hold, we must check if:
>> - *   runtime / (deadline - t)<  dl_runtime / dl_deadline .
>> + *   runtime / (deadline - t)<  dl_runtime / dl_period .
>> + *
>> + * Notice that the bandwidth check is done against the period. For
>> + * task with deadline equal to period this is the same of using
>> + * dl_deadline instead of dl_period in the equation above.
> First, it seems that the function returns true if:
>
> 	dl_runtime / dl_period<  runtime / (deadline - t)
>
>
> I'm a little confused by this. We are comparing the ratio of runtime
> left and deadline left, to the ratio of total runtime to period.
>
> I'm actually confused by this premise anyway. What's the purpose of
> comparing the ratio? If runtime<  (deadline - t) wouldn't it not be able
> to complete anyway? Or are we thinking that the runtime will be
> interrupted proportionally by other tasks?

That's a well-known property of the CBS scheduling algorithm:
the "unblock rule" says that, when a task wakes up, if the residual
budget over residual deadline fits within the allocated "bandwidth",
then we can keep the current (abs) deadline and residual budget
without disrupting the schedulability of the system (i.e., ability of
other admitted tasks to meet their deadlines).
Otherwise, we should reset the status, i.e., refill budget and set
the deadline a period in the future, because keeping the current
abs deadline of the task would result in breaking guarantees
promised to other tasks.
Imagine a task going to sleep and waking
too close to its deadline: its deadline would be the closest in the
system, and it wouldn't allow anyone else to run. However, if its
residual budget is also big, then this is going to not allow anyone
to run for too much. Now, when doing the classical easy admission
test for single-CPU EDF (sum of budgets over periods <= 1), we
hadn't accounted for such a scenario with tasks blocking (which can
actually be accounted for by using far more complex tests knowing
for how long each task will block etc.). However, using the CBS, we
can keep the easy test and add the simple cut-off rule at task
wake-up which adds "temporal isolation", i.e., the capability
to not disrupt others' guarantees if I sleep for too much.
Said this, I guess/hope the rule is implemented right :-)

For a formal proof, I think you can refer to the Abeni's paper(s):

-) Integrating Multimedia Applications in Hard Real-Time Systems, RTSS '98
     www.cis.upenn.edu/~lee/01cis642/papers/AB98.pdf

which redirects on the Technical Report:
-) Server Mechanisms for Multimedia Applications

Hope this helps,

     T.

-- 
Tommaso Cucinotta, Computer Engineering PhD, Researcher
ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
Tel +39 050 882 024, Fax +39 050 882 003
http://retis.sssup.it/people/tommaso