EDF priority tie-breaks.

Instead of tie-breaking by PID (which is a static
priority tie-break), we can tie-break by other
job-level-unique parameters. This is desirable
because tasks are equaly affected by tardiness
since static priority tie-breaks cause tasks
with greater PID values to experience the most
tardiness.

There are four tie-break methods:

1) Lateness.  If two jobs, J_{1,i} and J_{2,j} of
tasks T_1 and T_2, respectively, have equal
deadlines, we favor the job of the task that
had the worst lateness for jobs J_{1,i-1} and
J_{2,j-1}.

Note: Unlike tardiness, lateness may be less than
zero. This occurs when a job finishes before its
deadline.

2) Normalized Lateness.  The same as #1, except
lateness is first normalized by each task's
relative deadline.  This prevents tasks with short
relative deadlines and small execution requirements
from always losing tie-breaks.

3) Hash. The job tuple (PID, Job#) is used to
generate a hash. Hash values are then compared.
A job has ~50% chance of winning a tie-break
with respect to another job.

Note: Emperical testing shows that some jobs
can have +/- ~1.5% advantage in tie-breaks.
Linux's built-in hash function is not totally
a uniform hash.

4) PIDs. PID-based tie-break used in prior
versions of Litmus.

1 files changed, 8 insertions, 0 deletions

diff --git a/litmus/jobs.c b/litmus/jobs.c
index bc8246572e54..fb093c03d53d 100644
--- a/litmus/jobs.c
+++ b/litmus/jobs.c
@@ -23,6 +23,14 @@ static inline void setup_release(struct task_struct *t, lt_t release)
 void prepare_for_next_period(struct task_struct *t)
 {
         BUG_ON(!t);
+
+        /* Record lateness before we set up the next job's
+         * release and deadline. Lateness may be negative.
+         */
+        t->rt_param.job_params.lateness =
+                (long long)litmus_clock() - 
+                (long long)t->rt_param.job_params.deadline;
+
         setup_release(t, get_release(t) + get_rt_period(t));
 }