Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
BSD Operating Systems

New Scheduler Available for FreeBSD 232

Posted by Nik from the doesn't-blink-LEDs-when-switching-processes dept.
flynn_nrg writes "Luigi Rizzo, one of the FreeBSD developers, has just finished the code for a new scheduler. From the announcement: '...as promised, a first version of the Proportional Share scheduler that we developed is available here. These are for a recent -STABLE (i think any version from 4.4 should work; the only 3 files modified are kern_synch.c, kern_switch.c and proc.h, plus a one-line change to kern_exit.c). I have tested it a little bit on a diskless system, and it seems to survive running a full X session with the usual set of xterm, netscape etc. while i do a "renice" of the processes and even switch back and forth between schedulers. But do not trust this yet for a production system!' Read the full post here."
This discussion has been archived. No new comments can be posted.

New Scheduler Available for FreeBSD More

New Scheduler Available for FreeBSD

Comments Filter:

  • Why? (Score:1, Insightful)

    by Dratman ( 552554 )
    What is the purported advantage of the new scheduler?

    • Re:Why? (Score:3, Informative)

      by Anonymous Coward
      "There are compelling reasons to use proportional share scheduling techniques to support multimedia and other soft real-time applications on general-purpose operating systems. First, proportional share (PS) schedulers are a good match for existing infrastructure such as a periodic timer interrupt and mechanisms for assigning priorities to applications -- priorities can be mapped to shares in a proportional-share environment. Second, PS schedulers provide stronger guarantees to applications than do traditional time-sharing schedulers: they allocate a specific fraction of the CPU to each thread, and some schedulers provide error bounds on the allocation rate. Third, PS schedulers have clear semantics during underload: excess CPU time is allocated fairly, in contrast with some reservation-based schedulers that must idle or back off to a secondary scheduling policy once all application budgets are exhausted."

    • Re:Why? (Score:2, Funny)

      by Waffle Iron ( 339739 )
      What is the purported advantage of the new scheduler?

      Doesn't anybody read the submitters' article summaries any more? It says right at the top of this page that the new scheduler is Proportional. That's the advantage. We can therefore infer that the old one is inferior for a related reason: it's not Proportional.

      I'm all for good proportions. Kudos to the implementors. Keep up the good work.

  • uniprocessor only. (Score:2, Interesting)

    by Anonymous Coward
    what the hell happenned to developing SMP and UP capable schedulers ? or does BSD expect to run well on only UP systems ?

    • Re:uniprocessor only. (Score:2, Informative)

      by m0rten ( 307847 )
      The scheduler is far from finished, and would likely need a lot more work. Integrating it into 5.0-CURRENT (and bringing in the SMP support along with it) is already under way, but could probably take some time.
  • Why does this get on the main page, and why does the new Core Team [slashdot.org] does not?

    Either way, FreeBSD does fit the new trend now... more VM's means more freedom :)

  • No clue what Proportional Share Scheduling is? (Score:5, Informative)

    by arnoroefs2000 ( 122990 ) on Monday July 22, 2002 @04:01PM (#3933082) Homepage
    There's more info here [utah.edu].

    Excerpt:

    "There are compelling reasons to use proportional share scheduling techniques to support multimedia and other soft real-time applications on general-purpose operating systems. First, proportional share (PS) schedulers are a good match for existing infrastructure such as a periodic timer interrupt and mechanisms for assigning priorities to applications -- priorities can be mapped to shares in a proportional-share environment. Second, PS schedulers provide stronger guarantees to applications than do traditional time-sharing schedulers: they allocate a specific fraction of the CPU to each thread, and some schedulers provide error bounds on the allocation rate. Third, PS schedulers have clear semantics during underload: excess CPU time is allocated fairly, in contrast with some reservation-based schedulers that must idle or back off to a secondary scheduling policy once all application budgets are exhausted."
  • Im currently using linux with the low latency patch and pre-emptive multitasking. Does this help X seem a little smoother on BSD also?

  • 0(1) scheduler (Score:5, Informative)

    by Sivar ( 316343 ) <charlesnburns[@]gmai l . c om> on Monday July 22, 2002 @04:15PM (#3933185)
    Is FreeBSD's new one a 0(1) scheduler?
    0(1) is a "term" from computer science. When applied to schedulers, it basically means that no matter how many processes there are to schedule, a 0(1) scheduler's overhead will not significantly increase.
    Of course, with a small number of threads/processes to schedule, the Linux 0(1) scheduler will have greater initial overhead. It isn't until there are quite a few processes that it starts to show its power, and the more processes there are, the more useful it is.
    On a busy server with 4+ processors and thousands of processes, a standard scheduler's overhead is so great that it often exceeds the overhead of most of the individual server processes.

    • Re:0(1) scheduler (Score:3, Informative)

      by Osty ( 16825 )

      Is FreeBSD's new one a 0(1) scheduler?

      Just a nitpick. The term is "O(1)", not "0(1)", as in "Big Oh of 1" and not "Zero of 1".

    • Re:0(1) scheduler (Score:2, Interesting)

      by pgpckt ( 312866 )

      a 0(1) scheduler's overhead will not significantly increase.

      The term you are looking for is probably O(n), but definatly not O(1). O(1) will not increase at all, no matter how much data is put in. O(n) will increase linearly.
      • The term you are looking for is probably O(n), but definatly not O(1).
        No, he means O(1) scheduler [google.com], definitely not O(n). Most simple scheduling algorithms (e.g., basic round robin) are constant-time, and a contant-time scheduler patch [redhat.com] was recently released for Linux.

        Just think about it logically. Why would he expectantly ask if the scheduler was O(n)? Name one super-linear scheduling algorithm in use in modern operating systems.

      • O(1) will not increase - right. That is a good thing, wou want the scheduler to be as efficient as possible - right?
        • The running time can vary for given N, just not for abtrirary N. As demonstrated by the following code. It runs fastest when n = 1, followed by n = 2, but is still O(1) when n is not 1 or 2, because the running time is constant for large n.

          int orderOneButVarying(int n) {
          if (n == 1) {
          return n;
          } else if (n == 2) {
          for (int i = 0; i 3; i++) {
          n*=n;
          }
          return n;
          }

          for (int i = 0; i 1000; i++) {
          n+= n / 2;
          }

          return n;
          }

    • Re:0(1) scheduler (Score:1, Informative)

      by Anonymous Coward
      The original 4.4BSD scheduler was already O(1) (by use of priority buckets).

      It is only Linux that had (for a long time) the O(n) problem (all runnable tasks/threads in a single linked list that had to be fully scanned to find which one to run - ick!).
    • Is FreeBSD's new one a 0(1) scheduler?

      No, it O(log n) scheduler. Read the mails.

  • Darwin? (Score:3, Interesting)

    by BlackGriffen ( 521856 ) on Monday July 22, 2002 @04:25PM (#3933249)
    Anybody have any idea when/if Apple will integrate improvements from this scheduler in to Darwin/OSX?

    • Re:Darwin? (Score:5, Informative)

      by Sivar ( 316343 ) <charlesnburns[@]gmai l . c om> on Monday July 22, 2002 @04:39PM (#3933328)
      The scheduler is closely tied with the kernel, and MacOSX does not use the FreeBSD kernel at all. It uses the Mach kernel, which is not only a different kernel entirely but a different core kernel philosophy. Mach is a microkernel whereas FreeBSD's is a monolithic kernel. Both types have their advantages and disadvantages, but microkernels are vastly superior for a commercial OS and for driver installations. Monolithic kernels are theoretically faster and easier to implement.

      MacOSX gets its BSD label by using the BSD userland utilities. It is great that Mac's OS is no longer junk. In three months I went from "Macs are toy computers for kiddies and Photoshop pros" to "Wow--I can replace every PC and OS in my house with a single Mac! Great desktop, good server, and all the power of Unix."
      I have never been happier with the state of Apple Inc.
      • Cool, I always figured OS X was monolithic. That sort of reminds me of the famous usernet debate [google.com] between Linus and Andy Tanenbaun (MINIX) in 92 covering "microkernel vs monolithic systems". It was an interesting read, in I believe Linus stated "True, linux is monolithic, and I agree that microkernels are nicer."

      • Re:Darwin? (Score:5, Informative)

        by Drishmung ( 458368 ) on Monday July 22, 2002 @05:21PM (#3933547)
        Not quite. This link [apple.com] gives quite bit more background about Darwin. In particular:
        Part of the history of Mac OS X goes back to Berkeley Software Distributions (BSD) UNIX of the early seventies. Specifically, it is based in part on BSD 4.4 Lite. On a system level, many of the design decisions are made to align with BSD-style UNIX systems. Many of the libraries are derived from NetBSD (http://www.netbsd.org/), while many of the utilities are from FreeBSD (http://www.freebsd.org/). For future development, Mac OS X has adopted FreeBSD as a reference code base for BSD technology. Work is ongoing to more closely synchronize all BSD tools and libraries with the FreeBSD-stable branch.

        Although Mac OS X must credit BSD for most of the underlying levels of the operating system, Mac OS X also owes a major debt to Mach. The kernel is heavily influenced in its design philosophy by Carnegie Mellon's Mach project. The kernel is not a pure microkernel implementation though since the address space is shared with BSD processes.

        The Mac OS X kernel (also known as XNU) is a monolithic kernel (unlike Mach, but like Linux and xBSD) with Mach and BSD sitting side-by-side.

        Some earlier Apple Unix efforts were true micro kernel implementations. This was also driven by the attraction of a pure hardware abstraction layer. With Darwin this seems to have moved to a more pragmatic recognition that performance matters.

        In Darwin, the Mach bits handle memory management, IPC and device drivers. BSD handles users and permissions, the network stack, the virtual file system and POSIX.

        So, this won't directly benefit Darwin, though if it is generally useful then someone/anyone can try and put it into Darwin---long live open source! I confess I don't know how the Mach part of Darwin handles scheduling, though I had heard that the Mach VM and scheduling was pretty good.

        • That is a very informative link, thanks!
          Someone please mod this person up as my comment, currently at +5 (undeservingly), obviously has some flaws that Drishmung has corrected.
  • the only 3 files modified are kern_synch.c, kern_switch.c and proc.h, plus a one-line change to kern_exit.c

    I hate to be picky .. but that's 4 files modified. One-line or a thousand, it's still been modified.
    </END-RANT>
    • And modifying a .h file is modifying every file that includes it. How many files include proc.h? Sounds like a popular include file.
  • I've been poking my newbie nose around in scheduling for a little while, and while I still know very little I've found the field very interesting. It's always neat to see new features and techniques being tried, but there's a feature that exists in the windows nt scheduler that (as far as I can tell) is absent in *nix operating systems. Winnt maintains (I think) four process queues (realtime, high, normal, and idle) into which all processes fall. Every time the scheduler is run, it checks to see if any "realtime" processes can be run, then "high", then "normal", and finally "idle". Processes in "less important" queues are only run if all processes in "more important" queues cannot be run (i.e. they're blocking on input or whatever), or those queues are empty. I find this very useful because I can set a long-running cpu dependent process to "idle" priority and it will be run at nearly 100% cpu usage when the machine is idle, but will instantly get out of the way and not be run at all if I choose to run something else (e.g. a game), no matter how high it's "goodness" value gets from not using any cpu time.

    Is there any reason why something like this isn't implemented in Linux or FreeBSD? Low on the developers' feature priority list (har har)? Too difficult? Unnecessary?

    Thanks. I'd appreciate any feedback.
    • eeh? It's allready there, since the dawn of the dinosours. Check "man renice"!
      My SETI@home run at 100% only when my CPU is idle...
    • Not needed. Linux and FreeBSD both handle different priority levels quite nicely, and in fact can handle them in a much more fine-grained fashion. NT actually has additional priority levels in-between each that you described above, but Linux and BSD have a total of 41 possible priority values (from -20 to 20, including zero)
      If you set an application to a priority of 20, it isn't going to be bothering any other processes, and if you set an application to -20, it is going to be worshipped like a god by the scheduler.
      As far as I know, neither have a real-time scheduling mode like NT, which is actually a good thing in many cases. If a program running at real-time priority goes into an infinite loop, or for any reason uses 100% of hte CPU (SETI@Home, for example) than the system is locked the hell up. Even the mouse will not get any time for cursor movement, and you have to reset the machine.

      Read "man nice", "man renice", and probably "man top" (which I use to change priorities of running processes as root)
      • Not needed. Linux and FreeBSD both handle different priority levels quite nicely, and in fact can handle them in a much more fine-grained fashion. NT actually has additional priority levels in-between each that you described above, but Linux and BSD have a total of 41 possible priority values (from -20 to 20, including zero)
        Actually they can have much more than that, but the "user" can only set those 41 values. There isn't even a definition of how they have to map (so for instance you can have the schedular have priorities -20 to 20 including zero but in 0.5 increments. Or just -40 to 40 in 1.0 increments etc.
        As far as I know, neither have a real-time scheduling mode like NT, which is actually a good thing in many cases. If a program running at real-time priority goes into an infinite loop, or for any reason uses 100% of hte CPU (SETI@Home, for example) than the system is locked the hell up. Even the mouse will not get any time for cursor movement, and you have to reset the machine.
        Do "man sched_setparam" and man "setpriority" to learn about "real time" processes. Linux also had patches for SCHED_IDLE at one point, but that can cause pretty bad reasource deadlocks without priority inversion and so was never integrated.

        There can be problems if your "real time" process misbehaves but then don't do that.

        NOTE: The term "real time" is used to mean best effort at real time, for true real time you don't use a general purpose OS (Ie. NT doesn't count either).

      • I disagree to some extent with comments that Linux has a scheduler that is 'good enough.'

        I ran some real time multimedia streaming applications under linux a while ago (LiveIce; very nice tool) and found that even using nice, I would occationally get glitches in the stream output during broadcasts.

        Switching to FVWM helped somewhat, as did nice... But when it cames right down to it, I don't think this should have been a problem.

        • Try it with a low-latency or pre-emptive-scheduling patched kernel. By default the kernel is tuned as a server, not a multimedia workstation. The kernel team seems to be working to correct this by adding compile time options and/or a new scheduler, but for now, on stable kernels, it requires patches.

          I've personally found that the patches make an amazing improvement in UI responsiveness and media playback. I'm looking forward to 2.6.

      • The nice value is merely a weighting factor that is used in the calculation of a task's the priority. The actual priority of a task depends upon what the task is, how much CPU time it's used recently, and which run queue the task has been assigned to. Indeed, each process has two priorities, one for user-mode execution, and one for kernel-mode execution. Renicing a process -20 and expecting it to be treated as god may seem a reasonable inferance, but if you ever delve into the internals of BSD you'll discover how wrong you are - and how brain numbingly complex priority scheduling actual is.
    • Is there any reason why something like this isn't implemented in Linux or FreeBSD?

      FreeBSD does have something like this: idle, normal, and real time. By default it is normal, but you can change it to idle (idprio(1)) or real time (rtprio(1)).

      In the man page for rtprio(1) is one relevant bug:
      "Under FreeBSD system calls are currently never preempted, therefore non-realtime processes can starve realtime processes, or idletime processes can starve normal priority processes."

      Maybe the new scheduler will fix this?
    • On Linux and (I believe) FreeBSD, the ability to set processes to different levels of realtime priority has been in place for years. Very recent (last couple weeks?) versions of the new Linux O(1) scheduler can do "idle" priority, and it will probably be in the 2.6 mainstream kernel.

      Implementing the idle priority is hard, because if an "idle" task gets a lock on a crucial resource and gets preempted, any non-idle tasks that need that lock must then wait for the system to become idle -- potentially an indefinite amount of time.

    • Is there any reason why something like this isn't implemented in Linux or FreeBSD?
      Mostly because it's already implemented on both systems. For freebsd see rtprio, idprio, and of course good old nice.

Slashdot Top Deals

I've noticed several design suggestions in your code.

Close