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

crap

[cachimaster (127194)]

just finished make xconfig;make from 2.6.22!

Re:crap

[Hikaru79 (832891)]

Great. A new scheduler will surely attract more masses to Linux than, say, a non-ugly GUI-lib or a sane, standard windowing-environment would. That's the way to go.

Well, no offense, but I'm glad it isn't you that's in charge of making important decisions in that case. I realize that you were probably less than half-serious, but I would hate for the Linux community to ever be in the stage where "attract more masses" is a goal that diverts effort from interesting projects like this one.

With that said, what's wrong with Qt/KDE, particularly the new versions (the ones still in Alpha)? I'd say it is very much a "non-ugly GUI lib", and a "sane windowing environment".

Re:crap

[arodland (127775)]

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

Equal opportunity, affirmative action scheduler

[EmbeddedJanitor (597831)]

For the really touchy-feely OS out there!

It's Worse Than That

[grcumb (781340)]

A complete fair scheduler for geeks? I can just see it:

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
1 user 16 0 1464 184 140 S 90.0 86.1 0:01.93 wank
2 user RT 0 0 0 0 S 10.0 13.9 0:00.00 porn
3 user 34 19 0 0 0 Z 0.0 0.0 0:00.00 work
4 user RT 0 0 0 0 Z 0.0 0.0 0:00.00 socialise
5 user 10 -5 0 0 0 Z 0.0 0.0 0:00.31 getadate

Re:Equal opportunity, affirmative action scheduler

[Lithdren (605362)]

No it just means programs wont crash other programs based purly on the programming langauge that was used to bring them into being. All languages were created equal.

Except Basic. Nobody likes basic.

Re:Equal opportunity, affirmative action scheduler

[by Anonymous Coward]

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

Re:Equal opportunity, affirmative action scheduler

[sharkey (16670)]

Affirmative preemption!

Re:Equal opportunity, affirmative action scheduler

[by Anonymous Coward]

Except Basic. Nobody likes basic.

goto hell you insensitive clod!

Re:Equal opportunity, affirmative action scheduler

[Aethedor (973725)]

You meant: 10 GOTO 666 666 PRINT you insensitive clod!

Process Neutrality?

[Speare (84249)]

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.

Re:Process Neutrality?

[by Anonymous Coward]

Sort of. 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. For instance, VoIP requires very low latency, but BitTorrent doesn't. So shaping traffic so that VoIP stuff gets handled by a router first (while minimally affecting BitTorrent) improves the quality of service. On the kernel scheduling side of the analogy, some software needs to have quick access to the processor, often, but for short periods of time. A GUI interface is an example. Real-time software is a more important example.

A tiered internet is something else entirely.

Re:Process Neutrality?

[DreadSpoon (653424)]

I think you have this TOTALLY backwards.

The old scheduler was filled with huge chunks of complex code to try to guess at which processes were interactive and such, and would then specially treat those processes differently when scheduling.

The CFS does none of that. It schedules all processes the same, in a completely fair manner, and doesn't have any special logic in it that tries to classify processes at all, other than nice levels.

The part yet to be merged is the process grouping, which again isn't anything like the interactivity guessing code. It's just a simple way to say "these processes belong together, so when you do the CPU scheduling, treat them as a single group." It's basically just a weighting mechanism with a logical container.

For the attention of karma whores

[SoVeryTired (967875)]

Karma Whores:

Steal your insightful comments from http://linux.slashdot.org/article.pl?sid=07/04/22/ 1335255 [slashdot.org]

Re:For the attention of karma whores

[garcia (6573)]

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

Why...

[lawpoop (604919)]

Why does this sound like the title of a Monty Python Skit?

"Why isn't my process getting more CPU time?"

"Well, Sir, it's a Completely Fair Scheduler."

--mm line

[Enderandrew (866215)]

CFS has been available for some time in Andrew Morton's -mm branch of the kernel. If you really want it now, just download his latest patch and there you go.

I've reen running with it for some time, and I really like it. I'm still not sure if it is better than Con Kolivas' SD scheduler in his patchset, but we'll see.

Anyone with kids can tell you...

[s_p_oneil (795792)]

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

CFS vs. O(1)

[Ingo Molnar (206899)]

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

Re:CFS vs. O(1)

[-Bacon- (75425)]

Big O notation describes performance as "n" approaches infinity. If you cap n, then of course you cap the execution time, that's the case for most any algorithm. What you're describing still remains O(ln(n)).

Frankly big O notation isn't a very good way to describe scheduler performance. Execution time under common loads, and maybe an extreme case would be better. Who cares about an O(1) scheduler that always takes 1 second to schedule the next task :)

Re:Can anyone compare this to Jonathan Lemons Kque

[Defiler (1693)]

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 [kegel.com]

Now MacOS X needs to fix their kqueue bugs, and the world will be a happy place.

Re:Neato

[smartdreamer (666870)]

you'll feel a placebo effect.

Re:Neato

[fm6 (162816)]

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:Poor attribution

[by Anonymous Coward]

Not only does he get very little credit, but the whole experience of trying to get his patches merged into the mainline have soured him on kernel development altogether:
[ck] It is the end of -ck [bhhdoa.org.au]

It is clear that I cannot develop code for the linux kernel intended only to
be used out of mainline and not have mainline get involved somewhere along
the line. Whether it be the users or even other developers repeatedly
asking "when will this be merged". This forever gets me into a cycle of
actually trying to merge the stuff and ... well you all know what happens at
that point (again I had nastier words but decided not to use them.)

This is pretty sad for linux kernel development.

Re:how it's possible?

[Ingo Molnar (206899)]

Seriously? What, the kernel switches to a process, the process checks its environment and figures out that the event it was waiting for hasn't happened yet, and goes back to sleep? I can't believe that a project as mature as the Linux kernel would use a scheduler like that.

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 ;-)