Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for December 5, 2013
Deadline scheduling: coming soon?
LWN.net Weekly Edition for November 27, 2013
ACPI for ARM?
LWN.net Weekly Edition for November 21, 2013
Deadline scheduling for Linux
Posted Oct 13, 2009 21:00 UTC (Tue) by nybble41 (subscriber, #55106)
Posted Oct 13, 2009 21:14 UTC (Tue) by dlang (✭ supporter ✭, #313)
Posted Oct 14, 2009 0:43 UTC (Wed) by njs (guest, #40338)
Posted Oct 14, 2009 14:08 UTC (Wed) by clugstj (subscriber, #4020)
But really, the burning question for me is this: What application is this type of scheduling (deadline scheduling) sufficient for? I just don't see one where this is actually more useful that the standard priority-based scheduler.
What it's good for
Posted Oct 14, 2009 14:12 UTC (Wed) by corbet (editor, #1)
Posted Oct 14, 2009 16:18 UTC (Wed) by clugstj (subscriber, #4020)
Posted Oct 14, 2009 16:47 UTC (Wed) by corbet (editor, #1)
A bit more information can be found in this posting on the Ericsson site.
Posted Oct 14, 2009 18:47 UTC (Wed) by clugstj (subscriber, #4020)
The author doesn't explain at all why he feels the deadline scheduler is a better fit - he just says that it is.
Posted Oct 14, 2009 17:43 UTC (Wed) by khim (subscriber, #9252)
In this application, I would just set the priority high for this
"audio application" and it would still work.
Small correction: s/would still work/will break easily/. If you
only have one application then you don't need any scheduler. But if
you have few applications they will step on each other toes. With deadline
scheduler if application got the promise - it'll be run and other
applications will behave (they'll be evicted in worst case).
It's not the job for kernel to provide full set of usefull functions to
program - it should provide minimal set needed to make implementation
possible. AFAICS normal scheduler does not offer enough, while deadline
scheduler does (even if I'm not 100% sure it does so with current API).
Posted Oct 14, 2009 18:39 UTC (Wed) by clugstj (subscriber, #4020)
So, you are just trading one failure mode for another (if the system is overloaded). Misbehaving applications cause failure in either case. Also, having the scheduler reject work that it can't finish in time is STILL breakage of the system.
If I have two tasks, one real-time, one not, I set the real-time task to a higher priority and it gets all the CPU it wants, when it wants it - no breakage is possible from lower-priority tasks.
Where is the "killer app" for the deadline scheduler? People have been looking for it for years and no one seems to have found it. Maybe it doesn't exist.
People were happy for years...
Posted Oct 14, 2009 20:43 UTC (Wed) by khim (subscriber, #9252)
Where is the "killer app" for the deadline
Where is the killer app for multitasking OS? People used DOS for ten
years and were happy. Why, they even had background printing and other
goodies - with resident programs. Then suddenly... OS/2, Windows, Linux,
etc. WTF all the hoopla is all about?
As long as your system has one and one realtime program only -
you don't need deadline scheduler. But if you have two... Think mobile
phone: you have two competing real-time tasks. One is game you are
playing right now and another is actual phone application which sends and
receives calls! I sure as hell want to have high response times from my
games (and I currently don't have that) but if someone calls me -
all bets are off. If game can survive - I'm happy, but if not - I don't
Sure you can do this with todays scheduler and some tricks... like you
can run print.exe for background printing in DOS. Both are poor, fragile
Posted Oct 14, 2009 21:13 UTC (Wed) by raistlin (guest, #37586)
First of all, I kind of agree with you that it is not easy to find an application, or even a set of applications, that do not work _at_all_ with the current combination of best-effort + fixed priority real-time scheduling.
In fact, this is right the scheme that is implemented in Linux as for now and --fortunately for all of us! :-D-- Linux already works very well in many contextes, and succesfully runs thousands of applications!
On the contrary, since no deadline scheduling is in place, not only in Linux, but nor it is in the vast majority of all existent (even real-time) operating systems, it is hard to find an example of an app which is happily scheduled by deadlines at this moment! :-P
This said, the point here is if there are some kind of workload that would be better represented by a runtime/deadline/period model than just by a priority value.
Since you're looking for examples (and, to me, you're right in doing that!) we can consider multimedia applications, that are intrinsically periodic (or sporadic) --e.g., 25 frames per second-- and that intrinsically have deadlines --e.g., presentation times for frames.
Thus, especially if, as many are saying, we have quite a lot of these applications, would life be easier if we let them specify their requirements a little bit more naturally than asking them (or the sysadmin) to tune/tweak their priority?
I think that this is not going to be necessarily true, but if we want to try it out, we need a deadline scheduler! :-D
Then, from a more ``academic'' point of view, which is better from fixed priority and deadline based scheduler is a long struggle, which, as years are passing, is turning into a legendary tale, an epic saga... :-O
Here, in real-time scheduling theory, we have, among the others, two major algorithms: Rate Monotonic, which is fixed priority (prio = 1/task_period), and EDF, which is dynamic.
Again, my personal opinions are:
- FP/RM is very simple to understand and to implement
- FP/RM yields slightly smaller implementation overhead
- FP/RM is very predictable and deterministic, a lot useful in hard
- EDF is more flexible and still predictable
- EDF allows better exploitation of system resources (CPU, both on UP and
- EDF has more graceful performance degradation in case of system
overload (kind of fairness, bounded tardiness, etc.)
- EDF, for the reasons above, is often considered to be better suited for
soft real-time workloads, especially on mixed rt non-rt systems.
And again, which is the best one? Well, I'm not going to answer! :-D
By the way, I hope I added some bits to the discussion, did I?
Posted Oct 22, 2009 8:17 UTC (Thu) by sethml (subscriber, #8471)
1) A buggy task which gets stuck in an infinite loop, rather than locking out all lower-priority
tasks and effectively locking out the system as it would with RT sceduling, would just use up
its allocated time. This could be a huge debugging aid and reliability improvement in such a
2) A high priority task can leave some CPU time to lower-priority tasks. For example,
suppose you have a high-priority computational thread which occasionally spends several
CPU-seconds at a time, and a low-priority communication thread. It would be good to limit
the computation thread to consuming no more than 90% of the CPU, so communication can
proceed. Of course, it would be even nicer if it got all 100% when the communication thread
didn't want any.
Posted Oct 23, 2009 5:06 UTC (Fri) by damentz (guest, #41789)
Audio, video, 3D accelerated applications (video games) - all these are noticeable if they starve briefly.
Although assigning real time priority to all the applications will work, you can cause a denial of service on your own system and root access is required to set real time priorities without prior configuration.
That's too much risk and work for me, the lowly user.
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds