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

Mon Aug 27 23:58:03 CEST 2012

Glenn,

Yeah, that's my thinking as well.  Bjoern has been a strong advocate of
looking at normalized lateness/tardiness, so I'm interested to hear his
input.

It does seem to me that a task with a short relative deadline will suffer a
lot from tardiness qualitatively even if it has a long period.

-Jeremy Erickson

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

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