Re: [RFD] sched/deadline: EDF dynamic quota design

[Peter Zijlstra]

On Wed, May 14, 2014 at 01:32:45PM +0200, Peter Zijlstra wrote:
> On Wed, May 14, 2014 at 06:43:38PM +0800, xiaofeng.yan wrote:
> > Hi all,
> > 
> > We design dynamic quota function based on current EDF schedule .
> > Wehave realized this dynamic quota design and get good performance in the actual scene.
> > The impalement for this function is very strong connected with production line requirement.
> > In some implementations, the current design in product could be be accepted by community,
> > such as beyond the total bandwidth limitations.
> > So we design some parts again.
> > If you want to review our current implements in product, I will send our patches and test result.
> > We hope to push it to the main line. Could you give me suggestion whether it can be accepted or not?
> > We will be very grateful for your suggestion.
> 
> At the very least you could've Cc'ed the people who actually wrote the
> EDF stuff :-/

Also, Cc lkml, left the rest of the msg intact as clearly people haven't
had a copy yet.

> > The design principle is as follows:
> > 
> > 
> > ------------------EDF Dynamic Quota Design------------------
> > 
> > * Current EDF defect
> >   EDF tasks' bandwidth is fixed currently. they could not adjust
> >   their quota whenever they are busy or idle.
> > 
> > * The scene for dynamic quota
> >   Currently, we have the scenarios which need to adjust tasks'
> >   quota dynamically. Such as, the network's workload fluctuates when
> >   forwarding the packets, which results in imbalance. Busy task should
> >   increase quota, and idle task should reduce quota.
> >   It is beneficial to increase the processing ability of the business.
> > 
> > * Dynamic quota idea
> >   We add the dynamic quota function based on current EDF schedule.
> >   The principle is as follows:
> >   The total bandwidth of EDF tasks is fixed during running.
> >   Idle tasks release left bandwidth to the global bandwidth pool, and
> >   busy tasks get some quota from the global pool.
> > 
> > * Example.
> >   Three tasks: T1,T2,T3. Their initial status is as follows,
> >   T1(200us,500us,500us)
> >   T2(200us,500us,500us)
> >   T3(200us,500us,500us)
> > 
> >   At time t1, the tasks' running status is as follows,
> >   T1(200us,500us,500us)
> >   T2(100us,500us,500us)
> >   T3(200us,500us,500us)
> >   Busy tasks: T1,T3
> >   Idle task:  T2
> >   Bandwidth pool: 20%
> > 
> >   Now, there are 20% quota in the bandwidth pool, T1 or T3 get 5% quota
> >   (adjustable) from the bandwidth pool when they enter run-queue.
> >   Then, the status is as follows:
> >   T1(225us,500us,500us)
> >   T2(100us,500us,500us)
> >   T3(225us,500us,500us)
> >   Bandwidth pool: 10%
> > 
> >   Busy tasks could get the quota when the bandwidth pool is not empty.
> > 
> > ----------------------------------------------------------------------------------------
> 
> Yeah, not sure that's sound. But I'll leave that to others.
> 
> So there have been papers on how if you transform the runtime into an
> avg the tardiness also turns into an avg and remains bounded.
> 
> Now, you still have to guarantee your individual tasks respect the avg,
> otherwise the tardiness guarantees are out the window along with it.
> 
> I've not thought through your proposal to see if it maintains this
> guarantee -- but seeing how you don't talk about guarantees at all I
> fear the worst.
> 
> Another point is that 'avg' or 'dynamic' tasks should co-exist with the
> normal fixed runtime tasks (ideally) without affecting the performance
> of the normal tasks (too much).
> 
> Your proposal also doesn't cover this.
> 
> There have also been proposals to turn the CBS into a 'soft' CBS and
> instead of hard throttling allow the task to continue executing at a
> lower class (throttle in effect turns into a switch to SCHED_NORMAL, and
> unthrottle restores it to SCHED_DEADLINE).
> 
>

Attachment: pgphmmqqfsP4h.pgp
Description: PGP signature