RSDL completely fair starvation free interactive cpu scheduler

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

This message is to announce the first general public release of the "Rotating Staircase DeadLine" cpu scheduler.

Just to make it clear. The purpose of this scheduler is at all costs to maintain absolute fairness no matter what type of load it is put under.

This means that if you heavily load up your machine without the use of 'nice' then your interactive tasks _will_ slow down proportionately to the amount of cpu you use. So doing make -j4 for example will make any other task started in taht presence run precisely 1/5th speed, but they will still be responsive, have low latency (and audio shouldn't skip for example).

Quoted 2 lines · Con Kolivas

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

Quoted 2 lines

This message is to announce the first general public release of the "Rotating Staircase DeadLine" cpu scheduler.

Thanks a lot!

Quoted 3 lines

Just to make it clear. The purpose of this scheduler is at all costs to maintain absolute fairness no matter what type of load it is put under.

Great!

Quoted 6 lines

This means that if you heavily load up your machine without the use of 'nice' then your interactive tasks _will_ slow down proportionately to the amount of cpu you use. So doing make -j4 for example will make any other task started in taht presence run precisely 1/5th speed, but they will still be responsive, have low latency (and audio shouldn't skip for example).

That's just what it did, but when you "nice make -j4", things (gears) start to stutter. Is that due to the staircase?

Quoted 12 lines · Con Kolivas

Quoted 10 lines · Al Boldi

Quoted 6 lines · Con Kolivas

This means that if you heavily load up your machine without the use of 'nice' then your interactive tasks _will_ slow down proportionately to the amount of cpu you use. So doing make -j4 for example will make any other task started in taht presence run precisely 1/5th speed, but they will still be responsive, have low latency (and audio shouldn't skip for example).

That's just what it did, but when you "nice make -j4", things (gears) start to stutter. Is that due to the staircase?

Quoted 7 lines

gears isn't an interactive task. Apart from using it as a background load to check for starvation because it loads up the cpu fully (which a gpu intensive but otherwise simple app like this should _not_ do) graphics card drivers and interrupts and so on, I wouldn't put much credence on gears as anything else. However I suspect that gears will still get a fair share of the cpu on RSDL which almost never happens on any other scheduler.

If I run glxgears, thunderbird/firefox become really slow to respond/display and cpu usage isn't even at 100%. I had thunderbird lagging on keyboard character repeat earlier but can't reproduce that now even with glxgears - however firefox lags really badly on keyboard input with glxgears running.

Quoted 5 lines · Simon Arlott

If I run glxgears, thunderbird/firefox become really slow to respond/display and cpu usage isn't even at 100%. I had thunderbird lagging on keyboard character repeat earlier but can't reproduce that now even with glxgears - however firefox lags really badly on keyboard input with glxgears running.

Hi Simon

You're hitting a nasty udev bug here that is unrelated to the cpu scheduler

and almost certainly responsible for your bad behaviour.

Also this patch was actually for 2.6.20 and you seem to have applied it to 2.6.21-rc2. I haven't even checked that it cleanly applies to that kernel.

Quoted 11 lines · Con Kolivas

Quoted 5 lines · Simon Arlott

If I run glxgears, thunderbird/firefox become really slow to respond/display and cpu usage isn't even at 100%. I had thunderbird lagging on keyboard character repeat earlier but can't reproduce that now even with glxgears - however firefox lags really badly on keyboard input with glxgears running.

Hi Simon

You're hitting a nasty udev bug here that is unrelated to the cpu scheduler

Yes, I've already reported this.

Quoted 1 line

and almost certainly responsible for your bad behaviour.

What? How do you make the leap from lockdep output on boot to my experience of slow interactive response?

Quoted 3 lines

Also this patch was actually for 2.6.20 and you seem to have applied it to 2.6.21-rc2. I haven't even checked that it cleanly applies to that kernel.

It doesn't, a one line fix from Ingo conflicts (and a comment that was changed). 7355690ead6d61f6344072ae61060f985060da29 [PATCH] sched: fix SMT scheduler bug 72fd4a35a824331d7a0f4168d7576502d95d34b3 [PATCH] Numerous fixes to kernel-doc info in source files.

I have reverted your patch and the laggy behaviour remains when running glxgears (in fact it seems a bit worse), I don't know about the thunderbird lag while typing since I can't easily reproduce it but I don't recall it ever happening before. So, your patch isn't the cause of a serious slowdown when running glxgears in the background (although it doesn't improve the situation much). It looks like it just slows down X in general rather than using much CPU.

Quoted 2 lines

That's just what it did, but when you "nice make -j4", things (gears) start to stutter. Is that due to the staircase?

gears isn't an interactive task. Apart from using it as a background load to check for starvation because it loads up the cpu fully (which a gpu intensive but otherwise simple app like this should _not_ do) graphics card drivers and interrupts and so on, I wouldn't put much credence on gears as anything else. However I suspect that gears will still get a fair share of the cpu on RSDL which almost never happens on any other scheduler.

(...)

Quoted 10 lines

Quoted 2 lines

That's just what it did, but when you "nice make -j4", things (gears) start to stutter. Is that due to the staircase?

gears isn't an interactive task. Apart from using it as a background load to check for starvation because it loads up the cpu fully (which a gpu intensive but otherwise simple app like this should _not_ do) graphics card drivers and interrupts and so on, I wouldn't put much credence on gears as anything else. However I suspect that gears will still get a fair share of the cpu on RSDL which almost never happens on any other scheduler.

Con,

I've now given it a try with HZ=250 on my dual-athlon. It works beautifully. I also quickly checked that playing mp3 doesn't skip during make -j4, and that gears runs fairly smoothly, since those are the references people often use.

But with real work, it's excellent too. When I saturate my CPUs by injecting HTTP traffic on haproxy, the load is stable and the command line perfectly responsive, while in the past the load would oscillate and the command line sometimes stopped to respond for a few seconds.

I've also launched my scheddos program (you may remember, the one we did a few experiments with). I could not cause any freeze at all. Plain 2.6.20 had already improved a lot in this area, but above 4 processes/CPU, occasional short freezes did still occur. This time, even at 100 processes, the system was rather slow (of course!) but just as expected, and nothing more.

I also tried the good old "dd if=/dev/zero bs=1|...|dd bs=1 of=/dev/null" and it did not cause any trouble.

I will boot 2.6 slightly more often to test the code under various conditions, and I will recommend it to a few people I know who tend to switch back to 2.4 after one day full of 2.6 jerkiness.

Overall, you have done a great job !

I hope that more people will give it a try, first to help find possible remaining bugs, and to pronounce in favour of its inclusion in mainline.

Cheers,
Willy

I've now given it a try with HZ=250 on my dual-athlon.

It works
beautifully. I also quickly checked that playing mp3 doesn't skip during make -j4, and that gears runs fairly smoothly, since those are the references people often use.

But with real work, it's excellent too. When I saturate my CPUs by injecting HTTP traffic on haproxy, the load is stable and the command line perfectly responsive, while in the past the load would oscillate and the command line sometimes stopped to respond for a few seconds.

I've also launched my scheddos program (you may remember, the one we did a few experiments with). I could not cause any freeze at all. Plain 2.6.20 had already improved a lot in this area, but above 4 processes/CPU, occasional short freezes did still occur. This time, even at 100 processes, the system was rather slow (of course!) but just as expected, and nothing more.

I also tried the good old "dd if=/dev/zero bs=1|...|dd bs=1 of=/dev/null" and it did not cause any trouble.

I will boot 2.6 slightly more often to test the code under various conditions, and I will recommend it to a few people I know who tend to switch back to 2.4 after one day full of 2.6 jerkiness.

Overall, you have done a great job !

I hope that more people will give it a try, first to help find possible remaining bugs, and to pronounce in favour of its inclusion in mainline.

On Mon, Mar 05, 2007 at 08:49:29AM +1100, Con Kolivas wrote:
(...)

Quoted 10 lines

Quoted 2 lines

That's just what it did, but when you "nice make -j4", things (gears) start to stutter. Is that due to the staircase?

gears isn't an interactive task. Apart from using it as a background load to check for starvation because it loads up the cpu fully (which a gpu intensive but otherwise simple app like this should _not_ do) graphics card drivers and interrupts and so on, I wouldn't put much credence on gears as anything else. However I suspect that gears will still get a fair share of the cpu on RSDL which almost never happens on any other scheduler.

Con,

I've now given it a try with HZ=250 on my dual-athlon. It works beautifully. I also quickly checked that playing mp3 doesn't skip during make -j4, and that gears runs fairly smoothly, since those are the references people often use.

But with real work, it's excellent too. When I saturate my CPUs by injecting HTTP traffic on haproxy, the load is stable and the command line perfectly responsive, while in the past the load would oscillate and the command line sometimes stopped to respond for a few seconds.

I've also launched my scheddos program (you may remember, the one we did a few experiments with). I could not cause any freeze at all. Plain 2.6.20 had already improved a lot in this area, but above 4 processes/CPU, occasional short freezes did still occur. This time, even at 100 processes, the system was rather slow (of course!) but just as expected, and nothing more.

I also tried the good old "dd if=/dev/zero bs=1|...|dd bs=1 of=/dev/null" and it did not cause any trouble.

I will boot 2.6 slightly more often to test the code under various conditions, and I will recommend it to a few people I know who tend to switch back to 2.4 after one day full of 2.6 jerkiness.

Overall, you have done a great job !

I hope that more people will give it a try, first to help find possible remaining bugs, and to pronounce in favour of its inclusion in mainline.

Cheers,
Willy

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 4 lines · Al Boldi

Ok, gears is smooth when you run "make -j4", but with "nice make -j4", gears becomes bursty. This looks like a problem with nice-levels. In general, looking subjectively at top d.1, procs appear to show jerkiness when nice'd.

Don't use glxgears, please. Ever. Unless you want meaningless gears.

It displays totally erratic behaviour anyway, and does sched_yield (strace tells us this) which means IT GIVES UP ITS TIME TO RUN, ie yields the cpu to someone else.

Quoted 2 lines

Do you have an objective test-case that can show the even-ness of RSDL in both nice'd and normal scenarios?

A big movie, like DVD-quality, full resolution should do the trick. That's what I used ;)

Debian and Ubuntu at least ship "stress" which I also used and reniced in-flight with excellent results, but do note to start off with small settings and work up or you might overcommit your box, in a way which no scheduler can handle.

Quoted 5 lines · Markus Törnqvist

Quoted 4 lines · Al Boldi

Ok, gears is smooth when you run "make -j4", but with "nice make -j4", gears becomes bursty. This looks like a problem with nice-levels. In general, looking subjectively at top d.1, procs appear to show jerkiness when nice'd.

Quoted 1 line

Don't use glxgears, please. Ever. Unless you want meaningless gears.

Quoted 3 lines

It displays totally erratic behaviour anyway, and does sched_yield (strace tells us this) which means IT GIVES UP ITS TIME TO RUN, ie yields the cpu to someone else.

I just strace'd it here. It doesn't show any yield in the mesa-5.0 version. Which version are you using?

Quoted 4 lines · Con Kolivas

Gears just isn't an interactive task and just about anything but gears would be a better test case since its behaviour varies wildly under different combinations of graphics cards, memory bandwidth, cpu and so on.

What about reflect? It has the same problem.

Quoted 1 line

I'm not even sure what you're trying to prove with gears.

RSDL fairness.

Ok, try this:

# gears & gears &
Both run smoothly.
# nice gears & nice gears &
Both run smoothly.

Now:

# gears & nice -10 gears &
Both stutter.

But:

# gears & nice --10 gears &
Both run smoothly.

Something looks fishy with nice levels.

Otherwise, your scheduler looks great!

Hah I just wish gears would go away. If I get hardware where it runs at just the right speed it looks like it doesn't move at all. On other hardware the wheels go backwards and forwards where the screen refresh rate is just perfectly a factor of the frames per second (or something like that).

This is not a cpu scheduler test and you're inferring that there are cpu scheduling artefacts based on an application that has bottlenecks at different places depending on the hardware combination.

Quoted 9 lines · Con Kolivas

Hah I just wish gears would go away. If I get hardware where it runs at just the right speed it looks like it doesn't move at all. On other hardware the wheels go backwards and forwards where the screen refresh rate is just perfectly a factor of the frames per second (or something like that).

This is not a cpu scheduler test and you're inferring that there are cpu scheduling artefacts based on an application that has bottlenecks at different places depending on the hardware combination.

I'd add that Xorg has its own scheduler (for X11 operations, of course), that has its own quirks, and chances are that it is the one you're testing with glxgears. And as Con said, as long as glxgears does more FPS than your screen refresh rate, its flickering its completely
meaningless: it doesn't even attempt to sync with vblank. Al, you'd better try with Quake3 or Nexuiz, or even Blender if you want to test 3D interactivity under load.

BTW, another way to show these hickups would be through some kind of a cpu/proc timing-tracer. Do we have something like that?

Quoted 2 lines · Al Boldi

BTW, another way to show these hickups would be through some kind of a cpu/proc timing-tracer. Do we have something like that?

Here is something like a tracer.

Original idea by Chris Friesen, thanks, from this post:
http://marc.theaimsgroup.com/?l=linux-kernel&m=117331003029329&w=4

Try attached chew.c like this:
Boot into /bin/sh.
Run chew in one console.
Run nice chew in another console.
Watch timings.

Console 1: ./chew

Console 2: nice -10 ./chew

pid 669, prio 10, out for 5 ms
pid 669, prio 10, out for 65 ms

pid 669, prio 10, out for 6 ms
pid 669, prio 10, out for 65 ms

Console 2: nice -15 ./chew
pid 673, prio 15, out for 6 ms
pid 673, prio 15, out for 95 ms

OTOH, mainline is completely smooth, albeit huge drop-outs.

Thanks!

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Quoted 7 lines · Con Kolivas

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 3 lines

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Applied on top of v0.28 mainline, and there is no difference.

What's it look like on your machine?

Quoted 8 lines · Al Boldi

Quoted 7 lines · Con Kolivas

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 7 lines

Quoted 3 lines

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Applied on top of v0.28 mainline, and there is no difference.

What's it look like on your machine?

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 17 lines · Con Kolivas

Quoted 8 lines · Al Boldi

Quoted 7 lines · Con Kolivas

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 7 lines

Quoted 3 lines

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Applied on top of v0.28 mainline, and there is no difference.

What's it look like on your machine?

Quoted 9 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Quoted 10 lines

Quoted 9 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

Quoted 13 lines · Con Kolivas

Quoted 10 lines

Quoted 9 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Quoted 9 lines

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

It only takes one negatively nice'd proc to affect X adversely.

Thanks!

--
Al

_______________________________________________
http://ck.kolivas.org/faqs/replying-to-mailing-list.txt
ck mailing list - mailto: [email protected]
http://vds.kolivas.org/mailman/listinfo/ck

Op Monday 12 March 2007, schreef Al Boldi:

Quoted 2 lines

It only takes one negatively nice'd proc to affect X adversely.

goes faster than ever)? Or is this really the scheduler's fault?

Quoted 1 line

It only takes one negatively nice'd proc to affect X adversely.

Then, maybe, we should start nicing X again, like we did/had to do until a few years ago? Or should we just wait until X gets fixed (after all, development goes faster than ever)? Or is this really the scheduler's fault?

Quoted 13 lines · Con Kolivas

Quoted 10 lines

Quoted 9 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Quoted 9 lines

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

It only takes one negatively nice'd proc to affect X adversely.

Quoted 25 lines

Quoted 23 lines · Con Kolivas

Quoted 11 lines

Quoted 10 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

Quoted 1 line

It only takes one negatively nice'd proc to affect X adversely.

I have an idea. Give me some time to code up my idea. Lack of sleep is making me very unpleasant.

Op Monday 12 March 2007, schreef Con Kolivas:

Quoted 26 lines · Al Boldi

Quoted 25 lines

Quoted 23 lines · Con Kolivas

Quoted 11 lines

Quoted 10 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

Quoted 4 lines

Quoted 1 line

It only takes one negatively nice'd proc to affect X adversely.

I have an idea. Give me some time to code up my idea. Lack of sleep is making me very unpleasant.

You're excited by RSDL and the positive comments, aren't you? Well, don't forget to sleep, sleeping makes ppl smarter you know ;-)

IIRC, about 2 or three years ago (or maybe on the 2.6.10 timeframe), there was a patch which managed to pass the interactive from one app to another when there was a pipe or udp connection between them. This meant that a marked-as-interactive xterm would, when blocked waiting for an Xserver response, transfer some of its interactiveness to the Xserver, and aparently it worked very good for desktop workloads so, maybe adapting it for this new scheduler would be good.

Quoted 24 lines · Al Boldi

Quoted 23 lines · Con Kolivas

Quoted 7 lines · Al Boldi

Quoted 6 lines · Con Kolivas

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 6 lines

Quoted 3 lines

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Applied on top of v0.28 mainline, and there is no difference.

What's it look like on your machine?

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

Quoted 28 lines

Quoted 17 lines · Con Kolivas

Quoted 8 lines · Al Boldi

Quoted 7 lines · Con Kolivas

Quoted 5 lines · Con Kolivas

And thank you! I think I know what's going on now. I think each rotation is followed by another rotation before the higher priority task is getting a look in in schedule() to even get quota and add it to the runqueue quota. I'll try a simple change to see if that helps. Patch coming up shortly.

Quoted 7 lines

Quoted 3 lines

Can you try the following patch and see if it helps. There's also one minor preemption logic fix in there that I'm planning on including. Thanks!

Applied on top of v0.28 mainline, and there is no difference.

What's it look like on your machine?

Quoted 9 lines

The higher priority one always get 6-7ms whereas the lower priority one runs 6-7ms and then one larger perfectly bound expiration amount. Basically exactly as I'd expect. The higher priority task gets precisely RR_INTERVAL maximum latency whereas the lower priority task gets RR_INTERVAL min and full expiration (according to the virtual deadline) as a maximum. That's exactly how I intend it to work. Yes I realise that the max latency ends up being longer intermittently on the niced task but that's -in my opinion- perfectly fine as a compromise to ensure the nice 0 one always gets low latency.

Quoted 2 lines

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

There is a way that I toyed with of creating maps of slots to use for each different priority, but it broke the O(1) nature of the virtual deadline management. Minimising algorithmic complexity seemed more important to maintain than getting slightly better latency spreads for niced tasks. It also appeared to be less cache friendly in design. I could certainly try and implement it but how much importance are we to place on latency of niced tasks? Are you aware of any usage scenario where latency sensitive tasks are ever significantly niced in the real world?

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Quoted 2 lines · Al Boldi

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Can you try the attached patch please Al and Mike? It "dithers" the priority bitmap which tends to fluctuate the latency a lot more but in a cyclical fashion. This tends to make the max latency bound to a smaller value and should make it possible to run -nice tasks without killing the latency of the non niced tasks. Eg you could possibly run X nice -10 at a guess like we used to in 2.4 days. It's not essential of course, but is a workaround for Mike's testcase.

Quoted 11 lines · Con Kolivas

Quoted 2 lines · Al Boldi

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Can you try the attached patch please Al and Mike? It "dithers" the priority bitmap which tends to fluctuate the latency a lot more but in a cyclical fashion. This tends to make the max latency bound to a smaller value and should make it possible to run -nice tasks without killing the latency of the non niced tasks. Eg you could possibly run X nice -10 at a guess like we used to in 2.4 days. It's not essential of course, but is a workaround for Mike's testcase.

Oops, one tiny fix. This is a respin of the patch, sorry.

Quoted 11 lines · Con Kolivas

Quoted 2 lines · Al Boldi

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Can you try the attached patch please Al and Mike? It "dithers" the priority bitmap which tends to fluctuate the latency a lot more but in a cyclical fashion. This tends to make the max latency bound to a smaller value and should make it possible to run -nice tasks without killing the latency of the non niced tasks. Eg you could possibly run X nice -10 at a guess like we used to in 2.4 days. It's not essential of course, but is a workaround for Mike's testcase.

Oops, one tiny fix. This is a respin of the patch, sorry.
---

Quoted 13 lines · Con Kolivas

Quoted 11 lines · Con Kolivas

Quoted 2 lines · Al Boldi

I think, it should be possible to spread this max expiration latency across the rotation, should it not?

Can you try the attached patch please Al and Mike? It "dithers" the priority bitmap which tends to fluctuate the latency a lot more but in a cyclical fashion. This tends to make the max latency bound to a smaller value and should make it possible to run -nice tasks without killing the latency of the non niced tasks. Eg you could possibly run X nice -10 at a guess like we used to in 2.4 days. It's not essential of course, but is a workaround for Mike's testcase.

Quoted 1 line

Oops, one tiny fix. This is a respin of the patch, sorry.

Bah with a bit more sleep under my belt it became clear that I forgot to update the expired array in any proper way so this change almost breaks stuff at the moment in the shape it's in. Please disregard this change for now apart from interest in how I'm tackling the nice issue.

However, I must inform people that I have to arrest the RSDL development for at least this week. I have a new and fairly serious neck problem that is being exacerbated badly by sitting in front of the computer for any extended period.

Here are full patches for rsdl 0.31 for various base kernels. A full announce with a fresh -mm series will follow...

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.3-rsdl-0.31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-sched-rsdl-0.31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-mm2-rsdl-0.31.patch

Quoted 8 lines · Con Kolivas

Here are full patches for rsdl 0.31 for various base kernels. A full announce with a fresh -mm series will follow...

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.3-rsdl-0.31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-sched-rsdl-0.
31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-mm2-rsdl-0.31
.patch

It still has trouble with the x/gforce vs two niced encoders scenario. The previously reported choppiness is still present.

I suspect that x/gforce landing in the expired array is the trouble, and that this will never be smooth without some kind of exemption. I added some targeted unfairness to .30, and it didn't help much at all.

Priorities going all the way to 1 were a surprise.

Quoted 13 lines · Mike Galbraith

Quoted 8 lines · Con Kolivas

Here are full patches for rsdl 0.31 for various base kernels. A full announce with a fresh -mm series will follow...

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.3-rsdl-0.31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-sched-rsdl-0.
31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-mm2-rsdl-0.31
.patch

It still has trouble with the x/gforce vs two niced encoders scenario. The previously reported choppiness is still present.

Quoted 5 lines

I suspect that x/gforce landing in the expired array is the trouble, and that this will never be smooth without some kind of exemption. I added some targeted unfairness to .30, and it didn't help much at all.

Priorities going all the way to 1 were a surprise.

It wasn't going to change that case without renicing X.

Quoted 21 lines · Mike Galbraith

Quoted 19 lines · Con Kolivas

Quoted 9 lines

Here are full patches for rsdl 0.31 for various base kernels. A full announce with a fresh -mm series will follow...

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.3-rsdl-0.31.p
atch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-sched-rsd
l-0. 31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-mm2-rsdl-
0.31 .patch

It still has trouble with the x/gforce vs two niced encoders scenario. The previously reported choppiness is still present.

I suspect that x/gforce landing in the expired array is the trouble, and that this will never be smooth without some kind of exemption. I added some targeted unfairness to .30, and it didn't help much at all.

Priorities going all the way to 1 were a surprise.

Quoted 1 line

It wasn't going to change that case without renicing X.

Con. You are trying to wedge a fair scheduler into an environment where totally fair simply can not possibly function.

If this is your final answer to the problem space, I am done testing, and as far as _I_ am concerned, your scheduler is an utter failure.

Quoted 20 lines · Con Kolivas

Quoted 18 lines · Mike Galbraith

Quoted 8 lines · Con Kolivas

Here are full patches for rsdl 0.31 for various base kernels. A full announce with a fresh -mm series will follow...

http://ck.kolivas.org/patches/staircase-deadline/2.6.20.3-rsdl-0.31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-sched-rsdl-0.
31.patch
http://ck.kolivas.org/patches/staircase-deadline/2.6.21-rc3-mm2-rsdl-0.31
.patch

It still has trouble with the x/gforce vs two niced encoders scenario. The previously reported choppiness is still present.

I suspect that x/gforce landing in the expired array is the trouble, and that this will never be smooth without some kind of exemption. I added some targeted unfairness to .30, and it didn't help much at all.

Priorities going all the way to 1 were a surprise.

Quoted 1 line

It wasn't going to change that case without renicing X.

Con. You are trying to wedge a fair scheduler into an environment where totally fair simply can not possibly function.

If this is your final answer to the problem space, I am done testing, and as far as _I_ am concerned, your scheduler is an utter failure.

Sorry, I haven't really been following this thread and now I'm confused.

You're saying that it's somehow the scheduler's fault that X isn't running with a high enough priority?

P.S. "utter failure" was too harsh. What sticks in my craw is that the world has to adjust to fit this new scheduler.

From my POV 0.30 is better than mainline - it handles my load(s) better.

P.S. "utter failure" was too harsh. What sticks in my craw is that the world has to adjust to fit this new scheduler.

Quoted 2 lines · Mike Galbraith

P.S. "utter failure" was too harsh. What sticks in my craw is that the world has to adjust to fit this new scheduler.

I have never seen X run nearly as smooth as our favorite proprietary OS on similar spec hardware with ANY scheduler.

Quoted 2 lines · Mike Galbraith

P.S. "utter failure" was too harsh. What sticks in my craw is that the world has to adjust to fit this new scheduler.

I have never seen X run nearly as smooth as our favorite proprietary OS on similar spec hardware with ANY scheduler.

P.S. "utter failure" was too harsh. What sticks in my craw is that the world has to adjust to fit this new scheduler.

-Mike

Wrong. I call a good job giving a _preference_ to the desktop. I call rigid fairness impractical for the desktop, and a denial of reality.

Quoted 2 lines

Wrong. I call a good job giving a _preference_ to the desktop. I call rigid fairness impractical for the desktop, and a denial of reality.

Assuming you *want* that. It's possible that the desktop may not be particularly important and the machine may be doing much more important server work with critical latency issues. So if you want that, you have to ask for it.

Again, your complaint is that the other server gave you what you wanted even when you didn't ask for it. That's great for you but totally sucks for the majority of other people who want something else.

Quoted 3 lines · David Schwartz

Quoted 2 lines

Wrong. I call a good job giving a _preference_ to the desktop. I call rigid fairness impractical for the desktop, and a denial of reality.

Quoted 4 lines

Assuming you *want* that. It's possible that the desktop may not be particularly important and the machine may be doing much more important server work with critical latency issues. So if you want that, you have to ask for it.

Amusing argument ;-) I doubt that there are many admins ripping and encoding CDs on their employers critical production servers.

Quoted 4 lines · Nicholas Miell

Sorry, I haven't really been following this thread and now I'm confused.

You're saying that it's somehow the scheduler's fault that X isn't running with a high enough priority?

I'm saying that the current scheduler adjusts for interactive loads, this new one doesn't. I'm seeing interactivity regressions, and they are not fixed with nice unless nice is used to maximum effect. I'm saying yes, I can lower my expectations, but no I don't want to.

A four line summary is as short as I can make it.

-Mike

RSDL appears to be completely deterministic, which is a very strong virtue.

The X people have plans for how to go about fixing this, but until then, there's no reason to hold up kernel development.

On a side note, I wonder how long it's going to take to fix all the X/client combinations out there.

Quoted 2 lines · Mike Galbraith

On a side note, I wonder how long it's going to take to fix all the X/client combinations out there.

AIUI X's clients largely access it via libraries X ships, so the X update will sweep the vast majority of them in one shot. You'll have to either run the clients from remote hosts with downrev libraries or have downrev libraries around (e.g. in chroots) for clients to link to for the clients not to cooperate.

Quoted 2 lines · Nicholas Miell

RSDL appears to be completely deterministic, which is a very strong virtue.

Yes. That's why RSDL aroused my curiosity big time.

Quoted 2 lines

The X people have plans for how to go about fixing this, but until then, there's no reason to hold up kernel development.

I'm not in a position to hold up development.

On a side note, I wonder how long it's going to take to fix all the X/client combinations out there.

The X people have plans for how to go about fixing this, [...]

Quoted 1 line · Nicholas Miell

The X people have plans for how to go about fixing this, [...]

then we'll first have wait for those X changes to at least be done in a minimal manner so that they can be tested for real with RSDL. (is it _really_ due to that? Or will X regress forever once we switch to RSDL?) We cannot regress the scheduling of a workload as important as "X mixed with CPU-intense tasks". And "in theory this should be fixed if X is fixed" does not cut it. X is pretty much _the_ most important thing to optimize the interactive behavior of a Linux scheduler for. Also, paradoxically, it is precisely the improvement of _X_ workloads that RSDL argues with.

this regression has to be fixed before RSDL can be merged, simply because it is a pretty negative effect that goes beyond any of the visible positive improvements that RSDL brings over the current scheduler. If it is better to fix X, then X has to be fixed _first_, at least in form of a prototype patch that can be _tested_, and then the result has to be validated against RSDL.

why isn't niceing X to -10 an acceptable option?

if you overload the box enough things slow down, what scheduler avoids that?

where RSDL 'regresses' is with multiple CPU hog running at once (more then the number of real CPU's you have available) at the same priority, with one of them being the X server process.

the initial report was that with X + 2 cpu hogs on 1.5 cpu's there's more of a slowdown (even with a nice difference of 5 between X and the other processes)

Quoted 1 line · David Lang

why isn't niceing X to -10 an acceptable option?

Xorg's priority is only part of the problem. Every client that needs a substantial quantity of cpu while a hog is running will also need to be negative nice, no?

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
6599 root      26   0  174m  30m 8028 R   51  3.1   7:08.70 0 Xorg

I don't suppose you can be a bit more specific, and define how much CPU constitutes a "substantial quantity"? It looks to me like X already got about half of a CPU.

Quoted 2 lines

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
6599 root      26   0  174m  30m 8028 R   51  3.1   7:08.70 0 Xorg

Quoted 4 lines

Quoted 3 lines

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ P
COMMAND 6599 root 26 0 174m 30m 8028 R 51 3.1
7:08.70 0 Xorg

This is a snippet from a hacked up by me version of RSDL.30, not stock.

Quoted 5 lines · On Sat, 17 Mar 2007 15:33:41 +0100 Mike Galbraith <[email protected]> wrote:

Quoted 4 lines

Quoted 3 lines

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ P
COMMAND 6599 root 26 0 174m 30m 8028 R 51 3.1
7:08.70 0 Xorg

Quoted 2 lines

This is a snippet from a hacked up by me version of RSDL.30, not stock.

Oops. Thanks, sorry about my confusion. What does it look like without your patches? (I'm not sure if you've already sent this... I can't find any in the list archives.)

Quoted 1 line · Nicholas Miell

The X people have plans for how to go about fixing this, [...]

then we'll first have wait for those X changes to at least be done in a minimal manner so that they can be tested for real with RSDL. (is it _really_ due to that? Or will X regress forever once we switch to RSDL?)

We cannot regress the scheduling of a workload as important as "X mixed with CPU-intense tasks". And "in theory this should be fixed if X is fixed" does not cut it. X is pretty much _the_ most important thing to optimize the interactive behavior of a Linux scheduler for. Also, paradoxically, it is precisely the improvement of _X_ workloads that RSDL argues with.

this regression has to be fixed before RSDL can be merged, simply because it is a pretty negative effect that goes beyond any of the visible positive improvements that RSDL brings over the current scheduler. If it is better to fix X, then X has to be fixed _first_, at least in form of a prototype patch that can be _tested_, and then the result has to be validated against RSDL.

Quoted 6 lines

this regression has to be fixed before RSDL can be merged, simply because it is a pretty negative effect that goes beyond any of the visible positive improvements that RSDL brings over the current scheduler. If it is better to fix X, then X has to be fixed _first_, at least in form of a prototype patch that can be _tested_, and then the result has to be validated against RSDL.

RSDL is, above all else, fair. Predictably so.

Quoted 1 line · Nicholas Miell

The X people have plans for how to go about fixing this, [...]

[...] Or will X regress forever once we switch to RSDL?)
We cannot regress the scheduling of a workload as important as "X mixed with CPU-intense tasks". And "in theory this should be fixed if X is fixed" does not cut it. X is pretty much _the_ most important thing to optimize the interactive behavior of a Linux scheduler for. Also, paradoxically, it is precisely the improvement of _X_ workloads that RSDL argues with.

this regression has to be fixed before RSDL can be merged, [...]

Quoted 11 lines · Ingo Molnar

Quoted 1 line · Nicholas Miell

The X people have plans for how to go about fixing this, [...]

[...] Or will X regress forever once we switch to RSDL?)
We cannot regress the scheduling of a workload as important as "X mixed with CPU-intense tasks". And "in theory this should be fixed if X is fixed" does not cut it. X is pretty much _the_ most important thing to optimize the interactive behavior of a Linux scheduler for. Also, paradoxically, it is precisely the improvement of _X_ workloads that RSDL argues with.

Quoted 1 line

this regression has to be fixed before RSDL can be merged, [...]

Let me restate the fact, if it wasn't obvious enough, that most people who tried RSDL (and most of them use desktop systems, me including) never see any regressions compared to mainline. Quite contrary -- their impressions were that with RSDL desktop system runs more smoothly, even under fierce load, which was never possible with mainline scheduler.

(see http://article.gmane.org/gmane.linux.kernel/504068 for a list of references.)

The most frustrating part of a discussion of this nature on lkml is that earlier information in a thread seems to be long forgotten after a few days and all that is left is the one reporter having a problem.

Rocks and clubs at work (down boy <whack>, down i say!;).

This is .30 with some targeted unfairness. I seem to be making progress

toward beating it to a bloody but cooperative pulp. It might be possible to have my cake and eat it too. Likely too ugly to live though.

top - 11:35:50 up 57 min, 12 users, load average: 5.20, 4.30, 2.57

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
6599 root      26   0  174m  30m 8028 R   51  3.1   7:08.70 0 Xorg
7991 root      29   0 18196  14m 5188 R   47  1.4   0:55.70 0

amarok_libvisua 7995 root 37 5 3720 2444 976 R 44 0.2
0:27.53 1 lame 7993 root 37 5 3720 2448 976 R 40 0.2
0:46.60 1 lame

Quoted 9 lines

top - 11:35:50 up 57 min, 12 users, load average: 5.20, 4.30, 2.57

 PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  P COMMAND
6599 root      26   0  174m  30m 8028 R   51  3.1   7:08.70 0 Xorg
7991 root      29   0 18196  14m 5188 R   47  1.4   0:55.70 0

amarok_libvisua 7995 root 37 5 3720 2444 976 R 44 0.2
0:27.53 1 lame 7993 root 37 5 3720 2448 976 R 40 0.2
0:46.60 1 lame

What X driver are you using Mike? Are you on a builtin video chipset using mobo shared memory? I'm running the nvidia 9755 driver here with a jaton nvidia 6200-256 card here, and YES I KNOW that taints the kernel, but x is using on average, 1.3% of the cpu.

Xorg is using 50% cpu because I'm asking it to.

-Mike

On Saturday 17 March 2007, Mike Galbraith wrote:
[...]

Quoted 1 line

Xorg is using 50% cpu because I'm asking it to.

What advantage is that giving you?

Quoted 5 lines · Gene Heskett

On Saturday 17 March 2007, Mike Galbraith wrote:
[...]

Quoted 1 line

Xorg is using 50% cpu because I'm asking it to.

What advantage is that giving you?

It's a test scenario. Read the thread please, I really don't want to repeat myself endlessly.

And for Mark and others who are as confused as I was, this is the thread that Mike meant to reference:
http://thread.gmane.org/gmane.linux.kernel/503455/focus=6614

Quoted 3 lines · Con Kolivas

The most frustrating part of a discussion of this nature on lkml is that earlier information in a thread seems to be long forgotten after a few days and all that is left is the one reporter having a problem.

One? I'm not the only person who reported regression.

Quoted 3 lines · Con Kolivas

The most frustrating part of a discussion of this nature on lkml is that earlier information in a thread seems to be long forgotten after a few days and all that is left is the one reporter having a problem.

One? I'm not the only person who reported regression.

Mike, I'm not saying RSDL is perfect, but v0.31 is by far better than mainline. Try this easy test:

startx with the vesa driver
run reflect from the mesa5.0-demos
load 5 cpu-hogs
start moving the mouse

On my desktop, mainline completely breaks down, and no nicing may rescue.

On RSDL, even without nicing, the desktop is at least useable.

Quoted 8 lines · Al Boldi

Mike, I'm not saying RSDL is perfect, but v0.31 is by far better than mainline. Try this easy test:

startx with the vesa driver
run reflect from the mesa5.0-demos
load 5 cpu-hogs
start moving the mouse

Quoted 1 line

On my desktop, mainline completely breaks down, and no nicing may rescue.

(hmm.. i would think that _renicing_ X would help that)

Quoted 1 line

On RSDL, even without nicing, the desktop is at least useable.

So neither does a good job with this load.

-Mike

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 1 line

So neither does a good job with this load.

that sorely depends on what you mean by good job.

It seems like what you call a good job is preserving the speed of the gui(X + apps which uses it) at _ALL_ costs to other stuff.

Quoted 5 lines · Kasper Sandberg

Quoted 1 line

So neither does a good job with this load.

that sorely depends on what you mean by good job.

It seems like what you call a good job is preserving the speed of the gui(X + apps which uses it) at _ALL_ costs to other stuff.

Wrong. I call a good job giving a _preference_ to the desktop. I call rigid fairness impractical for the desktop, and a denial of reality.

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

-Mike

maybe if it is possible to classify program behaviors that cause RSDL to do bad (relatively) or the mainline scheduler to jitter, we could try modifying the existing heuristics to get a better default scheduler.

of course, it wouldn't be able to cater to all the workloads and would meet everybody's definition of optimal. but getting close to optimal in most cases should be a good enough goal for linux's default sched!

i've been following this thread, and there's been many instances of 'RSDL is gr8' and 'RSDL regresses'.

maybe RSDL isn't the answer. maybe the current mainline sched isn't either. but RSDL definitely has done *something* right.

What i think is needed is 'why this works here' and 'how to get this behavior to work with some other possibly conflicting but important workloads'.

(just my 2c :-)

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

-Mike

not really, only X sucks. KDE works atleast as good with rsdl as vanilla. i dont know how originally said kde works worse, wasnt it just someone that thought?

Quoted 6 lines · Mike Galbraith

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Quoted 4 lines

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

not really, only X sucks. KDE works atleast as good with rsdl as vanilla. i dont know how originally said kde works worse, wasnt it just someone that thought?

Quoted 7 lines · Kasper Sandberg

Quoted 6 lines · Mike Galbraith

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Quoted 7 lines

Quoted 3 lines

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

not really, only X sucks. KDE works atleast as good with rsdl as vanilla. i dont know how originally said kde works worse, wasnt it just someone that thought?

It was probably me, and I had the opinion that KDE is not as smooth as GNOME with RSDL. I haven't had time to measure, but using for daily stuff for about an hour each way hasn't changed my opinion. Every once in a while KDE will KLUNK to a halt for 200-300ms doing mundane stuff like redrawing a page, scrolling, etc. I don't see it with GNOME.

Quoted 7 lines · Kasper Sandberg

Quoted 6 lines · Mike Galbraith

Quoted 4 lines · Radoslaw Szkodzinski

I'd recon KDE regresses because of kioslaves waiting on a pipe (communication with the app they're doing IO for) and then expiring. That's why splitting IO from an app isn't exactly smart. It should at least be ran in an another thread.

Quoted 8 lines

Quoted 4 lines

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

not really, only X sucks. KDE works atleast as good with rsdl as vanilla. i dont know how originally said kde works worse, wasnt it just someone that thought?

It was probably me, and I had the opinion that KDE is not as smooth as GNOME with RSDL. I haven't had time to measure, but using for daily stuff for about an hour each way hasn't changed my opinion. Every once in a while KDE will KLUNK to a halt for 200-300ms doing mundane stuff like redrawing a page, scrolling, etc. I don't see it with GNOME.

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

Quoted 3 lines

Hm. Sounds rather a lot like the...
X sucks, fix X and RSDL will rock your world. RSDL is perfect. ...that I've been getting.

Blah. Nothing's perfect. Especially not computer programs.

Still, it's not a smart decision on KDE's part.
It will break a lot of scheduling decisions, esp. you can't use IO priorities.

..
Mike, I'm not saying RSDL is perfect, but v0.31 is by far better than mainline. Try this easy test:

startx with the vesa driver
run reflect from the mesa5.0-demos
load 5 cpu-hogs
start moving the mouse

On my desktop, mainline completely breaks down, and no nicing may rescue.

On RSDL, even without nicing, the desktop is at least useable.

Dell notebook, single P-M-2GHz, ATI X300, open source X.org:
(1) build a kernel in one window with "make -j$((NUMBER_OF_CPUS + 1))".
(2) try to read email and/or surf in Firefox/Thunderbird.

Stock scheduler wins easily, no contest.

Quoted 5 lines · Mark Lord

Dell notebook, single P-M-2GHz, ATI X300, open source X.org:
(1) build a kernel in one window with "make -j$((NUMBER_OF_CPUS + 1))".
(2) try to read email and/or surf in Firefox/Thunderbird.

Stock scheduler wins easily, no contest.

What happens when you renice X ?

Quoted 3 lines · Xavier Bestel

Quoted 2 lines · Mark Lord

Dell notebook, single P-M-2GHz, ATI X300, open source X.org:
(1) build a kernel in one window with "make -j$((NUMBER_OF_CPUS +

1))".

