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

[Björn Brandenburg]

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.

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.

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.

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.

Personally, I would prefer simple solutions like 2) or 4), or some other solution with a clear analytical benefit.

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

Thanks,
Björn