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

[KDR_11k]

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, they wanted us to use Qt, they gotta live with the consequences).

Re:crap

[packeteer]

You have a good point that Linux shouldn't only be attracting new users. However I imagine that if Linux did reach large numbers of new people things would be really incredible. If you like Linux now imagine how it would be with much more hardware vendor's support along with games and most applications working on Linux.

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

[Anonymous Coward]

Then you were doing it wrong.

First, storing anything inside a widget is completely backwards. It also happens to be how the Win32 API works, and how all Microsoft GUI libraries work, so it's a common (and perhaps forgivable) mistake. Ignoring the fact that a displayed list really shouldn't be the same thing as a stored list, it creates all kinds of synchronisation issues, and it's really, really slow. Inserting thousands of entries into any list or table, in any GUI library, will slow things down.

The correct way is to store the data somewhere, and then tell Qt how to get at it. When Qt needs to (say, when the control needs to be redrawn, the user scrolls the table, or you update the portion that's currently being displayed), it'll fetch the data. It doesn't matter if your table contains fifteen elements, or the entire set of integers from 0 to 2^128. Qt will remain fast.

Second, why were you updating a table that often? Nobody can read fast enough to keep up with that.

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

[Anonymous Coward]

Nitpick:

  "what's wrong with Qt/KDE, particularly the new versions (the ones still in Alpha)?"

I consider myself to be a fairly advanced user. I program. I've had jobs as a systems administrator. I use Linux wherever I possibly can (ie, wherever an employer doesn't require me to use Windows). I use KDE as my desktop.

With that said: The development of Qt/KDE ain't my ball of wax. I'm not about to use an alpha version. You expect regular, plain-vanilla users to use an alpha version of a big, complicated piece of software? That's crazy...

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]

Perhaps you should try the scheduler. I've been running it since it's conception, and my system has never run smoother.

Re:crap

[Loki_1929]

While responses like this remain the norm, Linux will never overtake Microsoft's OSs as the dominate force behind modern computing. If you think berating those attempting to develop applications for Linux is going to help things, you're absolutely wrong. And if responses like this are all that come when someone's trying to use Linux for something and is having trouble, then there's no reason to continue trying to use Linux. Microsoft's offerings (with the exception thus far of Vista) have been getting more reliable and more powerful pretty consistently since Windows 2000. I develop applications used on both ends, and the C# ASP.NET apps run just as reliably as anything else I've ever coded, yet take 1/10th the time of doing the same work in something like PHP/MySQL.

Bottom line? If you really give a damn about Linux and want it to get the support from large companies which will propel it forward, you're going to need people on the inside of those companies using it and using it effectively. If you can't come up with a constructive comment, perhaps keeping your mouth shut is the best approach. It's not what you say; it's how you say it.

Re:crap

[Gulthek]

Programmers that code well will, programmers that don't won't. If a programmer can't recognize the best tool for the job, why should we do it for him/her? Other programmers that do recognize the best tool for the job (be it Linux, Windows, OS X, BeOS, Atheos, or whatever) will fill the void they leave behind.

Re:crap

[KDR_11k]

It's basically a packet sniffer for some special sensor hardware, updating that fast is simply a requirement. Don't ask me how they're intending to read it, they wanted it and we can't say no then.

Re:crap

[KDR_11k]

I'm not sure what you mean with telling it to look elsewhere because all I could find to add stuff into a table was addItem and QTableWidgetItems. We didn't see a performance decrease from table length, the load remained constant independent of the length but that constant was too high for anything approaching a stress situation.

As for the update rate, that was a requirement, we can't do anything about it.

Re:crap

[Loki_1929]

Why should you? Because those developing exclusively for Windows will help them, but will help them do their work on Windows. Laugh at Monkeyboy Ballmer all you want, but ask yourself how well that iPhone's going to do in the long run without an SDK.

Developers are the life and death of any platform. Nintendo had something like 96% of the North American gaming market and proceeded to squeeze the life out of their developers in the 1980s. Now they're just getting back into the game (pardon the pun), having been all but eliminated from the gaming world by those giving developers an alternative to banging their collective heads into walls.

The vast bulk of coders are mediocre, average coders (as with anything). If you want some percentage of the top percentage developing some percentage of their apps on Linux, that's fine, but Windows will remain supreme unless/until something better comes along (and supports the developers). The mediocre, average application developers are the ones that have to change before there can ever be a large scale shift in the mainstream platform world. If they just get slapped down every time they try, they'll go back to what they know, and they'll go back where they know they'll get the help they need.

Re:crap

[cgh4be]

You do realize these would be two totally different groups of people. Kernel devs focus on the kernel and GUI devs focus on QT/Gnome/X/etc. There's no reason they can't work in parallel and devoting efforts to one in no way precludes devoting any effort to the other. It's no like The Linux Company, Inc. has decided to move all their GUI developers to scheduler improvements.

Re:crap

[jaden78]

That's assuming you are using X on the server.

Re:crap

[Anonymous Coward]

Watch X's CPU usage on this pure-JS page. :(

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

[The Spoonman]

iPhone's going to do in the long run without an SDK

He could call IBM on that iPhone and asked how well it worked for OS/2. Oh, there was an SDK for OS/2, but it was $600/seat. All of the MS SDKs were and still are free because it bears repeating: "Developers are the life and death of any platform". Thought the developer at the time..."Hmmm...do I pay a ton of money to have my program work exclusively on OS/2, or do I just code it for free to run on Windows and then it'll work on OS/2?"

Re:crap

[richlv]

i remember reading that once xorg was split up (in the modular stuff at version 7), they will be working on threading things out more. like, mouse control separated and being given higher priority to avoid those cases when you click on something accidentally because mouse stuttered a bit...
i hope i can say 'we all hate that' :)

i would guess this could expand in other things getting separated, thus allowing finer control over priorities. it's a good thing it got forked :)

Re:crap

[arodland]

"The server" I'm talking about is the X server, not a server machine -- so we can assume it's pretty likely that it's going to be running X :)

Re:crap

[Tweekster]

Its not like MS ever bothered implementing either of those things.

Re:crap

[Jeremi]

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, they wanted us to use Qt, they gotta live with the consequences).

I had a similar problem a few years ago when I was using a QTable to implement a system log window. It turns out the default/naive QTable object model is insufficient to do that sort of thing well. What you need to do is implement your own data-model object and have the QTable watch that instead. Once I did that, the log table was very fast, to the point that I haven't had to think about that issue since.

Re:crap

[pherthyl]

It's a common excuse to blame the toolkit for your own incompetence.

Reminds me of a post on the Qt forums once, where a user said that Qt was really slow for drawing images, like 3 seconds to paint an image to the screen, but this user said that if he used OpenGL rendering, it was acceptably fast. Some people had already replied and said that if the standard method is too slow then you have to use OGL. Instead of asking the fundamental question of why it was so slow to start with. Well after I asked, it turns out this guy was looping through the image pixel by pixel and painting them to the screen one by one. So instead of painter->drawImage() he had over 400,000 function calls to draw a single pixel, and then came to the conclusion that Qt was slow.

Every time you do something that seems basic, but the tools you have make it hard or slow to do, then you need to re-evaluate how you're approaching the problem. Especially Qt is so mature that any common task you want to accomplish probably already has a function dedicated to it and won't require more than a few lines of code.

Re:crap

[pherthyl]

Then you're doing your updates wrong or using the wrong widget for the job. An excellent Qt resource is the forum at http://www.qtcentre.org/forum/f-qt-programming-2.h tml/ Ask there and post the relevant code.

Re:crap

[gnuman99]

That is NOT the problem of the scheduler. It is a problem of the X server. The X server should kill the offending process or stop accepting requests from it.

