Message-ID: <4628B1DF.8000400@bigpond.net.au>
Date:	Fri, 20 Apr 2007 22:28:15 +1000
From:	Peter Williams <pwil3058@...pond.net.au>
To:	Ingo Molnar <mingo@...e.hu>
CC:	linux-kernel@...r.kernel.org,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Con Kolivas <kernel@...ivas.org>,
	Nick Piggin <npiggin@...e.de>, Mike Galbraith <efault@....de>,
	Arjan van de Ven <arjan@...radead.org>,
	Thomas Gleixner <tglx@...utronix.de>, caglar@...dus.org.tr,
	Willy Tarreau <w@....eu>, Gene Heskett <gene.heskett@...il.com>
Subject: Re: [patch] CFS scheduler, v3

Peter Williams wrote:
> Ingo Molnar wrote:
>> * Peter Williams <pwil3058@...pond.net.au> wrote:
>>
>>>> - bugfix: use constant offset factor for nice levels instead of
>>>>   sched_granularity_ns. Thus nice levels work even if someone sets   
>>>> sched_granularity_ns to 0. NOTE: nice support is still naive, i'll   
>>>> address the many nice level related suggestions in -v4.
>>> I have a suggestion I'd like to make that addresses both nice and 
>>> fairness at the same time.  As I understand the basic principle 
>>> behind this scheduler it to work out a time by which a task should 
>>> make it onto the CPU and then place it into an ordered list (based on 
>>> this value) of tasks waiting for the CPU. I think that this is a 
>>> great idea [...]
>>
>> yes, that's exactly the main idea behind CFS, and thanks for the 
>> compliment :)
>>
>> Under this concept the scheduler never really has to guess: every 
>> scheduler decision derives straight from the relatively simple 
>> one-sentence (!) scheduling concept outlined above. Everything that 
>> tasks 'get' is something they 'earned' before and all the scheduler 
>> does are micro-decisions based on math with the nanosec-granularity 
>> values. Both the rbtree and nanosec accounting are a straight 
>> consequence of this too: they are the tools that allow the 
>> implementation of this concept in the highest-quality way. It's 
>> certainly a very exciting experiment to me and the feedback 'from the 
>> field' is very promising so far.
>>
>>> [...] and my suggestion is with regard to a method for working out 
>>> this time that takes into account both fairness and nice.
>>>
>>> First suppose we have the following metrics available in addition to 
>>> what's already provided.
>>>
>>> rq->avg_weight_load /* a running average of the weighted load on the 
>>> CPU */ p->avg_cpu_per_cycle /* the average time in nsecs that p 
>>> spends on the CPU each scheduling cycle */
>>
>> yes. rq->nr_running is really just a first-level approximation of 
>> rq->raw_weighted_load. I concentrated on the 'nice 0' case initially.
>>
>>> I appreciate that the notion of basing the expected wait on the 
>>> task's average cpu use per scheduling cycle is counter intuitive but 
>>> I believe that (if you think about it) you'll see that it actually 
>>> makes sense.
>>
>> hm. So far i tried to not do any statistical approach anywhere: the 
>> p->wait_runtime metric (which drives the task ordering) is in essence 
>> an absolutely precise 'integral' of the 'expected runtimes' that the 
>> task observes and hence is a precise "load-average as observed by the 
>> task"
> 
> To me this is statistics :-)
> 
>> in itself. Every time we base some metric on an average value we 
>> introduce noise into the system.
>>
>> i definitely agree with your suggestion that CFS should use a 
>> nice-scaled metric for 'load' instead of the current rq->nr_running, 
>> but regarding the basic calculations i'd rather lean towards using 
>> rq->raw_weighted_load. Hm?
> 
> This can result in jerkiness (in my experience) but using the smoothed 
> version is certainly something that can be tried later rather than 
> sooner.  Perhaps just something to bear in mind as a solution to 
> "jerkiness" if it manifests.
> 
>>
>> your suggestion concentrates on the following scenario: if a task 
>> happens to schedule in an 'unlucky' way and happens to hit a busy 
>> period while there are many idle periods. Unless i misunderstood your 
>> suggestion, that is the main intention behind it, correct?
> 
> You misunderstand (that's one of my other schedulers :-)).  This one's 
> based on the premise that if everything happens as the task expects it 
> will get the amount of CPU bandwidth (over this short period) that it's 
> entitled to.  In reality, sometimes it will get more and sometimes less 
> but on average it should get what it deserves. E.g. If you had two tasks 
> with equal nice and both had demands of 90% of a CPU you'd expect them 
> each to get about half of the CPU bandwidth.  Now suppose that one of 
> them uses 5ms of CPU each time it got onto the CPU and the other uses 
> 10ms.  If these two tasks just round robin with each other the likely 
> outcome is that the one with the 10ms bursts will get twice as much CPU 
> as the other but my proposed method should prevent and cause them to get 
> roughly the same amount of CPU.  (I believe this was a scenario that 
> caused problems with O(1) and required a fix at some stage?)
> 
> BTW this has the advantage that the decay rate used in calculating the 
> task's statistics can be used to control how quickly the scheduler 
> reacts to changes in the task's behaviour.

I think that, with this model, if the current task hasn't surrendered 
the CPU when the next task on the queue's "on CPU" time arrives that the 
current task should be pre-empted in favour of that task.  I'm not sure 
what would be the best way to implement this.

Peter
-- 
Peter Williams                                   pwil3058@...pond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists