2010-11-11 22:13:17

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Fri, 2010-10-29 at 08:42 +0200, Raistlin wrote:
> The bandwidth enforcing mechanism implemented inside the
> SCHED_DEADLINE policy ensures that overrunning tasks are slowed
> down without interfering with well behaving ones.
> This, however, comes at the price of limiting the capability of
> a task to exploit more bandwidth than it is asigned.
>
> The current implementation always stops a task that is trying
> to use more than its runtime (every deadline). Something else that
> could be done is to let it continue running, but with a "decreased
> priority". This way, we can exploit full CPU bandwidth and still
> avoid interferences.
>
> In order of "decreasing the priority" of a deadline task, we can:
> - let it stay SCHED_DEADLINE and postpone its deadline. This way it
> will always be scheduled before -rt and -other tasks but it
> won't affect other -deadline tasks;
> - put it in SCHED_FIFO with some priority. This way it will always
> be scheduled before -other tasks but it won't affect -deadline
> tasks, nor other -rt tasks with higher priority;
> - put it in SCHED_OTHER.
>
> Notice also that this can be done on a per-task basis, e.g., each
> task can specify what kind of reclaiming mechanism it wants to use
> by means of the sched_flags field of sched_param_ex.
>
> Therefore, this patch:
> - adds the flags for specyfing DEADLINE, RT or OTHER reclaiming
> behaviour;
> - adds the logic that changes the scheduling class of a task when
> it overruns, according to the requested policy.

The first two definitely should require SYS_CAP_ADMIN because it allows
silly while(1) loops again.. but can we postpone this fancy feature as
well?

I'd much rather have the stochastic thing implemented that allows
limited temporal overrun.


2010-11-12 15:36:48

by Dario Faggioli

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Thu, 2010-11-11 at 23:12 +0100, Peter Zijlstra wrote:
> > Therefore, this patch:
> > - adds the flags for specyfing DEADLINE, RT or OTHER reclaiming
> > behaviour;
> > - adds the logic that changes the scheduling class of a task when
> > it overruns, according to the requested policy.
>
> The first two definitely should require SYS_CAP_ADMIN because it allows
> silly while(1) loops again..
>
Sure, good point!

> but can we postpone this fancy feature as
> well?
>
As you wish, I'll keep backing it in my private tree...

> I'd much rather have the stochastic thing implemented that allows
> limited temporal overrun.
>
... 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?
In this scheduler, we do have resource reservations to deal with
overruns, provided it can guarantee bandwidth isolation among tasks even
in case of overrun (which is very typical soft real-time solution, but
can provide hard guarantees as well, if the analysis is careful enough).

Are we sure the two approaches matches, and/or can live together?

That's because I'm not sure what we would do, at that point, while
facing a runtime overrun... Enforce the bandwidth by stopping the task
until its next deadline (as we do now)? Or allows it to overrun basing
of the statistical information we have? Or do we want somehow try to do
both?

I know we can discuss and decide the details later, after merging all
this... But I still think it's worth trying to have at least a basic
idea of how to do that, just to avoid doing something now that we will
regret then. :-)

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]


Attachments:
signature.asc (198.00 B)
This is a digitally signed message part

2010-11-12 16:07:29

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

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. It explicitly allows for deadline
misses, but requires the tardiness of those misses to be bounded, ie.
the UNC soft real-time definition.

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.

By using the average CET (much more easily obtained) we get a much
higher system utilization, but since its an average we need to deal with
deadline overruns due to temporal overload scenarios.

Their reasoning goes that since its an average, an overrun must be
compensated by a short run in the near future. The variance parameter
provides a measure of 'near'. Once we've 'consumed' this short run and
are back to the average case our tardiness is back to 0 as well
(considering an otherwise tight scheduler, say P-EDF), since then we've
met the bandwidth requirements placed by this scheduler.

And since the pure statistics allow for an arbitrary large deviation
from the average it also requires a max runtime in order to be able to
place a bound on tardiness.

So for G-EDF with stochastic ET we still get a bounded tardiness, its a
simple sum of bounds, one due to the G in G-EDF and one due to the
stochastic ET.

2010-11-12 17:45:34

