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

[Tommaso Cucinotta]

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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/