Implementation of the EDZL scheduler.wip-edzl-final

Implementation of the EDZL scheduler.  Zero-laxity points are
tracked by timers while jobs are in the pending state.  Locking
primatives are not supported.

4 files changed, 53 insertions, 3 deletions

diff --git a/include/litmus/edzl_common.h b/include/litmus/edzl_common.h
new file mode 100644
index 000000000000..d1a89ee08554
--- /dev/null
+++ b/include/litmus/edzl_common.h
@@ -0,0 +1,14 @@
+/*
+ * EDZL common data structures and utility functions shared by all EDZL
+ * based scheduler plugins
+ */
+
+#ifndef __UNC_EDZL_COMMON_H__
+#define __UNC_EDZL_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+int edzl_higher_prio(struct task_struct* first,
+                     struct task_struct* second);
+
+#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 246483783fc0..3203a0809f96 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -54,6 +54,12 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_release(t)          (tsk_rt(t)->job_params.release)
 #define get_class(t)            (tsk_rt(t)->task_params.cls)
 
+#ifdef CONFIG_PLUGIN_EDZL
+#define get_zerolaxity(t)   (tsk_rt(t)->job_params.zero_laxity)
+#define set_zerolaxity(t)   (tsk_rt(t)->job_params.zero_laxity=1)
+#define clear_zerolaxity(t) (tsk_rt(t)->job_params.zero_laxity=0)
+#endif
+
 inline static int budget_exhausted(struct task_struct* t)
 {
         return get_exec_time(t) >= get_exec_cost(t);
@@ -86,6 +92,21 @@ static inline lt_t litmus_clock(void)
         return ktime_to_ns(ktime_get());
 }
 
+#ifdef CONFIG_PLUGIN_EDZL
+inline static lt_t laxity_remaining(struct task_struct* t)
+{
+    lt_t now = litmus_clock();
+    lt_t remaining = budget_remaining(t);
+    lt_t deadline = get_deadline(t);
+    
+    if(lt_before(now + remaining, deadline))
+        return (deadline - (now + remaining));
+    else
+        return 0;
+}
+#endif
+
+
 /* A macro to convert from nanoseconds to ktime_t. */
 #define ns_to_ktime(t)          ktime_add_ns(ktime_set(0, 0), t)
 
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a7a183f34a80..41768f446436 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -90,6 +90,14 @@ struct rt_job {
          * Increase this sequence number when a job is released.
          */
         unsigned int    job_no;
+    
+#ifdef CONFIG_PLUGIN_EDZL
+        /* boolean indicating zero-laxity state.  We will
+     set this flag explicitly at zero-laxity detection.
+     This makes priority comparison operations more
+     predictable since laxity varies with time */
+        unsigned int    zero_laxity:1;
+#endif    
 };
 
 struct pfair_param;
@@ -113,6 +121,11 @@ struct rt_param {
 
         /* timing parameters */
         struct rt_job           job_params;
+    
+#ifdef CONFIG_PLUGIN_EDZL
+        /* used to trigger zero-laxity detection */
+        struct hrtimer          zl_timer;
+#endif    
 
         /* task representing the current "inherited" task
          * priority, assigned by inherit_priority and
@@ -120,7 +133,7 @@ struct rt_param {
          * could point to self if PI does not result in
          * an increased task priority.
          */
-         struct task_struct*    inh_task;
+    struct task_struct* inh_task;
 
 #ifdef CONFIG_NP_SECTION
         /* For the FMLP under PSN-EDF, it is required to make the task
diff --git a/include/litmus/sched_global_plugin.h b/include/litmus/sched_global_plugin.h
index cac2de63a3ee..21a91817eac1 100644
--- a/include/litmus/sched_global_plugin.h
+++ b/include/litmus/sched_global_plugin.h
@@ -29,7 +29,7 @@ typedef struct task_struct* (*take_ready_t)(rt_domain_t* rt);
 typedef void (*add_ready_t)(rt_domain_t* rt, struct task_struct *new);
 typedef void (*job_arrival_t)(struct task_struct* task);
 typedef void (*job_completion_t)(struct task_struct *t, int forced);
-
+typedef int (*preemption_needed_t)(struct task_struct *t);
 
 struct sched_global_plugin {
     
@@ -41,6 +41,7 @@ struct sched_global_plugin {
     add_ready_t     add_ready;
     job_arrival_t   job_arrival;
     job_completion_t    job_completion;
+    preemption_needed_t preemption_needed;
     
     rt_domain_t domain;
     
@@ -60,7 +61,6 @@ extern struct sched_global_plugin* active_gbl_plugin;
  *
  * Use prefix "gbl_" (global)
  */
-int gbl_preemption_needed(struct task_struct *t);
 int gbl_ready_order(struct bheap_node* a, struct bheap_node* b);
 int gbl_cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b);
 void gbl_update_cpu_position(cpu_entry_t *entry);
@@ -69,6 +69,7 @@ void gbl_link_task_to_cpu(struct task_struct* linked, cpu_entry_t *entry);
 void gbl_unlink(struct task_struct* t);
 void gbl_preempt(cpu_entry_t *entry);
 void gbl_requeue(struct task_struct* task);
+void gbl_update_queue_position(struct task_struct *task);
 void gbl_check_for_preemptions(void);
 void gbl_release_jobs(rt_domain_t* rt, struct bheap* tasks);
 void gbl_job_completion(struct task_struct *t, int forced);
@@ -87,6 +88,7 @@ long gbl_activate_plugin(void* plugin);
  * Use prefix "gblv_" (global virtual)
  */
 void gblv_job_arrival(struct task_struct* task);
+int gblv_preemption_needed(struct task_struct *t);
 void gblv_tick(struct task_struct* t);
 struct task_struct* gblv_schedule(struct task_struct * prev);
 void gblv_finish_switch(struct task_struct *prev);