Debating the Linux Process Scheduler

An anonymous reader writes "The Linux 2.6.23 kernel is expected around the end of the month, and will be the first to include Ingo Molnar's much debated rewrite of the process scheduler called the Completely Fair Scheduler. In another Linux kernel mailing list thread one more developer is complaining about Molnar and his new code. However, according to KernelTrap a number of other Linux developers have stood up to defend Molnar and call into question the motives of the complaints. It will be interesting to see how the new processor really performs when the 2.6.23 kernel is released."

Comments

Can someone provide some insight?

[Opportunist]

Is someone who does understand the differences able to explain, in non-kernel-developer terms, what the big differences will be for the average user, developer or administrator? I mean, I'd love to discuss it, but first of all I'd want to know what we're discussing.

Re:Can someone provide some insight?

[Zephiris]

Essentially, the difference is how well processor resources are divided up, how evenly, and how big the pieces are each process or task gets. Most anyone who has used Linux has had the dreaded moment where you're trying to multitask a bit, and are compiling a program while listening to music, or waching a video, and then...that's terrific, video frames are dropped, or the audio skips. Even if intermitant, it's quite annoying, at the very least. The 'Completely Fair Scheduler' is an attempt to have more fair, sane, and generally less complex scheduling. This also happens to reduces the worst case latencies, averaging from (at least on the tests with my computer) 120+ms on vanilla 2.6.22 scheduler, to ~2.6ms with CFS.

It's largely a drastic improvement over the old scheduling mechanisms that Linux has relied on, although other OSes have largely worked through such problems some time ago.