The scheduler just schedules CPU time per process/thread based on CPU need (if applicable). It is not there to police if one process is abusing the API of another process.

Re:crap

[cstdenis]

Developers Developers Developers Developers Developers

Re:crap

[Deagol]

Although really, switching to KDE is known to have a much stronger positive effect.

Fancy desktops are for wusses. I switched from KDE to evilwm at the start of the year. Now *that* is a huge improvement in memory footprint and desktop responsiveness (not to mention getting more screen real estate). Even rxvt takes up more resident memory than evilwm. ;) If I could get apps a tad leaner than Firefox and Gaim (that don't totally suck -- Links, for example, doesn't count), I'd be a that much happier.

Re:crap

[Anonymous Coward]

Do you run Gentoo? This is not meant as a flame, but Gentoo users seem to notice differences in CFLAGS, scheduling and filesystems more acutely than the rest of us ;)

Re:crap

[Grishnakh]

So what's the solution to this mess? Re-architect the X server to be multi-threaded? Or fix the X server to prevent abusive app behavior?

Re:crap

[setagllib]

Oh I'm well aware of light WMs, having used them myself for years before finally deciding KDE was more convenient. I don't need graphical apps much (Eclipse + Firefox is plenty), but as soon as I started looking about for office suites, etc. it turned out KDE often had the best of breed, and well integrated to boot. So if I was going to run mostly KDE applications, the memory footprint of running kwin + kicker instead of fluxbox just doesn't seem like such a big deal.

KDE 3.5 performs well even on a lousy 800Mhz P3 with 256MB RAM, in a default Kubuntu Feisty deployment, and all of my production machines are a lot more powerful than that example. I'm way past the point where I can argue about resource usage as a factor in deciding a desktop environment. And even if KDE is heavier than even XFce, it's a lot more useful.

Re:crap

[arodland]

I never said otherwise. Of course the problem is the X server (and even beyond that, the problem is X), and the problem needs to be fixed at that end. That was my point, actually -- that attempts to fix it from the scheduler end are ultimately futile and in the end just add complexity, and make as many things worse as they make better :)

Re:crap

[XO]

Then there was EMX, which gave you GCC and complete access to the OS/2 API for free. And allowed easy porting of Unix-ish programs.

But, yes, part of the problem for OS/2 development was that IBM did not very well support devs. Windows wasn't exactly really hip on that, either. Until there was MSDN, it cost a bunch of money to get documentation, and compilers that worked for Windows. However, there were some non-Microsoft entries.

The Borland C++ for OS/2, was complete and total garbage. Maybe if they'd made a better product, there'd be a little more life for that product.

IBM has had a very bad way of treating the smaller users and devs. It also didn't help that the parts of OS/2 that weren't extremely excellent (like the Workplace Shell) were extremely piss poor. (The multimedia support)

Re:crap

[Anonymous Coward]

Outsource the solution.

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

Re:crap

[The Spoonman]

Windows wasn't exactly really hip on that, either. Until there was MSDN, it cost a bunch of money to get documentation, and compilers that worked for Windows.

Not so, you could always download SDKs and documentation from MS' BBS way back in the day. There was never a cost. The only significant thing a paid MSDN subscription gets, aside from those levels where you get copies of all of their software, is everything's mailed to you, rather than you having to find it. I've never, even back in the Windows 2.0 days where I started, had to pay for an SDK.

Re:crap

[Anonymous Coward]

Oh please! I downloaded the patch, patched the kernel and built it and am running it now (as I type to you). Seems to go well enough, but I haven't pressure-tested it yet. How long does it take though? On my old 5-year-old system, I can grab the patch, patch the kernel, build it and reboot in less than 25 minutes. Most of that is watching the computer work real hard.

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

[LodCrappo]

instead of psdoom we will now use pshelo_kitty?

Re:Equal opportunity, affirmative action scheduler

[jack455]

nice - run a program with modified scheduling priority As I understand it, the priorities aren't changed, nice is more of a voluntary abdication of priority? or am I confused?

Good joke though possibly too subtle...

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.

Re:Equal opportunity, affirmative action scheduler

[fph il quozientatore]

For the really touchy-feely OS out there! Nothing to see, my Boobuntu 8.08 alredy comes with it preinstalled.

Re:Equal opportunity, affirmative action scheduler

[Anonymous Coward]

Watch your lip, son; that's borderline racism/anti-semitism. ;)

Neato

[friedman101]

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

Re:Neato

[Anonymous Coward]

Read the FAQ: You will be fairly scheduled, even if you are a complete loser.

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

[arth1]

The parent shouldn't be modded funny, but insightful.

Yes, really, it is a placebo effect, and that's the intention too:
The overhead is bigger with the CFS scheduler, but since it steals a little bit away from all the slowly trudging tasks and give it to the most demanding ones, those will finish faster. And that's more noticable. I'll exaggerate for effect here, but this is what happens:
One "greedy" task takes two seconds instead of three, and that's going to be noticed. But at the same time, fifteen other "nicer" tasks take a tenth of a second more runtime each, and that's not as noticable. The overall effect is burning more cycles in overhead, with less CPU to each task on average. But since the "greediest" tasks get more CPU time, and those are the ones that are noticed, the system will appear faster. This is a placebo effect, but a well calculated one.

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

[Corwn of Amber]

