Con Kolivas Introduces New BFS Scheduler

Sep 02, 2009

After two years deep into Linux, the Australian Con Kolivas has emerged with a new scheduler that above all should provide significantly better performance on dual and quad processors.

The Australian developer Con Kolivas

Whoever hasn't recently had a good enough reason to translate the kernel should take a look at the new patch from Con Kolivas. His Brain Fuck Scheduler (BFS) should, after compiling on a quad system, demonstrate better performance than the current Completely Fair Scheduler (CFS) from Ingo Molnar.

As Kolivas writes in his FAQ to the BFS, the performance improvement contrasts with how the current schedulers work with the CPUs:

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

The name Kolivas gave to his scheduler obviously meant to be provocative. On the one hand he was determined that it was possible to write a good scheduler using simple means and straightforward thinking. On the other he wanted to point out that it was totally unsatisfactory to have a scheduler support 4096 processors but be incapable of successfully running a Flash video on an average system.

This xkcd cartoon inspired Con Kolivas to write a new scheduler.

Kolivas nevertheless doubts that his newest scheduler will ever be accepted into the official Linux kernel, even though it can run faster on systems with up to 16 CPUs than any previous scheduler. It simply doesn't scale to 4096 processors nor does it work satisfactorily on non-uniform memory access (NUMA) systems.

The BFS patch along with benchmark diagrams and other details are on ck.kolivas.org. Why Kolivas turned his back on kernel development two years ago was revealed in an interview with Linux Magazine, a transcript of which also appears at the same website.

Related content

  • Ingo Molnar Tests New BF Scheduler

    Kernel developer Ingo Molnar has done a benchmark test to compare his Completely Fair Scheduler (CFS) with the recently released BFS from Australian Con Kolivas.

    more »
  • A Gaggle of Schedulers in Kernel Development Battle

    Really Fair - Really Simple, Really Fair - Really Unfair: three schedulers are the topic of current discussions on the kernel mailing list.

    more »
  • Kernel News
    more »
  • Realtime

    Linux provides tools and patches for speeding up the priority of multimedia applications. So if you're not getting the performance you expect, try shifting into overdrive.

    more »
  • Completely Fair Scheduler Analyzed

    Avinesh Kumar, an IBM developer has taken a close look at the Completely Fair Scheduler (CFS) introduced with kernel 2.6.23, comparing it with other schedulers. In the conclusion to the analysis, Kumar discusses changes in the future kernel 2.6.24 scheduler.

    more »