Quoted 5 lines

Quoted 3 lines

(2) try to read email and/or surf in Firefox/Thunderbird.

Stock scheduler wins easily, no contest.

What happens when you renice X ?

Dunno -- not necessary with the stock scheduler.

Quoted 5 lines

Quoted 3 lines

Quoted 1 line

Stock scheduler wins easily, no contest.

What happens when you renice X ?

Dunno -- not necessary with the stock scheduler.

Could you try something like renice -10 $(pidof Xorg) ?

Quite frankly, I was *planning* on merging RSDL very early after 2.6.21, but there is one thing that has turned me completely off the whole thing:

- the people involved seem to be totally unwilling to even admit there might be a problem.

This is like alcoholism. If you cannot admit that you might have a problem, you'll never get anywhere. And quite frankly, the RSDL proponents seem to be in denial ("we're always better", "it's your problem if the old scheduler works better", "just one report of old scheduler being better").

And the thing is, if people aren't even _willing_ to admit that there may be issues, there's *no*way*in*hell* I will merge it even for testing. Because the whole and only point of merging RSDL was to see if it could replace the old scheduler, and the most important feature in that case is not whether it is perfect, BUT WHETHER ANYBODY IS INTERESTED IN TRYING TO FIX THE INEVITABLE PROBLEMS!

