Linux: Completely Fair Scheduler Merged

Submitted by Jeremy
on July 10, 2007 - 12:02pm

Ingo Molnar [interview]'s Completely Fair Scheduler [story] has been merged into the Linux kernel for inclusion in the upcoming 2.6.23 release. A comment in the patch titled 'sched: cfs core code' noted, "apply the CFS core code. This change switches over the scheduler core to CFS's modular design and makes use of kernel/sched_fair/rt/idletask.c to implement Linux's scheduling policies." Another patch included documentation which described the new scheduler, "80% of CFS's design can be summed up in a single sentence: CFS basically models an 'ideal, precise multi-tasking CPU' on real hardware." It goes on to explain:

"CFS's task picking logic is based on this p->wait_runtime value and it is thus very simple: it always tries to run the task with the largest p->wait_runtime value. In other words, CFS tries to run the task with the 'gravest need' for more CPU time. So CFS always tries to split up CPU time between runnable tasks as close to 'ideal multitasking hardware' as possible.

"Most of the rest of CFS's design just falls out of this really simple concept, with a few add-on embellishments like nice levels, multiprocessing and various algorithm variants to recognize sleepers."

Credit was given to four developers other than Ingo Molnar: "Con Kolivas, for pioneering the fair-scheduling approach [story]; Peter Williams, for smpnice; Mike Galbraith, for interactivity tuning of CFS, Srivatsa Vaddagiri, for group scheduling enhancements [story]".

The CFS scheduler replaces Ingo's own O(1) scheduler which was first proposed on January 3rd, 2002 [story], and merged into the 2.5.2-pre10 kernel a few days later, on January 8th [story].

Imho CFS is much better than

SlashBeast (not verified)
on
July 10, 2007 - 12:45pm

Imho CFS is much better than standard linux scheduler and SD.

Bastards!!! How can you say

Anonymous (not verified)
on
July 10, 2007 - 2:47pm

Bastards!!! How can you say that?! Have you really tryied both schedulers?! I guess not. CFS it's aproaching SD. SD it's stable and behaves better since the beginning.

CK rules! (Technical merit). CFS it's only being merged because Ingo has 'good friends'.

CFS isn't really fair

Adam Petaccia (not verified)
on
July 10, 2007 - 7:30pm

As much as I try to stay out of fanboyism, I have a feeling you're right. Con has been working on his scheduler for a good while, and in the open, and regularly outperforms / out"fair"s CFS and CFS got on the fast track to getting merged, while SD barely got considered.

Apparently, Con is getting out of the kernel business for a while, and I can't blame him. After regularly getting technically ahead, he just gets pushed further behind in the merge queue.

Am I the only one that sees the irony in the Completely Fair Scheduler not getting merged in a completely fair way?

CFS vs SD

pomac (not verified)
on
July 11, 2007 - 2:30am

All i can say from using both is that i think that Con aimed it a little bit too much towards fairness...

A computer only has limited amounts of cpu and if you are really 'fair' then you still starve things but it's more noticeable for the user.

I tried SD, played around with it and liked it until i started a compile or used something else that required CPU. The slow down is not something you'd expect and feels damn odd quite frankly. As someone who started playing with unix schedulers and different approaches to 'fair' cpu usage (as a user) with executive on the amiga i have to say that i wonder if it was smart to be that fair.

CFS actually seems to be doing a better job, even though i hate to admit it...
Con has done many great things and it's because of him that we get a new scheduler but, from a unbiased user perspective, CFS is the way to go =P.

I hope that he keeps hacking and that his swap prefetch and other patches gets merged in to mainline soon!

PS. And yes, it felt a bit like nepotism.
DS.

Too much fairness.. lol

Anonymous (not verified)
on
July 11, 2007 - 4:45am

Too much fairness.. and you say the response it's odd... It's responsive -- you are not used to that with the traditional and the cfs scheduler.

"Too much fairness", lol. Thanks for sharing that joke, fanboy.

*sigh*

pomac (not verified)
on
July 11, 2007 - 5:17am

And here i thought i was clear.

