Re:How Con Kolivas's BFS CPU scheduler works
by DarkShikari on Friday October 16, 2009 @04:43PM
(#886137)
One advantage of BFS is the fact that it is very simple: the sheer number of heuristics that have made their way into CFS have a tendency to cause all sorts of problems in--often rather important--pathological cases.
The speed loss was so huge on what should have been an extremely easy load that it probably explains quite a few "Windows is faster than Linux" benchmarks I've seen over the past few months...
Re:How Con Kolivas's BFS CPU scheduler works
by jws on Friday October 16, 2009 @05:36PM
(#886224)
If the scheduler's purpose is "to make typical desktop loads feel better", how do you benchmark that? There is certainly room for improvement in making the Linux desktop feel good, but I don't know how one would get to a number. Perhaps you'd have to resort to double blind comparison tests.
(FWIW, my 1.2GHz PPC running Debian performs unacceptably as a desktop machine. There are sometimes >1000ms lags between a keypress and it being reflected on the X11 display with no background load. But I can't say this is because of the scheduler.)
Re:How Con Kolivas's BFS CPU scheduler works
by viraptor on Friday October 16, 2009 @06:17PM
(#886288)
> how do you benchmark that?
By getting statistics from the scheduler itself: how long did the process have to wait before it started executing. Also by looking at global effects: run N mplayers at the same time and look for dropped frames ; run an app that maps similar amount of work to N children and measure the run time ; measure the time needed for compiling [big project] with concurency == number of cpus ; ...
Re:How Con Kolivas's BFS CPU scheduler works
by Tuna-Fish on Friday October 16, 2009 @08:50PM
(#886451)
run an app that maps similar amount of work to N children and measure the run time ; measure the time needed for compiling [big project] with concurency
These are both the kind of tasks Kolivas is willing to totally throw under the bus for better worst case latency.
Remember, the single goal of the project is to get worst-case latency for all non-cpu-limited processes on the system as low as it possibly can get. Throughput, and even best- and average case latency are considered entirely expendable. This is why the BFS is hard to benchmark.
Re:How Con Kolivas's BFS CPU scheduler works
by scott_s on Friday October 16, 2009 @10:49PM
(#886544)
Then measure worst case latency. I don't see what the difficulty is.
If you're purporting to improve the performance of something, but you aren't always measuring the impact your changes have on the actual performance of that something, you're working blind.
Re:How Con Kolivas's BFS CPU scheduler works
by mquander on Friday October 16, 2009 @10:09PM
(#886518)
Actually, Kolivas states in the FAQ that compiling in particular is measured to be significantly faster with BFS:
"For years we've been doing our workloads on linux to have more work than we had CPUs because we thought that the "jobservers" were limited in their ability to utilise the CPUs effectively (so we did make -j6 or more on a quad core machine for example). This scheduler proves that the jobservers weren't at fault at all, because make -j4 on a quad core machine with BFS is faster than any choice of job numbers on CFS." [1]
Re:How Con Kolivas's BFS CPU scheduler works
by nailer on Saturday October 17, 2009 @04:13PM
(#887366)
> Remember, the single goal of the project is to get worst-case latency for all non-cpu-limited processes on the system as low as it possibly can get. Throughput, and even best- and average case latency are considered entirely expendable.
I've just been listing to lectures from MIT's introduction to algorithms, where more emphasis is placed on worst-case scenarios than otherwise, the reasoning being that these make guarantees possible. So more power to BFS.
At some point in the discussion, someone introduces a benchmark that clearly reproduces a problem with the current CFS scheduler. I think that perfectly illustrates what you are looking for (unfortunately, I have to run and can't pinpoint the exact post in this timeframe).
Re:How Con Kolivas's BFS CPU scheduler works
by nailer on Saturday October 17, 2009 @08:09AM
(#886862)
Quite an interesting read. Did anyone else fidn it worrying that Ingo Molnar attempted to benchmark a scheduler that aims for interactive response using:
* kernel build
* pipe
* messaging performance
* OLTP performance
And then wonders why he doesn't get an improvement?
One of the other posters puts it perfectly:
"Do you know what a normal desktop PC looks like? No, a more realistic question based on what you chose to benchmark to prove your point would be: Do you know what normal people actually do on them?"
In answer to the parent poster, see Nikos Chantziaras' posts.
Re:How Con Kolivas's BFS CPU scheduler works
by yason on Saturday October 17, 2009 @03:09AM
(#886726)
Is there a scheduler API in Linux kernel already? If there isn't, it seems that developing schedulers would really benefit from the ability to have them loaded / unloaded as kernel modules, like filesystems. The system could fall back to some generic round-robin scheduler if none of the more advanced schedulers were loaded, or when switching between schedulers.
I would want to try out BFS but I'm old enough to not take the time and effort to compile and patch my own kernel anymore, so I'll probably just wait until BFS becomes the default in mainstream kernels. If ever, considering the scheduler wars in the recent years.
A single kernel module I could compile and try out pretty easily, especially with module-assistant. Or if there's a .deb of Ubuntu kernel patched with BFS, that would do too.
I'm lazy, yes. Until I hack the Linux kernel day and night myself, it's probably better this way. But I would still like to try out BFS, up to some degree.
Re:How Con Kolivas's BFS CPU scheduler works
by alextp on Saturday October 17, 2009 @07:43AM
(#886854)
Linus is openly opposed to the idea of scheduler modules, his argument being that schedules are core parts of a kernel, and modularizing schedulers woud encourage many different schedulers each good at a simple thing instead of a single scheduler well optimized for all workloads.
Re:How Con Kolivas's BFS CPU scheduler works
by yason on Saturday October 17, 2009 @11:48AM
(#887052)
Yeah, the conclusion was something like this a couple of years ago when the issue was brought up on LKML. Too bad his opinion hasn't changed.
I don't think it's a good idea to wait for the perfect one-size-fits-all scheduler instead of supporting competition between different schedulers. People have different needs and hence they need different schedulers -- I might suggest that it's be the only way to ever find the well-optimized single scheduler.
Re:How Con Kolivas's BFS CPU scheduler works
by ars on Friday October 16, 2009 @05:14PM
(#886185)
I have to say it looks really really good. It's tuned specifically for desktop needs.
What are the chances of this getting into mainline? Yes, I read about his history. Maybe it will go in anyway. (But it really needs a new name - any suggestions for a better back-ronym?)
One thing I did not see that it has, is hyperthreading support, i.e. detecting that two cores are really the same, and not scheduling two tasks on the same core, while other are available. And also, not scheduling idle priority tasks on a core used by other tasks.
Re:How Con Kolivas's BFS CPU scheduler works
by ars on Friday October 16, 2009 @05:48PM
(#886251)
He replied:
> Does BFS support hyperthreading?
> Meaning, detecting that two cores are really the same, and not scheduling two tasks on the same core, while others are available.
The answer to that is "somewhat". It depends on the topology and workload, but it does not do anything like the complex balancing the mainline scheduler does to achieve this. I don't have enough hardware to see how it works in the real world on different topology and what workloads and how that compares to mainline.
> And also, not scheduling idle priority tasks on a core used by other tasks.
It does nothing smart to separate idle priority tasks from normal ones on SMT siblings vs cores.
And to answer the obvious question that follows these, I don't anticipate I'll be adding any more complex HT management than is already there as that will sway from the philosophy of BFS.
Re:How Con Kolivas's BFS CPU scheduler works
by wmf on Friday October 16, 2009 @05:28PM
(#886209)
New Intel desktop/laptop systems have hyperthreading on by default, so the real question is whether desktop workloads are hurt by HT. In that case BFS could improve performance by avoiding co-scheduling (which it currently doesn't appear to do).
Re:How Con Kolivas's BFS CPU scheduler works
by altie on Friday October 16, 2009 @08:23PM
(#886425)
There isn't one answer for either desktop or server workloads, only trends. Some processor resources get cut in half between threads, some are duplicated and the threads compete for some others. If your favorite benchmark bottlenecks on a resource that's shared or divided between threads, it'll probably do worse with hyperthreading on; if that's not the case, and a lot of the instructions in the hot path can go to any decoder or ALU, it'll probably do better.
Re:How Con Kolivas's BFS CPU scheduler works
by Scott_MacGregor on Friday October 16, 2009 @05:33PM
(#886217)
This thing needs a better name. I can see the technology benefit, but commercially it needs a more technologically correct (P.C.) name.
If this is sold, the publicity people will have heart attacks and the legal documents will come up on porn searches. Not the best business strategy to peruse if the developers want to maximize the value of this asset.
Re:How Con Kolivas's BFS CPU scheduler works
by zokier on Friday October 16, 2009 @06:34PM
(#886324)
There is the beauty of BFS. It's not meant to be sold, nor it's not meant to be in mainline. It's just Cons scheduler. He wrote it because he had to upgrade his kernel and wasn't happy with its scheduler. So he wrote a new one. This is the very essence of Linux imho. From hackers to hackers without extraneous corporate bullshit like PC-speak etc.
Re:How Con Kolivas's BFS CPU scheduler works
by Scott_MacGregor on Saturday October 17, 2009 @10:59AM
(#886990)
Not necessarily marketing material, but a lot of big companies like to issue press releases when they add something or buy something. Plus, if it is picked up and used by any big name in the industry some of the blogs will probably pick it up and make a mockery out the name using their so-called clever writing skills, lol.
From a business standpoint, this might be a concern for some companies. I can’t see any "positive business reason" to have a name like that, it only seems like a negative to me.
Re:How Con Kolivas's BFS CPU scheduler works
by jsrn on Friday October 16, 2009 @05:44PM
(#886246)
perhaps you are right (although I don't quite understand what "publicity people" will have to do with a kernel scheduler), but the Unix world seems to have done not too badly with non-PC expressions such as "killing" or "starving" a process.
The kill system call even made it into "serious" standard documents:
Re:How Con Kolivas's BFS CPU scheduler works
by Scott_MacGregor on Saturday October 17, 2009 @11:03AM
(#886996)
If it is picked up and used by any big name in the industry, some of the blogs will probably pick it up and make a mockery out the name. From a business standpoint, this might be a concern for some companies.
Here's one example from a recent commit:
http://patchwork.kernel.org/patch/47921/
The speed loss was so huge on what should have been an extremely easy load that it probably explains quite a few "Windows is faster than Linux" benchmarks I've seen over the past few months...
(FWIW, my 1.2GHz PPC running Debian performs unacceptably as a desktop machine. There are sometimes >1000ms lags between a keypress and it being reflected on the X11 display with no background load. But I can't say this is because of the scheduler.)
By getting statistics from the scheduler itself: how long did the process have to wait before it started executing. Also by looking at global effects: run N mplayers at the same time and look for dropped frames ; run an app that maps similar amount of work to N children and measure the run time ; measure the time needed for compiling [big project] with concurency == number of cpus ; ...
These are both the kind of tasks Kolivas is willing to totally throw under the bus for better worst case latency.
Remember, the single goal of the project is to get worst-case latency for all non-cpu-limited processes on the system as low as it possibly can get. Throughput, and even best- and average case latency are considered entirely expendable. This is why the BFS is hard to benchmark.
If you're purporting to improve the performance of something, but you aren't always measuring the impact your changes have on the actual performance of that something, you're working blind.
"For years we've been doing our workloads on linux to have more work than we had CPUs because we thought that the "jobservers" were limited in their ability to utilise the CPUs effectively (so we did make -j6 or more on a quad core machine for example). This scheduler proves that the jobservers weren't at fault at all, because make -j4 on a quad core machine with BFS is faster than any choice of job numbers on CFS." [1]
[1] http://ck.kolivas.org/patches/bfs/bfs-faq.txt
I've just been listing to lectures from MIT's introduction to algorithms, where more emphasis is placed on worst-case scenarios than otherwise, the reasoning being that these make guarantees possible. So more power to BFS.
Yes you can.
And you answered your own question: latency is exactly how you benchmark this (with a measure of total throughput added in to make sure it's not low).
At some point in the discussion, someone introduces a benchmark that clearly reproduces a problem with the current CFS scheduler. I think that perfectly illustrates what you are looking for (unfortunately, I have to run and can't pinpoint the exact post in this timeframe).
* kernel build
* pipe
* messaging performance
* OLTP performance
And then wonders why he doesn't get an improvement?
One of the other posters puts it perfectly:
"Do you know what a normal desktop PC looks like? No, a more realistic question based on what you chose to benchmark to prove your point would be: Do you know what normal people actually do on them?"
In answer to the parent poster, see Nikos Chantziaras' posts.
I would want to try out BFS but I'm old enough to not take the time and effort to compile and patch my own kernel anymore, so I'll probably just wait until BFS becomes the default in mainstream kernels. If ever, considering the scheduler wars in the recent years.
A single kernel module I could compile and try out pretty easily, especially with module-assistant. Or if there's a .deb of Ubuntu kernel patched with BFS, that would do too.
I'm lazy, yes. Until I hack the Linux kernel day and night myself, it's probably better this way. But I would still like to try out BFS, up to some degree.
I don't think it's a good idea to wait for the perfect one-size-fits-all scheduler instead of supporting competition between different schedulers. People have different needs and hence they need different schedulers -- I might suggest that it's be the only way to ever find the well-optimized single scheduler.
What are the chances of this getting into mainline? Yes, I read about his history. Maybe it will go in anyway. (But it really needs a new name - any suggestions for a better back-ronym?)
One thing I did not see that it has, is hyperthreading support, i.e. detecting that two cores are really the same, and not scheduling two tasks on the same core, while other are available. And also, not scheduling idle priority tasks on a core used by other tasks.
I emailed him to ask.
> Does BFS support hyperthreading?
> Meaning, detecting that two cores are really the same, and not scheduling two tasks on the same core, while others are available.
The answer to that is "somewhat". It depends on the topology and workload, but it does not do anything like the complex balancing the mainline scheduler does to achieve this. I don't have enough hardware to see how it works in the real world on different topology and what workloads and how that compares to mainline.
> And also, not scheduling idle priority tasks on a core used by other tasks.
It does nothing smart to separate idle priority tasks from normal ones on SMT siblings vs cores.
And to answer the obvious question that follows these, I don't anticipate I'll be adding any more complex HT management than is already there as that will sway from the philosophy of BFS.
Regards, Con
But anyway, if people are using unstable Linux scheduling algorithms, I bet they are OK tweaking their BIOS settings, too.
http://www.bitsum.com/prolasso.php
If this is sold, the publicity people will have heart attacks and the legal documents will come up on porn searches. Not the best business strategy to peruse if the developers want to maximize the value of this asset.
From a business standpoint, this might be a concern for some companies. I can’t see any "positive business reason" to have a name like that, it only seems like a negative to me.
Just don't say what BFS stands for.
OK, it's a bit of a stretch that they'll say what the scheduler is on the PO, but it could happen.
It needs a backronym.
Bloody Fine Scheduler?
Bazinga Fast Scheduler?
BigBang Feory Scheduler? :)
For example the BFG 9000 http://en.wikipedia.org/wiki/BFG_9000
The kill system call even made it into "serious" standard documents:
http://www.opengroup.org/onlinepubs/9699919799/functions/kil...
http://www.snopes.com/inboxer/outrage/master.asp