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

[James H. Anderson]

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.

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).  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.

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)

Regarding all these "legacy" issues, I think it would be helpful to
write them all down carefully and formally, and then think about
what are the *simplest* mechanisms that will do the job in the common
case.  It is not worthwhile (in my opinion) to introduce tons of
complexity to nip at corner cases that aren't that common.  Of course,
this begs the question of what is "common" and what is not: something
that may also be worth trying to find evidence for and writing down.

Or better yet, someone needs to define a new standard for multicore...
but I'm not sure how that gets done.

Gotta go....

-Jim
--
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/