Torvalds Explains Scheduler Decision

Firedog writes "There's been a lot of recent debate over why Linus Torvalds chose the new CFS process scheduler written by Ingo Molnar over the SD process scheduler written by Con Kolivas, ranging from discussing the quality of the code to favoritism and outright conspiracy theories. KernelTrap is now reporting Linus Torvalds' official stance as to why he chose the code that he did. 'People who think SD was "perfect" were simply ignoring reality,' Linus is quoted as saying. He goes on to explain that he selected the Completely Fair Scheduler because it had a maintainer who has proven himself willing and able to address problems as they are discovered. In the end, the relevance to normal Linux users is twofold: one is the question as to whether or not the Linux development model is working, and the other is the question as to whether the recently released 2.6.23 kernel will deliver an improved desktop experience."

Comments

Re:good for you

[RebelWebmaster]

Hasn't Linus already said he's very interested in adding it into the Linux kernel (going so far as to say that it could be a reason to consider going GPLv3 in the future if Sun releases Solaris under it), but right now it's tied up in closed source?

For those of us who are not kernel hackers,

[MoOsEb0y]

What do CFS and SD stand for in this case? The summary and linked articles do not describe this.

Re:good for you

[RebelWebmaster]

Is CDDL compatible with GPLv2? I may have mispoke in my first post, but I think the gist of what I was trying to say is still there. ZFS is behind a license which isn't compatible with the license Linux is under. Or am I completely misunderstanding things? I'll admit I'm far from an expert on these matters...

"desktop experience"

[drDugan]

which kernel scheduler is pretty low on the list of factors affecting what the Linux desktop experience is all about...

frankly, really high quality experiences take organizational planning and leveraging the expereince of huge groups in way that the "bazzaar" model of software developemnt in open source does not do well. Would someone please just build a mutual benefit corporation for open source users and maintainers? Let's start paying for project managers and the other experienced professionals required to make a "desktop experience" and you will see Linux take over.

I find him rather rude

[bogaboga]

Having lurked on http://www.lkml.org/ for several years, I find Linus to be rather rude. May be it's because English is not his first language...so words are not well chosen. I must say though, that I excuse him because he produces, [or helps produce] a very useful product on the world today. That is the Linux kernel.

Re:I find him rather rude

[Anonymous Coward]

It can be difficult to be sure whether you really do get along or not. I'm also a Finn but grew up abroad and moved here when I was 16. I do speak the language fluently since I spoke it with my parents at home but I got quite a culture shock when I moved here. At first I constantly had the feeling that I must've said something inappropriate or offended someone if people around me were quiet but eventually I've learnt to accept that it's not necessary to constantly engage in a more or less pointless conversation. People here say precisely what they mean, which in a sense is convenient but can feel very harsh at times (i.e. you rarely need to try to guess what somebody means but it's hard to judge the "magnitude" of an objection). My greatest problem is probably that if I disagree with someone I'd like to give a subtle hint first but nobody gets it if I and if I say explicitly what I mean, I feel like I'm making too much of an issue over something that is relatively minor.

Re:I find him rather rude

[drerwk]

I had the pleasure of visiting Helsinki for work for 6 weeks in deep winter. The Finns are terrific. My favorite mannerism is when you get bumped on the sidewalk which is of course very icy, in the morning walk to work crowd, and fall on your behind. The polite response is a half laugh/cough "Ho!". No help up, no sorry, just "Ho!". At first, when it was me, I thought it was personal and rude. But I saw some poor lady get exactly the same treatment. Everyone was treated the same.

During the same trip I saw the Gulf of Finnland freeze. First salt water body I've seen freeze. And the Finns were thrilled because now the drive to Tallinn was a mere 80 mi round trip, and the booze in Tallinn is tax free.

Ooksie isso olute kiitose...pardon my phonetic spelling

Re:I find him rather rude

[Johnno74]

I second that. I've worked with Finnish guys, and thats just the way they are. Its not that they are rude, its just that they don't care so much about being polite.

This might trample on a few toes but it sure gets the job done.

Re:I find him rather rude

[jibun]

Just to clarify, what you heard as "ho!" was probably the word "oho" which basically means the same as "oops" in English. For some Finnish people, especially for the younger urbanites, this word has replaced the Finnish equivalent for sorry, "anteeks(i)" [UN-tayk-s(ee)], presumably because they are too "busy" to ponder whether the incident was their fault or not. It's like pleading "no contest" :) This behavior is a product of Finland's accelerated post-WW2 urbanization which relinquished the grip of Finland's traditionally quite strict ethics on how you addressed your superiors and peers. You see, the rural societies were quite hierarchical but in the industrialized communities, where sons and daughters of farmers moved to work in factories, the young people declared themselves free of formal speech patterns -- for instance insisting on egalitarian thees and not yous (see http://en.wikipedia.org/wiki/T-V_distinction).

Unfortunately the current generation, the kids of these baby boomers (the 20 and 30-somethings of today) don't have the same sense of community that their parents had when they grew up, so they have gone over the top and partially lost their moral compass wrt. what is polite enough to be acceptable. There are signs of a counter-phenomenon emerging as a result of the very good economic growth in Finland's telecommunications sector (read: Nokia) which has increased the number of well-off people considerably and made middle class values somewhat fashionable again. Whether this will make people less rude on icy boardwalks, remains to be seen.

Yksi kuiva siideri, kiitos. Pankille, kiitos.

Re:I find him rather rude

[epine]

• Polite: That's an interesting idea, but doesn't quite fit with the approach we're taking. Thank you for your input, though.
  

What you have depicted as polite I would portray as the inscrutible kiss-off of death. Thank you for your input, though.

When I read Con's resignation screed, he put forward views of determinism I strongly disagree with. Con seems to have missed the news bulletin that adversarial solutions in game theory usually entail mixed strategies (i.e. non-deterministic responses).

It's usually a bad situation if only pure strategies can be implemented efficiently. The first example I became aware of was polar vs Cartesian coordinates. This is high school stuff. Some calculations are faster in one form than the other. Conversion from one to the other is costly. There is no comfortable place halfway in between. What you want from a scheduler to provide a consistent experience over a wide range of loads are highly efficient optimal cases for emphasizing latency or throughput (whichever the situation demands) and a low-cost method to blend the optimal cases non-deterministically. Non-determinism ensures you never get into that sidewalk gridlock where both parties simultaneously zig when they should have zagged. I once read a paper from the 1960s which advocated hashing symbol tables in compilers non-deterministically so that you never had any single program source which was consistently worst case (nor could an adversary realiably craft one).

Determinism is known to be a terrible feature in a security system. If you have a remote, battery-operated system which consistently responds to every event, and events can be triggered falsely, it's quite a simple matter to trigger false events until the battery goes dead, which you can be certain of in the first instance it fails to respond. A stochastic response is far harder to mess with: where the probability of response declines with the battery reserve. At what point does the adversary become entirely confident that the battery is dead?

Deterministic systems are far too sensitive to adversarial manipulation, and I never got the sense reading Con's own words that he has much appreciation for the adversarial nature of providing a balanced response in all scenarios.

Nor does it help much to split the scheduler. I can see it now. My rotations are slow! You idiot, use polar! My translations are slow! You idiot, use Cartesian! And the middle ground never gets solved.

There were instincts expressed from Con's side of the fence that left me uncomfortable. In any case, contribution should be measured in ideas, not lines of code.

I was especially puzzled by claims that Linus was covering up poor decisions in prior kernels in light of the improved algorithm since discovered. In my view the primary responsibility of a kernel maintainer is to never integrate code that won't converge on stability, where the exact nature of the stability offered is pragmatically redefined on a regular basis. If Linus ever had a need to cover something up, it was the VM fiasco, not the O(1) scheduler. The ego involved in suggesting that the aim of the Linux kernel developers is to never release a dominated algorithm (to fall back on game theory terminology) staggers the mind, an affiliative arrogance far beyond any allegation of arrogance personally leveled at Linus himself. I wonder if there has ever been a good thread on lkml concerning projected ego-creep.

Re:I find him rather rude

[Anonymous Coward]

Linus is from Finland, and speaks Finnish, but Swedish is his native language.

And I've heard him talk -- his English is idiomatically perfect, native, and indicates he's probably even thinking in it.

He's simply rude, and there's no making excuses for him.

Damn right the desktop experience is improved!

[Anonymous Coward]

You can be pretty damn right that the desktop experience is improved with Ingo Molnar's scheduler! If you have done any serious audio work on any platform you know that Linux kernel + Ingo Molnar's IO scheduler = the best platform for serious audio work. This combination has the lowest latencies. Linux kernel+Ingo Molnar's IO scheduler+Ardour offers currently lowest latencies and the best of all - it's completely free! It is pretty amazing - really. Every true professional audio engineer will agree with me.

Re:Damn right the desktop experience is improved!

[Blakey Rat]

But would it have been equally improved using Con's CFS? You aren't telling both sides of the story. (Which is fine, if you've only tried the one scheduler. But this topic is about the decision to use Ingo's rather than Con's.)

Why not both?

[rm999]

Why can't there be a flag that determines what scheduler is used at runtime, with both schedulers built into the kernel? I thought the whole point of Linux is that it is customizable and modular - I know this doesn't necessarily apply to the kernel, but why not?

I know very little about operating systems, schedulers, and maintaining large projects, so please excuse any ignorance in my post ;)

Re:RTFA and understand

[arth1]

As long as it's not anything like the CFQ IO elevator, which has turned out to slow down and increase critical latencies on every system I've tested it on, compared with deadline and anticipatory schedulers. This seems to be especially true for hard working (i.e. underpowered) systems, where the need for a good IO scheduler is higher.
I know, IO and job scheduling are two different things, but I still hope the "completely fair" naming part is coincidental, and not a promise of similarity.

Its the desktop stupid!

[bradbury]

Have you improved it to the point that when the system is borderline out of main memory or has a moderately high load average it actually *works* as a desktop system?

E.g. when Firefox is consuming 65-70% of main memory and slower than #%#$ and you know it is waiting on swapped out pages and your swap rate is measured in the dozens to hundreds rather than hundreds to thousands (on vmstat)? (I mean really, how can one take an operating system seriously when only memory is at 100% and not CPU + memory + Disk I/O?)

The real issue, for those who have read comments that Con has made in interviews, seems to be the lack of concern on the part of most of the "in-crowd" Linux developers for performance on the desktop. In part this seems driven by the fact that the people who actually get paid to maintain Linux, benchmark it and "improve" it only care about its performance in server farms and *not* on the individual desktop. I will weigh in on the side of desktop user out there (that wants the Linux sitting beneath their desk to devote its every waking minute to making *them* happy) by saying that if my mplayer "hangs" in the middle of a song (only to continue with a loud burst of noise 10 seconds later) when the CPU is busy with "nice -19" processes, my Firefox browser takes half a minute to scroll a page or open a screen) when memory is tight, and it takes minutes to bring up a tab or minimized program I haven't touched in 3 days and return them to a functional state then the operating system *Has a PROBLEM*.

Con was very clear in his interviews that the problem is the lack of caring about *desktop* performance. Given my comments in the previous paragraph -- some of these areas may be very difficult to benchmark and as a result one is left with nothing but handwaving and loud voices when it comes to discussions about whether the problem exists and how it should be fixed.

I will say this, in the mid-'90s I used X-windows under Unixware on *Pentium 1s* as a desktop machine. I now use X-windows under Linux on a Pentium 4 (with 5-10x more main memory) as a desktop machine. I would argue that my desktop user experience is as problematic now as it was then *despite* the hardware improvements. That IMO is what Con felt was the problem he was trying to address. That is what it would appear the core Linux developers may be failing to address. Con's points raised my awareness level to the extent that I actually went investigating to see whether there were open source distributions of the BeOS and/or Darwin (which is based on Mach) available since they are based on different OS architecture models and might be more end-user friendly [1]. I was hoping to find something I could run in a VM under Linux on my current hardware without major file system surgery. But I have little confidence that such an approach would fix core problems with the Linux scheduling and paging systems. I would *love* to see a real side-by-side comparison of Linux vs. FreeBSD for desktop users with an emphasis on how BSD scheduling, paging and swapping may be different (better?).

(And as a side note, I could care *zero* about the performance of Linux in file server applications!)

1. I did use both Nextstep (on Pentiums) and IRIX (on a R4000) for a while and found both to provide better end-user experience than Unixware (X) or Windows (95-98). I am disappointed that Linux barely manages to match those experiences given the hardware available nearly a decade later.

Re:Its the desktop stupid!

