Re: SCHED_EDF infos

[Peter Zijlstra <peterz@infradead.org>]

On Fri, 2009-05-08 at 11:10 +0200, Henrik Austad wrote:
> > In fact, I also  don't have perfect know how to solve PI in Multicore.
> > [...]
> > > deadline inversion will be a problem, in fact, whatever you chooose to 
> > > be the 'key' for picking tasks (priority, niceness, deadlines, wind 
> > > direction, <whatever>), you can pretty much take that and add a 
> > > -inversion after it. :)
> 
> No, PI is going to be deadly no matter what you do.

Right, we would need to extend the Priority Inheritance Protocol to
include everything the regular scheduling functions operate on.

That is, we can reduce scheduling to a single order operator that orders
all the available tasks, such that t_n < t_n+1.

For pure EDF that would be a comparison on deadlines (and available
bandwidth), for FIFO on static priority and for CFS something based on
the virtual runtimes of the involved tasks. For the combined set of
these scheduling classes the comparator uses the class hierarchy to
order between them.

Lets call the full set of data that is used to determine this order a
task's key.

If we then substitute this key for the static priority of the classic
PIP and use this generic comparison operator, it can be extended to
cover arbitrary complex scheduling functions.


This is a bit like the Proxy Execution Protocol, where we leave the
blocked task in the runqueue, but run another task in its stead. The key
point is that it donates the full task state as relevant to the
scheduling function, or even more directly, it uses the scheduler
itself, to solve the Priority Inversion.