Re: SCHED_EDF infos

Peter Zijlstra
2009-05-30T21:15:55Z

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.