[patch] CFS scheduler, -v6

[patch] CFS scheduler, -v6

[Ingo Molnar]

i'm pleased to announce release -v6 of the CFS scheduler patchset. The 
main goal of CFS is to implement "high quality desktop scheduling" as 
well as technically possible.

The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be downloaded 
from the usual place:

    http://redhat.com/~mingo/cfs-scheduler/

i got lots of -v5 feedback (thanks and please keep the reports coming!) 
so the -v6 release includes many bugfixes and improvements:

    19 files changed, 317 insertions(+), 744 deletions(-)

the biggest user-visible changes in -v6 are various refinements to the 
precise-scheduling infrastructure that should result in generally better 
interactivity and a smoother desktop. In particular a number of "movie 
playback lags/stutters" and "firefox lags under load" type of 
regressions have been resolved. (Please re-report any regression that 
might not be fixed yet.)

Changes since -v5:

 - feature: increase the preemption granularity value on SMP systems. 
   Idea and code comes from the SD scheduler of Con Kolivas, with Con's
   kind permission. (thanks Con!)

 - fix: the "privileged_nice_level=X" boot option should convert signed
   integers. (Mike Galbraith)

 - build fix: yield_to unistd.h fix (Srivatsa Vaddagiri)

 - build fix: CONFIG_HEADERS_CHECK complained about sched.h.
   (reported by Zach Carter)

 - build fix: normalize_rt_tasks() UP build fix. (Mike Galbraith)

 - interactivity fix: sched_clock() accuracy fixes. This should resolve 
   certain types of interactivity regressions reported on systems that
   change their CPU frequencies. (mainly laptops)

 - default settings tweak: changed the X renicing default from -19 to 
   -10, based on tester feedback. (Might still be too much - more 
   feedback is needed.)

 - feature: introduced "wakeup granularity" and added the 
   /proc/sys/kernel/sched_wakeup_granularity_ns tunable, set to 0 by 
   default for now. This is now distinct from the sched_granularity_ns
   'preemption granularity' property of the scheduler - allowing a
   more agressive increase in the preemption granularity without
   jeopardizing interactivity.

 - debugging feature: SysRq-T now also shows the /proc/sched_debug 
   output - useful to generate a dump of all relevant scheduler state in 
   one easy step.

 - debugging feature: make SysRq-Nice normalize negative nice level 
   tasks too and reset the CFS state.

 - debugging: extend /proc/sched_debug with a few more clock related 
   fields, to be able to better debug problems caused by unstable 
   clocks.

 - upstream fix: SysRq-T should show runnable tasks

 - optimization: introduce p->load_shift to simplify the 64-bit math on 
   32-bit systems and avoid expensive 64-bit divisions.

 - cleanup: renamed CONFIG_RENICE_X to CONFIG_BOOST_X.

 - cleanup: got rid of more unused code from sched.c

 - lots of other smaller stuff i forgot :)

As usual, any sort of feedback, bugreport, fix and suggestion is more 
than welcome,

	Ingo

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Wednesday 25 April 2007, Ingo Molnar wrote:
>i'm pleased to announce release -v6 of the CFS scheduler patchset. The
>main goal of CFS is to implement "high quality desktop scheduling" as
>well as technically possible.
>
>The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be downloaded
>from the usual place:
>
>    http://redhat.com/~mingo/cfs-scheduler/
>
It hasn't made it to this server yet, and its 22:14 EDT here.

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Doing gets it done.

Re: [patch] CFS scheduler, -v6

[Nick Piggin]

On Wed, Apr 25, 2007 at 11:47:04PM +0200, Ingo Molnar wrote:
> 
> i'm pleased to announce release -v6 of the CFS scheduler patchset. The 
> main goal of CFS is to implement "high quality desktop scheduling" as 
> well as technically possible.
> 
> The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be downloaded 
> from the usual place:
> 
>     http://redhat.com/~mingo/cfs-scheduler/
> 
> i got lots of -v5 feedback (thanks and please keep the reports coming!) 
> so the -v6 release includes many bugfixes and improvements:
> 
>     19 files changed, 317 insertions(+), 744 deletions(-)
> 
> the biggest user-visible changes in -v6 are various refinements to the 
> precise-scheduling infrastructure that should result in generally better 
> interactivity and a smoother desktop. In particular a number of "movie 
> playback lags/stutters" and "firefox lags under load" type of 
> regressions have been resolved. (Please re-report any regression that 
> might not be fixed yet.)
> 
> Changes since -v5:
> 
>  - feature: increase the preemption granularity value on SMP systems. 
>    Idea and code comes from the SD scheduler of Con Kolivas, with Con's
>    kind permission. (thanks Con!)
> 
>  - fix: the "privileged_nice_level=X" boot option should convert signed
>    integers. (Mike Galbraith)
> 
>  - build fix: yield_to unistd.h fix (Srivatsa Vaddagiri)
> 
>  - build fix: CONFIG_HEADERS_CHECK complained about sched.h.
>    (reported by Zach Carter)
> 
>  - build fix: normalize_rt_tasks() UP build fix. (Mike Galbraith)
> 
>  - interactivity fix: sched_clock() accuracy fixes. This should resolve 
>    certain types of interactivity regressions reported on systems that
>    change their CPU frequencies. (mainly laptops)
> 
>  - default settings tweak: changed the X renicing default from -19 to 
>    -10, based on tester feedback. (Might still be too much - more 
>    feedback is needed.)
> 
>  - feature: introduced "wakeup granularity" and added the 
>    /proc/sys/kernel/sched_wakeup_granularity_ns tunable, set to 0 by 
>    default for now. This is now distinct from the sched_granularity_ns
>    'preemption granularity' property of the scheduler - allowing a
>    more agressive increase in the preemption granularity without
>    jeopardizing interactivity.
> 
>  - debugging feature: SysRq-T now also shows the /proc/sched_debug 
>    output - useful to generate a dump of all relevant scheduler state in 
>    one easy step.
> 
>  - debugging feature: make SysRq-Nice normalize negative nice level 
>    tasks too and reset the CFS state.
> 
>  - debugging: extend /proc/sched_debug with a few more clock related 
>    fields, to be able to better debug problems caused by unstable 
>    clocks.
> 
>  - upstream fix: SysRq-T should show runnable tasks

BTW. can you send this upstream? It is very annoying how it currently works,
and I've had more than one bug that required seeing runnable tasks in order
to diagnose and fix...

Re: [patch] CFS scheduler, -v6

[Andrew Morton]

On Thu, 26 Apr 2007 05:29:27 +0200 Nick Piggin <npiggin@suse.de> wrote:

> >  - upstream fix: SysRq-T should show runnable tasks
> 
> BTW. can you send this upstream? It is very annoying how it currently works,
> and I've had more than one bug that required seeing runnable tasks in order
> to diagnose and fix...

I have it.  I'm just waiting to see if Linus took it.  Seems not.

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Wed, Apr 25, 2007 at 11:47:04PM +0200, Ingo Molnar wrote:
>>  - upstream fix: SysRq-T should show runnable tasks

On Thu, Apr 26, 2007 at 05:29:27AM +0200, Nick Piggin wrote:
> BTW. can you send this upstream? It is very annoying how it currently works,
> and I've had more than one bug that required seeing runnable tasks in order
> to diagnose and fix...

There are other things that should go upstream separately. The
init/main.c comment fix for one. I'd even argue that scheduler classes
should be done separately from and prior to the specific cfs policy.


-- wli

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Nick Piggin <npiggin@suse.de> wrote:

> >  - upstream fix: SysRq-T should show runnable tasks
> 
> BTW. can you send this upstream? It is very annoying how it currently 
> works, and I've had more than one bug that required seeing runnable 
> tasks in order to diagnose and fix...

yeah, sent it to lkml yesterday, a few minutes after having figured it 
out.

	Ingo

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> i'm pleased to announce release -v6 of the CFS scheduler patchset. The 
> main goal of CFS is to implement "high quality desktop scheduling" as 
> well as technically possible.
> 
> The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be 
> downloaded from the usual place:
> 
>     http://redhat.com/~mingo/cfs-scheduler/

i've also uploaded the -v6 patch against v2.6.21.

	Ingo

Re: [patch] CFS scheduler, -v6

[Redeeman]

On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
<snip>
> As usual, any sort of feedback, bugreport, fix and suggestion is more 
> than welcome,

well, from my experiences with cfs on workstation/desktop, on amd64
2ghz, cfs doesent measure up to SD at all.

audio skips easily, with or without reniced X, and games are not as
smooth. also it seems to be much lower throughput. vanilla seems much
better by comparisin.
> 
> 	Ingo
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Thursday 26 April 2007, Redeeman wrote:
>On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
><snip>
>
>> As usual, any sort of feedback, bugreport, fix and suggestion is more
>> than welcome,
>
>well, from my experiences with cfs on workstation/desktop, on amd64
>2ghz, cfs doesent measure up to SD at all.
>
>audio skips easily, with or without reniced X, and games are not as
>smooth. also it seems to be much lower throughput. vanilla seems much
>better by comparisin.

Well, I don't generally feel as if the few stutters I just heard in a cbs news 
story I just played were anything but dsl glitches here. xmms, playing high 
quality (Q7) oggs from my own drive are dead smoothly done.  nbc did want to 
let me play anything because I have adblock enabled, and neither did abc but 
their anims played nicely, fox news smoothly played everything I clicked on.

The only problem I've had so far is with a proprietary daemon from belkin, 
which took about 10 kills and restarts after I'd booted to 2.6.21-CFS-v6 
before it quit wanting a steady 40% of the cpu when it was running.  Now it 
only does that when the bulldog gui is running.  That's not normal either, 
but getting fixes out of belkin is like breeding elephants, lots of yelling 
and screaming and it takes 22 months to get results.  My next ups will NOT be 
a belkin.

X is not reniced here, but I did run kmail up to -5.

Compared to mainline?  I still think this is a 100% keeper for desktop users 
like me.

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Two heads are more numerous than one.

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Thu, 2007-04-26 at 16:06 +0200, Redeeman wrote:
> On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
> <snip>
> > As usual, any sort of feedback, bugreport, fix and suggestion is more 
> > than welcome,
> 
> well, from my experiences with cfs on workstation/desktop, on amd64
> 2ghz, cfs doesent measure up to SD at all.
> 
> audio skips easily, with or without reniced X, and games are not as
> smooth. also it seems to be much lower throughput. vanilla seems much
> better by comparisin.

Can you give some details wrt these audio skips?  What are you doing,
and what is your config.  I don't see audio skips at all, unless I
intentionally beg for it via massive renice of X + a _very_ heavy CPU
client, and even then, only on UP (logical, one exec path).

	-Mike

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
> i got lots of -v5 feedback (thanks and please keep the reports coming!) 

You asked for it :)

CFS breaks the PI support for futexes. Fix below.

	tglx

Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -3234,6 +3234,12 @@ void rt_mutex_setprio(struct task_struct
 	on_rq = p->on_rq;
 	if (on_rq)
 		dequeue_task(rq, p, 0);
+
+	if (rt_prio(prio))
+		p->sched_class = &rt_sched_class;
+	else
+		p->sched_class = &fair_sched_class;
+
 	p->prio = prio;
 
 	if (on_rq) {

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
> > i got lots of -v5 feedback (thanks and please keep the reports coming!) 
> 
> You asked for it :)
> 
> CFS breaks the PI support for futexes. Fix below.

thanks, applied! :-) (Did you manage to test whether PI works?)

	Ingo

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Thu, 2007-04-26 at 21:35 +0200, Ingo Molnar wrote:
> * Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> > On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
> > > i got lots of -v5 feedback (thanks and please keep the reports coming!) 
> > 
> > You asked for it :)
> > 
> > CFS breaks the PI support for futexes. Fix below.
> 
> thanks, applied! :-) (Did you manage to test whether PI works?)

Yup, all tests of the kernel tester scripts work as well as the glibc
tests.

	tglx

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Thu, 2007-04-26 at 10:41 -0400, Gene Heskett wrote:
<snip>
> 
> Compared to mainline?  I still think this is a 100% keeper for desktop users 
> like me.

Here its alot worse, just playing an ogg with ogg123 even without
anything reniced (X is 0), just pressing a link in konqueror can make
audio skip (ogg123 fails to fill the alsa buffer, and thus it skips).
this is something that simply does not happen for me on vanilla,
staircase or SD.

it just doesent seem to work properly..

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> > thanks, applied! :-) (Did you manage to test whether PI works?)
> 
> Yup, all tests of the kernel tester scripts work as well as the glibc 
> tests.

great! I think this fix was the last one needed to make CFS fully 
compatible with the vanilla scheduler.

	Ingo

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Thursday 26 April 2007, Kasper Sandberg wrote:
>On Thu, 2007-04-26 at 10:41 -0400, Gene Heskett wrote:
><snip>
>
>> Compared to mainline?  I still think this is a 100% keeper for desktop
>> users like me.
>
>Here its alot worse, just playing an ogg with ogg123 even without
>anything reniced (X is 0), just pressing a link in konqueror can make
>audio skip (ogg123 fails to fill the alsa buffer, and thus it skips).
>this is something that simply does not happen for me on vanilla,
>staircase or SD.
>
>it just doesent seem to work properly..