You're most definetly not used to the fact that SD slows down EVERYTHING in relation to the number of processes and cpu usage.

It, on a 3800+ amd64, becomes slower than my 50mhz 030 amiga using just about any scheduler in executive.

A sheduler is supposed to be fair, but not everyone gets a run / go since thats not what you expect or how you want it to work. Heck even Con aknoledged this by adding the deadline.

Yeah, yeah, i know, don't feed the trolls... but, being called fanboy when you really DID test it all and came to a conclusion is not fun even if it's by a uninformed troll.

Sure, you're not being

Anonymous (not verified)
on
July 11, 2007 - 10:37am

Sure, you're not being fanboy.
Your AMD64 just behave different than the ones i've tested.
Even different from the Intels where i also tested (sd+cfs+mainline).

After all i just tested several different machines with the different schedulers. Don't feed the trolls.

How in the world could any

Anonymous (not verified)
on
July 11, 2007 - 11:26am

How in the world could any of you imagine that the machine is the important part here?

It's the difference in workloads that is important here.

Yes,I too felt Con Kolivas

Prakash J K (not verified)
on
July 12, 2007 - 5:13am

Yes,I too felt Con Kolivas was purposefully set back by Linus & Co.-I have to say that alas.hrmm..

Except, it's not.

Anonymous (not verified)
on
July 10, 2007 - 8:20pm

Except, it's not.

fJHlstC

on
May 3, 2011 - 9:33pm

exbLRk fJHlstC

Why should I care about CFS?

Fred Flinta (not verified)
on
July 10, 2007 - 4:10pm

I am a new novice computer user.
Why should I care about Linux getting this CFS?
How will it benefit me?

Because its fair!

Adam Petaccia (not verified)
on
July 10, 2007 - 7:35pm

Quite frankly, because its completely fair.

I'll try to demonstrate with an example: It means that (if I understand correctly) that if you have an "evil" process that insists on consuming all the processing resources your computer has, it wont be too successful, as it will be forced to share those resources with all the other programs that want the processor, meaning you should still be able to work. (Think compiling a large program while still using your desktop, for example).

Basically for the everyday user: your system is less likely to get starved, and slow to a crawl than before. Not that it was bad before, but now its even less likely to happen.

Even better, CFS is in many

jospoortvliet (not verified)
on
July 11, 2007 - 4:03am

Even better, CFS is in many cases more responsive than the current CPU scheduler, and might also lead to a (slightly) higher throughput (=performance).