While it's not exactly THE most scientific, I had a few rounds of testing over which did better on load vs. things still behaving exactly the way they should. I ran all of them with audio playing through KDE artsd, video player, glxgears, etc, loaded, plus inducing a CPU load via 'stress'. Linux, even with CFS, it's still fairly easy to 'upset' it by just producing a fairly large (2-4) amount of load. Solaris did notably better. While it seemed to have a few quirks with scheduling in general, it could sustain a load of around 8-12 without producing video/audio frame drops. FreeBSD, with the experimental SCHED_ULE 2.0 scheduler (as of March 2007) could sustain a load of over 80 with no problems, frame drops, or even glxgears slowing down to a complete crawl (although you wouldn't want to especially use OpenGL at such, it was still getting the speed of software glxgears), and even at 120+ load, the mouse wouldn't respond, while everything else kept going fine. This seems purely useless, but it really comes in handy if trying to do one or more KDE compiles while watching video, on Linux, this tends to be prevented. For the uninitiated, load averages like that are basically a multiplier vs. how much actual work your computer can do in real time. Eg, a 0.5 load would mean you're doing 50% of what you could in realtime. A 2.0 load means you're trying to handle twice what you can do in realtime, it is weighted against how many processors you have (I have one), but other things like disk access can also contribute to the load average, depending on OS.

So, longer story short, a superior CPU scheduler can make a world of difference in how things behave when your system's something else with the CPU(s) at the same time.

Re:Can someone provide some insight?

[Anonymous Coward]

Typical Linux response. Usually it's Linus that calls bullshit, then other people discover it's true, then Linux appropriates it, and acts like it invented it.

Object lesson: /dev/poll. Linus ranted about how Solaris must have "cheated", then mysteriously the same architecture appears in Linux less than a year later.

Re:Can someone provide some insight?

[dpilot]

Do you want your media to play without skips or drops while you're compiling your new kernel?

There have long been tricks like "interactive priority boost" or "nice -10 X" that attempt to make the desktop more responsive, and media play smoothly. But others believe those are just tricks, bound to misbehave in corner cases, and that a good scheduler and well implemented priority scheme will do just as well without the drawbacks. That's where CFS is trying to be. In particular most desktop responsiveness is of the sort, "I need a little CPU, and I need it NOW!" while compiles and such are "I need lots of CPU, and I'll take it whenever I can get it." The CFS keeps track of not just who's using a timeslice, but how much time they're using. That way, those short bursts of CPU keep their priority intact, while more CPU-intensive processes tend to get some priority degradation.

This goes back a little farther than Ingo Molnar's current involvement. A while back, Con Kolivas began putting in a bunch of work on the scheduler trying to get desktop response to work right, essentially he wanted his media, and his compiles, too. He did a lot of work and attracted a lot of users and fanbois along the way. More recently, Ingo Molnar get interested too, and came up with the "Completely Fair Scheduler." When it came time to pick one, Linus saw the CFS doing pretty well, still under heavy and active development. CK's scheduler was also pretty good, but the fanbois poisoned the waters, insisting that it was perfect as it was, and didn't need fixing. Linux chose an active development model over "perfection." Unfortunately Con Kolivas felt slighted in the process, and left. IIRC, he may have been absent during the decision window, and his fanbois did him in.

Add to all of this the fact that the kernel can now run tickless, so that laptops can really scale back their power in between keystrokes or while you're reading the screen. There has been quite a bit of interesting work on scheduling, lately.

Re:Can someone provide some insight?

[mamer]

Another question: I've been waiting for OpenMP support in gcc, it seems to be coming soon. In the meantime, I tried to parallelize my code by hard coding my threads using pthreads. I tested it by running several matrix-matrix multiplications "in parallel" on a multi-core CPU, and what I've got was all threads running on the same processor. Only after increasing my number of threads to a couple of dozens, I get some of them to run on the second processor. So basically, I am not getting any performance gain. I asked a number of people an they tell me "this is an old problem, basically the Linux kernel scheduler is stupid and nobody has bothered to fix it". Now, is Ingo's new scheduler fixing this? if gcc-openmp relies on the kernel scheduler, should we expect that open-mp will basically work-but-not-really-work on shared memory multi processor machines? I think this is an important issue to address, especially in an era where high-performace computing has become the driving force behind the hardware. BTW, how are otehr commercial compilers overcoming this scheduling problem?

Re:Can someone provide some insight?

[TheRaven64]

Well damn. That's just... embarassing It's more embarrassing than the grandparent states, actually. ULE 2 has been improved a lot in the last few months, and the newer ULE 3 performs a lot better, particularly on SMP systems. From what I've seen, the new Linux scheduler has roughly the same shape (and size) performance curves on 1-8 CPU systems as the old 4BSD scheduler that ULE replaces.

Why's everyone using linux if it sucks so much? Because Linux sounds cool, while BSD sounds geeky. I was recently reminded of how badly Linux sucks when I went over some old code I'd written to get the CPU name and speed. The FreeBSD and OpenBSD implementations of this code each called a single sysctl for each result. The Linux version had to read /proc/cpuinfo and parse it. Actually, it had to parse it in two different ways, because it turns out the format of cpuinfo is different on x86 and all other platforms. Reading the battery life was even worse. On FreeBSD it's just a matter of reading the hw.acpi.battery.life sysctl (one line of code). For Linux, it involves parsing some messy procfs stuff with a format that has a habit of changing between releases. I don't understand how a developer could prefer Linux to any other UNIX.

Re:Can someone provide some insight?

[Wdomburg]

Kolivas maintained the SD scheduler, which never made it into mainline.

Re:Can someone provide some insight?

[SEAL]

Whenever Linux or another kernel developer would bring up a point of failure in Kolvias's scheduler instead of Fixing the problem Kolvias would lash out and say it wasn't broken.

CFS won not because it was a better scheduler at the time, but because Inglo worked with the developers to make it better, instead of fighting everyone who questioned anything about it.

I believe Linus was the claiming Ingo worked better with the developers (or at least I saw him write to that effect on the LKML). By contrast, Kolivas had many individuals helping out with his branch who were quite pleased with his progress.

The problem is that Kolivas was working to help desktop, and particularly 3D game users. He'd say it wasn't broken if it was optimizing for those particular platforms at a cost of a fraction of a percent Oracle performance. Most of the kernel devs don't care 2 cents about 3D or desktop users, and many are employed by large enterprise businesses, so you can see who won.

Personally I think Kolivas should've been given full access to merge his code. Many of us found his work very useful and it's sad to see him driven away by a few people who are oblivious to what everyday users need. Even if his scheduler was not the default one, it still would've been nice to have as a mainline kernel option.

- SEAL

Re:Can someone provide some insight?

[GooberToo]

Average? Probably nothing.

I don't think that's really fair. Average these days actually has a large spread. Average web user? Average game player? Average video watcher? Average musician? Averaging what? And that's the point of the CFS. Each of those users have different expectations and each reflect a different type of scheduler workload. The old scheduler has lots and lots of code to handle various performance problems for corner cases for each type of "average user" depicted above. This in turn means the code is hard to read, hard to understand, and even harder to maintain. Worse, some code which help some corner cases actually make things worse for others. This in turn means more special case coding and even more complex testing.

The CFS is designed to simplify most everything the O(1) schedule does without tons of complex heuristics and special code to address various corner cases. In other words, in stead of trying to guess what you really want, the CFS simply tries to be as fair as possible for everyone, thusly ensuring many categories of corner cases are simply no longer an issue with the CFS.

This does not mean CFS is always better than O(1), but early results indicate they are traveling down a good road. In fact, the last round of patches I read about, actually establish CFS ~12% faster then the old O(1) schedule. Of course, it's yet to be seen how well it will be received and how quickly it will prove it self with a large user base. The devil is in the details with schedulers and sometimes real world user workloads don't reflect anything which has been tested/validating during development.

Nonetheless, development on CFS continues and it certainly is providing hope it will be smaller, faster, provide lower latency, be easier to maintain, and address a wider range of workloads, including many corner cases, without requiring complex code to track and analyze heuristics.

Long story short, yes, if all goes well, even the average user may notice an improvement depending on the particulars of their workload. Wouldn't you notice a more responsive desktop? ;)

Re:Can someone provide some insight?

[rbanffy]

"The problem is that Kolivas was working to help desktop, and particularly 3D game users."

I don't know for sure, but I think it should be trivial to have a kernel switch activated on boot to set the preferred scheduler. This way, 3D gamers would be happy to set the -ks (I fail to remember its correct name) while the rest of us would be happy to leave it alone and get the CFS. Maybe by having a modular scheduler architecture would allow to have kernels with the -openvz or -oraclesbest or whatever other schedulers one may want (and could get support from the kernel developers).

A slightly more clever approach would be to let one switch schedulers on the fly, but I think it's asking too much.

Re:Can someone provide some insight?

[rg3]

I'm not trying to debunk your claims or anything, but I tried to reproduce that behaviour in my 2.6.22.6 kernel (no CFS, that will be in 2.6.23), and I couldn't make mplayer drop any frames. I launched mplayer to play an MPEG4 movie with MP3 audio, launched 8 infinite loops and ran updatedb so as to keep a good amount of IO too. mplayer didn't drop any frames and the audio didn't skip at all. The load average was 10 point something. And I set the scheduler governor to powersave, so I was effectively running at 800 MHz instead of the full 1800 Mhz.

Maybe my setup is different. Preemptive kernel, 1000 Hz, CFS IO scheduler. So I'm not sure how a load average of 2 or 4 can disturb the Linux kernel at all. Can you please elaborate on your setup? Maybe it's a bug in artsd or your video player. I have no idea. My mplayer uses ALSA.

Re:In a blind taste test....

[MyLongNickName]

As a windows user who has very little experience with Windows: This is one of the strengths of open source. if you have a large enough base of contributors, these "little" details are brought out into the open, and you can really understand how things work. I've read a bit on the subject, and it is interesting to see the different approaches that can be taken to something that most of us do not even think about.

With Windows, how does this work? I will never know for sure. if MS doesn't choose to make it known, it isn't known. If they choose to make it known, then I just have to trust they are telling the truth (Windows Update anyone).

With a project like this, you are much more likely to get the best approach to the situation.

BEOS scheduler?

[Danathar]

Does anybody know what kind of scheduler BEOS used before it's demise? I seem to recall it ran circles around other OS's at the time when it came to multitasking multimedia.

Re:Snooze

[TheRaven64]

Maybe I missed them, but where were all of the Slashdot articles about the ULE 2 and ULE 3 FreeBSD schedulers? From all the benchmarks I've seen, they make the Linux scheduler look embarrassingly antiquated (performance characteristics matching the 4BSD scheduler that ULE was originally designed to replace).

Re:Esoteric Discussions

[larien]

Hrm, wonder how Solaris does it? You can have multiple schedulers running under a single OS instance, although using different ones in the same processor set means you might not get the results you're after. Source is in Open Solaris, so there may be scope to re-use it elsewhere, dependant on licensing restrictions.

For those who wonder, default schedulers under Solaris 10 include TS (Timeshare, the default), IA (Interactive), FSS (Fair share scheduler, workload management), RT (Real Time), FX (Fixed) and SYS (System). You can, if you really want, run processes under all of these on the same processor, but it wouldn't be recommended :P

Scheduler Question for the /. Experts

[Cassini2]

One way to cause dramatic performance problems on a Windows machine is to simply write a program that accesses lots of files. Performing a network backup with the Windows Networking API is a good example of this. Windows responds by fetching the files from disk and using system memory as a cache. In the process, the working set of programs running on the computer is paged out. The result is that low-priority activities can dramatically slow down potentially important activities on the computer. A good example of this is doing a network backup or a background virus scan on a Windows computer while trying to do any foreground activity (like browsing the web or using Microsoft Word).

So far, in my experience, Linux seems pretty immune to these priority inversions. Will the new scheduling algorithms allow low-priority processes to cause priority inversions by abusing non-processor resources like the network or disk drives?

Re:Snooze

[oojah]

I guess articles on the FreeBSD schedulers are either not being submitted or are being rejected. It's a shame either way. I don't use BSD (for no particular reason) but I'd still very much like to hear about what's going on there.