Skip to contentSkip to conversation

CFS scheduler, -v8

PATCH Zoltan Boszormenyi 7 participants 10 messages May 3, 2007 – May 7, 2007

lore
Share & tools
lore
#0 lore raw

Hi!

Quoted 6 lines
Quoted 1 line · *** Balbir Singh

The problem is with comparing a s64 values with (s64)ULONG_MAX, which evaluates to -1. Then we check if exec_delta64 and fair_delta64 are greater than (s64)ULONG_MAX (-1), if so we assign (s64)ULONG_MAX to the respective values.

ah, indeed ...

Quoted 7 lines
Quoted 3 lines

The fix is to compare these values against (s64)LONG_MAX and assign (s64)LONG_MAX to exec_delta64 and fair_delta64 if they are greater than (s64)LONG_MAX.

Tested on PowerPC, the regression is gone, tasks are load balanced as they were in v7.

thanks, applied!

Ingo

I started up 12 glxgears to see the effect of CFS v8 on my Athlon64 X2 4200.

Without this patch all the GL load was handled by the second core, the system only stressed the first core if other processes were also started, i.e. a kernel compilation. With this patch the load is evenly balanced across the two cores all the time. And while doing make -j4 on the kernel, the 12 gears are still spinning about 185+ FPS and there are only slightly visible hiccups. Switching between workspaces, i.e. refreshing the large windows of Thunderbird and Firefox are done very quickly, the whole system is exceptionally responsive.

Thanks for this great work!

Best regards,
Zoltán Böszörményi

#1 lore raw
Quoted 7 lines · Zoltan Boszormenyi

I started up 12 glxgears to see the effect of CFS v8 on my Athlon64 X2 4200.

Without this patch all the GL load was handled by the second core, the system only stressed the first core if other processes were also started, i.e. a kernel compilation. With this patch the load is evenly balanced across the two cores all the time.

ok, i didnt realize that it would affect x86_64 too. I'll do a -v9 release with this fix included.

Quoted 5 lines

[...] And while doing make -j4 on the kernel, the 12 gears are still spinning about 185+ FPS and there are only slightly visible hiccups. Switching between workspaces, i.e. refreshing the large windows of Thunderbird and Firefox are done very quickly, the whole system is exceptionally responsive.

great! So it seems -v8 does improve OpenGL handling too :-)

Quoted 1 line

Thanks for this great work!

you are welcome :)

Ingo

#2 lore raw

Hello,

Quoted 1 line · Ingo Molnar

great! So it seems -v8 does improve OpenGL handling too :-)

What are your thoughts/plans concerning merging CFS into mainline ? Is it a bit premature to get it into 2.6.22 ? I remember Linus was ok to change the default scheduler rapidly (the discussion was about sd at that time) to get more testing than in -mm.

Signature · 1 line
Damien Wyart
#3 lore raw
Quoted 4 lines · Damien Wyart

What are your thoughts/plans concerning merging CFS into mainline ? Is it a bit premature to get it into 2.6.22 ? I remember Linus was ok to change the default scheduler rapidly (the discussion was about sd at that time) to get more testing than in -mm.

And what about group scheduling extensions? Do you have plans to work on it? I was begining to work on a prototype to do group scheduling based on CFS, basically on the lines of what you and Linus had outlined earlier:

	http://lkml.org/lkml/2007/4/18/271
	http://lkml.org/lkml/2007/4/18/244
Signature · 2 lines
Regards,
vatsa
#4 lore raw
Quoted 4 lines · Damien Wyart
Quoted 4 lines

What are your thoughts/plans concerning merging CFS into mainline ? Is it a bit premature to get it into 2.6.22 ? I remember Linus was ok to change the default scheduler rapidly (the discussion was about sd at that time) to get more testing than in -mm.

Quoted 6 lines · Srivatsa Vaddagiri

And what about group scheduling extensions? Do you have plans to work on it? I was begining to work on a prototype to do group scheduling based on CFS, basically on the lines of what you and Linus had outlined earlier:

	http://lkml.org/lkml/2007/4/18/271
	http://lkml.org/lkml/2007/4/18/244

Tong Li's Trio scheduler does a bit of this, though it doesn't seem to have the mindshare cfs seems to have acquired.

The hyperlink seems to have broken, though:

	http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch

-- wli

#5 lore raw
Quoted 14 lines · William Lee Irwin III
Quoted 4 lines · Damien Wyart
Quoted 4 lines

What are your thoughts/plans concerning merging CFS into mainline ? Is it a bit premature to get it into 2.6.22 ? I remember Linus was ok to change the default scheduler rapidly (the discussion was about sd at that time) to get more testing than in -mm.

Quoted 6 lines · Srivatsa Vaddagiri

And what about group scheduling extensions? Do you have plans to work on it? I was begining to work on a prototype to do group scheduling based on CFS, basically on the lines of what you and Linus had outlined earlier:

	http://lkml.org/lkml/2007/4/18/271
	http://lkml.org/lkml/2007/4/18/244
Quoted 5 lines

Tong Li's Trio scheduler does a bit of this, though it doesn't seem to have the mindshare cfs seems to have acquired.

The hyperlink seems to have broken, though:

	http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch

Yeah, I just fixed the link. The code was written based on the 2.6.19.2 scheduler. I could forward-port it to the latest kernel if there's interest and I can find time. :) Here's a description of the design:

http://lkml.org/lkml/2007/4/20/286

Thanks,

tong

#6 lore raw
Quoted 4 lines · William Lee Irwin III
Quoted 4 lines

