Digg - What is the Completely Fair Scheduler? (via Mowser)

Discover the best of the web!
Learn more about Digg by taking the tour.

What is the Completely Fair Scheduler?

immike.net — A pretty detailed explanation about whats up with the upcoming 2.6.23 Linux kernel release.

Bury

Favorite?

bedoyle 353 days ago, made popular 352 days ago

471 diggs digg it

49 Comments Who Dugg It? Blog It Email It

Dougman82, on 10/10/2007, -7/+2Hmmm... 20 diggs and 0 comments later, site down.

mmalone, on 10/10/2007, -0/+9Eh. It's not from this... and it should be up now. Another article on the site is on Digg, and the same article just hit del.icio.us front page. Been serving like 20 requests/sec all day. Tons of comments => tons of cache invalidations => server slowdown.

Try now and it should be all good.

Dougman82, on 10/10/2007, -1/+6Sweet, got through. Actually a very interesting article. I was wondering what was behind the new CFS scheduler.

geminitojanus, on 10/10/2007, -0/+8The article both over-complicates what's going on, and fails to explain some fairly simple-to-know facts.

First of all, CFS is still a O(1) scheduler, all context switches happen in constant time. All that CFS improves on is the precision of switches; before, the scheduler uses ticks and there are some odd conditions where a process can use a huge amount of CPU time, without ever being taxed for it (for example, if the process enters on the tick but leaves before the tick, it's not charged for the amount of processing time that happened within the tick.

With CFS, we get rid of "Jiffies", "time slices" and "Hz time", and we just do it on raw nanosecond-time. It's "Completely Fair", because it keeps a journal of exactly how long each process has the CPU, and balances that time out amongst processes evenly. We have a billion nanoseconds in a second, with one process running, it gets the whole billion nanoseconds, with two, each process gets half a billion (minus a few nanoseconds used for each context switch), and so on and so forth. This is nothing but an optimization of the previous scheduling algorithm. [For those who are interested, "nice" still works by calculating exact runtime, adjusted for the process's nice level, ahead of time as part of the scheduler's overhead and is even more precise than before.] myfanwy, on 10/10/2007, -1/+3hmm, CFS scheduler; is that a case of redundant RAS syndrome? mmalone, on 10/10/2007, -0/+3@geminitojanus: my understanding is that CFS is O(log n), not O(1), since it uses a red-black tree to organize processes and selects the leftmost node for execution. Search time on an rbtree is O(log n). Am I missing something?

There are other differences from the current O(1) scheduler too. For example, CFS doesn't do any interactive process identification. And with CFS the time quantum is more variable than with the current scheduler since they're partially determined by the amount of CPU time other processes on the box are using. I wouldn't call CFS "nothing but an optimization."

myfanwy, on 10/10/2007, -0/+1bugger, wrong place

OneAndOnlySnob, on 10/10/2007, -1/+1209 diggs and 31 comments later, site up. Hmm indeed.

nontitle, on 10/10/2007, -1/+4This seems pretty cool, hopefully it lets me play Nexuiz faster than before.

mmalone, on 10/10/2007, -0/+8You might also be interested in The Kernel Trap's article discussing CFS's impact on games. It's at: http://kerneltrap.org/node/14023

There are also some interesting comments in the discussion thread on Slashdot at http://linux.slashdot.org/article.pl?sid=07/07/31/1457207&from=rss

serend, on 10/10/2007, -4/+3I still think that CK's Staircase / Deadline scheduler was and is better.. Too bad CK had to go out on a limb and cause some drama.

YourDoom123, on 10/10/2007, -2/+2isn't Deadline an IO scheduler? this is talking about the cpu scheduler which was never revealed in the kernel options menu: there's only one.

Urusai, on 10/10/2007, -0/+3The difference between the CPU and IO schedulers isn't hardly covered. Really, the IO scheduler is what sucks in Linux. Try copying a big file in the background and watch your desktop stutter and freeze.

DrDabbles, on 10/10/2007, -1/+4If you don't know what you're talking about, don't speak. To say it's the IO scheduler is to do a disservice to the topic. The IO sched. needs more work, though CFS does a good enough job as does deadline, but the IO scheduler is showing age. The CPU scheduler known as CFS tries to simplify scheduling, thus lowering overhead and theoretically increasing interactivity and process responsiveness without sacrificing actual processing performance.

The problem CK has always had with his patches is that he thinks one way and starts off running. When his staircase scheduler first came out (This predates the 2.6 kernel...I tested it in embedded network devices I was developing at the time), it sucked BADLY for a system under any real load. It worked great for a desktop running a web browser, but do any actual processing and watch out. His other patches introduce stability issues and break compatibility in many cases. This is also why resiser4 has not been adopted to mainline vanilla kernel.

For a good dose of reality, and a history lesson...go read kerneltrap XVampireX, on 10/10/2007, -0/+1DrDabbles is right, It's a great thing to have at least a few people who are less into hacking the kernel but more into how it works :)
I'm a big fan of kerneltrap, read it every week, and sometimes even several days a week.

shethinkmefunny, on 10/10/2007, -0/+1I have yet to play with either scheduler, but I've tried a few kernels with the -ck patches, and while it makes standard usage seem snappier, it has a few show stopping trade-offs, specifically multitasking during large file transfers. With the standard kernel, transferring 100 GB of data from one drive to another (separate SATA drives on different channels in my case) will slow the system somewhat, but not enough to be a real hindrance. With the -ck patched kernel, that same 100 GB transfer makes all my running applications cease to respond, albeit with up to 15% faster file transfer speeds. It's irritating, to say the least, to see my hyperthreaded 3.4GHz machine with 2 gigs of RAM all but lock up during a large file transfer.

If his coding style carried over to his scheduler, I would be more inclined to go with the CFS, as everything I've read suggests that while it's not particularly stellar in any one area, it's very competent across a very broad spectrum of usage scenarios.

XVampireX, on 10/10/2007, -0/+1IO Scheduling always needs to be better. Also what file system you choose makes a big difference on the speed of your file transfers and on how much it affects the desktop performance.

cricoste90, on 10/10/2007, -27/+1Buried as Linux spam.

mmalone, on 10/10/2007, -0/+10Uh, how is an article explaining how a technology works spam? ha1f, on 10/10/2007, -0/+5im burying you because you dont read articles before you do *****. fmorel90, on 10/10/2007, -0/+6If you don't want Linux articles, then uncheck the Linux/Unix category.

And how is this spam anyway? It's explaining something which a lot of people have been wondering about (apparently..since lots of people dugg this story). daftman, on 10/10/2007, -1/+2Dig him down if you feel like getting a hammer and smash his head in.

ha1f, on 10/10/2007, -2/+26Whats this? a Linux article on digg that isnt Ubuntu specific AND actually provides useful information? Bravo. Bravo, I say.

MeneerR, on 10/10/2007, -5/+2Well, without Ubuntu, what would you have to be a TROLL about?

wonboodoo, on 10/10/2007, -0/+4Anyone have links to benchmark comparisons between the different schedulers?

geminitojanus, on 10/10/2007, -0/+4Sadly, because the scheduler isn't hot-swappable, benchmarks are hard to do. However, there are a few that have been done: http://kerneltrap.org/node/14023

(And Google is your friend)

myfanwy, on 10/10/2007, -6/+1all redundant in 5 years when we have 256 core processors.......but a useful stopgap.
impressive work

on 10/10/2007, -0/+2I doubt it. As computer resources increase, usage of those resources tends to increase as well. I've got 39 processes running on my XP box right now, and the only somewhat out-of-place thing is an X server. I have even more running on my Linux machine.35263526, etnu, on 10/10/2007, -1/+1Even if you had more CPUs than processes on the system, you'd still have some processes that needed more CPU time than others, and hence will need a good scheduler.

ZeekWatson, on 10/10/2007, -5/+6Ingo fought long and hard for the status quo. Complaints against the current O(1) scheduler (author: Ingo) were met with flames and ignorance. Con spent a year developing a new scheduler and proving that it was better than the scheduler that Ingo wrote. Ingo spent the entire year ignoring and denying Con's scheduler, but one day he saw the light and wrote his own knockoff in "62 hours" and gets it merged the next week. This is *****.

The end result is that Con has been driven from Kernel development by asses like Ingo. Whether CFS is better than SD is irrelevant. What has happened is the guy who spawned the entire process of getting an improved scheduler in the kernel and spent a year overseeing and improving it has his concept stolen by Ingo. Ingo did not want a new scheduler, he wanted his name to be on the current scheduler. When he saw that disappearing he had to take drastic action and he "authored" a new, improved scheduler. All for his own glory.

stmiller, on 10/10/2007, -1/+5This is not the case at all. Ingo has a long track record of dedication to work in the kernel with schedulers, and is willing to maintain all work on this scheduler into the future. Con does not have a similar track record, and was NOT willing to maintain his scheduler work into the future. It was also clear that Con's behavior and personality also were not desirable by Linus and other kernel devs.

http://en.wikipedia.org/wiki/Ingo_Molnar

ZeekWatson, on 10/10/2007, -2/+2What a load of crap. Con released 30+ versions of SD over 1 year. He has also been working on scheduler improvements since 2004. If that isn't showing dedication and a willingness to support your software then what is?

Here is Con's wikipedia page ... dunno why you linked Ingo's?

http://en.wikipedia.org/wiki/Con_Kolivas

davidrools, on 10/10/2007, -1/+3I'm not a programmer so I don't know if this is possible for a kernel but:

Could the scheduler be user-customizable? It seems like one of those things that geeks would like to tweak for their preferred use and most people can just ignore it.

ZeekWatson, on 10/10/2007, -2/+4There is a patch set called plugsched http://kerneltrap.org/node/11776 (that has been rejected by Ingo Molnar). It allows easy authoring of schedulers and allows one to be picked at boot time. The reasoning seems to be that linux doesn't need multiple schedulers, it needs 1 scheduler with Ingo's name on it. grumpyrain, on 10/10/2007, -0/+1In theory yes, but I don't imagine it would be trivial to switch schedulers on a system you are running on without a restart at least.

nazsco, on 10/10/2007, -4/+2why one scheduler got not-merged because of this one? merge both, choose a default, and let the brave souls compile their crap. eventualy, nature will choose the better one.

brokencrystal, on 10/10/2007, -1/+1nature? DrDabbles, on 10/10/2007, -0/+3Because then you need a pluggable interface for task schedulers. That's not only more overhead, but a huge slowdown, and a headache to maintain and/or develop. Also, it's been tried with patches in the past with bad results.

ZeekWatson, on 10/10/2007, -2/+1Actually there is negligible overhead (you can't measure the slowdown), and a patchset to do this has existed since 2004. It hasn't been merged because Linus/Ingo didn't think multiple schedulers in the kernel was a good idea.

http://kerneltrap.org/node/11776

crash128, on 10/10/2007, -7/+0Confession #1: I have used air freshener as a deodorant. (not a biggie, but gotta start somewhere).

coolwalking, on 10/10/2007, -0/+1What? ekravchenko, on 10/10/2007, -0/+1lol, this was totally off topic

kethraal, on 10/10/2007, -1/+10"The end result is that Con has been driven from Kernel development by asses like Ingo"

Interesting -- as I recall (from reading LKML, etc.) was that Con basically took the attitude of "If I can't patch what I want as I see fit and have everyone like it, then I'm taking my toys and going home." At least Ingo was civil -- Con came off sounding like a whiny little playground brat.

Also, Con's staircase scheduler sucked. I'm sorry -- but it did. It was great if you were running a light-use setup (a desktop environment and a browser/text-editor or so), but if you put it under any real load it crumpled under the strain. This is, of course, totally unacceptable for a kernel that finds its way onto millions of high-load servers. When people pointed this out to Con, his reaction was basically: "No. It's good. Trust me -- I know it's good." instead of "Oh. Hmm... how can I improve my algo?" See the difference? One makes you sound like an arrogant prick (not a good thing for a cooperative project like Linux), the other makes you sound like a valuable asset to any team.

ZeekWatson, on 10/10/2007, -3/+4How should Con have acted? The patches he's been submitting for years have all been rejected and deferred and suddenly he sees someone implement a cheap knockoff of his biggest project and said knockoff gets merged into the kernel in less than a month. The kicker was the knockoff was implemented by the same guy who blocked almost all of Con's patches.

What should he have done? "Good show old chap!"???! Thieves and liars don't deserve "civil" -- they deserve the blunt truth.

daftman, on 10/10/2007, -2/+3*yawn*
It's linux, where everything is ***** open and everyone copy from each other. Knockoffs are common and especially when they improve on your own work. If he has that mentality, why the ***** did he program for linux and not start his own company or work for a proprietary company where they guard their "originals" like hawks.
There is no thieves are liar. It sounds like you are getting too emotional on something that is purely technical. Con is not a team player, that's all. SteveMax, on 10/10/2007, -0/+2So, you're saying that, to Con, having "his" scheduler on the kernel was more important than having the best scheduler on the kernel? Why does it matter who wrote it, as long as it's GPL'd and good? For the comments I see here, CFS manages higher loads better than SD did, and performs just as well under desktop environments. Someone improved on his idea, and that idea is going to the kernel. He should be happy, not be a bitch about it.

Think about it: you get a patch that breaks the kernel under high loads. You ask the maintainer to fix that behaviour. He doesn't do so for over a year, and keeps sending new versions with the same behaviour. You get fed up, and do the job yourself. If Con wasn't an ass about it, his scheduler could have been merged.

Darkhacker, on 10/10/2007, -1/+1GPL != Public Domain. Con wrote a vast majority of the code for it and Ingo basically took that code, altered it, and then claimed the entire thing as his own. Does Con not deserve ANY credit?

xeno439, on 12/29/2007, -0/+1good find. But I really think you should see http://www.sickscripts.com and http://www.mp34.us for more answers to this question. Who knows what is fair and what is not. The solutions may not be that far away from http://www.spongyweb.com either.

That was profound, almost as profound at http://www.thatsprofound.com crossers, 18 hr 51 min ago, -0/+0as I can't read the article, cause link not works. so no comment!
http://www.shpe-sac.org
http://www.ocflex.com/
http://www.trgovinca.org
http://www.chasr.org/

Login or register to add a comment

Create a new account or login to join in the conversation on Digg. You'll also be able to Digg stories to help promote things you like.