What growth market? Linux has ownzored the server market long ago and still leads. (I'm not going to bother check the numbers when I remember about 70% marketshare for Apache) The growth market is on the desktop, and possibly in embedded...

I'm not concerned anyway : I've tested Vista, it told me it wouldn't play a standard DVD because "there was no protected path for HD content." Game Over, never again. "Vista is unusable forever, it's a crapware with a shiny skin."
Then I used Ubuntu some months, and while I really enjoy read/write support for every FS under the sun or in the Turing Tar-Pit, now that I installed MacOSX 'just to see' (and use Adobe software w/o Windows malware), *I'm never going back*. I'll just migrate my data to HFS+ partitions eventually... If you have a compatible PC, just try it (Hardware Compatibility List here)

Re:Neato

[Breakfast Pants]

Actually this particular type of scheduler makes basically all the wrong optimizations for a server. In a server environment, you are much more concerned with throughput than you are with latency. It is really hard to define 'better scheduler', it all depends on what you are doing.

Re:Neato

[Anonymous Coward]

you'll feel a placebo effect. Jeez, you've just gone and spoilt it now ...

Cool

[Ximok]

I had always been impressed with Linux's scheduler. The fact that it is getting better, just makes me happy.

--Insert Microsft Bash Here... not the CLI

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

[NuShrike]

I hear FreeBSD degrades gracefully also. Anybody want to comment?

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

[Ded Bob]

Might make it the ideal OS for my needs (I now have Linux on the desktop and FreeBSD on the servers).

You may want to wait for FreeBSD 7 before making the switch. It also has some pretty nice schedulers coming: SCHED_SMP and SCHED_ULE

Re:Cool

[FST777]

I've not made the switch to Linux on the desktop for scheduling reasons (have used FreeBSD for years as my primary desktop). As for the servers: if it ain't broke, don't fix it. Even when 7 is alive, I won't switch to it in the foreseeable future. When I have to install a new, separate, server, be sure that I take all the options into account.

I have years of experience managing FreeBSD servers and desktops. I have only worked with Linux on my desktop for a month or two. New servers which have to be reliable will run FreeBSD, albeit only because I can troubleshoot it much quicker than I can troubleshoot a Linux server.

Re:Cool

[Anonymous Coward]

Even Solaris 10 out of the box has a better scheduler than Linux for server applications. Doesn't matter, though. My company is moving away from Solaris to Linux, despite the fact that I keep pointing out that the holy grail for large numbers of Linux fans and developers is the desktop, not the server. It's evident in the tradeoffs that have been made in favor of desktop applications recently, such as this new scheduler.

But, somebody made the choice that we should buy x86 hardware from a vendor with garbage for support, buy support and licenses from a major Linux vendor, and cram it all together with licenses and support from VMware, and watch CPU cycles waste away rather than running Solaris 10 with zones on SPARC on one support contract from one vendor who isn't going to blame the virtualization/hardware/os vendor whenever a problem strikes.

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?

[Ximok]

My knowledge is also limited, but if I understand correctly: if a process under the new CFS system requests more processing time (like say a realtime application) it will have a better chance of getting that time in a timely fashion.

Please someone correct me if you know more.

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?

[ZachMG]

So it won't take twice the bandwidth?

Re:Process Neutrality?

[__aawavt7683]

To me, it seems to sound more like QoS:

The processes under the new scheduler are awarded CPU time as needed, as opposed to blindly. Yet at the same time, you're not discriminating solely on the user running the process.

I'd say it sounds good, but I'm not sure how internet analogies work vs processor time...

and on an off note, I really would like it to improve things cause my linux experience (wine * 3, azureus, md5summing/sorting/awking 500 meg files, multiple times in a row) tends to be exceedingly jerky, slow, and can be brought to its knees relatively easily. Even significantly worse than Windows at times. I rather want to try this scheduler to see how things go; though I just installed kernel 2.6.22 and have noticed improvement with the CFS IO scheduler. Interesting.

-DrkShadow

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?

[Chandon Seldon]

and on an off note, I really would like it to improve things cause my linux experience (wine * 3, azureus, md5summing/sorting/awking 500 meg files, multiple times in a row) tends to be exceedingly jerky, slow, and can be brought to its knees relatively easily.

Do you have enough RAM? That sounds more like thrashing than any kind of CPU scheduling issue.

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?

[Tacvek]

I think nice levels have more to do with that.

I'm thinking what is going on is that programs are often returning part of their timeslice (perhaps because they are waiting for something, so each cycle consists of a breif check of that, followed by returning the rest of the timeslice) will be able to get a larger percentage of the CPU time later, such that the average amount of time the program gets is the same. Basically the idea is to ensure that if there are 'n' processes running, overall they will each average '1/n' of the total CPU time (assuming all have the same nice levels etc.). But I may be totally wrong here too.

The most simple (but terribly naive) scheduler would be one that gives each process a slice of time, in some order, perhaps by the process number, repeating at the beginning when it reaches the end. Obviously that does not allow for many complications, such as processing having different nice levels (priority levels), and processes that give back part (most) of their timeslice some of the time would end up having much less total CPU time over (for example) a 5 minute period than one that always used all of its timeslice.

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.

Re:Process Neutrality?

[Goalie_Ca]

Attach some processor afinity code and you'll have a very very effective multi-core scheduling. I suppose that the "ready" cue on a 4 cpu core will be basically empty at any given moment.

Re:Process Neutrality?

[Anonymous Coward]

Fair enough, but I don't see how that applies to this scheduling algorithm -- the algorithm for which the analogy to net neutrality was made.

Re:Process Neutrality?

[xenocide2]

More like, do you have a multicore? Wine is good, but not very efficient. Which might be okay, except he's claiming several background disk intensive processes. A faster disk would likely also help. So now you've got a potentially CPU loaded system trying to juggle disk access in the background. DMA helps, but perhaps it's leading to excessive amounts of locking? As in "well, wine could continue, but it needs access to kernel structure slab which is currently locked until DMA completes".

An easy way to diagnose this is to put up a system monitor that displays, system, user, iowait and idle times. GNOME's system monitor applet does this but has a horrible default iowait color indistinguishable from black. Make it yellow, since it's drastically different than sys or user times ;)

Re:Process Neutrality?

[kcbrown]

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.

Well, if you want "fair and balanced", then you want...

Windows! The "Fox News" of operating systems!

Re:Process Neutrality?

[Anonymous Coward]

So there is an analogy. But the analogy isn't with a tiered internet.

It's more like a car ...

Re:Process Neutrality?

[The Raven]

This isn't as strained as an analogy as you might think.

As long as the scheduler gives priority to realtime tasks and GUI threads, it's neutral. But if, say, the new scheduler decided to boost the priority of Quicktime threads, and lower the priority of MPEG threads... then we might be arguing for scheduler neutrality too.

It's not about prioritizing a TYPE of service, but about prioritizing a particular VENDOR.

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.

Re:Kernel building is pretty fast

[that this is not und]

That's just the thing, though. To rebuild 'a different OS' it depends on how the OS is designed. The Linux kernel itself is not an OS. With most 'distros' there is no unified build process. To build NetBSD, for instance, you start with two source trees, a Kernel source tree and a 'base userland' source tree. Two make commands. With Linux you're at the mercy of whatever assorted build methods each bunch of components requires. There are Linux kernel-base OSes that have pulled together a unified build, but even those are 'pulled together' collections of source, not a controlled set that can be tagged and pulled from a single CVS tree.

If you're talking about Windows or OS/2 or something of that sort, much more uncertainty is introduced.

Re:Kernel building is pretty fast

[Anonymous Coward]

As a former Windows Builder, and a Gentoo user... it takes a lot longer to 'build' "Linux" than it did XP or even Longhorn, but the results are infinitely more satisfying and stable.

Re:Kernel building is pretty fast

[Walter Carver]

He is talking about the kernel, not the whole 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?

[bubulubugoth]

Giving more time to more demanding applications.

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.

With this "fair" approach, the waiter is floating, looking at the dishes and knowing his customers, and will provide attention if the customer ask for it, or if the waiter "feels" that the customer will ask for something if offered...

So, the trick about this "fair multitask" is to mediate, between really greedy customers, and very lazy customers, and give enough time to each, so you, as user, feel that the application you need to run fast, for example, a photo processing application, really gets more cpu's time, than for example, that nifty system tray g-mail email notifier...

So, your overall feeling is better performance with the same hardware.

This can also applies to servers...

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?

[DigiShaman]

With this new scheduler, I'd better expect a very responsive GUI with silky smooth motion. Unless however, the KDE or Gnome is the limitation in this area.

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?

[Anonymous Coward]

Sigh...you know just enough to sound like a clueless fucking moron. Obviously, it only gives runnable processes CPU time.

Re:how it's possible?

[dryeo]

Well I hope it really works this way. One reason I still don't use Linux is it is just to jerky for a desktop system. As a server it is great but who needs to click on a link in Seamonkey and the mouse stalls along with everything else?
I've run various versions of Linux and each release seems worse. Slackware 2 (Kernel v1.3) felt really fast and I used it quite a bit. 2.0.x kernels were pretty well as good then and the 2.2.x not much worse. 2.4.x kernels would periodically swap everything to swap and the system would come to a halt. Meanwhile the foreground app seemed to get more and more starved for cycles. Now I periodically boot into Linux, get frustrated with how slow it is, install Fluxbox, and still be frustrated by how slow it is.
Meanwhile I would run the same apps in X under OS/2 and have a smooth computing experience.
I think the saving thing for Linux is most people are coming from Windows and just expect a slow experience.
I'm still running under OS/2 and generally things are smooth. Set up as a desktop system (priority=dynamic) the foreground app gets a priority boost as well as an IO boost while the background apps still get a decent amount of CPU.
There are also other priority levels if you don't care about something getting cycles or even want them to get cycles no matter what for time critical apps.
I'll have to migrate to Linux again eventually and I would really like it to be smooth and also it would be nice if it was configurable, eg which mouse button does what, what a folder looks like and this text app uses this editor and this text app uses this other editor without having to click through a list.
Sure wish IBM way back had actually released the WorkPlace Shell as open source. It could of been fixed, expanded and we would have a great desktop system in Linux.

Re:how it's possible?

[the_greywolf]

Then you will definitely appreciate the new scheduler. It improves nearly all common cases, and (based on my experience with Con's SD scheduler, which CFS is "inspired" from) it makes the whole system snappier, more responsive, and more usable. It's really quite a night-and-day difference.

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?

[Schraegstrichpunkt]

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.

Yeesh. How on earth did you get the idea that you should be commenting about how the Linux scheduler works, since it appears that you don't know what you are talking about. Basically, only processes with task->state == TASK_RUNNING get CPU time. Processes that are waiting for I/O to complete or for a signal to be delivered don't have task->state == TASK_RUNNING.

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?

[Anonymous Coward]

Well for god's sakes, this is what I love about open source... the gentleman who wrote the thing pipes into a public discussion forum with his comments :).

Re:how it's possible?

[slashdotmsiriv]

... and this people, is why we read /. !

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?

[mystran]

I'd guess the idea is that if you are going to give each of two CPU hogs exactly 50% of CPU, you don't need an explicit timeslice as such, only some threshold of how much difference is 'unfair' enough to pre-empt the process. Say, we set the threshold at 2% then we run process A until it's got 51% of CPU, at which point we run process B until it's got 51% of CPU and so on.

For the simple case of two processes then, it seems like we have timeslices, but once stuff starts changing dynamically any "timeslice" can basicly become arbitrarily short or long.. and ofcourse we don't need to consider the threshold value at all when we consider which process to schedule, because it would only be necessary to avoid constant pre-emption when two competing tasks are already in balance.

Could ofcourse be that I've completely failed to understand the CFS concept, but the above I'd guess based on what the author explained above.

Re:how it's possible?

[Anonymous Coward]

alright.. why did this drivel get modded 2 informative ..

come on .. "how it's possible?"

"how's you's so stupids?"

that's it . I quit.

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.

Re:how it's possible?

[justthinkit]

[The old O(1) scheduler] mostly boils down to 'sleepers get more CPU time than runners'.

Isn't this guaranteed to melt down response times at a point well less than 100%? As the system gets more loaded down, more tasks are sleepers...so one of these gets activated...but it runs for less time because there are even more sleepers...so one of these gets activated for even less time... To risk an analogy, the old O(1)'s scheme sounds like "as the waiter gets more and more busy at the restaurant, greeting new customers becomes more and more of a priority".

As early as Windows 3.x you could set the time slice interval (I think it defaulted to 50msec) -- hopefully the Linux schedulers have a minimum-time-needed per-slice-or-else nothing-gets-done setting.

/me ducks back into the shadows...

Re:how it's possible?

[Doctor Memory]

I guess I missed the obvious part of 'most applications get "time", even if they don't need them [sic]'. Actually, I was trolling for more information about the scheduler, under the guise of poking fun at the OP. And I got it!

Thanks for flaming!

Re:how it's possible?

[Anonymous Coward]

Processes ready and waiting for CPU time are not considered "sleepers." Sleeping is waiting for some other external event like a timer expiration or I/O completion.

Re:how it's possible?

[Corwn of Amber]

Actually, Beryl did make my Linux experience a happy game. The desktop cube is the only feature I find lacking in MacOSX.

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.

Isn't This Called Cron?

[Anonymous Coward]

I thought Linux used Cron as a scheduler ?

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.

Found the punchline

[lawpoop]

I've found the punchline:

I think I'll wait for the unbelievably fair scheduler, or perhaps the ridiculously fair scheduler. Props to tji.

Re:Found the punchline

[lunchlady55]

Don't PREPARE the ludicrously fair scheduler. Just GO!

(It's gone PLAID)

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.

Re:--mm line

[MrNemesis]

Shame to see that the -ck branch is now dead :(

http://bhhdoa.org.au/pipermail/ck/2007-June/007893 .html

Re:--mm line

[BiggerIsBetter]

I'm still not sure if it is better than Con Kolivas' SD scheduler in his patchset, but we'll see.

Well, the CK patchset has been formally discontinued... the reasons for which appear to be related to this (and it seems that CFS was related in many ways to SD as well).
http://artipc10.vub.ac.be/serendipity/archives/32- The-end-of-the-CK-kernel-patch-set.html

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

I liked the old O(1) scheduler

[OrangeTide]

I thought the design was pretty elegant. although in practice we've been having huge problems getting Linux to scale past 32 or so CPUs. partially the locking and partially because the scheduler is not smart enough to schedule complex workloads effectively that you see on huge SMP systems.

Re:I liked the old O(1) scheduler

[Anonymous Coward]

The schedulers we're talking about are per-CPU. The spread of tasks over different CPU's happens somewhere else. SGI has beens scaling Linux in the 1000's of processors count, so perhaps an upgrade of your kernel might be in place.

Re:I liked the old O(1) scheduler

[OrangeTide]

per-CPU schedulers do not handle complex work loads well. SGI's 1000s of processor systems also do not handle complex workloads. SGI stuff is always extremely fast, but weird/unconventional in behavior. If you give those big machines the specialized kind of work they are designed to handle they perform amazingly. But if you're looking for a general purpose 128-node server, Linux 2.6 can't deliver. (Solaris can, and Linux is very close)

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.

Re:Anyone with kids can tell you...

[bar-agent]

Did you know this technique -- A divides, B gets first pick -- has been extended to arbitrary numbers of agents? But it gets tricky. I read an article about it in Discover years ago, and there's a book for laymen that explains it all. See also fair division.

"And now for something COMPLETELY FAIR." (NT)

[Anonymous Coward]

no, not the NT scheduler... "NT" stands for "no text," silly!

This comment intentionally left blank (except for this bit... and the bit above)

Re:Buried

[stonedcat]

There's a shitty site called digg and several look-a-likes out there for people like you to feel power in the news others post. Go troll there.

Re:Buried

[Anonymous Coward]

If you want an intelligent discussion, read the Linux Kernel mailing list. If you want infantile and sophomoric prattle, stay here.

The hope is

[Anonymous Coward]

I believe to expose multiple tasks to as much bandwidth as possible, fairly.
Isn't that kooky?

Completly fair = communist?

[smartdreamer]

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

Re:Completly fair = communist?

[Curufinwe Melwasul]

Well then processes would have to:
1. stand in line to get a ticket for some cpu time
2. stand in line to get the cpu time...
3. find out that there is no more cpu time available
4. come back the next day and go to 1

Re:Completly fair = communist?

[maino82]

in communist kernel, task schedules YOU!

Re:Completly fair = communist?

[Anonymous Coward]

Ah, but now some get a VIP pass to the front, while others have to take the piss and wait.

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?

[Anonymous Coward]

Really? I have had the exact opposite experience with Windows NT based kernels compared to Linux kernels. Audio and video are regularly choppy on Linux, reboot to Windows, and no choppiness.

My understanding is that the NT kernel, which was designed by the original VMS architects, allows for preemption while executing in kernel mode. However, Linux, in it's unpatched form does not allow preemption while in a syscall. This had made Linux unsuitable as a RTOS and for multimedia unless the kernel is patched.

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?

[the_greywolf]

Ingo's posts could explain far better than I. Suffice to say, a running task won't be starved CPU just because another process has come along to snatch it away. The previous scheduler didn't do this, and seemed to favor processes that needed far less CPU.

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

[Anonymous Coward]

I'd mod you up informative but I know nothing about scheduling. Irony!

Cool-If Bush wrote operating systems.

[Anonymous Coward]

"I had always been impressed with Linux's scheduler. The fact that it is getting better, just makes me happy."

I like the "No task left behind" scheduler too.

Great name

[Anonymous Coward]

Of course, the next one will be the Completely Amazing Scheduler, followed by the Completely Wonderful Scheduler, followed by the Absolutely Perfect Scheduler, followed by the Even More Perfect Scheduler...

Re:Great name

[Anonymous Coward]

I'm waiting for the Perfect ASS (Absolutely Stunning Scheduler)

hmmmm..........

[Sillygates]

What version of KDE are you running?

Fairness

[bdjacobson]

What is it about us nerds/geeks that we like things to be completely fair?

Also, lately I've found that life is a lot less stressful when you stop worrying about things being fair or not; and stop worrying that you might have gotten the short end of the stick. Another thing-- all those dreams of grandiosity every nerd/geek has (wooing the beautiful girl, or being the life of a party, etc; but just can't seem to accomplish), you feel far more empowered to do them when you get a full night's sleep, as opposed to staying up running that instance again for the loot, and then being tired the next day. If you treat your school/college work like a game that you want to master (for a very real benefit I might add-- sure, being the best at Fourier transforms might not net you a top NSA job because the government network was brute-forced in 15 seconds by Megatron's minions, but there are more subtle ep33n enhancements that can add up to something similarly lofty in enough time) the point becomes to learn the material not just finish the problems and turn it in. Then you start getting 100's on tests and it feeds back into itself and you know if you want to accomplish something, you can. Then you have fun and try updating your clothing and hair style, and then when you're really cooking you start walking around like a badass because you know you are one. Quite fun actually. But you never get there if you don't learn to give up the petty things (fairness) that get under your skin for the bigger picture of learning to control your charisma.

Completely Fair?

[Anonymous Coward]

I think I'll wait for the unbelievably fair scheduler, or perhaps the ridiculously fair scheduler.

Re:Completely Fair?

[Anonymous Coward]

...or the Totally Fair Scheduler, or the Way Fair Scheduler...

Preemptive Kernel?

[Anonymous Coward]

Last time I looked, execution could not be preempted when in kernel mode. Has this changed yet?

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]

Tell him to build his own kernel.
That what people who make their own drivers do.

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

[the_greywolf]

That's precisely what he's been doing for years, and he's all but given up on it because of all of his failed attempts to get the kernel devs to look at his code. It's only in the last few months that Ingo bothered to take Con's ideas seriously.

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?

Re:Poor attribution

[Anonymous Coward]

Actions speak louder than words. Whose code actually got the final merge?

Re:Poor attribution

[the_greywolf]

Here's how I see it:

Con sees problems in the process scheduler. He knows no one else will fix it, so he takes a little bit of free time from being a medical practitioner to hunkerdown and figure out how to "fix" the scheduler. He does so. He succeeds in improving the interactivity of Linux 2.4-based systems. 2.5 becomes 2.6, and Con moves his efforts there, trying to get Ingo to accept his new scheduler design. Ingo writes the "O(1) scheduler." Con keeps improving his staircase design, still trying to get Ingo to give it a chance. Years pass.

Con finally convinces a number of kernel devs to see that the existing scheduler sucks and that Staircase is a vast improvement. Ingo writes CFS. 4 weeks later, he effectively declares CFS to be "done" and ready for the kernel.

Con has spent YEARS working to perfect his scheduler design. Now, finally, people are taking his approach seriously, and Ingo undercuts him by putting his scheduler in the kernel and not Con's.

Con is very obviously sick of the bullshit. He's tired of trying, and it's adversely affecting his health. He was bedridden and still managed to fix what few bugs had shown up in his latest RSDL implementation. And Ingo is merging code a few weeks old? A still-flawed design that hasn't been tested enough?

This is UNFAIR. Both to Con and to users of Linux. Con has been getting the short end of the stick for far too long.

What I think the appropriate attribution should be is this: Ingo should flatly state that CFS is a rip-off of RSDL. He should admit that the only reason CFS exists is because of Con's RSDL. Ingo should admit that CFS is young and poorly tested and that RSDL is a mature, solid, well-tested design. Con didn't "pioneer the fair scheduling approach." Con opened Ingo's eyes to the fact that the old scheduler is a piece of shit.

Ingo should get on his knees and worship at the shrine of Con Kolivas.

Yes, I'm bitter. I'm sick of watching this.

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

Re:It's Worse Than That

[Anonymous Coward]

Nearly wet myself. Thanks!

Does this mean that the O(1) scheduler was bad?

[iammaxus]

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?

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.

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)

[Anonymous Coward]

He understands, it's just getting twisted a bit. =/

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)

[John Nowak]

The upper bound though is a result of the PID limit, not because the scheduler itself has some incremental algorithm with clearly-defined time bounds. If the PID limit were to be increased, the maximum time taken by the scheduler would increase logarithmically. Claiming that some data structure will exhibit O(1) performance just because you artificially limit how many things can be stored in it doesn't make much sense. You may be right that this argument is not new, but if that's the case, it seems unfortunate.

Re:CFS vs. O(1)

[IkeTo]

> I also have no idea where ~20-21 came from, as the maximum depth at four million is higher
> than that.

That 20-21 number might be wrong for the "depth", but would be about right if he is talking about the "black depth" of the red-black tree (a red-black tree of depth 22 contains 1+2+...+2^21 = 2^22-1 = 4M-1 nodes), which is at least half of the actual depth. So the actual depth is no more than 44 (actually a bit less).

Re:CFS vs. O(1)

[Elladan]

This is true, but again, kind of silly.

All algorithms on a real computer have a clear upper bound, be it 2^32 (integer limits), [memory size]/data structures (allocation limit), or ultimately 2^[memory size] (state limit).

In practice, it's fairly useful to do this for a particular real-time system, because it allows you to place numeric bounds on the running time of a component. But in that case, you're not really looking for the big-O number: you're looking for the worst case time it takes, hence, the actual runtime. O(ten quadzillion) isn't very useful in practice.

Or to put it another way, a CPU scheduler that operates using a bubble sort is also O(1), since a computer can only hold so many processes in RAM.

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

[Ingo Molnar]

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

You are nitpicking :-) But let me nitpick too: your 1 git machine has _a lot more_ states than 2^(1024*1024*1024*8). It is described by a quantum wave function that has at least 10^28 particles in it, with each particle having infinite observable states. Even if we applied some common-sense granularity to the observation of the 4 coordinates of the particles in question, the total number of possible states is more on the order of 2^(10^28) than on the order of 2^(8gig) ;-)

See? What i said was totally accurate when in nitpicking mode, still it missed the big picture by being purist and it didnt bring the discussion forward even one inch. In fact it had the exact opposite effect - the only effect this paragraph had is maybe some extra global warming ;-)

What i tried to say with my O(1) comment is that even for the worst-case scenario, CFS's algorithms never go deeper than 15-20 in the tree. Which compares quite favorably to the 140 worst-case steps the "O(1) scheduler" has to take (on an architecture that has no in-hardware bit-search instruction).

So despite that you'd not try to point this out, just because the mathematical definition of its algorithm says O(log2(N))? That would plainly defeat the fundamental purpose of why we define ordo/theta notations: to be able to compare algorithms along their worst-case/best-case/average performance characteristics.

And if you'd try to point it out, wouldnt you do it similarly to how i did, by describing the worst-case behavior in words and pointing out the failure of the strict definition?

Re:CFS vs. O(1)

[Anonymous Coward]

By this argument of yours that the number of pid is limited and in turn it's a constant, all Linux schedulers would be O(1) no matter what. Including the one you just called the O(N) scheduler a few lines above. Quote below:

