Slashdot Mirror
Linux Gets Completely Fair Scheduler
SchedFred writes "KernelTrap is reporting that CFS, Ingo Molnar's Completely Fair Scheduler, was just merged into the Linux kernel. The new CPU scheduler includes a pluggable framework that completely replaces Molnar's earlier O(1) scheduler, and is described to 'model an "ideal, precise multi-tasking CPU" on real hardware. 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.' The new CPU scheduler should improve the desktop Linux experience, and will be part of the upcoming 2.6.23 kernel."
I know enough about process scheduling to fill a ketchup cup at the nearest burger joint, but it struck me that this sounds like the debate about "network neutrality" vs "tiered service." The O(1) was supposed to be a very generic decision-making system that made a decision in a very agnostic way (to simplify the work down to a predictable consistent order of work). This CFS strikes me as a system which will have a much higher level of complexity and context awareness, which sounds like some processes will get more than others. The intention is to make it fair in the real world but not necessarily balanced, since not all processes are alike in their needs or expectations of task switching.
This is just rambling on, and admittedly it may be straining a metaphor too far, so don't go crazy biting my head off for not knowing all things about the kernel. See 'ketchup cup' above.
[
We saw crazy performance improvements implementing kqueue in bsd, would love to see something that great at handling many sockets standard linux.
Actually, no, Gnome and KDE aren't the troublemakers. It turns out that certain X drivers are poorly written and X preempts processes vying for CPU. CFS helps improve the situation - almost to the point where you don't notice it.
grey wolf
LET FORTRAN DIE!
a fair scheduler won't help. BeOS had a very snappy, responsive GUI by being multithreaded (each window was a thread) and giving window/display threads higher priority. Even if the CPU(s) were bogged down with other threads, moving windows, the display stayed responsive. X is single threaded and the window manager architecture makes the problem worse. A fair scheduler doesn't help; it actually makes things worse.
If you mean the typical user running Linux on their PC: probably no effect at all. But a better scheduler would make a lot of difference to a server. And that's the growth market for Linux these days.
Yep. I've seen this in CFS testing actually. Pretty much all of the work that the X server does can be assumed to be "on behalf of" somebody, but in the end those cycles still belong to the X server. So an app can be thoroughly abusive, spam the X server with requests, fill up queues, and prevent anyone else from using the server to do anything useful -- and yet it still gets priority because as far as the scheduler can tell it's a perfectly nice I/O-bound task that spends most of its time waiting for the X server to get back to it. As I recall, Linus provided a "fix" for that particular problem sometime early in 2.6 or late in 2.5 -- but later retracted it because it did more harm than good -- any simple solution you might think of has already been tried and thrown away.
:)
Oh, and the abusive app that likes to make X servers choke? Firefox. Ugh. Hate that thing.
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 even admitted that the design was based on Con's SD work.
The only reason CFS is in the kernel and not SD is politics.
If it's a red-black tree, it's O(2 ln(N)). The fact that N never gets too big has nothing to do with it. It is... disturbing... to hear this from someone like Ingo. I also have no idea where ~20-21 came from, as the maximum depth at four million is higher than that.