Re: SCHED_EDF infos

[Peter Zijlstra <peterz@infradead.org>]

On Sat, 2009-05-30 at 22:40 +0200, Henrik Austad wrote:
> On Sat, May 30, 2009 at 09:15:57PM +0200, Peter Zijlstra wrote:
> > 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.
> 
> I think you can do this in pick_next_task, actually.
> 
> I wonder, will it be enough to add a single task_struct *blocker to task_struct? 
> 
> Then you will end up with a list (or tree of tasks) all ending in a single task 
> that holds the required resource. Say task A,B,C,D and E holds some critical 
> resource, then you can end up with (awful ascii-art to starboard!):
> 
>    A -> B -> E
>              ^
>              |
>         C -> D
> 
> So, whenever A-D is being scheduled, E will be picked by pick_next_task as it 
> detects that it is blocked, so it follows the blocker untill it finds an 
> unblocked task. That task  must then be the holder of the resource.
> 
> Now, the 'only' thing that needs to be done, is to let the kernel update the 
> blocker with the correct task, and detect the moment it releases the resource.
> 
> Or am I missing some crazy racecondition here?

Except for the bit where you avoid multiple cpus trying to run the same
task :-)

It's tracktable, but it really complicates the matter. But yes, PEP is
very attractive.