I wish I could throw a clue about what I might be doing different, but every 
skip I've heard so far has been an mplayer artifact due to a spastic dls 
connection.  Every locally sourced audio or avi type file I've tried so far 
has worked very smoothly.

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
PIZZA!!

Re: [patch] CFS scheduler, -v6

[Con Kolivas]

On Friday 27 April 2007 00:41, Gene Heskett wrote:
> On Thursday 26 April 2007, Redeeman wrote:
> >On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
> ><snip>
> >
> >> As usual, any sort of feedback, bugreport, fix and suggestion is more
> >> than welcome,
> >
> >well, from my experiences with cfs on workstation/desktop, on amd64
> >2ghz, cfs doesent measure up to SD at all.
> >
> >audio skips easily, with or without reniced X, and games are not as
> >smooth. also it seems to be much lower throughput. vanilla seems much
> >better by comparisin.

That's a pretty bad regression for CFS to not even play audio without 
stuttering.

> Well, I don't generally feel as if the few stutters I just heard in a cbs
> news story I just played were anything but dsl glitches here. xmms, playing
> high quality (Q7) oggs from my own drive are dead smoothly done.  nbc did
> want to let me play anything because I have adblock enabled, and neither
> did abc but their anims played nicely, fox news smoothly played everything
> I clicked on.
>
> The only problem I've had so far is with a proprietary daemon from belkin,
> which took about 10 kills and restarts after I'd booted to 2.6.21-CFS-v6
> before it quit wanting a steady 40% of the cpu when it was running.  Now it
> only does that when the bulldog gui is running.  That's not normal either,
> but getting fixes out of belkin is like breeding elephants, lots of yelling
> and screaming and it takes 22 months to get results.  My next ups will NOT
> be a belkin.
>
> X is not reniced here, but I did run kmail up to -5.
>
> Compared to mainline?  I still think this is a 100% keeper for desktop
> users like me.

Hi Gene

Have you given up on SD testing then since it's stable and CFS is still shiny 
and new (and written by Ingo) therefore it must be better? 

-- 
-ck

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Thursday 26 April 2007, Con Kolivas wrote:
>On Friday 27 April 2007 00:41, Gene Heskett wrote:
>> On Thursday 26 April 2007, Redeeman wrote:
>> >On Wed, 2007-04-25 at 23:47 +0200, Ingo Molnar wrote:
>> ><snip>
>> >
>> >> As usual, any sort of feedback, bugreport, fix and suggestion is more
>> >> than welcome,
>> >
>> >well, from my experiences with cfs on workstation/desktop, on amd64
>> >2ghz, cfs doesent measure up to SD at all.
>> >
>> >audio skips easily, with or without reniced X, and games are not as
>> >smooth. also it seems to be much lower throughput. vanilla seems much
>> >better by comparisin.
>
>That's a pretty bad regression for CFS to not even play audio without
>stuttering.
>
>> Well, I don't generally feel as if the few stutters I just heard in a cbs
>> news story I just played were anything but dsl glitches here. xmms,
>> playing high quality (Q7) oggs from my own drive are dead smoothly done. 
>> nbc did want to let me play anything because I have adblock enabled, and
>> neither did abc but their anims played nicely, fox news smoothly played
>> everything I clicked on.
>>
>> The only problem I've had so far is with a proprietary daemon from belkin,
>> which took about 10 kills and restarts after I'd booted to 2.6.21-CFS-v6
>> before it quit wanting a steady 40% of the cpu when it was running.  Now
>> it only does that when the bulldog gui is running.  That's not normal
>> either, but getting fixes out of belkin is like breeding elephants, lots
>> of yelling and screaming and it takes 22 months to get results.  My next
>> ups will NOT be a belkin.
>>
>> X is not reniced here, but I did run kmail up to -5.
>>
>> Compared to mainline?  I still think this is a 100% keeper for desktop
>> users like me.
>
>Hi Gene
>
>Have you given up on SD testing then since it's stable and CFS is still
> shiny and new (and written by Ingo) therefore it must be better?

Not necessarily Con.  Do you have a fresh one for 2.6.21?

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Been Transferred Lately?

Re: [patch] CFS scheduler, -v6

[Con Kolivas]

On Friday 27 April 2007 10:39, Gene Heskett wrote:
> Not necessarily Con.  Do you have a fresh one for 2.6.21?

Since people get nervous about any rejects here is an (otherwise identical) 
patch for 2.6.21

http://ck.kolivas.org/patches/staircase-deadline/2.6.21-sd-0.46.patch

-- 
-ck

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Thursday 26 April 2007, Con Kolivas wrote:
>On Friday 27 April 2007 10:39, Gene Heskett wrote:
>> Not necessarily Con.  Do you have a fresh one for 2.6.21?
>
>Since people get nervous about any rejects here is an (otherwise identical)
>patch for 2.6.21
>
>http://ck.kolivas.org/patches/staircase-deadline/2.6.21-sd-0.46.patch

Thanks, I'll try to give it some cpu time in the next day.

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Our informal mission is to improve the love life of operators worldwide.
		-- Peter Behrendt, president of Exabyte

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Thu, 2007-04-26 at 22:09 +0200, Kasper Sandberg wrote:
> On Thu, 2007-04-26 at 10:41 -0400, Gene Heskett wrote:
> <snip>
> > 
> > Compared to mainline?  I still think this is a 100% keeper for desktop users 
> > like me.
> 
> Here its alot worse, just playing an ogg with ogg123 even without
> anything reniced (X is 0), just pressing a link in konqueror can make
> audio skip (ogg123 fails to fill the alsa buffer, and thus it skips).

What arguments are you passing to ogg123?  I'm creating some ogg files
right now, and would like to reproduce these skips to see why they're
happening if possible.

	-Mike

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Fri, 2007-04-27 at 06:02 +0200, Mike Galbraith wrote:
> On Thu, 2007-04-26 at 22:09 +0200, Kasper Sandberg wrote:
> > On Thu, 2007-04-26 at 10:41 -0400, Gene Heskett wrote:
> > <snip>
> > > 
> > > Compared to mainline?  I still think this is a 100% keeper for desktop users 
> > > like me.
> > 
> > Here its alot worse, just playing an ogg with ogg123 even without
> > anything reniced (X is 0), just pressing a link in konqueror can make
> > audio skip (ogg123 fails to fill the alsa buffer, and thus it skips).
> 
> What arguments are you passing to ogg123?  I'm creating some ogg files
> right now, and would like to reproduce these skips to see why they're
> happening if possible.

Well, I can't reproduce any skips with my config.  That doesn't mean
anything wrt _your_ skips of course.  Maybe it's a config or hardware
difference.  With my 3GHz P4 low latency desktop full preempt setup,
ogg123 works absolutely flawlessly (using default settings) both in UP
and SMP configurations, even under quite hefty load.

I do get some ALSA gripes when doing heavy IO...

root@Homer: grep ALSA /ogg123.log
Audio Device:   Advanced Linux Sound Architecture (ALSA) output
ALSA: underrun, at least 0ms.04:49.37  (103.0 kbps)  Output Buffer  12.5%
ALSA: underrun, at least 0ms.04:15.20  (102.1 kbps)  Output Buffer  12.5%
ALSA: underrun, at least 0ms.03:30.80  (126.7 kbps)  Output Buffer  96.9%
ALSA: underrun, at least 0ms.05:15.93  ( 99.9 kbps)  Output Buffer  25.0%

...but no audible effect whatsoever.  Heavy IO to my very full and
likely fragmented ext3 filesystem is a very big problem here no matter
what CPU or IO scheduler I'm using.
 
As I write this, I've got a heavy kernel build running, and was browsing
around with firefox and konqueror, checking mail etc etc as it was
running.  I definitely feel the load (no surprise;), but ogg123 is
delivering dropout free audio.  (this is the UP cfs-v6 kernel)

top - 07:34:56 up  1:00, 13 users,  load average: 35.92, 34.72, 24.21
Tasks: 294 total,  31 running, 263 sleeping,   0 stopped,   0 zombie
Cpu(s): 93.8%us,  6.2%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
24878 root      20   0 28628  24m 4176 R  3.5  2.5   0:01.56 cc1
25236 root      20   0 22608  18m 3964 R  3.5  1.9   0:00.47 cc1
25385 root      20   0 17184  11m 2196 R  3.5  1.2   0:00.23 cc1
25405 root      20   0 15996  10m 2196 R  3.5  1.0   0:00.18 cc1
24668 root      20   0 35828  31m 4152 R  3.0  3.1   0:02.07 cc1
24763 root      20   0 36420  32m 4160 R  3.0  3.2   0:01.86 cc1
24976 root      20   0 26880  23m 4156 R  3.0  2.3   0:01.23 cc1
25054 root      20   0 25016  21m 4140 R  3.0  2.1   0:01.00 cc1
25058 root      20   0 28272  24m 4140 R  3.0  2.4   0:00.97 cc1
25090 root      20   0 27384  23m 4140 R  3.0  2.4   0:00.94 cc1
25123 root      20   0 26068  22m 4120 R  3.0  2.2   0:00.89 cc1
25270 root      20   0 22584  18m 3976 R  3.0  1.8   0:00.42 cc1
25303 root      20   0 18232  14m 4024 R  3.0  1.5   0:00.33 cc1
25310 root      20   0 20436  15m 2196 R  3.0  1.5   0:00.32 cc1
25348 root      20   0 19176  14m 3948 R  3.0  1.5   0:00.29 cc1
25349 root      20   0 19408  14m 2196 R  3.0  1.4   0:00.29 cc1
25360 root      20   0 19432  13m 2196 R  3.0  1.4   0:00.28 cc1
25395 root      20   0 17136  11m 2196 R  3.0  1.1   0:00.21 cc1
25426 root      20   0 12608 7732 2184 R  3.0  0.7   0:00.10 cc1
25432 root      20   0 12528 6936 2184 R  3.0  0.7   0:00.09 cc1
23766 root      20   0 44116  39m 4104 R  2.5  4.0   0:03.74 cc1
25124 root      20   0  6380 4084  972 R  2.5  0.4   0:00.05 as
25183 root      20   0 24948  20m 4052 R  2.5  2.1   0:00.73 cc1
25363 root      20   0 17156  13m 3820 S  2.5  1.3   0:00.26 cc1
25445 root      20   0 10268 5404 2140 R  2.5  0.5   0:00.05 cc1
25452 root      20   0 10096 3680 1384 R  1.5  0.4   0:00.03 cc1
 5355 root      15  -5  185m  26m 4716 S  1.0  2.6   3:11.71 Xorg
25184 root      20   0  5576 3284  848 R  1.0  0.3   0:00.02 as
 6396 root      20   0 14960 3100 2168 R  0.5  0.3   0:12.50 ogg123

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Kasper Sandberg <lkml@metanurb.dk> wrote:

> > Compared to mainline?  I still think this is a 100% keeper for 
> > desktop users like me.
> 
> Here its alot worse, just playing an ogg with ogg123 even without 
> anything reniced (X is 0), just pressing a link in konqueror can make 
> audio skip (ogg123 fails to fill the alsa buffer, and thus it skips).

update for lkml readers: this is some really 'catastrophic' condition 
triggering on your box. Here ogg123 just never skips on an older 750 MHz 
box, which is 4-5 times slower than your 2GHz box - while i have _fourty 
nice-0 infinite loops_ running. I.e. at this clearly ridiculous load, at 
just 2.5% of CPU time ogg123 is just chugging along nicely and never 
leaves out a beat.

i'll try to figure out what is happening on your box. I asked for your 
.config off-list (which you already sent me) and i'll try to reproduce 
your problems. One thing i noticed: when ogg123 plays with 'esd' also 
running on the system, it starts skipping really badly - but it does so 
under all schedulers i tried (cfs, sd, vanilla).

	Ingo

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> update for lkml readers: this is some really 'catastrophic' condition 
> triggering on your box. Here ogg123 just never skips on an older 750 
> MHz box, which is 4-5 times slower than your 2GHz box - while i have 
> _fourty nice-0 infinite loops_ running. I.e. at this clearly 
> ridiculous load, at just 2.5% of CPU time ogg123 is just chugging 
> along nicely and never leaves out a beat.

Kasper, just to exclude the possibility that this is somehow related to 
IO scheduling, could you copy the OGG file over to /dev/shm and play it 
from there? Do you still get the bad skips?

	Ingo

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Fri, Apr 27, 2007 at 01:53:44PM +0200, Ingo Molnar wrote:
> i'll try to figure out what is happening on your box. I asked for your 
> .config off-list (which you already sent me) and i'll try to reproduce 
> your problems. One thing i noticed: when ogg123 plays with 'esd' also 
> running on the system, it starts skipping really badly - but it does so 
> under all schedulers i tried (cfs, sd, vanilla).

I see similar here, but this has not always been the case. 2.6.10 did
not have the issue with esd.


-- wli

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> > > Compared to mainline?  I still think this is a 100% keeper for 
> > > desktop users like me.
> > 
> > Here its alot worse, just playing an ogg with ogg123 even without 
> > anything reniced (X is 0), just pressing a link in konqueror can 
> > make audio skip (ogg123 fails to fill the alsa buffer, and thus it 
> > skips).
> 
> update for lkml readers: this is some really 'catastrophic' condition 
> triggering on your box. Here ogg123 just never skips on an older 750 
> MHz box, which is 4-5 times slower than your 2GHz box - while i have 
> _fourty nice-0 infinite loops_ running. I.e. at this clearly 
> ridiculous load, at just 2.5% of CPU time ogg123 is just chugging 
> along nicely and never leaves out a beat.

