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

Comments

crap

[cachimaster]

just finished make xconfig;make from 2.6.22!

Re:crap

[cachimaster]

Is not fair!

Re:crap

[setagllib]

With desktop environments like GNOME taking up more CPU time per user than all Google servers combined, a strong scheduler is desirable to make it at least sort-of tolerable. Although really, switching to KDE is known to have a much stronger positive effect.

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:crap

[Hikaru79]

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]

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

Re:crap

[dam.capsule.org]

Fair enough.

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:crap

[setagllib]

Surely you jest. The vast majority of GUI CPU time on a typical GNOME box is spent in Pango. I dare you to profile it and prove me wrong. Pango puts in a lot of hard work, and most of it goes to waste. Now parts of GNOME are actually written in C# using Mono and Gtk#, giving you a couple of extra layers of failware. The work X.Org does is extremely minimal these days, especially when it uses hardware acceleration for some render tasks.

Smart scheduling is no competition for fast code, and KDE wins hard by using Qt. Even Swing with the (apparently proprietary) Java2D backend is much faster than GTK, even when GTK uses Cairo.

Look at 'top' and sort by total CPU time. X.Org will be one of the highest, but you have to remember it takes a chunk of everyone's CPU time and that persists even after they die. I'm sure if you add up all your other graphical programs, even the ones that are running just now and not counting the old ones, it'll be much higher than X.Org.

Re:crap

[JohnFluxx]

Learn Model View Controller programming. I have coded a similar thing myself in Qt without such problems.

Re:crap

[MT628496]

Smart scheduling is no competition for fast code, and KDE wins hard by using Qt. Even Swing with the (apparently proprietary) Java2D backend is much faster than GTK, even when GTK uses Cairo.

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

Re:crap

[Anonymous Coward]

For a requirement like that, you would have likely wanted to implement your own model backing a QTableView. You would have extended QAbstractItemModel and handled data updates there, and let notifications to the GUI flow when needed. You would probably have seen better performance. See http://doc.trolltech.com/4.3/qtableview.html , http://doc.trolltech.com/4.3/qabstracttablemodel.h tml , http://doc.trolltech.com/4.3/qabstractitemmodel.ht ml , and http://doc.trolltech.com/4.3/sql-tablemodel.html for more information.

Re:crap

[shellbeach]

I have never seen any instance where Cairo made something faster. Well, Inkscape seems to think 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."

Equal opportunity, affirmative action scheduler

[EmbeddedJanitor]

For the really touchy-feely OS out there!

Re:Equal opportunity, affirmative action scheduler

[ArcherB]

For the really touchy-feely OS out there!
Does this mean all apps will play nice?

Re:Equal opportunity, affirmative action scheduler

[Lithdren]

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

[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

[Anonymous Coward]

Except Basic. Nobody likes basic. goto hell you insensitive clod!

Re:Equal opportunity, affirmative action scheduler

[sharkey]

Affirmative preemption!

Re:Equal opportunity, affirmative action scheduler

[Aethedor]

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

Re:Equal opportunity, affirmative action scheduler

[Andrzej Sawicki]

instead of psdoom we will now use psOMG_PONIES?

Fixed.

Neato

[friedman101]

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

Re:Neato

[smartdreamer]

you'll feel a placebo effect.

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:Neato

[BooleanLobster]

Hey, you're right! I feel it!

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.

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.

Re:Process Neutrality?

[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]

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.

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

Re:Process Neutrality?

[the_greywolf]

It works quite well. I use Con Kolivas' SD scheduler (on which CFS is based), and in a similar situation (with heavy I/O and numerous power-hungry apps), it performs exceedingly well.

Ingo tests CFS with a kernel make -j50 - just to give you an idea of what we're shooting for here.

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.

Prediction ...

[Gopal.V]

I've sort of gazed for a few seconds at the CFS articles and the following phrase caught my attention the most

it uses a time-ordered rbtree to build a 'timeline' of future task execution

But more importantly, I think the factor which'll probably sway me the most is /proc/sys/kernel/sched_granularity_ns. Except I've been salting my config options with one true test ... that kind of thing makes you paranoid about random tune-ups :)

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.