by Luca Abeni

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On 12/11/10 17:04, 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. It explicitly allows for deadline
> misses, but requires the tardiness of those misses to be bounded, ie.
> the UNC soft real-time definition.
>
> 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.
[...]
BTW, sorry for the shameless plug, but even with the current
SCHED_DEADLINE you are not forced to dimension the runtime using the
WCET. You can use some stochastic analysis, providing probabilistic
deadline guarantees. See (for example) "QoS Guarantee Using
Probabilistic Deadlines"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7683&rep=rep1&type=pdf
and "Stochastic analysis of a reservation based system"
http://www.computer.org/portal/web/csdl/doi?doc=doi/10.1109/IPDPS.2001.925049
(sorry, this is not easy to download... But I can provide a copy if you
are interested).


Luca

2010-11-12 17:52:02

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Fri, 2010-11-12 at 18:41 +0100, Luca Abeni 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.
> [...]
> BTW, sorry for the shameless plug, but even with the current
> SCHED_DEADLINE you are not forced to dimension the runtime using the
> WCET.

Yes you are, it pushes the deadline back on overrun. The idea it to
maintain the deadline despite overrunning your budget (up to a point).

The paper we're all talking about is:

A. Mills and J. Anderson, " A Stochastic Framework for Multiprocessor
Soft Real-Time Scheduling", Proceedings of the 16th IEEE Real-Time and
Embedded Technology and Applications Symposium, pp. 311-320, April 2010.
http://www.cs.unc.edu/~anderson/papers/rtas10brevised.pdf

And I see they've got a new stochastic paper out:

A. Mills and J. Anderson, " Scheduling Stochastically-Executing Soft
Real-Time Tasks: A Multiprocessor Approach Without Worst-Case Execution
Times", in submission.
http://www.cs.unc.edu/~anderson/papers/rtas11b.pdf

2010-11-12 17:58:13

by Luca Abeni

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On 12/11/10 18:51, Peter Zijlstra wrote:
> On Fri, 2010-11-12 at 18:41 +0100, Luca Abeni 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.
>> [...]
>> BTW, sorry for the shameless plug, but even with the current
>> SCHED_DEADLINE you are not forced to dimension the runtime using the
>> WCET.
>
> Yes you are, it pushes the deadline back on overrun.
I think in case of overrun it postpones the deadline (by a period P),
avoiding to execute the task until the end of the current period, right?

> The idea it to
> maintain the deadline despite overrunning your budget (up to a point).
>
> The paper we're all talking about is:
>
> A. Mills and J. Anderson, " A Stochastic Framework for Multiprocessor
> Soft Real-Time Scheduling", Proceedings of the 16th IEEE Real-Time and
> Embedded Technology and Applications Symposium, pp. 311-320, April 2010.
> http://www.cs.unc.edu/~anderson/papers/rtas10brevised.pdf
I see... This is a different approach to stochastic analysis, which
requires modifications to the scheduler.

In the analysis I mentioned, you still enforce a maximum runtime C every
period P, but C can be smaller than the WCET of the task. If C is larger
than the average execution time, you can use queuing theory to find the
probability to miss a deadline (or, the probability to finish a job in a
time x * P).


Luca

2010-11-12 18:07:56

by Tommaso Cucinotta

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

Il 12/11/2010 18:41, Luca Abeni ha scritto:
>
>> algorithm with resource reservation. It explicitly allows for deadline
>> misses, but requires the tardiness of those misses to be bounded, ie.
>> the UNC soft real-time definition.
>>
>> 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.
>
> [...]
> BTW, sorry for the shameless plug, but even with the current
> SCHED_DEADLINE you are not forced to dimension the runtime using the
> WCET. You can use some stochastic analysis, providing probabilistic
> deadline guarantees. See (for example) "QoS Guarantee Using
> Probabilistic Deadlines"
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7683&rep=rep1&type=pdf
>
> and "Stochastic analysis of a reservation based system"
> http://www.computer.org/portal/web/csdl/doi?doc=doi/10.1109/IPDPS.2001.925049
>
> (sorry, this is not easy to download... But I can provide a copy if
> you are interested).
Thanks, Luca, for supporting the viewpoint. I also repeated this
multiple times, during the LPC as well.

Let me underline a few key points, also about the technique suggested by
Zijlstra:

-) the specification of a budget every period may be exploited for
providing deterministic guarantees to applications, if the budget =
WCET, as well as probabilistic guarantees, if the budget < WCET. For
example, what we do in many of our papers is to set budget = to some
percentile/quantile of the observed computation time distribution,
especially in those cases in which there are isolated peaks of
computation times which would cause an excessive under-utilization of
the system (these are ruled out by the percentile-based allocation); I
think this is a way of reasoning that can be easily understood and used
by developers;

-) setting a budget equal to (or too close to) the average computation
time is *bad*, because the is almost in a meta-stable condition in which
its response-time may easily grow uncontrolled;

-) same thing applies to admitting tasks in the system: if you only
ensure that the sum of average/expected bandwidths < system capacity,
then the whole system is at risk of having uncontrolled and arbitrarily
high peak delays, but from a theoretical viewpoint it is still a
"stable" system; this is not a condition you want to have in a sane
real-time scenario;

-) if you want to apply the Mills & Anderson's rule for controlling the
bound on the tardiness percentiles, as in that paper (A Stochastic
Framework for Multiprocessor
Soft Real-Time Scheduling), then I can see 2 major drawbacks:
a) you need to compute the "\psi" in order to use the "Corollary 10"
of that paper, but that quantity needs to solve a LP optimization
problem (see also the example in Section 6); the \psi can be used in Eq.
(36) in order to compute the *expected tardiness*;
b) unfortunately, the expected tardiness is hardly the quantity of
interest for any concrete real-time application, where some percentile
of the tardiness distribution may be much more important; therefore, you
are actually interested in Eq. (37) for computing the q-th percentile of
the tardiness. Unfortunately, such last bound is provided through the
Chebychev (or Markov, or whatever it is called) inequality simply from
the expected average, and this bound is well-known to be so conservative
(a 99% percentile is basically hundred times the average). The
consequence is that you would end-up to actually admit very few tasks as
compared to what actually fits into the system.

Please, understand me: I don't want to say that that particular
technique is not useful, but I'd like simply to stress that such
policies might just belong to the user-space. If you really want, you
can disable *any* type of admission control at the kernel-level, and you
can disable *any* kind of budget enforcement, and just trust the
user-space to have deployed the proper/correct number & type of tasks
into your embedded RT platform.

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

2010-11-12 18:57:14

by Dario Faggioli

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

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

--
<<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]


Attachments:
signature.asc (198.00 B)
This is a digitally signed message part

2010-11-12 19:08:03

by Dario Faggioli

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Fri, 2010-11-12 at 19:07 +0100, Tommaso Cucinotta wrote:
> Let me underline a few key points, also about the technique suggested by
> Zijlstra:
>
> [...]
>
> I can see 2 major drawbacks:
> a) you need to compute the "\psi" in order to use the "Corollary 10"
> of that paper, but that quantity needs to solve a LP optimization
> problem (see also the example in Section 6); the \psi can be used in Eq.
> (36) in order to compute the *expected tardiness*;
>
> [...]
>
Wow man! You really know what "give us details" means, don't you? :-PP

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]


Attachments:
signature.asc (198.00 B)
This is a digitally signed message part

2010-11-13 00:43:52

by Peter Zijlstra

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Fri, 2010-11-12 at 19:07 +0100, Tommaso Cucinotta wrote:
> Il 12/11/2010 18:41, Luca Abeni ha scritto:
> >
> >> algorithm with resource reservation. It explicitly allows for deadline
> >> misses, but requires the tardiness of those misses to be bounded, ie.
> >> the UNC soft real-time definition.
> >>
> >> 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.
> >
> > [...]
> > BTW, sorry for the shameless plug, but even with the current
> > SCHED_DEADLINE you are not forced to dimension the runtime using the
> > WCET. You can use some stochastic analysis, providing probabilistic
> > deadline guarantees. See (for example) "QoS Guarantee Using
> > Probabilistic Deadlines"
> > http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7683&rep=rep1&type=pdf
> >
> > and "Stochastic analysis of a reservation based system"
> > http://www.computer.org/portal/web/csdl/doi?doc=doi/10.1109/IPDPS.2001.925049
> >
> > (sorry, this is not easy to download... But I can provide a copy if
> > you are interested).
> Thanks, Luca, for supporting the viewpoint. I also repeated this
> multiple times, during the LPC as well.
>
> Let me underline a few key points, also about the technique suggested by
> Zijlstra:
>
> -) the specification of a budget every period may be exploited for
> providing deterministic guarantees to applications, if the budget =
> WCET, as well as probabilistic guarantees, if the budget < WCET. For
> example, what we do in many of our papers is to set budget = to some
> percentile/quantile of the observed computation time distribution,
> especially in those cases in which there are isolated peaks of
> computation times which would cause an excessive under-utilization of
> the system (these are ruled out by the percentile-based allocation); I
> think this is a way of reasoning that can be easily understood and used
> by developers;