Also, while I don't agree with starting to renice X to get something usable, it seems real that there's something funny on Mike's system which makes it behave particularly strangely when combined with RSDL, because other people in comparable tests (including me) have found X perfectly smooth even with loads in the tens or even hundreds. I really suspect that we will find a bug in RSDL which triggers the problem and that this fix will help discover another problem on Mike's hardware which was not triggered by mainline.

Moving right along to the bugs part, I hope others are looking as well, and not only talking.

One area that looks pretty fishy to me is cross-cpu wakeups and task migration. p->rotation appears to lose all meaning when you cross the cpu boundary, and try_to_wake_up()is using that information in the cross-cpu case. In pull_task() OTOH, it checks to see if the task ran on the remote cpu (at all, hmm), and if so tags the task accordingly.

'f' is a progglet which sleeps a bit and burns a bit, duration depending on argument given. 'sh' is a shell 100% hog. In this scenario, the argument was set such that 'f' used right at 50% cpu. All are started at the same time, and I froze top when the first 'f' reached 1:00.

Quoted 4 lines · Mike Galbraith

'f' is a progglet which sleeps a bit and burns a bit, duration depending on argument given. 'sh' is a shell 100% hog. In this scenario, the argument was set such that 'f' used right at 50% cpu. All are started at the same time, and I froze top when the first 'f' reached 1:00.