i've done some ogg123 testing on another box, which should be very 
similar to yours (2GHz, 1 core used), running your .config on 
2.6.21-cfs-v6.

I started an ogg123 instance and i also started up 10 infinite loops (at 
nice-0) to create some competition for ogg123:

  Audio Device:   Advanced Linux Sound Architecture (ALSA) output

  Playing: ./music.ogg
  Ogg Vorbis stream: 2 channel, 44100 Hz
  Title: Track 01

system utilization:

 top - 13:24:24 up 1 min,  3 users,  load average: 2.79, 0.10, 0.21
 Tasks: 184 total,  12 running, 172 sleeping,   0 stopped,   0 zombie
 Cpu(s):100.0%us,  0.0%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
 Mem:   1017616k total,   211548k used,   806068k free,    12936k buffers

ogg123 never skips. Then i cranked up the load to 50 infinite loops (!). 
No problems whatsoever. No problems at 100 tasks either. No problems 
with 250 (!) nice-0 infinite loops running either:

 top - 13:11:54 up 3 min,  3 users,  load average: 215.64, 82.67, 30.38
 Tasks: 424 total, 254 running, 170 sleeping,   0 stopped,   0 zombie
 Cpu(s): 99.8%us,  0.2%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st
 Mem:   1017616k total,   237868k used,   779748k free,    12916k buffers
 Swap:        0k total,        0k used,        0k free,   155472k cached

ogg123 just never leaves out a beat, output buffer never goes below 90%:

 Time: 03:14.10 [01:23.84] of 04:37.93  (133.0 kbps)  Output Buffer  90.6%

then i increased the load to 350 tasks competing with ogg123 for the CPU 
and ogg123 is still going strong:

 Time: 04:27.66 [00:10.28] of 04:37.93  (107.1 kbps)  Output Buffer  87.5%

at 500 tasks it's still borderline (output buffer sometimes dipping as 
low as 50%) and i thought 550 tasks would be it - but it needed 600 (!) 
nice-0 (!) infinite loops to compete for one poor CPU for me to hear the 
very first skip. And even at 600 tasks:

 top - 13:17:17 up 8 min,  3 users,  load average: 567.82, 338.00, 151.65
 Tasks: 774 total, 604 running, 170 sleeping,   0 stopped,   0 zombie
 Cpu(s): 99.9%us,  0.1%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

the music is still enjoyable. It needed 650 tasks for the skipping to 
become frequent and unbearable.

so ogg123 under CFS is _ridiculously_ robust in all my testing and all 
systems i've tried.

so i think it has to be some other variable that causes that 
catastrophic skipping on your system. Could you try a few things to help 
me debug this problem:

 - make sure ogg123 is the only task accessing the sound hardware. E.g. 
   check via 'top' that no other task (such as esd) is trying to access
   it at the same time.

 - please start the ogg123 instance in a plain VGA text console, not
   under X. This would take X and the xterm out of the picture. (ogg123 
   updates the terminal frequently)

 - To exclude the possibility of FS and IO interaction, could you copy 
   your ogg file to /dev/shm and play it from there? Is it still 
   skipping?

if after these two tests ogg123 is still skipping badly for you then it 
would be nice to run ogg123 the following way:

   strace -f -ttt -TTT -o ogg123-trace.txt ogg123 ./your-music.ogg

and send me ogg123-trace.txt privately (compressed). Based on that 
output i'll try to come up with some more active debugging method. 
Thanks!

	Ingo

Re: [patch] CFS scheduler, -v6

[Mark Lord]

Ingo,

You've really outdone yourself this time!

2.6.21 + CFS-v6, plus the futex PI fix patch posted later,
just absolutely rocks here!

I'm having a very difficult time finding any fault with it,
and it has now displaced the stock scheduler as my default
and personal favourite.

The KDE (Dapper Drake) desktop is smooth under 100% CPU load,
mp3's play without glitches, and everything is just *so* responsive.

Well done.  Let's get something like this into mainline.
-- 
Mark Lord
Real-Time Remedies Inc.
mark@rtr.ca

Re: [patch] CFS scheduler, -v6

[Mark Lord]

Mark Lord wrote:
> Ingo,
> 
> You've really outdone yourself this time!
> 
> 2.6.21 + CFS-v6, plus the futex PI fix patch posted later,
> just absolutely rocks here!
> 
> I'm having a very difficult time finding any fault with it,
> and it has now displaced the stock scheduler as my default
> and personal favourite.
> 
> The KDE (Dapper Drake) desktop is smooth under 100% CPU load,
> mp3's play without glitches, and everything is just *so* responsive.

Oh, and all of this is *without* renicing X11, even with "make -j2"
happening on the kernel tree.

Cheers

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Fri, 2007-04-27 at 13:55 +0200, Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> > update for lkml readers: this is some really 'catastrophic' condition 
> > triggering on your box. Here ogg123 just never skips on an older 750 
> > MHz box, which is 4-5 times slower than your 2GHz box - while i have 
> > _fourty nice-0 infinite loops_ running. I.e. at this clearly 
> > ridiculous load, at just 2.5% of CPU time ogg123 is just chugging 
> > along nicely and never leaves out a beat.
> 
> Kasper, just to exclude the possibility that this is somehow related to 
> IO scheduling, could you copy the OGG file over to /dev/shm and play it 
> from there? Do you still get the bad skips?

That's what I can observe here:

ogg123 local harddisk	skips
ogg123 nfs		works
ogg123 /dev/shm		works

The skips when running from the local harddisk are definitely caused by
the I/O scheduler or some other bottleneck in the block/disk/scsi/sata
jungle. I try to find out more details.

	tglx

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> > Kasper, just to exclude the possibility that this is somehow related 
> > to IO scheduling, could you copy the OGG file over to /dev/shm and 
> > play it from there? Do you still get the bad skips?
> 
> That's what I can observe here:
> 
> ogg123 local harddisk	skips
> ogg123 nfs		works
> ogg123 /dev/shm		works
> 
> The skips when running from the local harddisk are definitely caused 
> by the I/O scheduler or some other bottleneck in the 
> block/disk/scsi/sata jungle. I try to find out more details.

and is it independent of the scheduler - i.e. can you see this skipping 
on vanilla too?

	Ingo

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Fri, 2007-04-27 at 15:39 +0200, Thomas Gleixner wrote:
> ogg123 local harddisk	skips
> ogg123 nfs		works
> ogg123 /dev/shm		works
> 
> The skips when running from the local harddisk are definitely caused by
> the I/O scheduler or some other bottleneck in the block/disk/scsi/sata
> jungle. I try to find out more details.

Forgot to mention that it happens with any scheduler.

	tglx

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Mark Lord <lkml@rtr.ca> wrote:

> > You've really outdone yourself this time!
> >
> > 2.6.21 + CFS-v6, plus the futex PI fix patch posted later, just 
> > absolutely rocks here!
> >
> > I'm having a very difficult time finding any fault with it,
> > and it has now displaced the stock scheduler as my default
> > and personal favourite.
> >
> > The KDE (Dapper Drake) desktop is smooth under 100% CPU load, mp3's 
> > play without glitches, and everything is just *so* responsive.
> 
> Oh, and all of this is *without* renicing X11, even with "make -j2" 
> happening on the kernel tree.

cool! :) Regarding renicing: all people so far who tried reniced and 
non-reniced X say both work fine under CFS, so i've disabled the option 
by default in the Kconfig.

	Ingo

Re: [patch] CFS scheduler, -v6

[Bill Davidsen]

Con Kolivas wrote:
> On Friday 27 April 2007 10:39, Gene Heskett wrote:
>> Not necessarily Con.  Do you have a fresh one for 2.6.21?
> 
> Since people get nervous about any rejects here is an (otherwise identical) 
> patch for 2.6.21
> 
> http://ck.kolivas.org/patches/staircase-deadline/2.6.21-sd-0.46.patch
> 
I applied an older version, maybe rc7 or so, without issues. It may have 
bitched about the Makefile, can't remember, I sometimes add my own patch 
level infor for local fixes.

BTW: to build allmodconfig 2.6.21 the sd-0.46 was marginally faster in 
real time. Perhaps down in the noise, I'm getting ready to boot and test 
the x86_64 version.

-- 
Bill Davidsen <davidsen@tmr.com>
   "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot

Re: [patch] CFS scheduler, -v6

[Lee Revell]

On 4/27/07, Ingo Molnar <mingo@elte.hu> wrote:
> ogg123 never skips. Then i cranked up the load to 50 infinite loops (!).
> No problems whatsoever. No problems at 100 tasks either. No problems
> with 250 (!) nice-0 infinite loops running either:

Different soundcards support different ranges and defaults for buffer
and period sizes and many naive apps don't bother to set a sane buffer
size.  Check the PCM states under /proc/asound/ on both good and bad
configs.

Lee

Re: [patch] CFS scheduler, -v6

[Srivatsa Vaddagiri]

On Wed, Apr 25, 2007 at 11:47:04PM +0200, Ingo Molnar wrote:
> The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be downloaded 
> from the usual place:
> 
>     http://redhat.com/~mingo/cfs-scheduler/

+static inline struct rb_node * first_fair(struct rq *rq)
+{
+	if (rq->rb_leftmost)
+		return rq->rb_leftmost;
+	return rb_first(&rq->tasks_timeline);
+}

Won't it help if you update rq->rb_leftmost above from the value
returned by rb_first(), so that subsequent calls to first_fair will be
sped up?

-- 
Regards,
vatsa

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Srivatsa Vaddagiri <vatsa@in.ibm.com> wrote:

> On Wed, Apr 25, 2007 at 11:47:04PM +0200, Ingo Molnar wrote:
> > The CFS patch against v2.6.21-rc7 or against v2.6.20.7 can be downloaded 
> > from the usual place:
> > 
> >     http://redhat.com/~mingo/cfs-scheduler/
> 
> +static inline struct rb_node * first_fair(struct rq *rq)
> +{
> +	if (rq->rb_leftmost)
> +		return rq->rb_leftmost;
> +	return rb_first(&rq->tasks_timeline);
> +}
> 
> Won't it help if you update rq->rb_leftmost above from the value 
> returned by rb_first(), so that subsequent calls to first_fair will be 
> sped up?

yeah, indeed. Would you like to do a patch for that?

	Ingo

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Srivatsa Vaddagiri <vatsa@in.ibm.com> wrote:

> > yeah, indeed. Would you like to do a patch for that?
> 
> My pleasure :)

thanks! I've applied your patch to my tree and it will be in -v7 which 
i'll release in a few minutes.

	Ingo

Re: [patch] CFS scheduler, -v6

[Srivatsa Vaddagiri]

On Sat, Apr 28, 2007 at 03:53:38PM +0200, Ingo Molnar wrote:
> > Won't it help if you update rq->rb_leftmost above from the value 
> > returned by rb_first(), so that subsequent calls to first_fair will be 
> > sped up?
> 
> yeah, indeed. Would you like to do a patch for that?

My pleasure :)

With the patch below applied, I ran a "time -p make -s -j10 bzImage"
test.

2.6.20 + cfs-v6			-> 186.45 (real)
2.6.20 + cfs-v6 + this_patch	-> 184.55 (real)

or about ~1% improvement in real wall-clock time. This was with the default 
sched_granularity_ns of 6000000. I suspect larger the value of
sched_granularity_ns and the number of (SCHED_NORMAL) tasks in system, better 
the benefit from this caching.


Cache value returned by rb_first(), for faster subsequent lookups.

Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com>


---


diff -puN kernel/sched_fair.c~speedup kernel/sched_fair.c
--- linux-2.6.21/kernel/sched_fair.c~speedup	2007-04-28 19:28:08.000000000 +0530
+++ linux-2.6.21-vatsa/kernel/sched_fair.c	2007-04-28 19:34:55.000000000 +0530
@@ -86,7 +86,9 @@ static inline struct rb_node * first_fai
 {
 	if (rq->rb_leftmost)
 		return rq->rb_leftmost;
-	return rb_first(&rq->tasks_timeline);
+	/* Cache the value returned by rb_first() */
+	rq->rb_leftmost = rb_first(&rq->tasks_timeline);
+	return rq->rb_leftmost;
 }
 
 static struct task_struct * __pick_next_task_fair(struct rq *rq)
_




	

-- 
Regards,
vatsa

Re: [patch] CFS scheduler, -v6

[Srivatsa Vaddagiri]

On Sat, Apr 28, 2007 at 08:53:27PM +0530, Srivatsa Vaddagiri wrote:
> With the patch below applied, I ran a "time -p make -s -j10 bzImage"
> test.

On a 4CPU (accounting HT) Intel Xeon 3.6GHz box

> 
> 2.6.20 + cfs-v6			-> 186.45 (real)
> 2.6.20 + cfs-v6 + this_patch	-> 184.55 (real)
> 
> or about ~1% improvement in real wall-clock time. This was with the default 
> sched_granularity_ns of 6000000. I suspect larger the value of
> sched_granularity_ns and the number of (SCHED_NORMAL) tasks in system, better 
> the benefit from this caching.