[TheRaven64]

I would *love* to see a real side-by-side comparison of Linux vs. FreeBSD for desktop users with an emphasis on how BSD scheduling, paging and swapping may be different FreeBSD currently has two schedulers:

• The old 4BSD scheduler has been tweaked a bit in the last decade, but is still fairly similar to the original. It is a high-throughput scheduler, which works well on servers and does okay on desktops.
• The newer ULE[1] scheduler is latency-focussed. It prioritises I/O-bound tasks and respects 'nice,' so is generally much better for desktop use, where a little throughput can be sacrificed for responsiveness.

I've been using ULE since the 5.x series, and it seems nice. It's been improved a lot since originally being integrated. It's hard to make a good benchmark for this kind of thing, because what you are really trying to optimise for is 'user experience.' The Windows scheduler has a trick where it prioritises the process owning the foreground window, hoping that the user's attention is on that window, so they get a perceived boost in responsiveness. Doing this on *NIX would require window manager cooperation.

[1] ULE doesn't stand for anything, it was just chosen so the option in the kernel config file for adding it would be SCHED_ULE (SCHED_4BSD for the other one).

Re:Linus, Games are important!

[miffo.swe]

1. Games run just perfectly on Linux with often better speed than in Windows. Every single game i has played in Linux has worked perfectly and smoothly. What Linux needs for gaming is more normal users who buys games. If there is a market someone will fill it quickly. I will also strongly refute that games are essential to desktops. There are infact people who use their computer to actually do something useful. 2. This decision has nothing to do with egos. This guy just happens to believe that its essential to speed up the kernel when the only slow apps in Linux are non-native apps like Java, OpenOffice or Firefox. Those are not slow because of any sheduler but because they are written with slow toolchains. More work on making the kernel more responsive wont help at all at this stage.

Re:"aimed at improving the desktop experience"

[Anonymous Coward]

Linus slightly disagrees. From TFA:

People are suggesting that you'd have a separate "desktop kernel". That's
insane. It also shows total ignorance of maintainership, and reality. And
I bet most of the people there haven't tested _either_ scheduler, they
just like making statements.

The fact is, I've _always_ considered the desktop to be the most important
part. And I suspect that that actually is true for most kernel developers,
because quite frankly, that's what 99% of them ends up using. If a kernel
developer uses Windows for his day-to-day work, I sure as hell wouldn't
want to have him developing Linux. That has nothing to do with anything
anti-windows: but the whole "eat your own dogfood" is a very fundamental
thing, and somebody who doesn't do that shouldn't be allowed to be even
_close_ to a compiler!

[emphasis mine]

I'm gonna have to go with Linus on this one.

Re:RTFA and understand

[wellingj]

You should realize that CFS was built around the -rt patch
The -rt patch will:

• Make latencies deterministic
• Reduce latencies if used correctly
• Add slight over head to overall througput

I think once the -rt patch is merged into the mainline it will work wonders
for games and all sorts of other important things, like industrial automation,
automated stock trading, and other high-speed data acquisition and processing.
So there is a road map to improve scheduling. In fact it's actually a broader and
more appealing plan than just scheduling for the desktop, IMHO. I think this is what
Linus is trying to get at in terms of his why he doesn't want a perfect desktop scheduler.

Excuse me?

[deblau]

one of the main reasons that I never ended entertaining the notion of merging SD for very long at all: Con ended up arguing against people who reported problems, rather than trying to work with them.

OK, Linus doesn't like people who don't play well with others.

instead of keeping to your isolated world, instead of just talking about your own machine and ignoring other peoples machines and issues and instead of just denying that problems may exist, and instead of attacking people who report problems, how about working with them?

OK, he really doesn't like people who don't play well with others. We get it.

If a kernel developer uses Windows for his day-to-day work, I sure as hell wouldn't want to have him developing Linux. That has nothing to do with anything anti-windows: but the whole "eat your own dogfood" is a very fundamental thing, and somebody who doesn't do that shouldn't be allowed to be even _close_ to a compiler!

Wait, what? Now who's not playing well with others? My hypocrisy meter just pegged.

And what's with the massive ego? It's as if suddenly Linus thinks he invented compilers or something. I think he needs to take a vacation and regain some perspective.

CDDL is designed to be GPL incompatible

[eean]

