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

Process Neutrality?

[Speare]

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.

Can anyone compare this to Jonathan Lemons Kqueue?

[Desmoden]

We saw crazy performance improvements implementing kqueue in bsd, would love to see something that great at handling many sockets standard linux.

Questions

[flar2]

Is there a default scheduler in the linux kernel? If so, which is it? Are there several schedulers to choose from? If so, which one(s) do the major distros use? Will the new CFS be the new default or just another choice?

Improve how?

[suv4x4]

The new CPU scheduler should improve the desktop Linux experience, and will be part of the upcoming 2.6.23 kernel.

Could someone outline concrete problem the Linux desktop scheduling had right now that are visible resolved by CFS.

I'm not a heavy user of Linux desktop (just servers on the shell), but it was always my experience that Linux handles simultaneous multimedia tasks (for example) better on the same hardware than Windows.

While I contribute this more to architectural problem on the Windows side (such as.. it's quite easy an app to stall Explorer.exe or vice versa, no amount of scheduling helps there), I'm curious to see if there's tangible difference someone could describe with CFS running desktop software in Linux.

Re:Cool

[tkavanaugh]

I've always been more impressed with the Solaris' scheduler, I've done a few ports recently of realtime applications to linux from solaris 8 and 10 that have a hard time running properly under linux...
Of course these applications have had years of tuning under SOlaris so it's not an entirely accurate example...

Re:how it's possible?

[the_greywolf]

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.

Re:crap

[Anonymous Coward]

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.

Re:CFS vs. O(1)

[Anonymous Coward]

I thought the depth of rbtrees were C*ln(n) where 1C2, so that the number of "steps" in going down the tree would be bounded to 16*2 in this case?

Maybe I'm remembering the worst case behaviour of rbtree wrong.

Re:Process Neutrality?

[mc6809e]

Scheduling algorithms are very important for routers too. So there is an analogy. But the analogy isn't with a tiered internet. It's with protocol based QoS.

The analogy with a tiered internet is fine, provided you look back far enough in the history of computers.

Before personal computers became common, people got a lot of their work done by renting time on mainframes. People that wanted cheap CPU cycles had their jobs wait for spare cycles. Those that needed immediate answers paid more and their jobs got a higher priority.

In essence some people paid more for lower latency while others that could wait got a discount.

Re:Neato

[fm6]

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.

Re:Improve how?

[CoughDropAddict]

I don't see how this improves the situation for realtime applications. A realtime application's need can be summarized thus: "I need X amount of resources (CPU time, I/O bandwidth) by timestamp Y." As I understand it, CFS distributes CPU time completely equally among runnable processes, so if the realtime application needs more than an equal share in order to maintain its realtime processing, it's sorry out of luck.

If I run 50 processes that are spinning, each one of them will get just as much CPU time as the realtime process. How is CFS going to protect that realtime process from starvation?

Re:crap

[arodland]

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. :)

This is politics, not programming

[ZeekWatson]

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.

Re:CFS vs. O(1)

[John Nowak]

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.

Re:how it's possible?

[Ganesh999]

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

Just a thought - have you considered using the golden ratio instead of basic proportions? Is it feasible/viable?

(http://en.wikipedia.org/wiki/Golden_ratio)

Disclaimer: I haven't the first clue about kernel internals, let alone scheduling.

However, my complete lack of knowledge of such things, this problem seems somewhat analogous to location of maxima/minima in real data. In that application, bracketing & bisection via golden ratio provides the fastest convergence (faster than equal bisection).

If CFS proves to be good, then perhaps such an approach (i.e. phi-weighting, in *favour* of sleeping processes?) would provide the optimal solution.

I'd be interested in your thoughts.

Conrad

Re:crap

[John Betonschaar]

Qt is slow as molasses. We just failed the speed requirement for an uni project because Qt will easily eat 100% CPU if you have to log data into a table a few times a second (of course that's the reason we don't care

Well, maybe you just need to learn how to code write efficient Qt code then... Qt is not the fastest UI library on earth, but it is *not* 'slow as molasses'. We use it on hardware ranging from Pentium-II@500Mhz, to UltraSparcII@400Mhz to dual Opterons, and even on the lowest-end hardware it works fine.

Why, by the way, would you want to log data into a Qt table a few times a second? Do you seriously expect people to 'read the table' *a few times a second*. Don't you think data aggregation and lazy posting to the table would be a better idea for *any* GUI toolkit. You just sound like blame your own incompetence in GUI programming on Qt.

Re:Cool

[FST777]

That's correct in my experience. I have no experience with Solaris, but I have seen FreeBSD go through high spikes where Linux grinds to a halt. With smaller loads Linux feels a tad more responsive though.

I do hope this scheduler will make things even better: gracefull degrading and responsiveness in one. Might make it the ideal OS for my needs (I now have Linux on the desktop and FreeBSD on the servers).

Re:Ok, here's your Microsoft bash

[jasonwea]

Nice pun.

I've found Cygwin and PuTTYcyg [gccaz.edu] configured with Consolas 11pt [imageshack.us] gives a quite usable CLI on Windows. My favourite terminal emulator is definitely Terminal.app [imageshack.us] though.

Re:how it's possible?

[tbriggs6]

Thank you Ingo for replying! I am very interested in your work on scheduling both from an academic and pragmatic point of view. In an earlier post, someone commented on the anecdotal differences in the Solaris scheduler to the Linux scheduler w.r.t. heavily loaded systems. I was wondering if you have any comment on this, specifically with regards to the increasing use of virtualization, specifically VMWare products. Will/can CFS improve vm performance? Will CFS improve the throughput processing capabilities of Linux, or is it chiefly designed to improve interactive processing w/out degrading throughput? Finally, I am curious, has there been any consideration to allowing scheduling hints to be passed in from the programmer, ala cache hint directives in some of intel's compilers.

Re:crap

[shellbeach]

I have never seen any instance where Cairo made something faster.

Well, Inkscape seems to think [inkscape.org] that Cairo makes their rendering faster:

"In this version, Inkscape starts using the cairo library for rendering. It is now used for outline mode display which, thanks to using cairo and other optimizations, redraws faster by about 25%. More impressive are memory savings: thanks to cairo, in outline mode Inkscape now takes only about 50% of the memory used by 0.45 for the same file."