Comments to selected things inline.<div><br><div>><br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
> 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.<br>

<br>
</div>I like this idea and it is something I will consider.  Although, a<br>
job's priority can change if it suspends (either for a lock or I/O).<br>
This may be harmless, but I want to make sure that there aren't any<br>
strange edge cases.  With regards to priority inheritance, I suppose<br>
there would be no inheritance between jobs of equal deadlines.  Still,<br>
suppose we have a self-suspension within a critical section.  Could an<br>
inversion occur since the lock holder's priority would decrease due to<br>
its suspension?  If there is an inversion, would it be bounded without<br>
priority inheritance?<br>
<div class="im"><br></div></blockquote><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
> 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.<br>

<br>
</div>I think this approach could perform better than hashes, but I would<br>
rather avoid methods that rely on execution time estimates and<br>
budgets.  Execution times can vary and we sometimes run with budget<br>
enforcement disabled.  Perhaps this approach would not work best for<br>
my GPU use-cases, but would for others.  We could add this as a<br>
compile time (or runtime?) tie-break method.<br>
<div class="im"><br>
> 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.<br>
<br>
</div>I like this idea more than the previous one.  I imagine that tasks<br>
would naturally take turns being the tie-break victim (in<br>
round-robin?).  As you suggested in #3, I suppose this would have to<br>
be normalized?  Should we normalize by relative deadline instead of<br>
period since we now support arbitrary deadlines?  Do we also need to<br>
consider utilization/density?<br>
<div class="im"><br></div></blockquote><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
> 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.<br>
<br>
</div>This was my first thought, but I couldn't come up with a<br>
straight-forward implementation.  Also, I'm not sure how it would work<br>
with tasks of different relative deadlines.<br>
<div class="im"><br></div></blockquote><div>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.</div><div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
> Personally, I would prefer simple solutions like 2) or 4), or some other solution with a clear analytical benefit.<br>
<br>
</div>I agree, but I would also like to avoid dependencies on things like<br>
execution times and budgets.  Perhaps one of the theory guys would<br>
like to chime in and share their thoughts?<br>
<div class="im"><br></div></blockquote><div>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).</div>
<div> </div><div>-Jeremy Erickson</div></div></div></div>