May one enquire how much CPU the mythical 'f' uses when ran alone? Just to get a gauge for the numbers?

Quoted 4 lines · Mike Galbraith

'f' is a progglet which sleeps a bit and burns a bit, duration depending on argument given. 'sh' is a shell 100% hog. In this scenario, the argument was set such that 'f' used right at 50% cpu. All are started at the same time, and I froze top when the first 'f' reached 1:00.

May one enquire how much CPU the mythical 'f' uses when ran alone? Just to get a gauge for the numbers?

From task_running_tick():

From pull_task():

From recalc_task_prio(), which is called by enqueue_task():

Actually, the numbers are an interesting curiosity point, but not as interesting as the fact that the deadline mechanism isn't kicking in.

Quoted 1 line

From pull_task():

	/*
	 * If this task has already been running on src_rq this priority
	 * cycle, make the new runqueue think it has been on its cycle
	 */
	if (p->rotation == src_rq->prio_rotation)
		p->rotation = this_rq->prio_rotation;

The intent here is clearly that this task continue on the new cpu as if nothing has happened. However, when the task was dequeued, p->array was left as it was, points to the last place it was queued. Stale data.

Quoted 2 lines · Mike Galbraith

Actually, the numbers are an interesting curiosity point, but not as interesting as the fact that the deadline mechanism isn't kicking in.

it's not just the scheduling accounting being off, RSDL also seems to be accessing stale data here:

Quoted 8 lines

Quoted 1 line

From pull_task():

	/*
	 * If this task has already been running on src_rq this priority
	 * cycle, make the new runqueue think it has been on its cycle
	 */
	if (p->rotation == src_rq->prio_rotation)
		p->rotation = this_rq->prio_rotation;

Quoted 4 lines

The intent here is clearly that this task continue on the new cpu as if nothing has happened. However, when the task was dequeued, p->array was left as it was, points to the last place it was queued. Stale data.

it might point to a hot-unplugged CPU's runqueue as well. Which might work accidentally, but we want this fixed nevertheless.

Erk!

Quoted 2 lines · Mike Galbraith

Actually, the numbers are an interesting curiosity point, but not as interesting as the fact that the deadline mechanism isn't kicking in.

it's not just the scheduling accounting being off, RSDL also seems to be

accessing stale data here:

Quoted 13 lines

Quoted 1 line

From pull_task():

	/*
	 * If this task has already been running on src_rq this priority
	 * cycle, make the new runqueue think it has been on its cycle
	 */
	if (p->rotation == src_rq->prio_rotation)
		p->rotation = this_rq->prio_rotation;

The intent here is clearly that this task continue on the new cpu as if nothing has happened. However, when the task was dequeued, p->array was left as it was, points to the last place it was queued. Stale data.

it might point to a hot-unplugged CPU's runqueue as well. Which might work accidentally, but we want this fixed nevertheless.

This is a rather long message, and isn't directed at anyone in particular, it's for others who may be digging into their own problems with RSDL, and for others (if any other than Con exist) who understand RSDL well enough to tell me if I'm missing something. Anyone who's not interested in RSDL's gizzard hit 'D' now.

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines · Mike Galbraith

'f' is a progglet which sleeps a bit and burns a bit, duration depending on argument given. 'sh' is a shell 100% hog. In this scenario, the argument was set such that 'f' used right at 50% cpu. All are started at the same time, and I froze top when the first 'f' reached 1:00.

May one enquire how much CPU the mythical 'f' uses when ran alone? Just to get a gauge for the numbers?

Actually, the numbers are an interesting curiosity point, but not as interesting as the fact that the deadline mechanism isn't kicking in.

Quoted 1 line

From task_running_tick():

	/*
	 * Accounting is performed by both the task and the runqueue. This
	 * allows frequently sleeping tasks to get their proper quota of
	 * cpu as the runqueue will have their quota still available at
	 * the appropriate priority level. It also means frequently waking
	 * tasks that might miss the scheduler_tick() will get forced down
	 * priority regardless.
	 */
	if (!--p->time_slice)
		task_expired_entitlement(rq, p);
	/*
	 * We only employ the deadline mechanism if we run over the quota.
	 * It allows aliasing problems around the scheduler_tick to be
	 * less harmful.
	 */
	if (!rt_task(p) && --rq_quota(rq, rq->prio_level) < 0) {
		if (unlikely(p->first_time_slice))
			p->first_time_slice = 0;
		rotate_runqueue_priority(rq);
		set_tsk_need_resched(p);
	}

