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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20140514125515.GK13658@twins.programming.kicks-ass.net>
Date:	Wed, 14 May 2014 14:55:15 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	"xiaofeng.yan" <xiaofeng.yan@...wei.com>
Cc:	Ingo Molnar <mingo@...hat.com>, duzhiping.du@...wei.com,
	xiaofeng.yan2012@...il.com, juri.lelli@...il.com,
	luca.abeni@...tn.it, raistlin@...ux.it, henrik@...tad.us,
	tkhai@...dex.ru, harald.gustafsson@...csson.com,
	linux-kernel@...r.kernel.org
Subject: Re: [RFD] sched/deadline: EDF dynamic quota design

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).
> 
> 



Content of type "application/pgp-signature" skipped