Maybe, but I'm clearly not one of them because I'm not getting it.

> -) setting a budget equal to (or too close to) the average computation
> time is *bad*, because the is almost in a meta-stable condition in which
> its response-time may easily grow uncontrolled;

How so? Didn't the paper referenced just prove that the response time
stays bounded?

Setting it lower will of course wreak havoc, but that's what we have
bandwidth control for (implementing stochastic bandwidth control is a
whole separate fun topic though -- although I've been thinking we could
do something by lowering the max runtime every time a job overruns the
average, and limit it at 2*avg - max, if you take a simple parametrized
reduction function and compute the variability of th resulting series
you can invert that and find the reduction parameter to a given
variability).

> -) same thing applies to admitting tasks in the system: if you only
> ensure that the sum of average/expected bandwidths < system capacity,
> then the whole system is at risk of having uncontrolled and arbitrarily
> high peak delays, but from a theoretical viewpoint it is still a
> "stable" system; this is not a condition you want to have in a sane
> real-time scenario;

I'm not seeing where the unbounded comes from.

I am seeing that if you place your budget request slightly higher than
the actual average (say 1 stdev) your variability in the response time
will decrease, but at a cost of lower utilization.

> -) if you want to apply the Mills & Anderson's rule for controlling the
> bound on the tardiness percentiles, as in that paper (A Stochastic
> Framework for Multiprocessor
> Soft Real-Time Scheduling), then I can see 2 major drawbacks:
> a) you need to compute the "\psi" in order to use the "Corollary 10"
> of that paper, but that quantity needs to solve a LP optimization
> problem (see also the example in Section 6); the \psi can be used in Eq.
> (36) in order to compute the *expected tardiness*;

Right, but do we ever actually want to compute the bound? G-EDF also
incurs tardiness but we don't calculate it either. Both depend on the
full task set parameters which is not stable (nor accessible to
user-space in a meaningful manner).

> Please, understand me: I don't want to say that that particular
> technique is not useful, but I'd like simply to stress that such
> policies might just belong to the user-space. If you really want, you
> can disable *any* type of admission control at the kernel-level, and you
> can disable *any* kind of budget enforcement, and just trust the
> user-space to have deployed the proper/correct number & type of tasks
> into your embedded RT platform.

I'm very much against disabling everything and letting the user sort it,
that's basically what SCHED_FIFO does too and its a frigging nightmare.

The whole admission control and schedulability test is what makes this
thing usable. People who build closed systems can already hack their
kernel and do as they please, but for anything other than a closed
system this approach is useless.

2010-11-13 01:49:41

by Tommaso Cucinotta

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

Il 13/11/2010 01:43, Peter Zijlstra ha scritto:
> On Fri, 2010-11-12 at 19:07 +0100, Tommaso Cucinotta wrote:
>> -) the specification of a budget every period may be exploited for
>> providing deterministic guarantees to applications, if the budget =
>> WCET, as well as probabilistic guarantees, if the budget< WCET. For
>> example, what we do in many of our papers is to set budget = to some
>> percentile/quantile of the observed computation time distribution,
>> especially in those cases in which there are isolated peaks of
>> computation times which would cause an excessive under-utilization of
>> the system (these are ruled out by the percentile-based allocation); I
>> think this is a way of reasoning that can be easily understood and used
>> by developers;
> Maybe, but I'm clearly not one of them because I'm not getting it.
My fault for not having explained. Let me see if I can clarify. Let's
just consider the simple case in which application instances do not
enqueue (i.e., as soon as the application detects to have missed a
deadline, it discards the current job, as opposed to keep computing the
current job), and consider a reservation period == application period.

In such a case, if 'C' represents the (probabilistically modeled)
computation time of a job, then:

Prob{deadline hit} = Prob{enough runtime for a job instance} = Prob{C
<= runtime}.

