On Fri, 2010-10-29 at 08:34 +0200, Raistlin wrote:
> Make it possible to specify a period (different or equal than
> deadline) for -deadline tasks.
>
I would expect it to be:
runtime <= deadline <= period
On Thu, 2010-11-11 at 20:17 +0100, Peter Zijlstra wrote:
> On Fri, 2010-10-29 at 08:34 +0200, Raistlin wrote:
> > Make it possible to specify a period (different or equal than
> > deadline) for -deadline tasks.
> >
> I would expect it to be:
>
> runtime <= deadline <= period
>
Well, apart from that really unhappy comment/changelog, it should be
like that in the code, and if it's not, it is what I meant and I'll
change to that as soon as I can! :-)
Since you spotted it... The biggest issue here is admission control
test. Right now this is done against task's bandwidth, i.e.,
sum_i(runtime_i/period_i)<=threshold, but it is unfortunately wrong...
Or at least very, very loose, to the point of being almost useless! :-(
The more correct --in the sense that it at least yield a sufficient (not
necessary!) condition-- thing to do would be
sum_i(runtime_i/min{deadline_i,period_i})<=threshold.
So, what you think we should do? Can I go for this latter option?
Thanks,
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 / [email protected] /
[email protected]
On Thu, 2010-11-11 at 20:31 +0100, Raistlin wrote:
> On Thu, 2010-11-11 at 20:17 +0100, Peter Zijlstra wrote:
> > On Fri, 2010-10-29 at 08:34 +0200, Raistlin wrote:
> > > Make it possible to specify a period (different or equal than
> > > deadline) for -deadline tasks.
> > >
> > I would expect it to be:
> >
> > runtime <= deadline <= period
> >
> Well, apart from that really unhappy comment/changelog, it should be
> like that in the code, and if it's not, it is what I meant and I'll
> change to that as soon as I can! :-)
>
> Since you spotted it... The biggest issue here is admission control
> test. Right now this is done against task's bandwidth, i.e.,
> sum_i(runtime_i/period_i)<=threshold, but it is unfortunately wrong...
> Or at least very, very loose, to the point of being almost useless! :-(
Right, I have some recollection on that.
> The more correct --in the sense that it at least yield a sufficient (not
> necessary!) condition-- thing to do would be
> sum_i(runtime_i/min{deadline_i,period_i})<=threshold.
>
> So, what you think we should do? Can I go for this latter option?
I remember we visited this subject last time, but I seem to have
forgotten most details.
So sufficient (but not necessary) means its still a pessimistic approach
but better than the one currently employed, or does it mean its
optimistic and allows for unschedulable sets to be allowed in?
Il 11/11/2010 20:43, Peter Zijlstra ha scritto:
>> The more correct --in the sense that it at least yield a sufficient (not
>> necessary!) condition-- thing to do would be
>> sum_i(runtime_i/min{deadline_i,period_i})<=threshold.
>>
>> So, what you think we should do? Can I go for this latter option?
> So sufficient (but not necessary) means its still a pessimistic approach
> but better than the one currently employed, or does it mean its
> optimistic and allows for unschedulable sets to be allowed in?
It means that, if the new task passes the test, then it has its
guaranteed runtime_i over each time horizon as long as min{deadline_i,
period_i} (and all of the other tasks already admitted have their
guarantees as well of course). From the perspective of analyzing
capability of the attached task to meet its own deadlines, if the task
has a WCET of runtime_i, a minimum inter-arrival period of period_i, and
a relative deadline of deadline_i, then it is guaranteed to meet all of
its deadlines.
Therefore, this kind of test is sufficient for ensuring schedulability
of all of the tasks, but it is not actually necessary, because it is too
pessimistic. In fact, consider a task with a period of 10ms, a runtime
of 3ms and a relative deadline of 5ms. After the test passed, you have
actually allocated a "share" of the CPU capable of handling 3ms of
workload every 5ms. Instead, we actually know that (or, we may actually
force it to), after the deadline at 5ms, this task will actually be idle
for further 5ms, till its new period. There are more complex tests which
account for this, in the analysis.
Generally speaking, with deadlines different from periods, a tighter
test (for partitioned EDF) is one making use of the demand-bound
function, which unfortunately is far more heavyweight than a mere
utilization check (for example, you should perform a number of checks
along a time horizon that can go as far as the hyper-period [LCM of the
periods] of the considered task-set -- something that may require
arbitrary precision arithmetics in the worst-case). However, you can
check the *RT* conferences in the last 10 years in order to see all the
possible trade-offs between accuracy of the test and the imposed
computation requirement/overhead.
Summarizing, the test suggested by Dario is sufficient to ensure the
correct behavior of the accepted tasks, under the assumption that they
stick to the "sporadic RT task model", it is very simple to implement in
the kernel, but it is somewhat pessimistic. Also, it actually uses only
2 parameters, the runtime and the min{deadline_i, period_i}.
This clarifies also why I was raising the issue of whether to have at
all the specification of a deadline \neq period, in my other e-mail. If
the first implementation will just use the minimum of 2 of the supplied
parameters, then let them be specified as 1 parameter only: it will be
easier for developers to understand and use. If we identify later a
proper test we want to use, then we can exploit the "extensibility" of
the sched_params.
My 2 cents.
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
On Thu, 2010-11-11 at 20:43 +0100, Peter Zijlstra wrote:
> > Since you spotted it... The biggest issue here is admission control
> > test. Right now this is done against task's bandwidth, i.e.,
> > sum_i(runtime_i/period_i)<=threshold, but it is unfortunately wrong...
> > Or at least very, very loose, to the point of being almost useless! :-(
>
> Right, I have some recollection on that.
>
:-)
> So sufficient (but not necessary) means its still a pessimistic approach
> but better than the one currently employed, or does it mean its
> optimistic and allows for unschedulable sets to be allowed in?
>
Tommaso already gave the best possible explanation of this! :-P
So, trying to recap:
- using runtime/min(deadline,period) _does_ guarantee schedulability,
but also rejects schedulable situations in UP/partitioning. Quite
sure it _does_not_ guarantee schedulability in SMP/global, but
*should* enable bounded tardiness;
- using runtime/period _does_not_ guarantee schedulability nor in
UP/partitioning neither in SMP/global, but *should* enable bounded
tardiness for _both_.
The *should*-s come from the fact that I feel like I read it somewhere,
but right now I can't find the paper(s), not even following the
references indicated by Bjorn and Jim in previous e-mails and threads
(i.e., I can't find anything _explicitly_ considering deadline!=period,
but it might be my fault)... :-(
Thus, all this being said, what do you want me to do? :-D
Since we care about bounded tardiness more than 100%-guaranteed
schedulability (which, BTW, neither min{} could give us, at least for
SMPs), should we stay with runtime/period? Tommaso, Luca, do you think
it would be so bad?
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 / [email protected] /
[email protected]
On Fri, 2010-11-12 at 14:33 +0100, Raistlin wrote:
> On Thu, 2010-11-11 at 20:43 +0100, Peter Zijlstra wrote:
> > > Since you spotted it... The biggest issue here is admission control
> > > test. Right now this is done against task's bandwidth, i.e.,
> > > sum_i(runtime_i/period_i)<=threshold, but it is unfortunately wrong...
> > > Or at least very, very loose, to the point of being almost useless! :-(
> >
> > Right, I have some recollection on that.
> >
> :-)
>
> > So sufficient (but not necessary) means its still a pessimistic approach
> > but better than the one currently employed, or does it mean its
> > optimistic and allows for unschedulable sets to be allowed in?
> >
> Tommaso already gave the best possible explanation of this! :-P
>
> So, trying to recap:
> - using runtime/min(deadline,period) _does_ guarantee schedulability,
> but also rejects schedulable situations in UP/partitioning. Quite
> sure it _does_not_ guarantee schedulability in SMP/global, but
> *should* enable bounded tardiness;
> - using runtime/period _does_not_ guarantee schedulability nor in
> UP/partitioning neither in SMP/global, but *should* enable bounded
> tardiness for _both_.
> Thus, all this being said, what do you want me to do? :-D
runtime/min(deadline,period) sounds fine, as its more useful than
runtime/period.
On 11/11/2010 08:31 PM, Raistlin wrote:
> On Thu, 2010-11-11 at 20:17 +0100, Peter Zijlstra wrote:
>> On Fri, 2010-10-29 at 08:34 +0200, Raistlin wrote:
>>> Make it possible to specify a period (different or equal than
>>> deadline) for -deadline tasks.
>>>
>> I would expect it to be:
>>
>> runtime<= deadline<= period
>>
> Well, apart from that really unhappy comment/changelog, it should be
> like that in the code, and if it's not, it is what I meant and I'll
> change to that as soon as I can! :-)
>
> Since you spotted it... The biggest issue here is admission control
> test. Right now this is done against task's bandwidth, i.e.,
> sum_i(runtime_i/period_i)<=threshold, but it is unfortunately wrong...
> Or at least very, very loose, to the point of being almost useless! :-(
The point is that when the relative deadline is different from the period,
the concept of "task utilisation", or "bandwidth" becomes fuzzy at least
(I would say it becomes almost meaningless, but...).
The test with min{D,P} is technically more correct (meaning that it will
never accept unschedulable tasks), but it rejects some schedulable tasks.
As Tommaso pointed out, a more complex admission test would be needed.
> The more correct --in the sense that it at least yield a sufficient (not
> necessary!) condition-- thing to do would be
> sum_i(runtime_i/min{deadline_i,period_i})<=threshold.
>
> So, what you think we should do? Can I go for this latter option?
The one with min{} is at lest correct :)
Luca
On Fri, 2010-11-12 at 14:46 +0100, Luca Abeni wrote:
> > So, what you think we should do? Can I go for this latter option?
> The one with min{} is at lest correct :)
>
Seems that Peter agrees (and I'm Tommaso would agree too) so, copy
that! ;-P
Thanks,
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 / [email protected] /
[email protected]