Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror
×
Linux Software

Bossa, a Framework for Scheduler Development 152

Eugenia writes "The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems. This article gives you a glimpse of what scheduling development is like by letting you implement your own Linux scheduler thanks to Bossa, a framework for scheduler development."
This discussion has been archived. No new comments can be posted.

Bossa, a Framework for Scheduler Development

Comments Filter:
  • by grub ( 11606 ) <slashdot@grub.net> on Thursday July 08, 2004 @03:49PM (#9646844) Homepage Journal

    Most commodity computers can only run one process at a time

    Ha, with Longhorn 2010XP+++ and Office 2012 I'll be able to have two Clippys simultaneously! Take that, hippy!
  • by GillBates0 ( 664202 ) on Thursday July 08, 2004 @03:53PM (#9646887) Homepage Journal
    I see your FIFO scheduler and raise you my Elevator algorithm!
  • Ordinary users? (Score:4, Insightful)

    by MisterFancypants ( 615129 ) on Thursday July 08, 2004 @03:57PM (#9646914)
    "The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems"

    I know some people will take this as flamebait, but I honestly don't mean it to be. However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

    Users don't care about OS internals. Don't send them to a page explaining OS scheduling, just tell them "All new Linux makes your applications more responsive!". That's all they want to hear.

    Seriously.

    • by ErichTheWebGuy ( 745925 ) on Thursday July 08, 2004 @04:02PM (#9646961) Homepage
      parent poster is right. one of my wannabe-geek coworkers saw that and asked me, "doesn't evolution take care of your scheduling needs?" I am not joking. True story.
    • Re:Ordinary users? (Score:1, Insightful)

      by Anonymous Coward
      If you don't want to know what a scheduler is, you don't have to read the article. I don't know what bothers you about this. Nobody is asking the users to write their own scheduler.
    • What the poster meant was that the introduction of the O(1) scheduler, and the benefits to user experience it provided, caused a lot of "ordinary users" to take notice. That doesn't necessarily mean most "ordinary users" know, or even care.

      However, for those that do, you'll Soon be able to drop in the latest IO, CPU or 'whatever' scheduler, now being developed independantly from the kernel.
      • MOD PARENT UP (Score:1, Insightful)

        by Anonymous Coward
        This guy gets it. MisterFancypants is just looking for excuses to complain. The article never implied that ordinary users should care about, or even know about, scheduling. What it says is that scheduling algorithms are important for ordinary users. There is a world of difference between these two statements.
    • Re:Ordinary users? (Score:3, Insightful)

      by GammaTau ( 636807 )

      Users don't care about OS internals. Don't send them to a page explaining OS scheduling, just tell them "All new Linux makes your applications more responsive!". That's all they want to hear.

      I don't think the ordinary users (at least the ones you talk about) are readers of Slashdot or OSNews. This is not marketing material you are reading. It would be silly to judge it as such.

    • However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

      Are you suggesting the key to Linux's acceptance on the desktop is what CmdrTaco thinks is newsworthy on a geek website?

      That's something of a misnomer, because Malda does not develop linux kernel code. And the developers were not banging his door down insisting that Malda report a story on Bossa. Developers don't give a

    • Apparently, you've never gotten a woman to go home with you by promising to show her your new scheduler.

      (Okay, neither have I, but that's only because I'm married.)
      • In that case, it seems to be pretty easy to do so:

        you: Honey, do you want to come home and see my new scheduler?

        wife: Can you show it to me while I eat the leftover pizza, I'm hungry!

        you: Sure, but please pay attention this time, it's really really cool and neat!

        wife: That's what you said about your new Perl program, but it just looked like you banged on the keyboard for a couple of hours and held down the shift key.
        • But this is what you might prefer:

          wife: Honey, do you remember you promised to get your new scheduler done this weekend?
          you: Okay, but I was planning on mowing the lawn.
          wife: You used that excuse last week. Now won't you please finish the scheduler? *Starts rubbing geek's shoulders.* You know how smooth-running software makes me feel...

          Or:

          you: How'r you doing, Honey?
          wife: I'm almost done with my new Linux scheduler. It's really hot.
          you: *drools*
    • I tried to say sort of thing on slashdot the other day and got modded troll.

      Its refreshing to see that people who get it can be modded up.

      Linux is clever, Linux is powerful. Linux is not user friendly on a desktop. Users should not need to know the locations and contents of config files, and be familiar with dozens of command line commands just to do something simple.
    • Hello, welcome to Slashdot!

      This is a geek site. We talk about geek stuff here, like OS schedulers. If you want to hear "new linux makes computer faster!", go read some RedHat marketing materials.

      Just because your idea of the "average linux user" doesn't care about OS schedulers doesn't mean we're not allowed to talk about them.
    • I know some people will take this as flamebait, but I honestly don't mean it to be.

      No, you meant it as a troll. And a good work too, +5 insightfull and plenty of replies.

      Risin' up, straight to the top
      Had the guts, got the glory...

      However, as long as Linux is in a state where developers think that "ordinary Linux users" have to even care what a scheduler is, Linux will be a failure for mainstream desktop usage.

      Why is it that so many people have a problem understanding the difference between the expres

  • by Doc Ruby ( 173196 ) on Thursday July 08, 2004 @03:57PM (#9646917) Homepage Journal
    A really distributable system would include only the scheduler in the kernel, with an "outer" layer of secure (crypto signed, sealed and delivered) APIs for submitting process and data requests, and an "inner" core for hardware access, including CPU, data (storage/network such as ethernet, USB, IDE, RAM, BIOS ROM, etc) and presentation (monitors, keyboards, mice, soundcards, printers, etc). Such a nanokernel would be tiny, highly efficient, and mix/matchable with many other apps and OS'es. Privileges would be part of a comprehensive security model, with IPC filtered through access control, whether within a single memory segment, LAN, or WAN. All domains would be virtualized. And such symmetry and simplicity would set the stage for flexible inter-kernel load balancing and failover.

    We're talking open-ended scalability. Security. Performance. Reliability. The OS is no longer just a privileged app, but a smaller, more focused critter, serving apps rather than being served by them. With this new scheduler framework, let a billion nanokernels bloom.
    • And you've just created the need for a "sub-kernel" which would do your actual work. We're talking more complexity. More bugs. Less performance. Less security. You haven't made the kernel smaller, you've just pulled a part of it out because you think it'd be cool to hold its beating heart in your hand while it still runs.
      • by Doc Ruby ( 173196 ) on Thursday July 08, 2004 @04:16PM (#9647085) Homepage Journal
        No, those other jobs removed from the nanokernel run as independent apps. We've simplified the architecture, by reducing the inner complexity of the kernel, and moving its functions into the rest of the system. IPC and HW access are the only roles which need unique centralization, even in our "OS" paradigm. That means bugs are easier to identify, with fewer hidden dependencies (they're more overt). And performance is more granular, with less extra functions required to be loaded, and logically considered, to perform a specified task. Better security from the reduced trust among processes and the kernel, with a simpler model for their interoperation.

        The kernel is much smaller. The old kernel's functions are distributed in more, optional, dynamically (runtime) includable objects, so they might even be spread among a larger total object population. But that isn't necessary to specific operations, and that can be tuned at runtime, by some of the processes themselves. Just another step down the road away from the monolithic, single-task computer, for increased parallelism and manageability.
        • Just another step down the road away from the monolithic, single-task computer, for increased parallelism and manageability.

          I'm a neophyte at kernel design, so be patient. :-)

          How will this effect really high-end performance applications? Specifically, I'm thinking of music applications. The holy grail of desktop music production is a one-box solution. We want a single computing device with enough horsepower to do:

          • Realtime synthesis with a wide variety of highly complicated models from various sources
          • The smaller, more "agile" nanokernel could offer better interrupt handling and more granular CPU/memory accesses, therefore keeping more accurately on a realtime track. But for high-throughput realtime signal processing, another computing model is probably more appropriate: truly parallel logic arrays.

            True parallelism means the that clock rates don't have to be jacked up to millions of times the rate of the events being processed (eg. 100s of GHz for 10s of KHz audio), just to ensure that thousands of thou
      • Taco, it just struck me that the mod system is seriously remiss in not having a way to mod a post as being "Eloquent". It's really something different from "Interesting", isn't it.
        (It would also be nice to be able to search comments by mod-type.)

        I wish I could use it here:
        "You haven't made the kernel smaller, you've just pulled a part of it out because you think it'd be cool to hold its beating heart in your hand while it still runs."
    • by sploo22 ( 748838 ) <dwahler@gm a i l . c om> on Thursday July 08, 2004 @04:03PM (#9646967)
      You mean an exokernel [mit.edu]?
      • by Anonymous Coward
        No, it does sound like he's describing a microkernel (or "nanokernel", ugh) rather than an exokernel. The defining characteristic of an exokernel is that it provides no abstraction at all. It multiplexes hardware, but does not abstract it. There are no OS "system calls" in the traditional sense. There is no message passing; there are no OS provisions at all, really. Your "application" (which is really an operating system) deals with hardware, with the exokernel checking to make sure the device is being
        • Parent is correct. Mod up!
        • Mod parent up. It's correct.

          This is not about an exokernel. As the parent says:

          The defining characteristic of an exokernel is that it provides no abstraction at all.

          From http://www.pdos.lcs.mit.edu/exo.html:

          An exokernel eliminates the notion that an operating system should provide abstractions on which applications are built.

    • by Bloater ( 12932 ) on Thursday July 08, 2004 @04:17PM (#9647093) Homepage Journal
      > A really distributable system would include only the scheduler in the kernel

      No, a kernel doesn't even need to have a scheduler in it. It needs to be able to take instructions to transfer control to another cpu context, and be able to create the necessary page tables, and that's about it.
      • How does that kernel arbitrate competing requests from multiple outboard schedulers? First-come-first-served isn't going to work very well, and is subject to DoS attacks. And how would only a single outboard arbitrating scheduler be identified and enforced?
        • The scheduler can be a privileged/trusted process without being a part of the kernel.
          • How does that architecture address the security issues in my post, to which you responded? Examples?
            • Kind of like "init" works on Linux - you specify at boot time a trusted program to be your scheduler, which the kernel runs. As long as your scheduler is well-behaved there are no problems (and it will be well-behaved because YOU wrote it -- or your vendor, as the case may be).

              Perhaps I'm not understanding the issues you're raising.
              • The problem is ensuring that the scheduler running outside the kernel process could be replaced by a "hostile" scheduler. But I suppose that the child could use the same signed API access that I mention to ensure authenticated process access. Do you have any examples of existing kernels using your architecture?
    • it's probably called HURD. and will be ready next year.
    • by sql*kitten ( 1359 ) * on Thursday July 08, 2004 @04:19PM (#9647118)
      You are describing the IBM AS/400.
    • A really distributable system would include only the scheduler in the kernel, with an "outer" layer of secure (crypto signed, sealed and delivered) APIs for submitting process and data requests, and an "inner" core for hardware access, including CPU, data (storage/network such as ethernet, USB, IDE, RAM, BIOS ROM, etc) and presentation (monitors, keyboards, mice, soundcards, printers, etc). Such a nanokernel would be tiny, highly efficient, and mix/matchable with many other apps and OS'es. Privileges woul

    • I was under the impression that monolithic kernels, like micro-kernels, do the same job, which is simply to interface with hardware via assorted interfaces and their corresponding drivers (CPU, power management, peripheral buses, block device interfaces, networking, sound, video, etc.). The difference being that monolithic kernels can either have certain (non-critical) interfaces and drivers compiled into the kernel itself or externally as a module, whereas ie, Hurd has fixed modular interfaces to everythin

  • by Anonymous Coward on Thursday July 08, 2004 @04:01PM (#9646951)
    I thought everone was using MS project. No?
  • by Anonymous Coward
    What the hell is a scheduler?
    • by Timesprout ( 579035 ) on Thursday July 08, 2004 @04:15PM (#9647072)
      Depends how you pronounce it. If you pronounce it properly then it a vital part of the OS determining how the various running processes interact with the system, resources and each other. If you use the American pronunciation then its something KDE are probably working on to organise your time.
    • by The Analog Kid ( 565327 ) on Thursday July 08, 2004 @04:16PM (#9647086)
      What a Scheduler is. [wikipedia.org]
    • A scheduler is a part of the OS which decides what process has access to a given resource at a given time. The main scheduler is the process scheduler, which allocates which process gets to use a CPU right now. There's also schedulers for disk access, sending ethernet packets, and anything else that can only be accessed 1 at a time.
    • What the hell is a scheduler?

      The scheduler is the person on your project team who, after each week's schedule slips, tapes together the latest updated Gantt chart printouts into long banners and hangs them the walls.

    • by vadim_t ( 324782 ) on Thursday July 08, 2004 @05:06PM (#9647532) Homepage
      It's the part of the OS that determines what task to run.

      The problem is this: You want to run tasks A, B, and C, and need to do it in the most optimal way possible.

      The simplest way is FIFO, like say, DOS. If A starts first, then A runs until completion, then B starts. This is bad for many reasons, like that if A gets stuck for any reason nothing gets done, and that while A is waiting for input the free resources can't be used for anything else.

      A simple way of multitasking would be simply alternating between A, B and C every fixed interval. But that's not very good either, perhaps B doesn't need to do any processing now, and only wastes time, while C could really use that.

      A better way is to do it by priorities, but then you need to find a good way of calculating this priority.

      One of the reasons there's so much talk about them is that most become slower when you have more tasks. Most of the simple ones need to examine every running task to determine what should run now, and if you want to launch 10000 processes at once, that's not good. O(1) schedulers are a solution for that, because they use algorithms that always take the same amount of time to execute, irregardless of whether there's 3 or 10000 tasks. That doesn't mean a simpler scheduler wouldn't work faster for 10 tasks, though.

      The other problem is how to determine how to distribute CPU time. Say, for servers you mostly want fast and fair3o determine which processes are interactive, and which are on the background and won't mind some interruption.
  • I don't know that much about os programming, but I do remember back in my college days for our OS class, there was nothing I hated more than trying to progam a scheduler for our minuature OS assignment. Working with semaphores and locks... *shudder* keep the bad man away!!

    My condolences to all who do work on this part of the OS.

    • From the article

      If one's job is to develop scheduling algorithms, then one shouldn't have to hack kernel code.

      Exactly to bring back people like you

    • Re:eeek (OT) (Score:2, Interesting)

      by slashjames ( 789070 )
      Working with semaphores and locks... *shudder* keep the bad man away!!

      Just remember that it's those semaphores, mutexes, and locks that allow multi-threaded applications work. A class that is supposed to be "thread safe" but isn't will make your life rather... interesting.
      • Not knowing what "semaphores, mutexes, and locks" are in a scheduler, I still have to ask how a scheduler can make a "'threadsafe' but isn't" class be "safe"?
  • Are we back to "better scheduling?" ... I thought that was a mainframe technology struggle...........
  • I hope ... (Score:3, Funny)

    by The-Bus ( 138060 ) on Thursday July 08, 2004 @04:20PM (#9647121)
    I hope this succeeds, then gets improved upon in a second version. How cool would it be to be a part of the next project called... "Bossa Nova"?
  • Interrupts (Score:3, Interesting)

    by LordMyren ( 15499 ) on Thursday July 08, 2004 @04:21PM (#9647127) Homepage
    I have a sneaking support its poor interrupt handling which makes my ALSA skip like Riverdance every time i start a file copy in mid song.

    Even buffering the full song, it still skips. I've tried XMMS, moosic, mpg321. I've sought ever high priority trick i can. No matter what I try, start that file copy and WHAMO, instant pain and suffering.

    Myren
    • Re:Interrupts (Score:3, Informative)

      by plam ( 123263 )
      Have you turned on DMA for your hard drive? (hdparm -d 1 /dev/hda).
      • Re:Interrupts (Score:3, Informative)

        by cr0sh ( 43134 )
        hdparm has to honestly be one of the most undelooked at tools for increasing performance in a Linux system. Everything will get a boost from using hdparm - just remember to update your /etc/rc* scripts to reinstate your choices on reboot. A good document for hdparm can be found here:

        Speeding up Linux Using hdparm [linuxdevcenter.com]

  • by vijaya_chandra ( 618284 ) on Thursday July 08, 2004 @04:22PM (#9647141)
    10 penguins for anyone who can suggest a scheduler that taxes the stupid newbie programs with

    while(1);

    (/me too is a newbie)
    • 10 penguins for anyone who can suggest a scheduler that taxes the stupid newbie programs with

      while(1);

      Doesn't the scheduler in Linux 2.6 already prefer IO bound applications over CPU bound ones ?

  • The Bossa DSL is more constrained than C or C++ in that, for example, pointers (known for being the cause of many bugs) are absent and infinite loops can't be defined.

    The part about infinite loops would be interesting as you can always shoot yourself in the foot in a zillion ways

    For eg: a stupid like me might write something like

    do blahblahblah while f(pid1) is less than f(pid2)

    where f(x) isn't effected by blahblahblah() and f(x) is less than f(y) when x is less than y
    • The Bossa DSL is more constrained than C or C++ in that, for example, pointers (known for being the cause of many bugs) are absent and infinite loops can't be defined.

      The omega incomplete domain-specific language (DSL) is not a feature, its a bug. Turing machines have more smarts. The last thing I would want when writing a scheduler is some broken language that interferes with what I can do. If you can't be trusted with pointers and loops, you don't have any business writing a scheduler. Yes, you

      • Gadzooks, man. I don't have time to read the book you just posted, but I'll tell you one thing DSL shows is how lacking C is in expressing Finite State Machines.

        Like 15 years ago IBM had a language called FAPL which was cool at expressing FSMs -- totally useful for describing commmunications protocols or, in this case, scheduling protocols.

        But FAPL would probably make you sh*t bricks after your palpitations over DSL.

        PS -- I'll bet you're not really precluded by DSL from scheduling a task every 100 bogo
  • by nusratt ( 751548 ) on Thursday July 08, 2004 @04:59PM (#9647479) Journal
    "Working with semaphores and locks... *shudder* keep the bad man away!!"
    http://slashdot.org/comments.pl?sid=11388 0&cid=964 7043

    Actually, it's quite interesting. It forces you to conceptualize with a certain kind of rigor, and to code with particular vigilance for potential deadlocks, race-conditions, and mis-serialization of resource-updates.

    I can't tell you the number of times that I've read or listened to a description of a design or architecture, and immediately said "uh-oh", to the surprise and dismay of developers who really should know better.

    In a time of increasing processor parallelism, this is a skill-set which must be mastered by anyone who truly aspires to become (or remain) a serious professional-level developer. It's not just for kernel-hackers.
    • It frightens me when so many "programmers" or "software engineers" seem to be frightened by or even oblivious to concurrency problems. This should be a fundamental skill anyone writing software should have. Are there schools out there not teaching these basic concepts somewhere in their degree program?
      • Wow, I'm definately out of my league here. In the class I was referring to above, our prof made us create a pseudo os that would be able to handle multithreaded apps that my prof made up. The last app he made had multiple consumers, multiple producers, multiple resources, and totally inane production/consumption restrictions. My team was one of three (out of 24) that got that last one working perfectly. In any case it was very unpleasant experience (I suppose the time limit didn't help either).

        In my exper

  • by rsd ( 194962 ) on Thursday July 08, 2004 @05:09PM (#9647550) Homepage
    Using a plugin^Mmodule interface to load schedulers at runtime wouldn't generate
    a performance impact in the scheduler? (as opposed to have the scheduler compiled
    inside the kernel).

    I AFAIK, the scheduler has to be as compact (optimized) as possicible to reside as long as possible
    in the cpu's cache. This way it can check the memory pages map as fast as possible to [de]allocate,
    switch process as fast as possible.

    Using a module scheduler, wouldn't make it have to derreference each function address each time
    each function is called?
    And probably sometimes derreferencing derreferences few times to get the correct address?

    Couldn't this hurt performance?

    I agree that loading an efficient scheduler to handle a situation better than the defalt scheduller would
    compensate for that, but still...
    • If the modules are binary, the point is moot. If they're not, remember that a DSL can often encode the same functionality in less space (interpreter+data) than machine language. As you pointed out ourself, cache hitrate are extremely important, so by having less data to cache (and less new instructions to decode), the interpreter can probably be very competitive, or maybe even better than a binary.
  • The problem of multimedia apps running smoothly affects not only OS kernels, but also things like Java machine. Since Java is taking more serious tasks nowadays from streaming media in handhelds to (they say) NASA Mars rovers.

    With Real Time Java [rtj.org] a programmer can request explicit timing guarantees, by direct interaction with the scheduler. Just derive your threads from javax.realtime.RealtimeThread (if it is implemented in your version of Java :)

  • Sorry, but the name Bossa immediately invokes thoughts of Jar Jar Binks, as in : "Yousa Bossa. Jar Jar Binks thinka massa need a process."
  • I hope I coule use Generate algorithms to find out the best scheduler for the system.
  • Any errors that occur, all that will be able to be said is, "Blame it on the Bossa Nova [webfitz.com]." (Long groan follows.)
  • The recent activity in Linux kernel development caused by the introduction of a new scheduler by Ingo Molnar has emphasized for ordinary Linux users the importance of schedulers in modern operating systems. This article gives you a glimpse of what scheduling development is like by letting you implement your own Linux scheduler thanks to Bossa, a framework for scheduler development.

    I'm a bit confused... Is this about scheduling??

  • by ThePhin ( 525032 ) on Friday July 09, 2004 @10:27AM (#9652404) Homepage

    Xavier Leroy is one of the authors of Ocaml, an efficient (within 2x of C) variant of the ML functional programming language. In the Caml-list mailing list recently, he had this to say about scheduling:

    The 2.6 Linux kernels changed the behavior of sched_yield() in a way that causes the unfairness you observed. Other threaded applications are affected, including Open Office (!). My belief is that it's really a bug in 2.6 kernels and that the new behavior of sched_yield(), while technically conformant to the POSIX specs, lowers the quality of implementation quite a lot.

    (I seem to remember from my LinuxThreads development days that this isn't the first time the kernel developers broke sched_yield(), then realized their error.)

    The question I'm currently investigating is whether the call to sched_yield() can be omitted, as it's just a scheduling hint. Initial experiments suggested that this would hurt fairness (in Caml thread scheduling) quite a lot on all platforms other than Linux 2.6. More careful experiments that I'm currently conducting suggest that it might not be so bad. One can also play games where sched_yield() isn't called if there are no other Caml threads waiting for the global Caml mutex.

    So at least one class of user is forced to be aware of the scheduler, to refer to another poster's assertion that users shouldn't even need to know...

    • > So at least one class of user is forced to be aware of the scheduler, to refer to another poster's assertion that users shouldn't even need to know...

      For some info on sched_yield:

      Sched_yield is intended to allow a non-preemtive system to give other processes a go. You call it when you are using the cpu in a long running calculation. You *ought* to use it in every such case. A smart pre-emptive scheduler will ignore it, and a dumb non-pre-emptive one will round robin to another process.

      While it shoul
  • Does this mean there will be a realtime Linux that's not just a kernel running on top of a small proprietary realtime kernel like rtLinux currently is?

My sister opened a computer store in Hawaii. She sells C shells down by the seashore.

Working...