Re: RFC for a new Scheduling policy/class in the Linux-kernel

[Henrik Austad <henrik@austad.us>]

On Tuesday 14 July 2009 18:54:13 James H. Anderson wrote:
> On Tue, 14 Jul 2009, Peter Zijlstra wrote:
> > Hi Jim,
> >
> > On Tue, 2009-07-14 at 11:19 -0400, James H. Anderson wrote:
> >> The first email in this thread that I was cc'ed on talked about
> >> implementing global EDF,
> >
> > Hendrik says that its a modified Modified-Least-Laxity-First, so
> > something like M^2-LLF, and I cc'ed you (and I meant to add Bjorn too,
> > but now see I failed to actually do so) in the hope that you would have
> > some thoughts on his scheduling algorithm, since that is what you do a
> > lot of ;-)
> >
> > It could well be he modified M-LLF into G-EDF, but I'm behind in my
> > reading here, so I'll have to leave that up to others.

Using deadlines as the only measure on multi-core will fail as you must 
consider time (of deadline-miss) in a different way.

In UP, this is given implicitly as you only have a single processor. In MC you 
need to do this the hard way, namely compute the point in time not when the 
task misses the deadline, but when it will *eventually* fail a dealine. By 
doing that, you combine deadline, wcet and granted time in one variable, and 
you have a *single* variable to compare.

By doing this in a global sense, you can avoid bin-packing, load-balancing and 
a lot of the issues that seem to be keeping the PI-people busy. But I think 
I'm going to stay away from that topic now (as I haven't had the time to give 
those emails their deserved attention.

I think M^2-LLF would be as good a name as EFF, but I wanted to emphasize the 
usage of the two failure-variables (the static and the dynamic).

> I meant to say something about this algorithm earlier that may be
> worthwhile.  If I understand Hendrik's algorithm correctly, it falls
> within a class of global schedulers for which bounded deadline
> tardiness is guaranteed (as long as total utilization doesn't exceed
> the system's capacity).  

the tardiness is either 0 or bounded, depending on what you want (and what you 
will do with tasks that do miss their deadlines when they block on locks).

> This follows from results in: 
>
> H. Leontyev and J. Anderson, "Generalized Tardiness Bounds for Global
> Multiprocessor Scheduling",  Proceedings of the 28th IEEE Real-Time
> Systems Symposium, pp. 413-422, December 2007.

Is this available outside locked portals?

> This is a positive thing w.r.t. wanting to support soft real-time
> workloads.  However, global EDF also has this property and (I would
> think) is easier to implement (I'm just guessing here -- we haven't
> actually implemented any algorithm that involves laxities in
> LITMUS^RT).  Ted Baker did some work on an algorithm called EDZL
> (EDF until zero laxity) that is essentially a hybrid of these two
> algorithms.  In simulations we've done (not based on real implementations),
> EDZL exhibits really low tardiness (almost non-existent).  EDZL may
> give you the benefits of using laxities where useful and be easier
> to implement (but that's just my guess)



-- 
     henrik