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?

[Jeff DeMaagd]

I'd love to discuss it, but first of all I'd want to know what we're discussing.

That's not the Slashdot way. We're supposed to have an unfounded opinion based on insufficient facts and preexisting prejudices.

Re:Can someone provide some insight?

[Aladrin]

Average? Probably nothing. But for devs/admins that are worried about certain processes taking more time than others, it -should- be more fair and keep things running smoother.

It's possible for programs right now to exploit how the current schedule dishes out time. As far as I know, they currently only do so out of ignorance, rather than malice. The new scheduler just corrects the problem.

It's not something a user can really see unless they know exactly what they are looking for, and unless a dev/admin has a program that's behaving unfairly, it's not really going to matter to them, either.

There is another invisible effect as well... Kolivas apparently publicly announced his decision to stop working on the kernel, which would include the current scheduler. That means finding another maintainer for his code, should any problems surface. If you've got 2 pieces of code that test the same in speed (as they do according to some), and 1 has a dev that's willing to keep working on it, and the other doesn't... Which would you pick?

The new code also has the added advantage of being a really really neat idea, which encourages people to work on it as well.

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?

[FauxPasIII]

Each process running on Linux has a "niceness" value which you as the user can set. The value indicates which ones you want to have more access to CPU power. The numbers range from 19, meaning roughly "only use the CPU when noone else needs it", to -20 meaning "all your CPU are belong to it".

The new scheduler will make those values behave more like they're supposed to relative to one another, and hopefully use fewer resources for itself in doing so.

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?

[Opportunist]

That sounds sensible. With the increase of Linux boxes run by "average" people (who will not directly notice a difference), the threat of malware for Linux is going to be on the rise, too. And those people usually know how to exploit even the smallest flaws in a system.

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?

[ciroknight]

Kolivas apparently publicly announced his decision to stop working on the kernel, which would include the current scheduler. That means finding another maintainer for his code, should any problems surface. If you've got 2 pieces of code that test the same in speed (as they do according to some), and 1 has a dev that's willing to keep working on it, and the other doesn't... Which would you pick?

Wow, not even a full year has past and we're already getting revisionist historians trying to change the situation.

Kolivas quit because of the scheduler debacle, because nobody would listen to Kolivas but were apt to follow Linus and his cronie Ingo around when they drum up more-or-less the exact same thing. Instead of critically listening to Kolivas' points, Linus and Ingo attacked Kolivas' merits. Under that kind of personal attack, I couldn't say I wouldn't have quit just to shut them up. Not all of us are stubborn mules and jackasses.

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?

[WhiteWolf666]

Average developer or administrator? Your system will be more "stable" under heavy loads, with fewer/no processes starved for CPU cycled. The new scheduler (building on Kovilas work in an unfriendly fashion) better divides up processor time among multiple tasks.

Average user? Multimedia tasks will not skip or stutter while the system is under load. The opposite of Vista's network performance taking a nose dive while playing MP3s, Linux systems with the new scheduler will see little/no impact from background/normal operations on their gaming, music, and video. Your mouse won't skip around while the system is loaded, and responsiveness will remain high except in situations involving super-heavy I/O usage (I/O starvation is more difficult to solve than CPU starvation).

It actually makes a substantial difference, and the system is much more fun to use.

There are some informal test results (LKML) from kernel trap:

here's an update: checking whether Wine could be a factor in your
problem i just tested latest CFS against latest SD with a 3D game
running under Wine: v2.6.22-ck1 versus v2.6.22-cfsv19 (to get the
most comparable kernel), using Quake 3 Arena Demo under Wine (0.9.41).
Here are the results in a pretty graph:
      http://people.redhat.com/mingo/misc/cfs-vs-sd-wine-quake.jpg
or, in text

2.6.22-ck1 2.6.22-cfs-v19
quake + 0 loops 41 fps quake + 0 loops 41 fps
quake + 1 loop 3 fps quake + 1 loop 41 fps
quake + 2 loops 2 fps quake + 2 loops 32 fps
quake + 3 loops 1 fps quake + 3 loops 24 fps
quake + 4 loops 0 fps quake + 4 loops 20 fps
quake + 5 loops 0 fps quake + 5 loops 16 fps

Quake3-under-Wine behavior under SD/-ck: framerate breaks down massively
during any kind of load. The game is completely unusable with 1 CPU loop
running already!

Quake3-under-Wine behavior under CFS: framerate goes down gently with
load, gameplay remains smooth. Framerate is still pretty acceptable and
the game is playable even with a 500% CPU overload. The graph looks good
and the framerate reduction goes roughly along the expected 1/n
'fairness curve' - so it all looks pretty healthy. [Note: quake3 keeps
its fully 41 fps even with 1 competing loop running on the CPU due to
"sleeper fairness".]

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?

[peragrin]

What goes around comes around.

Revisionist history is working both ways I see. 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. FOSS projects are about helping everyone, and listening to new Ideas. Something Kolvias was having a hard time doing.

That is at least how i read the whole debate.

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?

[recoiledsnake]

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.

That was certainly not how I read it when it happened. I came off with the impression that Kolivas was ripped off of his ideas by Inglo and that Linus was wrong in brushing Inglo off and going with Inglo.

The LKML email linked reinforces my suspicion. Habits and attitudes don't die easily. We see ANOTHER guy complaining that his patch was half bakedly ripped off with no explanations whatsoever and a tangential acknowledgement.

FOSS projects are about helping everyone, and listening to new Ideas. Something Kolvias was having a hard time doing.

Did you even read the linked email? Inglo seems to be talking in patches and with no discussion. If something were to happen to him or if he quits due to any reason, there would be no one who would understand the code and the features behind it enough to maintain it.

Re:Can someone provide some insight?

[Opportunist]

Folks? Could we concentrate on creating a good system instead of egos?

You know, this really has a lot of the Life of Brian. "This is his gourd", "No, we'll follow his sandal".

The nice thing about Linux is that we can actually choose which one we prefer. Put both into the distributions and let the people sort it out. The better one will prevail.

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?

[m50d]

Well damn. That's just... embarassing. Why's everyone using linux if it sucks so much?

The same reason as windows: hardware support.

Re:Can someone provide some insight?

[cartman]

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.

There are good reasons for exposing cpu info (and other kinds of OS data) as files, rather than gathering that data through system calls. Exposing the data as files makes that data usable to the range of tools people use on an OS (Unix) that supposedly treats everything as files. The data can be grepped, piped, opened, run through 'sed', cut, awked, etc. Exposing OS-internal data as files is done for the same reason that RDBMSes expose internal data as tables, and for the same reason that XML schema are XML documents themselves (this is why people complained about DTDs--they weren't XML).

Linux did not invent this idea. The inventors of Unix (Thompson and Ritchie) came up with the idea of exposing internal OS data as files, which they considered a natural extension of the Unix philosophy of treating everything as files.

You may disagree with it, or you may not be familiar with all the arguments for and against it. However you should refrain from just concluding that "LINUX SUCKS" because something was not the way you expected.

Whether the data should be exposed through files is an arguable point. It's not an area in which BSD is clearly factually superior. My own opinion is that gathering that data through files is better.

Re:Can someone provide some insight?

[rbanffy]

The scheduler has nothing to do with security exploits. This will only distribute cycles more evenly. Additionally the ideal malware should take steps to prevent it from getting too much CPU time in order to avoid detection.

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?

[Dolda2000]

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. While I agree with you that Linux seems almost pathetic compared to BSD when under heavy load, I have to object to that reason for calling the *BSDs superior to Linux. In fact, the sysctl interface is the single most bothering thing about the *BSDs to me. Isn't the treatment of everything as a file the very core of the Unix philosophy? It may be true that files like /proc/cpuinfo could very well be made easier to parse, but I find nothing to complain about with e.g. the /proc/sys/ tree, or, for that matter, sysfs. Requiring a special syscall just to fetch kernel data that could just as well be made available through the file system is, in my mind, just ugly for a Unix system, and I can only imagine that it is done that way for historical reasons.

In almost any other way, however, I would prefer the *BSDs over Linux. I still run Linux, though, but that's mainly because I want to keep running Kerberized NFS. :) When FreeBSD implements that, I may well switch.

Re:Can someone provide some insight?

[AnyoneEB]

You are right. It would be easy. In fact, someone wrote a patch for it called plugsched. It was not accepted into the kernel due to the fact that it would supposedly discourage the idea of simply making a scheduler which worked well for everyone.

Re:Can someone provide some insight?

[ciroknight]

You shouldn't say "someone did", it was Kolivas himself that first offered the pluggable scheduler patch so that his patch could be used along side any new future schedulers and offer a concrete way to benchmark the changes caused by scheduling. And this was done years ago, circa 2004: http://ck.kolivas.org/patches/plugsched/

Of course, Linus and Ingo rejected those patches as well.

Re:Can someone provide some insight?

[ciroknight]

PlugSched would have let us do this in a big way, letting us change at boot or even while the system is running what cpu scheduler is working. But, most distributions pull most of their code from the Mainline and Linus' blessed code, so it's unlikely any distribution will ever see Kolivas' scheduler in action to know whether or not it could do better than Ingo's bastard-clone.

Now we get even more people questioning Ingo's code, and instead of examining the code, we get people starting to question Roman's merits too. The personal attacks over this need to stop, and we need to look at the actual problem instead of looking at the developers who are questioning the choices. I personally hope Kolivas will come back to the kernel and hasn't moved on for good, just needing some time away from the hot-heads and their corporate Linux eccentricity. Desktop Linux needs to start at the Kernel and end at the user, no component between left behind.

Re:Can someone provide some insight?

[Cajal]

Of course, the parent poster wasn't just complaining that Linux exposes this information as files rather than via sysctl. The real problem is that the format of the information changes frequently, and varies between platforms. /proc/cpuinfo, for example, varies widely between x86, ppc and sparc.

It's exactly this sort of inattention to detail that makes me not enjoy developing on Linux.

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:Can someone provide some insight?

[martin-boundary]

Indeed. There are known discussions. These are discussions we know that we know. There are known undiscussions. That is to say, there are discussions that we know that we don't know. But there are also unknown undiscussions. These are discussions we don't know we don't know. They occur a lot on slashdot.

Re:Can someone provide some insight?

[Jah-Wren Ryel]

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). I don't know one thing about how PlugSched was implemented, but other unices like HPUX have the ability to designate that certain cpus will run under specific schedulers. So you can run straight FIFO scheduler on one pair of cpus, a real-time scheduler on another set of cpus and the normal unix scheduler on the rest. You need to combine that with a way to bind processes to those cpus to get the benefit of the different schedulers, but that almost goes without saying.