The reason for ticking both runqueue and task is that you can't sample a say 100KHz information stream at 1KHz and reproduce that information accurately. IOW, task time slices "blur" at high switch frequency, you can't always hit tasks, so you hit what you _can_ hit every sample, the runqueue, to minimize the theoretical effects of time slice theft. (I've instrumented this before, and caught fast movers stealing 10s of milliseconds in extreme cases.) Generally speaking, statistics even things out very much, the fast mover eventually gets hit, and pays a full tick for his sub-tick dip in the pool, so in practice it's not a great big hairy deal.

If you can accept that tasks can and do dodge the tick, an imbalance between runqueue quota and task quota must occur. It isn't happening here, and the reason appears to be bean counting error, tasks migrate but their quotas don't follow. The first time a task is queued at any priority, quota is allocated, task goes to sleep, quota on departed runqueue stays behind, task awakens on a different runqueue, allocate more quota, repeat. For migration, there's twist, if you pull an expired task, expired tasks don't have a quota yet, so they shouldn't screw up bean counting.

Quoted 2 lines

From pull_task():

	/*
	 * If this task has already been running on src_rq this priority
	 * cycle, make the new runqueue think it has been on its cycle
	 */
	if (p->rotation == src_rq->prio_rotation)
		p->rotation = this_rq->prio_rotation;

The intent here is clearly that this task continue on the new cpu as if nothing has happened. However, when the task was dequeued, p->array was left as it was, points to the last place it was queued. Stale data.

Quoted 1 line

From recalc_task_prio(), which is called by enqueue_task():

static void recalc_task_prio(struct task_struct *p, struct rq *rq)

{
	struct prio_array *array = rq->active;
	int queue_prio, search_prio;

	if (p->rotation == rq->prio_rotation) {
		if (p->array == array) {
			if (p->time_slice && rq_quota(rq, p->prio))
				return;
		} else if (p->array == rq->expired) {
			queue_expired(p, rq);
			return;
		} else
			task_new_array(p, rq);
	} else
		task_new_array(p, rq);
	search_prio = p->static_prio;

p->rotation was set to this runqueue's prio_rotation, but p->array is stale, still points to the old cpu's runqueue, so...

static inline void task_new_array(struct task_struct *p, struct rq *rq)

{
	bitmap_zero(p->bitmap, PRIO_RANGE);
	p->rotation = rq->prio_rotation;
}

p->bitmap is the history of all priorities where this task has been allocated a quota. Here, that history is erased, so the task can't continue it's staircase walk. It is instead given a new runqueue quota and time_slice (didn't it just gain ticks?). Now, what if a cross-cpu wakeup or migrating task _didn't_ have a stale array pointer, rather it pointed to the current active array, _and_ there were no quota available at it's priority? It didn't bring any of it's old quota with it after all. In that case, it would fall through as well, and get the full new time_slice and runqueue quota treatment.

The next logical step if the above is correct is obvious. If it's not, really bad things are going to happen here shortly :)

-Mike (broom and dustpan at the ready)

Now to figure out some meaningful cheap way of improving this accounting.

Thanks again!

Quoted 1 line · Con Kolivas

Now to figure out some meaningful cheap way of improving this accounting.

The accounting is easy iff tick resolution is good enough, the deadline mechanism is harder. I did the "quota follows task" thing, but nothing good happens. That just ensured that the deadline mechanism kicks in constantly because tick theft is a fact of tick-based life. A reasonable fudge factor would help, but...

I see problems wrt with trying to implement the deadline mechanism.

As implemented, it can't identify who is doing the stealing (which happens constantly, even if userland if 100% hog) because of tick resolution accounting. If you can't identify the culprit, you can't enforce the quota, and quotas which are not enforced are, strictly speaking, not quotas. At tick time, you can only close the barn door after the cow has been stolen, and the thief can theoretically visit your barn an infinite number of times while you aren't watching the door. ("don't blink" scenarios, and tick is backward-assward blink)

You can count nanoseconds in schedule, and store the actual usage, but then you still have the problem of inaccuracies in sched_clock() from cross-cpu wakeup and migration. Cross-cpu wakeups happen quite a lot. If sched_clock() _were_ absolutely accurate, you wouldn't need the runqueue deadline mechanism, because at slice tick time you can see everything you will ever see without moving enforcement directly into the most critical of paths.

IMHO, unless it can be demonstrated that timeslice theft is a problem with a real-life scenario, you'd be better off dropping the queue ticking. Time slices are a deadline mechanism, and in practice the god of randomness ensures that even fast movers do get caught often enough to make ticking tasks sufficient.

(that was a very long-winded reply to one sentence because I spent a lot of time looking into this very subject and came to the conclusion that you can't get there from here. fwiw, ymmv and all that of course;)

Quoted 1 line

Thanks again!

You're welcome.

The deadline mechanism is easy to hit and works. Try printk'ing it.

The deadline mechanism is easy to hit and works. Try printk'ing it.

Quoted 6 lines · On Wed, 21 Mar 2007 15:57:44 +0100 Mike Galbraith <[email protected]> wrote:

I was more than a bit surprised that mainline did this well, considering that the proggy was one someone posted long time ago to demonstrate starvation issues with the interactivity estimator. (source not available unfortunately, was apparently still on my old PIII box along with the one Willy posted when I installed opensuse 10.2 on it. damn. trivial thing though)

This one? :)

Quoted 10 lines · Paolo Ornati

Quoted 6 lines · On Wed, 21 Mar 2007 15:57:44 +0100 Mike Galbraith <[email protected]> wrote:

I was more than a bit surprised that mainline did this well, considering that the proggy was one someone posted long time ago to demonstrate starvation issues with the interactivity estimator. (source not available unfortunately, was apparently still on my old PIII box along with the one Willy posted when I installed opensuse 10.2 on it. damn. trivial thing though)

Quoted 1 line

This one? :)

No, but that one went to bit heaven too ;-)

Mike, if you need my old scheddos, I can resend it to you as well as to any people working on the scheduler and asking for it. Although trivial, I'm a bit reluctant to publish it to the whole world because I suspect that distros based on older kernels are still vulnerable and the fixes may not be easy. Anyway, it has absolutely no effect on non-interactive schedulers.

I don't agree with starting to renice X to get something usable

Quoted 1 line · Willy Tarreau

I don't agree with starting to renice X to get something usable

X looks very special to me: it's a big userspace driver, the primary task handling user interaction on the desktop, and on some OS the part responsible for moving the mouse pointer and interacting with windows is even implemented as an interrupt handler, and that for sure provides for smooth user experience even on very low-end hardware. Why not compensate for X design by prioritizing it a bit ?
If RSDL + reniced X makes for a better desktop than sotck kernel + X, on all kind of workloads, it's good to know.

than mainline. However top output under 100% load (eg kernel compilation) looks like below -- the %CPU error seems a bit high...

Quoted 1 line · Willy Tarreau

I don't agree with starting to renice X to get something usable

[...] Why not compensate for X design by prioritizing it a bit ?

there were multiple attempts with renicing X under the vanilla scheduler, and they were utter failures most of the time. _More_ people complained about interactivity issues _after_ X has been reniced to -5 (or -10) than people complained about "nice 0" interactivity issues to begin with.

The vanilla scheduler's auto-nice feature rewards _behavior_, so it gets X right most of the time. The fundamental issue is that sometimes X is very interactive - we boost it then, there's lots of scheduling but nice low latencies. Sometimes it's a hog - we penalize it then and things start to batch up more and we get out of the overload situation faster. That's the case even if all you care about is desktop performance.

no doubt it's hard to get the auto-nice thing right, but one thing is
clear: currently RSDL causes problems in areas that worked well in the vanilla scheduler for a long time, so RSDL needs to improve. RSDL should not lure itself into the false promise of 'just renice X statically'. It wont work. (You might want to rewrite X's request scheduling - but if so then i'd like to see that being done _first_, because i just dont trust such 10-mile-distance problem analysis.)

Quoted 5 lines

there were multiple attempts with renicing X under the vanilla scheduler, and they were utter failures most of the time. _More_ people complained about interactivity issues _after_ X has been reniced to -5 (or -10) than people complained about "nice 0" interactivity issues to begin with.

Unfortunately, nicing X is not going to work. It causes X to pre-empt any local process that tries to batch requests to it, defeating the batching. What you really want is X to get scheduled after the client pauses in sending data to it or has sent more than a certain amount. It seems kind of crazy to put such login in a scheduler.

Perhaps when one process unblocks another, you put that other process at the head of the run queue but don't pre-empt the currently running process. That way, the process can continue to batch requests, but X's maximum latency delay will be the quantum of the client program.

Quoted 8 lines

The vanilla scheduler's auto-nice feature rewards _behavior_, so it gets X right most of the time. The fundamental issue is that sometimes X is very interactive - we boost it then, there's lots of scheduling but nice low latencies. Sometimes it's a hog - we penalize it then and things start to batch up more and we get out of the overload situation faster. That's the case even if all you care about is desktop performance.

Quoted 7 lines

no doubt it's hard to get the auto-nice thing right, but one thing is
clear: currently RSDL causes problems in areas that worked well in the vanilla scheduler for a long time, so RSDL needs to improve. RSDL should not lure itself into the false promise of 'just renice X statically'. It wont work. (You might want to rewrite X's request scheduling - but if so then i'd like to see that being done _first_, because i just dont trust such 10-mile-distance problem analysis.)

I am hopeful that there exists a heuristic that both improves this problem and is also inherently fair. If that's true, then such a heuristic can be added to RSDL without damaging its properties and without requiring any special settings. Perhaps longer-term latency benefits to processes that have yielded in the past?

I think there are certain circumstances, however, where it is inherently reasonable to insist that 'nice' be used. If you want a CPU-starved task to get more than 1/X of the CPU, where X is the number of CPU-starved tasks, you should have to ask for that. If you want one CPU-starved task to get better latency than other CPU-starved tasks, you should have to ask for that.

Fundamentally, the scheduler cannot do it by itself. You can create cases where the load is precisely identical and one person wants X and another person wants Y. The scheduler cannot know what's important to you.

DS

I agree for giving a process more than a fair share, but I don't think "latency" is the best term for what you describe later. If you think of latency as the time between a process unblocking and the time when it gets CPU, that is a more traditional interpretation. I'm not really sure latency and CPU-starved are compatible.

Quoted 5 lines · Bill Davidsen

I agree for giving a process more than a fair share, but I don't think "latency" is the best term for what you describe later. If you think of latency as the time between a process unblocking and the time when it gets CPU, that is a more traditional interpretation. I'm not really sure latency and CPU-starved are compatible.

For CPU-starvation, I think 'nice' is always going to be the fix. If you want a process to get more than its 'fair share' of the CPU, you have to ask for that. I think the scheduler should be fair by default.

However, cleverness in the scheduler with latency can make things better without being unfair to anyone. It's perfectly fair for a task that has been blocked for awhile to pre-empt a CPU-limited task when it unblocks.

What I'm arguing is that if your task is CPU-limited and the scheduler is fair, that's your fault -- nice it. If your task is suffering from poor latency, and it's using less than its fair share of the CPU (because it is not CPU-limited), that is something the scheduler can be smarter about.

Honestly, I have always been against aggressive pre-emption. I think as CPUs get faster and timeslices get shorter, it makes less and less sense. In many

Linus, you're unfair with Con. He initially was on this position, and lately worked with Mike by proposing changes to try to improve his X responsiveness.

I was very happy to see the "try this patch" email from Al Boldi - not because I think that patch per se was necessarily the right fix (I have no idea),

but simply because I think that's the kind of mindset we need to have.

Not a lot of people really *like* the old scheduler, but it's been tweaked over the years to try to avoid some nasty behaviour. I'm really hoping that RSDL would be a lot better (and by all accounts it has the potential for that), but I think it's totally naïve to expect that it won't need some tweaking too.

So I'll happily still merge RSDL right after 2.6.21 (and it won't even be a config option - if we want to make it good, we need to make sure *everybody* tests it), but what I want to see is that "can do" spirit wrt tweaking for issues that come up.

Because let's face it - nothing is ever perfect. Even a really nice conceptual idea always ends up hitting the "but in real life, things are ugly and complex, and we've depended on behaviour X in the past and can't change it, so we need some tweaking for problem Y".

And everything is totally fixable - at least as long as people are willing to!

Quoted 2 lines · Willy Tarreau

Linus, you're unfair with Con. He initially was on this position, and lately worked with Mike by proposing changes to try to improve his X responsiveness.

I was not actually so much speaking about Con, as about a lot of the tone in general here. And yes, it's not been entirely black and white. I was very happy to see the "try this patch" email from Al Boldi - not because I think that patch per se was necessarily the right fix (I have no idea), but simply because I think that's the kind of mindset we need to have.

