The Completely Fair Scheduler

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

credit goes to Con Kolivas

[phrasebook]

This new scheduler may have 'Ingo Molnar' written all over it but I'll be giving the credit to ck!

Optimizations leading to less optimized code

[suv4x4]

It's a very interesting phenomenon.

After enough number of iterations trying to optimize a software program to do everything very well compared to the base "naive" solution, you end up with an OS that does everything poorly.

It's counterintuitive, but we see it it every day around us.

What I really want

[Anonymous Coward]

I want a nice-like utility that works for more than just CPU time. I want to be able to do hddnice -5 firefox and networknice -7 pr0ndownloader. Why can't the principles of nice work for various forms of I/O scheduling as well as CPU scheduling? Does anyone know of a Unix that has these sorts of things. I just hate it when my system is unresponsive because some process, which is niced into all get out, is swapping like crazy, and is allowed to do so because "it's not using CPU time". Bah!

Re:This is communism!

[Anonymous Coward]

This sort of scheduler is more suited for desktops, where you want everything to react responsively at the cost of lower throughput.

Re:credit goes to Con Kolivas

[Anonymous Coward]

Perhaps if we had more 'ego maniacs' like Ingo, stuff would work better?

I don't think your characterization is fair, I read the entire thread and all I see is someone doing his job.

Re:Surprised?

[Anonymous Coward]

Yeah, I know what O(1) means, but I still don't know what "You will be surprised to know that O(1) is really too good not to have any side-effects on fairness to all tasks." means.

Interactive tasks

[Zarhan]

For this reason, I've been using Con Kolivas' patches to replace the scheduler. http://members.optusnet.com.au/ckolivas/kernel/ [optusnet.com.au] - very helpful especially if you don't have the fastest computer around. Also seems to help a bit with I/O - if my hard drive is trashing for whatever reason, interactive stuff still remains reasonably responsive. Or at least it doesn't make my mouse cursor skip...

Even so, I'd prefer to have IO better scheduled - ionice doesn't really seem to work at least for me.

Re:Optimizations leading to less optimized code

[Chandon Seldon]

After enough number of iterations trying to optimize a software program to do everything very well compared to the base "naive" solution, you end up with an OS that does everything poorly.

That's blatantly false. Sure, there are tradeoffs. There are also cases where a better algorithm is an outright win 100% of the time.

Re:O(1) - what a huge misnomer

[xenocide2]

It seems like the difference is that people call it an O(1) scheduler to reflect the fact that all the work required to be done at the end of a timeslice (record keeping, picking a new process etc) is done in constant time, and people arguing for O(n) are referring to the cost to schedule all processes. Nobody's saying they can find a schedule for n processes without looking at all of them.

Re:Isnt this called Cron ?

[Anonymous Coward]

Coming up with an idea (even if totally made up) and the backing it up with arguments is much harder than memorization and regurgitation and actually backing it up with things having to do with that class shows you have learned something, or at least know about the concepts discussed in the class.

Re:credit goes to Con Kolivas

[Anonymous Coward]

Yeah right. doing his job.. Take all the credits. Diss other people's ideas, reimplement them and claim innovation. That used to define the Microsoft notion of innovation.

I don't know any of these guys and never dealt with them on any level.

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!

--- linux.orig/kernel/sched.c
+++ linux/kernel/sched.c
@@ -16,6 +16,7 @@
  * by Davide Libenzi, preemptible kernel bits by Robert Love.
  * 2003-09-03 Interactivity tuning by Con Kolivas.
  * 2004-04-02 Scheduler domains code by Nick Piggin
+ * 2007-04-15 Con Kolivas was dead right: fairness matters! :)
  */

Ingo admitting he was wrong and giving full credit to someone else for the idea is not consistent with my view of an egomaniac. If you have other issues, slashdot may not be the best place to resolve them.

Re:I/O prioritisation

[JonXP]

And Vista has it completely. Just start up the Resource Monitor (either via the start menu, or the button on the task manager) and you can see all your I/O statistics, as well as several other computer health stats.

Re:Linux is fading away

[maxwell demon]

Possible explanation: More people know about Linux now, so there's less need to Google to learn about it.
Alternative explanation: People have less problems now using Linux, so they google less for solutions on Linux problems.
Third explanation: Linux documentation got substantially better, so people have less need to use Google as a substitute.
Fourth explanation: The larger density of Linux installations comes with a larger density of Linux experts, so people are more likely to consult their local Linux guru than Google.

Pick your favorite choice or make up yet another explanation.

Yes, those explanations are all completely made up, but so was the explanation you had in mind.

Re:Linux is fading away

[Khazunga]

Bah, it's so easy... [google.com]

Re:Isnt this called Cron ?

[shaitand]

'Grades should evaluate the ability to *use* the material of a course.'

I disagree. That falls back to a measure of the intellect of the individual. That will play a role after school but you don't go to school to demonstrate your abilities or use material, you go to learn material.

'An A-level student is one who grasps the course material so well that he builds on it to produce other conclusions.'

I agree with that. Someone who has a fully grasp of the material understands it well. As I said, the grade should reflect understanding of the material that you took the course to learn. It should not reflect intellect (beyond that required to understand said material), creativity, etc.

'If you lack skills needed to compound your understanding of the material, tough luck. A B is not a poor grade...'

I never said a student with a more thorough understanding of the material shouldn't get an A. I said the A shouldn't be reserved for the quick thinking creative writer who can make up nonsense on the spot for a test question. The slow methodical student may have greater insight into the material but be less creative.

This is the same faulty logic that leads to essays and papers as a measure of understanding. Papers do demonstrate understanding but they aren't the best tool to do so. If papers are primary method used to measure understanding then you aren't ultimately measuring comprehension of the material, you are measuring writing ability.