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."

Neato

[friedman101]

What sort of gain can the typical linux user expect because of this?

Kernel building is pretty fast

[EmbeddedJanitor]

Should take you less than 15 minutes to get there again.

If you really want a rough time, see how long it takes to rebuild a different OS.

Re:For the attention of karma whores

[garcia]

The sad thing is that the summary reads almost identical:

"Kernel trap has a nice summary of what is going on behind the scenes to change the Linux Scheduler. The O(1) Linux scheduler is going to be changed so that it is fair to interactive tasks. You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks."

Re:Cool

[HairyCanary]

Ha, I was about to come in and say the same thing. I've always been disappointed in the Linux scheduler compared with my Solaris servers. I run an ISP and frequently get abnormally high load spikes -- my Linux servers handle the load poorly, degrading all of the sudden to gridlock. The Solaris servers, on the other hand, degrade gracefully, still serving up requests but getting slower as the load skyrockets.

Re:how it's possible?

[BitchKapoor]

You're right. The comment to which you replied is simply incorrect.

Re:Process Neutrality?

[Anonymous Coward]

The crucial difference is that the CFS gives/takes processor time to/from processes purely based on improving the overall processor throughput and "responsiveness" of the system. CFS makes its decisions exclusively from a technical standpoint.

This is not comparable to tiered network service because tiered network service makes decisions on what data packets to carry/drop based on political, legal, and business policies.

As an example, CFS will probably place a low priority on background backup tasks and a high priority on real-time audio applications because users will quickly notice if their audio files are skipping but are less likely to notice/care if their backups take slightly longer. This is a feature of a quality scheduler. However, if CFS further increased its preference for real-time audio applications because the programmer owned stock in several music companies then that would be an example of a "tiered service scheduler".

Poor attribution

[the_greywolf]

So little credit is given to Con Kolivas, whose Staircase Deadline scheduler (a more mature and refined design than CFS) spurred Ingo to finally improve his scheduler (which he wrote on the spot because, apparently, Con's scheduler wasn't good enough for him).

And all Con gets is a minor footnote.

Re:CFS vs. O(1)

[SillyPerson]

Am I the only person worried that the main author of CFS does not seem to understand big O notation and red-black trees?

Politics are destroying Linux too

[TeXMaster]

How does CFS work? CFS follows an approach similar to Con Kolivas' SD project:

Too bad that the NIH syndrome hit Linux Kernel development too, and Ingo Molnar, after blocking all the attempts to merge SD into mainline because "it couldn't be done", uses the same idea, whips out his own scheduler calling it "Completely Fair", and woosh it gets merged (easily, given that Ingo Molnar himself is the maintainer of that part of the kernel).

Con Kolivas is (obviously and justifiably) disgruntled, to say the least, he stops working on the SD project, and Linux loses an excellent developer because of politics.

Re:Poor attribution

[Anonymous Coward]

Whether this is accurate or not, a good manager doesn't post his criticisms of people's characters and communication styles in public.

For me, this posting evaluates to "--linus".

Re:You mean for....

[CmdrGravy]

I think there's a reason it's called the American Dream and not, for instance, the American Reality.

Angsty nerds are not destroying Linux

[Per Abrahamsen]

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.

Ingo is a power freak

[Anonymous Coward]

His approach for years was to knock all contributions that improved on his earlier code so that they didn't get into the kernel. And now suddenly he sees the light and gathers up all those ideas of others into a new version as if it were novel, totally forgetting that he had rejected them before. And to compound the problem, his quick rehash then immediately gets merged in despite being effectively untested.

If this were business or politics, "corrupt" would describe this state of affairs quite adequately.

For all the talk of code merging based on merit, what we really have in the kernel is an old boys' club in which the inner circle get a free pass even when they deliver crap, as in this case.

Ingo's CFS code is utterly immature and bug-ridden, and should not have been merged. Since he accepts that Con's SD is a great idea, and as it has the benefit of a lot of testing and code maturity, Ingo should have backed its incorporation into the kernel, instead of opposing it.

But no, then it wouldn't bear Ingo's name on it, which would be total anathema to Ingo.

This is a bad state of affairs folks.

Re:Poor attribution

[Abcd1234]

Well, if the mailing list is erupting in flames because of this, then it very much makes sense for Linus to explain the reasoning behind the decision. Otherwise, potential kernel devs may be turned away, as they may simply see Con getting shafted, instead of what appears to be a personality conflict, and get the impression that Linux kernel developers are resistant to outside contributions.

Besides, Con clearly aired his side of the story in public. Are you saying Linus shouldn't be given the opportunity to do the same?

Re:Neato

[Geek of Tech]

Yeah. I know what you mean. I kept trying to convince the developers to use a scheduler that would make the CPU run faster than physically possible myself too. They just went all crazy on me. I guess we'll have to keep on using a scheduler that decides how to schedule the CPU time instead of one that can run all the processes at once. Silly developers.

Re:how it's possible?

[Bri3D]

The thing is that the problem isn't in the application processing; it's in X's processing. CFS (which I have run) does not help with X and GUI applications at all. As a matter of fact it made things worse for me, because some processes (Firefox especially) send huge chunks of X requests to the server at once. With CFS, X, because it has the highest "need" for CPU and is niced to a very high priority on many desktop distributions to "improve responsiveness" blocks all other applications from processing, leading to slowness (Firefox "flickering" pages as it sends chunks of X requests off while it's still trying to render the rest).

Attempting to nice X to a lower priority only makes things worse; then your GUI applications block up X and it doesn't help to have your GUI applications processing when you can't see what they're doing!

What really needs to happen is X needs to either go away or be fixed. Linux *desperately* needs less stupid Beryl/Compiz/compiz fuzion extreme lol edition or whatever they're calling it these days, and instead someone needs to create a windowing server which gives each window a draw thread, BeOS style.

Re:CFS vs. O(1)

[Ingo Molnar]

(To answer your question: the 20-21 comes from other limits to the task space - right now we are still limited to 32k pids.)

Yes, you are right, operations on an rbtree of an arbitrary data structure are of course an O(log2(N)) algorithm, no argument about that.

I know what the mathematical meaning and definition of the big/little ordo/theta notations is (probably better than i should ;), I only wanted to point out the fact that an O(log2(N)) algorithm for most data structures in the kernel (or elsewhere on today's computers) is equivalent to O(1) in practice, especially if N is fundamentally limited to 15 bits like in this case!

The main purpose of the ordo/theta notations is to be able to talk about and compare the performance (worst-case/best-case/average-case) qualities of algorithms. Sticking to their strict mathematical definition in cases where it departs from their original purpose results in worse software :)

And talking about big ordo differences between algorithms operating in finite machines still makes sense (naturally): for example, O(sqrt(N)) is not equivalent to O(1) in practice - it can still be very large, even with a pretty limited N. O(N) is also obviously very relevant in practice, even on very limited machines. But the difference between O(log2(N)) and O(1) is insignificant in most cases, and in fact it is deceiving in this case. (as i pointed it out with the O(140) example.)

Re:It's about that time of year again...

[doti]

Yep, there are two things I don't like about the Linux scheduler:

1) No I/O awareness. When copying a bunch of big files around, I want that process to have lower possible priority, and not interfere with other system activities, like opening a new program, or doing small I/Os. Bottom line: give bulky transfers idle priority.

2) Lack of idle priority. I want to be able to run a process that only gets CPU time if there's nothing else to do. Even with the lowest possible priority, it will still eat some precious (~5% last time I checked) CPU time.