Not a lot of people really *like* the old scheduler, but it's been tweaked over the years to try to avoid some nasty behaviour. I'm really hoping that RSDL would be a lot better (and by all accounts it has the potential for that), but I think it's totally naïve to expect that it won't need some tweaking too.

So I'll happily still merge RSDL right after 2.6.21 (and it won't even be a config option - if we want to make it good, we need to make sure *everybody* tests it), but what I want to see is that "can do" spirit wrt tweaking for issues that come up.

Because let's face it - nothing is ever perfect. Even a really nice conceptual idea always ends up hitting the "but in real life, things are ugly and complex, and we've depended on behaviour X in the past and can't change it, so we need some tweaking for problem Y".

And everything is totally fixable - at least as long as people are willing to!

Linus

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

Quoted 1 line

Stock scheduler wins easily, no contest.

What happens when you renice X ?

Dunno -- not necessary with the stock scheduler.

Could you try something like renice -10 $(pidof Xorg) ?

Could you try something as simple and accepting that maybe this is a problem?

Quite frankly, I was *planning* on merging RSDL very early after 2.6.21, but there is one thing that has turned me completely off the whole thing:

- the people involved seem to be totally unwilling to even admit there might be a problem.

This is like alcoholism. If you cannot admit that you might have a problem, you'll never get anywhere. And quite frankly, the RSDL proponents seem to be in denial ("we're always better", "it's your problem if the old scheduler works better", "just one report of old scheduler being better").

And the thing is, if people aren't even _willing_ to admit that there may be issues, there's *no*way*in*hell* I will merge it even for testing. Because the whole and only point of merging RSDL was to see if it could replace the old scheduler, and the most important feature in that case is not whether it is perfect, BUT WHETHER ANYBODY IS INTERESTED IN TRYING TO FIX THE INEVITABLE PROBLEMS!

See?

Can you people not see that the way you're doing that "RSDL is perfect" chorus in the face of people who report problems, you're just making it totally unrealistic that it will *ever* get merged.

So unless somebody steps up to the plate and actually *talks* about the problem reports, and admits that maybe RSDL will need some tweaking, I'm not going to merge it.

Because there is just _one_ thing that is more important than code - and that is the willingness to fix the code...

Linus
_______________________________________________
http://ck.kolivas.org/faqs/replying-to-mailing-list.txt
ck mailing list - mailto: [email protected]
http://vds.kolivas.org/mailman/listinfo/ck

Quite frankly, I was *planning* on merging RSDL very early after 2.6.21, but there is one thing that has turned me completely off the whole thing:

- the people involved seem to be totally unwilling to even admit there might be a problem.

I've droppped it from my machine -- interactive response is much more important for my primary machine right now.

Quoted 2 lines · Mark Lord

I've droppped it from my machine -- interactive response is much more important for my primary machine right now.

Help out with a data point? Are you running KDE as well?

Quoted 2 lines · Mark Lord

I've droppped it from my machine -- interactive response is much more important for my primary machine right now.

Help out with a data point? Are you running KDE as well? If you are, then it looks like the common denominator that RSDL is handling poorly is client-server communication. (KDE's KIO slaves in this case, but X in general.)

If so, one would hope that a variation on Linus's 2.5.63 pipe wakeup pass-the-interactivity idea could work here. The problem with that original patch, IIRC, was that a couple of tasks could bounce their interactivity bonus back and forth and thereby starve others. Which might be expected given there was no 'decaying' of the interactivity bonus, which means you can make a feedback loop.

Anyway, looks like processes that do A -> B -> A communication chains are getting penalized under RSDL. In which case, perhaps I can make a test case that exhibits the problem without having to have the same graphics card or desktop as you.

Ray
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 9 lines · Al Boldi

..
Mike, I'm not saying RSDL is perfect, but v0.31 is by far better than mainline. Try this easy test:

startx with the vesa driver
run reflect from the mesa5.0-demos
load 5 cpu-hogs
start moving the mouse

Quoted 4 lines

On my desktop, mainline completely breaks down, and no nicing may rescue.

On RSDL, even without nicing, the desktop is at least useable.

I use a simpler, far more common (for lkml participants) workload:

Dell notebook, single P-M-2GHz, ATI X300, open source X.org:
(1) build a kernel in one window with "make -j$((NUMBER_OF_CPUS + 1))".
(2) try to read email and/or surf in Firefox/Thunderbird.

Stock scheduler wins easily, no contest.

sched.c renamed from sched.bak.c +0 -0

@@ -938,7 +938,11 @@ static void activate_task(struct task_st
 				     (now - p->timestamp) >> 20);
 	}

Quoted 6 lines · Al Boldi

sched.c renamed from sched.bak.c +0 -0

@@ -938,7 +938,11 @@ static void activate_task(struct task_st
 				     (now - p->timestamp) >> 20);
 	}
 

sched.c static void activate_task(struct task_st · line 948

Quoted 9 lines

sched.c renamed from sched.bak.c +5 -1

-	p->quota = rr_quota(p);
+	/*
+	 * boost factor hardcoded to 5; adjust to your liking
+	 * higher means more likely to DoS
+	 */
+	p->quota = rr_quota(p) + (((now - p->timestamp) >> 20) * 5);
 	p->prio = effective_prio(p);
 	p->timestamp = now;
 	__activate_task(p, rq);

i've tried this and it lasted only a few minutes -- i was seeing mouse cursor stalls lasting almost 1s. i/o bound tasks starving X? After reverting the patch everything is smooth again.

Quoted 10 lines · Artur Skawina

sched.c static void activate_task(struct task_st · line 945

Quoted 6 lines · Al Boldi

sched.c renamed from sched.bak.c +5 -1

-	p->quota = rr_quota(p);
+	/*
+	 * boost factor hardcoded to 5; adjust to your liking
+	 * higher means more likely to DoS
+	 */
+	p->quota = rr_quota(p) + (((now - p->timestamp) >> 20) * 5);

mouse cursor stalls lasting almost 1s. i/o bound tasks starving X? After reverting the patch everything is smooth again.

This patch wasn't really meant for production, as any sleeping background proc turned cpu-hog may DoS the system.

If you like to play with this, then you probably want to at least reset the quota in its expiration.

Quoted 1 line · Con Kolivas

The most frustrating part of a discussion of this nature on lkml is that earlier information in a thread seems to be long forgotten after a few days and all that is left is the one reporter having a problem.

One? I'm not the only person who reported regression.

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

Quoted 2 lines · Con Kolivas

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

RSDL still has heuristics very much, but this time it's hardcoded into the design! Let me demonstrate this via a simple experiment.

in the vanilla scheduler, the heuristics are ontop of a fairly basic (and fast) scheduler, they are plain visible and thus 'optional'. In RSDL, the heuristics are still present but more hidden and more engrained into the design.

But it's easy to demonstrate this under RSDL: consider the following two scenarios, which implement precisely the same fundamental computing workload (everything running on the same, default nice 0 level):

1) a single task runs almost all the time and sleeps about 1 msec every 100 msecs.

[ run "while N=1; do N=1; done &" under bash to create such a
workload. ]

2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1 msec and passes the 'token' around to the next task in the ring. (in essence every task will sleep 9900 msecs before getting another run)

[ run http://redhat.com/~mingo/scheduler-patches/ring-test.c to
create this workload. If the 100 tasks default is too much for you then you can run "./ring-test 10" - that will show similar effects.
]

Workload #1 uses 100% of CPU time. Workload #2 uses 99% of CPU time. They both do in essence the same thing.

if RSDL had no heuristics at all then if i mixed #1 with #2, both workloads would get roughly 50%/50% of the CPU, right? (as happens if i mix #1 with #1 - both CPU-intense workloads get half of the CPU)

in reality, in the 'ring workload' case, RSDL will only give about _5%_ of CPU time to the #1 CPU-intense task, and will give 95% of CPU time to the #2 'ring' of tasks. So the distribution of timeslices is significantly unfair!

Why? Because RSDL still has heuristics, just elsewhere and more hidden:
in the "straightforward CPU intense task" case RSDL will 'penalize' the task by depleting its quota for running nearly all the time, in the "ring of tasks" case the 100 tasks will each run near their priority maximum, fed by 'major epoch' events of RSDL, thus they get 'rewarded' for seemingly sleeping alot and spreading things out. So RSDL has fundamental unfairness built in as well - it's just different from the vanilla scheduler.

Quoted 43 lines · Con Kolivas

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

RSDL still has heuristics very much, but this time it's hardcoded into the design! Let me demonstrate this via a simple experiment.

in the vanilla scheduler, the heuristics are ontop of a fairly basic (and fast) scheduler, they are plain visible and thus 'optional'. In RSDL, the heuristics are still present but more hidden and more engrained into the design.

But it's easy to demonstrate this under RSDL: consider the following two scenarios, which implement precisely the same fundamental computing workload (everything running on the same, default nice 0 level):

1) a single task runs almost all the time and sleeps about 1 msec every 100 msecs.

[ run "while N=1; do N=1; done &" under bash to create such a
workload. ]

2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1 msec and passes the 'token' around to the next task in the ring. (in essence every task will sleep 9900 msecs before getting another run)

[ run http://redhat.com/~mingo/scheduler-patches/ring-test.c to
create this workload. If the 100 tasks default is too much for you then you can run "./ring-test 10" - that will show similar effects.
]

Workload #1 uses 100% of CPU time. Workload #2 uses 99% of CPU time. They both do in essence the same thing.

if RSDL had no heuristics at all then if i mixed #1 with #2, both workloads would get roughly 50%/50% of the CPU, right? (as happens if i mix #1 with #1 - both CPU-intense workloads get half of the CPU)

in reality, in the 'ring workload' case, RSDL will only give about _5%_ of CPU time to the #1 CPU-intense task, and will give 95% of CPU time to the #2 'ring' of tasks. So the distribution of timeslices is significantly unfair!

Quoted 8 lines

Why? Because RSDL still has heuristics, just elsewhere and more hidden:
in the "straightforward CPU intense task" case RSDL will 'penalize' the task by depleting its quota for running nearly all the time, in the "ring of tasks" case the 100 tasks will each run near their priority maximum, fed by 'major epoch' events of RSDL, thus they get 'rewarded' for seemingly sleeping alot and spreading things out. So RSDL has fundamental unfairness built in as well - it's just different from the vanilla scheduler.

We're obviously disagreeing on what heuristics are so call it what you like.

You're simply cashing in on the deep pipes that do kernel work for other tasks. You know very well that I dropped the TASK_NONINTERACTIVE flag from rsdl which checks that tasks are waiting on pipes and you're exploiting it. That's not the RSDL heuristics at work at all, but you're trying to make it look like it is the intrinsic RSDL system at work. Putting that flag back in is simple enough when I'm not drugged. You could have simply pointed that out instead of trying to make my code look responsible.

For the moment I'll assume you're not simply trying to make my code look bad and that you thought there really was an intrinsic design problem, otherwise I'd really be unhappy with what was happening to me.

-----Original Message-----
From: [email protected] [mailto:[email protected]]On Behalf Of jos poortvliet
Sent: Saturday, March 17, 2007 5:24 AM
To: [email protected]
Cc: Con Kolivas; Ingo Molnar; Al Boldi; Mike Galbraith; [email protected]; Nicholas Miell; Linus Torvalds; Andrew Morton
Subject: Re: [ck] Re: is RSDL an "unfair" scheduler too?

Op Saturday 17 March 2007, schreef Con Kolivas:

Quoted 8 lines · Ingo Molnar

Quoted 7 lines · Con Kolivas

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

RSDL still has heuristics very much, but this time it's hardcoded into the design! Let me demonstrate this via a simple experiment.

Quoted 6 lines

Quoted 6 lines

in the vanilla scheduler, the heuristics are ontop of a fairly basic (and fast) scheduler, they are plain visible and thus 'optional'. In RSDL, the heuristics are still present but more hidden and more engrained into the design.

But it's easy to demonstrate this under RSDL: consider the

following two

Quoted 4 lines

Quoted 4 lines

scenarios, which implement precisely the same fundamental computing workload (everything running on the same, default nice 0 level):

1) a single task runs almost all the time and sleeps about 1

msec every

Quoted 7 lines

Quoted 7 lines

100 msecs.

[ run "while N=1; do N=1; done &" under bash to create such a
workload. ]

2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1 msec and passes the 'token' around to the next task in the

ring. (in

Quoted 1 line

Quoted 1 line

essence every task will sleep 9900 msecs before getting

another run)

