Deadline Scheduling Proposed For the Linux Kernel 113
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."
Re:What's the difference? (Score:5, Informative)
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.
Re:What's the difference? (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.
Re:first post (Score:4, Informative)
Re:Is this a unique scheduler? (Score:5, 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.
Re:We already have one. (Score:5, Informative)
Re:European Projects (Score:3, 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 [europa.eu] with more on the various projects and the proposals they put out.
Re:What's the difference? (Score:4, Informative)
That's probably why he's asking jackass.
Re:What's the difference? (Score:5, 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.
What to do get a try (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.