Implemented background scheduling

1 files changed, 81 insertions, 32 deletions

diff --git a/litmus/sched_edfsc.c b/litmus/sched_edfsc.c
index 3db7c4f44822..e6eb50d05e46 100644
--- a/litmus/sched_edfsc.c
+++ b/litmus/sched_edfsc.c
@@ -54,15 +54,16 @@ u64 sys_util, future_sys_util;
 

 static u64 cont_job_id;

 

-#define is_container(task) task->container_domain == NULL

-#define is_fixed(task) task->container_task != NULL

-#define is_migrating(task) !is_fixed(task) && !is_container(task)

+#define is_container(task) task && task->container_domain == &gsched_domain

+#define is_fixed(task) task && task->container_task != NULL

+#define is_migrating(task) task && task->container_domain == NULL && task->container_task == &gsched_domain

 

 #define FP_SHIFT 20

 #define fp_div(a, b) a * (1 << FP_SHIFT) / b

 #define to_fp(a) a << FP_SHIFT

 

 //preempts whatever is scheduled on that core. If it's a container, then preempt its fixed task

+//works if entry->scheduled is null

 static void preempt(cpu_entry_t *entry)

 {

         if (is_container(entry->scheduled))

@@ -71,18 +72,18 @@ static void preempt(cpu_entry_t *entry)
                 preempt_if_preemptable(entry->scheduled, entry->cpu);

 }

 

-//requeues task in the specified domain

-static noinline void requeue(struct task_struct* task, rt_domain_t* domain)

+//requeues task in the domain recorded in its edfsc_params

+static noinline void requeue(struct task_struct* task)

 {

         BUG_ON(!task);

         /* sanity check before insertion */

         BUG_ON(is_queued(task));

 

         if (is_early_releasing(task) || is_released(task, litmus_clock()))

-                __add_ready(domain, task);

+                __add_ready(tsk_rt(task)->edfsc_params.container_domain, task);

         else {

                 /* it has got to wait */

-                add_release(domain, task);

+                add_release(tsk_rt(task)->edfsc_params.container_domain, task);

         }

 }

 

@@ -104,7 +105,7 @@ static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
         /* Note that a and b are inverted: we want the lowest-priority CPU at

          * the top of the heap.

          */

-        return edf_higher_prio(b->linked, a->linked);

+        return (is_container(b->linked) && tsk_rt(b->linked)->utilization == to_fp(1)) || edf_higher_prio(b->linked, a->linked);

 }

 

 /* caller must hold gsnedf lock */

@@ -207,10 +208,12 @@ static noinline void unlink(struct task_struct* t)
         }

 }

 

