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

[Glenn Elliott]

Since lateness is a function of absolute deadline, I thought it would be goofy to normalize against period.


On Aug 27, 2012, at 4:46 PM, Jeremy Erickson <jerickso at cs.unc.edu> wrote:

> 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
> 
> _______________________________________________
> 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/e1234e13/attachment.html>