lkml.org 
[lkml]   [2010]   [Nov]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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



\
 
 \ /
  Last update: 2010-11-12 19:13    [W:0.090 / U:0.136 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site