So, more stable, higher performance and faster response times are the reasons why CFS is good for you. (I won't comment here on the whole CFS/SD issue, enough has been said already)

Wtf.com are you doing

Anonymous (not verified)
on
July 11, 2007 - 3:25am

Wtf.com are you doing reading kerneltrap then?

Hahaha *zing*

Anonymous (not verified)
on
July 11, 2007 - 8:41am

Hahaha *zing*

**eyeroll**

on
July 11, 2007 - 9:37am

Here comes Slashdot....

Too bad Con has been kicked

Anonymous (not verified)
on
July 10, 2007 - 6:26pm

Too bad Con has been kicked away.
I see we have kernel mafia too.

What mafia are you talking about?

amirm (not verified)
on
July 10, 2007 - 10:10pm

They can't accept just about every patch, they are picky - and thats the way it should be.

They can't accept just about every patch, they are picky - and t

Anonymous (not verified)
on
July 11, 2007 - 9:24am

Like ext4? Ready for production?

They're not even comparable

on
July 13, 2007 - 1:06am

The difference is that ext4 sits alongside ext3 and ext2 so only those that want to use it will be affected. The way the scheduler was merged it replaced the old one so everyone is affected. If they had implemented pluggable CPU schedulers like they did with the I/O elevators it wouldn't be a big deal but for some reason Linus doesn't like that idea.

kernel owners picky based on "good ole kernel-boy network"?

Anonymous (not verified)
on
July 11, 2007 - 1:34pm

Should kernel owners be picky based on personal favoritism or on "merit"? Bush is picky as well -- I doubt that anyone would argue that his picks are based on merit.

I've got it running since a few hours

krassesauto (not verified)
on
July 10, 2007 - 10:08pm

and its causing hickups everywhere :(

Maybe it needs some more time to shake out the bugs, but well, they've still got 8 weeks till release.

regards
http://krasses-auto.de/

Have noticed the same

Amirm (not verified)
on
July 10, 2007 - 10:15pm

Under heavy load it seems to freeze the machine for a half a second.

Ingo Molnar is the worst

Anonymous (not verified)
on
July 10, 2007 - 11:03pm

Ingo Molnar is the worst kind of loser: an attention whore. His O(1) scheduler turned out to be a piece of crap and Con Kolivas spent a considerable amount of time implementing a better solution: Staircase Deadline (SD). The SD scheduler is a well tested, good performing scheduler and just when you think its going to be merged into Linus' kernel and replace Ingo's O(1) turd (and remove Ingo's name from some "important" files), Igno spends a couple of days reimplementing SD. I guess he wont be getting his name deleted after all!

This shows the black side of open source. Con developed SD in the open and Igno stole his ideas. It was only after people started pointing out that CFS looked _very_ similar to SD that Igno admitted that the design was based on Con's SD work.

The only reason CFS is in the kernel and not SD is politics.

Don't want to get involved

Anonymous (not verified)
on
July 11, 2007 - 1:53am

Don't want to get involved in the flamewars. However, what you write regarding Ingo not giving credits to Con in the first run is just plain wrong. See: http://kerneltrap.org/node/8059

so like, why didn't Ingo

Anonymous (not verified)
on
July 11, 2007 - 3:30am

so like, why didn't Ingo work with Con to improve the
existing SD codebase instead of writing his own from scratch
at the last minute?

Maybe because he didn't want

Anonymous (not verified)
on
July 11, 2007 - 7:57am

Maybe because he didn't want to start from a bloatbomb?

Why are we all acting like

Anonymous (not verified)
on
July 11, 2007 - 3:47pm

Why are we all acting like children at an elementary school?

Almost slanderous

Wynand Winterbach (not verified)
on
July 11, 2007 - 6:29am

You only have the courage to be so base in your criticism because you are anonymous.

Not every choice made by a manager (Linus in this case) is malicious, even if it seems so to you. Sometimes, "politics" translates into "I know this guy better". And since people are often forced to make decisions in the midst of uncertainty, they often choose the road with more certainty.

To call a piece of software which has worked, a "turd", is childish at best. I've been using that "turd" for a long time and it works for me. You forget that "turds" are part of the evolution of anything. Would you call Aristotelian physics "turd physics" because it turned out not to quite right?

I do think it's a shame that Con's work didn't get into the kernel. It really is. But there's no need to insult Ingo.

Don't be such a coward man! If you are going to make strong statements about people, use your real name.

And i had the strange idea

Anonymous (not verified)
on
July 11, 2007 - 10:46am

And i had the strange idea that Linux was all about the best solutions and not friends and deals.

I can't talk about others but i don't insult Ingo (i believe he's an important person on kernel development and i respect him much), but i don't understand why he copied Con's idea/implementation instead of contributing.

Somehow doesn't feel ethical.
If the opposite happened, have no doubts, everyone stood by Ingo.

Let's not talk a about Linus's decision. Have he really tested both schedulers, compared code, measured negative/positive feedback from others beside the author? Are you sure? Are you really sure?

Read Fredrick Brooks

on
July 11, 2007 - 11:22am

I can't talk about others but i don't insult Ingo (i believe he's an important person on kernel development and i respect him much), but i don't understand why he copied Con's idea/implementation instead of contributing.

Fredrick Brooks once said, "[P]lan to throw one away; you will, anyhow." You can look on Con's SD as the prototype from which Ingo took several good ideas to make his version.

Whether that's actually the case, I don't know. But, it's one plausible way of thinking about it.

The older linux scheduler

Anonymous (not verified)
on
July 11, 2007 - 12:49am

The older linux scheduler since 2.3 kernels is buggy and i
burnt 4 motherboards as i said, so it really pisses me off to see
that a correct module takes so much christian time to be
included in the nucleus

Are you saying that the old

Anonymous (not verified)
on
July 11, 2007 - 1:21am

Are you saying that the old Linux scheduler burnt your motherboard? Heh

A sheduler is supposed to be

silver (not verified)
on
March 24, 2008 - 11:22am

A sheduler is supposed to be fair, but not everyone gets a run / go since thats not what you expect or how you want it to work. Heck even Con aknoledged this by adding the deadline.

Haha.

Anonymous (not verified)
on
July 11, 2007 - 9:26am

Haha.

como se what?

Anonymous (not verified)
on
July 12, 2007 - 4:05am

Nucleus? Did you just install z/OS? Haven't we gotten rid of mainframes yet? lol

rbtree vs heap

Anonymous (not verified)
on
July 11, 2007 - 1:13am

If the operations needed used for the rbtree are insert and remove leftmost node, why use a rbtree when a (binary) heap would be much cheaper? (in terms of memory use and constant factor in performance)

Completely Fair Scheduler

Anonymous (not verified)
on
July 11, 2007 - 2:56am

While I have not been testing any of the new schedulers, I have been following the discussions and tests on LKML. From my outside observations of those discussions and tests I concluded that the SD scheduler is outperforming CFS. So I am very supprised that CFS is merged instead of SD.

Surprised, why?

Anonymous (not verified)
on
July 11, 2007 - 4:43am

Surprised, why?

The SD it's just the scheduler who 'revolutioned' the behavior of the Linux kernel to the users, it's the new concept. It's also the one tested for most people and for most time without reports of 'this shit under this condition_nn sucks', the implementation it's clean and stable for months.

Of course it's not a rip-off with bad behavior with lots of corrections on the last month and the author it's not employed by red hat...

Why are you surprised???

Completely Fair Scheduler not susceptible to user-mode priv?

Anonymous (not verified)
on
July 11, 2007 - 12:12pm

Note the part about the fact that the CFS is (supposedly) not susceptible to the same attacks as SD and the O(1) scheduler.

That was discussed in another KernelTrap post here, as was suggested on slashdot.

Anyway having fair per-user

Ivan Tikhonov (not verified)
on
July 11, 2007 - 5:26am

Anyway having fair per-user sheduler will be much better. Linux suck for shared hosting without it.

It does remind me

Anonymous (not verified)
on
July 11, 2007 - 5:39am

The whole issue does somehow remind me of Reiser4 and Ext4.

Essentially Con FAILED IT

Anonymous (not verified)
on
July 11, 2007 - 6:31am

Con makes himself look like a baby. He provides a framework but doesn't provide any good implementations and even worse his framework is a lie. It was a good start but it didn't go far enough like how Ingo described. Con's idea of the fair scheduler was not his. That is baloney. Also the only value of anything Con did was to push for a better API to allow developers in. Linux and many open source projects keep valuable contributions out.

LIBC keeps researchers out. They don't allow in more effecient algorithms and instead opt for O(N^2) string search algorithms.

GCC up until recently made it impossible for code optimization research to be used. GCC and RMS stopped researchers from modularizing GCC to allow analysis plugins etc.

Linux makes it very hard architecturally for any good idea to be implemented.

Also a fair scheduler is NOT any one of these idiots ideas. It is a very old OS research idea and there are billions of papers about fair scheduling. None of the kernel developers here care because they never read research and only care about tiny shit hacks. The big picture is a nuisance, just ignore it all together. Go ahead and flame the researchers but these are guys who are provably valuable work which if more devs would pick up would greatly increase the performance of the kernel. Too bad most OSS hackers just lack the background necessary to even "GET IT".

Impossible

Sere (not verified)
on
July 11, 2007 - 7:42am

I think that achieving the _perfect_ CPU scheduler is _impossible_. How should a piece of software (no matter by whom it was written/stolen/whatever) know what the user wants? I mean, if the PC could read my mind, it would know that right now I feel like using my mous in the application SOandSO and in the background it should run ThisandThat and the scheduler would ignore all the unneeded. That is not the case so we just say that fair is a modification of the round-robinson-model. We can do 10000000x mods of it, but we cant get anywhere near perfection because of the reasons above. I have used CFS and didnt feel anything had improved or deteriorated. I might try SD, I my not. I trust that the devs will give the user what they think is best. If it aint, there alway is the next release to try again.

Get it over with, call him a whiner

Anonymous (not verified)
on
July 11, 2007 - 10:47am

I think you should have called him a whiner. That is the typical kernel team reply when they have no other meaningful reponse to a legitimate gripe. Or perhaps you should just say, "he doesn't understand."

Research is not about production-quality implementations

on
July 11, 2007 - 5:50pm

Your point of view is the one of a researcher, but for a developer it's a different story.

About libc, Ulrich Drepper is widely known to be difficult to work with - not only for researchers, also for open-source developers.
The fact that he rejects OpenBSD strlcpy() since 'programmers should write correct software' (and care for strncpy problems) is a proof of this (btw, Linux kernel has an implementation of strlcpy() API for internal usage, because of its various simplicity and performance advantages).

> Linux makes it very hard architecturally for any good idea to be implemented.
Well, Linux has not the cleanest design out here; in part that's just because of old code nobody cleaned up (it is clear that the current API for page tables, bound to the i386 tree structure, is a bad API - just nobody has succeeded in cleaning it up yet).

However, in many other case the problem are just that Linux is difficult because of optimizations and tuning, and sometimes optimizations require reducing modularity.

Also, researchers are valued for the papers they write and ideas they have, not for the performance they get. Most articles talk about unpublished implementations. Also, can you tell me how many of those scheduling papers were tested with a real-world kernel running a real compiler on it, and how many of those implementations are available to be benchmarked? (Btw, Minix is not a real-world kernel - its performance is too bad, so it's just a research prototype). Every published scheduler can give some wonderful benchmark, the problem is having little regressions in real-world usage (and well, scheduling is known to be hard - NP-complete IIRC - so an algorithm is almost bound to be worse than another in some case). So, those papers didn't prove a lot about real-world performance of fair-scheduling - Con's implementation did prove it in practice, compared to Ingo's O(1) scheduler.

Finally, Ingo Molnar's lockdep work is really a piece of original research art (and a wonderful idea). Even though he doesn't care at all about publishing an article on it. And it's not true that Linux developers ignore research - Rik van Riel for instance is very careful to academic research.

About the other issue (Con's credit and politics): rewriting a software is not a way to steal merit from other people; Ingo started from very different basic ideas, and his new scheduler is more different from his own O(1) than SD itself.

PS: you've already published exactly this comment on a related article (http://kerneltrap.org/node/8059#comment-232890), this is strange IMHO.

PS: you've already published

georg_H (not verified)
on
July 13, 2007 - 2:04pm

PS: you've already published exactly this comment on a related article

Thanks. I was getting a sense of "Dejà-Vu" so bad I had to verify the comment date and the current date three times while reading it.

Deja Vu ?

Sum Juan (not verified)
on
July 30, 2007 - 3:30am

This wouldn't been some sort of repackaged retorical smear capaign would it. Cause if not you really need to find something more original to come up with after 4 months.

Cronyism is alive and well on the kernel team

Anonymous (not verified)
on
July 11, 2007 - 7:42am

The Free Software ideal encourages the free flow of ideas in the academic tradition. But Molnar has used his priviledged position jealously stonewall Con Kolivas's work and reimplement it, all to call more glory to himself. Nice try asshole. The situation reminds me of the Russian mathematician Perelman who solved the Poicare Conjecture the and the botched attempt by the unscrupulous mathematician Lau to reimplement his ideas and claim the proof as his own. Molnar's attribution Kolivas's ideas is not enough. If he were a real lead he would help patch up Kolivas's work and get it into the kernel.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Warning: Duplicate entry '2147483643' for key 1 query: INSERT INTO accesslog (title, path, url, hostname, uid, sid, timer, timestamp) values('', 'node/11737', '', '207.241.237.214', 0, '1fa0636ca2a9f184bc0500ad9174f4f0', 102, 1328576822) in /var/www/localhost/kerneltrap/includes/database.mysql.inc on line 128