Messages in this thread | | | Date | Mon, 31 May 2021 08:59:14 +0200 | From | luca abeni <> | Subject | Re: [PATCH v5 1/3] sched/fair: Introduce the burstable CFS controller |
| |
Hi all,
On Tue, 25 May 2021 12:46:52 +0200 Peter Zijlstra <peterz@infradead.org> wrote: [...] > > We did some compute on the probability that deadline is missed, and the expected > > boundary. These values are calculated with different number of control groups and > > variable CPU utilization when runtime is under exponential distribution, poisson > > distribution or pareto distribution. > > > > The more control groups there are, the more likely deadline is made and the smaller average > > WCET to expect. Because many equal control groups means small chance of U > 1. > > > > And the more under utilized the whole system is, the more likely deadline is made and the smaller > > average WCET to expect. > > > > More details are posted in > > https://lore.kernel.org/lkml/5371BD36-55AE-4F71-B9D7-B86DC32E3D2B@linux.alibaba.com/. > > Indeed you did; I'm a bit sad it's so hard to find papers that cover > this. When one Googles for 'Probabilistic WCET' there's a fair number of > papers about using Extreme Value Theory to estimate the traditional WCET > given measurement based input. Many from the excellent WCET track at > ECRTS.
If I understand well the context, you do not need probabilistic WCET here... If you assume to know the probability distribution of the inter-arrival times and execution times (this is what is assumed at https://lore.kernel.org/lkml/5371BD36-55AE-4F71-B9D7-B86DC32E3D2B@linux.alibaba.com/, right?), then you can use "standard" queuing theory to compute the response time distribution.
If I understand well, in the link mentioned above the response times are measured by simulating a model of the scheduler. Queuing theory can be used instead, as shown (for example) in these papers: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.7683&rep=rep1&type=pdf http://retis.sssup.it/~giorgio/paps/2001/wpdrts01.pdf (these papers consider a scheduler similar to SCHED_DEADLINE, but the approach can be easily applied to every scheduler that guarantees a runtime in a period --- I think the CFS controller falls in this category, right?) I think the burst mentioned above can be added to this queuing model; I'll have a look at this in the next days.
The problem with this approach is that the execution times of different activation of a task are considered to be independent and identically distributed (this is the infamous "IID assumption"). And this assumption is often unrealistic... The probabilistic WCET approach mentioned above allows you to analyze the behaviour of a scheduler without assuming that the execution (and/or inter-activation) times are IID.
Luca
> The thing is, the last time I attended that conference (which appears to > be almost 4 years ago :/), I'm sure I spoke to people about exactly the > thing explored here. Albeit, at the time we discussed this as a > SCHED_DEADLINE task model extension. > > Let me Cc a bunch of people that might know more..,
| |