Follow Slashdot blog updates by subscribing to our blog RSS feed


Forgot your password?
Programming Linux

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.'"
This discussion has been archived. No new comments can be posted.

Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler

Comments Filter:
  • by Anonymous Coward on Sunday September 06, 2009 @05:35AM (#29330037)

    Why would the summary omit this precious bit of information?

  • great news (Score:5, Interesting)

    by amn108 ( 1231606 ) on Sunday September 06, 2009 @05:36AM (#29330045)

    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)

    by CAIMLAS ( 41445 ) on Sunday September 06, 2009 @05:41AM (#29330067) Homepage

    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)

    by kav2k ( 1545689 ) on Sunday September 06, 2009 @05:49AM (#29330093)
    Citing the FAQ:

    Are you looking at getting this into mainline?


    No really, are you?


    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)

    by MichaelSmith ( 789609 ) on Sunday September 06, 2009 @06:12AM (#29330179) Homepage Journal

    The "bad maintainer" part is referring to bad blood over the adoption of Ingo Molnar's CFS [] 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)

    by boldie ( 1016145 ) on Sunday September 06, 2009 @06:39AM (#29330241)
    Still some grudge towards Torvalds and Molnar? From the FAQ:
    Are you looking at getting this into mainline?

    No really, are you?

    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!
  • by tpgp ( 48001 ) on Sunday September 06, 2009 @06:43AM (#29330255) Homepage

    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)

    by amn108 ( 1231606 ) on Sunday September 06, 2009 @07:18AM (#29330345)

    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.

  • by MosesJones ( 55544 ) on Sunday September 06, 2009 @07:18AM (#29330347) Homepage

    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)

    by dbIII ( 701233 ) on Sunday September 06, 2009 @07:39AM (#29330411)
    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.
  • by Jurily ( 900488 ) <jurily@g m a i l . com> on Sunday September 06, 2009 @07:59AM (#29330477)

    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)

    by smoker2 ( 750216 ) on Sunday September 06, 2009 @09:18AM (#29330835) Homepage Journal
    The hardware is not the point. The software is. I run a linux machine which I use both as a media and web server, and as my main desktop for web browsing, email, WP etc. A hard coded setup would not be useful there.

    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)

    by TheRaven64 ( 641858 ) on Sunday September 06, 2009 @10:01AM (#29331037) Journal
    Why does Linux not have pluggable schedulers already? You can choose the scheduler in FreeBSD by changing a compile-time option and in OpenSolaris and Xen by changing a boot-time parameter. I think HURD can swap them out at run time, but I only know one person who actually runs HURD, and he also runs other systems for real work. If your system already has clean interfaces for the scheduler, then making them pluggable at compile time is trivial and making them pluggable at boot time is only a small amount of effort (although a bit more to make sure this has no performance side-effects). If it doesn't already have clean interfaces to the scheduler, then it probably has more serious problems than the lack of plug-support.
  • Re:great news (Score:1, Interesting)

    by Anonymous Coward on Sunday September 06, 2009 @10:08AM (#29331089)

    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.

  • by TheRaven64 ( 641858 ) on Sunday September 06, 2009 @10:08AM (#29331093) Journal

    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)

    by gbjbaanb ( 229885 ) on Sunday September 06, 2009 @10:17AM (#29331159)

    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.

  • by TheRaven64 ( 641858 ) on Sunday September 06, 2009 @10:18AM (#29331173) Journal

    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)

    by TheRaven64 ( 641858 ) on Sunday September 06, 2009 @10:37AM (#29331283) Journal
    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.
  • Kudos Con (Score:4, Interesting)

    by amightywind ( 691887 ) on Sunday September 06, 2009 @10:41AM (#29331309) Journal

    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." []

  • Re:great news (Score:5, Interesting)

    by macshit ( 157376 ) <.snogglethorpe. .at.> on Sunday September 06, 2009 @02:21PM (#29332983) Homepage

    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)

    by Simetrical ( 1047518 ) <> on Sunday September 06, 2009 @02:23PM (#29333015) Homepage

    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)

    by SL Baur ( 19540 ) <> on Sunday September 06, 2009 @07:27PM (#29335215) Homepage Journal

    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.

Experience varies directly with equipment ruined.