SCHED_DEADLINE returns

By Jonathan Corbet
April 11, 2012

Deadline scheduling has been discussed on these pages a number of times. In short: rather than using priorities, a deadline scheduler characterizes each process with a maximum CPU time required and the deadline by which it must receive that CPU time. A properly-written deadline scheduler can ensure that every process meets its deadlines while refusing to take work that would cause any deadlines to be missed. Patches adding a deadline scheduler to Linux have existed for a few years, but their progress toward the mainline has been slow; recently that progress has been very slow since the principal developer involved has moved on to other projects.

The deadline scheduler patches now have a new developer in the form of Juri Lelli; Juri has posted a new version of the patches to restart the discussion. The changes from the last time around are mostly minor: review comments addressed and an improved migration mechanism added. The plan is to continue to fill in the gaps required to make the deadline scheduler production-worthy and, eventually, to get it into the mainline. To that end, there is a new git repository, an application designed to test deadline scheduling, and a new mailing list. One assumes Juri would be most appreciative of testing and patches.

Index entries for this article
Kernel	Scheduler/Deadline scheduling

SCHED_DEADLINE returns

Posted Apr 12, 2012 7:24 UTC (Thu) by flok (subscriber, #17768) [Link] (2 responses)

I wonder if it would be helpfull if an application could somehow tell the scheduler of the amount of time it'll need to do its job. Then the scheduler might be able to its job more efficiently.

SCHED_DEADLINE returns

Posted Apr 12, 2012 19:24 UTC (Thu) by dlang (guest, #313) [Link] (1 responses)

two problems

1. how can the application know this? (the time will vary depending on how well caching works)

2. what do you do with an application that ends up using more than it claimed it would?

SCHED_DEADLINE returns

Posted Apr 12, 2012 19:39 UTC (Thu) by corbet (editor, #1) [Link]

Of course, deadline scheduling depends on exactly this: an application must declare a worst-case execution time along with its deadline. Knowing what the WCET should be is, of course, not a small problem; it's currently fodder for a number of academic careers, I think. Usual practice, I suspect, is to determine it empirically.

As for what happens if you blow the WCET: the deadline scheduler just freezes you out until the next scheduling period starts.

SCHED_DEADLINE returns

Posted Apr 12, 2012 11:32 UTC (Thu) by armisx (guest, #83957) [Link] (2 responses)

What we need now is a deadline for merging them...

SCHED_DEADLINE returns

Posted Apr 13, 2012 16:08 UTC (Fri) by bronson (subscriber, #4806) [Link] (1 responses)

If only the developers could predict exactly how long this job will take...

SCHED_DEADLINE returns

Posted Apr 14, 2012 1:51 UTC (Sat) by nevets (subscriber, #11875) [Link]

Some of the changes may go in soon. The general scheduling looks pretty good. But the later patches (namely the priority inheritance ones) need more consideration and thought. Thus, you may get deadline scheduling, but they wont have any guarantees ;-)