"i wrote inherited them from the original O(N) scheduler".

So make up your mind, either all Linux scheduler are O(1) (including the 2.2.x one), or you lower the hype a bit and you properly call CFS O(log(N)).

When you look at the scheduler algorithm itself, isolated from the rest of the kernel subsystem (like the pid allocator code) CFS is O(log(N)), not O(1). The old scheduler was really O(1) and it's a pity it's gone. The only thing I'm sorry about is that there's no good technical reason why multiple process schedulers can't co-exist like it happens with the I/O scheduler.

Andrea Arcangeli (Anonymous Coward not ;)

Re:CFS vs. O(1)

[Elladan]

Of course -- but I think it's a little silly to say that it's O(1). It is, but only in the trivial and non-useful sense.

The more accurate description might be: "It's O(log(N)), but that the maximum process count is such that it compares favoriably to the old scheduler in real workloads."

Of course, I'm curious as to how well your scheduler really performs on hardware. Note that doing a bit search in software (that is, a bunch of branch instructions in L1 cache) is a lot cheaper than walking an indirection tree (likely L2 or even full cache stall each time). In general, tree approaches tend to be very pretty, but don't perform quite as well as you'd hope due to cache and branch performance... Did it work out well in reality?

For small algorithms (or even medium size ones like a scheduler), I think order analysis is generally of limited use. For example, a hash table with unknown dataset size theoretically tends to be logarithmic when you consider rehashing and so forth... But a hash table is very popular because it has low average-case constants. On the other hand, devices such as hard disks can often be modelled in terms of disk seeks, in which case order analysis can map quite well to performance.

Anyway, you're quite right that the computer machine has more states than 2^[memory] as a physical device, but in as much as it creates a digital runtime environment for software to execute on, it only provides a limited number of bits to use as state. Then again, it also has a disk drive, and a network, so the actual complexity is difficult to estimate. :-)

Re:CFS vs. O(1)

[Breakfast Pants]

Hey asshole, smileys don't automatically smooth things over. You need to cut that out.

Re:CFS vs. O(1)

[Anonymous Coward]

"(disclaimer, i'm the main author of CFS.)"

You are nothing but a Linus crony. You are just not that good. Kolivas is better.

What I'd rather have...

[techno-vampire]

wooing the beautiful girl...

I think I speak for geeks everywhere when I say that I'd rather have the beautiful girl wooing me!

Re:What I'd rather have...

[bdjacobson]

wooing the beautiful girl...

I think I speak for geeks everywhere when I say that I'd rather have the beautiful girl wooing me!

No no no those are the aggressive type. A PITA to have a relationship with.

Re:What I'd rather have...

[ultranova]

I think I speak for geeks everywhere when I say that I'd rather have the beautiful girl wooing me!

In Soviet Russia, the beautiful girl woos you! It's the homeland of Vodka after all...

Re:What I'd rather have...

[HiThere]

ALL girls are a PITA to have a relationship with. And so are all guys, ask any girl.

Also, FWIW, beauty isn't all it's cracked up to be. Beautiful girls are usually the vain ones, because you don't get to be beautiful without devoting as much effort to beauty as a jock devotes to being a jock.

Also, you don't want one with the same interests. Merely compatible ideals. If you get married, you want to have a complementary relationship, where the strengths of one covers the weaknesses of the other. (I really lucked out...eventually. But it took me long enough. [I.e., a great deal longer than I wanted it to. And a few mistakes along the way that, fortunately, weren't disastrous. Only wasted a few years and a bit of money.])

Beauty. Here's a secret, that shouldn't be one. When you look at something after awhile you stop seeing it, except when you look again on purpose. Pick someone that you enjoy looking at, but don't worry much about more than that. The three of the four most beautiful girls I ever met were all borderline psycho (though not blatantly). And they all believed that because they were beautiful the world owed them not merely a living, but also most of their whims. OTOH, the absolute most beautiful girl I ever met was charming, personable, and warm as well as beautiful. (She went for someone else, the lucky dog.) Personality should rule your preferences...right after ideals. Unfortunately, both personality and ideals can't be told at a glance, so you've got to spend a bit of time. But you can enjoy the research...or at least try to. (If you don't, you're likely to miss out.)

Hint: Compliment her. Often. And don't stop when you get married.

Hint: Be affectionate, indirectly. Pet dogs sensually. People put themselves in the place of others, and imagine how they are feeling. Women like to be petted...as long as they feel safe. If you're petting a dog and she's watching, she may empathize with the dog, and imagine you petting her. (Check out mirror neurons for why this works.)

