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

[Björn Brandenburg]

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.