Re: SCHED_EDF infos
From: Peter Zijlstra
Date: Sat May 30 2009 - 17:16:00 EST
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
It's tracktable, but it really complicates the matter. But yes, PEP is
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/