Deadline scheduling for Linux [LWN.net]

Deadline scheduling for Linux

Posted Oct 13, 2009 20:55 UTC (Tue) by dlang (guest, #313)
In reply to: Deadline scheduling for Linux by clugstj
Parent article: Deadline scheduling for Linux

why would you submit a job if it doesn't yet have the data it needs available?

to post comments

Deadline scheduling for Linux

Posted Oct 13, 2009 21:00 UTC (Tue) by nybble41 (subscriber, #55106) [Link] (1 responses)

Presumably so that the OS knows to reserve room in the schedule ahead of time for when the data will be available...?

Deadline scheduling for Linux

Posted Oct 13, 2009 21:14 UTC (Tue) by dlang (guest, #313) [Link]

but without any indication of how much time the process will take to complete, the only thing the OS could do is prohibit anything else from using the CPU between the start time and the deadline, which is almost certainly _not_ the correct thing to do.

Deadline scheduling for Linux

Posted Oct 14, 2009 0:43 UTC (Wed) by njs (subscriber, #40338) [Link]

Yes, I'd also like to understand what the difference is between the interface clugstj suggests and the existing clock_nanosleep(CLOCK_MONOTONIC, TIMER_ABSTIME, ...) interface.

Deadline scheduling for Linux

Posted Oct 14, 2009 14:08 UTC (Wed) by clugstj (subscriber, #4020) [Link] (10 responses)

Because I know exactly when it WILL be available. If I have to tell the scheduler each and every time when I want a piece of code (that runs periodically) to run, it is not really doing me much good. I might as well just use the standard realtime priority-based scheduler and set the priority appropriately.

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) [Link] (9 responses)

Any sort of periodic data-processing application can benefit from this sort of scheduling regime. Imagine an audio application which must get data into the sound card's buffers every so often. With deadline scheduling, that can happen and audio glitches go away.

What it's good for

Posted Oct 14, 2009 16:18 UTC (Wed) by clugstj (subscriber, #4020) [Link] (8 responses)

My question is why is "deadline" better than priority-based. In this application, I would just set the priority high for this "audio application" and it would still work. I don't see the "deadline scheduler" helping in any way here.

What it's good for

Posted Oct 14, 2009 16:47 UTC (Wed) by corbet (editor, #1) [Link] (1 responses)

Tweaking the priority is OK if the audio application is the only thing you care about. But priorities don't eliminate interference between applications, and they can be hard to set up correctly in more complex situations.

A bit more information can be found in this posting on the Ericsson site.

What it's good for

Posted Oct 14, 2009 18:47 UTC (Wed) by clugstj (subscriber, #4020) [Link]

OK, I've read the Ericsson posting. The example there is dead easy to do with priority-based scheduling, the 20ms tasks are done at a higher priority than the rest of the software.

The author doesn't explain at all why he feels the deadline scheduler is a better fit - he just says that it is.

Correction!

Posted Oct 14, 2009 17:43 UTC (Wed) by khim (subscriber, #9252) [Link] (5 responses)

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).

Correction!

Posted Oct 14, 2009 18:39 UTC (Wed) by clugstj (subscriber, #4020) [Link] (4 responses)

"it'll be run and other applications will behave (they'll be evicted in worst case)."

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) [Link]

Where is the "killer app" for the deadline scheduler

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 care.

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 solutions.

Correction!

Posted Oct 14, 2009 21:13 UTC (Wed) by raistlin (guest, #37586) [Link]

Hi clugstj, I'll try to show my point of view on this point...

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
real-time scenarios
- EDF is more flexible and still predictable
- EDF allows better exploitation of system resources (CPU, both on UP and
SMP)
- 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?

Regards,
Dario

Correction!

Posted Oct 22, 2009 8:17 UTC (Thu) by sethml (guest, #8471) [Link]

I see this kind of sceduler being useful for two cases:

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
system.

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.

Correction!

Posted Oct 23, 2009 5:06 UTC (Fri) by damentz (subscriber, #41789) [Link]

There is no "killer app", but there are killer categories.

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.