I'm kind of surprised that linux does not support that sort of thing already, with SGI's heavy use of linux on their NUMA altix systems, I would have thought that support for multiple simultaneous schedulers would already be in the mainline.

Re:Can someone provide some insight?

[drsmithy]

Err...only slightly. Unix based operating systems separate user space from the rest of the system. Nothing much can be done without root access.

Pretty much everything malware might want to do, it can do without elevated privileges.

Installing Malware on a Unix system is, for this reason virtually impossible.

It's as simple as convincing an end user to execute a program with elevated privileges. Which is only marginally more difficult than convincing them to run a program at all. Which isn't particularly difficult.

MA large user base is often used as a rationalization for windows malware, but in reality it is just an incorrect excuse.

It's not an "excuse", it's an inescapable aspect of the "malware problem".

Re:Can someone provide some insight?

[marcosdumay]

"The explanation that this is a way to steer the development toward a single scheduler that should function well enough for everyone, desktop, embedded or server, works for me."

Ok, so the scheduler must be perfectly fair, priorizing no process, so servers work well. Must give priority to IO bound processes, so desktop users feel the system smoot. And shouldn't be configurable, to not penalize the resource constrained embebed systems.

Let me add that it should give priority entirely for time constrained processes and never reschedule processes, so it can be used for real time. Of course, it should reschedule processes periodicaly, so desktop users won't need to wait CPU bound processes to end before they are able to move their mouse.

There you have, your ultimate process shceduler. Seems quite doable.

In a blind taste test....

[budword]

I doubt any of us could tell the difference. Storm in a tea cup.

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.

Re:In a blind taste test....

[peterpi]

It could help stop you forgetting to close your 'i' tag too! :p

Re:In a blind taste test....

[morgan_greywolf]

I doubt any of us could tell the difference. Storm in a tea cup. I probably could. But then again, I do a lot of realtime audio recording and editing and therefore I make use of Ingo Molnar's REALTIME and PREEMPT kernel scheduler patches.

