Re: [RFC 7/8] Make GRUB a task's flag

From: Luca Abeni
Date: Fri Jan 15 2016 - 04:09:11 EST

On Fri, 15 Jan 2016 09:41:50 +0100
Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:

> On Fri, Jan 15, 2016 at 09:15:39AM +0100, Luca Abeni wrote:
> > On 01/14/2016 08:56 PM, Peter Zijlstra wrote:
> > >Something with an average runtime/budget that also puts limits on
> > >the max (say 2*avg) would be far more amenable to be exposed to
> > >unpriv tasks, except since that would directly result in an
> > >average tardiness bound this might be non-trivial to combine with
> > >tasks not opting for this.
> > I'll try to think about this... The advantage of GRUB is that a
> > theoretically sound algorithm already existed; here, we would need
> > to design the algorithm so that it does not break the
> > SCHED_DEADLINE guarantees. Anyway, this is an interesting
> > challenge, I'll work on it :)
> Didn't Baruah and Jim do the whole theory on statistical EDF? Which
> shows that if you use a statistical budget the combined distribution
> transfers to the tardiness. With stdev=0 for the budgets this
> trivially collapses to the regular EDF, since then the combined
> distribution is also stdev=0 and you get 0 tardiness (on UP).
I remember a paper by Anderson, but it was slightly different from
this... Maybe I am remembering the wrong paper... I'll check it again.

> But yes, combining the two into one scheduler is 'interesting'. I was
> thinking it would be possible with least-laxity-first, since you can
> assign the hard (stdev=0) tasks a tighter laxity bound.
> But LLF is horrendously painful to implement IIRC.
LLF would be interesting (even because if would help in implementing an
optimal SMP scheduler), but yes, it is not simple to implement (at
least, as far as I remember). I had a student working on it, who
implemented some kind of LLF approximation, but I still have to cleanup
the code and see how much useful it can be).