Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
×
Software Linux

The Really Fair Scheduler 199

derrida writes "During the many threads discussing Ingo Molnar's recently merged Completely Fair Scheduler, Roman Zippel has repeatedly questioned the complexity of the new process scheduler. In a recent posting to the Linux Kernel mailing list he offered a simpler scheduler named the 'Really Fair Scheduler' saying, 'As I already tried to explain previously CFS has a considerable algorithmic and computational complexity. This patch should now make it clearer, why I could so easily skip over Ingo's long explanation of all the tricks CFS uses to keep the computational overhead low — I simply don't need them.'"
This discussion has been archived. No new comments can be posted.

The Really Fair Scheduler

Comments Filter:
  • by El_Muerte_TDS ( 592157 ) on Saturday September 01, 2007 @03:58PM (#20435691) Homepage
    The the fancy fair scheduler.
    • Fuck this. (Score:5, Funny)

      by Anonymous Coward on Saturday September 01, 2007 @04:11PM (#20435779)
      Let's just go back to cooperative multitasking like Mac OS where everything was simple.
    • What I don't understand is why these schedulers can't just be swapped out by the users. I know there was some discussion of this, and it was vetoed by the kernel maintainers. It makes a lot of sense to me to just allow users to insert kernel modules with schedulers and just do something in the /proc filesystem to go between them. Then people could use whatever they like, and if they write their own, they wouldn't have to recompile the kernel.

      After all, isn't that the idea of open source software -- may th

      • by cnettel ( 836611 ) on Saturday September 01, 2007 @04:32PM (#20435901)
        The scheduler is at the very heart of the kernel. It's relatively hard to make the logic for choicing what and when to context-switch modular, while keeping the actual context-switches fast enough. Diferent schedulers tend to have different ideas on what stats to keep, and you all want it with good memory locality. After all, we should remember that this is a piece of code that's relevant tens or hundreds of times per second, no matter what you do with your machine.
        • Re: (Score:3, Interesting)

          by dhasenan ( 758719 )
          Then don't allow them to compile schedulers as modules -- force each kernel to have a single scheduler built in. Then it's a matter of specifying the interface and then linking in a different object file.

          It's doable (easy, even), it doesn't require significant investment from a kernel maintenance perspective, and it cuts through a fair bit of politicking.
        • Re: (Score:3, Interesting)

          by sonpal ( 527593 )
          One could say the same about filesystems - but we figured out how to abstract the filesystem API in UNIX a long time ago. This led to a lot of innovation in filesystems - ext2, ext3, ReiserFS, AFS, ZFS, etc. I think we might see similar innovation in schedulers if the scheduler was pluggable. At the very least, I suspect that Con Klivas would still be a kernel developer had we supported pluggable schedulers, and that alone might justify making the scheduler pluggable.

          I expect that there would be a per
      • Re: (Score:3, Insightful)

        by treke ( 62626 )
        The simplest answer is that the developers who have the final say don't want to do it that way. They think that it's better for the kernel to have one single scheduler that gets widely tested against every type of load than to have multiple schedulers that tend to only get tested in their areas of optimization.
      • Because this patch is just an improvement over CFS, and should either merged in mainline's CFS or completely rejected?
    • by Megane ( 129182 ) on Saturday September 01, 2007 @06:32PM (#20436483)
      I'm waiting for the Science Fair Scheduler. And the ladies out there might want to try the Vanity Fair Scheduler.
    • Re: (Score:3, Funny)

      by BronsCon ( 927697 )
      "fancy fair scheduler"

      Oh, FFS.
    • Instead of all the communist central planning nonsense trying to come up with ever cleverer politburo schemes, we should have a Market-Based Scheduler: CPU resources should be auctioned every 100ms. Let the market decide.
  • by amliebsch ( 724858 ) on Saturday September 01, 2007 @03:58PM (#20435697) Journal
    Still waiting for Steve Jobs' "Insanely Fair Scheduler."
    • by Xtravar ( 725372 ) on Saturday September 01, 2007 @04:02PM (#20435719) Homepage Journal

      Still waiting for Steve Jobs' "Insanely Fair Scheduler."
      Wouldn't that be named something more like iFS or iSched?

      God forbid we drop the lower-case I naming convention. It stands for "interwebs compatible".
      • Re: (Score:3, Funny)

        Sorry, Apple already has designs on the iSched moniker.
        Where else would you keep your iLawnmower?

      • I think we should hold a conference for kernel developers the world over to air their concerns about this issue.

        We could call it the "International Scheduler Fair".
    • by JoeCommodore ( 567479 ) <larry@portcommodore.com> on Saturday September 01, 2007 @04:10PM (#20435767) Homepage
      Sure would be better than the "Multicolored Pinwheel of Wait" part of OS X now.
      • by Anti-Trend ( 857000 ) on Saturday September 01, 2007 @04:59PM (#20436019) Homepage Journal
        Agreed. While I recognise and appreciate the humor in your comment, this is the main reason I use Debian on the desktop rather than OS X -- I multitask heavily. A Linux kernel with a Desktop preemption model and 1000Hz Timer frequency is a Godsend for those who push their PC's a tad too hard on a regular basis. I would like to see a simplified version of the scheduler, but all said CFS isn't as bad as everybody makes it out to be.
      • Upgrade to 1GB of RAM (2GB on Intel) and you won't see it anymore. (usually.)

        -:sigma.SB

        • Nonsense.

          I see the pinwheel many times a day, and that's on a fully tricked out MacBookPro.
        • Re: (Score:3, Informative)

          Upgrade to 1GB of RAM (2GB on Intel) and you won't see it anymore. (usually.)

          -:sigma.SB

          Depends a lot on your situation.

          Even with many many gigabytes of ram there are many situations where Apples applications (or the os) just sit there and do nothing (or spinning that pinwheel like they've nothing better to do) and you wonder if they crashed or what... Often enough, no. They're just doing the wrong or stupid thing and it eventually recovers. How often you see it depends a lot on your usage pattern.

          None of these (near as I can tell) have anything to do with the scheduler. Just shoddy code and

        • It came up all the time. This was a G5 with 4Gb of RAM. It usually only made an appearance when I tried to get to a downed server through the finder. The other apps were usable, but Finder was out for about five minutes as it figured out what the problem was. This could also happen through a program's file menu dialogs, so if I was trying to open a file in Photoshop and misclicked on a toasted server in the sidebar, Photoshop became frozen.
        • Oh yeah? Well Vista runs fine on 512mb of ram. I never see the pinwheel. Did you do something stupid like turn off ReadyBoost?

          Oh wait. Wrong OS. Sorry.

          FWIW, I get the pinwheel on my 1gb macbook sometimes while I'm in firefox sometimes. My "real" box that I do most of my work on runs Vista /w 2gb of ram and it does the same, only doesn't give me the visual queue that the mac does. All OS's suck in their own creative way. Your mileage may vary.
      • Yeah, that's one thing Microsoft got right. I mean, it's an HOURGLASS that never stops running! Incredible!

        Oh wait. They replaced it with a teal pinwheel in Vista, I forgot. Pfft.

    • and BOOM!
    • by Alsee ( 515537 )
      I think I am going to write and submit a scheduler, just so I can name it the My Scheduler Is Better Than Your Scheduler Scheduler.

      -
  • Does it... (Score:4, Interesting)

    by markov_chain ( 202465 ) on Saturday September 01, 2007 @04:03PM (#20435727)
    help in the case when a process goes nuts allocating memory, and stops the GUI dead in its tracks? No Alt-Ctrl-Backspace, no switching to console, unbearably slow remote login...
    • Re:Does it... (Score:5, Informative)

      by DaleGlass ( 1068434 ) on Saturday September 01, 2007 @04:12PM (#20435795) Homepage
      I don't think any scheduler will help you with that. The slowness is due to the swapping in and out from the disk, and that's going to be limited by the horribly slow speed of the disk.

      You could tweak things to make this a less likely ocurrence though.

      Disable overcommit by echo 2 > /proc/sys/vm/overcommit_memory. No more OOM killer killing some random unrelated process. Memory allocations will fail and programs will be able to handle that correctly.

      Set some memory limits in /etc/security/limits.conf

      Avoid having too much swap space. It's awfully slow, if you're using it too much all you'll manage is to run more things slower.

      Get more RAM, it's cheap. If you're regularly swapping then you definitely should.
      • Thanks for the suggestions, I'll try some out.

        I'm far from knowledgeable about what's possible to do right now using various tuning knobs. I guess I'm surprised that the GUI doesn't get priority over this sort of runaway process, but I have to temper this with saying that I never played with adjusting the nice level of various relevant processes.

        Increasing the RAM size is not a solution though, since the kind of runaway process that causes the freeze will allocate everything it can anyway.
        • by pe1chl ( 90186 )
          I'm surprised that the GUI doesn't get priority over this sort of runaway process

          That is because the GUI is just a set of processes running under the same mechanism, not some special part of the kernel or something like that.
          • Right, but that set of processes could be run at some higher nice level, which in theory would result in them preempting the runaway process. I'll shut up now because this is easy to test and I've never done it.
            • One can use nice(1) to give a program higher or lower priority to the scheduler.

              So if you have a program that hogs the CPU - be nice(1) to it! :-)
              • by pe1chl ( 90186 )
                This will not accomplish much.
                For one, in Linux the process priority us dynamically adjusted. So a program that hogs the CPU will automatically decrease in priority so that it gets all CPU time remaining after other processes that use little CPU have got their share. It will not really starve lower-priority processes, as happens on a completely priority determined scheduler with static priorities (found in realtime kernels, in Windows NT, etc).

                But, another issue is that a process that makes the system slo
      • by cnettel ( 836611 )
        Well, it should be possible for a scheduler to realize "oh, this process causes thrashing, I'll give it like 30 secs to see if it calms down, if not I'll freeze any more hard page errors caused by it for another 30 secs". Basically, in addition to thread quanta, introduce another level of longtime quanta for stuff that won't complete soon anyway. The worst killer here is when you have two processes, basically independent, that would each fit in RAM, but the scheduler insists on keeping them switching severa
        • Well, I'm not an expert in scheduling stuff, but that sounds pretty complicated.

          Say, what if you really need to run a process that causes the box to swap like mad? It could be that you're say, trying to build MAME, which seems to have a couple of files that make gcc consume about 512MB RAM. Now what if you need to do this on a box with just 384MB? Having the scheduler keep pausing it would only make it longer.

          Then, the most evil type of swap death is a positive feedback loop. For example, mail servers. Too
      • Re:Does it... (Score:5, Informative)

        by Just Some Guy ( 3352 ) <kirk+slashdot@strauser.com> on Saturday September 01, 2007 @05:35PM (#20436205) Homepage Journal

        Avoid having too much swap space. It's awfully slow, if you're using it too much all you'll manage is to run more things slower.

        FreeBSD likes lots of extra swap space. An idle system will notice that some process hasn't run in a month and will push it to swap, proactively freeing RAM for something else that might want it. Note that it will only page out a process's data segment; it's code segment uses the filesystem itself for paging (why copy "firefox" into swap when there's already a perfectly readable copy on the filesystem?).

        Unless, of course, you unlink its executable file, in which case it allocates swap to hold the file [freebsd.org] first. Which also illustrates that while unnecessary computational complexity is bad, willingness to do complex things when the situation demands can lead to some pretty cool stuff.

        • FreeBSD likes lots of extra swap space. An idle system will notice that some process hasn't run in a month and will push it to swap, proactively freeing RAM for something else that might want it. Note that it will only page out a process's data segment; it's code segment uses the filesystem itself for paging (why copy "firefox" into swap when there's already a perfectly readable copy on the filesystem?).

          Unless, of course, you unlink its executable file, in which case it allocates swap to hold the file first

          • 'There's a point where adding more swap is only going to allow the system to run even worse instead of having the process die and fix the problem.'

            Not to mention, despite what BSD does to proactively free RAM you don't want to do that unless there is a shortage of ram in the first place. After all, the program that has been idle for a month might kick up and do something and if nothing else needs the ram it is using, it will be more responsive if it is still in RAM than if it is sitting in swap on a box wit
            • Misunderstanding... (Score:3, Interesting)

              by Junta ( 36770 )
              At least in linux, and I presume FreeBSD's swap strategy is similar, you miss the point. Let's look at two scenarios, one with proactive swapping, one without, and a malloc comes in that exceeds system memory.

              Non-proactive case:
              -kernel sees malloc, knows it lacks physical memory to accommodate, malloc is blocked while kernel does housekeeping.
              -kernel picks the appropriate amount of pages to write to swap, then writes those pages to swap space, taking a while since block storage IO is excruciatingly slow.
              -A
    • ulimit is your friend.
    • Re: (Score:3, Informative)

      by Anonymous Coward
      (on a bash shell)
      ulimit -v 4096
      command_that_uses_memory

      This will limit the amount of memory available to command_that_uses_memory, and kill it once that limit is reached. But do you really want firefox forcibly killed every time you visit youtube?
  • by heinousjay ( 683506 ) on Saturday September 01, 2007 @04:03PM (#20435729) Journal
    I'd have to imagine doing so much work to prove a particular implementation's value mathematically is a good step toward depoliticizing the scheduler. That should help in what's been a contentious piece of the kernel of late.
    • by ianare ( 1132971 ) on Saturday September 01, 2007 @04:46PM (#20435957)
      One would hope, but it doesn't look like it's going that way. If you look at Ingo's reply, then Roman's reply to that, you can see what could be the start of yet another flame fest :

      Hi,

      On Fri, 31 Aug 2007, Ingo Molnar wrote:

      > So the most intrusive (math) aspects of your patch have been implemented
      > already for CFS (almost a month ago), in a finegrained way.

      Interesting claim, please substantiate.

      > Peter's patches change the CFS calculations gradually over from
      > 'normalized' to 'non-normalized' wait-runtime, to avoid the
      > normalizing/denormalizing overhead and rounding error.

      Actually it changes wait-runtime to a normalized value and it changes nothing about the rounding error I was talking about. It addresses the conversion error between the different units I was mentioning in an earlier mail, but the value is still rounded.

      > > This model is far more accurate than CFS is and doesn't add an error
      > > over time, thus there are no more underflow/overflow anymore within
      > > the described limits.

      > ( your characterisation errs in that it makes it appear to be a common
      > problem, while in practice it's only a corner-case limited to extreme
      > negative nice levels and even there it needs a very high rate of
      > scheduling and an artificially constructed workload: several hundreds
      > of thousand of context switches per second with a yield-ing loop to be
      > even measurable with unmodified CFS. So this is not a 2.6.23 issue at
      > all - unless there's some testcase that proves the opposite. )

      > with Peter's queue there are no underflows/overflows either anymore in
      > any synthetic corner-case we could come up with. Peter's queue works
      > well but it's 2.6.24 material.

      Did you even try to understand what I wrote? I didn't say that it's a "common problem", it's a conceptual problem. The rounding has been improved lately, so it's not as easy to trigger with some simple busy loops. Peter's patches don't remove limit_wait_runtime() and AFAICT they can't, so I'm really amazed how you can make such claims.

      > All in one, we dont disagree, this is an incremental improvement we are
      > thinking about for 2.6.24. We do disagree with this being positioned as
      > something fundamentally different though - it's just the same thing
      > mathematically, expressed without a "/weight" divisor, resulting in no
      > change in scheduling behavior. (except for a small shift of CPU
      > utilization for a synthetic corner-case)

      Everytime I'm amazed how quickly you get to your judgements... :-( Especially interesting is that you don't need to ask a single question for that, which would mean you actually understood what I wrote, OTOH your wild claims tell me something completely different.

      BTW who is "we" and how is it possible that this meta mind can come to such quick judgements?

      The basic concept is quite different enough, one can e.g. see that I have to calculate some of the key CFS variables for the debug output. The concepts are related, but they are definitively not "the same thing mathematically", the method of resolution is quite different, if you think otherwise then please _prove_ it.

      bye, Roman
      • by HeroreV ( 869368 ) on Saturday September 01, 2007 @10:26PM (#20437765) Homepage
        When will people learn that being rude doesn't help? If you want somebody to work with you, you need to play nice. It's not pleasant, and it's not easy to make yourself calm down and act like a pussy, but it's important if you ever want any collaboration.

        Example:

        Interesting, but I don't see this. Can you point it out?

        I think you misunderstood me. It may not be a common problem, but it is a conceptual problem. The rounding has been improved lately, so it's not as easy to trigger with some simple busy loops. Peter's patches don't remove limit_wait_runtime() and AFAICT they can't, so I don't see how what you said can be correct.

        I'm worried about how quickly you judged this issue, and that you haven't been more in contact with me discussing it. This issue is important to me, and I'd really like to work with you to get it resolved.
        • Re: (Score:3, Interesting)

          by ccp ( 127147 )

          When will people learn that being rude doesn't help? If you want somebody to work with you, you need to play nice. It's not pleasant, and it's not easy to make yourself calm down and act like a pussy, but it's important if you ever want any collaboration.

          (emphasis mine)

          Very true, but I have this suspicion that some hacker's rudeness is intended to piss people off and keep the field, the spotlight, and the pressumed "glory" to themselves.

          Sad thing is, it works a lot of the time, and you can always blame old

    • Re: (Score:3, Interesting)

      Math is reliable, but it's slow going, even for very simple math.

      People prefer verbal reasoning, even though all kinds of logical errors can slip in undetected, for the simple fact that they can read it at the speed of speech -- even if they really shouldn't.

      This is PAINFULLY evident in the software world. I imagine even kernel developers tend to be lazy this way.
      • by Goonie ( 8651 ) * <robert,merkel&benambra,org> on Saturday September 01, 2007 @06:11PM (#20436377) Homepage
        A fair proportion of the time, the mathematics applied in computer science (and, probably, most other disciplines) starts with simplifying and often unrealistic assumptions.

        Not that maths isn't useful, but much of the time it can't give you definitive answers for the questions you really want answers to, only somewhat related, simpler ones.

        • The practice of making simplifying assumptions is mainly a problem when modeling performance. In this case, the guy was just describing the calculations that his code made. You don't have to model every aspect of behavior to model some aspects rigorously. Math bugs in microprocessors aside, I can't think of any reason why he would have needed to compromise rigor. (A typical mistake here would have been to ignore some limitations of computer arithmetic, but the limitations of computer arithmetic were cen
  • by WombatDeath ( 681651 ) on Saturday September 01, 2007 @04:04PM (#20435735)
    In which no process gets any resources at all. I've also been considering a quantum scheduler, in which each CPU cycle is assigned to every process simultaneously.

    Shit, I've just figured out why I'm a project manager.
    • Re: (Score:3, Informative)

      by roman_mir ( 125474 )
      Pay per scheduler, the kind that allocates time to processes that are initialized by the highest paying bidder. I am aiming for a CEO.
    • You're already at 5 Funny, so all I can do is say that is a pretty dang funny post, the second line made me laugh out loud (not just the LOL that everyone types, but the real laugh out loud where the guy next to you wonders what the hell you're doing)
    • I thought you were an off-shore helpdesk?
    • I've also been considering a quantum scheduler...

      Otherwise known as the Heisenberg Uncertainty Scheduler.

      The main problem with this is you can know which process is scheduled or which will be next, but not both. In fact, the act of scheduling would probably alter the scheduler itself.

  • This post (Score:4, Funny)

    by fishthegeek ( 943099 ) on Saturday September 01, 2007 @04:18PM (#20435823) Journal
    has been scheduled for use by the slashdot server farm on September 6, 2007 at 14:54:23. Please refresh this page at that time for fishthegeek's insightful comment.

    Automatically generated by:
    Slashdot Predictive Post Scheduler v 2.12.02-16
  • More flame bait? (Score:5, Insightful)

    by Bryan Ischo ( 893 ) * on Saturday September 01, 2007 @04:29PM (#20435891) Homepage
    I read the article in question. There is obviously much disagreement about the value of the Really Fair Scheduler, and so I must assume that "derrida" and the Slashdot editors are once again just trying to invite more people to the flame-fest as usual.

    The comments on the article at the linked-to site suggest that there are potentially flaws in the logic behind the Really Fair Scheduler, and that its author has ignored advancements in the CFS that make most (or all?) of its improvements irrelevent. Also there are many suggestions that the author of the Really Fair Scheduler, some guy named Roman something-or-other, is raging on the kernel lists rather than working cooperatively to improve the Linux scheduler.

    Given what I have seen, I suspect that the Really Fair Scheduler is going nowhere, and that "derrida" knows that and is just trying to add more fuel to the flame-fire by posting about it on Slashdot.

    • and so I must assume that "derrida" and the Slashdot editors

      I don't know who you are but in cases like this we need facts and not assumptions, not perceptions, not mild understandings of issues.

      • I suspect what we need in cases like this is for everyone who wouldn't have know about this except through Slashdot to just STFU and GTFA. So, err, this will be my last post in this thread :-)
    • by Dr. Spork ( 142693 ) on Saturday September 01, 2007 @05:36PM (#20436215)
      You could be right, but Roman is in a tough position, because he's arguing for a change that he thinks is big, and Ingo seems to be trying to sap his enthusiasm by telling him to essentially "work on what we're doing" when Roman wants to have a debate about the best architecture for the scheduler.

      In order to help give substance to the debate, Roman coded together some proof-of-concept stuff, but instead of his architectural ideas being looked at seriously and critically, Ingo instructs him to strip away most things and "well use it." That really should seem to everyone on the sidelines like Roman's ideas are being ignored without debate. Now, maybe Ingo is polite, Roman's work just sucks, and Ingo won't confront him on it. But if that's not the case, maybe there should be a (non-flamey) debate about the best architecture for the scheduler.

      • Re: (Score:3, Funny)

        by Hooya ( 518216 )
        Or perhaps he's dreading having to say:

        My name is Ingo Molnar, you kill -9ed my scheduler. Prepare to oops!
  • ingo's reply (Score:5, Informative)

    by ianare ( 1132971 ) on Saturday September 01, 2007 @04:32PM (#20435909)
    Ingo's reply can be found here [lkml.org]. Roman's reply to that is here [lkml.org] and here [lkml.org]
    • poor guy... :(
    • Question: Can not someone run both schedulers through the same series of severe test cases (unit testing) and analyze the results, allowing the authors of each to add more test cases as needed to prove points. At some point the strengths and weaknesses of each will become apparent. End of the day results will be the proof.
      • Re: (Score:3, Interesting)

        by budgenator ( 254554 )
        The problem is Linux is used in a spectrum of 3 obvious types, servers, workstations and desktop and the developers tend to be very sensitive to the server and workstations areas so in the end of the day it'll be test cases that favor servers vs. test cases that favor desktops. What makes me wonder is why don't they develop three, each one optimized for a particular usage pattern and just let me select the kernel I want with GRUB? It should be possible to modify init to select the correct rc.conf to each pa
        • Don't forget the embedded spectrum, which likes Ingo's -rt patch. Which is currently being merged into the kernel. [osadl.org]
          I actually think that its at the heart of why Linus has given Ingo the go-ahead to do the CFS scheduler, because ultimately the CFS and -rt scheduler will be one and the same, or CFS layered ontop of -rt. What this means is more usage of the vanilla kernel for embedded devices instead of the 'other' real time Linux derivatives such as RT Linux from FSM labs and the RTAI patch.
  • by Anonymous Coward on Saturday September 01, 2007 @04:52PM (#20435985)
    Screw the CPU scheduler at this point. The kernel folks are missing the obvious and utter brokenness of the IO scheduling. These bugs have been outstanding about a year now!! And it's not just AMD64 anymore either. Quoth the kernel bug report:

    "Now, as far as this bug being AMD64 only. We develop a portable data analysis
    tool and we run it on Intel Core Mobile systems (Sony UX series, Panasonic
    Toughbook series) and see this bug or one almost exactly like it on those
    platforms as well.
    "

    http://bugzilla.kernel.org/show_bug.cgi?id=7372 [kernel.org]
    http://bugzilla.kernel.org/show_bug.cgi?id=8636 [kernel.org]
    http://www.nabble.com/IO-activity-brings-my-deskto p-to-its-knees-(2.6.22.1-ck1)-t4192136.html [nabble.com]
    http://forums.gentoo.org/viewtopic-t-482731-start- 500.html [gentoo.org]

    At first, deadline IO was touted as an answer, but that doesn't completely fix things.
    Some say Native Command Queueing is broken. One person claims deadline + NCQ disabled helps.
    Some say the kernel's vfs_cache_pressure settings help, while others refute it (compare kernel bug report versus page 21 of the gentoo forum thread). But no one understands what's really broken in the kernel.

    Can we please get Ingo working on IO scheduling? PLEASE?
  • by r00t ( 33219 ) on Saturday September 01, 2007 @04:53PM (#20435989) Journal
    Who's the fairest scheduler made?
  • Sausages (Score:5, Funny)

    by chiok ( 858005 ) on Saturday September 01, 2007 @07:10PM (#20436707)
    "To retain respect for sausages and Linux schedulers, one must not watch them in the making."
    -- Otto von Bismarck (paraphrased)
  • by elmartinos ( 228710 ) on Saturday September 01, 2007 @07:40PM (#20436941) Homepage
    Writing a fair scheduler is difficult. Why not let the user decide? I propose a popup message for each context switch: "Hello, it seems the CPU is doing a context switch. Which application to you want to allow to run this time?".
  • by DeVilla ( 4563 ) on Saturday September 01, 2007 @10:35PM (#20437811)
    Does Linus like him? More than Ingo?
  • Next week: (Score:4, Funny)

    by bytesex ( 112972 ) on Sunday September 02, 2007 @02:23AM (#20438659) Homepage
    Next week: a completely new scheduler, written by Ingo, in 05:12:43.33213, called the 'Astoundingly Fair Scheduler', which doesn't look at all like this new improvement, especially - hey look ! Something shiny ! And in two weeks time, a defence written by Linus Torvalds, detailing why the AFS is so much better than the RFS, and why Ingo can be trusted so much more when it comes to maintaining stuff like that.
  • Bunch of school kids. Life is unfair, deal with it.

    Suggestions for next iterations: Ass of a scheduler, bastard scheduler, unfair bully scheduler, depressed goth scheduler... (I will leave the exercise of figuring out the allocation semantics to reader)
  • Review feedback (Score:5, Informative)

    by Ingo Molnar ( 206899 ) on Sunday September 02, 2007 @09:29AM (#20441021) Homepage

    Oh my gosh, the Linux scheduler is on Slashdot. Again! :-)

    Frankly, this amount of interest in the Linux scheduler is certainly flattering to all of us Linux scheduler hackers, but there are certainly more important areas that need improvement: 3D support, the MM / IO schedulers, stability, compatibility, etc. (There's also the FreeBSD scheduler that went through a total rewrite recently - and it got not a single Slashdot article that i remember.)

    But i digress. A couple of quick high-level points (most of the details can be found in the discussions on lkml):

    I find the RFS submission interesting and useful, and i have asked the author to split the patch up a bit better, to separate the core idea from optimizations and unrelated changes - to ease review and merging of the changes, and to make the changes bisectable during QA after they have been applied to the mainstream kernel. (That is how patches are typically submitted to the Linux-kernel mailing list - it's a basic requirement before anything can be merged. CFS for example was applied to the 2.6.23 development tree in form of a series of 50 (!) separate patches. (And the scheduler works at every patching/bisection point.))

    I also pointed him to the latest "bleeding edge" scheduler tree, which already implements the same non-normalized form of math and makes some of the rounding and performance arguments moot i believe. (lkml mail [iu.edu]).

    There are some issues where i disagree with Roman at the moment: even when comparing to unmodified current upstream CFS, i think Roman makes too much out of rounding behavior and i have asked him to substantiate his claims with numbers (lkml mail) [iu.edu].

    The current precision/rounding of CFS is better than one part in a million. (in fact it's currently even better than that, but i'm saying 1:1000000 here because we could in the future consciously decrease precision, if performance or simplicity arguments justify it.)

    I can understand his desire towards creating interest in his patch, but IMO it should not be done by unfairly (pun unintended ;) trash-talking other people's code. The math code in CFS that achieves precision has gone through more than 5 complete rewrites already in the 20-plus CFS versions, and the current variant was not written by me but was largely authored by Thomas Gleixner and Peter Zijlstra.

    New, better approaches are possible of course and the math is relatively easy to replace, due to the internal modularity of CFS. So we are keeping an open mind towards further improvements. (which includes the possibility of total replacements as well. Dozens of times has my own kernel code been replaced with new, better implementations in the past - and that includes large parts of the scheduler too. In fact only ~30% of current kernel/sched.c was authored by me, the rest has been written by the other 90+ scheduler contributors, according to the git-annotate output that covers the past ~2.5 years of kernel history. Beyond that numerous other people have contributed to the scheduler in the past.)

    About the submitted code: it was a bit hard to review it because the new code did not contain any comments - it only included raw code - which is very uncommon for patches of such type. The email gave the theoretical background but there was little implementational detail in the patch itself connecting the theory to practice.

    So to drive this issue forward i have today posted a question to Roman in form of a tiny patch [iu.edu] that extracts only his suggested new math from his patch and applies it to CFS. If it is indeed what Roman intended then we can analyze that in isolation and in more detail. The patch is as small as it gets:

    include/linux/sched.h | 1 +

    • Re: (Score:3, Informative)

      by MrCopilot ( 871878 )
      Nice to see you interested in our interest. I've read your lkml responses and they reinforce Linus' decision to chose you to Maintain the Scheduler (IMHO).

      It should be pointed out to all Kernel Hackers, the kernel is the product, not a place for their pet project unmodified. No offense to Roman. This part of the code is a bit beyond me, But your approach to his patches seems reasonable. I hope he follows up with the patches you requested. We all want a faster "Fair" scheduler.

      Like many here, I was intr

    • Re: (Score:3, Insightful)

      by scumdamn ( 82357 )
      Speaking of unfair, I think it's completely unfair for you to ruin a wonderful flame war based on supposition and misunderstanding. How dare you roll up on Slashdot busting caps with your reasoned approach, data, and project management skills? Now this topic of conversation is hosed because nobody can BS their way through why you're a bad guy who's stepping on Roman's neck because of some daddy issues or something. Sheesh, of all the gall...

"The vast majority of successful major crimes against property are perpetrated by individuals abusing positions of trust." -- Lawrence Dalzell

Working...