The standard scheduler, without those patches, is just about completely useless for realtime audio recording and editing, even with nothing more than the necessary apps, JACK, X, a lightweight window manager (openbox), HAL, syslogd, anacron, and 6 gettys running. Even taken anacron out of the situation didn't help.

I think there was a TV show about this

[RightSaidFred99]

When Nerds Attack 3: The Nerdening.

Re:Snooze

[Reason58]

Seriously has Slashdot got such a boner for Linux that they'll post absolutely every fucking little boring thing they find? You must be new here.

Still don't understand the fixation

[Anonymous Coward]

Another CFS flamewar within 2 weeks of the last slashdot article on it.
http://linux.slashdot.org/article.pl?sid=07/09/01/1853228

And yet the most important performance bugs in the kernel haven't had any updates.
http://bugzilla.kernel.org/show_bug.cgi?id=7372
http://bugzilla.kernel.org/show_bug.cgi?id=8636

I do not understand the fixation on CPU scheduling when there are so many other things that need attention. [Heck, if disk IO performance is so broken, I certainly don't have the guts to try out the new firewire code in 2.6.22 as well and add another variable into my life.]

Re:Still don't understand the fixation

[phantomlord]

Roman is a long time kernel dev and is the maintainer of AFFS, HFS, M68K and kconfig. He's hardly new to the scene. New to the scheduler code, perhaps.

All of this started with Roman doing a code review of CFS a month or two ago. Roman asked some questions to clarify what certain parts of the code were doing, Ingo asked Roman to provide more info so he could see where CFS was falling short on Roman's test cases. Both sides kept trying to talk passed each other. Eventually, Roman got frustrated and provided a new scheduler/patch with some mathematical proofs behind it to make the scheduling better. Roman and Ingo continued to talk passed each other. Ingo picked up some of Roman's patches. Roman feels slighted like he's being ignored but was just as guilty in ignoring Ingo (and other CFS devs) along the way. Factor in the taste in people's mouth from earlier this year with Con and the lines were already drawn before Roman got involved.

It's a clash of egos all around and nothing atypical for a large open source project.

Esoteric Discussions

[Archangel Michael]

More importantly, if there are more than one Scheduler, and if someone could tell the difference, why isn't s/he using the ALTERNATE Scheduler and compiling their own custom, tweaked and totally tuned kernel?

Seriously, most people aren't going to notice, and those that do notice, ought to be able to compile their own kernel, and ought to do exactly that. This is nothing short of an esoteric discussion and shouldn't extend beyond kernel developers. Most people don't know, and don't care which scheduler is implemented.

I'm one of those somewhere between caring and not. I only care about the supposed differences in approach to scheduling, and quite frankly, from what little I understand, the various schemes to scheduling have their advantages and disadvantages. I seriously doubt that ONE is better in all circumstances compared to all the others.

Re:Esoteric Discussions

[LizardKing]

if there are more than one Scheduler, and if someone could tell the difference, why isn't s/he using the ALTERNATE Scheduler and compiling their own custom, tweaked and totally tuned kernel?

Someone (Con Kolivas?) suggested a "pluggable" scheduler API. I think this was even backed up by patches to provide this functionality. Linus Torvalds rejected the proposal - I think he said that the benefits would be outweighed by the need to maintain multiple schedulers. My opinion is that the kernel could have included a single scheduler in the kernel.org tarballs, but by providing the pluggable API it would lower the bar for those who wish to develop or play with different schedulers.

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

Re:more important things

[Chirs]

Have you considered the fact that different people work on different areas of the kernel? The people that work on the scheduler generally have very little to do with hardware drivers.

Re:Snooze

[EricR86]

If Microsoft or Apple were more open with regards to their kernel development, I'm pretty sure issues like this would be posted here on slashdot - regardless of a favored OS.

Ugh bring back 2.7 please

[maelstrom]

I know they've changed the model of development for the kernel, but how many new schedulers have we gone through between 2.4 and 2.6 now? Maybe it is just me, but the scheduler seems like a pretty important piece of the kernel.... Ripping it out every 6 months and calling it "stable" seems a bit off to me.

Oh well. I guess I'm just getting cranky in my "old" age.

Re:Ugh bring back 2.7 please

[luciofm]

There was the 2.4 schuduler, the old O(1) 2.6 scheduler and now the new 2.6 CFS scheduler...
This doenst seem to me to be ripped every 6 months, unless the 2.6 tree is just about 6 months older...

Did the Open Source is about choise 6

[denisbergeron]

Why not having the possibility to choose the sheduler ? What about a modular kernel sheduler, so everyone will be happy.

Flamewars are usual in developer websites

[Spy der Mann]

For example, ReactOS had a flamewar regarding the "stolen code from Windows", and it was nearly identical. There was this obsessive guy that got fed up over nothing just because his pride as a person was hurt. In the end he was just misinterpreting stuff. The other guy tried to be calm and understanding, but it didn't work.

In the end, it's just about one thing: Some developers, no matter how high their IQ is, are too full of themselves because they have a stupid complex and a low self-esteem.

Re:That was actually quite fun. Thanks.

[jeevesbond]

What a bunch of babies.

Maybe to you. To me all the flaming and arguing, over a change that will not--apparently--have much of an effect upon the average user, means that the kernel developers are passionate about what they do. It means that, once the dust settles, we'll get a superior product. Maybe if the developers in Microsoft were this passionate Windows would be as good as GNU/Linux.

If you're not entertained by this you don't have to read the stories, just apt-get upgrade and enjoy the software. This is the way things work in the world of Free software, as Linus says: 'May the best code win!' If you want a kernel developed by boring, outsourced workers: choose Microsoft.

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:BEOS scheduler?

[norkakn]

Yeah, but how was it as a LAMP stack?

No, there aren't. This is what a kernel DOES.

[Valdrax]

I know its not easy getting info on wireless chips, but time would be better spent working on something like that.

I'll ignore for a moment the fact that you're essentially making the same argument as "Why aren't all scientists (from solid-state physicists to cognitive neuroscientists) working on a cure for cancer instead of [perceived frivolous research in the news]?" You're ignoring the different kinds of expertise that go into a complex field of work like kernel development.

Instead, I'm just going to focus on your assertion that support for a few more wireless chipsets than the abundant choices we have today is more important than fixing problems in the most central and fundamental task of the kernel -- a task that even the most minimalist microkernels consider necessary to put into the microkernel.

This is simply hogwash. Scheduling affects every single part of the system, and it's a major factor in the perceived and real performance of a system. Fixes to the scheduler will affect how a user enjoys their system over the entire life of the system whereas a missing wireless driver affects them once -- at purchase time.

Furthermore, not all Linux systems have wireless networking. Adding more wireless drivers is going to be useless in nearly all server and most embedded uses. You seem to be under the mistaken impression that the purpose of Linux is to provide a good desktop or laptop experience. There are considerably more application domains that Linux operates in.

And frankly...

Just look at all the live CD's out there and how many can connect to wifi? Ubuntu and not much else.

This is not the kernel developers' problem. They've provided the functionality as evidenced by the fact that Ubuntu can do it. This is up to the distro developers to work on. Again, you make the mistake of assuming that all developers are equal and interchangeable and that they all have the same responsibilities in bringing the product to you, the unpaying customer.

Re:more important things

[Hatta]

There isn't much more important work for a kernel than improving performance under load. They could probably do better by focusing on I/O scheduling than CPU scheduling. My CPU spends an inordinate amount of time waiting for IO. But kernel performance is of the utmost importance to kernel developers. What does it matter if it runs on your hardware if it doesn't run well?

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

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?

CFS issues - some bugs to iron out before 2.6.23

[tota]

The discussion is not as bad as it sounds (almost normal for LKML!), it's just that Roman wants to talk about the maths and Ingo works with patches... as Willy Tarreau pointed out "I know for sure that the common language here on LKML is patches".

Beyond the heated discussion with Roman Zippel, there are still a few workloads which can trigger regressions, one of which I found running some unit tests.

This is covered in this thread, and although there is now a version of CFS which does not exhibit the problem (see graph of combo3-yield patch) it is not the one that is meant to be merged in 2.6.23 (these patches are 2.6.24 material) so Ingo is getting me to test patches until this regression can be solved.

One slightly annoying thing is that the current fix involves using sysctl to switch back (at least partially) to the old scheduler mechanism!

Re:Already suggested

[tinkerghost]

Potentially dangerous to allow "anyone" to do it... it would be much better to have some type of ACL that allows specific users/group and/or perhaps specific programs to be reniced outside of root's control.

The principle is that Skype/Kphone/FPS register themselves with a 'loader' type function requesting a nice level of -10 at install. Daemons that don't care about latency can register themselves as +10. Anything that doesn't care, doesn't register.

Since only Root should be able to perform a systemwide install & consequentially have access to the 'loader', Root would be determining the runlevel, but any user can use it. If the program were installed locally by a non-Root user, then it wouldn't be able to access the 'loader' to configure it & would run normally at nice 0.

The current model, limits any normal user to nice 0 and above, with everything defaulting to 0. Lets face it, most daemons aren't time sensative enough to require a nice of 0 - the 10mS difference in mounting the CD is totally overwhelmed by the 2 seconds it takes the tray to close & the disk to spin up anyway - a perfect candidate for a nice of 10.

On the other side of the coin, dropping Skype or Kphone into nice 0 is bad. As audio systems, pretty much any delay is a recipee for poor audio quality. They need control when they need it - not 10mS later. The same with GUIs, because they directly interact with people, they need to have the snappy response of a negative nice program - not as negative as multimedia, but better than the baseline.

Gross mis-characterizations of Molnar

[l4m3z0r]

As I started reading the comments on here I noticed that many were quick to down Ingo for his transgressions and its quite obvious from the comments that no one has bothered to read the exchange on LKML in order to become familiar with what is going on. I have read it, I have 0 bias for either Zippel or Molnar and I can say without any reservation that Zippel is a wank and Molnar is borderline saintly.

A recap of what I have read and understood about the entire situation:

• Zippel shows up with some patches out of the blue and makes some claims about them.
• Molnar takes time out of his day to look at and understand the patches and points out a few things such as lack of comments and missing functionality, also points out that some of the things Zippel wants to do have been done since the last time Zippel looked at the code and that he should look into the latest they've done.
• At this point Zippel decides to try to get into a pissing contest with Molnar and makes more claims about the superiority of his math and how the patches aren't the point.
• They argue back and forth all the while Molnar very seriously considering and understanding Zippels concerns. Molnar asks Zippel to split up his giant patch into smaller pieces that are commented and cleaned in order to bring the useful ones into the kernel more easily.
• Zippel essentially whines and repeats the same arguments over and over for a bunch of threads.
• Molnar basically pleads for him to cooperate so CFS can get the benefits Zippel has to offer.
• Zippel refuses, acts like a child.
• Molnar reworks a few of Zippel's ideas into smaller patches and incorporated them into CFS and attributes this to Zippel.
• Zippel is very rude about this and accuses Molnar of stealing from Zippel.
• Molnar again asks him to cooperate.
• Other people get annoyed start criticizing Zippel.

Ultimately I think Zippel is purposefully trying to provoke Molnar throughout all of this. His wild accusations are nothing more than games that he is playing, the guy has a chip on his shoulder and if Linux was my toy, I would have blocked him from the mailing lists.

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.

Re:Fairness is relative...

[ultranova]

On a personal workstation, however, an interactive user doesn't necessarily want all the programs to have fair access... we typically would like to have what we're concentrating on currently to be more responsive (have potentially unfair access) or else we may see dropped frames, stuttering music, or the like because the scheduler is trying to be fair to applications that aren't interactive with the console user.

This is where priority levels, or "nice", come in. They allow the user to tell the computer which stuff should be preferred/unpreferred, and how much.

Unfortunately, some people insist that the scheduler should guesstimate the priorities by itself, rather than depending on the user's judgement; since the scheduler can't read the mind of the user, such guesstimating (or "heuristic") scheduler frequently guesses wrong, leading to performance problems. What's even worse is that the constantly changing "dynamic priority" for every program can easily lead to temporary high latency, which in turn leads to audio/video skips and unresponsive system.

A totally fair scheduler will give each process CPU time according to their nice level, without trying to guesstimate. Con Kolivas came up with such a design (the Staircase Deadline scheduler), after which Ingo Molnar wrote a similar design (the CFS) based on the SD which then got accepted into the kernel. Con wasn't happy about this and quit kernel development altogether, which is unfortunate since the "-ck" patchset maintained by him was/is a huge improvement over the vanilla kernel.

Given you both can't seem to get Ingo's name right

[Chuck Chunder]

That was certainly not how I read it when it happened

Perhaps we shouldn't trust either of your readings.