-- 
Regards,
vatsa

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Fri, 2007-04-27 at 13:55 +0200, Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> > update for lkml readers: this is some really 'catastrophic' condition 
> > triggering on your box. Here ogg123 just never skips on an older 750 
> > MHz box, which is 4-5 times slower than your 2GHz box - while i have 
> > _fourty nice-0 infinite loops_ running. I.e. at this clearly 
> > ridiculous load, at just 2.5% of CPU time ogg123 is just chugging 
> > along nicely and never leaves out a beat.
> 
> Kasper, just to exclude the possibility that this is somehow related to 
> IO scheduling, could you copy the OGG file over to /dev/shm and play it 
> from there? Do you still get the bad skips?
Just copied to a tmpfs, and it still skips badly.

in response to your question, Ingo, yes, i see those atleast 0 ms
messages.

I am not running esd, i use alsa directly from ogg123.

but its not just ogg123, mplayer does it too. just moving a window can
trigger it. even scrolling in my maillist causes it.

and this ONLY happens on cfs, not vanilla, not staircase, not sd.

while i look at top, the load average is 0.11

its definetly not an IO issue, cause i just tried creating some IO load,
like reading files, it doesent skip, but moving windows triggers it
better than anything(mplayer seems more sensitive than ogg123), it seems
anything X-related makes it explode..

tried looking for buffer stuff in /proc/asound, couldnt find anything,
im using the via82xx driver.


> 
> 	Ingo
> 

Re: [patch] CFS scheduler, -v6

[Lee Revell]

On 4/28/07, Kasper Sandberg <lkml@metanurb.dk> wrote:
> tried looking for buffer stuff in /proc/asound, couldnt find anything,
> im using the via82xx driver.
>

Use fuser to see which sound device is used:

$ fuser /dev/snd/*
/dev/snd/controlC0:  14028
/dev/snd/pcmC0D0c:   14028m
/dev/snd/pcmC0D0p:   14028m

So process 14028 is using capture device 0 substream 0 and playback
device 0 substream 0.  Examine the hw_params for playback device like
so:

$ cat /proc/asound/card0/pcm0p/sub0/hw_params
access: MMAP_INTERLEAVED
format: S16_LE
subformat: STD
channels: 2
rate: 48000 (48000/1)
period_size: 1024
buffer_size: 2048
tick_time: 1000

This application (jackd) is a sophisticated user of ALSA API and
allows the user to set period and buffer size but many apps just use
the default they get from ALSA.  These apps will work well with a
driver that happens to have a large default buffer but will fail
(skip) with drivers that default to a small buffer.

Lee

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

Okay so i've tried with cfs 7 now, and the completely broken audio
behavior is fixed.

The only things i really notice now is that gtk apps seems to redraw
somewhat slower, and renicing X doesent seem to be able to bring it on
par with SD or vanilla.

And smoothness just doesent match SD, it may be abit better than
vanilla/staircase, i cant really definitively say, but SD just has the
smoothness factor which is extremely attractive.

This is with 3d stuff, like through wine or natively on linux, under
load(and even just minor things like using a browser or other things,
like spamasassin), vanilla/staircase(not rsdl or sd)/cfs will go down in
FPS, but at the same time stutter, it goes down to around the same fps
under same load, as SD, but SD is completely smooth.

Im not sure im describing properly, but say it takes 35fps for the 3d
stuff to seem perfect, the fps monitor updates once every 1 or two
seconds, showing average fps(havent looked at the code, but i assume it
spans those 1-2 seconds), usually i have like 60 fps, but under load it
can go down to 35, but under anything but SD its not smooth, it will do
the 35 fps, but i suspect it does it in chunks, for example it will skip
for 200 ms and then hurry to display the 35 frames. This means it does
get the workload done, but not in a very plesant matter, and its here i
see SD as being in such a high league that its really impossible to
describe the results with any other word than Perfect.

mvh.
Kasper Sandberg

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

Hi,

On Sun, Apr 29, 2007 at 03:18:32AM +0200, Kasper Sandberg wrote:
> Okay so i've tried with cfs 7 now, and the completely broken audio
> behavior is fixed.
> 
> The only things i really notice now is that gtk apps seems to redraw
> somewhat slower, and renicing X doesent seem to be able to bring it on
> par with SD or vanilla.
> 
> And smoothness just doesent match SD, it may be abit better than
> vanilla/staircase, i cant really definitively say, but SD just has the
> smoothness factor which is extremely attractive.

(...)

I don't know if Mike still has problems with SD, but there are now several
interesting reports of SD giving better feedback than CFS on real work. In
my experience, CFS seems smoother on *technical* tests, which I agree that
they do not really simulate real work.

I really think that if we merged SD in 2.6.22, at least we could focus
more on differences between it (which will become mainline) and CFS in
order to improve CFS for later inclusion when mature enough. Or maybe
only relevant parts of CFS will be merged into mainline later. But at
least, testers will not have to patch anymore to report feedback with
SD during -rc, and above all they would not compare anymore against
old-vanilla, thus reducing the number of tests.

Just my 2 cents,
Willy

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Sun, 2007-04-29 at 07:30 +0200, Willy Tarreau wrote:

> I don't know if Mike still has problems with SD...

I'm neither testing recent SD releases nor looking at the source.  All
the testing I did was a waste of my time and lkml bandwidth.

	-Mike

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Kasper Sandberg <lkml@metanurb.dk> wrote:

> Okay so i've tried with cfs 7 now, and the completely broken audio 
> behavior is fixed.

great! :) This worried me alot!

> Im not sure im describing properly, but say it takes 35fps for the 3d 
> stuff to seem perfect, the fps monitor updates once every 1 or two 
> seconds, showing average fps(havent looked at the code, but i assume 
> it spans those 1-2 seconds), usually i have like 60 fps, but under 
> load it can go down to 35, [...]

What is this "3D stuff" exactly, and what are you using to monitor the 
framerates? (Also, could you please try another experiment and enable 
CONFIG_PREEMPT? CFS works smoothest with that enabled.)

	Ingo

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Willy Tarreau <w@1wt.eu> wrote:

> I don't know if Mike still has problems with SD, but there are now 
> several interesting reports of SD giving better feedback than CFS on 
> real work. In my experience, CFS seems smoother on *technical* tests, 
> which I agree that they do not really simulate real work.

well, there are several reports of CFS being significantly better than 
SD on a number of workloads - and i know of only two reports where SD 
was reported to be better than CFS: in Kasper's test (where i'd like to 
know what the "3D stuff" he uses is and take a good look at that 
workload), and another 3D report which was done against -v6. (And even 
in these two reports the 'smoothness advantage' was not dramatic. If you 
know of any other reports then please let me know!)

	Ingo

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 08:59:01AM +0200, Ingo Molnar wrote:
> 
> * Willy Tarreau <w@1wt.eu> wrote:
> 
> > I don't know if Mike still has problems with SD, but there are now 
> > several interesting reports of SD giving better feedback than CFS on 
> > real work. In my experience, CFS seems smoother on *technical* tests, 
> > which I agree that they do not really simulate real work.
> 
> well, there are several reports of CFS being significantly better than 
> SD on a number of workloads - and i know of only two reports where SD 
> was reported to be better than CFS: in Kasper's test (where i'd like to 
> know what the "3D stuff" he uses is and take a good look at that 
> workload), and another 3D report which was done against -v6. (And even 
> in these two reports the 'smoothness advantage' was not dramatic. If you 
> know of any other reports then please let me know!)

There was Caglar Onur too but he said he will redo all the tests. I'm
not tracking all tests nor versions, so it might be possible that some
of the differences vanish with v7.

In fact, what I'd like to see in 2.6.22 is something better for everybody
and with *no* regression, even if it's not perfect. I had the feeling
that SD matched that goal right now, except for Mike who has not tested
recent versions. Don't get me wrong, I still think that CFS is a more
interesting long-term target. But it may require more time to satisfy
everyone. At least with one of them in 2.6.22, we won't waste time
comparing to current mainline.

> 	Ingo

Willy

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Willy Tarreau <w@1wt.eu> wrote:

> > know of any other reports then please let me know!)
> 
> There was Caglar Onur too but he said he will redo all the tests. 
> [...]

well, Caglar said CFSv7 works as well as CFSv6 in his latest tests and 
that he'll redo all the tests to re-verify his original regression 
report :)

> In fact, what I'd like to see in 2.6.22 is something better for 
> everybody and with *no* regression, even if it's not perfect.
>
> I had the feeling that SD matched that goal right now, [...]

curious, which are the reports where in your opinion CFS behaves worse 
than vanilla? There were two audio skipping reports against CFS, the 
most serious one got resolved and i hope the other one has been resolved 
by the same fix as well. (i'm still waiting for feedback on that one)

> [...] except for Mike who has not tested recent versions. [...]

actually, dont discount Mark Lord's test results either. And it might be 
a good idea for Mike to re-test SD 0.46?

	Ingo

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 09:30:30AM +0200, Ingo Molnar wrote:
> > In fact, what I'd like to see in 2.6.22 is something better for 
> > everybody and with *no* regression, even if it's not perfect.
> >
> > I had the feeling that SD matched that goal right now, [...]
> 
> curious, which are the reports where in your opinion CFS behaves worse 
> than vanilla?

see below :-)

> There were two audio skipping reports against CFS, the 
> most serious one got resolved and i hope the other one has been resolved 
> by the same fix as well. (i'm still waiting for feedback on that one)

your answer to your question above ;-)
Yes, we're all waiting for feedback. And I said I did not track the
versions involved, so it is possible that all previously encountered
regressions are fixed by now.

> > [...] except for Mike who has not tested recent versions. [...]
> 
> actually, dont discount Mark Lord's test results either. And it might be 
> a good idea for Mike to re-test SD 0.46?

In any case, it might be a good idea because Mike encountered a problem
that nobody could reproduce. It may come from hardware, scheduler design,
scheduler bug, or any other bug, but whatever the cause, it would be
interesting to conclude on it.

> 	Ingo

Willy

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Sun, Apr 29, 2007 at 09:16:27AM +0200, Willy Tarreau wrote:
> In fact, what I'd like to see in 2.6.22 is something better for everybody
> and with *no* regression, even if it's not perfect. I had the feeling
> that SD matched that goal right now, except for Mike who has not tested
> recent versions. Don't get me wrong, I still think that CFS is a more
> interesting long-term target. But it may require more time to satisfy
> everyone. At least with one of them in 2.6.22, we won't waste time
> comparing to current mainline.

I think it'd be a good idea to merge scheduler classes before changing
over the policy so future changes to policy have smaller code impact.
Basically, get scheduler classes going with the mainline scheduler.

There are other pieces that can be merged earlier, too, for instance,
the correction to the comment in init/main.c. Directed yields can
probably also go in as nops or -ENOSYS returns if not fully implemented,
though I suspect there shouldn't be much in the way of implementing them.
p->array vs. p->on_rq can be merged early too. Common code for rbtree-
based priority queues can be factored out of cfq, cfs, and hrtimers.
There are extensive /proc/ reporting changes, large chunks of which
could go in before the policy as well.

I'm camping in this weekend, so I'll see what I can eke out.


-- wli

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Sun, 2007-04-29 at 08:59 +0200, Ingo Molnar wrote:
> * Willy Tarreau <w@1wt.eu> wrote:
> 
> > I don't know if Mike still has problems with SD, but there are now 
> > several interesting reports of SD giving better feedback than CFS on 
> > real work. In my experience, CFS seems smoother on *technical* tests, 
> > which I agree that they do not really simulate real work.
> 
> well, there are several reports of CFS being significantly better than 
> SD on a number of workloads - and i know of only two reports where SD 
> was reported to be better than CFS: in Kasper's test (where i'd like to 
> know what the "3D stuff" he uses is and take a good look at that 
> workload), and another 3D report which was done against -v6. (And even 
> in these two reports the 'smoothness advantage' was not dramatic. If you 
> know of any other reports then please let me know!)

I can tell you one thing, its not just me that has observed the
smoothness in 3d stuff, after i tried rsdl first i've had lots of people
try rsdl and subsequently sd because of the significant improvement in
smoothness, and they have all found the same results.

The stuff i have tested with in particular is unreal tournament 2004 and
world of warcraft through wine, both running opengl, and consuming all
the cpu time it can get.

and the thing that happens is simply that even when theres only that
process, sd is still smoother, but the significance is much larger once
just something starts, like if the mail client starts fetching mail, and
running some somewhat demanding stuff like spamasassin, the only way you
notice it is by the drop in fps, smoothness is 100% intact with SD
(ofcourse if you started HUGE load it probably would get so little cpu
it would stutter), but with every other scheduler you will notice
immediate and quite severe stuttering, in fact to many it will seem
intolerable.

I can tell you how I first noticed this, i was experimenting in ut2k4
with sd, and usually i always have to close my mail client, because when
spamasassin starts (nice 0), the game would stutter quite much, but when
i was playing i noticed some IO activity and work noises from my disk,
but that was all, no noticable stutter or problems with the 3d, but i
couldnt figure out why, i then discovered i had forgotten to close my
mail client which i previously ALWAYS have had to do.

If you have some ideas on how these problems might be fixed i'd surely
try fixes and stuff, or if you have some data you need me to collect to
better understand whats going on. But i suspect any somewhat demanding
3d application will do, and the difference is so staggering that when
you see it in effect, you cant miss it.

> 
> 	Ingo
> 

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Willy Tarreau <w@1wt.eu> wrote:

> > > [...] except for Mike who has not tested recent versions. [...]
> > 
> > actually, dont discount Mark Lord's test results either. And it 
> > might be a good idea for Mike to re-test SD 0.46?
> 
> In any case, it might be a good idea because Mike encountered a 
> problem that nobody could reproduce. [...]

actually, Mark Lord too reproduced something similar to Mike's results. 
Please try those workloads yourself.

	Ingo

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 10:00:28AM +0200, Ingo Molnar wrote:
> 
> * Willy Tarreau <w@1wt.eu> wrote:
> 
> > > > [...] except for Mike who has not tested recent versions. [...]
> > > 
> > > actually, dont discount Mark Lord's test results either. And it 
> > > might be a good idea for Mike to re-test SD 0.46?
> > 
> > In any case, it might be a good idea because Mike encountered a 
> > problem that nobody could reproduce. [...]
> 
> actually, Mark Lord too reproduced something similar to Mike's results. 

OK.

> Please try those workloads yourself.

Unfortunately, I do not have their tools, environments nor hardware.
That's the advantage of having multiple testers ;-)

> 	Ingo

Willy

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* William Lee Irwin III <wli@holomorphy.com> wrote:

> I think it'd be a good idea to merge scheduler classes before changing 
> over the policy so future changes to policy have smaller code impact. 
> Basically, get scheduler classes going with the mainline scheduler.

i've got a split up patch for the class stuff already, but lets first 
get some wider test-coverage before even thinking about upstream 
integration. This is all v2.6.22 stuff at the earliest.

	Ingo

Re: [patch] CFS scheduler, -v6

[Ingo Molnar]

* Kasper Sandberg <lkml@metanurb.dk> wrote:

> If you have some ideas on how these problems might be fixed i'd surely 
> try fixes and stuff, or if you have some data you need me to collect 
> to better understand whats going on. But i suspect any somewhat 
> demanding 3d application will do, and the difference is so staggering 
> that when you see it in effect, you cant miss it.

it would be great if you could try a simple experiment: does something 
as simple as glxgears resized to a large window trigger this 
'stuttering' phenomenon when other stuff is running? If not, could you 
try to find the simplest 3D stuff under Linux that already triggers it 
so that i can reproduce it?

(Also, as an independent debug-test, could you try CONFIG_PREEMPT too 
perhaps? I.e. is this 'stuttering' behavior independent of the 
preemption model and a general property of CFS?)

	Ingo

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Sun, 2007-04-29 at 09:16 +0200, Willy Tarreau wrote:

> In fact, what I'd like to see in 2.6.22 is something better for everybody
> and with *no* regression, even if it's not perfect. I had the feeling
> that SD matched that goal right now, except for Mike who has not tested
> recent versions. Don't get me wrong, I still think that CFS is a more
> interesting long-term target.

While I haven't tested recent SD versions, unless it's design has
radically changed recently, I know what to expect.  CFS is giving me a
very high quality experience already (it's at a whopping v7), while
RSDL/SD irritated me greatly at version v40.  As far as I'm concerned,
CFS is the superior target, short-term, long-term whatever-term.  For
the tree where I make the decisions, the hammer has fallen, and RSDL/SD
is history.  Heck, I'm _almost_ ready to rm -rf my own scheduler trees
as well... I could really use some free disk space.

	-Mike

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 12:54:36AM -0700, William Lee Irwin III wrote:
> On Sun, Apr 29, 2007 at 09:16:27AM +0200, Willy Tarreau wrote:
> > In fact, what I'd like to see in 2.6.22 is something better for everybody
> > and with *no* regression, even if it's not perfect. I had the feeling
> > that SD matched that goal right now, except for Mike who has not tested
> > recent versions. Don't get me wrong, I still think that CFS is a more
> > interesting long-term target. But it may require more time to satisfy
> > everyone. At least with one of them in 2.6.22, we won't waste time
> > comparing to current mainline.
> 
> I think it'd be a good idea to merge scheduler classes before changing
> over the policy so future changes to policy have smaller code impact.
> Basically, get scheduler classes going with the mainline scheduler.
> 
> There are other pieces that can be merged earlier, too, for instance,
> the correction to the comment in init/main.c. Directed yields can
> probably also go in as nops or -ENOSYS returns if not fully implemented,
> though I suspect there shouldn't be much in the way of implementing them.
> p->array vs. p->on_rq can be merged early too.

I agree that merging some framework is a good way to proceed.

> Common code for rbtree-based priority queues can be factored out of
> cfq, cfs, and hrtimers.

In my experience, rbtrees are painfully slow. Yesterday, I spent the
day replacing them in haproxy with other trees I developped a few
years ago, which look like radix trees. They are about 2-3 times as
fast to insert 64-bit data, and you walk through them in O(1). I have
many changes to apply to them before they could be used in kernel, but
at least I think we already have code available for other types of trees.

> There are extensive /proc/ reporting changes, large chunks of which
> could go in before the policy as well.
> 
> I'm camping in this weekend, so I'll see what I can eke out.

good luck !

Willy

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

* William Lee Irwin III <wli@holomorphy.com> wrote:
>> I think it'd be a good idea to merge scheduler classes before changing 
>> over the policy so future changes to policy have smaller code impact. 
>> Basically, get scheduler classes going with the mainline scheduler.

On Sun, Apr 29, 2007 at 10:03:59AM +0200, Ingo Molnar wrote:
> i've got a split up patch for the class stuff already, but lets first 
> get some wider test-coverage before even thinking about upstream 
> integration. This is all v2.6.22 stuff at the earliest.

I'd like to get some regression testing (standard macrobenchmarks) in
on the scheduler class bits in isolation, as they do have rather
non-negligible impacts on load balancing code, to changes in which such
macrobenchmarks are quite sensitive.

This shouldn't take much more than kicking off a benchmark on an
internal box at work already set up to do such testing routinely.
I won't need to write any fresh testcases etc. for it. Availability
of the test systems may have to wait until Monday, since various people
not wanting benchmarks disturbed are likely to be out for the weekend.

It would also be beneficial for the other schedulers to be able to
standardize on the scheduling class framework as far in advance as
possible. In such a manner comparative testing by end-users and more
industrial regression testing can be facilitated.


-- wli

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Sun, Apr 29, 2007 at 12:54:36AM -0700, William Lee Irwin III wrote:
>> Common code for rbtree-based priority queues can be factored out of
>> cfq, cfs, and hrtimers.

On Sun, Apr 29, 2007 at 10:13:17AM +0200, Willy Tarreau wrote:
> In my experience, rbtrees are painfully slow. Yesterday, I spent the
> day replacing them in haproxy with other trees I developped a few
> years ago, which look like radix trees. They are about 2-3 times as
> fast to insert 64-bit data, and you walk through them in O(1). I have
> many changes to apply to them before they could be used in kernel, but
> at least I think we already have code available for other types of trees.

Dynamic allocation of auxiliary indexing structures is problematic for
the scheduler, which significantly constrains the algorithms one may
use for this purpose.

rbtrees are not my favorite either. Faster alternatives to rbtrees
exist even among binary trees; for instance, it's not so difficult to
implement a heap-ordered tree maintaining the red-black invariant with
looser constraints on the tree structure and hence less rebalancing.
One could always try implementing a van Emde Boas queue, if he felt
particularly brave.

Some explanation of the structure may be found at:
http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L1/lecture1.pdf

According to that, y-trees use less space, and exponential trees are
asymptotically faster with a worst-case asymptotic running time of

	O(min(lg(lg(u))*lg(lg(n))/lg(lg(lg(u))), sqrt(lg(n)/lg(lg(n)))))

for all operations, so van Emde Boas is not the ultimate algorithm by
any means at O(lg(lg(u))); in these estimates, u is the size of the
"universe," or otherwise the range of the key data type. Not to say
that any of those are appropriate for the kernel; it's rather likely
we'll have to settle for something less interesting, if we bother
ditching rbtrees at all, on account of the constraints of the kernel
environment.

I'll see what I can do about a userspace test harness for priority
queues more comprehensive than smart-queue.c. I have in mind the
ability to replay traces obtained from queues in the kernel and loading
priority queue implementations via dlopen()/dlsym() et al. valgrind can
do most of the dirty work. Otherwise running a trace for some period of
time and emitting the number of operations it got through should serve
as a benchmark. With that in hand, people can grind out priority queue
implementations and see how they compare on real operation sequences
logged from live kernels.


-- wli

Re: [patch] CFS scheduler, -v6

[Con Kolivas]

On Sunday 29 April 2007 18:00, Ingo Molnar wrote:
> * Willy Tarreau <w@1wt.eu> wrote:
> > > > [...] except for Mike who has not tested recent versions. [...]
> > >
> > > actually, dont discount Mark Lord's test results either. And it
> > > might be a good idea for Mike to re-test SD 0.46?
> >
> > In any case, it might be a good idea because Mike encountered a
> > problem that nobody could reproduce. [...]
>
> actually, Mark Lord too reproduced something similar to Mike's results.
> Please try those workloads yourself.

I see no suggestion that either Mark or Mike have tested, or for that matter 
_have any intention of testing_, the current version of SD without fancy 
renicing or anything involved. Willy I grealy appreciate you trying, but I 
don't know why you're bothering even trying here since clearly 1. Ingo is the 
scheduler maintainer 2. he's working on a competing implementation and 3. in 
my excellent physical and mental state I seem to have slighted the two 
testers (both?) somewhere along the line. Mike feels his testing was a 
complete waste of time yet it would be ludicrous for me to say that SD didn't 
evolve 20 versions further due to his earlier testing, and was the impetus 
for you to start work on CFS. The crunch came that we couldn't agree that 
fair was appropriate for mainline and we parted ways. That fairness has not 
been a problem for his view on CFS though but he has only tested older 
versions of SD that still had bugs.

Given facts 1 and 2 above I have all but resigned myself to the fact that SD 
has -less than zero- chance of ever being considered for mainline and it's my 
job to use it as something to compare your competing design with to make sure 
that when (and I do mean when since there seems no doubt in everyone else's 
mind) CFS becomes part of mainline that it is as good as SD. Saying people 
found CFS better than SD is, in my humble opinion, an exaggeration since 
every one I could find was a glowing standalone report of CFS rather than any 
comparison to the current very stable bug free version of SD. On the other 
hand I still see that when people compare them side to side they find SD is 
better, so I will hold CFS against that comparison - when comparing fairness 
based designs.

On a related note - implementing a framework is nice but doesn't address any 
of the current fairness/starvation/corner case problems mainline has. I don't 
see much point in rushing the framework merging since it's still in flux.

-- 
-ck

Re: [patch] CFS scheduler, -v6

[Mike Galbraith]

On Sun, 2007-04-29 at 19:52 +1000, Con Kolivas wrote:
> On Sunday 29 April 2007 18:00, Ingo Molnar wrote:
> > * Willy Tarreau <w@1wt.eu> wrote:
> > > > > [...] except for Mike who has not tested recent versions. [...]
> > > >
> > > > actually, dont discount Mark Lord's test results either. And it
> > > > might be a good idea for Mike to re-test SD 0.46?
> > >
> > > In any case, it might be a good idea because Mike encountered a
> > > problem that nobody could reproduce. [...]
> >
> > actually, Mark Lord too reproduced something similar to Mike's results.
> > Please try those workloads yourself.
> 
> I see no suggestion that either Mark or Mike have tested, or for that matter 
> _have any intention of testing_, the current version of SD without fancy 
> renicing or anything involved. Willy I grealy appreciate you trying, but I 
> don't know why you're bothering even trying here since clearly 1. Ingo is the 
> scheduler maintainer 2. he's working on a competing implementation and 3. in 
> my excellent physical and mental state I seem to have slighted the two 
> testers (both?) somewhere along the line. Mike feels his testing was a 
> complete waste of time yet it would be ludicrous for me to say that SD didn't 
> evolve 20 versions further due to his earlier testing, and was the impetus 
> for you to start work on CFS. The crunch came that we couldn't agree that 
> fair was appropriate for mainline and we parted ways. That fairness has not 
> been a problem for his view on CFS though but he has only tested older 
> versions of SD that still had bugs.

The crunch for me came when you started hand-waving and spin-doctoring
as you are doing now.  Listening to twisted echoes of my voice is not my
idea of a good time.

	-Mike

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

Willy,

On Sun, 2007-04-29 at 09:16 +0200, Willy Tarreau wrote:
> In fact, what I'd like to see in 2.6.22 is something better for everybody
> and with *no* regression, even if it's not perfect. I had the feeling
> that SD matched that goal right now, except for Mike who has not tested
> recent versions. Don't get me wrong, I still think that CFS is a more
> interesting long-term target. But it may require more time to satisfy
> everyone. At least with one of them in 2.6.22, we won't waste time
> comparing to current mainline.

Oh no, we really do _NOT_ want to throw SD or anything else at mainline
in a hurry just for not wasting time on comparing to the current
scheduler.

I agree that CFS is the more interesting target and I prefer to push the
more interesting one even if it takes a release cycle longer. The main
reason for me is the design of CFS. Even if it is not really modular
right now, it is not rocket science to make it fully modular.

Looking at the areas where people work on, e.g. containers, resource
management, cpu isolation, fully tickless systems ...., we really need
to go into that direction, when we want to avoid permanent tinkering in
the core scheduler code for the next five years.

As a sidenote: I really wonder if anybody noticed yet, that the whole
CFS / SD comparison is so ridiculous, that it is not even funny anymore.
CFS modifies the scheduler and nothing else, SD fiddles all over the
kernel in interesting ways. 

This is worse than apples and oranges, it's more like apples and
screwdrivers. 

Can we please stop this useless pissing contest and sit down and get a
modular design into mainline, which allows folks to work and integrate
their "workload X perfect scheduler" and gives us the flexibility to
adjust to the needs of upcoming functionality.

	tglx

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> Can we please stop this useless pissing contest and sit down and get a
> modular design into mainline, which allows folks to work and integrate
> their "workload X perfect scheduler" and gives us the flexibility to
> adjust to the needs of upcoming functionality.

If I don't see some sort of modularity patch soon I'll post one myself.


-- wli

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Sun, 2007-04-29 at 12:30 +0200, Thomas Gleixner wrote:
> Willy,
<snip>
> As a sidenote: I really wonder if anybody noticed yet, that the whole
> CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> CFS modifies the scheduler and nothing else, SD fiddles all over the
> kernel in interesting ways. 
> 

have you looked at diffstat lately? :)

sd:
 Documentation/sched-design.txt  |  241 +++++++
 Documentation/sysctl/kernel.txt |   14
 Makefile                        |    2
 fs/pipe.c                       |    7
 fs/proc/array.c                 |    2
 include/linux/init_task.h       |    4
 include/linux/sched.h           |   32 -
 kernel/sched.c                  | 1279
+++++++++++++++++++---------------------
 kernel/softirq.c                |    2
 kernel/sysctl.c                 |   26
 kernel/workqueue.c              |    2
 11 files changed, 919 insertions(+), 692 deletions(-)

cfs:
 Documentation/kernel-parameters.txt |   43
 Documentation/sched-design-CFS.txt  |  107 +
 Makefile                            |    2
 arch/i386/kernel/smpboot.c          |   13
 arch/i386/kernel/tsc.c              |    8
 arch/ia64/kernel/setup.c            |    6
 arch/mips/kernel/smp.c              |   11
 arch/sparc/kernel/smp.c             |   10
 arch/sparc64/kernel/smp.c           |   36
 fs/proc/array.c                     |   11
 fs/proc/base.c                      |    2
 fs/proc/internal.h                  |    1
 include/asm-i386/unistd.h           |    3
 include/asm-x86_64/unistd.h         |    4
 include/linux/hardirq.h             |   13
 include/linux/sched.h               |   94 +
 init/main.c                         |    2
 kernel/exit.c                       |    3
 kernel/fork.c                       |    4
 kernel/posix-cpu-timers.c           |   34
 kernel/sched.c                      | 2288
+++++++++---------------------------
 kernel/sched_debug.c                |  152 ++
 kernel/sched_fair.c                 |  601 +++++++++
 kernel/sched_rt.c                   |  184 ++
 kernel/sched_stats.h                |  235 +++
 kernel/sysctl.c                     |   32
 26 files changed, 2062 insertions(+), 1837 deletions(-)


> This is worse than apples and oranges, it's more like apples and
> screwdrivers. 
<snip>
> 
> 	tglx
> 
> 
> 

Re: [patch] CFS scheduler, -v6

[Con Kolivas]

On Sunday 29 April 2007 20:30, Thomas Gleixner wrote:
> As a sidenote: I really wonder if anybody noticed yet, that the whole
> CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> CFS modifies the scheduler and nothing else, SD fiddles all over the
> kernel in interesting ways.

This is a WTF if ever I saw one.

-- 
-ck

Re: [patch] CFS scheduler, -v6

[Bill Huey]

On Sun, Apr 29, 2007 at 08:53:36PM +1000, Con Kolivas wrote:
> On Sunday 29 April 2007 20:30, Thomas Gleixner wrote:
> > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> > CFS modifies the scheduler and nothing else, SD fiddles all over the
> > kernel in interesting ways.
> 
> This is a WTF if ever I saw one.

You should look at the progression of SD versus CFS. You'll find the exact
opposite has happened and it's kind of baffling that you'd say something like
that. So I don't know what is coloring your experiences with this.

SD is highly regular patch and cleanly applies into that portion of the kernel.
Folks have been asking from some kind of pluggability for this kind of
development for years and had it repeatedly blocked in various ways. So this
seems quite odd that you'd say something like that.

bill

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> Willy,
> 
> On Sun, 2007-04-29 at 09:16 +0200, Willy Tarreau wrote:
> > In fact, what I'd like to see in 2.6.22 is something better for everybody
> > and with *no* regression, even if it's not perfect. I had the feeling
> > that SD matched that goal right now, except for Mike who has not tested
> > recent versions. Don't get me wrong, I still think that CFS is a more
> > interesting long-term target. But it may require more time to satisfy
> > everyone. At least with one of them in 2.6.22, we won't waste time
> > comparing to current mainline.
> 
> Oh no, we really do _NOT_ want to throw SD or anything else at mainline
> in a hurry just for not wasting time on comparing to the current
> scheduler.

It is not about doing it in a hurry. I see SD as a small yet efficient
update to current scheduler. It's not perfect, probably not much extensible
but the risks of breaking anything are small given the fact that it does
not change much of the code or behaviour.

IMHO, it is something which can provide users with a useful update while
leaving us with some more time to carefully implement the features of CFS
one at a time, and if it requires 5 versions, it's not a problem.

> I agree that CFS is the more interesting target and I prefer to push the
> more interesting one even if it takes a release cycle longer. The main
> reason for me is the design of CFS. Even if it is not really modular
> right now, it is not rocket science to make it fully modular.
> 
> Looking at the areas where people work on, e.g. containers, resource
> management, cpu isolation, fully tickless systems ...., we really need
> to go into that direction, when we want to avoid permanent tinkering in
> the core scheduler code for the next five years.
> 
> As a sidenote: I really wonder if anybody noticed yet, that the whole
> CFS / SD comparison is so ridiculous, that it is not even funny anymore.

Contrarily to most people, I don't see them as competitors. I see SD as
a first step with a low risk of regression, and CFS as an ultimate
solution relying on a more solid framework.

> CFS modifies the scheduler and nothing else, SD fiddles all over the
> kernel in interesting ways. 

Hmmm I guess you confused both of them this time. CFS touches many places,
which is why I think the testing coverage is still very low. SD can be
tested faster. My real concern is : are there still people observing
regressions with it ? If yes, they should be fixed before even being
merged. If no, why not merge it as a fix for the many known corner cases
of current scheduler ? After all, it's already in -mm.

Willy

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Sun, 2007-04-29 at 12:48 +0200, Kasper Sandberg wrote:
> On Sun, 2007-04-29 at 12:30 +0200, Thomas Gleixner wrote:
> > Willy,
> <snip>
> > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> > CFS modifies the scheduler and nothing else, SD fiddles all over the
> > kernel in interesting ways. 
> > 
> 
> have you looked at diffstat lately? :)
> 
> sd:
>  Documentation/sched-design.txt  |  241 +++++++
>  Documentation/sysctl/kernel.txt |   14
>  Makefile                        |    2
>  fs/pipe.c                       |    7
>  fs/proc/array.c                 |    2
>  include/linux/init_task.h       |    4
>  include/linux/sched.h           |   32 -
>  kernel/sched.c                  | 1279
> +++++++++++++++++++---------------------
>  kernel/softirq.c                |    2
>  kernel/sysctl.c                 |   26
>  kernel/workqueue.c              |    2
>  11 files changed, 919 insertions(+), 692 deletions(-)
> 
> cfs:
>  Documentation/kernel-parameters.txt |   43
>  Documentation/sched-design-CFS.txt  |  107 +
>  Makefile                            |    2
>  arch/i386/kernel/smpboot.c          |   13
>  arch/i386/kernel/tsc.c              |    8
>  arch/ia64/kernel/setup.c            |    6
>  arch/mips/kernel/smp.c              |   11
>  arch/sparc/kernel/smp.c             |   10
>  arch/sparc64/kernel/smp.c           |   36
>  fs/proc/array.c                     |   11
>  fs/proc/base.c                      |    2
>  fs/proc/internal.h                  |    1
>  include/asm-i386/unistd.h           |    3
>  include/asm-x86_64/unistd.h         |    4
>  include/linux/hardirq.h             |   13
>  include/linux/sched.h               |   94 +
>  init/main.c                         |    2
>  kernel/exit.c                       |    3
>  kernel/fork.c                       |    4
>  kernel/posix-cpu-timers.c           |   34
>  kernel/sched.c                      | 2288
> +++++++++---------------------------
>  kernel/sched_debug.c                |  152 ++
>  kernel/sched_fair.c                 |  601 +++++++++
>  kernel/sched_rt.c                   |  184 ++
>  kernel/sched_stats.h                |  235 +++
>  kernel/sysctl.c                     |   32
>  26 files changed, 2062 insertions(+), 1837 deletions(-)

Sorry, my bad. I looked at a diffstat of the ck full set. Not only the
SD part of it.

	tglx

Re: [patch] CFS scheduler, -v6

[Con Kolivas]

On Sunday 29 April 2007 21:11, Willy Tarreau wrote:
> On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> > Willy,
> >
> > On Sun, 2007-04-29 at 09:16 +0200, Willy Tarreau wrote:
> > > In fact, what I'd like to see in 2.6.22 is something better for
> > > everybody and with *no* regression, even if it's not perfect. I had the
> > > feeling that SD matched that goal right now, except for Mike who has
> > > not tested recent versions. Don't get me wrong, I still think that CFS
> > > is a more interesting long-term target. But it may require more time to
> > > satisfy everyone. At least with one of them in 2.6.22, we won't waste
> > > time comparing to current mainline.
> >
> > Oh no, we really do _NOT_ want to throw SD or anything else at mainline
> > in a hurry just for not wasting time on comparing to the current
> > scheduler.
>
> It is not about doing it in a hurry. I see SD as a small yet efficient
> update to current scheduler. It's not perfect, probably not much extensible
> but the risks of breaking anything are small given the fact that it does
> not change much of the code or behaviour.
>
> IMHO, it is something which can provide users with a useful update while
> leaving us with some more time to carefully implement the features of CFS
> one at a time, and if it requires 5 versions, it's not a problem.
>
> > I agree that CFS is the more interesting target and I prefer to push the
> > more interesting one even if it takes a release cycle longer. The main
> > reason for me is the design of CFS. Even if it is not really modular
> > right now, it is not rocket science to make it fully modular.
> >
> > Looking at the areas where people work on, e.g. containers, resource
> > management, cpu isolation, fully tickless systems ...., we really need
> > to go into that direction, when we want to avoid permanent tinkering in
> > the core scheduler code for the next five years.
> >
> > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
>
> Contrarily to most people, I don't see them as competitors. I see SD as
> a first step with a low risk of regression, and CFS as an ultimate
> solution relying on a more solid framework.
>
> > CFS modifies the scheduler and nothing else, SD fiddles all over the
> > kernel in interesting ways.
>
> Hmmm I guess you confused both of them this time. CFS touches many places,
> which is why I think the testing coverage is still very low. SD can be
> tested faster. My real concern is : are there still people observing
> regressions with it ? If yes, they should be fixed before even being
> merged. If no, why not merge it as a fix for the many known corner cases
> of current scheduler ? After all, it's already in -mm.
>
> Willy

Willy, you're making far too much sense. Are you replying to the correct 
mailing list?

-- 
-ck

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Sun, 2007-04-29 at 20:53 +1000, Con Kolivas wrote:
> On Sunday 29 April 2007 20:30, Thomas Gleixner wrote:
> > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> > CFS modifies the scheduler and nothing else, SD fiddles all over the
> > kernel in interesting ways.
> 
> This is a WTF if ever I saw one.

Sorry. My dumbness. I went into the wrong directory to run the diffstat.
It had the full ck set applied.

	tglx

/me goes off to clean the harddisk

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Sun, 2007-04-29 at 13:11 +0200, Willy Tarreau wrote:
> > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> 
> Contrarily to most people, I don't see them as competitors. I see SD as
> a first step with a low risk of regression, and CFS as an ultimate
> solution relying on a more solid framework.

That's the whole reason why I don't see any usefulness in merging SD
now. When we merge SD now, then we need to care of both - the real
solution and the fixup of regressions. Right now we have a not perfect
scheduler with known weak points. Ripping it out and replacing it is
going to introduce regressions, what ever low risk you see.

And I still do not see a benefit of an intermediate step with a in my
opinion medium to high risk of regressions, instead of going the full
way, when we agree that this is the correct solution.

	tglx

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Sun, 2007-04-29 at 13:11 +0200, Willy Tarreau wrote:
> On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
<snip>
> Contrarily to most people, I don't see them as competitors. I see SD as
> a first step with a low risk of regression, and CFS as an ultimate
> solution relying on a more solid framework.
> 
See this is the part i dont understand, what makes CFS the ultimate
solution compared to SD?

<snip>
> 
> Willy
> 
> 

Re: [patch] CFS scheduler, -v6

[Paolo Ciarrocchi]

On 4/29/07, Con Kolivas <kernel@kolivas.org> wrote:
> On Sunday 29 April 2007 21:11, Willy Tarreau wrote:
> > On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> > > Willy,
> > >
> > > On Sun, 2007-04-29 at 09:16 +0200, Willy Tarreau wrote:
> > > > In fact, what I'd like to see in 2.6.22 is something better for
> > > > everybody and with *no* regression, even if it's not perfect. I had the
> > > > feeling that SD matched that goal right now, except for Mike who has
> > > > not tested recent versions. Don't get me wrong, I still think that CFS
> > > > is a more interesting long-term target. But it may require more time to
> > > > satisfy everyone. At least with one of them in 2.6.22, we won't waste
> > > > time comparing to current mainline.
> > >
> > > Oh no, we really do _NOT_ want to throw SD or anything else at mainline
> > > in a hurry just for not wasting time on comparing to the current
> > > scheduler.
> >
> > It is not about doing it in a hurry. I see SD as a small yet efficient
> > update to current scheduler. It's not perfect, probably not much extensible
> > but the risks of breaking anything are small given the fact that it does
> > not change much of the code or behaviour.
> >
> > IMHO, it is something which can provide users with a useful update while
> > leaving us with some more time to carefully implement the features of CFS
> > one at a time, and if it requires 5 versions, it's not a problem.
> >
> > > I agree that CFS is the more interesting target and I prefer to push the
> > > more interesting one even if it takes a release cycle longer. The main
> > > reason for me is the design of CFS. Even if it is not really modular
> > > right now, it is not rocket science to make it fully modular.
> > >
> > > Looking at the areas where people work on, e.g. containers, resource
> > > management, cpu isolation, fully tickless systems ...., we really need
> > > to go into that direction, when we want to avoid permanent tinkering in
> > > the core scheduler code for the next five years.
> > >
> > > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> >
> > Contrarily to most people, I don't see them as competitors. I see SD as
> > a first step with a low risk of regression, and CFS as an ultimate
> > solution relying on a more solid framework.
> >
> > > CFS modifies the scheduler and nothing else, SD fiddles all over the
> > > kernel in interesting ways.
> >
> > Hmmm I guess you confused both of them this time. CFS touches many places,
> > which is why I think the testing coverage is still very low. SD can be
> > tested faster. My real concern is : are there still people observing
> > regressions with it ? If yes, they should be fixed before even being
> > merged. If no, why not merge it as a fix for the many known corner cases
> > of current scheduler ? After all, it's already in -mm.
> >
> > Willy
>
> Willy, you're making far too much sense. Are you replying to the correct
> mailing list?

FWIW, I strongly agree with Willy.

Ciao,
-- 
Paolo
"Tutto cio' che merita di essere fatto,merita di essere fatto bene"
Philip Stanhope IV conte di Chesterfield

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Sun, 2007-04-29 at 14:00 +0200, Kasper Sandberg wrote:
> On Sun, 2007-04-29 at 13:11 +0200, Willy Tarreau wrote:
> > On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> <snip>
> > Contrarily to most people, I don't see them as competitors. I see SD as
> > a first step with a low risk of regression, and CFS as an ultimate
> > solution relying on a more solid framework.
> > 
> See this is the part i dont understand, what makes CFS the ultimate
> solution compared to SD?

SD is a one to one replacement of the existing scheduler guts - with a
different behaviour.

CFS is a huge step into a modular and hierarchical scheduler design,
which allows more than just implementing a clever scheduler for a single
purpose. In a hierarchical scheduler you can implement resource
management and other fancy things, in the monolitic design of the
current scheduler (and it's proposed replacement SD) you can't. But SD
can be made one of the modular variants.

	tglx

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Sun, 2007-04-29 at 14:13 +0200, Thomas Gleixner wrote:
> On Sun, 2007-04-29 at 14:00 +0200, Kasper Sandberg wrote:
> > On Sun, 2007-04-29 at 13:11 +0200, Willy Tarreau wrote:
> > > On Sun, Apr 29, 2007 at 12:30:54PM +0200, Thomas Gleixner wrote:
> > <snip>
> > > Contrarily to most people, I don't see them as competitors. I see SD as
> > > a first step with a low risk of regression, and CFS as an ultimate
> > > solution relying on a more solid framework.
> > > 
> > See this is the part i dont understand, what makes CFS the ultimate
> > solution compared to SD?
> 
> SD is a one to one replacement of the existing scheduler guts - with a
> different behaviour.
> 
> CFS is a huge step into a modular and hierarchical scheduler design,
> which allows more than just implementing a clever scheduler for a single
> purpose. In a hierarchical scheduler you can implement resource
> management and other fancy things, in the monolitic design of the
> current scheduler (and it's proposed replacement SD) you can't. But SD
> can be made one of the modular variants.
But all these things, arent they just in the modular scheduler policy
code? and not the actual sched_cfs one?

> 
> 	tglx
> 
> 
> 

Re: [patch] CFS scheduler, -v6

[Willy Tarreau]

On Sun, Apr 29, 2007 at 01:59:13PM +0200, Thomas Gleixner wrote:
> On Sun, 2007-04-29 at 13:11 +0200, Willy Tarreau wrote:
> > > As a sidenote: I really wonder if anybody noticed yet, that the whole
> > > CFS / SD comparison is so ridiculous, that it is not even funny anymore.
> > 
> > Contrarily to most people, I don't see them as competitors. I see SD as
> > a first step with a low risk of regression, and CFS as an ultimate
> > solution relying on a more solid framework.
> 
> That's the whole reason why I don't see any usefulness in merging SD
> now. When we merge SD now, then we need to care of both - the real
> solution and the fixup of regressions. Right now we have a not perfect
> scheduler with known weak points. Ripping it out and replacing it is
> going to introduce regressions, what ever low risk you see.

Of course, but that's also the purpose of -rc. And given its small
footprint, it will be as easy to revert it as to apply it, should any
big problem appear.

> And I still do not see a benefit of an intermediate step with a in my
> opinion medium to high risk of regressions, instead of going the full
> way, when we agree that this is the correct solution.

The only difference is the time to get it in the right shape. If it
requires 3 versions (6 months), it may be worth "upgrading" the current
scheduler to make users happy. I'm not kidding, I've switched the default
boot to 2.6 on my notebook after trying SD and CFS. It was the first time
I got my system in 2.6 at least as usable as in 2.4. And I know I'm not
the only one.

Willy

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Sun, Apr 29, 2007 at 02:13:30PM +0200, Thomas Gleixner wrote:
> SD is a one to one replacement of the existing scheduler guts - with a
> different behaviour.
> CFS is a huge step into a modular and hierarchical scheduler design,
> which allows more than just implementing a clever scheduler for a single
> purpose. In a hierarchical scheduler you can implement resource
> management and other fancy things, in the monolitic design of the
> current scheduler (and it's proposed replacement SD) you can't. But SD
> can be made one of the modular variants.

The modularity provided is not enough to allow an implementation of
mainline, SD, or nicksched without significant core scheduler impact.

CFS doesn't have all that much to do with scheduler classes. A weak form
of them was done in tandem with the scheduler itself. The modularity
provided is sufficiently weak the advantage is largely prettiness of the
code. So essentially CFS is every bit as monolithic as mainline, SD, et
al, with some dressing that suggests modularity without actually making
any accommodations for alternative policies (e.g. reverting to mainline).

You'll hit the holes in the driver API quite quickly should you attempt
to port mainline to it. You'll hit several missing driver operations
right in schedule(), for starters. At some point you may also notice
that simple enqueue operations are not all that's there. Representing
enqueueing to active vs. expired and head vs. tail are needed for
current mainline to be representible by a set of driver operations.
It's also a bit silly to remove and re-insert a queue element for cfs
(or anything else using a tree-structured heap, which yes, a search
tree is, even if a slow one), which could use a reprioritization driver
operation, but I suppose it won't oops.

You'll also hit the same holes should you attempt to write such a
modularity patch for mainline as opposed to porting current mainline to
the driver API as-given. It takes a bit more work to get something that
actually works for all this, and it borders on disingenuity to
suggest that the scheduler class/driver API as it now stands is
capable of any such thing as porting current mainline, nicksched, or SD
to it without significant code impact to the core scheduler code.

So on both these points, I don't see cfs as being adequate as it now
stands for a modular, hierarchical scheduler design. If we want a truly
modular and hierarchical scheduler design, I'd suggest pursuing it
directly and independently of policy, and furthermore considering the
representability of various policies in the scheduling class/driver API
as a test of its adequacy.


-- wli

Re: [patch] CFS scheduler, -v6

[Thomas Gleixner]

On Sun, 2007-04-29 at 05:55 -0700, William Lee Irwin III wrote:
> You'll also hit the same holes should you attempt to write such a
> modularity patch for mainline as opposed to porting current mainline to
> the driver API as-given. It takes a bit more work to get something that
> actually works for all this, and it borders on disingenuity to
> suggest that the scheduler class/driver API as it now stands is
> capable of any such thing as porting current mainline, nicksched, or SD
> to it without significant code impact to the core scheduler code.

I never said, that the current implementation of CFS fits the criteria
of modularity, but it is a step in that direction. I'm well aware that
there is a bunch of things missing and it has hard coded leftovers,
which are related to the current two hard coded policy classes.

> So on both these points, I don't see cfs as being adequate as it now
> stands for a modular, hierarchical scheduler design. If we want a truly
> modular and hierarchical scheduler design, I'd suggest pursuing it
> directly and independently of policy, and furthermore considering the
> representability of various policies in the scheduling class/driver API
> as a test of its adequacy.

Ack. I don't worry much whether the CFS policy is better than the SD
one. I'm all for a truly modular design. SD and SCHED_FAIR are good
proofs for it.

	tglx

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Sunday 29 April 2007, Willy Tarreau wrote:
>On Sun, Apr 29, 2007 at 08:59:01AM +0200, Ingo Molnar wrote:
>> * Willy Tarreau <w@1wt.eu> wrote:
>> > I don't know if Mike still has problems with SD, but there are now
>> > several interesting reports of SD giving better feedback than CFS on
>> > real work. In my experience, CFS seems smoother on *technical* tests,
>> > which I agree that they do not really simulate real work.
>>
>> well, there are several reports of CFS being significantly better than
>> SD on a number of workloads - and i know of only two reports where SD
>> was reported to be better than CFS: in Kasper's test (where i'd like to
>> know what the "3D stuff" he uses is and take a good look at that
>> workload), and another 3D report which was done against -v6. (And even
>> in these two reports the 'smoothness advantage' was not dramatic. If you
>> know of any other reports then please let me know!)
>
>There was Caglar Onur too but he said he will redo all the tests. I'm
>not tracking all tests nor versions, so it might be possible that some
>of the differences vanish with v7.
>
>In fact, what I'd like to see in 2.6.22 is something better for everybody
>and with *no* regression, even if it's not perfect. I had the feeling
>that SD matched that goal right now, except for Mike who has not tested
>recent versions. Don't get me wrong, I still think that CFS is a more
>interesting long-term target. But it may require more time to satisfy
>everyone. At least with one of them in 2.6.22, we won't waste time
>comparing to current mainline.
>
>> 	Ingo
>
>Willy

In the FWIW category, I haven't built and tested a 'mainline' since at least 
2-3 weeks ago.  That's how dramatic the differences are here.  Here, my main 
notifier of scheduling fubar artifacts is usually kmail, which in itself 
seems to have a poor threading model, giving the composer pauses whenever its 
off sorting incoming mail, or compacting a folder, all the usual stuff that 
it needs to do in the background.  Those lags were from 10 to 30 seconds 
long, and I could type whole sentences before they showed up on screen with 
mainline.

The best either of these schedulers can do is hold that down to 3 or 4 words, 
but that's an amazing difference in itself.  With either of these schedulers, 
having a running gzip session that amanda launched in the background cause 
kmail to display a new message 5-30 seconds after the + key has been tapped 
is now into the sub 4 second range & often much less.  SD seems to, as it 
states, give everyone a turn at the well, so the slowdowns when gzip is 
running are somewhat more noticeable, whereas with CFS, gzip seems to be 
pretty well preempted long enough to process most user keypresses.  Not all, 
because tapping the + key to display the next message can at times be a 
pretty complex operation.

For my workload, CFS seems to be a marginally better solution, but either is 
so much better than mainline that there cannot be a reversion to mainline 
performance here without a lot of kicking and screaming.

'vmstat -n 1' results show that CFS uses a lot less time doing context 
switches, which as IUI, is to be counted against OS overhead as it does no 
productive work while the switch is being done.  For CFS, that's generally 
less than 500/second, and averageing around 350, which compared to SD046's 
average of about 18,000/second, it would appear that CFS allows more REAL 
work to get done by holding down on the non-productive time a context switch 
requires.

FWIW, amanda runtimes tend to back that up, most CFS runs are sub 2 hours, SD 
runs are seemingly around 2h:10m.  But that again is not over a sufficiently 
large sample to be a benchmark tool either, just one persons observation.  I 
should have marked the amdump logs so I could have determined that easier by 
tracking which scheduler was running for that dump.  amplot can be 
informative, but one must also correlate, and a week ago is ancient history 
as I have no way to verify which I was running then.

The X86's poor register architecture pretty well chains us to the 'context 
switch' if we want multitasking.

I'm reminded of how that was handled on a now largely dead architecture some 
here may never have seen an example of, TI's 99xx chips, where all 
accumulators and registers were actually stored in memory, and a context 
switch was a simply matter of reloading the register that pointed into this 
memory array with a new address so a context switch was just a matter of 
reading the next processes address and storing it in the address register, 
itself also just a location in memory.  The state image of the process 
being 'put to sleep' was therefore maintained indefinitely as long as the 
memory was refreshed.  Too bad we can't do that on the x86 but I assume TI 
has patent lawyers standing by ready to jump on that one.  However, with 
today's L1 cache being the speed and size that it is, it sure looks like a 
doable thing even at 2GHZ+ clocks.

Yup, we've tried lots of very productive ways to get that job done over the 
last 40 years, and everytime somebody has a really good idea, the patent 
prevents its application.  And they call that progress...  SIGH..  Just 
imagine how much money TI would have today if the royalty asked had only been 
a dime a chip...  And to a very limited extent, one could do that on an 
RCA-180x too, using its plethora of internal registers, any of which could be 
made the PC or SP (or DMA pointer too IIRC) with a one byte command.

Anyway, in my mind CFS wins this round, but its a smallish margin, like 
judging ice skaters, a 9.7 vs 9.5 rating.  Not a huge difference, until 
mainlines 0.0 score is thrown into the pot for a reality check comparison.

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
And on the eighth day, we bulldozed it.

Re: [patch] CFS scheduler, -v6

[Gene Heskett]

On Sunday 29 April 2007, Paolo Ciarrocchi wrote:
[...]

>> > > CFS modifies the scheduler and nothing else, SD fiddles all over the
>> > > kernel in interesting ways.

Huh?  Doesn't grok.

>> > Hmmm I guess you confused both of them this time. CFS touches many
>> > places, which is why I think the testing coverage is still very low. SD
>> > can be tested faster. My real concern is : are there still people
>> > observing regressions with it ? If yes, they should be fixed before even
>> > being merged. If no, why not merge it as a fix for the many known corner
>> > cases of current scheduler ? After all, it's already in -mm.
>> >
>> > Willy
>>
>> Willy, you're making far too much sense. Are you replying to the correct
>> mailing list?
>
>FWIW, I strongly agree with Willy.

If we're putting it to a vote, I'm with Willy.  But this is a dictatorship and 
we shouldn't forget it. :)

-- 
Cheers, Gene
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
An ambassador is an honest man sent abroad to lie and intrigue for the
benefit of his country.
		-- Sir Henry Wotton, 1568-1639

Re: [patch] CFS scheduler, -v6

[Ray Lee]

On 4/29/07, Kasper Sandberg <lkml@metanurb.dk> wrote:
> On Sun, 2007-04-29 at 08:59 +0200, Ingo Molnar wrote:
> > well, there are several reports of CFS being significantly better than
> > SD on a number of workloads - and i know of only two reports where SD
> > was reported to be better than CFS: in Kasper's test (where i'd like to
> > know what the "3D stuff" he uses is and take a good look at that
> > workload), and another 3D report which was done against -v6. (And even
> > in these two reports the 'smoothness advantage' was not dramatic. If you
> > know of any other reports then please let me know!)
>
> I can tell you one thing, its not just me that has observed the
> smoothness in 3d stuff, after i tried rsdl first i've had lots of people
> try rsdl and subsequently sd because of the significant improvement in
> smoothness, and they have all found the same results.
>
> The stuff i have tested with in particular is unreal tournament 2004 and
> world of warcraft through wine, both running opengl, and consuming all
> the cpu time it can get.

[snip more of sd smoother than cfs report]

WINE is an interesting workload as it does most of its work out of
process to the 'wineserver', which then does more work out of process
to the X server. So, it's three mutually interacting processes total,
once one includes the original client (Unreal Tournament or World of
Warcraft, in this case).

Perhaps running one of the windows system performance apps (that can
be freely downloaded) under WINE would give some hard numbers people
could use to try to reproduce the report.

Ray

Re: [patch] CFS scheduler, -v6

[Kasper Sandberg]

On Sun, 2007-04-29 at 08:42 -0700, Ray Lee wrote:
> On 4/29/07, Kasper Sandberg <lkml@metanurb.dk> wrote:
> > On Sun, 2007-04-29 at 08:59 +0200, Ingo Molnar wrote:
> > > well, there are several reports of CFS being significantly better than
> > > SD on a number of workloads - and i know of only two reports where SD
> > > was reported to be better than CFS: in Kasper's test (where i'd like to
> > > know what the "3D stuff" he uses is and take a good look at that
> > > workload), and another 3D report which was done against -v6. (And even
> > > in these two reports the 'smoothness advantage' was not dramatic. If you
> > > know of any other reports then please let me know!)
> >
> > I can tell you one thing, its not just me that has observed the
> > smoothness in 3d stuff, after i tried rsdl first i've had lots of people
> > try rsdl and subsequently sd because of the significant improvement in
> > smoothness, and they have all found the same results.
> >
> > The stuff i have tested with in particular is unreal tournament 2004 and
> > world of warcraft through wine, both running opengl, and consuming all
> > the cpu time it can get.
> 
> [snip more of sd smoother than cfs report]
> 
> WINE is an interesting workload as it does most of its work out of
> process to the 'wineserver', which then does more work out of process
> to the X server. So, it's three mutually interacting processes total,
> once one includes the original client (Unreal Tournament or World of
> Warcraft, in this case).
the wineserver process is using next to no cpu-time compared to the main
process..

> 
> Perhaps running one of the windows system performance apps (that can
> be freely downloaded) under WINE would give some hard numbers people
> could use to try to reproduce the report.
> 
> Ray
> 

Re: [patch] CFS scheduler, -v6

[Mark Lord]

Willy Tarreau wrote:
> ..
> Contrarily to most people, I don't see them as competitors. I see SD as
> a first step with a low risk of regression, and CFS as an ultimate
> solution relying on a more solid framework.

I see SD as 100% chance of regression on my main machine.

But I will retest (on Monday?) with the latest, just to see
if it has improved closer to mainline or not.

-ml

3d smoothness (was: Re: [patch] CFS scheduler, -v6)

[Kasper Sandberg]

On Sunday 29 April 2007 19:39, Ingo Molnar wrote:
> hi Kasper,
>
> i found an aspect of CFS that could cause the kind of 'stuttering' you
> described in such detail. I'm wondering whether you could try the
> attached -v8-rc1 patch ontop of the -v7 CFS patch - does it improve the
> 'games FPS' situation in any way? Thanks in advance,
>
> 	Ingo

This patch makes things much worse, i'd categorize it as severe regression
compared to cfs 7. It makes the cursor in X stutter enormously, it even 
caused my entire X to lock up for a second, and events like keyboard input is 
totally wrecked, it lagged as i wrote in xchat. as for under load, it seems 
only worse..

Also if i just press a link in konqueror on some website, while it loads, the 
mouse is stuttering untill the page has loaded finished.

this seems weird because its such a relatively simple patch.

In the patchs defense, gtk seems to redraw faster (when, and only when 3d is 
NOT running)

i also discovered another thing about cfs 7 (without this patch), which is 
same behavior as old staircase/vanilla, but which SD actually fixes.

this is a wine case, where when it loads a level in world of warcraft, the 
audio skips. I believe this to be a problem in wine, however, in sd it 
actually does not skip. On the desktop however, the audio issues were totally 
fixed in v7..

mvh.
Kasper Sandberg

Re: 3d smoothness (was: Re: [patch] CFS scheduler, -v6)

[Ingo Molnar]

* Kasper Sandberg <lkml@metanurb.dk> wrote:

> This patch makes things much worse, [...]

yeah, the small patch i sent to you in private mail was indeed buggy,
please disregard it.

	Ingo

Re: 3d smoothness (was: Re: [patch] CFS scheduler, -v6)

[Kasper Sandberg]

On Mon, 2007-04-30 at 22:17 +0200, Ingo Molnar wrote:
> * Kasper Sandberg <lkml@metanurb.dk> wrote:
> 
> > This patch makes things much worse, [...]
> 
> yeah, the small patch i sent to you in private mail was indeed buggy,
> please disregard it.
It also hardlocked my box :) but it was worth a shot.
> 
> 	Ingo
> 

Re: [patch] CFS scheduler, -v6

[Nick Piggin]

On Sun, Apr 29, 2007 at 03:37:47PM +0200, Thomas Gleixner wrote:
> On Sun, 2007-04-29 at 05:55 -0700, William Lee Irwin III wrote:
> > You'll also hit the same holes should you attempt to write such a
> > modularity patch for mainline as opposed to porting current mainline to
> > the driver API as-given. It takes a bit more work to get something that
> > actually works for all this, and it borders on disingenuity to
> > suggest that the scheduler class/driver API as it now stands is
> > capable of any such thing as porting current mainline, nicksched, or SD
> > to it without significant code impact to the core scheduler code.
> 
> I never said, that the current implementation of CFS fits the criteria
> of modularity, but it is a step in that direction. I'm well aware that
> there is a bunch of things missing and it has hard coded leftovers,
> which are related to the current two hard coded policy classes.

[ I've tuned out of most of the scheduler discussion lately, sorry ;) ]


People seem to be confusing scheduler policy with a modular framework.

First of all, I don't know that any of the schedulers can "just go in"
and replace the mainline one, because they are still under development
and have not been sufficiently tested and contrasted IMO.

Secondly, if we want to have a modular framework, it should:
- be a seperate patchset to any new scheduler policy
- obviously retain the existing policy for testing / comparison purposes
- be able to be compiled out. I don't know whether it's CFS policy or
  the framework (maybe both), but CFS is quite a bit slower at context
  switching when I last measured with lmbench (several releases ago).

I still would rather not have a modular framework unless we decide
that is the only wake to make upstream progress. But if we did have
the modular framework, we still need to decide on the process of
avoiding profileration, selecting a default scheduler, and a plan for
future phasing out of non-default GP schedulers once a new one gets
selected.

Re: [patch] CFS scheduler, -v6

[William Lee Irwin III]

On Tue, May 01, 2007 at 09:55:15AM +0200, Nick Piggin wrote:
> People seem to be confusing scheduler policy with a modular framework.
> First of all, I don't know that any of the schedulers can "just go in"
> and replace the mainline one, because they are still under development
> and have not been sufficiently tested and contrasted IMO.

I've already made noise about separate modular framework patches, so
recast whatever confusion seems apparent to you in those terms.


On Tue, May 01, 2007 at 09:55:15AM +0200, Nick Piggin wrote:
> Secondly, if we want to have a modular framework, it should:
> - be a seperate patchset to any new scheduler policy
> - obviously retain the existing policy for testing / comparison purposes
> - be able to be compiled out. I don't know whether it's CFS policy or
>   the framework (maybe both), but CFS is quite a bit slower at context
>   switching when I last measured with lmbench (several releases ago).

Compiling such things out is interesting at best, as they typically
require significant code restructuring. You can make the indirect calls
conditional by calling some particular driver directly inside wrapper
macros for the indirect calls via case analysis on ->policy, I suppose.

There are issues with using cfs' notion of a modular framework to
verify performance non-regression, in particular the fact it's
incapable of representing mainline. There is also the problem of doing
very little in the way of hiding data, so that in the event of using it
to compare different implementations of the same policy, e.g. competing
SCHED_OTHER implementations, each is stuck maintaining the others'
state variables, save for the case where one or both happens to have
all its state variable updates fit entirely inside the driver operations,
in which case they still take the hit for bloating the task_struct, and
worse yet, some asymmetry in terms of which is exempt from maintaining
the others' state variables occurs which furthermore penalizes the
competitor maintaining the least state or doing the least state updates.
Such a state of affairs must not be allowed to stand.


On Tue, May 01, 2007 at 09:55:15AM +0200, Nick Piggin wrote:
> I still would rather not have a modular framework unless we decide
> that is the only wake to make upstream progress. But if we did have
> the modular framework, we still need to decide on the process of
> avoiding profileration, selecting a default scheduler, and a plan for
> future phasing out of non-default GP schedulers once a new one gets
> selected.

It certainly cuts down on the eye bleed but I suppose that takes a
back seat to performance considerations.


-- wli

Re: [patch] CFS scheduler, -v6

[Art Haas]

Hi.

Just wanted to chime and and say that my build of 2.6.21 + CFS-v6 + PI
patch by Thomas Gleixner has been running exceptionally well on my
single processor PII machine (Debian unstable) and my SMP PII machine
(Fedora Rawhide). On both systems no automatic 'renice'-ing happens,
and I've not noticed any performance issues on the Debian box while
in X. The Fedora machine currently runs X only occasionally as most of
the time I use it for building and testing various non-graphical
things.

Art Haas
-- 
Man once surrendering his reason, has no remaining guard against absurdities
the most monstrous, and like a ship without rudder, is the sport of every wind.

-Thomas Jefferson to James Smith, 1822