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

[Glenn Elliott]

On Mon, Aug 6, 2012 at 6:10 AM, Björn Brandenburg <bbb at mpi-sws.org> wrote:
> On Aug 6, 2012, at 3:22 AM, Glenn Elliott wrote:
>
>>  Currently, Litmus tie-breaks jobs with equal deadlines by PID.  Tasks with lower PIDs get priority over those with higher PIDs.  Basically, the system becomes a static-priority system on synchrounsly-released sets of jobs.  Though tardiness may or may not be bounded, the jobs with greater PIDs always suffer the greatest levels of tardiness. This can make analysis of task set runs cumbersome since there can be a large skew in average response times of tasks.  I am of the opinion that if all tasks have the same periods and all have the same execution behaviors, it would be nice if all tasks had the same average response time (at least in the soft real-time case).
>>
>> How do we tie-break if not by PID?
>>
>> We could try to tie-break by release-time, but this doesn't work when all tasks share the same period.  We could try prioritizing jobs with the latest completion time of their prior job over others, but this requires carrying state information from the prior job into the next; this seems cumbersome.
>>
>> I'd like to propose the following solution:  Instead of tie-breaking by PID, let's instead generate a single hash for the key (pid, job number)-- that is, the pair makes up the hash key (from a crypto-perspective, PID is the salt and job number is the input).  With deadlines, this gives us a total sorted order of all active jobs.  Presuming that the hash function is uniform, response time skew due to PID-base tie-breaks should be eliminated.  In theory, tardiness should be averaged out across all tasks.
>
>
> Hi Glenn,
>
> I think the proposal is interesting, but there's a couple of things that I'm wondering about.
>
> 1) I don't see how the hash-based tie-breaking would yield any analytical advantages. As far as I can see it doesn't make things worse, but if the only advantage is average-case improvements, then couldn't something simpler be used instead?
>
> 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?

> 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?

> 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.

> 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?

>> As an aside, the logic in the return statement of edf_higher_prio() is getting long and complex.  I had to stare at my modifications for some time before I felt that I hadn't broken anything.  Could we consider breaking it up into a series of if-else statements?  Would the compiler generate just-as-efficient code?
>
>
> Agreed, a series of simpler if-return statements might simplify this. The compile creates a sequence of conditional branches anyway. Patches welcome. ;-)

Great!  I'll have something for you soon-ish.

> Thanks,
> Björn


Thanks for your thoughts!

-Glenn