For the attention of karma whores

[SoVeryTired]

Karma Whores:

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

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

Why...

[lawpoop]

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

how it's possible?

[Saija]

"The new CPU scheduler should improve the desktop Linux experience"
really? and how it's suppose to do that wonderful thing?
ps: i'm just curious and noob, so please don't smash me... ;)

Re:how it's possible?

[Anonymous Coward]

The CPU scheduler affects the latency of processes. Interactive applications are very latency sensitive - if they do not get scheduled frequently enough the system will feel sluggish. A good desktop scheduler will therefore schedule all of your interactive tasks frequently. I don't understand the details of the CFS, but if it claims to improve the desktop Linux experience then it must do this.

The tradeoff with short timeslices is that there's more overhead due to context switches and so the overall time spent doing useful work on the cpu will be lower. For non-latency sensitive applications it makes sense to keep the cpu residency time of processes high to maximize throughput. Hence the "desktop->server" tunable.

The blurb does mention that that CFS has 'no notion of timeslices' which sounds like nonsense, but I trust Ingo knows what he's talking about so maybe we have different definitions for that term. Anyone care to explain?

Re:how it's possible?

[Doctor Memory]

Right now, most applications get "time", even if they don't need them... so, you are "wasting time" being a "good kernel/waiter" by going to your customer (process), and asking if he needs something more, just to wait for a "no" as answer. 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. That sounds more like the result of trying to squeeze a scheduler into 256 bytes so you can lock it into two cache lines. I mean seriously, it's like cooperative multitasking with preemption...

I know it's a little "old school", but whatever happened to keeping track of which processes were "runnable" (i.e., had something to do) and which processses were waiting (blocking on I/O, waiting for a semaphore, waiting until the kernel gave them a buffer, etc.)? I kind of liked VMS's scheduler, it would boost the priority of processes that were waiting for TTY input (i.e., users), then gradually (over the next couple of context switches) return the priority to the default. That way, even if the system was busy, interactive users got a little more attention, so the system *felt* faster. I'm sure the Linux scheduler has some equally interesting features.

Re:how it's possible?

[BitchKapoor]

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

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:how it's possible?

[Ingo Molnar]

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

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

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.

Re:Can anyone compare this to Jonathan Lemons Kque

[Defiler]

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.

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?

Re:Questions

[lordtoran]

Is there a default scheduler in the linux kernel? If so, which is it? The O(1) scheduler.

Are there several schedulers to choose from? No, there is currently only that one CPU scheduler in the kernel, but you can set a specific scheduling policy for a running process to optimize its behavior. There are however multiple I/O 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? CFS is the new default scheduler from 2.6.23 on and replaces O(1).

--mm line

[Enderandrew]

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.

Isnt this called Cron?

[TheVelvetFlamebait]

I thought Linux used Cron as a scheduler ?
 

Re:Isnt this called Cron?

[Anonymous Coward]

That is for scheduling background tasks that run once a day (or whatever you set it to)

This is for scheduling CPU resouces in real time. To decide if Firefox or Apache is going to be executed the following split second.

Re:Isnt this called Cron?

[bioglaze]

Yeah, and it performs better with Cron Kolivas patchset :-)

Anyone with kids can tell you...

[s_p_oneil]

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

Re:Anyone with kids can tell you...

[Burdell]

Yeah, but then when you get three threads, it gets more complicated. Also, one indecisive thread, and everybody stands around and complains while the one tries to decide which slice to take.

Re:Anyone with kids can tell you...

[complete loony]

Look, if you two threads can't learn to cooperate, neither of you will get a time slice.

Completly fair = communist?

[smartdreamer]

So does Linux reached the computer's communist's holy grail?

Re:Completly fair = communist?

[maino82]

in communist kernel, task schedules YOU!

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:Improve how?

