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
Imho CFS is much better than standard linux scheduler and SD.
Bastards!!! How can you say
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
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
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
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*
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
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
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
Yes,I too felt Con Kolivas was purposefully set back by Linus & Co.-I have to say that alas.hrmm..
Except, it's not.
Except, it's not.
Why should I care about CFS?
I am a new novice computer user.
Why should I care about Linux getting this CFS?
How will it benefit me?
Because its fair!
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
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
Wtf.com are you doing reading kerneltrap then?
Hahaha *zing*
Hahaha *zing*
**eyeroll**
Here comes Slashdot....
Too bad Con has been kicked
Too bad Con has been kicked away.
I see we have kernel mafia too.
What mafia are you talking about?
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
Like ext4? Ready for production?
They're not even comparable
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"?
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
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
Under heavy load it seems to freeze the machine for a half a second.
Ingo Molnar is the worst
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
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
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
Maybe because he didn't want to start from a bloatbomb?
Why are we all acting like
Why are we all acting like children at an elementary school?
Almost slanderous
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
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
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
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
Are you saying that the old Linux scheduler burnt your motherboard? Heh
A sheduler is supposed to be
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.
Haha.
como se what?
Nucleus? Did you just install z/OS? Haven't we gotten rid of mainframes yet? lol
rbtree vs heap
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
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?
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?
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
Anyway having fair per-user sheduler will be much better. Linux suck for shared hosting without it.
It does remind me
The whole issue does somehow remind me of Reiser4 and Ext4.
Essentially Con FAILED IT
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
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
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
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
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 ?
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
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.
The Corleone word comes to
The Corleone word comes to my mind...