Quoted 3 lines

Quoted 3 lines

[ run http://redhat.com/~mingo/scheduler-patches/ring-test.c to
create this workload. If the 100 tasks default is too

much for you

Quoted 1 line

Quoted 1 line

then you can run "./ring-test 10" - that will show

similar effects.

Quoted 1 line

Quoted 1 line

   ]

Well, re-reading his post, he has a point - one WOULD expect each of these 2
tasks to have an equal share of CPU, and if RSDL doesn't currently take this
pipe-thing into account, it might need some fixing. call it heuristics or not
(after all, how could one NOT say a scheduler uses heuristics of some kind?).

We're obviously disagreeing on what heuristics are [...]

You're simply cashing in on the deep pipes that do kernel work for other tasks. You know very well that I dropped the TASK_NONINTERACTIVE flag from rsdl which checks that tasks are waiting on pipes and you're exploiting it.

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. [...]

Quoted 1 line · Con Kolivas

We're obviously disagreeing on what heuristics are [...]

that could very well be so - it would be helpful if you could provide your own rough definition for the term, so that we can agree on how to call things?

[ in any case, there's no rush here, please reply at your own pace, as
your condition allows. I wish you a speedy recovery! ]

Quoted 4 lines

You're simply cashing in on the deep pipes that do kernel work for other tasks. You know very well that I dropped the TASK_NONINTERACTIVE flag from rsdl which checks that tasks are waiting on pipes and you're exploiting it.

Con, i am not 'cashing in' on anything and i'm not 'exploiting' anything. The TASK_NONINTERACTIVE flag is totally irrelevant to my argument because i was not testing the vanilla scheduler, i was testing RSDL. I could have written this test using plain sockets, because i was testing RSDL's claim of not having heuristics, i was not testing the vanilla scheduler.

I have simply replied to this claim of yours:

Quoted 2 lines

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. [...]

and i showed you a workload under _RSDL_ that clearly shows that RSDL is an unfair scheduler too.

my whole point was to counter the myth of 'RSDL has no heuristics'. Of course it has heuristics, which results in unfairness. (If it didnt have any heuristics that tilt the balance of scheduling towards sleep-intense tasks then a default Linux desktop would not be usable at all.)

so the decision is _not_ a puristic "do we want to have heuristics or not", the question is a more practical "which heuristics are simpler, which heuristics are more flexible, which heuristics result in better behavior".

Ingo

Ok but please look at how it appears from my end (illness aside).

You initially said you were pleased with this design.

Quoted 1 line · Con Kolivas

Ok but please look at how it appears from my end (illness aside).

( i really think we should continue this debate after you get better.
Everything looks much darker when you are ill! )

Quoted 1 line

You initially said you were pleased with this design.

I said that 2 years ago about the staircase scheduler and i am still saying this about RSDL today. That doesnt make my position automatically correct though :-) For example i wrote and maintained the 4g:4g patchset for over 2 years and still that was no guarantee of it making sense upstream ;) And it was a hell of a lot of work (much uglier and nastier work than any scheduler hacking and tuning, believe me), and it was thrown away as a cute but unnecessary complication we dont need. So what? To me what matters is the path you walk, not the destination you reach.

in terms of RSDL design, i like it, still i'm kind of asking myself 'couldnt something in this direction be done in a much simpler and less revolutionary way'? For example couldnt we introduce per-priority level timeslice quotas in the current scheme as well, instead of the very simplistic and crude STARVATION_LIMIT approach? Furthermore, couldnt we make the timeslices become smaller as the runqueue length increases, to make starvation less of a problem? It seems like the problem cases with the current scheduler arent so much centered around the interactivity estimator, it is more that timeslices get distributed too coarsely, while RSDL distributes timeslices in a more finegrained way and is thus less suspect to starvation under certain workloads.

Well, the heuristic here is that process == job. I'm not sure heuristic is the right name for it, but it does point out a deficieny.

A cpu-bound process with many threads will overwhelm a cpu-bound single threaded threaded process.

A job with many processes will overwhelm a job with a single process.

A user with many jobs can starve a user with a single job.

I don't think the problem here is heuristics, rather that the scheduler's manages cpu quotas at the task level rather than at the user visible level. If scheduling were managed at all three
hierarchies I mentioned ('job' is a bit artificial, but process and
user are not) then:

- if N users are contending for the cpu on a multiuser machine, each should get just 1/N of available cpu power. As it is, a user can run a few of your #1 workloads (or a make -j 20) and slow every other user down - your example would work perfectly (if we can communicate to the kernel what a job is)

- multi-threaded processes would not get an unfair advantage

Quoted 31 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

We're obviously disagreeing on what heuristics are [...]

that could very well be so - it would be helpful if you could provide your own rough definition for the term, so that we can agree on how to call things?

[ in any case, there's no rush here, please reply at your own pace, as
your condition allows. I wish you a speedy recovery! ]

Quoted 4 lines

You're simply cashing in on the deep pipes that do kernel work for other tasks. You know very well that I dropped the TASK_NONINTERACTIVE flag from rsdl which checks that tasks are waiting on pipes and you're exploiting it.

Con, i am not 'cashing in' on anything and i'm not 'exploiting' anything. The TASK_NONINTERACTIVE flag is totally irrelevant to my argument because i was not testing the vanilla scheduler, i was testing RSDL. I could have written this test using plain sockets, because i was testing RSDL's claim of not having heuristics, i was not testing the vanilla scheduler.

I have simply replied to this claim of yours:

Quoted 2 lines

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. [...]

and i showed you a workload under _RSDL_ that clearly shows that RSDL is an unfair scheduler too.

my whole point was to counter the myth of 'RSDL has no heuristics'. Of course it has heuristics, which results in unfairness. (If it didnt have any heuristics that tilt the balance of scheduling towards sleep-intense tasks then a default Linux desktop would not be usable at all.)

Quoted 6 lines

so the decision is _not_ a puristic "do we want to have heuristics or not", the question is a more practical "which heuristics are simpler, which heuristics are more flexible, which heuristics result in better behavior".

Ingo

Ok but please look at how it appears from my end (illness aside).

I spend 3 years just diddling with scheduler code trying my hardest to find a design that fixes a whole swag of problems we still have, and a swag of problems we might get with other fixes.

You initially said you were pleased with this design.

..lots of code, testing, bugfixes and good feedback.

Then Mike has one testcase that most other users disagree is worthy of being considered a regresssion. You latched onto that and basically called it a showstopper in spite of who knows how many other positive things.

Then you quickly produce a counter patch designed to kill off RSDL with a config option for mainline.

Then you boldly announce on LKML "is RSDL an "unfair" scheduler too?" with some test case you whipped up to try and find fault with the design.

What am I supposed to think? Considering just how many problems I have addressed and tried to correct with RSDL succesfully I'm surprised that despite your enthusiasm for it initially you have spent the rest of the time trying to block it.

Please, either help me (and I'm in no shape to code at the moment despite what I have done so far), or say you have no intention of including it. I'm risking paralysis just by sitting at the computer right now so I'm dropping the code as is at the moment and will leave it up to your better judgement as to what to do with it.

Con Kolivas wrote:

Now for something constructive... by any chance is Mike running KDE instead of GNOME? I only had a short time to play because I had to look at another problem in 2.6.21-rc3 (nbd not working), so the test machine is in use. But it looked as if behavior was not as smooth with KDE. May that thought be useful.

Now for something constructive... by any chance is Mike running KDE instead of GNOME?

Quoted 2 lines

Now for something constructive... by any chance is Mike running KDE instead of GNOME?

Yes.

-Mike

Quoted 2 lines

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

RSDL still has heuristics very much, but this time it's hardcoded into the design! Let me demonstrate this via a simple experiment.

in the vanilla scheduler, the heuristics are ontop of a fairly basic (and fast) scheduler, they are plain visible and thus 'optional'. In RSDL, the heuristics are still present but more hidden and more engrained into the design.

But it's easy to demonstrate this under RSDL: consider the following two scenarios, which implement precisely the same fundamental computing workload (everything running on the same, default nice 0 level):

1) a single task runs almost all the time and sleeps about 1 msec every 100 msecs.

[ run "while N=1; do N=1; done &" under bash to create such a
workload. ]

2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1 msec and passes the 'token' around to the next task in the ring. (in essence every task will sleep 9900 msecs before getting another run)

[ run http://redhat.com/~mingo/scheduler-patches/ring-test.c to
create this workload. If the 100 tasks default is too much for you then you can run "./ring-test 10" - that will show similar effects.
]

Workload #1 uses 100% of CPU time. Workload #2 uses 99% of CPU time. They both do in essence the same thing.

if RSDL had no heuristics at all then if i mixed #1 with #2, both workloads would get roughly 50%/50% of the CPU, right? (as happens if i mix #1 with #1 - both CPU-intense workloads get half of the CPU)

in reality, in the 'ring workload' case, RSDL will only give about _5%_ of CPU time to the #1 CPU-intense task, and will give 95% of CPU time to the #2 'ring' of tasks. So the distribution of timeslices is significantly unfair!

Why? Because RSDL still has heuristics, just elsewhere and more hidden:
in the "straightforward CPU intense task" case RSDL will 'penalize' the task by depleting its quota for running nearly all the time, in the "ring of tasks" case the 100 tasks will each run near their priority maximum, fed by 'major epoch' events of RSDL, thus they get 'rewarded' for seemingly sleeping alot and spreading things out. So RSDL has fundamental unfairness built in as well - it's just different from the vanilla scheduler.

Ingo

Quoted 2 lines · Con Kolivas

Despite the claims to the contrary, RSDL does not have _less_ heuristics, it does not have _any_. It's purely entitlement based.

RSDL still has heuristics very much, but this time it's hardcoded into the design! Let me demonstrate this via a simple experiment.

But it's easy to demonstrate this under RSDL: consider the following two scenarios, which implement precisely the same fundamental computing workload (everything running on the same, default nice 0 level):

1) a single task runs almost all the time and sleeps about 1 msec every 100 msecs.

[ run "while N=1; do N=1; done &" under bash to create such a
workload. ]

2) tasks are in a 'ring' where each runs for 100 msec, sleeps for 1 msec and passes the 'token' around to the next task in the ring. (in essence every task will sleep 9900 msecs before getting another run)

Workload #1 uses 100% of CPU time. Workload #2 uses 99% of CPU time. They both do in essence the same thing.

if RSDL had no heuristics at all then if i mixed #1 with #2, both workloads would get roughly 50%/50% of the CPU, right? (as happens if i mix #1 with #1 - both CPU-intense workloads get half of the CPU)

Well, the heuristic here is that process == job. I'm not sure heuristic is the right name for it, but it does point out a deficieny. A cpu-bound process with many threads will overwhelm a cpu-bound single threaded threaded process.
A job with many processes will overwhelm a job with a single process. A user with many jobs can starve a user with a single job.
I don't think the problem here is heuristics, rather that the scheduler's manages cpu quotas at the task level rather than at the user

visible level. If scheduling were managed at all three hierarchies I mentioned ('job' is a bit artificial, but process and user are not) then:
- if N users are contending for the cpu on a multiuser machine, each should get just 1/N of available cpu power. As it is, a user can run a few of your #1 workloads (or a make -j 20) and slow every other user down
- your example would work perfectly (if we can communicate to the kernel what a job is)
- multi-threaded processes would not get an unfair advantage

One issue this raises is prioritizing users on a system, threads within processes, jobs within users, etc.

Quoted 3 lines · William Lee Irwin III

One issue this raises is prioritizing users on a system, threads within processes, jobs within users, etc.

Doing some "classing" even by just euid might be a good idea. It would actually catch X automatically most of the time, because the euid of the X server is likely to be root, so even for the "trivial" desktop example, it would kind of automatically mean that X would get about 50% of CPU time even if you have a hundred user clients, just because that's "fair" by euid.

Dunno. I guess a lot of people would like to then manage the classes, which would be painful as hell.

Quoted 7 lines · Linus Torvalds

Quoted 3 lines · William Lee Irwin III

One issue this raises is prioritizing users on a system, threads within processes, jobs within users, etc.

Doing some "classing" even by just euid might be a good idea. It would actually catch X automatically most of the time, because the euid of the X server is likely to be root, so even for the "trivial" desktop example, it would kind of automatically mean that X would get about 50% of CPU time even if you have a hundred user clients, just because that's "fair" by euid.

