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
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!
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?
My pics.
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
I don't know about you, but I run 8 CPU linux cluster nodes at 100% on all CPUs for weeks at a time and I'm only at the very bottom end of "high performance computing". For about two minutes in total a day the nodes are dumping things to disk (snapshots) and are I/O bound. The rest of the time they are pegged at 100% until the job finishes (which takes days to weeks - geophysical stuff). There are several applications that behave this way on these nodes, but there are some that sit waiting doing nothing because they are badly written. That means I think your above statement is a strongly misleading pile of steaming rubbish.
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.
I am TheRaven on Soylent News
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
And how does Linux handle the T2? The chip has some incredibly complex scheduling constraints; for good performance you need to track both the cycle counter and the wall clock (to balance memory and CPU-bound loads), you need to balance cache churn with workload in your processor affinity (sometimes having related threads on the same core is faster, sometimes it isn't). Somehow, I can't help feeling that the one-size-fits-all scheduler in Linux doesn't actually do all of this.
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