The CDDL was designed to be GPL incompatible, Solaris didn't want its crown jewels to be in Linux.

Re:Linus as the benevolent dictator again

[schon]

Con never claimed SD was perfect. Care to share with the group where exactly Linus says he did? You use the words "utter shit" - seems that it's something you know a lot about. Or do you enjoy building straw men?

it's quite disgusting to see Linus make such sweeping statements to the contrary. Sadly, since Linus' word is gospel - even if he is speaking utter shit Funny, I read the email exchange, and I can't see *anyone* telling Linus that he's speaking "utter shit" - So why is it that if Linus is (as you claim) lying through his teeth about events that happened, that nobody calls him on it?

Linus pointed out problems with Con dismissing other people's problems, and nobody says "oh, that didn't happen" - except you. In fact, the general response was "well, that didn't happen very often."

Similarly, even people who are attacking Linus say that Ingo acted the way Linus says he acted in the same situation - in other words the main reason Linus rejected SD is confirmed by the very people who are arguing for SD.

then Con will get publicly slammed by people like you who think it's fine to comment on what they don't know about So it's OK for you to do it about Linus, but it's not OK for someone to do it about Con? Somehow the words "Pot. Kettle. Black." come to mind.

Re:Linus, Games are important!

[pakar]

Ehmm... I'm not a 'gamer'.. Maybe once every 2 months or so if i don't have anything better to do... But most people i know below 30 are playing games, and without having good support for that in gnu/linux they will never switch away from windows.

The problem the linux distributions have today is that they have a bad reputation that scares people away and this scares people away from it.. (remember that all unknowns are scary for most people)

Now back to the topic... First of all i do want to say that i have not had the chance to try the CFS scheduler yet, but the thing here is that the SD scheduler where great on lots of other tasks too. With the plain O1 scheduler i had lots of problems when playing video-streams during high-cpu load,and the issue was that the scheduler gave background-jobs to large timeslices that cause the player to skip frames and such. With the SD scheduler there where some really nice things you could do then too, like setting the background-jobs to SCHED_ISO that caused the process ONLY to use unused cpu-time and this worked great. Could have 5-6 gcc's loading the cpu without even a frame dropped and did try out a opengl game (enemyterritory) during compilations just to see how it worked, and no problems there either.. Then after switching back to the O1 scheduler i could not even have 2-3 gcc's running without loosing LOTS of frames, and did not even bother with trying out a game..

So you see, games are just a part of it.. All types of lowlatency applications like video, music, games and some daemons like nfsd and such needs a good scheduler to give the best performance/interactivity.

I think i'm gonna give the CFS scheduler a try during the week, but i dont have any high hopes after what people have reported about it yet. And i do think it would be a better idea to implement multiple schedulers that you could choose between instead of having 'one size fits all'.

Re:Linus as the benevolent dictator again

[Anonymous Coward]

To make matters worse, some quotes (of Linus) from TFA:

So if you are going to have issues with the scheduler, which one do you pick: the one where the maintainer has shown that he can maintain schedulers for years, can can address problems from _different_ areas of life? Or the one where the maintainer argues against people who report problems, and is fixated on one single load?

He actually has the audacity to argue Con wasn't able to "maintain a scheduler for years" when that's exactly what he had done - outside mainline. Ingo's old scheduler was a real mess because it was hack after hack stacked on top of another. If anything, Ingo's the one who couldn't properly maintain a scheduler (perhaps because he was to lenient and didn't defend the integrity of it's design). He then continues:

That's really what it boils down to. I was actually planning to merge CK for a while. The _code_ didn't faze me.

If the code didn't bother him and a double-blind test showed CFS and SD were equal in performance, then WHY go with the rushed implementation of CFS instead of the mature SD which had been in development for years? Oh yeah, and it's easy to say he "was actually planning to merge CK for a while" now, aint' it? Damage control anyone? He stabbed Con in the back, plain and simple. Con had been working on SD for a long, long time and Ingo (like you pointed out) used that work to make his own implementation in - what was it, 62 hours? - which made him look like a rock star by comparison. Linus the proceeds to flush Con down the toilet and pats Ingo on the back for a job well done. Linus is being a prick, and sooner or later people will stop making excuses on his behalf just like they did Google.

This sort of crap really pisses me off.

