From 8d687fc34b89fa1150a82f71fed35e21490df42b Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Mon, 20 Aug 2012 17:28:55 -0400 Subject: 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. --- include/litmus/litmus.h | 2 +- include/litmus/rt_param.h | 6 ++++++ litmus/edf_common.c | 24 +++++++++++++++++------- litmus/jobs.c | 8 ++++++++ 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)); } -- cgit v1.2.2