From 4b38febbd59fd33542a343991262119eb9860f5e Mon Sep 17 00:00:00 2001 From: Andrea Bastoni Date: Thu, 17 Dec 2009 21:23:36 -0500 Subject: [ported from 2008.3] Core LITMUS^RT infrastructure Port 2008.3 Core LITMUS^RT infrastructure to Linux 2.6.32 litmus_sched_class implements 4 new methods: - prio_changed: void - switched_to: void - get_rr_interval: return infinity (i.e., 0) - select_task_rq: return current cpu --- litmus/jobs.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 litmus/jobs.c (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c new file mode 100644 index 00000000000..36e314625d8 --- /dev/null +++ b/litmus/jobs.c @@ -0,0 +1,43 @@ +/* litmus/jobs.c - common job control code + */ + +#include + +#include +#include + +void prepare_for_next_period(struct task_struct *t) +{ + BUG_ON(!t); + /* prepare next release */ + t->rt_param.job_params.release = t->rt_param.job_params.deadline; + t->rt_param.job_params.deadline += get_rt_period(t); + t->rt_param.job_params.exec_time = 0; + /* update job sequence number */ + t->rt_param.job_params.job_no++; + + /* don't confuse Linux */ + t->rt.time_slice = 1; +} + +void release_at(struct task_struct *t, lt_t start) +{ + t->rt_param.job_params.deadline = start; + prepare_for_next_period(t); + set_rt_flags(t, RT_F_RUNNING); +} + + +/* + * Deactivate current task until the beginning of the next period. + */ +long complete_job(void) +{ + /* Mark that we do not excute anymore */ + set_rt_flags(current, RT_F_SLEEP); + /* call schedule, this will return when a new job arrives + * it also takes care of preparing for the next release + */ + schedule(); + return 0; +} -- cgit v1.2.2 From b53c479a0f44b8990ce106622412a3bf54809944 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Mon, 16 Jul 2012 20:20:52 -0400 Subject: New Feature: Arbitrary deadlines. Added support for arbitrary deadlines. Constraint: Relative deadline must be >= exec cost. Use: Set relative deadline in rt_task::rdeadline. Set value to 0 to default to implicit deadlines. Limitations: PFAIR not supported by this patch. PFAIR updated to reject tasks that do not have implicit deadlines. --- litmus/jobs.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index 36e314625d8..bc8246572e5 100644 --- a/litmus/jobs.c +++ b/litmus/jobs.c @@ -6,13 +6,13 @@ #include #include -void prepare_for_next_period(struct task_struct *t) +static inline void setup_release(struct task_struct *t, lt_t release) { - BUG_ON(!t); /* prepare next release */ - t->rt_param.job_params.release = t->rt_param.job_params.deadline; - t->rt_param.job_params.deadline += get_rt_period(t); + t->rt_param.job_params.release = release; + t->rt_param.job_params.deadline = release + get_rt_relative_deadline(t); t->rt_param.job_params.exec_time = 0; + /* update job sequence number */ t->rt_param.job_params.job_no++; @@ -20,10 +20,16 @@ void prepare_for_next_period(struct task_struct *t) t->rt.time_slice = 1; } +void prepare_for_next_period(struct task_struct *t) +{ + BUG_ON(!t); + setup_release(t, get_release(t) + get_rt_period(t)); +} + void release_at(struct task_struct *t, lt_t start) { - t->rt_param.job_params.deadline = start; - prepare_for_next_period(t); + BUG_ON(!t); + setup_release(t, start); set_rt_flags(t, RT_F_RUNNING); } -- cgit v1.2.2 From e6f51fb826ce98d436f445aae4eb9e9dba1f30e8 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Mon, 20 Aug 2012 17:28:55 -0400 Subject: 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. --- litmus/jobs.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index bc8246572e5..fb093c03d53 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 From b7012aa7edba4b88906fc39b9005ff4dae69be59 Mon Sep 17 00:00:00 2001 From: Manohar Vanga Date: Thu, 4 Oct 2012 00:30:51 +0200 Subject: litmus: get rid of RT_F_SLEEP and RT_F_RUNNING This patch removes the flags RT_F_SLEEP and RT_F_RUNNING as their name is misleading. This patch replaces them with a 'completed' field in struct rt_param. Signed-off-by: Manohar Vanga --- litmus/jobs.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index fb093c03d53..13a4ed4c9e9 100644 --- a/litmus/jobs.c +++ b/litmus/jobs.c @@ -38,7 +38,7 @@ void release_at(struct task_struct *t, lt_t start) { BUG_ON(!t); setup_release(t, start); - set_rt_flags(t, RT_F_RUNNING); + tsk_rt(t)->completed = 0; } @@ -48,7 +48,7 @@ void release_at(struct task_struct *t, lt_t start) long complete_job(void) { /* Mark that we do not excute anymore */ - set_rt_flags(current, RT_F_SLEEP); + tsk_rt(current)->completed = 1; /* call schedule, this will return when a new job arrives * it also takes care of preparing for the next release */ -- cgit v1.2.2 From 6fd05d4b6c92bb3207fbd30423adf93d5b9b1bdc Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Wed, 9 May 2012 17:11:56 -0400 Subject: Track tasks average execution time, drop in TASK_EXIT record Conflicts: include/litmus/rt_param.h litmus/jobs.c litmus/sched_color.c litmus/sched_task_trace.c --- litmus/jobs.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index 13a4ed4c9e9..8f56131b959 100644 --- a/litmus/jobs.c +++ b/litmus/jobs.c @@ -8,13 +8,14 @@ static inline void setup_release(struct task_struct *t, lt_t release) { - /* prepare next release */ - t->rt_param.job_params.release = release; - t->rt_param.job_params.deadline = release + get_rt_relative_deadline(t); - t->rt_param.job_params.exec_time = 0; + tsk_rt(t)->tot_exec_time += tsk_rt(t)->job_params.exec_time; + /* prepare next release */ + tsk_rt(t)->job_params.release = tsk_rt(t)->job_params.deadline; + tsk_rt(t)->job_params.deadline += get_rt_period(t); + tsk_rt(t)->job_params.exec_time = 0; /* update job sequence number */ - t->rt_param.job_params.job_no++; + tsk_rt(t)->job_params.job_no++; /* don't confuse Linux */ t->rt.time_slice = 1; -- cgit v1.2.2 From bef23ef491e6926f99e14c3b7c5ae2073b2e56a3 Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Thu, 27 Sep 2012 20:09:25 -0400 Subject: Properly track max_exec_time to output in task_exit record. --- litmus/jobs.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index 8f56131b959..802c0b9754c 100644 --- a/litmus/jobs.c +++ b/litmus/jobs.c @@ -8,7 +8,11 @@ static inline void setup_release(struct task_struct *t, lt_t release) { - tsk_rt(t)->tot_exec_time += tsk_rt(t)->job_params.exec_time; + lt_t exec_time = tsk_rt(t)->job_params.exec_time; + + tsk_rt(t)->tot_exec_time += exec_time; + if (tsk_rt(t)->max_exec_time < exec_time) + tsk_rt(t)->max_exec_time = exec_time; /* prepare next release */ tsk_rt(t)->job_params.release = tsk_rt(t)->job_params.deadline; -- cgit v1.2.2 From 836dabfa1ffb64b76541ebc3ca37d2b327a7c8e4 Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Fri, 28 Sep 2012 16:52:08 -0400 Subject: Move task time accounting into the complete_job method. --- litmus/jobs.c | 27 +++++++++++++++++++-------- 1 file changed, 19 insertions(+), 8 deletions(-) (limited to 'litmus/jobs.c') diff --git a/litmus/jobs.c b/litmus/jobs.c index 802c0b9754c..7bc75bba863 100644 --- a/litmus/jobs.c +++ b/litmus/jobs.c @@ -5,18 +5,13 @@ #include #include +#include static inline void setup_release(struct task_struct *t, lt_t release) { - lt_t exec_time = tsk_rt(t)->job_params.exec_time; - - tsk_rt(t)->tot_exec_time += exec_time; - if (tsk_rt(t)->max_exec_time < exec_time) - tsk_rt(t)->max_exec_time = exec_time; - /* prepare next release */ - tsk_rt(t)->job_params.release = tsk_rt(t)->job_params.deadline; - tsk_rt(t)->job_params.deadline += get_rt_period(t); + tsk_rt(t)->job_params.release = release; + tsk_rt(t)->job_params.deadline += release + get_rt_period(t); tsk_rt(t)->job_params.exec_time = 0; /* update job sequence number */ tsk_rt(t)->job_params.job_no++; @@ -52,6 +47,22 @@ void release_at(struct task_struct *t, lt_t start) */ long complete_job(void) { + lt_t amount; + lt_t now = litmus_clock(); + lt_t exec_time = tsk_rt(current)->job_params.exec_time; + + tsk_rt(current)->tot_exec_time += exec_time; + if (lt_before(tsk_rt(current)->max_exec_time, exec_time)) + tsk_rt(current)->max_exec_time = exec_time; + + if (is_tardy(current, now)) { + amount = now - get_deadline(current); + if (lt_after(amount, tsk_rt(current)->max_tardy)) + tsk_rt(current)->max_tardy = amount; + tsk_rt(current)->total_tardy += amount; + ++tsk_rt(current)->missed; + } + /* Mark that we do not excute anymore */ tsk_rt(current)->completed = 1; /* call schedule, this will return when a new job arrives -- cgit v1.2.2