Comments

  • oiaohm doesn't know crap

    -ck never used -rt.

    It just demonstrates how little you know about that patchset and how bent you are about protecting people that's retarded scheduler development for years in addition to displacing a creative coder that had his ideas misunderstood and then stolen by folks that have little to do with the realities how open source ideals need to be followed to keep attracting folks like him to do significant work.

  • About the desktop

    oiaohm: did you bother to try it?

    Seriously?

    Because the difference is NOTICABLE.

    Desktops don't usually run a lot of processes so a competent scheduler will make it very smooth without stupid biases left and right.

    As for cgroups - the average desktop user does not care about that, and given the choice between doing cgroups or having a scheduler that doesn't need them for the desktop, any distro should go for the saner scheduler.

    ... And I think BFS has cgroups support anyway if you want them

  • Con Kolivas' Work

    oiaohm, if you're going to say that much about your countryman, Con Kolivas, do him the courtesy of putting your name on it. It's bad etiquette to be as thoroughly critical as you have been without giving people a chance to size up your knowledge and your body of work.

    Con Kolivas is right, that an operating system must be responsive to users as a top priority. He's worked hard to make his point. He should be recognized as a guy with a positive agenda and a willingness to work very hard to prove his point, and to make his computer more responsive to the user.

    Bureaucracy is necessary for something as big as the Linux Kernel project, but it should not be so impersonal and dismissive of hard work, good priorities, and the willingness of an individual to challenge the consensus of that bureaucracy.

    Kudos to Con Kolivas for putting the computer user ahead of the corporate server with 4096 processors. I never want my computer to become unresponsive for even a fraction of a second. When that happens, I smolder with a quiet fury, and I become motivated to strip out whatever code is responsible for it.

  • 5 Cent from a troll

    Con Kolivas is doing what Linus Torvalds used to do. It is what the hacker spirit is about, which we all are glorifying, to justify our strong emotions against software companies and closed source products:

    Somebody is unhappy about a piece of software, then making use of the own abilities to release an own version of the software.

    That business people, managers and computer illiterate people dont understand the potential of this creative use of a very basic form of freedom is not surprising at all. But that it is so well established and common within communities around free and open source software, that many people tend to forget what freedom is actually about, that is more than ironic.

  • Con Kolivas

    "Con Kolivas is basically a spoilt brat coder half promising users solutions then not going to follow the process threw to give users solutions. He should be treated as such." - oiaohm

    oiaohm, I already know from hanging out with you in #boycottnovell that you are not one to be calling another a spoilt brat. I'm not saying you are one, but neither is Con Kolivas.

    Richard Stallman is right to put focus on the relationship between software problems and social problems. I've noticed an attitude of "intellectual materialism" which leads people into a pissing contest where objectivity is lost.

    People can come up with rationalizations for their position when the objective reality of software is so complex and always shifting. It would take a long time and too much work to prove a critic wrong in this environment.

    People should stop resting so much of their sense of identity in their comprehension of technical concepts. Those who would like to establish that they are truly a unique specimen of cognitive ability may be trying to consolidate power or increase influence by shrouding their arcane knowledge with mystifying jargon.

    This is the mentality of a techno-priesthood. This is not in the spirit of sharing. With enough patience, algebra can be taught to a monkey.

    The question in my mind is this - to what extent is a given programmer conceited and ambitious. Con Kolivas is putting forth a lot of effort to demystify things, and to bring the center of gravity back from the 4096 processor corporate servers and onto the desks of users.

    I don't ever want my computer to stop responding, for even a half second. I don't want any blips in my audio, video, or graphical rendering. I want my operating system to be clear and responsive like clean water, never frozen.

    I understand the need to work within the boundaries of bureaucratic processes and to work as members of a team. I also know that not everyone within a bureaucracy is as adult or professional as they claim to be. The Linux project requires bureaucracy in addition to centralized control.

    No Linux Kernel fork is going to be worthwhile because it would be without the good-will of Linus Torvalds, and that new social rift would cause all kinds of new incompatibilities in the software ecosystem we all share.

    Reconciliation is the best option, and that requires people stop denigrating each others work. If a guy like Kolivas says he's not being appreciated, and he's got a following of people who appreciate his priorities, his results, his timeliness, that tells me that the bureaucracy should take notice and consider changing priorities themselves in favor of more user-responsiveness for desktops, rather than focusing on corporate big-iron to the detriment of desktop users.

    Con Kolivas may well care more about user freedom than Linus Torvalds. That doesn't mean he can go head to head with Torvalds in a political clash without breaking the working relationships Con Kolivas would require to work in the team.

    If Con Kolivas is called a brat for what he's done, I'd say he's more of an enfant terrible who has said something necessary. Maybe Linus Torvald's usurping the GNU project's own kernel project was also necessary and timely.

    What is not necessary is for the squabble to continue to the detriment of computer users freedom everywhere. It's time for reconciliation, not more flame wars. Con Kolivas has defended his reputation against critics with his latest work. People should understand his need to do so, because when you find yourself on the outside of a social group, subject to a dog-piling, you do need to defend your ego.

    Likewise, Linus Torvalds should stop taking shots at Richard Stallman. Linux enthusiasts should stop denigrating the Hurd project, and start treating it as the older, feebler, but wiser brother of the Linux kernel project. The Hurd could use some appreciation. The *nix design is based on an old template, and the Hurd is a fresh start, relative to the *nix mono-kernel design.

    My theory is that everyone has an ego and it's a part of your psychological anatomy. It's time for free and open source software geeks to learn more social skills and to stop throwing hay-makers at each other's egos with abandon.

    Once in a while, it's pretty awesome to have a throw-down. It's kind of like a gangster rapper chain-snatching a rival, and then ripping each other on the mic.

    But if that's all that's happening, it loses its entertainment value, battles are not decisive, beefs last too long, and morale suffers. Meanwhile, Microsoft is still there, denying computer users their freedom.

    Also, let's not forget all the revenue that we stand to gain by cooperating more effectively on behalf of computer users freedom.

  • -ck patchset was not a god send.

    -ck patchset is same as using real-time tree patches now and CFS. Yes it gives you gapless audio.

    Due to the overrides done right set of loads system dies due to the hacks done to the kernel with either -ck patchset or CFS + real-time patches at moment. Sorry need for the old -ck patch set is long gone. It will be completely gone once the real-time tree features are implemented completely correctly so they can all be merged into kernel.

    It was the problem Con Kolivas could not see. Just because it works fine for 90 percent. The 10 percent its causing data loss and other bad things to happen is not worth it. CFS is just a clean implementation without hacks of scheduler Con Kolivas designed.

    Simple terms implement items correctly or there will be cases were the complete thing malfunctions. I have tested Con Kolivas new patchset sorry its not like the -ck patches its not going to solve the problem in any way. Its gained speed at the price of control.

    Linux developers did take on what Con Kolivas did in the -ck tree. Just in different ways. Number 1 don't hack around issue work on addressing the issues in the core code causing lots of the faults Con Kolivas was hacking around. Real-time Tree merge is taking a lot longer than expected.

    Yes that is another of Con Kolivas faults. I want the solution now. No tolerance to make it work right.

    Common argument from Con Kolivas fans is that is knew what he was doing more than the other developers in the Linux kernel. Sorry to say no he did not. Lot of the other developers had done stuff like Con Kolivas in the past causing the performance problems we suffer from today. They gained an important lesson. Do it right or don't do it at all.

    Basically stop following crap. Con Kolivas is always great at making benchmarks at saying this is better than the default kernel. Never once looking at the side branches and the advantages those give.

    Remember the default kernel first requirement and I do mean first requirement is stability. Second is performance. Con Kolivas problem was trying to merge items that broke the first for the second. I personally prefer stability. Then would not accept that for stability at times you need to step back from what looks like perfect performance.

    Real-time tree maintainers know this. They have only been trying to merge for the last 6 years. Yes they know what they have will make stuff bench faster just like Con Kolivas benchmarks. They also know the side effects. They have been far more tolerant than Con Kolivas at merging piece by piece heading to goal.

    Now Con Kolivas releases code as ha ha I am better the code is that crappy the main line kernel will never merge it. Con Kolivas is basically a spoilt brat coder half promising users solutions then not going to follow the process threw to give users solutions. He should be treated as such.

    Con Kolivas would have been better to stay away them come back and do what he has done now.

    Reason Con Kolivas would have been just remembered as a person who wanted to implement features to fast and run out of tolerance to do it. Sparking off the work to put more effort into merging the real-time tree and other developers reseaching how to improve performance. This includes adding more tools for finding performance defects inside the kernel so they can be fixed far deep reaching than any of Con Kolivas benchmark tools. Able to tell you exactly what functions in the kernel are causing the performance problems. Con Kolivas benchmark tools could not answer that only that there was a problem.

    Now that is not what Con Kolivas fans want to hear. That the work of Con Kolivas was just a start. The idea of a good performing desktop is not Con Kolivas alone.

    Now Con Kolivas is a brat. Maybe give Con Kolivas a few more years and he might work out the Linux kernel developers are not dumb. They are just slow moving they do get there in the end just not as fast as people like. In early linux kernel history most likely that Con Kolivas never looked at they were fast moving and made the mistakes that cause the suffering today. They are once bitten twice shy. Dealing with people that have been hurt requires tolerance Con Kolivas sadly lacked. Progress may have been a lit more complete if Con Kolivas had been a better with tolerance.

    Con Kolivas wound have fitted perfectly into the early linux kernel development world. There is a chance that he is a hang over from it too.

    Con Kolivas would be welcomed back by the kernel world. Lot were sad to see his ideas go. Ok they were not merging his ideas. Even so it was giving other developers ideas where to look in the source base to fix problems.

    Lot of explosions are caused in the Linux kernel by the stability rule. Con Kolivas is not the only developer who has walked away. Lot have walked away cooled off and worked out the mistake. One of the lead network stack developers did with 2.4 Linux kernel. Solution was to put forward to branch a new version 2.6 that did not need to be binary compatible. TTY one recently makes me wonder if that should be the branch cause for 2.8.

    None bar Con Kolivas that have ever walked away have returned as a brat. At least Con Kolivas is first at something.

  • One thing for sure: -ck works

    One thing is for sure, the -ck patches before that one did an increadible job. Still, many years and hardware generations after, the best performing system I ever had (as in user experience, gapless audio playback while copying large and many files, ...) was a 300 MHz Pentium II with probably 512 MB RAM running a 2.4 -ck kernel.

    My current systems still have gaps in Audio playback even though they are running at 1.8 GHz and more.

    I wish back my old system, just for playing audio.

    Ergo, I/O scheduling still sucks in Linux. A users perspective, only supported by many hours of use experience with the system.

  • Con Kolivas Is Right

    Con Kolivas Is Right

    It's about time someone starts forking the Linux kernel. Linux Torvalds has broken the most basic rules of computer science from day one. Today's Linux is a broken mess because of no design or bad design by Torvalds.

    Con Kolivas should fork the kernel and call it Conux or something? Maybe he could build a team of smart programmers who actually read/write standard English? Unlike the typical Linux user: "Yes it still by Con Kolivas benchmark would look to be perfect."

  • Con Kolivas still has not learnt a thing.

    This is pure I am good you are bad kind of thing.

    I am sorry to say the scheduler is not that great for desktop. Shows promise when you need non bias load distribution.

    Remember Windows scheduler is worse performing than the Linux one on threw put. Reason why desktop user like it more is bias. I state that again bias.

    Desktop users don't want a fair scheduler they want a bias one. Windows gives a bias to the active window application so it gets more cpu time. So what the user is working on happen sooner. Windows gives a bias to audio and video output as well so they happen on time and don't break up.

    The desktop scheduler is more lack of integration from X11 to scheduler and lack of real time support to deal with video and audio issues.

    Same kind of issue of not wanting to work with others got Con Kolivas into trouble in the first place. The current Linux kernel does have multible schedulers. So if Con Kolivas one was good enough there is no reason why it could not be merged.

    There is a bigger problem. Really Linux has too many schedulers working independant to each other. Con Kolivas is not addressing how to link up IO scheduler to CPU scheduler. There is no point of giving a fixed slice cpu time to a process that is just going to look at the IO scheduler and go ok cannot do anything. That loses a block of time. Integration between the schedulers need to be done as well as integration between interface and scheduler.

    Yes it still by Con Kolivas benchmark would look to be perfect. It fails to take account of real world problems.

    Cgroups if used correctly by the desktop can allow the system to be recoverable in case of lockups due to run away processes in a reasonable amount of time. Should desktop user have to know how to set cgroups answer no. Should distributions been setting them up so user does not find themselves jammed answer is yes. Does using Cgroups cost performance answer yes. Does user care most of the time no. Lose of there work due to lockup is more of a problem to them.

    Con Kolivas step back look at the big picture for once. The issue is far bigger than the scheduler you could alter that for ever without fixing the rest you will never fix up the Linux desktop.
comments powered by Disqus
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters

Support Our Work

Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.

Learn More

News

Tag Cloud

Administration Community Events Hardware Linux Linux Pro Magazine Mobile Programming Security Software Ubuntu Web Development Windows free software open source