Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler 333
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.'"
BFS is the Brain Fuck Scheduler. (Score:5, Interesting)
Why would the summary omit this precious bit of information?
great news (Score:5, Interesting)
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?
Glory! (Score:5, Interesting)
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?
Re:Glory! (Score:5, Interesting)
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.
Re:Glory! (Score:3, Interesting)
The "bad maintainer" part is referring to bad blood over the adoption of Ingo Molnar's CFS [kerneltrap.org] over Kolivas's own RSDL
Yeah but Con just didn't give the impression that he intended to be around to support his code. He is an anaesthetist. Software is a hobby which he could give up whenever he wants to. I think that is very different from somebody who is doing software for their career.
4096 cpu machines (Score:4, Interesting)
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 [xkcd.com].
I don't have 4096 CPUs, good job Con Kolivas!
Re:Linux gets Yet Another Scheduler (Score:3, Interesting)
I've yet to be impressed by any of them, for any use, with any hardware.
I've yet to be impressed by your comment, which contains no reason for your opinion.
Care to give us some examples of your uses & hardware?
Re:4096 cpu machines (Score:3, Interesting)
Well who knows, maybe instead of the elusive year of Linux on desktop, we should be expecting and applauding years of downstream personal automated-installing GNU/Linux distributions like LFS or diy-linux, which will let users to choose schedulers and what not. Not exactly something I expect to happen soon, but my feeling is GNU/Linux is being institutionalized. It is like if the trust is just not there to anything but the mainline. People assume that the majority is right here - that the maintainers of mainline kernel know best - and every other hacker in minority like Con, is just experimenting. What if we can distribute this trust better - use "non-standard" schedulers etc - then the benchmarking will reach the users and the truth will be distilled eventually. If Cons new scheduler is as good as he tries to paint it, build kernel and use it in thousands. Currently, all eyes are on mainline, which is what prevents choice, even though the choice is "potentially" there.
16... okay for the desktop for 12 months (Score:5, Interesting)
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.
Re:He ain't kidding. (Score:3, Interesting)
Re:BFS is the Brain Fuck Scheduler. (Score:3, Interesting)
Another one for the Geeks-are-great-at-naming-things wall.
All the TLAs are taken anyway. As always, you'll have to look at the context.
Re:great news (Score:3, Interesting)
While I'm here, why does the summary [sic] i.e. It is a contraction of 2 words and perfectly acceptable. And in case they were worried about repetition with the following words " it is ", i.e. means "that is" as in "that is to say" used with a pause in normal speech. You have to read the preceding sentence, not take terms in isolation.
Re:great news (Score:5, Interesting)
Re:great news (Score:1, Interesting)
Out of interest, does it schedule disk access too? The article only mentions CPU scheduling, but I find that I rarely hit (or even get near) the 100% CPU usage, but when some process is monopolizing the hard disk (which I bought quite recently and is supposed to be moderately fast) everything becomes slow as tar, even when I set the process' priority to "idle". I'm using Windows XP at the moment, and have tested some GNU/Linux live CD's, which had the same problem, so understandably I'm more interested in how well schedulers cope with disk access.
Re:That has NEVER been the goal (Score:3, Interesting)
Hurd is not unsuccessful because it is a microkernel, it is unsuccessful because it is run by perfectionists. Every time they get something quite good, they realise that a complete rewrite could make it even better and they throw away a lot of good code.
Xen seems to be doing quite well as a microkernel, but until everyone is using multiprocessor machines there is a performance penalty for using a microkernel. When everyone is using multicore, they still have the disadvantage that monolithic kernels have been under active development for the last thirty years (more in a few cases) while microkernels have been largely ignored.
A modern OS kernel, however, often has a lot more in common with microkernel designs even if it's all running in a single address space. Take a look, for example, at the OpenSolaris network stack. Every component runs in a separate thread and communicates with those above and below via message passing. It would be trivial to separate these out into different userspace processes, but there's no real advantage to doing so.
Re:great news (Score:5, Interesting)
OOh. I've just seen the 'thought for the day' at the bottom of the page:
"One size fits all": Doesn't fit anyone.
Even the gods of slashdot are getting in on the debate.
Re:Linux on the Desktop/Linux on the Server (Score:5, Interesting)
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.
Re:He ain't kidding. (Score:3, Interesting)
Kudos Con (Score:4, Interesting)
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 [kerneltrap.org]
Re:great news (Score:5, Interesting)
I never really understood Linus' handling of Con in the past
Linux kernel development is all about "playing well with others": a very important part of the process is being able to handle criticism constructively and fix the problems it addresses, or show that it is wrong; that's the way progress is made. You need to do this again and again and again. Most criticism is very technical and can be quite insightful, but can also be strong and relentless -- people will point out every single little flaw, and possible flaws, and unclear points, and whitespace inconsistencies, and... To be a successful linux developer you need to be able to deal with this constructively, and the more important and core the area you're dealing with, the more important this becomes.
The impression I've gotten from reading various past "Con threads", is that while he tries in the beginning, Con doesn't deal well with this process; he can't keep his ego submerged, gets frustrated, and everything (perhaps including Con himself last time I read one of these threads) ends up unravelling. The same thing has derailed other big projects too (i.e., reiser4, when Reiser himself was still involved).
It's a shame when this happens, but basically the process is more important that specific pieces of technology -- technology can be replaced, but the process is what makes linux as good as it is.
Re:Glory! (Score:4, Interesting)
Anyway, Windows has had 2 schedulers for ages - you can select desktop or server style processing (and cache strategy) since NT4.
That's not two schedulers, it's just some tunables. See pages 391 to 444 of Windows Internals, 5th Edition (or comparable pages in earlier editions). For instance, on Vista the default quantum is two clock intervals (a "clock interval" is usually about 10 to 15 ms), while on Windows Server it's twelve clock intervals. Similarly, on desktops an extra boost is given to the currently focused application. You can adjust this at runtime in the GUI on Vista under Advanced System Settings -> Advanced -> Performance -> Settings -> Advanced (yes, apparently scheduler adjustments are very advanced in Microsoft's view). It can be controlled with slightly more granularity with the registry key HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation (a six-bit bitfield).
Linux currently offers scheduler tunables both at compile-time and runtime. Try ls /proc/sys/kernel/sched_*. It has more than Windows, apparently. I expect there are some compile-time options too, but I'm not an expert in anything related to kernels or systems programming.
Re:4096 cpu machines (Score:3, Interesting)
You might want to look up how he treated Alan Cox in relation to the tty code in the kernel, as well.
I followed that. Linus wasn't wrong about anything and Alan was acting a tad obtuse. 2.6.32 has been delayed another week to pick another louse out of the pty code.
There was more going on than was posted on lkml. Alan has always called Linus "pinhead" and gotten away with it.
Although he has an abrasive personality with developers at times, Linus is pretty good with testers. He was very patient with me in the 1.3 cycle (including sending me patches to test) as I was debugging what would ultimately prove to be a bad cache chip.
If that makes me a Linus fan boy, whatever. I'm amazed at what he's managed to accomplish. And for all of his "snapping and snarling" I've faced far worse from managers at work with no proven technical skills whatsoever.