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."
just finished make xconfig;make from 2.6.22!
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.
[
Steal your insightful comments from http://linux.slashdot.org/article.pl?sid=07/04/22/ 1335255
Slashdot: news for Apple. Stuff that Apple.
This isn't really the same kind of component.
On the other hand, Linux has epoll, which fills the same role as kqueue.
In my experience, epoll is at least as good.
http://www.kegel.com/c10k.html#nb.epoll
Now MacOS X needs to fix their kqueue bugs, and the world will be a happy place.
It also means that tasks which were denied adequate runtime in the past will now be favored over current tasks, to make up for the prior unfairness. :)
The only way to make it completely fair is to let one thread slice the time up, and let the other thread choose which slice it wants. ;-)
you'll feel a placebo effect.
Affirmative preemption!
--
"Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next.
[ck] It is the end of -ck
This is pretty sad for linux kernel development.
(disclaimer, i'm the main author of CFS.)
I'd like to point out that CFS is O(1) too.
With current PID limits the worst-case depth of the rbtree is ~15 [and O(15) == O(1), so execution time has a clear upper bound]. Even with a theoretical system that can have 4 million tasks running at once (!), the rbtree depth would have a maximum of ~20-21.
The "O(1) scheduler" that CFS replaces is O(140) [== O(1)] in theory. (in practice the "number of steps" it takes to schedule is much lower than that, on most platforms.)
So the new scheduler is O(1) too (with a worst-case "number of steps" of 15, if you happen to have 32 thousand tasks running at once(!)), and the main difference is not in the O(1)-ness but in the behavior of the scheduler.
No, CFS does not do that, and that would be quite silly to do indeed :-)
CFS keeps tasks that woke up in the runqueue, and allows them to run immediately in the typical case - just like the old scheduler did.
Where CFS differs from the old scheduler is mainly the case when there are more tasks runnable than there are CPUs/cores available. In such cases, on any modern multitasking kernel, the scheduler has to decide which task to run, and in what order and weight to run those tasks, with the goal to provide to the user the happy illusion of multiple, snappy applications running at once.
The old O(1) scheduler decided the "order and weight" of runnable tasks based on an pretty elaborate set of heuristics. The rules are pretty complex, but it mostly boils down to 'sleepers get more CPU time than runners'.
(sidenote: CFS is an O(1) scheduler too for all practical purposes, with an upper limit of ~15 algorithmic steps worst-case)
Now those heuristics worked pretty well for 15 years (those sleep-heuristics were always part of Linux scheduling, the O(1) scheduler i wrote inherited them from the original O(N) scheduler), but good is never good enough in the land of Linux ;-)
How does CFS work? CFS follows an approach similar to Con Kolivas' SD project: a scheduler core that instead of heuristics uses "fair scheduling" to achieve interactivity. Runnable tasks are scheduled in a painstakingly fair way (and that seemingly simple concept alone is pretty hard to achieve in a general purpose kernel).
The simplest case is when there are only CPU-intense tasks running. For example, if there are 8 CPU-intense tasks running on the CPU, each task gets exactly 12.5% CPU time. If you watch how much CPU time the tasks get it will be 12.5% long-term too, with no deviations, with no skewing caused by other tasks running inbetween.
The more complex case is when applications schedule frequently (and that is the case on most desktops and servers), so CFS extends the concept of 'fairness' to sleeping tasks too. CFS accounts not only 'runners', but 'sleepers' too. Tasks that sleep/run frequently are still given their full 'fair share' of the CPU, up to the limit they could have gotten were they not sleeping at all.
So for example, if you have two tasks on a CPU, one a 100% CPU hog, the other one an application that sleeps/runs 50% of the time - both will get 50% of the CPU in CFS. Under the strict 'runner fairness' approach (which for example SD is following), the 100% CPU hog would get ~66% of CPU time, the sleeper would get ~33% of CPU time.
To achieve 'sleeper fairness', CFS runs the (ex-)sleeper task sooner, to offset its disadvantage of not hanging around on the CPU all the time. Or in other words: interactive tasks (tasks that sleep often) will get to the CPU with lower latencies. Which is the holy grail of good desktop scheduling :-)
(granted, CFS does a whole lot more than that, its patch-impact size is 3 times larger than SD. CFS is not a single patch but a series of 50 patches, which also modularize kernel scheduling policy implementation (note, it does not modularize the scheduler itself a'la PlugSched), offer "group scheduling" (nifty thing for containers/virtualization and large systems, written by Srivatsa Vaddagiri of IBM), offer precise CPU usage accounting to /proc (used by CPU/task monitoring tools), and much more. We decided to turn Linux scheduling upside down, which gave me the easy excuse^H^H^H opportunity to extend the scheduler's design a bit more ;-)
You meant: 10 GOTO 666 666 PRINT you insensitive clod!
It doesn't have to be like this. All we need to do is make sure we keep talking.
> So little credit is given to Con Kolivas ...
> And all Con gets is a minor footnote.
I'm a kernel developer myself and quite surprised you see it that way.
Let's take a look at the kernel code:
1) Ingo credited Con for the "fair scheduling" approach right on the first page of kernel/sched.c. That's the
most prominent place you can get credited for working on the Linux scheduler
* 2007-04-15 Work begun on replacing all interactivity tuning with a
* fair scheduling design by Con Kolivas.
2) He credited Con for a line of code that he added to CFS from SD, in kernel/sched.c
* This idea comes from the SD scheduler of Con Kolivas:
This is the only SD code in CFS - the two designs and approaches are quite different.
3) He credited Con in Documentation/sched-design-CFS.txt
I'd like to give credit to Con Kolivas for the general approach here:
he has proven via RSDL/SD that 'fair scheduling' is possible and that
it results in better desktop scheduling. Kudos Con!
4) Finally he credited Con in the CFS commit log as well:
commit c31f2e8a42c41efa46397732656ddf48cc77593e
Author: Ingo Molnar
Date: Mon Jul 9 18:52:01 2007 +0200
sched: add CFS credits
add credits for recent major scheduler contributions:
Con Kolivas, for pioneering the fair-scheduling approach
Peter Williams, for smpnice
Mike Galbraith, for interactivity tuning of CFS
Srivatsa Vaddagiri, for group scheduling enhancements
Signed-off-by: Ingo Molnar
I don't see much more places, where credit could be documented.
tglx
> Ingo please comment on this because I have read similar stories elsewhere and would like to hear a
/. article. (Direct link to full KernelTrap article not provided, in the hope of saving the site from a slashdotting).
> response.
I'd understand if Ingo doesn't want to comment on this; it was a painful clash between two competent and strong characters, which expanded to other parties accusing Ingo of elitism and plagiarism.
For reference, this was archived on kerneltrap.org, and I believe it was covered in an earlier
For what it's worth, here's the "facts" as I see them :
1/ It looks as though Ingo *and*Linus* refused Con's original patch on certain grounds which weren't clearly understood/communicated. Ingo, however, stated that in general he was "quite positive about the staircase scheduler." He proceeded to test it and gave Con feedback.
2/ Con's work was good enough that Ingo about-turned on his earlier, negative stance about fair schedulers and was inspired to go and develop something very similar (but which fitted better with the overall kernel architecture). It's clear that this was predominantly Ingo's own code (hence no plagiarism), and Ingo credits Con in the code comments for coming up with the general approach.
3/ Somewhere in the middle of the ensuing discussion on lkml there are complaints that Con wasn't kept in the loop. However, Ingo cites examples where he *did* communicate to Con; by Con's own admission he was very ill (hospitalised) during a critical period.
4/ Parent suggests that Con has since stopped contributing to the kernel. I don't see any indication of this in the kernel thread - in fact Con's post gives every indication that he'll continue to contribute.
My analysis :
I put the situation down to an applied case of "standing on the shoulders of giants". It's very rare that anyone creates something completely new, and in large projects this can occasionally generate friction.
Con was in a susceptible condition when the CFS code was released, had a grumble on the list, but generally acted pretty maturely. Ingo credited Con's contributions wherever feasible, clarified this in discussion, and stayed polite and friendly throughout. End of story.
What's pretty disgusting is the partisan name-calling that follows in the KernelTrap comments. "Shame on Ingo", "Con is acting like a baby", etc. I hope that this doesn't generate bad feeling between Molnar & Kolivas, because after Con's original complaint on lkml and Ingo's response things seemed to be settled.
No doubt in future Ingo will take an increased amount of care about vetting other people's code, not promoting his own to the exclusion of others, and crediting other people in his own work (note: I don't claim that he has been lacking in this respect in the past). Con, likewise, will doubtless be mollified when his contributions are more readily recognised as being of merit in future. In the meantime Linus has emphasised that competition between developers is a *good* thing to a reasonable extent, as it directly increases motivation.
Now, I suggest that everyone else with a ready opinion hold their breath a while, and let all them get on with coding.
Conrad
Well, given that he is the maintainer, Ingo Molnar's code is presumably more maintainable. It happens all the time in free software projects, someone submits a patch, the idea in the patch is good, but the section of the code is important enough that the maintainer must be certain he understands it. Rewriting it is a good way to gain such understanding.
Back when I was a maintainer, I guess I rewrote half the patches I got. Most submitters are just happy to see the functionality in there, but there was a few people with fragile egos take it as a personal insult That happens, life goes on, and usually the fragile egos grow more robust with time, and learn that developing what amounts to a prototype of the final code is also a valuable contribution.