[detain]

Its been already said, but ill repeat just for completion.

Basically right now the scheduler is unbiased, giving ticks to all applications regardless of their need for processing time. An example of this would be in X windows when you have little taskbar icons that rarely do anything, vs having cd burning software running.

The scheduler will quickly learn that most of the time it asks the taskbar application if it needs to do anything, it doesnt, and that most of the time it asks the cd writing software to do anything, it neeeds cpu. So very quickly it will start checking on the cd writing process more frequently than the taskbar process. This will give you a very noticable performance increase in your system.

With this in mind, there should be a very noticable performance increase in all desktop and server systems. This scheduling change is a very big addition to the main branch of the kernel. Its been available for some time in various kernel patches but the fact that its making it to the main kernel branch means its matured enough for prime time and its been ackhowledged as benefitial to the linux kernel.

I for one am anxious to try this out on all our systems. From what Im reading it has some fine tuning options which should be really nice to play with.

Re:Improve how?

[the_greywolf]

CFS and Con Kolivas' SD both aim to improve interactivity of processes under high load - in particular, the goal was to reduce scheduling latency for applications which have realtime needs - like audio players. Con Kolivas has been maintaining variations no his low-latency Staircase design for several years with precisely that goal in mind.

On the desktop, it improves latencies for (for example) music players and 3D games, improving performance and elimingating jitter, lag, and general choppiness. Both SD and CFS achieved this under loads as high as 50.

On the server, it can have several benefits, including improved time-to-network latencies. They both want and need test cases for servers that show no detrimental effects. If you want to help, you can try out CFS on a server and report to Ingo if there are performance or latency issues.

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:Improve how?

[ultranova]

The scheduler will quickly learn that most of the time it asks the taskbar application if it needs to do anything, it doesnt, and that most of the time it asks the cd writing software to do anything, it neeeds cpu. So very quickly it will start checking on the cd writing process more frequently than the taskbar process. This will give you a very noticable performance increase in your system.

How did this rubbish get modded informative ? Is it someone's idea of a joke ? Or do people simply apply the "informative" mod on things they know nothing about ?

The scheduler doesn't "ask" the processes anything. It goes through the list of runnable tasks - the tasks which aren't currently blocked waiting for data to arrive from the network, the user to press a key, some time to elapese, or something else - and decides which one should run next, and for how long. After it has run, it picks the next task, and so on.

The "taskbar processes" are inactive because they are blocking on a socket (which connects to the X server), waiting for message from X server, which might carry user input or whatever. They aren't in the runqueue so the shceduler doesn't have anything to do with them. Only once they receive the message they've been waiting for do they become runnable again, and thus subject to scheduling.

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:Isn't This Called Cron?

[TheCoelacanth]

No.

Cron schedules tasks to execute at specified times. This article refers to the kernel's CPU scheduler which determines which running process gets to use the CPU at any given moment.

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.

hmmmm..........

[Sillygates]

What version of KDE are you running?

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

