Sorry for the delayed response... I think I must have inadvertently
deleted this
email last week and Bjoern just mentioned it to me...
> On Fri, 2010-11-12 at 17:04 +0100, Peter Zijlstra wrote:
>
>> On Fri, 2010-11-12 at 16:36 +0100, Raistlin wrote:
>>
>>> But at this point I can't avoid asking. That model aims at _pure_
>>> hard real-time scheduling *without* resource reservation capabilities,
>>> provided it deals with temporal overruns by means of a probabilistic
>>> analysis, right?
>>>
>> From what I understood from it, its a soft real-time scheduling
>> algorithm with resource reservation.
>>
>>
> Mmm... I've gone through it (again!) quickly, and you're right, it
> mentions soft real-time, and I agree that for those systems average CET
> is better than worst CET. However, I'm not sure resource reservation is
> there... Not in the paper I have at least, but I may be wrong.
>
>
>> The problem the stochastic execution time model tries to address is the
>> WCET computation mess, WCET computation is hard and often overly
>> pessimistic, resulting in under-utilized systems.
>>
>>
> I know, and it's very reasonable. The point I'm trying to make is that
> resource reservation tries to address the very same issue.
> I am all but against this model, just want to be sure it's not too much
> in conflict to the other features we have, especially with resource
> reservation. Especially considering that --if I got the whole thing
> about this scheduler right-- resource reservation is something we really
> want, and I think UNC people would agree here, since I heard Bjorn
> stating this very clear both in Dresden and in Dublin. :-)
>
> BTW, I'm adding them to the Cc, seems fair, and more useful than all
> this speculation! :-P
>
> Bjorn, Jim, sorry for bothering. If you're interested, this is the very
> beginning of the whole thread:
> http://lkml.org/lkml/2010/10/29/67
>
> And these should be from where this specific discussion starts (I hope,
> the mirror is not updated yet I guess :-( ):
> http://lkml.org/lkml/2010/10/29/49
> http://groups.google.com/group/linux.kernel/msg/1dadeca435631b60
>
> Thanks and Regards,
> Dario
>
If you're talking about our most recent "stochastic" paper, it is about
supporting
soft real-time task systems on a multiprocessor where resource
reservations are
used. The main result of the paper is that if you provision the
reservation for a
task slightly higher than it's average-case execution time, and if you use a
scheduling algorithm (like global EDF) that ensures bounded tardiness
(w.r.t.
these reservations), then the task's expected tardiness will be bounded
and the
expected bound does not depend on worst-case execution times. I'm not
sure if
slack-reallocation methods have come up in this discussion (sorry, I'm
really
pressed for time and didn't look), but we didn't get into that in our
paper. However,
such methods would be easy to incorporate. I think one of the most
beautiful
aspects of this paper (which we didn't say enough about) is that the
analysis
completely separates all the stochastic stuff from the reasoning needed to
derive tardiness bounds under a given scheduler. In other words, you
can simply
ignore all stochastic issues when reasoning about tardiness. I gathered
there was
some confusion about whether we were using resource reservations. Such
reservations are actually crucial for our analysis as they allow
independence to
be assumed across tasks. And oh yeah: this work has nothing to do with hard
real-time and worst-case execution times are not used at all.
Just to make sure I don't end up creating more confusion, the paper I'm
talking
about is this one:
http://www.cs.unc.edu/~anderson/papers/rtas11b.pdf
I hope this helps.
-Jim Anderson
Hi James,
On 15/11/10 19:37, James H. Anderson wrote:
[...]
>>> The problem the stochastic execution time model tries to address is the
>>> WCET computation mess, WCET computation is hard and often overly
>>> pessimistic, resulting in under-utilized systems.
>>>
>> I know, and it's very reasonable. The point I'm trying to make is that
>> resource reservation tries to address the very same issue.
>> I am all but against this model, just want to be sure it's not too much
>> in conflict to the other features we have, especially with resource
>> reservation. Especially considering that --if I got the whole thing
>> about this scheduler right-- resource reservation is something we really
>> want, and I think UNC people would agree here, since I heard Bjorn
>> stating this very clear both in Dresden and in Dublin. :-)
>>
>> BTW, I'm adding them to the Cc, seems fair, and more useful than all
>> this speculation! :-P
>>
>> Bjorn, Jim, sorry for bothering. If you're interested, this is the very
>> beginning of the whole thread:
>> http://lkml.org/lkml/2010/10/29/67
[...]
> If you're talking about our most recent "stochastic" paper, it is about
> supporting
> soft real-time task systems on a multiprocessor where resource
> reservations are
> used. The main result of the paper is that if you provision the
> reservation for a
> task slightly higher than it's average-case execution time, and if you
> use a
> scheduling algorithm (like global EDF) that ensures bounded tardiness
> (w.r.t.
> these reservations), then the task's expected tardiness will be bounded
> and the
> expected bound does not depend on worst-case execution times. I'm not
> sure if
> slack-reallocation methods have come up in this discussion (sorry, I'm
> really
> pressed for time and didn't look), but we didn't get into that in our
> paper.
So, if I understand well (sorry, I am just trying to make a short
summary to check if we are aligned) your analysis is similar to the one
presented in the papers I mentioned earlier in this thread (different
stochastic modelling, but similar approach): you analyse a reservation
in isolation and you provide some stochastic tardiness guarantees based
on an (e_i, p_i) service model.... Right?
If my understanding is correct (please, correct me if I am wrong), your
analysis can be applied even with the current version of Dario's patch
(I mean: no modifications to the patch are needed for removing
assumptions about WCET knowledge... Your paper uses a sporadic server
for the reservation mechanism, but I think a CBS can work too...).
Thanks,
Luca
On 15/11/10 19:37, James H. Anderson wrote:
[...]
> If you're talking about our most recent "stochastic" paper, it is about
> supporting
> soft real-time task systems on a multiprocessor where resource
> reservations are
> used. The main result of the paper is that if you provision the
> reservation for a
> task slightly higher than it's average-case execution time
[...]
BTW, I think we are aligned on this.
I was a little bit surprised when Peter mentioned allocating a runtime
equal to the average execution time (because of the meta-stability
considerations that Tommaso also mentioned), but I fully agree that if
the allocated runtime is higher than the average execution time then the
queue is stable and it's possible to find a bound for the expected
tardiness (or even its probability distribution... This is similar to my
"probabilistic deadlines").
Luca
On 11/15/2010 2:23 PM, Luca Abeni wrote:
> Hi James,
>
> On 15/11/10 19:37, James H. Anderson wrote:
> [...]
>>>> The problem the stochastic execution time model tries to address is
>>>> the
>>>> WCET computation mess, WCET computation is hard and often overly
>>>> pessimistic, resulting in under-utilized systems.
>>>>
>>> I know, and it's very reasonable. The point I'm trying to make is that
>>> resource reservation tries to address the very same issue.
>>> I am all but against this model, just want to be sure it's not too much
>>> in conflict to the other features we have, especially with resource
>>> reservation. Especially considering that --if I got the whole thing
>>> about this scheduler right-- resource reservation is something we
>>> really
>>> want, and I think UNC people would agree here, since I heard Bjorn
>>> stating this very clear both in Dresden and in Dublin. :-)
>>>
>>> BTW, I'm adding them to the Cc, seems fair, and more useful than all
>>> this speculation! :-P
>>>
>>> Bjorn, Jim, sorry for bothering. If you're interested, this is the very
>>> beginning of the whole thread:
>>> http://lkml.org/lkml/2010/10/29/67
> [...]
>> If you're talking about our most recent "stochastic" paper, it is about
>> supporting
>> soft real-time task systems on a multiprocessor where resource
>> reservations are
>> used. The main result of the paper is that if you provision the
>> reservation for a
>> task slightly higher than it's average-case execution time, and if you
>> use a
>> scheduling algorithm (like global EDF) that ensures bounded tardiness
>> (w.r.t.
>> these reservations), then the task's expected tardiness will be bounded
>> and the
>> expected bound does not depend on worst-case execution times. I'm not
>> sure if
>> slack-reallocation methods have come up in this discussion (sorry, I'm
>> really
>> pressed for time and didn't look), but we didn't get into that in our
>> paper.
> So, if I understand well (sorry, I am just trying to make a short
> summary to check if we are aligned) your analysis is similar to the
> one presented in the papers I mentioned earlier in this thread
> (different stochastic modelling, but similar approach): you analyse a
> reservation in isolation and you provide some stochastic tardiness
> guarantees based on an (e_i, p_i) service model.... Right?
Sorry, I don't have time right now to check these papers, but what you
are saying sounds correct.
>
> If my understanding is correct (please, correct me if I am wrong),
> your analysis can be applied even with the current version of Dario's
> patch (I mean: no modifications to the patch are needed for removing
> assumptions about WCET knowledge... Your paper uses a sporadic server
> for the reservation mechanism, but I think a CBS can work too...).
This sounds correct a well. We assume that if a job of a task overruns
its current budget allocation (which will likely happen, provisioning
reservations on the average case), then the remainder of that job will
be executed using future allocations for the same task. The analysis
doesn't (I think) depend too much on the exact way reservations are
supported.
-Jim
On Mon, 2010-11-15 at 13:37 -0500, James H. Anderson wrote:
> Sorry for the delayed response... I think I must have inadvertently
> deleted this
>
NP. Hope it's not my fault, due to GPG and stuff... :-)
> If you're talking about our most recent "stochastic" paper, it is about
> supporting
> soft real-time task systems on a multiprocessor where resource
> reservations are
> used.
>
Actually, we were talking about the previous one, which (if I got it
well) didn't include reservations, and that's why we were wondering how
to integrate it in the scheduler (which _is_ reservation based).
Now that this one is out, going for it simply solves all our issues,
also considering that it says something very similar to what we (Pisa
guys :-D) are familiar with, since we investigated this stuff too
sometime ago (actually, Luca did).
> However, such methods would be easy to incorporate.
>
I think it really should be... Actually, I'm under the impression that
we don't even need variance/std-dev of the execution time to be part of
the interface, do we?
> I gathered there was
> some confusion about whether we were using resource reservations. Such
> reservations are actually crucial for our analysis as they allow
> independence to be assumed across tasks.
>
Yes, as I said, this was because we were looking at first paper. Now we
got it, thanks a lot for clarifying! :-)
> I hope this helps.
>
A lot, thanks again.
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]