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.

4 files changed, 32 insertions, 8 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
diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index 668737f0fbf9..54285aaa0405 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -78,17 +78,27 @@ int edf_higher_prio(struct task_struct* first,
         else if (get_deadline(first_task) == get_deadline(second_task)) {
                 /* Need to tie break */
 
-                /* Tie break by pid */
-                if (first_task->pid < second_task->pid) {
+                /* Tie break by lateness. Jobs with greater lateness get
+                 * priority. This should spread tardiness across all tasks,
+                 * especially in task sets where all tasks have the same
+                 * period and relative deadlines.
+                 */
+                if (get_lateness(first_task) > get_lateness(second_task)) {
                         return 1;
                 }
-                else if (first_task->pid == second_task->pid) {
-                        /* If the PIDs are the same then the task with the
-                         * inherited priority wins.
-                         */
-                        if (!second_task->rt_param.inh_task) {
+                else if(get_lateness(first_task) == get_lateness(second_task)) {
+                        /* Tie break by pid */
+                        if (first_task->pid < second_task->pid) {
                                 return 1;
                         }
+                        else if (first_task->pid == second_task->pid) {
+                                /* If the PIDs are the same then the task with the
+                                 * inherited priority wins.
+                                 */
+                                if (!second_task->rt_param.inh_task) {
+                                        return 1;
+                                }
+                        }
                 }
         }
         return 0; /* fall-through. prio(second_task) > prio(first_task) */
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));
 }