Slashdot Mirror

← Back to Stories (view on slashdot.org)

Deadline Scheduling Proposed For the Linux Kernel

Posted by timothy on from the work-expands-to-fill-the-available-time-slices dept.

c1oud writes "At the last Real-Time Linux Workshop, held in September in Dresden, there was a lot of discussion about the possibility of enhancing real-time capabilities of Linux by adding a new scheduling class to the Linux kernel. According to most kernel developers, this new scheduling class should be based on the Earliest Deadline First (EDF) real-time algorithm. The first draft of the scheduling class was called 'SCHED_EDF,' and it was proposed and discussed on the Linux Kernel Mailing List (LKML) just before the workshop. Recently, a second version of the scheduling class (called 'SCHED_DEADLINE,' to meet the request of some kernel developers) was proposed. Moreover, the code has been moved to a public git repository on Gitorius. The implementation is part of a FP7 European project called ACTORS, and financially supported by the European commission. More details are available."

113 comments

  1. first post by fredan · · Score: 4, Funny

    because i'm using Earliest Deadline First scheduling!

    1. Re:first post by Anonymous Coward · · Score: 5, Funny

      I didn't get the first post because pulseaudio crashed my system, and my wifi wouldn't connect.
      Then I had to finish my windows 7 torrent, install it, and now I can post.

      Linux isn't ready for the first post.

    2. Re:first post by Anonymous Coward · · Score: 5, Funny

      Linux isn't ready for the first post.

      But Windows is ready for the last post.

    3. Re:first post by Smivs · · Score: 0, Offtopic

      Linux isn't ready for the first post.

      But Windows is ready for the last post.

      Never got mod points when you need 'em. Someone please mod this up as funny!

      --
      Smivs on the intertubes!
    4. Re:first post by tepples · · Score: 5, Funny

      I didn't get the first post because pulseaudio crashed my system

      It isn't PA that's crashing your system. It's the drivers, and PA just exposes defects that were already in the drivers.

    5. Re:first post by daem0n1x · · Score: 5, Funny

      IMHO, Windows is ready for the whipping post.

    6. Re:first post by Anonymous Coward · · Score: 0

      Yeah, and streaking is a great way to cool off - it just exposes penises that were already there.

    7. Re:first post by BrentH · · Score: 4, Funny

      Thanks PulseAudio, for exposing those damn drivers. I really hate it when audioservers simply work and just hide defects like this.

    8. Re:first post by raddan · · Score: 1, Funny

      And I suppose that PulseAudio is just exposing flaws in Linux, right? Lame.

    9. Re:first post by MadKeithV · · Score: 4, Informative

      Mod parent up as FUNNY..

    10. Re:first post by Anonymous Coward · · Score: 0

      Ah I get it. MP3 joke. Nice.

      Fun-Eeee

    11. Re:first post by Anonymous Coward · · Score: 0

      Yes, and pulseaudio devs will make no effort to fix those bugs, get them fixed, or get their software to play nice. It's their way or the highway, and this is why PulseAudio needs to be unceremoniously ripped from every distro. Not necessarilly because the software is THAT bad; especially in F12; it works pretty well. The attitude terrible
      https://bugzilla.redhat.com/show_bug.cgi?id=496714

    12. Re:first post by Anonymous Coward · · Score: 0

      This is gonna give me post traumatic stress disorder. Ug...

    13. Re:first post by tepples · · Score: 2, Insightful

      Thanks PulseAudio, for exposing those damn drivers. I really hate it when audioservers simply work and just hide defects like this.

      There comes a point beyond which a clusterfuck needs a clusterfix. Should Linus Torvalds just have kept on using Windows 3.1 and slogging through hiding its defects instead of building Linux? I don't think so. Likewise, programs that need real-time behavior can just hide the fact that existing Linux kernels have few provisions for real-time process scheduling by just hogging 100% CPU. But the right answer is to improve the scheduler's support for real-time semantics, as seen in the article.

    14. Re:first post by Anonymous Coward · · Score: 0

      Seems like good attitude to me.

    15. Re:first post by Per+Wigren · · Score: 1

      Yes, and pulseaudio devs will make no effort to fix those bugs, get them fixed, or get their software to play nice.

      Yes, this is why Lennart and the other PA devs are regularly contributing patches to ALSA and working with them to resolve bugs in drivers.

      I don't find any "terrible attitude" in that thread. They get a bug report, find that the kernel driver is failing and assign it to the kernel devs. The tone was very professional, no flamebaiting or otherwise bad attitude. Also, if you bothered to follow the links you'd see that the error was triggered with or without PulseAudio, meaning that it happens even without PulseAudio. The error is that VMWare's hardware emulation of the ens1371 sound card is incomplete.

      --
      My other account has a 3-digit UID.
    16. Re:first post by Air-conditioned+cowh · · Score: 1

      I didn't get the first post because pulseaudio crashed my system

      It isn't PA that's crashing your system. It's the drivers, and PA just exposes defects that were already in the drivers.

      It's no good he can't hear you. No Sound. His PA has just fallen out with his drivers. They felt "picked on".

    17. Re:first post by Thinboy00 · · Score: 1

      Combo breaker!

      --
      $ make available
    18. Re:first post by Anonymous Coward · · Score: 0

      wrong bug for the 'attitude'; that was one I opened after the fact. Because it was originally one virtualization product that I saw the problem in and therefore could NOT have been pulseaudio the bug was closed without any research.

      And in the first bug, as you point out, in one case it is vmware's hardware emulation; what about the individual with real hardware? Is that vmware's problem too?

      https://bugzilla.redhat.com/show_bug.cgi?id=494747

      no investigation, no request for more info; just closed, with a handy blame the other product response. just. awesome.

      Only after I tried vmware, kvm, virtualbox, and parallels, and saw similar nastiness in all was it even considered there might be something up; as far as I know sound in F11 still doesn't work with pulseaudio installed under any of these, though F12 is doing better...

      For the record, I also later experienced the problem on real Intel Audio hardware, though it has since been fixed.

      It might not be the WORST attitude, but it still sucks. Most devs actually care to investigate and respond with requests for info, and at least provide an explanation if they can't fix it. It can be understood.

      Anyway, if you can't tell I'm starting to rant, because I flat out hate PA; it's an elevator in my house; and worse it's now become a load bearing elevator; even gdm has a dependency on it in F12. Terrible idea.

      I won't win you over; you won't win me over. That's fine. But at least recognize the software is causing people endless frustration.

  2. Slashdot by dword · · Score: 1

    Misleading title, just 'cause they can.

  3. What's the difference? by guruevi · · Score: 2, Interesting

    I used to be into the Linux kernel a couple of years ago but since then I haven't really followed it anymore. What's the difference between these scheduling algorithms and do they work better than the current scheduling system?

    --
    Custom electronics and digital signage for your business: www.evcircuits.com
    1. Re:What's the difference? by Anonymous Coward · · Score: 0, Troll

      Spoken like someone who has never done any real-time programming.

    2. Re:What's the difference? by markkezner · · Score: 5, Informative

      Whether or not this scheduler is better depends on what you're trying to do.

      The proposed scheduler intends to work better for real-time apps, where the correctness of the algorithm depends on how timely the data gets processed. Low-latency audio is a good example of this, as a dropped or late packet of audio results in a nasty audible pop.

      --
      Dangerous, sexy, turing complete: Femme Bots
    3. Re:What's the difference? by Anonymous Coward · · Score: 5, Interesting

      These algorithms will produce substantially worse overall performance in all workloads. However, they allow absolute deadlines to be set for certain tasks. This is mostly useful for embedded devices -- if you're creating a medical device, or a subsystem for a plane, a 20% performance hit to guarantee you don't delay critical tasks for a couple seconds and get people killed isn't even a decision worth thinking about.

      This would make Linux a legitimate real time ("RT") kernel. There are RT Linuxes already, but they suck to work with -- I believe RTLinux (one of the RT variants), for example, requires all RT tasks to be in kernel-space.

      The upshot is that this is huge for Linux in certain business areas (and other RT OSes are currently quite pricey), but totally useless for your desktop or home server.

    4. Re:What's the difference? by conspirator57 · · Score: 2, Interesting

      yes it performs better. for certain workloads. with correct usage.

      like anything else it's a tradeoff. in this case you (or your application developer) have to be aware of how the scheduler works and be able to assign valid relative priorities and deadlines. Current schedulers you might have to worry about priority, but usually you don't. You also have to work out a way to work out utilization and negotiate fallback compute requirements based on the user's workload (other apps competing for the resource).

      Shortly, this scheduler is immediately useful for people making appliances (special purpose computers, e.g. a network firewall/router/voip box). It is less immediately useful for the desktop user, but i could imagine a set of circumstances that would make it very useful. The reason is that the appliance designer knows the compute workload fairly well and can take the time to assign priorities and deadlines for each process under each condition. When tools are made to automate this process on the fly, then desktop users will be able to open a bunch of crap and never have to worry that their voip app is going to stutter.

      --
      "If still these truths be held to be
      Self evident."
      -Edna St. Vincent Millay
    5. Re:What's the difference? by inode_buddha · · Score: 1

      It depends on the type of work load. Different schedulers are good for different tasks. Deadline scheduling is good for real time because it says "The job must be done by x time". In contrast, the Anticipatory scheduler tries to predict the next disk read, which may be good for streaming large files. The CFQ scheduler (the default) tries to balance everything out between extremes. There are a few other schedulers available as well. The scheduler can be selected on the kernel command line or from the bootloader. Google for it, there's plenty of info about it online.

      --
      C|N>K
    6. Re:What's the difference? by Lemming+Mark · · Score: 5, Informative

      I've not read TFA yet but will try not to spout rubbish ;-)

      Deadline-based scheduling is good for realtime processing and not necessarily better for your desktop or server. "Realtime" doesn't mean fast / high throughput and doesn't *necessarily* mean low latency. What it really means is "predictable", with low latency potentially being important. A server or desktop scheduling algorithm often does all kinds of crazy scaling of priorities according to process behaviour in the past, etc - it aims to keep processes running on the CPU as much as possible so that your overall performance is good. The desktop scheduler may also be tweaked to try and make sure interactive tasks respond quickly

      Typically a realtime scheduling algorithm is more "stupid" and therefore more predictable, so applications that need regular helpings of CPU can run without the behaviour of the scheduler disrupting their operation. Linux currently supports realtime scheduling through "round robin" and "first-in-first-out" classes, which are extremely "stupid" scheduling algorithms but useful in some cases. Realtime tasks run according to the chosen algorithm, then the normal desktop/server scheduler handles other tasks. It sounds to me like the proposal is to add a slightly more intelligent realtime scheduler allowing administrators and applications to control realtime behaviour differently when necessary. It doesn't sound like they're proposing replacing the main scheduling algorithm, although some OSes have played with using deadline-based scheduling exclusively.

      An EDF algorithm assigns each task a deadline and tries to always schedule the task whose deadline will expire soonest. Using a periodic deadline you can effectively specify stuff like "I need to be scheduled every 50ms, if at all possible" and the scheduler will try to make sure this happens. If you are, for instance, doing video streaming or interacting with a hardware buffer or controlling a robot arm you might have these requirements. In these cases, getting the CPU regularly is much more important than getting lots of CPU on average, which is why just renicing isn't sufficient.

    7. Re:What's the difference? by shish · · Score: 2, Interesting

      These algorithms will produce substantially worse overall performance in all workloads.

      Overall performance as in userspace apps will take 20% longer to perform CPU-bound tasks; or overall as in the scheduler will perform much worse ("the scheduler will now take 0.02% of CPU time, having previously taken 0.01%")? I think it's pretty important to specify over all of what...

      --
      I mod down anyone who says "I will be modded down for this", regardless of the rest of their comment
    8. Re:What's the difference? by MadKeithV · · Score: 1

      Real-time programming trying to add features to a live system while someone else is demoing the not-yet existing features to a customer.

    9. Re:What's the difference? by locallyunscene · · Score: 1

      Cool post. I don't know a lot about realtime scheduling, but a co-worker once described how a priority system works in this way(sorry it's a plane analogy rather than a car analogy):

      Priority isn't based on real life importance, but frequency and tolerance to gain "overall performance as you said". Say you have software to run a plane and the microwave needs to run 1ms every 10ms and the landing gear needs to run for 10ms every 30ms. Naively one might say the landing gear is of higher priority because it is more important than running the microwave. But this would cause missed deadlines for the microwave and for anything running at a lower priority than the microwave when both can run without missing their deadlines. The landing gear would be predictably interrupted an upper bound of 3 times to complete after 13ms which is well before the next time of 30 ms while not causing any problems.

      He had a cool job, but I did not envy his position when he had to explain to management why our project's equivalent of landing gear had to be lower priority than our microwave in order for real-time scheduling to run correctly.

    10. Re:What's the difference? by Sir_Lewk · · Score: 3, Informative

      That's probably why he's asking jackass.

      --
      "linux is just DOS with a UNIX like syntax" -- Galactic Dominator (944134)
    11. Re:What's the difference? by Mr+Z · · Score: 4, Informative

      20% overall hit on system performance, as in the peak throughput of your system may take a 20% or greater hit due to scheduler decisions that guarantee deadlines get met, even if that means not allowing work to proceed on tasks that are ready to run.

      For example, task A may be ready to run, but if the scheduler picks it, then task B might miss its deadline because A's time quanta is too long. This can be true even if B isn't yet ready to run, but is about to be. Ready-to-run task A may take 40ms with a deadline way in the future. Task B might be ready to run in 20ms, and when it does run, it'll run for 70ms. Now suppose B's deadline is 100ms away. If task A can't be preempted, we can't run task A, because then we'd start task B too late. A real-time scheduling algorithm might therefore choose to idle 20ms until B is ready if it's not possible to preempt task A.

      (Note to pedants out there: What I just described is not EDF, but a more generic off-the-top-of-my-head example of how realtime scheduling decisions, perhaps even just made by a human making a static schedule, can lead to idle time.)

      These sorts of statements tend to apply though when all tasks use a real-time scheduling algorithm, or only to the subset of tasks that are classified "real-time". Linux's scheduling algorithm will remain hybrid, with some real time tasks and the rest using the CFS scheduler (SCHED_OTHER).

      As a result, it seems highly unlikely to me that SCHED_EDF (or SCHED_DEADLINE or however it gets spelled) will make Linux a true hard real-time OS. It will just add a new, more traditional real time scheduler to the existing set of soft-real time schedulers (SCHED_RR, SCHED_FIFO). A system with predominately real-time tasks will probably meet all of its real time guarantees with high probability. I wouldn't run my medical equipment with it just yet though, particularly if any of the SCHED_OTHER tasks are doing disk I/O and/or thrashing the VM.

      Re: your sig... (0x2B | ~0x2B) = ~0, regardless of your bit length.

      --
      Program Intellivision!
    12. Re:What's the difference? by weicco · · Score: 1

      I don't know much about real-time systems but what I've understood is that some embedded real-time kernels (I think QNX is one) even tells in their programmer's manuals that "function X takes Y clock cycles to execute" so you can take this into account when designing your code.

      --
      You don't know what you don't know.
    13. Re:What's the difference? by Permutation+Citizen · · Score: 1

      In addition to this post, with EDF algorithm if you meet some given conditions, you have the guaranty that your deadlines will be met.

    14. Re:What's the difference? by Anonymous Coward · · Score: 0

      Are you sure it would be totally useless for the desktop? Isn't real-time scheduling useful for music work? (in order to gain low latency)

    15. Re:What's the difference? by mewsenews · · Score: 3, Funny

      Re: your sig... (0x2B | ~0x2B) = ~0, regardless of your bit length.

      Oh shit! Processor nerd SMACKDOWN!! This is better than wrestling!

    16. Re:What's the difference? by MBGMorden · · Score: 1

      This begs the question though: why is this specific-purpose scheduler being looked at while specific-purpose schedulers focusing on desktop use (as opposed to server use, which is what Linux scheduling is currently optimized for) have been disregarded.

      --
      "People who think they know everything are very annoying to those of us who do."-Mark Twain
    17. Re:What's the difference? by QuoteMstr · · Score: 1

      You complete misunderstand. This addition is something completely different from some hare-brained hacked-up "desktop" scheduler. Deadline scheduling a new kind of scheduling which the current scheduler implementation is being extended to support. It's the difference between a new image format and a new image viewer.

    18. Re:What's the difference? by Lisandro · · Score: 2, Interesting

      The upshot is that this is huge for Linux in certain business areas (and other RT OSes are currently quite pricey), but totally useless for your desktop or home server.

      I don't think so. If this means we'll get a pluggable scheduler architecture in Linux, i'm all for it.

      I thought it was all hogwash until i tried Ken Colivas' BFS patch. The difference it makes on a desktop system is notable, and it clearly demonstrates that having a single scheduling solution for a kernel oriented for everything from embedded systems to desktops to 4096-CPUs servers is insane.

    19. Re:What's the difference? by sjames · · Score: 2, Insightful

      Hard realtime is ...HARD.

      To get it right, not only do processes have to be scheduled correctly, so does I/O. Swapping/paging are out of the question. Even with all that, the hardware has to be appropriate as well. SMM and SMI as found in the x86 world these days is simply unacceptable, you can't be hard real time when there is an interrupt you can't mask or whose interrupt handler is not accessible to the OS. Especially when it switches the CPU to a different mode and stays there until it says it's done.

      You also can't have I/O devices that don't make guarantees about the maximum time an operation can take, no matter how often it does it in the "usual" time. This can be a problem for drives that may retry a read or write an arbitrary number of times and might or might not reallocate a sector at the other end of the platter unless it's all fully documented and the application in question doesn't have any deadlines too short to allow for that.

      How far away from all of that a particular device can stray (for the sake of cost mostly) will depend on how demanding the real time is and how much it matters if it misses a deadline. From there there are a zillion arguments if it's hard real time, soft real time, sorta squishy real time, not real time at all, or cheap consumer crap.

      Technically if some event has to be polled and responded to within a month or it'll cost a million dollars, it's hard real time even though an old desktop machine (or a bored night operator) can handle it.

    20. Re:What's the difference? by BikeHelmet · · Score: 1

      The desktop scheduler may also be tweaked to try and make sure interactive tasks respond quickly

      BFS! ;)

    21. Re:What's the difference? by Anonymous Coward · · Score: 0

      If this means we'll get a pluggable scheduler architecture in Linux, i'm all for it.

      It doesn't. It's not a new scheduler, it's a new scheduling class within the existing scheduler.

  4. Is this a unique scheduler? by jhfry · · Score: 2, Interesting

    Has a deadline based scheduler been done before? It seems like an excellent idea for time sensitive (real time) processing. I have worked with RT os's before, iRMX mostly, and always wondered how the scheduling worked.

    --
    Sometimes the best solution is to stop wasting time looking for an easy solution.
    1. Re:Is this a unique scheduler? by inode_buddha · · Score: 1

      Yes, it has been done. This seems to be a new implementation, perhaps with different characteristics and features.

      --
      C|N>K
    2. Re:Is this a unique scheduler? by Lemming+Mark · · Score: 4, Interesting

      Deadline scheduling is well established and has been done many times, in many flavours on other OSes. It's probably even been done on Linux before. But if this one gets upstream with the blessing of the kernel community, it would enhance Linux for everyone rather than just those running particular kernel patches.

      Linux seems to be having a lot of realtime-related work (see PREEMPT-RT, a somewhat separate but related area of work) done, which is interesting - I would have said that the conventional wisdom was that large, general-purpose OSes cannot be realtime-ified. It seems like certain parties are determined to prove this wrong - and it's looking to me somewhat like getting to "good enough" realtime behaviour will make large segments of users happy even though it's perhaps unlikely to ever replace ground-up realtime OS designs.

    3. Re:Is this a unique scheduler? by buchner.johannes · · Score: 1

      The Linux Kernel has 3 schedulers in the mainline:
      - Anticipatory http://www.kernel.org/doc/Documentation/block/as-iosched.txt
      - Deadline http://www.kernel.org/doc/Documentation/block/deadline-iosched.txt
      - CFQ http://kerneltrap.org/node/8082

      --
      NB: The message above might reflect my opinion right now, but not necessarily tomorrow or next year.
    4. Re:Is this a unique scheduler? by Lemming+Mark · · Score: 4, Informative

      True - those are IO schedulers, though, whereas the scheduler described in the article is a CPU scheduler. Not that IIRC the summary or myself went so far as to point that out explicitly, which was a mistake!

      For CPU scheduling Linux has a general purpose scheduler (which is CFS, in recent Linux releases) and two realtime scheduling classes (round robin and FIFO), if memory serves.

    5. Re:Is this a unique scheduler? by Mr+Z · · Score: 1

      If they can tie UI elements to a deadline such as "before the next screen refresh" to keep the UI snappy at (nearly) all times, I don't mind losing some background throughput.

      --
      Program Intellivision!
    6. Re:Is this a unique scheduler? by bill_mcgonigle · · Score: 1

      Has a deadline based scheduler been done before? It seems like an excellent idea for time sensitive (real time) processing. I have worked with RT os's before, iRMX mostly, and always wondered how the scheduling worked.

      The approach in Linux has been to launch a thin RT kernel, and then have it scedule linux. Or, at least that was the approach a big RT vendor has been selling. It seemed to work nicely from the demos I've seen, and had nice instrumentation, since people who care about RT need to measure it. Like Xen will eventually give way to KVM (or something like it), Linux will eventually be good at RT.

      --
      My God, it's Full of Source!
      OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
    7. Re:Is this a unique scheduler? by pablomme · · Score: 1

      From running `chrt` on 2.6.31:

      Scheduling policies:
          -b | --batch set policy to SCHED_BATCH
          -f | --fifo set policy to SCHED_FIFO
          -i | --idle set policy to SCHED_IDLE
          -o | --other set policy to SCHED_OTHER
          -r | --rr set policy to SCHED_RR (default)

      SCHED_OTHER, _RR and _FIFO are the ones you were referring to. But I don't know if _IDLE and _BATCH are separate scheduling algorithms or they are one of the others with different parameters...

      --
      The state you are in while your HEAD is detached... - wait, what?
  5. European Projects by Lemming+Mark · · Score: 3, Interesting

    The EU-funded projects are somewhat interesting in my experience. They tend to fund both academics and researchers from industry to do stuff and the projects tend to be more focused on practical results than a normal project funded by a research council. They can still generate research papers, etc, but there's more of an emphasis on producing new code that can actually be *used* to do stuff that wasn't available before. Whereas more academic research normally focuses on getting the code sufficiently robust that papers can be published about it, then it's often forgotten.

    I think the more practically focused work of this kind is valuable and would like to see more. It is less "valuable", academically and as such I suspect academics are less inclined to attribute prestige to those who have worked on it. It would be nice to see a bit more glory given to folks who work on these projects (disclaimer, I have done a *very* small amount of work on one myself) as a valid direction vs industry or academia. Also, this mode of development does remind me a little of some of RMS's writings about how Free Software development could be funded - here we have effectively a government body giving money to worthy causes, as represented by a team of interested experts, to enhance open source software for everyone involved in reasonably directed ways. Ideally it'd be nice to see "get stuff upstream" be a completion goal for these projects, I'm not sure to what extent that is already true.

    1. Re:European Projects by IBBoard · · Score: 2, Informative

      I don't think all of the EU FP7 stuff is "end-usable releases" - I'm working on a project that works with end-users but isn't planning (AFAIK) to be usable as-is at the end of it. At least I hope it isn't - we've got lots of fixing to do if it is :D

      If anyone cares, there's actually a public EU FP7 site with more on the various projects and the proposals they put out.

    2. Re:European Projects by Lemming+Mark · · Score: 1

      True, at least some of the stuff I've seen worked on isn't end-user ready yet (although if they had a "get it upstream" clause that would help ensure that it gets to users eventually). But typically EU projects seem to have a greater focus on creating stuff that's useful in the real world vs useful for publishing academic papers. They seem to have more freedom / inclination to build something that might be useful but isn't academically trendy. So it's more likely to improve the state of software in a direct fashion rather than by increasing the body of published papers. As you say, it's still a bit hit-and-miss whether something long-lasting comes out of it although one can hope that the companies and universities involved take the code somewhere. At least it gets written and published open source, though!

    3. Re:European Projects by Anonymous Coward · · Score: 0

      In which EU do you live in??? Valuable? Practical results?? C'mon...

    4. Re:European Projects by mvdwege · · Score: 1

      Erm, I think it is actually the other way around. Look at secure authentication over a network: which project was purely academic, and which project was a typical EU endeavour? And which project is currently in active practical use?

      Mart

      --
      "I know I will be modded down for this": where's the option '-1, Asking for it'?
  6. What I'm not clear about by Chrisq · · Score: 2, Interesting

    Is this suitable as a general purpose scheduler or is it just for real-time systems?

    1. Re:What I'm not clear about by AlastairLynn · · Score: 1

      Just real-time systems - ones where you have set deadlines :)

    2. Re:What I'm not clear about by Nadaka · · Score: 4, Interesting

      I think the question he is posing is:

      Is this type of scheduler perfect? Capable of real time, batch jobs and the mixed fruit bowl of jobs on a typical desktop or server?

      The answer is, probably not. There really is no such thing as a perfect scheduler. Different kinds of workloads have different requirements.

      A busy real time scheduler will tend to starve low priority jobs. This can become an issue if those low priority jobs manage to grab limited resources they are never given the time to use. As those resources dwindle, real time jobs will be harder to satisfy and the low priority jobs must be terminated or given time to release those resources. I can't really say for certain, but it looks like EDF would have these same kinds of issues.

      Interesting story a professor of mine told: An old university mainframe was brought offline after decades of operation. A core dump was performed and investigation revealed that there was a process that had been waiting to run for close to 30 years. Somehow, its priority was set to be lower than the idle process and this particular machine did not have automatic escalation of priority in its scheduler.

    3. Re:What I'm not clear about by natehoy · · Score: 4, Insightful

      Interesting story a professor of mine told: An old university mainframe was brought offline after decades of operation. A core dump was performed and investigation revealed that there was a process that had been waiting to run for close to 30 years. Somehow, its priority was set to be lower than the idle process and this particular machine did not have automatic escalation of priority in its scheduler.

      Actually, I think EDF would fix that, at least to an extent.

      Currently, prioritization is done based on, well priority. So if you took a job and set its priority to lower-than-idle, as you stated above, it will obviously never run.

      However, with EDF,you assign (if I understand it correctly) a deadline to each task rather than a priority. "Task X really should get done in the next 50 msec, but Task Y can wait up to 12 hours and no one's going to scream". On a normal peak-and-valley loaded machine, it'll work on the first deadline first, and if things queue up the low-"priority" ones will simply have longer deadlines. Ideally, the system has enough capacity to accommodate the longer deadline stuff "early" when it has time.

      However, on a heavily-peaked system, eventually those long-deadline jobs are going to get priority simply because their deadlines have been reached. So if you have a 50ms deadline job running every 20ms and those jobs start queuing up, then you submit a 12hour deadline job, in 12 hours that job will get the full attention of the system until it's done, because it has the earliest deadline.

      As with all things, this has its advantages and disadvantages. If that job that runs every 20ms is truly critical, then you're not going to like this scheme - eventually the low-"priority" stuff is going to come due and take precedent over your "critical" stuff because it's all based on what you asked for first, not how important each task was. On the other hand, this does prevent the very problem you describe - jobs running at such a low priority that they never get any lovin' at all.

      --
      "This post contains words, known to the State of California to cause thought. Wash brain thoroughly after reading."
    4. Re:What I'm not clear about by DragonWriter · · Score: 1

      Is this suitable as a general purpose scheduler or is it just for real-time systems?

      Its not a scheduler, its a scheduling class for the existing Linux scheduler. A scheduler can support several different scheduling classes for processes. The current Linux scheduler supports two (Round Robin and FIFO) designed for real-time processes as well as the base one for regular processes, as I understand it.

    5. Re:What I'm not clear about by randomsearch · · Score: 1

      EDF schedulers are usually employed in real-time systems, and those are predominantly embedded systems. They are simple to understand and analyse, such that engineers can have high confidence that all hard real-time tasks will meet their deadlines.

      Generally speaking, it is not useful for much else - you wouldn't want it in a desktop PC, for example. This is because the priority of a task is determined by its deadline in EDF and not other important factors such as the actions of a user. We like responsiveness in our desktops, and EDF is not sophisticated enough to provide it.

      http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling

      RS

    6. Re:What I'm not clear about by CODiNE · · Score: 2, Funny

      Somewhere there's a 57 year old grad student waiting for his job to finish running.

      And then the server shut down.

      Ouch.

      --
      Cwm, fjord-bank glyphs vext quiz
    7. Re:What I'm not clear about by Nadaka · · Score: 1

      You are right, EDF would prevent the issue of tasks never getting CPU time. However if your interpretation is correct, it also means that the urgent tasks may not be handled in real time if that 12 hour task reaches 12 hours and still needs significant CPU time. This violates the goal of real time performance if it were to happen. But then again any real time system will eventually fail if put under a sufficiently high load.

    8. Re:What I'm not clear about by Nadaka · · Score: 1

      Sounds like as good a time as any to either pick a different thesis project or settle for a liberal arts degree. :)

    9. Re:What I'm not clear about by Chrisq · · Score: 1

      Somewhere there's a 57 year old grad student waiting for his job to finish running.

      And then the server shut down.

      Ouch.

      He's probably in the bar and not going to budge until it finishes.

  7. Re:being back at 0 is now called delaying retireme by jdunn14 · · Score: 1

    At some point the anti-government rant is too vague to be effective.

  8. Linus won't allow that by Anonymous Coward · · Score: 3, Funny

    Remember Con Kolivas.

    1. Re:Linus won't allow that by RiotingPacifist · · Score: 3, Interesting

      For those that didn't catch it CK is back with the Brain Fuck scheduler, which improves desktop interaction, by ignoring the past. I CBA to recompile but the patches are here and while the chances of it getting into mainline are "LOL", it is being adopted by android.

      --
      IranAir Flight 655 never forget!
    2. Re:Linus won't allow that by whatajoke · · Score: 1

      It is alright Ingo; you dont need to snicker anonymously.

    3. Re:Linus won't allow that by molnarcs · · Score: 4, Funny

      I really like the design of his website. Even IE renders it correctly... That's what I call a clean design, UI experts and gnome devs take note!!

    4. Re:Linus won't allow that by koiransuklaa · · Score: 2, Interesting

      Got a reference for "being adopted by android"? Just an experimental git tree on android.git.kernel.org doesn't prove much...

    5. Re:Linus won't allow that by QuoteMstr · · Score: 1

      Actually, BFS performance is shitty. No, really shitty.

    6. Re:Linus won't allow that by dotgain · · Score: 1

      Actually, BFS performance is shitty. No, really shitty.

      Damn. And here was me thinking that a name like "Brain Fuck Scheduler" would get some attention and give Linux just the push it needs to succeed on the desktop.

    7. Re:Linus won't allow that by BikeHelmet · · Score: 2, Interesting

      You can take your superior benchmarks and shove it. On older hardware, the difference in responsiveness with BFS is absolutely astounding.

      Those tests are multi-processor multi-core runs, which is not what BFS was designed for. I would ask you to bench it on a single single-core, dual-core, tri-core, and quad-core CPU before making such statements.

      In my own tests on a shitty VIA C7 with a horribly slow(10MB/sec) Quantum EIDE(I think) drive, BFS dropped the times to launch programs almost in half. I'd place a bet that CFQ is doing some stupid shit optimized for high performance servers.

      And at least a few real-world tests heavily favour BFS. But I personally despise meaningless numerical benchmarks. I much prefer watching desktop responsiveness soar on old hardware.

    8. Re:Linus won't allow that by Slashcrap · · Score: 1

      You can take your superior benchmarks and shove it. On older hardware, the difference in responsiveness with BFS is absolutely astounding.

      And yet nobody can demonstrate it. Lots of people can feel the difference, but they tend to be the kind of people that post in forums about how the kernel developers are saboteurs for not making Reiser4 the default Linux filesystem.

      In other words, fourteen year old faggots with aspergers who should stay the fuck away from Linux and any other OS that isn't Windows.

    9. Re:Linus won't allow that by BikeHelmet · · Score: 1

      I never said anything about the kernel developers - I merely attacked the benchmarks being used.

      That's something I do for every OS. Most benchmarks aren't relevant.

    10. Re:Linus won't allow that by Anonymous Coward · · Score: 0

      Ingo seems to be biased against Con's work for some reason.

      If you want to benchmark a scheduler designed to increase responsiveness on old slow systems, what would be a sensible test rig. You might reasonably say a single (or just maybe dual) core Atom machine. Though perhaps not a dual quad-core processor machine with hyperthreading. Guess which of these Ingo choose to test on?

      Now give me good benchmarks run on a single or dual core machine if you want to make a valid argument against BFS.

  9. How does this compare by Anonymous Coward · · Score: 0

    to *BSD's "dead scheduling"?

    1. Re:How does this compare by SlothDead · · Score: 0, Redundant

      Please don't split your sentences, putting one half in the subject, the other half in the comment. Not everyone reads the subjects, since they are often useless, and reading just "to *BSD's "dead scheduling"?" sounds like a toast!

  10. Re:being back at 0 is now called delaying retireme by conspirator57 · · Score: 1

    just let them fade gently into that goodnight.

    --
    "If still these truths be held to be
    Self evident."
    -Edna St. Vincent Millay
  11. RTAI? by sam0737 · · Score: 1

    Is this thing going to replace https://www.rtai.org/ completely?

    More importantly, can http://linuxcnc.org/ a CNC software, benefit from this extension?

    1. Re:RTAI? by phantomcircuit · · Score: 1

      Why would a real time scheduler improve CNC software?

    2. Re:RTAI? by sam0737 · · Score: 1

      Currently that CNC software runs with the RTAI patch.

      The part that requires realtime are bitbanging the motor controller through parallel port, or act as a DIP Controller (http://en.wikipedia.org/wiki/PID_controller) to calculate the output of a more advance motor. All these need to be coordinated precisely at deterministic time, considering that it's controlling 3+ axis motor and a spindle.

      if it miss a 100us schedule, it would definitely affect the final product output.

      Of course, one could off-load all these realtime work to yet another embedded system, written with Realtime OS (or even without OS), then the Linux box can communicate with the box with whatsoever protocol, say USB. But this requires one more hardware, yet the capability of the hardware will be limited.

      If mainstream kernel does support realtime like RTAI extension, the project can use the mainstream distro and hopefully could make life easier.

  12. LoL by ae1294 · · Score: 1

    I don't know what all the fuss is about. I just use CRON....

    Thank you, I won't be here all week...

    1. Re:LoL by RiotingPacifist · · Score: 1

      Thank you, I won't be here all week...

      What's your schedule then...?

      --
      IranAir Flight 655 never forget!
    2. Re:LoL by ae1294 · · Score: 1

      What's your schedule then...?

      I'm honestly not really sure. I use CRON jobs to let me know stuff like that but there is a problem. I run Windows...

  13. We already have one. by Shadow-isoHunt · · Score: 0
    There's already a Deadline scheduler in the kernel, which works great under database loads. It can be selected with:

    CONFIG_IOSCHED_DEADLINE=y
    CONFIG_DEFAULT_DEADLINE=y

    --
    www.isoHunt.com
    1. Re:We already have one. by Pravetz-82 · · Score: 5, Informative

      These options are for the IO scheduler called "Deadline". TFA is about CPU scheduler.

    2. Re:We already have one. by Anonymous Coward · · Score: 0

      Erm, that's an I/O scheduler. TFA is about a CPU scheduler. Who modded this informative?

    3. Re:We already have one. by Lemming+Mark · · Score: 1

      True. But that's an IO scheduler, whereas the code mentioned in the article is a realtime CPU scheduling class. Probably would have been good if the article summary had mentioned this explicitly!

  14. This is great! by Zebedeu · · Score: 1

    I can't wait for my Linux installation to become at least 80% more efficient with this scheduler.

    I know that I become more efficient by at least that amount when a deadline approaches!

    1. Re:This is great! by coolsnowmen · · Score: 1

      I know you're joking, but a deadline scheduler doesn't make the kernel more efficient, it just makes it more predictable. Usually, Real-Time Scheduling causes a drop in efficiency.

  15. You won't ever beat the OpenBSD team. by Anonymous Coward · · Score: 0

    Give it up.

  16. You are missing Meatloaf's by Anonymous Coward · · Score: 0

    Meatloaf's new scheduler is not on your list, but then again it isn't in mainline yet.

  17. I don't by Anonymous Coward · · Score: 0

    have a problem with it.

  18. It can only do a subset of real-time by ClosedSource · · Score: 1

    The problem is that real-time issues aren't necessarily limited to a "get there before it's too late" scenario. In many real-time scenarios you have to comply with a timing "window" where being early is just as bad as being late. Imagine how bad music would sound if the time between notes were merely guaranteed to not exceed a certain maximum.

    In any case, PC's are a bad platform for software-based real-time unless you can turn off things like caches that introduce unpredictable delays.

    1. Re:It can only do a subset of real-time by Anonymous Coward · · Score: 0

      Which is why PCs are used for soft-real-time stuff like being the pretty front end to the embedded processors (even if they're on a PCI card in the PC) that do the hard-real-time stuff. Oh, yeah, some of those embedded processors use the Linux kernel.

    2. Re:It can only do a subset of real-time by QuoteMstr · · Score: 1

      In many real-time scenarios you have to comply with a timing "window" where being early is just as bad as being late.

      But just like in real life, if you arrive early, you can wait. If you arrive late, you can't make up the time. If precise timing is required, a program might set its deadline a little early, then busy-wait on a high-precision clock for the exact moment it needs to act.

    3. Re:It can only do a subset of real-time by ClosedSource · · Score: 1

      That's a valid approach as long as the timing intervals aren't too close together and the OS doesn't interrupt the process at the wrong time.

      For example your approach was used in Atari 2600 games to get the timing of the vertical blanking right. Of course on the 2600 there were no interrupts (and no OS) so you just had to make sure all code paths in your display routine didn't exceed the vertical blanking time and then sit in a tight loop reading the timer until it reaches 0.

      If you've ever seen the screen jump in the middle of an Atari 2600 game, it's because you triggered a code path that took too much time and messed up vertical blanking.

      On the other hand, this approach wouldn't work while you were writing to the screen because you didn't have any time to waste (unless you had a very simple display).

    4. Re:It can only do a subset of real-time by ClosedSource · · Score: 1

      Well, assuming the embedded processors have deterministic timing and the Linux kernel is also deterministic with respect to timing, it should be OK. On the other hand, if somebody uses dedicated hardware for a real-time function, it probably does at least some of the real-time in hardware rather than software.

      The best real-time OS's are usually designed from the ground up to be real-time. Adding real-time functionality to an existing kernel is sub-optimal.

  19. Last Windows equivalent was V3.11 by DanielSmedegaardBuus · · Score: 1

    This is exactly right.

    I used to work at a video duplicating plant where we controlled our source machines (Beta, DigiBeta, C1s, D2s, etc.) via a central computer. We had about 20 source machines providing movies, commercials, logos, and trailers to over 4000 VHS recorders divided into 14 racks.

    Until we got the centralized computer management thingie, we used manual switchboards and our skills to start, synchronize, and switch between, different source machines providing logos, trailers, commercials, and features, making sure each "item" was properly synchronized after each other.

    This was not so difficult with just trailers before a film, but if you had two source reels that needed to be switched in the middle of a movie, you had to make damn sure you didn't switch sources more than a couple of frames out of sync, or you'd get a really bad copy. It was a fun little game, but the computerized system, of course, made the whole thing much easier and much more accurate.

    But of course, this accuracy depended on the accuracy of the OS the system ran on. A running video player controlled via RF over BNC cables doesn't provide interrupts, the entire thing had to be timed to the frame from within the application itself. And not for one source and one target, but for M sources and M targets. So you needed an OS which absolutely guaranteed a time slice from the kernel at an absolutely non-negotiable point in time.

    That, at the time, would be Windows 3.11 :) And the time (when I left) was 1998. We were wondering at the time why the hell they'd use Windows 3.11 for that task, but I'm pretty sure they're still using that old thing, at least I don't see any reason why they wouldn't ;)

  20. Pre-emptive Multitasking by 7bit · · Score: 1

    How does this scheduling compare to how "Pre-emptive Multitasking" was performed on something like the AmigaOS? Does it allow for the same benefits as have been described for it? And if so, would there be any inevitable downsides to it for how Linux operates and why?

    My Linux knowledge is not yet very deep but I have occasionally read mention here and there of it's multitasking methodology being different from that of many other OS's and that it is part of what keeps it from becoming a desktop entertainment type of PC OS. Is this true? And is the difference really very great anymore? If the scheduling talked about in TFA is too heavy handed, are there any other ways to improve the Linux "Pre-emptive Multitasking" behavior that wouldn't be problematic?

    Or could a scheduling feature like this be made into something that you could turn On/Off at will without having to recompile etc every single time you need it's benefits?

  21. What to do get a try by Fri13 · · Score: 2, Informative

    I did swith from CFS to Deadline about week ago. I didn't even know this is now suggested. I just wanted to try does it help situation at all. Somehow I have feeled that CFQ has slowed my system.

    You can swtich the scheduler in running system, no need to even logout or restart. This is one reason why I love Linux OS (monolithic kernel = OS).

    became a root (or use sudo if it is a must).

    First to check out what scheduler you are currently using and what are available on your Linux OS:

    cat /sys/block/sda/queue/scheduler

    then switch to deadline by simply giving command:

    echo deadline > /sys/block/sda/queue/scheduler

    The Linux OS will first execute all currently running jobs with old scheduler what it was doing and then switch to new scheduler. On my system, it was right away because I was not running any heavy tasks.

    check again has the switch be done.

    cat /sys/block/sda/queue/scheduler

    And you should see [deadline] and not [cfq]

    That's it. Simply as that. But when you reboot the Linux OS, you need to do that again or then you can pass that to GRUB to order Linux OS to start with that scheduler.

    By adding in menu.lts option, to same line what starts by "kernel". To the end of that line just place this:

    elevator=deadline So it is the last on that line. Then it will be the used scheduler of Linux OS for all process just from begin of system boot.

    On my system, the speedup is good when running few applicatios only. But when multitasking few I/O apps, I got feeling it is slower. Like running a database sync, watching video and updating system packages made few hickups. Thats why I am littlebit curious this change by default. And I would like to test the BFS.

    and CFQ is better on multiuser environments than deadline.

    But this is the current one and mayby the newer should be tested first.

    1. Re:What to do get a try by Slashcrap · · Score: 1

      I did swith from CFS to Deadline about week ago.

      You could have saved yourself a really long, boring post if you'd just read enough to realise that this story is about something completely fucking different.

      I/O schedulers are not the same as process schedulers. Thanks for the tedious fucking anecdote though.

      And I would like to test the BFS.

      Yeah, I'd say you're probably in the target audience.

    2. Re:What to do get a try by Anonymous Coward · · Score: 0

      !informative, nobody's talking about the IO scheduler here...

    3. Re:What to do get a try by zigurat667 · · Score: 0

      What you're using is the deadline IO-Scheduler, not the CPU Scheduler mentioned in TFA.

  22. Yay! by HungWeiLo · · Score: 1

    I welcome anything that spices up competition between vxWorks, LynxOS, Green Hills, etc.

    --
    There are a huge number of yeast infections in this county. Probably because we're downriver from the bread factory.
  23. About time by thethibs · · Score: 1

    1970 just left a message. It says, "You're Welcome."

    --
    I'm a Programmer. That's one level above Software Engineer and one level below Engineer.
  24. Oh it's the daily KOS huh? by 7-Vodka · · Score: 1

    I love the daily KOS. The question is why does the CIA need a leftist blog?.
    Oh well

    --

    Liberty.

  25. Minix or MSWin? (Re:first post) by sowth · · Score: 1

    I thought Linus Torvalds was using Minix when he wrote Linux.

  26. Is this really good as the rt patch for desktops? by Anonymous Coward · · Score: 0

    I run a genuine realtime kernel here (2.6.29-rt23), and I can tell you it kicks ass.

    Prior to using a realtime kernel, some low priority background tasks like Tor often got little CPU time on my quad-core machine - even when the machine was idle. Worse, high priority tasks (eg. games) would often stop for such nonsense as their own disk activity. Furthermore, the active process count alone adversely affected performance - setting 50% of my processes to idle priority trippled performance of tasks given priorities as high as -19.

    After getting a realtime kernel, even idle tasks could soak up any leftover CPU cycles. Tor reliability went from one page in fifteen successfully downloading to 9 out of 10 with sufficient latency and bandwidth to handle YouTube and other video sites. Games now perform smoothly even while doing full blown disk backups.

    The effect generally seems to be that non-realtime systems spend too much time going through the process list to achieve low latencies. Now I have serious doubts that any hybrid scheduler that doesn't enforce realtime preemption on lower priority tasks - not to mention the kernel itself - is going to compare with my system.

    Getting the realtime patches to mainline status would probably be better for everyone than semi-adequate jobs that can only reduce interest in true hard realtime systems.