First version of EDF-os plugin before fixing compile errors

2 files changed, 120 insertions, 51 deletions

diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 49796bc62d0f..b741645c4e59 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -1,4 +1,5 @@
 #include <linux/threads.h>
+#include <litmus/bheap.h>
 
 /*
  * Definition of the scheduler plugin interface.
@@ -63,8 +64,12 @@ struct edffm_params {
 struct edfos_params {
         /* EDF-os where can a migratory task execute? */
         unsigned int    cpus[NR_CPUS];
-        /* how many cpus are used by this task? */
-        unsigned int nr_cpus;
+        /* Whether this task is a migrating task*/
+        unsigned int migrat;
+        /* ID of the first or only CPU*/
+        unsigned int first_cpu;
+        /* Time of next subtask release or deadline */
+        int heap_data[NR_CPUS];
         /* Fraction of this task exec_cost that each CPU should handle.
          * We keep the fraction divided in num/denom : a matrix of
          * (NR_CPUS rows) x (2 columns).
@@ -72,6 +77,8 @@ struct edfos_params {
          * The second column is the denominator.
          */
         lt_t            fraction[2][NR_CPUS];
+        struct bheap release_queue;
+        struct bheap ready_queue;
 };
 
 /* Parameters for NPS-F semi-partitioned scheduling algorithm.
diff --git a/litmus/sched_edf_os.c b/litmus/sched_edf_os.c
index 984d0678ee5a..c125fd7ee632 100644
--- a/litmus/sched_edf_os.c
+++ b/litmus/sched_edf_os.c
@@ -35,37 +35,16 @@ DEFINE_PER_CPU(edfos_domain_t, edfos_domains);
 #define edfos_params(t)         (t->rt_param.task_params.semi_part.os)
 
 /* Is the task a migratory task? */
-#define is_migrat_task(task)    (edfos_params(task).nr_cpus)
+#define is_migrat_task(task)    (edfos_params(task).migrat)
 /* t is on the wrong CPU (it should be requeued properly) */
-#define wrong_cpu(t)    is_migrat_task((t)) && task_cpu((t)) != get_partition((t))
-/* Get next CPU */
-#define migrat_next_cpu(t)      \
-        ((tsk_rt(t)->task_params.cpu == edfos_params(t).cpus[0]) ? \
-                edfos_params(t).cpus[1] : \
-                edfos_params(t).cpus[0])
-/* Get current cpu */
-#define migrat_cur_cpu(t)       \
-        ((tsk_rt(t)->task_params.cpu == edfos_params(t).cpus[0]) ? \
-                edfos_params(t).cpus[0] : \
-                edfos_params(t).cpus[1])
+#define wrong_cpu(t)            is_migrat_task((t)) \
+                                && task_cpu((t)) != get_partition((t))
 /* Manipulate share for current cpu */
-#define cur_cpu_fract_num(t)    \
-        ((tsk_rt(t)->task_params.cpu == edfos_params(t).cpus[0]) ? \
-                edfos_params(t).fraction[0][0] : \
-                edfos_params(t).fraction[0][1])
-#define cur_cpu_fract_den(t)    \
-        ((tsk_rt(t)->task_params.cpu == edfos_params(t).cpus[0]) ? \
-                edfos_params(t).fraction[1][0] : \
-                edfos_params(t).fraction[1][1])
+#define cur_cpu_fract_num(t)    edfos_params(t).fraction[0][get_partition(t)]
+#define cur_cpu_fract_den(t)    edfos_params(t).fraction[1][get_partition(t)]
 /* Get job number for current cpu */
 #define cur_cpu_job_no(t)       \