Hint: Always resolve arguments. This can be a lot of work, and you can need to force yourself to continue, but it can be crucial to your staying together. If you get into an argument with her, SOLVE IT!!. Sometimes this takes awhile, but try to resolve it before you go to sleep. Stop occasionally for a timed five minutes to cool off. (Use a timer with a bell. During that five minutes, try not to talk to each other...it's too likely to drift back into the argument.)
N.B.: Apologizing doesn't work, but it's a necessary step. But be sincere. "I'm sorry I made you mad." is often good, as it's usually easy to say this honestly.

Hint: Avoid lying to yourself. Just don't. Give yourself permission to avoid justifying, to yourself, things that you do which you consider immoral or unethical. (This isn't the same as giving yourself permission to do them. The point is to encourage honesty, so don't lie to yourself to justify it.) Try to avoid lying to others, but the crucial thing is to be honest with yourself. This can take practice, so start now.

Hint: When you are resolving an argument with your S.O., and you don't know why you did something...admit it. Then try to invent a reason...but explain that it's a guess or invention.

N.B.: These are things that have worked for me. I hope they help someone else, but no guarantees.

not unlike NT4

[Anonymous Coward]

Lets move the timeslices to ring 0 for graphics.. yeah yeah.. then all of the robust file sharing and stuff will slow down, but hey! we can make the gui more responsive..

On a more serious note, this could be cool, especially if system tasks get lower priority in favor of user defined ones, for HPC this could be alright..

Prepare for...

[Schraegstrichpunkt]

The Ludicrously Fair Scheduler!

How many nanoseconds...?

[Joce640k]

"start checking on the cd writing process more frequently than the taskbar process..."

So how many nanoseconds does it take to ask the taskbar if it wants any CPU?

I can't imagine it making a "very noticable" difference. More like 0.1%

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

[CoughDropAddict]

Complete rewrite of scheduler, again? Check.

Catchy new name? Check.

Promises that it's much better than the last scheduler? Check.

What, you're trying to tell me that complex heuristics to try to determine the "interactiveness" of processes wasn't the peak of scheduler technology?

I eagerly await the next grand rewrite when something else comes up that they didn't think through. My bets are that it will be the interdependency of I/O scheduling and CPU scheduling: what good is giving a process the CPU if it's swapped out? The VM system is going to immediately try to swap it back in, and switch to another task when this happens, and if memory is short to begin with this will just thrash, thrash, thrash (I'm sure everyone has experienced this at one time or another).

Can't wait for the "Completely Awesome Knows-About-I/O Scheduler."

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.

Process Farm?

[stinkbomb]

"All process are equal, but some are more equal than others."

Re:Process Farm?

[Anonymous Coward]

"Four threads good, two threads bad!"

How does it relate to disk IO?

[Anonymous Coward]

As an amd64 owner who's been taken aback by the very long-standing disk IO crisis:
http://bugzilla.kernel.org/show_bug.cgi?id=7372

I'm curious how this new scheduler may help/hurt me?
Deadline appears to help the problem, albeit not fix the root cause.

And is there any kind of disk IO scheduling work going on to help this in the future?
I'm really not sure why amd64 would be so broken while x86 is not. (IOMMU?)

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

Welfare scheduler

[jihadist]

Next up: equal time for processes that produce no tangible result. Soon Linux will run like the bloated bureaucratic nightmare that is the USA.

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:This is politics, not programming

[Anonymous Coward]

> This shows the black side of open source.

This is nothing compared to internal politics at large companies.

Re:This is politics, not programming

[mangastudent]

I've been watching this drama for a while ... and I must say it's extinguished any desire I had to contribute to the Linux kernel.

And parsing the exact truth of the matter is irrelevant: those of us who've been out in the real world long enough can feel in our gut that there's enough truth to the allegations that we just don't want to mess with this sort of thing, we demand payment for this sort of treatment ^_^ !

Instead, there are plenty of FOSS projects out there at all levels that don't have this degree of politics (which are inevitable, man is a political creature and all that).

Maybe FreeBSD will be SMP stable by the time I want or really need to do something like this.... But the bottom line is that I'm in no hurry, so I can carefully choose where to put my various efforts.

Re:This is politics, not programming

[Anonymous Coward]

"This is nothing compared to internal politics at large companies." - by Anonymous Coward on Wednesday July 11, @04:25AM (#19822851)

Damn straight... 110% agreement with you here!

(I've been there for 15++ years now, like you probably have, & it is NOT good (but, @ least you get PAID to be shit on in corporate environs, lol, where "soldiers (techs/admins/coders) win the battle", & "kings (mgt.) take all the credit" in mags, in meetings, etc. et al)).

Sad, but true. This? This IS life, and your statement's really about humanity in general, unfortunately.

APK

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:Ok, here's your Microsoft bash

[Xtravar]

Wow, puttycyg just made my life so much better. Thank you.

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

[LingNoi]

Ingo please comment on this because I have read similar stories elsewhere and would like to hear a response.

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

Re:Politics are destroying Linux too

[diegocgteleline.es]

It looks like most of people in the kernel considers CFS a cleaner "fair scheduler" than Con's implementation. If Ingo changed his opinion and the communication between people was not good, that's a completely different issue, but it's not that people has not considered Con's scheduler for inclusion in the kernel.

Re:Politics are destroying Linux too

[Anonymous Coward]

It's in the 3rd chapter of evil genius for dummies:

1/ Hear good idea and say no
2/ argument ensues, from it a third pattern will emerge
3/ present the new pattern ( wich incorporates all the 1/ good ideas ) as your own
4/ give mild credits to 1/ as to not look like a total bastard
5/ just feel good when 1/ leaves, it's his decision and it will make soon all reference to 3/ disappear from your public records, smile.

Re:Politics are destroying Linux too

[Anonymous Coward]

1. I tried in vain some time ago to push a working extensable pluggable cpu
scheduler framework (based on wli's work) for the linux kernel. It was
perma-vetoed by Linus and Ingo (and Nick also said he didn't like it) as
being absolutely the wrong approach and that we should never do that. Oddly
enough the linux-kernel-mailing list was -dead- at the time and the
discussion did not make it to the mailing list. Every time I've tried to
forward it to the mailing list the spam filter decided to drop it so most
people have not even seen this original veto-forever discussion.

2. Since then I've been thinking/working on a cpu scheduler design that takes
away all the guesswork out of scheduling and gives very predictable, as fair
as possible, cpu distribution and latency while preserving as solid
interactivity as possible within those confines. For weeks now, Ingo has said
that the interactivity regressions were showstoppers and we should address
them, never mind the fact that the so-called regressions were purely "it
slows down linearly with load" which to me is perfectly desirable behaviour.
While this was not perma-vetoed, I predicted pretty accurately your intent
was to veto it based on this. ...

http://www.gossamer-threads.com/lists/linux/kernel /755787#755787

Re:Politics are destroying Linux too

[ultranova]

It's in the 3rd chapter of evil genius for dummies:

Actually it sounds more like "Sociopathy for dummies". Taking advantage of people not on their guard doesn't require genius, just lack of conscience.

Dunno if it was what happened between Kolivas and Molnar, I haven't been paying enough attention to say for certain. A pity about the -ck patchset though, it has been in use in my desktop from the summer of 2005 now :(.

Re:Politics are destroying Linux too

[Doctor Memory]

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. It might also be good to point out that Ingo wrote his code in about three days (sixty-some hours IIRC), so "the loop" didn't really exist that long. It sounds like it was just one of those times when you start to play around with an idea and everything just falls into place and you wind up with something really great instead of the collection of heavily-instrumented test code you thought you'd have.

Re:Politics are destroying Linux too

[zymano]

Not politics. Sounds like jealousy and ip theft.

Re:crap - Flamebait!

[Anonymous Coward]

You, sir, are trolling. You are trying to bring up a GNOME vs KDE flamewar by posting "facts" that are exactly the opposite of what happens in reality. In most Linux distributions, GNOME outperforms KDE. The only exception might be SuSE that has a bloated version of GNOME and a bloated but slightly more optimized version of KDE. But if you compare other distributions like Ubuntu, Fedora, Red Hat, Debian and others, you will probably find that GNOME is more responsive than KDE. Thanks for the troll!

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:You mean for....

[EmbeddedJanitor]

The American Dream scheduler allocates 500% of the CPU. You just charge the other 400% to Visa.

Typical Linux user would not know

[EmbeddedJanitor]

First off, let's state that the typical Linux user is using Linux in an embedded form and does not even know they are running Linux. The hardware they are using probably will get no benefit from this new scheduling policy. A lot of systems will get far more benefit from the realtime patches that provide priority inheretance etc (ie a decidely unfair scheduler).

Re:crap - Flamebait!

[mrsteveman1]

More responsive and still very 'thinclient-like'

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.

Re:Angsty nerds are not destroying Linux

[TeXMaster]

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.

I've done this kind of stuff myself, but this is not even remotely what happened for the Linux scheduler. See also other comments in this subthread for closer-to-the-truth descriptions of what happened.

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.

Except that Con's implementation was everything but a prototype, and Ingo's implementation is not a rewriting of SD, but a different beast that shares some of the ideas with Con's scheduler (ironically, those same ideas that Ingo had dissed initially).

Better maintainenship is barely the issue here. If it really had been, Ingo could have prepared a simple framework to allow even just compile-time choice of scheduler, and then delegate the SD maintainership to Con. This would have given a much wider range of testers for the schedulers (the old one, SD, and even the new CFS), with significant means to determine which one was really better.

But no, apparently Ingo had no real intention to give SD a chance; heck, even just waiting for Con to get out of hospital would have been a sign of different intentions.

Ego? I am pissed at what happened, and my ego is not really directly involved with the events. I can just barely imagine how Con is feeling about it.

Why isn't a round-robin algorithm fair?

[master_p]

Suppose that tasks are placed in a linked list, and there are two lists: the runnable tasks and the blocked tasks.

Now suppose that we have two tasks: task A that consumes the CPU 100% and task B which is I/O bound and consumes 50% of the CPU (as per your example).

In the round-robin algorithm, each scheduled task is placed at the end of the list of runnable tasks, so other tasks get a fair chance of running.

When Task B is ready to run (because its data arrived from the network or hard disk, for example), it is removed from the list of blocked tasks and placed at the end of the list of runnable tasks.

Under the above setup, Task B will consume 50% of the CPU time, forcing task A to consume 50% as well, because ready tasks are placed at the end of the runnable queue.

Here is an example (assuming T is a scheduler time step):

step 1: task A runs for T; task B becomes ready at T/2
step 2: task B runs and becomes blocked at T/2; task A is ready
step 3: task A runs for T; task B becomes ready at T/2
step 4: task B runs and becomes blocked at T/2; task A is ready
step 5: task A runs for T; task B becomes ready at T/2
etc

So under this simple round-robin setup, each task gets 50% of the CPU, with one of the tasks waiting for 50% of the time and the other task not waiting at all.

So why isn't a round-robin algorithm fair like CFS?

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

[master_p]

But how does the round-robin algorithm is not fair in the same was as CFS? the end result seems the same.

Re:Why isn't a round-robin algorithm fair?

[grmoc]

Let me put it this way.
Instead of processes, we have people.

You give person A 1,000,000 dollars when they're born.
You give person B 1,000,000 dollars a second before he dies.

Is it fair?
In the end, they'd been given the same amount of money, right?
(The answer is no: it isn't fair :) )

Mod parent up

[Anonymous Coward]

Harsh as it may sound, this comment is really insightful.

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.

Selecting scheduler in real time stupids!!!

[Anonymous Coward]

$ iokctrl -set-sched=ingo
$ cat /proc/system/sched/policy
ingo
Bad interactivity!!!
$ iokctrl -set-sched=ckolivas
$ cat /proc/system/sched/policy
ckolivas
Good interactivity!!!

Re:AWESOME!!!!!!!!!!

[Anonymous Coward]

Maybe... but be nice, because chances are you work for one of us.

It will not do any good for heavy loads

[bradbury]

I will point out two areas where a "better" scheduler is unlikely to improve performance.

• In a case where you have maxed out memory [1].
• In a case where you want to run system builds *and* get good user performance [2].

Instead of fixing the software for "emerging" hardware, why not fix the system for the hundreds of millions of installed systems! Until problems such as these are fixed Linux is a toy from a power desktop user standpoint.

1. It is relatively easy to max out main memory by running Firefox (SeaMonkey, etc.) for long periods (days). Opening lots of tabs/windows can easily push the browser memory usage alone to 1+GB and it will stay there due to heap fragmentation. Allocating or deallocating browser memory requires paging through much of the heap and Linux paging performance stinks! I have found it impossible to max out CPU & Disk I/O in cases where the system is at or over full memory utilization. On a single user desktop PC it seems impossible to cause the system to "page thrash". This seems to be an aspect of how VM paging is scheduled and hasn't changed significantly since at least Linux 2.6.12.
2. Even when one is running system builds at nice -19, the old scheduling algorithm failed to give top CPU priority to the non-niced processes (niced processes seem to only be penalized after having consumed *seconds* of CPU time). Once complex system builds have placed most of the files in the buffer cache, a single compile proceeds very quickly -- potentially locking the CPU(s) into the build process rather than active (mouse, scrolling, X, etc.) user processes. I haven't seen the *new* scheduler yet but I'd like to see comments suggesting that it fixes the "nicing" problem -- i.e. *no* niced processes run until all "normal" priority processes are satisfied (or child processes inherit the parent's accumulated child CPU time as would be the case for a large make or "emerge"). Allowing "fair" scheduling across CPUs isn't going to be "fair" if small CPU consumption niced processes are being treated as equals of long running (perhaps large amount of accumulated CPU) user processes.

Re:It will not do any good for heavy loads

[The Cisco Kid]

Sounds like you need to read the man page for 'nice'

nice -19 is very much NOT nice. Its negative nice. -19 gives top priority to the process that is -19. If you want to give the build *LOW* priority, then nice it to 19 (or some other positive number), not *negative* 19.

Re:It will not do any good for heavy loads

[The Cisco Kid]

Here, I did it for you:

From 'man nice':

DESCRIPTION

Run COMMAND with an adjusted niceness, which affects process scheduling. With no COMMAND, print the current niceness. Nicenesses range from -20 (most favorable scheduling) to 19 (least favorable). I stand corrected. -19 isnt the top priority, -20 is. But both still have way higher priority than anything at the default. You want positive numbers to de-prioritize a process, not negative ones.

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.

Re:It will not do any good for heavy loads

[The Cisco Kid]

Perhaps I misunderstood your original post. You seemed to be complaining that a nice -19 process was getting higher priority than pretty much anything else, when that is exactly what it is supposed to do. That is also exactly what the man page says it does.

If, using your same script above, you ran:

# nice 19 ./loop ... then you'd hardly notice its impact at all, and other processes would get higher priority.

If you want to be able to *use* your system and let a compile/build progresss at *low* priority in the background, use nice 19 - NOT nice negative 19.

Re:It will not do any good for heavy loads

[bradbury]

We are becoming confused with the use of a minus character (-) as indicative of a switch/flag and its use to denote a negative number.

"nice -19" (one minus) is really a +19 (a low priority) -- this is how I run my builds so they *should* get minimal CPU time when other processes want CPU time.

"nice --19" (two minuses) is a -19 nice (i.e. high priority) -- running CPU bound processes with this priority will cause all "normal" user processes to perform poorly.

The point of my original message was that "nice -19" does *NO* good when one is dealing with short-running processes (like the thousands of C compiler processes required to build Firefox). I believe this is because the processes never accumulate sufficient CPU time to be considered CPU "hogs" and trigger scheduler options which attempt to balance CPU use. There is much more code in sched.c attempting to deal with multi-CPU machines (SMPs) You should bear in mind that the scheduler code was written from ~1996-2003 and CPUs are significantly faster now than they were during that period -- so "seconds" then (used to determine a CPU hog) should be tenths or hundredths of seconds today in determining CPU hogs.

Re:It will not do any good for heavy loads

[The Cisco Kid]

Now I see what you are saying.

Clearer usage might be 'nice -n 19' vs 'nice -n -19'

Re:It will not do any good for heavy loads

[bradbury]

I agree, the conventions are unclear as well as the documentation which is why I tried to give a bit of history. It would be better if there were two commands, e.g. "nice" and "nasty" which did the corresponding priority shifts with no positive and negative conventions involved.

Re:crap - Flamebait!

[Anonymous Coward]

Redhat/fedora at least are reknowned for crippling their KDE packages in one way or another (usually with their own "bluecurve" theme that is dog-slow and other idiocies). Debian's KDE packages are alright (and on my system at least on a par with GNOME in speed).

You sound like a complete asshat

[Anonymous Coward]

Rejecting someone else's idea for years and then turning around and implementing it yourself is textbook move I've seen for years and years in a research environment. I hope you understand how vile that is, you arrogant son of a bitch. You are overly protective of the code you write and refuse to listen to other smart people's views until it is overwhelming, then you go around and make your own version, and stick it in the main codeline because you have total control over it.

Really classy. No wonder everyone thinks you're an asshole.

Of course..

[Ztream]

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

Disk sharing?

[Anonymous Coward]

Is this scheduler aware of disk hog processes, so such processes will get throttled enough to share the disk with more important activity (such as swap activity)?

Re:Can anyone compare this to Jonathan Lemons Kque

[nizmogtr]

Just curious what sort of bugs are present in OS X's kqueue?
Again just curious. No flaming intended.

Re:Can anyone compare this to Jonathan Lemons Kque

[Defiler]

The big ones that come to mind are broken support for TCP_NOPUSH:
http://lists.danga.com/pipermail/memcached/2006-Ma rch/002024.html

..and the fact that it can't be used with stdin:
http://lists.apple.com/archives/darwin-dev/2006/Ap r/msg00072.html

The latter in particular is super irritating, at least to me.
I have to see any decent-sized project using events that didn't need Mac OS-specific configuration.

Really, we do.

[Corwn of Amber]

Because when you prelink the binaries the wrong way, apps get faulty and SLOW. Like they take minutes to load. (Then we have to update glibc, so everything gets revdep-rebuilt anyway...)

This is for you :)

[Anonymous Coward]

Smily time! :) =) :) =)

Also: ;) :*