Re:Nerds

[MrHanky]

I don't disagree that a story about the scheduler is potentially interesting, and that it's what Slashdot used to be about. But as you can see from the above comments, it's not exactly stuff that "nerds" these days care to Google when they don't understand what it's about. Personally, I started reading this site because I ran (and run) Linux, not the other way around. So I've got nothing against this particular story, even though most of the discussion is very poor, and, sadly, typical for this site.

That said, I do disagree that Slashdot has ever been a science site. There's a lot more to science than what interests the nerd crowds (the proper nerd crowds, not the Apple fanboys and gadget freaks, who could care less about how stuff works). Science, as it concerns Slashdot, is mainly science that concerns technology. Throw in a few dinosaurs and volcanoes for good measure. It's boys' stuff. Science fiction stuff. You won't find anything about the travel patterns of herring or anything that takes the social sciences seriously (plenty of people here would even claim "it's not science", demonstrating their own lack of insight into what the scientific method(s) constitute).

Re:Linus as the benevolent dictator again

[FreeGamer]

OMG people even have to steal comments these days?

I wrote this comment on kerneltrap.

Christ, that's incredible. Nice one "bconway".

Re:Linus's double standard: a historical perspecti

[paleshadows]

But did you read Con's messages sent to the LKML (rather than just those sent to Con's private ML)?

Not all of them, but many.

Con really did get quite whiny and argumentative at times, in bad ways. He seemed to be prone to taking criticism from certain people much too personally when he should have just focused on discussing the technical issues.

I disagree. I felt his comments were usually to the point, even though towards the end you could feel his more emotional. But see more on this below.

I do have sympathy for Con, but I also believe he could have helped his cause a lot by growing a thicker skin. The Linux kernel community has had problems in the past with subsystem maintainers who were drama queens. Richard Gooch and Andre the IDE guy come to mind. It's not too surprising that core kernel developers react negatively to similar behavior, even if it's much milder than the examples I gave.

My read is different, but it'll take a few paragraphs to explain why, so please bare with me. The O(1) so called "improved interactivity" was just a hack upon a hack upon a hack that never worked. If you ever read the code you know what I'm talking about. It was a complete mess. The mess was the result of trying to obtain a goal that is unobtainable: very roughly speaking, Ingo (and others) believed that it is possible to deduce how "important" a process is, based on the frequency of the process' sleep events (not the duration of the sleep). I can point you to a few research papers that show that this can simply *not* be done. Briefly, it has been shown that for each "important" application you can find an "unimportant" application such that the CPU usage pattern of the two is very similar; Hence, you would never be able to distinguish the important from the unimportant (if you are only basing you decision on CPU usage). All you can do is (1) divide the CPU equally, and (2) provide good response time to applications that sleep for long periods of time (like editors). According to several of his emails, Ingo is not reading scheduling papers, and proud of it.

I suspect Con doesn't read such papers either. But he knew this is the case nevertheless. For years Ingo and his followers attacked Con on this. Note that this is a purely technical issue, and Con was *completely* right, e.g. take a look at CFS, or at Linus's original scheduler that lasted until 2.2, or, Solaris, *BSD (with the exception of ULE), HPUX, etc. They are all much closer to the SD's philosophy than to the O(1)'s. (BTW, the only other OS that tried to do what Ingo wanted is... the Windows family).

The discussion between Con and others regarding this issue was not about minor details. Ingo and his followers view towards Con was plain and simple: "your design is crap, it doesn't do what schedulers are supposed to do". Con resisted. And I agree, after years in the business, he was occasionally emotional about it. But this is really understandable and reasonable. Especially when you compare it to the way Ingo and Linus express themselves from time to time (talk about "drama queens"). For example, notice how Linus talks to Ingo when Ingo doesn't understand something immediately.

The bottom line is that most of them are "drama queens" from time to time. Nobody is perfect. In absolute terms, however, I think Con usually expresses himself in a calm, quiet, and relatively humble manner. Certainly in comparison to Ingo/Linus.

Re:Linus as the benevolent dictator again

[James Lewis]

Out of curiosity, were there ever any benchmarks between the two schedulers, or is their comparison completely theoretical? And why does it matter if Con can maintain it or not? Why couldn't Ingo maintain Con's scheduler? He's getting paid right?