So, if runtime is set as the q-th quantile of the `C' probability
distribution, then:

Prob{deadline hit} = Prob{C <= runtime} = q

This is true independently of what else is admitted into the system, as
far as I get my runtime guaranteed from the scheduler.

Does this now make sense ?

If, on the other hand, task instances enqueue (e.g., I keep decoding the
current frame even if I know a new frame arrived), then the probability
of deadline-hit will be lower than q, and generally speaking one can use
stochastic analysis & queueing theory techniques in order to figure out
what it actually is.
>> -) setting a budget equal to (or too close to) the average computation
>> time is *bad*, because the is almost in a meta-stable condition in which
>> its response-time may easily grow uncontrolled;
> How so? Didn't the paper referenced just prove that the response time
> stays bounded?
Here I was not referring to GEDF, but simply to the case in which we are
reserved from the kernel a budget every period (whatever the scheduling
algorithm): as the reserved budget moves from the WCET down towards the
average computation time, the response time distribution moves from a
shape entirely contained below the deadline, to a more and more flat
shape, where the probability of missing the deadline for the task
increases over and over. Roughly speaking, if the application instances
do not enqueue, then with a budget = average computation time, I would
expect a ~50% deadline miss, something which hardly is acceptable even
for soft RT applications.
If instances instead enqueue, then the situation may go much worse,
because the response-time distribution flattens with a long tail beyond
the deadline. The maximum value of it approaches +\infty with the
reserved budget approaching the average computation time.
> Setting it lower will of course wreak havoc, but that's what we have
> bandwidth control for (implementing stochastic bandwidth control is a
> whole separate fun topic though -- although I've been thinking we could
> do something by lowering the max runtime every time a job overruns the
> average, and limit it at 2*avg - max, if you take a simple parametrized
> reduction function and compute the variability of th resulting series
> you can invert that and find the reduction parameter to a given
> variability).
I'd need some more explanation, sorry, I couldn't understand what you're
proposing.

>> -) if you want to apply the Mills& Anderson's rule for controlling the
>> bound on the tardiness percentiles, as in that paper (A Stochastic
>> Framework for Multiprocessor
>> Soft Real-Time Scheduling), then I can see 2 major drawbacks:
>> a) you need to compute the "\psi" in order to use the "Corollary 10"
>> of that paper, but that quantity needs to solve a LP optimization
>> problem (see also the example in Section 6); the \psi can be used in Eq.
>> (36) in order to compute the *expected tardiness*;
> Right, but do we ever actually want to compute the bound? G-EDF also
> incurs tardiness but we don't calculate it either.
I was assuming you were proposing to keep an admission test based on
providing the parameters needed for checking whether or not a given
tardiness bound were respected. I must have misunderstood. Would you
please detail what is the test (and result in the paper) you are
thinking of using ?
>> If you really want, you
>> can disable *any* type of admission control at the kernel-level, and you
>> can disable *any* kind of budget enforcement, and just trust the
>> user-space to have deployed the proper/correct number& type of tasks
>> into your embedded RT platform.
> I'm very much against disabling everything and letting the user sort it,
> that's basically what SCHED_FIFO does too and its a frigging nightmare.
Sure, I agree. I was simply suggesting it as a last-resort option
(possibly usable by exploiting a compile-time option of the scheduler
compiling out the admission test), useful in those cases in which you do
have a user-space complex admission test that you made (or even an
off-line static analysis of your system) but the simple admission test
into the kernel would actually reject the task set, being the test
merely sufficient.

Bye,

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

2010-11-13 21:08:31

by Dario Faggioli

[permalink] [raw]
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks

On Fri, 2010-11-12 at 18:51 +0100, Peter Zijlstra wrote:
> > BTW, sorry for the shameless plug, but even with the current
> > SCHED_DEADLINE you are not forced to dimension the runtime using the
> > WCET.
>
> Yes you are, it pushes the deadline back on overrun. The idea it to
> maintain the deadline despite overrunning your budget (up to a point).
>
BTW, although I share most of Luca's and Tommaso's viewpoints,
triggering bandwidth enforcement at runtime+something instead than just
at runtime doesn't look all that bad, and should fit nicely in what we
have now, without much twisting.

It's just another way to interpret the runtime, and it seems feasible
(or at least plan-able as future feature! :-P) to me... Actually this
was exactly what I was asking and what I wanted to know. :-)

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]


Attachments:
signature.asc (198.00 B)
This is a digitally signed message part