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