Warning: all these ideas seem interesting for desktop, but are definitely not for servers. I found RSDL to be excellent on servers, compared to mainline in which some services are starving under load. I can understand that on the desktop people want some unfairness, and I like the pgrp idea for instance. But this one will certainly fail on servers, or make the admins get grey hair very soon.

Maybe we're all discussing the problem because we have reached the point where we need two types of schedulers : one for the desktop and one for the servers. After all, this is already what is proposed with preempt, it would make sense provided they share the same core and avoid ifdefs or unused structure members. Maybe adding OPTIONAL unfairness to RSDL would help some scenarios, but in any case it is important to retain the default fairness it provides.

I didn't suggest adding any unfairness! I suggested being fair by user/job/process instead of being fair by thread (which is actually unfair as it favors multi threaded processes over single threaded processes).

Quoted 5 lines

I didn't suggest adding any unfairness! I suggested being fair by user/job/process instead of being fair by thread (which is actually unfair as it favors multi threaded processes over single threaded processes).

Wouldn't that be unfair because it favors multi-user approaches over single-user approaches with the same number of processes?

Consider two otherwise equivalent web server designs. They both use a helper process owned by the user who owns the file the web server is sending. One does a lot of work in the helper process, the other does very little. A "fair by user" scheduler would give the approach that puts more work in the helper process more CPU than the one that puts little work in the helper process.

Being fair by user builds lots of assumptions into the scheduler. When they're not true, the scheduler becomes sub-optimal. For example, consider a web server that runs two very important tools, 'foo' and 'bar'. Rather than running them as root, they run as users 'foo' and 'bar' for security. "Fair to user" would mean that just because most other people are using 'foo', I get less CPU when I try to use 'foo', because the OS doesn't know the "real user", just the fake user who owns the process -- a security decision that has no relationship to fairness. This would be handled perfectly by a "fair to process" approach.

As for favoring multi-threaded processes over single-threaded processes, sometimes that's what you want.

Consider two servers,

one using thread per
job the other using process per job. Does it make sense to give the "process per job" server as much CPU to do a single task as the "thread per job" server gets for all the clients it's dealing with?

It's really more important that the scheduler be tunable and predictable.

That way, we can tell it what we want and get it. But the scheduler cannot read our minds.

Quoted 2 lines

Consider two servers,

^ ^ ^

Well, aren't we discussing desktops?
Server admins can fine-tune the rights and CPU quotas per group.

Quoted 5 lines

I didn't suggest adding any unfairness! I suggested being fair by user/job/process instead of being fair by thread (which is actually unfair as it favors multi threaded processes over single threaded processes).

Wouldn't that be unfair because it favors multi-user approaches over single-user approaches with the same number of processes?

Consider two otherwise equivalent web server designs. They both use a helper process owned by the user who owns the file the web server is sending. One does a lot of work in the helper process, the other does very little. A "fair by user" scheduler would give the approach that puts more work in the helper process more CPU than the one that puts little work in the helper process.

Being fair by user builds lots of assumptions into the scheduler. When they're not true, the scheduler becomes sub-optimal. For example, consider a web server that runs two very important tools, 'foo' and 'bar'. Rather than running them as root, they run as users 'foo' and 'bar' for security. "Fair to user" would mean that just because most other people are using 'foo', I get less CPU when I try to use 'foo', because the OS doesn't know the "real user", just the fake user who owns the process -- a security decision that has no relationship to fairness. This would be handled perfectly by a "fair to process" approach.

As for favoring multi-threaded processes over single-threaded processes, sometimes that's what you want. Consider two servers, one using thread per job the other using process per job. Does it make sense to give the "process per job" server as much CPU to do a single task as the "thread per job" server gets for all the clients it's dealing with?

It's really more important that the scheduler be tunable and predictable. That way, we can tell it what we want and get it. But the scheduler cannot read our minds.

A fairly contrived example, but I see your point. Of course any system can be broken. I think that user-level scheduling is good for real multi user systems, where 'user' means a person, not an artificial entity. It's also good for a multi application server, where typically each service runs (or can be made to run) as a separate user.

Quoted 2 lines · Avi Kivity

A fairly contrived example, but I see your point. Of course any system can be broken. I think that user-level scheduling is good for real multi user systems, where 'user' means a person, not an artificial entity. It's also good for a multi application server, where typically each service runs (or can be made to run) as a separate user.

For a not so contrived example, look at email delivery. Some mailservers do all work as root (or some fixed email user)

Some servers will switch to the UID of the user receiving the message, limiting the damage in case of buffer overflow etc. A fair amount of work is then done as that user - running the message through virus/spam-checks and
then perhaps procmail.

Quoted 2 lines

Dunno. I guess a lot of people would like to then manage the classes, which would be painful as hell.

Sure ! I wouldn't like people to point the finger on Linux saying "hey look, they can't write a good scheduler so you have to adjust the knobs yourself!". I keep in mind that Solaris' scheduler is very good, both fair and interactive. FreeBSD was good (I haven't tested for a long time). We should manage to get something good for most usages, and optimize later for specific uses.

Like I've said in a previous email, SGI schedulers have an interactive term in addition to the normal "nice" values. If RSDL ends up being too rigid for desktop use, then this might be a good idea to explore in addition to priority manipulation.

Quoted 4 lines · Bill Huey

Like I've said in a previous email, SGI schedulers have an interactive term in addition to the normal "nice" values. If RSDL ends up being too rigid for desktop use, then this might be a good idea to explore in addition to priority manipulation.

I've done that already (ain't perfect yet, maybe never be). The hard part is making it automatic, and not ruining the good side of RSDL in the process.

Quoted 7 lines · Willy Tarreau

Quoted 1 line

Dunno. I guess a lot of people would like to then manage the classes, which would be painful as hell.

Sure ! I wouldn't like people to point the finger on Linux saying "hey look, they can't write a good scheduler so you have to adjust the knobs yourself!". I keep in mind that Solaris' scheduler is very good, both fair and interactive. FreeBSD was good (I haven't tested for a long time). We should manage to get something good for most usages, and optimize later for specific uses.

Like I've said in a previous email, SGI schedulers have an interactive term in addition to the normal "nice" values. If RSDL ends up being too rigid for desktop use, then this might be a good idea to explore in addition to priority manipulation.

However, it hasn't been completely proven that RSDL can't handle desktop loads and that needs to be completely explored first. It certain seems like, from the .jpgs that were posted earlier in the thread regarding mysql performance, that RSDL seems to have improved performance for those set ups so it's not universally the case that it sucks for server loads. The cause of this performance difference has yet to be pinpointed.

Also, bandwidth scheduler like this are a new critical development for things like the -rt patch. It would benefit greatly if the RSDL basic mechanisms (RR and deadlines) were to somehow slip into that patch and be used for a more strict -rt based scheduling class. It would be the basis for first-class control over process resource usage and would be a first in Linux or any mainstream kernel.

This would be a powerful addition to Linux as a whole and RSDL should not be dismissed without these considerations. If it can somehow be integrated into the kernel with interactivity concerns addressed, then it would be an all out win for the kernel in both these areas.

Maybe we're all discussing the problem because we have reached the point where we need two types of schedulers : one for the desktop and one for the servers. After all, this is already what is proposed with preempt, it would make sense provided they share the same core and avoid ifdefs or unused structure members. Maybe adding OPTIONAL unfairness to RSDL would help some scenarios, but in any case it is important to retain the default fairness it provides.

Quoted 7 lines · Willy Tarreau

Maybe we're all discussing the problem because we have reached the point where we need two types of schedulers : one for the desktop and one for the servers. After all, this is already what is proposed with preempt, it would make sense provided they share the same core and avoid ifdefs or unused structure members. Maybe adding OPTIONAL unfairness to RSDL would help some scenarios, but in any case it is important to retain the default fairness it provides.

Bingo.

Quoted 10 lines · Mike Galbraith

Quoted 7 lines · Willy Tarreau

Maybe we're all discussing the problem because we have reached the point where we need two types of schedulers : one for the desktop and one for the servers. After all, this is already what is proposed with preempt, it would make sense provided they share the same core and avoid ifdefs or unused structure members. Maybe adding OPTIONAL unfairness to RSDL would help some scenarios, but in any case it is important to retain the default fairness it provides.

Quoted 2 lines

Bingo.

Sounds like Staircase's interactive mode switch, except this actually requires writing additional code.

The per-user system would also be nice for servers, provided there are CPU/disc IO/swapper/... quotas or priorities at least.

Quoted 3 lines

The per-user system would also be nice for servers, provided there are CPU/disc IO/swapper/... quotas or priorities at least.

This is too hard to adjust. Imagine what would happen to your hundreds of apache processes when the "backup" user will start the rsync or tar+gzip, or when user "root" will start rotating and compressing the logs. Being able to group processes may be useful on servers, but it should be enabled on purpose by the admin.

Quoted 11 lines · Avi Kivity

Well, the heuristic here is that process == job. I'm not sure heuristic is the right name for it, but it does point out a deficieny.
A cpu-bound process with many threads will overwhelm a cpu-bound single threaded threaded process.
A job with many processes will overwhelm a job with a single process.
A user with many jobs can starve a user with a single job.
I don't think the problem here is heuristics, rather that the scheduler's manages cpu quotas at the task level rather than at the user visible level. If scheduling were managed at all three hierarchies I mentioned ('job' is a bit artificial, but process and user are not) then:
- if N users are contending for the cpu on a multiuser machine, each
should get just 1/N of available cpu power. As it is, a user can run a few of your #1 workloads (or a make -j 20) and slow every other user down
- your example would work perfectly (if we can communicate to the kernel
what a job is)
- multi-threaded processes would not get an unfair advantage

I like this notion very much. I should probably mention pgrp's' typical association with the notion of "job," at least as far as shells go.

One issue this raises is prioritizing users on a system, threads within processes, jobs within users, etc. Maybe sessions would make sense, too, and classes of users, and maybe whatever they call the affairs that pid namespaces are a part of (someone will doubtless choke on the hierarchy depth implied here but it doesn't bother me in the least). It's not a deep or difficult issue. There just needs to be some user API to set the relative scheduling priorities of all these affairs within the next higher level of hierarchy, regardless of how many levels of hierarchy (aleph_0?).

So in an attempt to summarise the situation, what are the advantages of RSDL over mainline.

Fairness

Starvation free

Much lower and bound latencies

Deterministic

Better interactivity for the majority of cases.

Now concentrating on the very last aspect since that seems to be the sticking point.

Quoted 6 lines

So in an attempt to summarise the situation, what are the advantages of RSDL over mainline.

Fairness

why do you think fairness is good, especially always good?

Quoted 3 lines

Starvation free

even starvation is sometimes a good thing - there's a place for processes that only use the CPU if it is otherwise idle. that is, they are deliberately starved all the rest of the time.

Quoted 3 lines

Much lower and bound latencies

in an average sense? also, under what circumstances does this actually matter? (please don't offer something like RT audio on an overloaded machine- that's operator error, not something to design for.)

Quoted 3 lines

Deterministic

not a bad thing, but how does this make itself apparent and of value to the user? I think everyone is extremely comfortable with non-determinism (stemming from networks, caches, interleaved workloads, etc)

Quoted 3 lines

Better interactivity for the majority of cases.

how is this measured? is this statement really just a reiteration of the latency claim?

Quoted 4 lines

Now concentrating on the very last aspect since that seems to be the sticking point.

nah, I think the fairness and latency claims are the real issues. -
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

why do you think fairness is good, especially always good?

even starvation is sometimes a good thing - there's a place for processes that only use the CPU if it is otherwise idle. that is, they are deliberately starved all the rest of the time.

Quoted 1 line

Much lower and bound latencies

in an average sense? also, under what circumstances does this actually
matter? (please don't offer something like RT audio on an overloaded machine- that's operator error, not something to design for.)

Quoted 1 line

Deterministic

not a bad thing, but how does this make itself apparent and of value to the user? I think everyone is extremely comfortable with non-determinism (stemming from networks, caches, interleaved workloads, etc)

Quoted 4 lines

I'm saying that the current scheduler adjusts for interactive loads, this new one doesn't. I'm seeing interactivity regressions, and they are not fixed with nice unless nice is used to maximum effect. I'm saying yes, I can lower my expectations, but no I don't want to.

Uh, no. Essentially, the current scheduler works around X's brokenness, in an often unpredictable manner.