Tong Li's Trio scheduler does a bit of this, though it doesn't seem to have the mindshare cfs seems to have acquired.
The hyperlink seems to have broken, though:

	http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch
Quoted 4 lines · Tong N

Yeah, I just fixed the link. The code was written based on the 2.6.19.2 scheduler. I could forward-port it to the latest kernel if there's interest and I can find time. :) Here's a description of the design:
http://lkml.org/lkml/2007/4/20/286

I have the interest. I don't see performance issues with any of the schedulers, but am rather interested in the feature.

-- wli

#7 lore raw
In reply to William Lee Irwin III
Quoted 8 lines · William Lee Irwin III
Quoted 6 lines · Srivatsa Vaddagiri

And what about group scheduling extensions? Do you have plans to work on it? I was begining to work on a prototype to do group scheduling based on CFS, basically on the lines of what you and Linus had outlined earlier:

	http://lkml.org/lkml/2007/4/18/271
	http://lkml.org/lkml/2007/4/18/244
Quoted 5 lines

Tong Li's Trio scheduler does a bit of this, though it doesn't seem to have the mindshare cfs seems to have acquired.

The hyperlink seems to have broken, though:

	http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch

The big question I have is, how well does DWRR fits into the "currently hot" scheduling frameworks like CFS? For ex: if the goal is to do fair (group) scheduling of SCHED_NORMAL tasks, can CFS and DWRR co-exist? Both seem to be radically different algorithms and my initial impressions of them co-existing is "No", but would be glad to be corrected if I am wrong. If they can't co-exist, then we need a different way of doing group scheduling on top of CFS, as that is gaining more popularity on account of better handling of interactivity.

Tong,
I understand a center hallmark of DWRR is SMP fairness.
Have you considered how bad/good the other alternative to achieve SMP fairness which is in vogue today : pressure/weight based balancing (ex: smpnice and CKRM CPU scheduler - ckrm.sourceforge.net/downloads/ckrm-ols03-slides.pdf)?

Signature · 2 lines
Regards,
vatsa
#8 lore raw
Quoted 15 lines · Srivatsa Vaddagiri
Quoted 8 lines · William Lee Irwin III
Quoted 6 lines · Srivatsa Vaddagiri

And what about group scheduling extensions? Do you have plans to work on it? I was begining to work on a prototype to do group scheduling based on CFS, basically on the lines of what you and Linus had outlined earlier:

	http://lkml.org/lkml/2007/4/18/271
	http://lkml.org/lkml/2007/4/18/244
Quoted 5 lines

Tong Li's Trio scheduler does a bit of this, though it doesn't seem to have the mindshare cfs seems to have acquired.

The hyperlink seems to have broken, though:

	http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch
Quoted 8 lines

The big question I have is, how well does DWRR fits into the "currently hot" scheduling frameworks like CFS? For ex: if the goal is to do fair (group) scheduling of SCHED_NORMAL tasks, can CFS and DWRR co-exist? Both seem to be radically different algorithms and my initial impressions of them co-existing is "No", but would be glad to be corrected if I am wrong. If they can't co-exist, then we need a different way of doing group scheduling on top of CFS, as that is gaining more popularity on account of better handling of interactivity.

Yeah, the intent of DWRR was to provide proportional fairness and rely on the underlying scheduler to support interactivity. In a way, DWRR ensures that each task receives its fair share, while the underlying scheduler determines the right order to run the tasks. Since SD is structurally similar to the stock scheduler, DWRR should co-exist with it easily. Co-existing with CFS requires more work, but I think the round-robin mechanism in DWRR could be applicable to CFS to facilitate cross-processor fairness.

Quoted 6 lines

Tong,
I understand a center hallmark of DWRR is SMP fairness.
Have you considered how bad/good the other alternative to achieve SMP fairness which is in vogue today : pressure/weight based balancing (ex: smpnice and CKRM CPU scheduler - ckrm.sourceforge.net/downloads/ckrm-ols03-slides.pdf)?

The disadvantage of DWRR is its potential overhead and the advantage is it can provide stronger fairness. If we have 2 processors and 3 tasks, DWRR ensures that each task gets 66% of the total CPU time, while smpnice would keep two tasks on the same processor and the third one on another. I did an analysis and showed that the lag bound of DWRR is constant if task weights are bounded by a constant. On the other hand, the cost DWRR pays is that it requires more task migrations. I tested with a set of benchmarks on an SMP and didn't see migrations were causing much performance impact, but this is certainly a big issue for NUMA.

tong

PS. I'm now porting the code to the latest kernel and will post as soon as I'm done.

#9 lore raw
In reply to Damien Wyart
Quoted 10 lines · Damien Wyart

Hello,

Quoted 1 line · Ingo Molnar

great! So it seems -v8 does improve OpenGL handling too :-)

What are your thoughts/plans concerning merging CFS into mainline ? Is it a bit premature to get it into 2.6.22 ? I remember Linus was ok to change the default scheduler rapidly (the discussion was about sd at that time) to get more testing than in -mm.

It would seem that a number of us are testing the variants and reporting results (I now have to pull all the new versions and redo stuff, but I have a new test I'm going to run as well).

Given that and the fact that there is another idea which can be tested from Tong Li, I think that decision can be postponed, Linus willing. There appear to be enough testers to be driving evolution now, authors may disagree, of course.

Several folks added to cc list...

Signature · 3 lines
Bill Davidsen <[email protected]>
  "We have more to fear from the bungling of the incompetent than from
the machinations of the wicked."  - from Slashdot