[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

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

[tglx]

> 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

Re:Poor attribution

[Anonymous Coward]

here is Linus' take on this issue:

A big issue for me is also the difference in how Con and Ingo took criticism. Both SD and CFS were criticized by various people over different things, and quite frankly, Ingo ended up trying to figure out why something didn't work, while Con ended up getting involved more in flame-wars with the people who criticised SD. Is that important too? Yes it is.

The full posting of Linus is at: http://bhhdoa.org.au/pipermail/ck/2007-June/007856 .html

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

[Anonymous Coward]

I'm not a kernel developer but happened to be reading the mailing lists when the "CFS" originally hit the scene a few months ago.

Basically Ingo Molnar, the author of CFS, who is also the maintainer of the scheduler in the kernel, opposed the inclusion of the competing SD scheduler from Con Kolivas for years. Then he claimed that he was just suddenly inspired to whip up a new scheduler that addresses the exact same problems. He then did so in "62 hours".

If you start at this point and read the next 20 or so messages it gives a pretty clear flavor of how things went down. ( the 62 hour comment is in there too).
http://www.gossamer-threads.com/lists/linux/kernel /755787#755787

you'll note that Ingo's defense is to use smileys and to tell some guy that he's a BSD developer and therefore doesn't understand Linux and should therefore butt out. (I also enjoyed the comment about how having pluggable schedulers is not desirable because it would confuse people. Not like there's already io schedulers, for example. )

After 10 years of working with developers in corporate land, to me it reads like a clear power-play followed by some significant chest thumping. On technical merit the scheduler sounds fine, but on process it was clearly crap and resulted in an obviously skilled and motivated contributor being driven from the world of kernel development.
(some have already posted this link: http://bhhdoa.org.au/pipermail/ck/2007-June/007893 .html )

i'll just post AC since i don't really want this to come back and haunt me in the future (yet i still feel compelled to say something on the topic)

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?

It's Worse Than That

[grcumb]

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

CFS vs. O(1)

[Ingo Molnar]

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

[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:CFS vs. O(1)

[eggnet]

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:CFS vs. O(1)

[Elladan]

Ingo,

This kind of a silly thing to say. I mean, all terminating algorithms on a finite machine are O(1) ultimately.

For example, your 1 gig machine only has 2^(1024*1024*1024*8) states it can go through to reach an answer, not including disk IO... and as we all know, O(2^[1024*1024*1024*8]) =~ O(10^2585827972) = O(1). :-)

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?

Re:CFS vs. O(1)

[Champion3]

Remember that the formal definition of big-O notation says that it holds _for_all_ n greater than some n0. But in this case n has a clearly defined upper bound. This argument is not new; it's used in realtime systems as well.

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: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:Does this mean that the O(1) scheduler was bad?

[ArbitraryConstant]

"This update seems to have come relatively soon after the O(1) scheduler (about a year?) which is relatively quick for changes to really important low-level parts of an operating system. Does this mean that the Linux community was relatively unhappy with the O(1) scheduler which was touted as a very good thing at the time"

The Linux O(1) scheduler has been around since 2002.

It's pretty good, but there are corner cases where you can fool it. For example, if a process classified as interactive goes CPU-bound, it can cause starvation for other processes.

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.

Ok, here's your Microsoft bash

[Weaselmancer]

You can download it here. Screenshots here.

Re:Ok, here's your Microsoft bash

[jasonwea]

Nice pun.

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

Re:How does it relate to disk IO?

[Ingo Molnar]

Hm, that seems to be more of a VM/IO-scheduling problem than a process scheduling problem.

Did you have a chance to try Peter Zijlstra's excellent per-bdi patches, as suggested in the bugzilla?

But in general, CFS ought to improve such workloads too (to a limited degree), in terms of not making any IO starvation worse by adding CPU starvation to the mix :-)

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:Politics are destroying Linux too

[Ganesh999]

> Ingo please comment on this because I have read similar stories elsewhere and would like to hear a
> 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 /. article. (Direct link to full KernelTrap article not provided, in the hope of saving the site from a slashdotting).

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

Re:Politics are destroying Linux too

[ultranova]

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.

No, Kolivas has definitely withdrawn from kernel development. From his -ck mailing list post:

All interest I have in kernel development, even out of the mainline spotlight, has been... abolished (I had nastier words but decided not to use them.)

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

So, I've had enough. I'm out of here forever. I want to leave before I get so disgruntled that I end up using windows. I may play occasionally with userspace code but for me the kernel is a black hole that I don't want to enter the event horizon of again.

Re:Politics are destroying Linux too

[Ganesh999]

> No, Kolivas has definitely withdrawn from kernel development. From his -ck
> mailing list post:
>
> "So, I've had enough. I'm out of here forever."

I stand corrected. What a shame that it spiralled this far.

Conrad

You mean for....

[EmbeddedJanitor]

the preemptively challenged.

Then there's the American Dream sheduler where you get priority if you work hard at it. You can't just inheret your priority like some rich child process.

Re:You mean for....

[CmdrGravy]

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

Re:You mean for....

[Plutonite]

I long for the day when processes will no longer be judged by the digits of their pid, but by the niceness of their cycles!

Also, in Soviet Russia, nice tasks preempt YOU!

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

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:Why isn't a round-robin algorithm fair?

[grmoc]

Lets say that the machine was running for 100s.
50 seconds of that time, it spent running process A.
50 seconds of that time, it spent running process B.

The 50 seconds of A may be distributed differently by different algorithms.
In some algorithms, A will run for 50 seconds, and then B will run for 50 seconds.
Obviously, this is not the best when you want some interactivity...
In other algorithms, the running of A and B will be interspersed, for instance, A may run for 200ms, followed by B for 200ms, etc. until the 100 seconds is up.
This gives a more interactive system.

Note that both of these algorithms give a 'fair' amount of time to each process, but one is only fair when 'fairness' is computed at the end.

A "better" algorithm, e.g. Inigo's CFS, EDF, GRRR (GR3), VTRR, etc. will also attempt to be fair on -small- timescales with divergent (and possibly grossly divergent) weights.

Wikipedia has a fairly nice page with links to more information:
http://en.wikipedia.org/wiki/Scheduling_(computing )

Re:It will not do any good for heavy loads

[bradbury]

Sigh... I can't believe I'm giving tutorials on /. :-(
The man page is worthless (and if the universe had any sense of justice many of the Linux man pages would be rewritten).

If one has a shell command file, "loop" containing...
    EXPR=1; while true; do EXPR=$[ $EXPR + 1 ]; done

and one says:
    nice -19 ./loop
then CPU usage goes to 100% and a glance at the nice column on the System Monitor reveals that a shell is running "loop" with a nice value of "19", i.e. the system is quite responsive.

If one (as root) says "nice --19 ./loop" you will also see CPU usage go to 100% and the System Monitor reveals that the loop shell is running at a nice value of "-19". *And* your system will be performing like a dog. You will not even be able to get the mouse to move "reliably" (this is on a Pentium IV @ 2.8 GHz).

Negative "nices" are are a lower numeric value but a "higher" effective priority (i.e. they get greater CPU time slice allocations).

For those of you who want the history on this, this is because in UNIX version 6, the priority of a process as well as the nice value were kept as signed bytes. Priorities less than zero were negative were system priorities which could not be interrupted. Low value positive priorities were system priorities which could be interrupted. User priorities started at 100. They could be niced to -20 (100 + -20 = 80) or +19 (100+19 = 119) as "starting" points for the scheduler (lowest priority got the CPU). If I recall, the running process had its priority bumped with each clock tick -- so it would go 101, 102, 103, etc. If niced its effective value would go 119, 120, 121, etc. The scheduler did a complete scan of the process table every few clock ticks and reset the priorities so that the totals wouldn't get above 127. You have to remember in the "old" days (1974-5), memory (for storing priorities and nice values) and CPU time for scanning scheduler tables (which are cheaper than linked lists) was expensive and programs were written to get the job done using as few resources as possible.

The problem we now have is that too many system developers (be they Linux kernel developers or Firefox developers) think resources like CPU time and memory are in infinite supply. This of course leads to [1] & [2].

I run both my Gentoo Linux package "emerges" (which can take many hours depending on # of packages) and my Firefox builds (which generally take about an hour) at "nice -19" but it doesn't do any good because the scheduler isn't designed to handle high CPU loads resulting from a process collective (build) vs. low average CPU loads (but potentially high burst loads) associated with long running processes (e.g. X11, mplayer, etc.). It would be very nice if I could actually *use* my system for editing, browsing, etc. while I'm running background system maintenance or development tasks.

1. The "Oh, throw another core at the problem" mentality.
2. The "Oh, throw another GB at the problem" mentality.

Of course..

[Ztream]

"Hello. My name is Ingo Molnar. You killed my task. Prepare to die."

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.