+//TODO change local linking

 static void g_preempt_check(void)

 {

         struct task_struct *task;

         cpu_entry_t *last;

+        cpu_entry_t *target;

 

 #ifdef CONFIG_PREFER_LOCAL_LINKING

         cpu_entry_t *local;

@@ -231,22 +234,31 @@ static void g_preempt_check(void)
         for (last = lowest_prio_cpu();

              edf_preemption_needed(&gsched_domain, last->linked);

              last = lowest_prio_cpu()) {

+                target = last;

+                if (is_container(last->linked) && tsk_rt(last->linked)->utilization == to_fp(1))

+                        break;

                 /* preemption necessary */

                 task = __take_ready(&gsched_domain);

-                TRACE("check_for_preemptions: attempting to link task %d to %d\n",

-                      task->pid, last->cpu);

-

+                if (is_container(task))

+                        cpu_entry_t *target = edfsc_cpus[tsk_rt(task)->edfsc_params.id];

                 if (requeue_preempted_job(last->linked))

                         requeue(last->linked);

-

-                link_task_to_cpu(task, last);

-                preempt(last);

+                TRACE("check_for_preemptions: attempting to link task %d to %d\n",

+                      task->pid, target->cpu);

+                if (target != last) {

+                        TRACE("check_for_preemptions: swapping tasks linked on %d and %d\n",

+                                  last->cpu, target->cpu);

+                        link_task_to_cpu(target->linked, last);

+                        preempt(last);

+                }

+                link_task_to_cpu(task, target);

+                preempt(target);

         }

 }

 

 static int c_preempt_check(container_domain_t* container)

 {

-        if (edf_preemption_needed(&container->domain, container->scheduled)) {

+        if (is_migrating(container->scheduled) || edf_preemption_needed(&container->domain, container->scheduled)) {

                 preempt(&container->domain);

                 return 1;

         } else

@@ -266,7 +278,7 @@ static void c_remove_task(struct task_struct *t)
 {

     struct task_struct* container_task = tsk_rt(t)->edfsc_params.container_task;

     if (is_queued(t)) {

-        remove(tsk_rt(container_task)->edfsc_params.container_domain, t);

+        remove(tsk_rt(container_task)->edfsc_params.container_domain.domain, t);

     }

     tsk_rt(container_task)->edfsc_params.container_domain.sys_util -=

         tsk_rt(t)->task_params.utilization;

@@ -300,8 +312,11 @@ static noinline void g_job_completion(struct task_struct* t, int forced)
                 unlink(t);

                 /* requeue

                  * But don't requeue a blocking task. */

-                if (is_current_running()) {

-                        requeue(t, gsched_domain);

+                if (is_current_running()) { //since we don't support blocking, this should always be true

+                        if (is_container(t) && is_container(tsk_rt(t)->edfsc_params.container_domain.scheduled)) {

+                                requeue(tsk_rt(t)->edfsc_params.container_domain.scheduled);

+                        }

+                        requeue(t);

                         g_preempt_check();

                 }

         }

@@ -337,8 +352,13 @@ static void g_finish_switch(struct task_struct *prev)
 #endif

 }

 

+static int fifo_prio(struct bheap_node* _a, struct bheap_node* _b) {

+        return 0;

+}

+

 // takes in the container_domain pointer in container task_struct

 // assuming prev is previous task running on the processor before calling schedule

+// global lock in effect

 static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_struct * prev)

 {

         rt_domain_t* edf = cedf.domain;

@@ -357,6 +377,7 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru
          */

         BUG_ON(cedf->scheduled && cedf->scheduled != prev);

         BUG_ON(cedf->scheduled && !is_realtime(prev));

+        BUG_ON(is_migrating(cedf->scheduled));

 

         /* (0) Determine state */

         exists      = cedf->scheduled != NULL;

@@ -365,7 +386,7 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru
                              && budget_exhausted(cedf->scheduled);

         np          = exists && is_np(cedf->scheduled);

         sleep       = exists && is_completed(cedf->scheduled);

-        preempt     = edf_preemption_needed(edf, prev);

+        preempt     = is_migrating(prev) || edf_preemption_needed(edf, prev);

 

         /* If we need to preempt do so.

          * The following checks set resched to 1 in case of special

@@ -389,7 +410,11 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru
          * this.

          */

         if (!np && (out_of_time || sleep)) {

-                c_job_completion(cedf->scheduled, !sleep);

+                if (is_fixed(cedf->scheduled))

+                        c_job_completion(cedf->scheduled, !sleep);

+                else {

+                        g_job_completion(cedf->scheduled, !sleep);

+                }

                 resched = 1;

         }

 

@@ -405,7 +430,11 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru
                  * the appropriate queue.

                  */

                 if (cedf->scheduled && !blocks)

-                        requeue(cedf->scheduled, edf);

+                        if (is_fixed(cedf->scheduled))

+                                requeue(cedf->scheduled, edf);

+                        else {

+                                requeue(cedf->scheduled, &gsched_domain);

+                        }

                 next = __take_ready(edf);

         } else

                 /* Only override Linux scheduler if we have a real-time task

@@ -417,11 +446,27 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru
         if (next) {

                 TRACE_TASK(next, "scheduled at %llu\n", litmus_clock());

         } else {

-                TRACE("becoming idle at %llu\n", litmus_clock());

+                struct bheap temp;

+                next = __take_ready(&gsched_domain);

+                while (is_container(next)) {

+                        bheap_insert(fifo_prio, &temp, tsk_rt(next)->heap_node);

+                        next = __take_ready(&gsched_domain);

+                }

+                if (next) {

+                        TRACE("stealing stack at %llu\n", litmus_clock());

+                } else {

+                        TRACE("cpu become idle at %llu\n", litmus_clock());

+                }

+                while (bheap_peak(fifo_prio, &temp)) {

+                        __add_ready(&gsched_domain, bheap_take(fifo_prio, &temp));

+                }

         }

-

+        

+        cedf->changed_budget = (budget_remaining(next) > budget_remaining(cedf->container)) ? budget_remaining(cedf->container) : budget_remaining(next);

+        cedf->scheduled_last_exec_time = get_exec_time(next);

+        tsk_rt(next)->job_params.exec_time += cedf->changed_budget;

+        

         cedf->scheduled = next;

-        sched_state_task_picked();

         raw_spin_unlock(&cedf->c_lock);

 

         return next;

@@ -437,16 +482,20 @@ static struct task_struct* edfsc_gschedule(struct task_struct * prev)
         raw_spin_lock(&g_lock);

 

         /* sanity checking */

-        BUG_ON(entry->scheduled && entry->scheduled != prev && entry->scheduled->container_domain != NULL);

+        BUG_ON(entry->scheduled && entry->scheduled != prev && !is_container(entry->scheduled));

         BUG_ON(entry->scheduled && !is_realtime(prev));

         BUG_ON(is_realtime(prev) && !entry->scheduled);

 

-    // update container budget if fixed task

-        if (prev && is_fixed(prev)) {

-                cont_domain_t* cdomain = tsk_rt(prev->container_task)->edfsc_params.container_domain;

+    // update container budget if prev was a fixed or background scheduled task

+        if (prev != entry->scheduled) {

+                cont_domain_t* cdomain = tsk_rt(entry->scheduled)->edfsc_params.container_domain;

                 prev->job_params.exec_time -= cdomain->changed_budget;

-                tsk_rt(prev->edfsc_params)->container_task->job_params.exec_time +=

+                tsk_rt(entry->scheduled)->job_params.exec_time +=

                         prev->job_params.exec_time - cdomain->scheduled_last_exec_time;

+                if (cdomain->changed_budget)

+                        tsk_rt(prev)->completed = 0;

+                if (budget_exhausted(entry->scheduled)

+                        tsk_rt(entry->scheduled)->completed = 1;

         }

 

         /* (0) Determine state */

@@ -470,9 +519,6 @@ static struct task_struct* edfsc_gschedule(struct task_struct * prev)
                            blocks, out_of_time, np, sleep, preempt,

                            prev->state, signal_pending(prev), is_cont);

 

-        if (is_cont && !sleep && !preempt && !out_of_time)

-                return edfsc_cschedule(tsk_rt(entry->scheduled)->edfsc_params.container_domain, prev);

-

         if (entry->linked && preempt)

                 TRACE_TASK(prev, "will be preempted by %s/%d\n",

                            entry->linked->comm, entry->linked->pid);

@@ -530,6 +576,9 @@ static struct task_struct* edfsc_gschedule(struct task_struct * prev)
                 if (exists)

                         next = prev;

 

+        if (is_container(next))

+                next = edfsc_cschedule(tsk_rt(next)->edfsc_params.container_domain, prev);      

+                

         sched_state_task_picked();

 

         raw_spin_unlock(&g_lock);