-        ((tsk_rt(t)->task_params.cpu == edfos_params(t).cpus[0]) ? \
-                tsk_rt(t)->semi_part.cpu_job_no[0] : \
-                tsk_rt(t)->semi_part.cpu_job_no[1])
-/* What is the current cpu position in the array? */
-#define edfos_cpu_pos(cpu,t)    \
-        ((cpu == edfos_params(t).cpus[0]) ? \
-         0 : 1)
+        tsk_rt(t)->semi_part.cpu_job_no[get_partition(t)]
 
 /*
  * EDF-os: migratory tasks have higher prio than fixed, EDF in both classes.
@@ -73,14 +52,18 @@ DEFINE_PER_CPU(edfos_domain_t, edfos_domains);
  */
 int edfos_higher_prio(struct task_struct* first, struct task_struct* second)
 {
-        if ((first && edfos_params(first).nr_cpus) ||
-                        (second && edfos_params(second).nr_cpus)) {
-                if ((first && edfos_params(first).nr_cpus) &&
-                        (second && edfos_params(second).nr_cpus))
+        if ((first && edfos_params(first).migrat) ||
+                        (second && edfos_params(second).migrat)) {
+                if ((first && edfos_params(first).migrat) &&
+                    (second && edfos_params(second).migrat))
                         /* both are migrating */
-                        return edf_higher_prio(first, second);
+                        if (edfos_params(first).first_cpu <
+                            edfos_params(second).first_cpu)
+                                return 1;
+                        else
+                                return 0;
 
-                if (first && edfos_params(first).nr_cpus)
+                if (first && edfos_params(first).migrat)
                         /* first is migrating */
                         return 1;
                 else
@@ -97,6 +80,11 @@ int edfos_ready_order(struct bheap_node* a, struct bheap_node* b)
         return edfos_higher_prio(bheap2task(a), bheap2task(b));
 }
 
+static int fakepfair_ready_order(struct bheap_node* a, struct bheap_node* b)
+{
+        return *((int*)a->value) < ((int*)b->value);
+}
+
 /* need_to_preempt - check whether the task t needs to be preempted
  *                   call only with irqs disabled and with ready_lock acquired
  */
@@ -260,31 +248,84 @@ static void requeue(struct task_struct* t, rt_domain_t *edf)
  */
 static void update_job_counter(struct task_struct *t)
 {
-        int cpu_pos;
-
-        /* Which CPU counter should be incremented? */
-        cpu_pos = edfos_cpu_pos(t->rt_param.task_params.cpu, t);
-        t->rt_param.semi_part.cpu_job_no[cpu_pos]++;
+        t->rt_param.semi_part.cpu_job_no[get_partition(t)]++;
 
         TRACE_TASK(t, "job_no = %d, cpu_job_no(pos %d) = %d, cpu %d\n",
-                        t->rt_param.job_params.job_no, cpu_pos, cur_cpu_job_no(t),
-                        t->rt_param.task_params.cpu);
+                        t->rt_param.job_params.job_no, get_partition(t),
+                        cur_cpu_job_no(t), t->rt_param.task_params.cpu);
+}
+
+
+static int compute_pfair_deadline(unsigned int wt_num, unsigned int wt_den,
+                                  unsigned int job_no)
+{       
+        unsigned int num, den, dead;
+        num = job_no * wt_den;
+        den = wt_num;
+        dead = num / den;
+        if (num % den > 0)
+                dead++;
+        return dead;
+}
+
+static int compute_pfair_release(unsigned int wt_num, unsigned int wt_den,
+                                 unsigned int job_no)
+{
+        return ((job_no - 1) * wt_den) / wt_num;
 }
 
 /* What is the next cpu for this job? (eq. 8, in EDF-Fm paper) */
 static int next_cpu_for_job(struct task_struct *t)
 {
+        unsigned int cpu, next_rel;
+        struct bheap_node* node;
         BUG_ON(!is_migrat_task(t));
+        
+        /* Process any new subtask releases. */
+        node = bheap_peek(fakepfair_ready_order,
+                          &edfos_params(t).release_queue);
+        while (node && *((int*)node->value) <= job_param(t)->job_no)
+        {
+                node = bheap_take(fakepfair_ready_order,
+                                  &edfos_params(t).release_queue);
+                cpu = ((int*)node->value) - edfos_params(t)->heap_data;
+                *((int*)node->value) = compute_pfair_deadline(fraction[0][cpu],
+                                fraction[1][cpu],
+                                edfos_param(t)->cpu_job_no[cpu] + 1);
+                bheap_insert(fakepfair_ready_order,
+                             &edfos_params(t).ready_queue, node);
+                node = bheap_peek(fakepfair_ready_order,
+                                  &edfos_params(t).release_queue);
+        }
+
+        /* Choose the next Pfair subtask. */
+        node = bheap_take(fakepfair_ready_order,
+                          &edfos_params(t).ready_queue);
+        cpu = ((int*)node->value) - edfos_params(t)->heap_data;
+
+        next_rel = compute_pfair_release(fraction[0][cpu], fraction[1][cpu],
+                                         edfos_params(t)->cpu_job_no[cpu] + 1);
+        if (next_rel < job_params(t)->job_no)
+        {
+                /* Next subtask already released. */
+                (*(int*)node->value) = compute_pfair_deadline(fraction[0][cpu],
+                                        fraction[1][cpu],
+                                        edfos_params(t)->cpu_job_no[cpu]);
+                bheap_insert(fakepfair_ready_order,
+                             &edfos_params(t).ready_queue, node);
+        }
+        else
+        {
+                /* Next subtask not yet released. */
+                (*(int*)node->value) = next_rel;
+                bheap_insert(fakepfair_ready_order,
+                             &edfos_params(t).release_queue, node);
+        }
 
         TRACE_TASK(t, "%u = %u * %u / %u\n",
                         t->rt_param.job_params.job_no, cur_cpu_job_no(t),
                         cur_cpu_fract_den(t), cur_cpu_fract_num(t));
-        if ((t->rt_param.job_params.job_no) ==
-                        (((lt_t) cur_cpu_job_no(t) * cur_cpu_fract_den(t)) /
-                        cur_cpu_fract_num(t)))
-                return edfos_params(t).cpus[0];
-
-        return edfos_params(t).cpus[1];
+        return cpu;
 }
 
 /* If needed (the share for task t on this CPU is exhausted), updates
@@ -292,15 +333,16 @@ static int next_cpu_for_job(struct task_struct *t)
  */
 static void change_migrat_cpu_if_needed(struct task_struct *t)
 {
+        int cpu;
         BUG_ON(!is_migrat_task(t));
         /* EDF-os: if it is a migrating task and it has already executed
          * the required number of jobs on this CPU, we need to move it
          * on its next CPU; changing the cpu here will affect the requeue
          * and the next release
          */
-        if (unlikely(next_cpu_for_job(t) != migrat_cur_cpu(t))) {
-
-                tsk_rt(t)->task_params.cpu = migrat_next_cpu(t);
+        cpu = next_cpu_for_job(t);
+        if (unlikely(cpu != get_partition(t))) {
+                tsk_rt(t)->task_params.cpu = cpu;
                 TRACE_TASK(t, "EDF-os: will migrate job %d -> %d\n",
                         task_cpu(t), tsk_rt(t)->task_params.cpu);
                 return;
@@ -431,6 +473,19 @@ static void edfos_task_new(struct task_struct * t, int on_rq, int running)
         rt_domain_t*            edf  = task_edf(t);
         edfos_domain_t*         edfos = task_edfos(t);
         unsigned long           flags;
+        unsigned int            i;
+        
+        for (i = 0; i < NR_CPUS; i++)
+        {
+                edfos_params(t)->heap_data[i] = compute_pfair_deadline(
+                                edfos_params(t)->fraction[0][i],
+                                edfos_params(t)->fraction[1][i],
+                                0);
+                bheap_add(fakepfair_ready_order, &edfos_params(t)->ready_queue,
+                          &edfos_params(t)->heap_data[i], GFP_ATOMIC);
+        }
+        /* Pick the first CPU to execute on. */
+        change_migrat_cpu_if_needed(t);
 
         TRACE_TASK(t, "EDF-os: task new, cpu = %d\n",
                    t->rt_param.task_params.cpu);
@@ -516,6 +571,7 @@ static void edfos_task_exit(struct task_struct * t)
         unsigned long flags;
         edfos_domain_t*         edfos = task_edfos(t);
         rt_domain_t*            edf;
+        unsigned int i;
 
         raw_spin_lock_irqsave(&edfos->slock, flags);
         if (is_queued(t)) {
@@ -526,6 +582,12 @@ static void edfos_task_exit(struct task_struct * t)
         if (edfos->scheduled == t)
                 edfos->scheduled = NULL;
 
+        /* Deallocate heap nodes. */
+        while (bheap_take_del(fakepfair_ready_order,
+                              &edfos_params(t)->release_queue)) {}
+        while (bheap_take_del(fakepfair_ready_order,
+                              &edfos_params(t)->ready_queue)) {}
+
         TRACE_TASK(t, "RIP\n");
 
         preempt(edfos);