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

[Jeremy Erickson]

Comments to selected things inline.

>

> > 2) For example, why not simply leave out tie breaks altogether (i.e.,
> remove the PID check)? Then the insertion order into the ready queue would
> create "arbitrary" tie breaks. While these tie breaks would not be
> necessarily consistent, I don't think this would affect worst-case
> analysis, which typically assumes that ties are broken against the job
> under analysis anyway.
>
> I like this idea and it is something I will consider.  Although, a
> job's priority can change if it suspends (either for a lock or I/O).
> This may be harmless, but I want to make sure that there aren't any
> strange edge cases.  With regards to priority inheritance, I suppose
> there would be no inheritance between jobs of equal deadlines.  Still,
> suppose we have a self-suspension within a critical section.  Could an
> inversion occur since the lock holder's priority would decrease due to
> its suspension?  If there is an inversion, would it be bounded without
> priority inheritance?
>
> Although I don't think doing this would invalidate any of our worst-case
analytical results (for exactly the reason Bjoern mentioned), it does break
some of the proofs as written.  For example, all of the Uma-style tardiness
proofs (including mine) work by inducting over the set of all jobs in
priority order.  If ties are not broken consistently between jobs, no such
ordering really exists, so the proof would need to be tweaked a bit.  As
Glenn pointed out, we no longer have job-level static priorities, which I
think could cause issues for synchronization.  So I wouldn't jump on this
method too quickly.


> > 3) If your goal is to equally distribute tardiness among jobs, why not
> directly tie-break by the current tardiness estimate? To deal with tasks
> with greatly differing periods, the tardiness  tie-break should probably be
> normalized with regard to the period (i.e., tie-break by relative
> tardiness). A job's estimated tardiness (and thus its estimated relative
> tardiness) assuming it is scheduled right away can be inferred from the
> current time, its deadline, and its remaining execution budget. In fact,
> when breaking a tie among two jobs A and B, you could even factor A's
> remaining execution budget to estimate B's tardiness if B is *not*
> scheduled right away.
>
> I think this approach could perform better than hashes, but I would
> rather avoid methods that rely on execution time estimates and
> budgets.  Execution times can vary and we sometimes run with budget
> enforcement disabled.  Perhaps this approach would not work best for
> my GPU use-cases, but would for others.  We could add this as a
> compile time (or runtime?) tie-break method.
>
> > 4) Alternatively, you could tie-break by the last job's actual
> tardiness. This would only be one additional lt_t variable in struct
> task_struct, which I think would be acceptable.
>
> I like this idea more than the previous one.  I imagine that tasks
> would naturally take turns being the tie-break victim (in
> round-robin?).  As you suggested in #3, I suppose this would have to
> be normalized?  Should we normalize by relative deadline instead of
> period since we now support arbitrary deadlines?  Do we also need to
> consider utilization/density?
>
> I do kind of like this method.  It might even be possible to exploit
analytically somehow with new analysis.  The previous method has a similar
potential, but looks more complicated to implement.


> > 5) Another simple solution for your particular use case might be to have
> a round-robin "tie-break" token, but this is probably also quite difficult
> to exploit analytically.
>
> This was my first thought, but I couldn't come up with a
> straight-forward implementation.  Also, I'm not sure how it would work
> with tasks of different relative deadlines.
>
> My intuition is that this would be harder to exploit analytically than the
previous two, although I haven't thought about it enough to have any actual
results.


> > Personally, I would prefer simple solutions like 2) or 4), or some other
> solution with a clear analytical benefit.
>
> I agree, but I would also like to avoid dependencies on things like
> execution times and budgets.  Perhaps one of the theory guys would
> like to chime in and share their thoughts?
>
> Method 4 only depends on deadlines, not execution times or budgets.  It
seems like the most promising option to me, although at present it doesn't
buy you anything analytically (like all proposals here).

-Jeremy Erickson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120815/95f1dcdc/attachment.html>