[LITMUS^RT] Hash-Based Tie-Breaking for EDF

Mon Aug 27 22:46:11 CEST 2012

Slightly off-topic question raised by this discussion: is it better to
normalize tardiness against period or relative deadline?  (It makes a
difference for the journalized version of my ECRTS paper.)  My inclination
is that relative deadline seems more useful.

-Jeremy Erickson

On Mon, Aug 27, 2012 at 3:58 PM, Glenn Elliott <gelliott at cs.unc.edu> wrote:

>
> On Aug 24, 2012, at 4:33 AM, Björn Brandenburg <bbb at mpi-sws.org> wrote:
>
> >
> > On Aug 21, 2012, at 12:10 AM, Glenn Elliott wrote:
> >
> >> I've implemented an alternative to hash-based tie-breaks.  This
> >> alternative implements Bjorn's suggestion to tie-break on tardiness.
> >> Jobs that were tardy in their last invocation get priority.  That is,
> >> the tardier a task's prior job was, the greater priority it gets in
> >> tie breaking.
> >
> > Hi Glenn,
> >
> > thanks a lot for spearheading this!
> >
> >>
> >> Some things to note:
> >> 1) Lateness is not normalized against relative deadline, so I believe
> >> some biases may emerge for some task sets.  For example, suppose we
> >> have a implicit-deadline periodic task set where all tasks have equal
> >> periods, but execution times vary from task to task.  I believe in the
> >> long term, tasks with longer execution times will be favored in
> >> tie-breaks (they will have greater lateness values, on average, even
> >> if they consistently win tie-breaks).  At first I thought this was a
> >> problem, but now I think this may actually be a desirable property.
> >
> > Not sure about this. Suppose you have a task with relative deadline 10ms
> and one with relative deadline 1000ms. Wouldn't a lateness of, say, 300ms
> be much more severe for the former task than for the latter? Shouldn't it
> receive priority based on that observation?
> >
> >> 2) Lateness is computed in prepare_for_next_period().  While our use
> >> of lateness in this patch is limited to EDF scheduling, I thought this
> >> information might be useful in future plugins.  It could also be
> >> exposed to the user space.  I'm not sure if this is really of any
> >> value though.
> >
> > Seems reasonable. Lateness could be exported via the control page.
> >
> >> 3) The computation of lateness casts (unsigned long long)'s to (long
> >> long)'s before computing a difference.  I originally had slightly more
> >> complicated code that avoided casts, but then I realized that our
> >> deadline comparators, i.e., lt_after(), do this casting as well.  If
> >> we're not concerned about overflow there, I figured I shouldn't worry
> >> about it either.  (Although, it does make me wonder why lt_t is
> >> (unsigned long long) and not (long long).)
> >
> > The LITMUS^RT time types mirror Linux's time definitions. We use 64-bit
> unsigned integers because that is what Linux uses (or used when LITMUS^RT
> was started). The lt_after() / lt_before() comparison functions can handle
> overflows to some extent.
> >
> >> 4) The idea of changing EDF tie breaking was generally well-received,
> >> so tie breaking methods is no longer a compile-time option.  I can add
> >> it back in if others object.
> >
> > I'd prefer a compile-time option (even if for no other reason than to
> enable easy comparisons).
> >
> >> 5) As per our earlier discussions, I've also recoded the EDF logic to
> >> be more readable in a separate patch.
> >>
> >> Two patches are attached. Patch #1 makes EDF logic more readable.
> >> Patch #2 implements lateness-based tie-breaks.  (Patch #2 depends upon
> >> Patch #1.)  These patches may be viewed on rtsrv.cs.unc.edu for UNC
> >> folks (branch: wip-edf-tie-break).  Note: I do not believe these
> >> patches include Bjorn's recent emergency fixes for partitioned
> >> scheduling.
> >
> > Would it be possible to move to the Github repo that Chris set up for
> for-review branches? Then everyone could participate (and we get a pretty
> interface for free).
> >
> > Thanks,
> > Björn
> >
> > PS: I'll be without email access for the next week or so, so I'll be
> slow to respond to follow ups.
> >
> >
> > _______________________________________________
> > litmus-dev mailing list
> > litmus-dev at lists.litmus-rt.org
> > https://lists.litmus-rt.org/listinfo/litmus-dev
>
>
>
> Hello All,
>
> I've created a more robust patch for EDF tie-breaking.  You may view the
> patch on github (wip-robust-tie-break):
> https://github.com/LITMUS-RT/litmus-rt/compare/wip-robust-tie-break
>
> What's new:
> 1) Tie-break method is configurable at compile-time.
> 2) Tie-break options: (1) Lateness, (2) Normalized Lateness (lateness is
> normalized by relative deadline), (3) Hash-based, (4) Traditional PID
> tie-break.
> 3) fpmath.h.  Normalized lateness required the introduction of fixed-point
> math.  I had considered an algebraically equivalent method* to compare
> normalized lateness values, but I realized that overflow was easily
> possible if both lateness and relative deadline were on the order of ~4
> seconds on 64-bit platforms (and 65 microseconds on 32-bit platforms).
>  fpmath.h is originally from an earlier version of Litmus (pre-Björn
> re-arch, I think).  I am not sure if it was ever mainlined into Litmus, or
> if it was only in a side-branch of Aaron Block's.  I have been maintaining
> my own fpmath.h for the last two years.  I have found it to be useful for
> implementing feedback control mechanisms for adaptive algorithms (Aaron
> used it for the same purposes).  My version of fpmath.h is pretty much like
> Aaron's, except I add support for 64-bit systems.  I think I also tweaked
> some #defines to allow use in liblitmus.  If we don't want to use fpmath.h,
> I suppose we could scale lateness and relative deadline parameters before
> making a comparison.  I wasn't sure what a proper scaling factor would be
> though.  There is also some loss of precision, but there already is some
> loss with fpmath.h.
>
> I'm afraid that I need to start working on more core activities, so I
> would like to wrap up this tie-break patch soon.  I would like us to decide
> exactly on what should go in staging (if anything).  If there isn't any
> interest, I'll just maintain this on my own on the side.  Please note that
> implementing different tie-breaking methods is pretty easy on top of the
> code I provide.  It just takes a few lines of code in edf_common.c and an
> update to Kconfig to add the new method.
>
> * The comparison "L_1/D_1 > L_2/D_2" is equivalent to "L_1*D_2 > L_2*D_1"
>
> Thanks,
> Glenn
>
>
> _______________________________________________
> litmus-dev mailing list
> litmus-dev at lists.litmus-rt.org
> https://lists.litmus-rt.org/listinfo/litmus-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120827/e78cc755/attachment.html>