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
--
To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
