Slashdot Mirror
Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler
myvirtualid writes "Con Kolivas has done what he swore never to do: returned to the Linux kernel and written a new — and, according to him — waaay better scheduler for the desktop environment. In fact, BFS appears to outperform existing schedulers right up until one hits a 16-CPU machine, at which point he guesses performance would degrade somewhat. According to Kolivas, BFS 'was designed to be forward looking only, make the most of lower spec machines, and not scale to massive hardware. i.e. [sic] it is a desktop orientated scheduler, with extremely low latencies for excellent interactivity by design rather than 'calculated,' with rigid fairness, nice priority distribution and extreme scalability within normal load levels.'"
Why would the summary omit this precious bit of information?
Great news :-) Now, will the kernel people with Mr. Torvalds at their head, restart the whole debate on pluggable schedulers. Since his scheduler, as he says, degrades beyond 16 CPUs, better options already exists for servers where I am guessing CFS is used. So, he may be back, but the road ahead is still as steep?
May I be the first to say "amen"? I've been very dissatisfied with the 2.6 kernel and its schedulers on the desktop, CFS in particular. CFS seems entirely braindead for desktop use compared to the older schedulers in 2.4 and yes, even 2.2.
A desktop machine needs to be, first and foremost, responsive. If it isn't, it's comparable to the cursor freezing and input taking several seconds to appear: on today's hardware, one might start to think "hey, did it freeze on me?" - completely unacceptable.
Maybe it can be chalked up to the non-priority of X and video at the kernel level; I don't know. Whatever it is, it used to be better, on very pathetic (133MHz) hardware, while doing a lot more (and when such hardware was not all that powerful anymore, as well).
My question is: is it in the kernel tree yet? Is this that 2.6.31 scheduler change I heard about earlier yesterday, or is it something Completely Different?
Oh yeah, and which other scheduler's, if any, did this guy write?
~/ssh slashdot.org ssh: connect to host slashdot.org port 22: too many beers
I smell another LKML flamewar coming....
This comment is fully compliant with RFC 527.
Took me a while to figure out what "forward looking" means in this context, since "forward-looking scheduler" doesn't seem to be common terminology, and I assumed he wasn't talking about his grand forward-looking vision for schedulerdom.
Based on some previous arguments he's had, it sounds like he opposes the common heuristic of upping interactive process priority by keeping track of how long processes sleep--- processes that sleep a lot are probably I/O bound, and should get a priority boost so they can run on the (less frequent than for CPU-bound processes) occasions when they're ready. Kolivas wants schedulers to be forward-looking in the sense that they decide how to schedule without looking at process run history, by looking purely at who's ready to run, available timeslices, priorities, etc.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
He means something different by it--- that the scheduler should only look forward, not look back to per-process history in making its scheduling decisions. A common hack/heuristic to improve interactive performance is to boost the priority of processes that sleep a lot, since CPU-bound jobs sleep rarely, while interactive processes sleep a lot. Kolivas think that's a hack that obscures the real problems with interactive performance, and leads to unpredictable performance since it doesn't fix the underlying issues. So wants to design schedulers with good interactive performance that make decisions based purely on the current set of running processes and priorities, and the upcoming timeslices.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Still some grudge towards Torvalds and Molnar? From the FAQ:
Are you looking at getting this into mainline?
LOL.
No really, are you?
LOL.
Really really, are you?
No. They would be crazy to use this scheduler anyway since it won't scale to their 4096 cpu machines. The only way is to rewrite it to work that way, or to have more than one scheduler in the kernel. I don't want to do the former, and mainline doesn't want to do the latter. Besides, apparently I'm a bad maintainer, which makes sense since for some reason I seem to want to have a career, a life, raise a family with kids and have hobbies, all of which have nothing to do with linux.
Reminds me of this XKCD.
I don't have 4096 CPUs, good job Con Kolivas!
CFS can't even cope with a CPU-bound application.
Who here runs Linux on anything with more than 16 cores? Why should everyone else get the shitty end of the stick just because of maybe a dozen institutes with deep pockets?
16 sounds like a ridiculously high number for a desktop but is it?
Already we have 4 core processes which have "soft" additional threads (Intel's HT for instance) and some people already have dual CPU desktop machines meaning they are already at the 16 CPU limit.
Roll on 12-18 months and we'll be seeing 8 core CPUs with 8 soft-cores as coming in on top end desktops. Roll forwards 3 years and you'll be seeing 32 core CPUs with 32 soft-cores which is where the scheduler breaks down.
So the problem here is that this is a brilliant optimisation for today and for pieces like the netbook market but won't be good for the desktop market long term.
With Linux looking to be strong in the netbook market however it does say that having a more efficient scheduler for that market would be a better idea than just optimising everything for the server side.
An Eye for an Eye will make the whole world blind - Gandhi
From what I understood from the kernel discussion last time, this would probably have to be #ifdefs galore.
No, it really wouldn't. Take a look at how Xen and FreeBSD implement pluggable schedulers. Each scheduler in Xen is identified by a struct which contains pointers to its state and all of the functions related to actions the scheduler needs to take. These are called from the rest of the code (most commonly the timer interrupt handler). The total extra cost is one extra load instruction per call, which is tiny compared to the amount of work that the scheduler does. In FreeBSD, it's even simpler. The functions that implement the scheduler are declared in a header and implemented once in each scheduler's .c file(s). At compile time, you simply compile in the scheduler you want. Total run time cost is zero. FreeBSD cares about stability, so they've retained the old 4BSD scheduler all through the transition to the ULE scheduler (which, by the way, was outperforming the CFS in the last set of benchmarks I saw, although not by as large a margin as it outperformed the old Linux scheduler). This allows people operating servers that would rather sacrifice a little performance than use relatively new code to select the old one. Xen is designed for a variety of workloads, and so it has several schedulers that you can choose between.
Of course, these are only possible if the interface between the scheduler and the rest of the kernel is clean already. If it isn't, however, then you almost certainly have bigger problems than not being able to choose between two schedulers.
I am TheRaven on Soylent News
Welcome back Con! I wonder how long it is before Ingo "Kudos Con" Molnar rips of the new design? The kernel team has developed a very bad case of "not invented here." http://kerneltrap.org/node/8059
an ill wind that blows no good
If you're interested, the clang team have done a lot of profiling of exactly what takes time when compiling. It's particularly interesting how much of a bottleneck preprocessing is with gcc and, more importantly, distcc (which sends the preprocessed sources over the network for compilation). Most of the results are on the web site, with a few in the mailing list archives.
I am TheRaven on Soylent News