EDF priority tie-breaks by lateness.

Instead of tie-breaking by PID (which is a static
priority tie-break), we can tie-break by lateness
of a prior job. That is, 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}. In case of lateness ties, we fall back
to PID comparisons. This later case will likely
only kick in for initial jobs, when lateness of
"prior" jobs is assumed to be 0.

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

2 files changed, 7 insertions, 1 deletions

diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 338245abd6ed..807b7888695a 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -63,7 +63,7 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_exec_time(t)    (tsk_rt(t)->job_params.exec_time)
 #define get_deadline(t)         (tsk_rt(t)->job_params.deadline)
 #define get_release(t)          (tsk_rt(t)->job_params.release)
-
+#define get_lateness(t)         (tsk_rt(t)->job_params.lateness)
 
 #define is_hrt(t)               \
         (tsk_rt(t)->task_params.cls == RT_CLASS_HARD)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 89ac0dda7d3d..fac939dbd33a 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -110,6 +110,12 @@ struct rt_job {
         /* How much service has this job received so far? */
         lt_t    exec_time;
 
+        /* By how much did the prior job miss its deadline by?
+         * Value differs from tardiness in that lateness may
+         * be negative (when job finishes before its deadline).
+         */
+        long long       lateness;
+
         /* Which job is this. This is used to let user space
          * specify which job to wait for, which is important if jobs
          * overrun. If we just call sys_sleep_next_period() then we