Updated logic in utilization tracking

1 files changed, 36 insertions, 38 deletions

diff --git a/litmus/sched_edfsc.c b/litmus/sched_edfsc.c
index e90cfc7b3485..c3c6dddc9eb2 100644
--- a/litmus/sched_edfsc.c
+++ b/litmus/sched_edfsc.c
@@ -30,7 +30,7 @@ typedef struct cont_domain {
         struct task_struct *scheduled; //fixed task
         lt_t scheduled_last_exec_time; //exec_time of the scheduled task when it was last scheduled
         lt_t changed_budget; //change to scheduled task's exec time due to container budget constraints
-        u64 f_util, future_f_util;
+        u64 f_util;
         struct bheap_node *hn;
         struct hrtimer idle_enforcement_timer;
         int timer_armed;
@@ -65,8 +65,8 @@ static cont_domain_t** container_list;
 static rt_domain_t gsched_domain;
 #define g_lock (gsched_domain.ready_lock)
 
-u64 m_util, future_m_util;
-u64 sys_util, future_sys_util;
+u64 m_util;
+u64 sys_util;
 
 #define is_container(task) ((task) && tsk_rt(task)->edfsc_params.domain != NULL && tsk_rt(task)->domain == &gsched_domain)
 #define is_fixed(task) ((task) && tsk_rt(task)->edfsc_params.container_task != NULL)
@@ -84,15 +84,15 @@ struct bheap_node* bheap_node_alloc(int gfp_flags);
 void bheap_node_free(struct bheap_node* hn);
 
 
-/* Do a backwards comparison based on future_f_util so that heavier containers
+/* Do a backwards comparison based on f_util so that heavier containers
  * will come first
  */
 static int container_lower_prio(const void *_a, const void *_b)
 {
         const cont_domain_t *a = (const cont_domain_t *)(_a);
         const cont_domain_t *b = (const cont_domain_t *)(_b);
-        if (a->future_f_util < b->future_f_util) return 1;
-        if (a->future_f_util > b->future_f_util) return -1;
+        if (a->f_util < b->f_util) return 1;
+        if (a->f_util > b->f_util) return -1;
         return 0;
 }
 
@@ -417,16 +417,7 @@ static void g_remove_task(struct task_struct *t)
 {
         BUG_ON(is_container(t));
         m_util -= get_rt_utilization(t);
-        future_m_util -= get_rt_utilization(t);
-        future_sys_util -= get_rt_utilization(t);
-        if (tsk_rt(t)->edfsc_params.move_to) {
-                prepare_for_next_period(t);
-                tsk_rt(t)->domain = (rt_domain_t*)tsk_rt(t)->edfsc_params.move_to;
-                tsk_rt(t)->edfsc_params.container_task = tsk_rt(t)->edfsc_params.move_to->container;
-                requeue(t);
-                tsk_rt(t)->edfsc_params.move_to->f_util += get_rt_utilization(t);
-                tsk_rt(t)->edfsc_params.move_to = NULL;
-        }
+        sys_util -= get_rt_utilization(t);
 }
 
 static void c_remove_task(struct task_struct *t)
@@ -434,29 +425,28 @@ static void c_remove_task(struct task_struct *t)
         struct task_struct* container_task = tsk_rt(t)->edfsc_params.container_task;
         tsk_rt(container_task)->edfsc_params.domain->f_util -=
                 get_rt_utilization(t);
-        tsk_rt(container_task)->edfsc_params.domain->future_f_util -=
-                get_rt_utilization(t);
-        future_sys_util -= get_rt_utilization(t);
+        sys_util -= get_rt_utilization(t);
 }
 
 /**
  * Remove a task from it's current domain and put it in a different domain.
  * Must be called at the greater time of job completion and deadline to respect
- * EDF-sc invariants.
+ * EDF-sc invariants. Can only go from migrating to fixed task.
  */
 static void migrate_task(struct task_struct *t)
 {
         BUG_ON(!t);
-        BUG_ON(is_container(t));
+        BUG_ON(is_container(t) || is_fixed(t));
         BUG_ON(!tsk_rt(t)->edfsc_params.move_to);
 
         if (is_queued(t))
                 remove(tsk_rt(t)->domain, t);
-        if (is_fixed(t)) {
-                c_remove_task(t);
-        } else {
-                g_remove_task(t);
-        }
+        // Remove the util of the "fake reservation task"(specified by the paper) from the system
+        sys_util -= get_rt_utilization(t);
+        prepare_for_next_period(t);
+        tsk_rt(t)->domain = (rt_domain_t*)tsk_rt(t)->edfsc_params.move_to;
+        tsk_rt(t)->edfsc_params.container_task = tsk_rt(t)->edfsc_params.move_to->container;
+        requeue(t);
         tsk_rt(t)->edfsc_params.move_to = NULL;
 }
 
@@ -918,7 +908,7 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer)
                 t = task_of_list_node(it);
                 if (u_extra >= get_rt_utilization(t)) {
                         for (i = 0; i < num_cpus; i++) {
-                                u64 leftover = to_fp(1) - container_domains[i].future_f_util
+                                u64 leftover = to_fp(1) - container_domains[i].f_util
                                         - get_rt_utilization(t);
                                 if (leftover >= 0) {
                                         container = &(container_domains[i]);
@@ -930,17 +920,14 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer)
                                 tsk_rt(t)->domain = (rt_domain_t*)container;
                                 tsk_rt(t)->edfsc_params.container_task = container->container;
                                 container->f_util += get_rt_utilization(t);
-                                container->future_f_util += get_rt_utilization(t);
                         } else {
                                 tsk_rt(t)->domain = &gsched_domain;
                                 tsk_rt(t)->edfsc_params.container_task = NULL;
                                 m_util += get_rt_utilization(t);
-                                future_m_util += get_rt_utilization(t);
                                 //list_add(&tsk_rt(t)->edfsc_params.qnode, &migrating_tasks);
                                 list_add(&t->edfsc_qnode, &migrating_tasks);
                         }
                         sys_util += get_rt_utilization(t);
-                        future_sys_util += get_rt_utilization(t);
                         need_reweight = 1;
                         // Setup the release time for the first job to be now
                         release_at(t, litmus_clock());
@@ -965,25 +952,35 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer)
         // migrating tasks and potentially all the containers every period for a
         // best-case Omega(m) and worst-case O(m^2) work---only once the scheduler
         // is actually working
+        // According to the paper, when we migrate, we must reserve space in the container
+        // We do this by adding a fake task that ultimately doesn't release any jobs
+        // This is represented here by adding the utilization to sys_util
+        // which will be subtracted when the migrating task is actually changed to fixed
         list_for_each(it, &migrating_tasks) {
                 struct task_struct* t = task_of_list_node(it);
+                // Although technically selecting the migrating tasks to be moved into containers
+                // doesn't change m_util and the container's f_util until after the move,
+                // but since the move is guaranteed to happen before the next container_boundary
+                // where we check all the utilization stuff, it's fine to account for it now
                 if (!(tsk_rt(t)->edfsc_params.move_to) && !is_released(t, now)
                                 && get_deadline(t) < get_deadline(&container_tasks[0]) + get_rt_period(&container_tasks[0])) {
                         tsk_rt(t)->edfsc_params.move_to = NULL;
 
                         container = NULL;
                         for (i = 0; i < num_cpus; i++) {
-                                u64 leftover = to_fp(1) - container_domains[i].future_f_util
+                                u64 leftover = to_fp(1) - container_domains[i].f_util
                                         - get_rt_utilization(t);
-                                if (leftover >= 0) {
+                                u_extra = to_fp(num_cpus) - sys_util;
+                                if (leftover >= to_fp(0) && u_extra >= get_rt_utilization(t)) {
                                         container = &(container_domains[i]);
                                         break;
                                 }
                         }
 
                         if (container) {
-                                container->future_f_util += get_rt_utilization(t);
-                                future_sys_util += get_rt_utilization(t);
+                                container->f_util += get_rt_utilization(t);
+                                m_util -= get_rt_utilization(t);
+                                sys_util += get_rt_utilization(t);
                                 tsk_rt(t)->edfsc_params.move_to = container;
                                 need_reweight = 1;
                         }
@@ -995,12 +992,12 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer)
                 int remaining;
                 // Sort containers by the utilization of their fixed tasks
                 sort(container_list, num_cpus, sizeof(cont_domain_t *), &container_lower_prio, NULL);
-                u_extra = to_fp(num_cpus) - future_sys_util;
+                u_extra = to_fp(num_cpus) - sys_util;
                 // Fully provision all the container tasks we can
-                for (i = 0; i < num_cpus && u_extra >= to_fp(1) - container_list[i]->future_f_util; i++) {
+                for (i = 0; i < num_cpus && u_extra >= to_fp(1) - container_list[i]->f_util; i++) {
                         struct task_struct* t = container_list[i]->container;
                         tsk_rt(t)->task_params.utilization = to_fp(1);
-                        u_extra -= to_fp(1) - container_list[i]->future_f_util;
+                        u_extra -= to_fp(1) - container_list[i]->f_util;
                 }
                 // Split the extra capacity between the remaining container tasks
                 // XXX this is actually dangerous as hell, right?  Since overheads are
@@ -1016,7 +1013,7 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer)
                 remaining = num_cpus - i;
                 for (; i < num_cpus; i++) {
                         struct task_struct* t = container_list[i]->container;
-                        tsk_rt(t)->task_params.utilization = container_list[i]->future_f_util + u_extra / remaining;
+                        tsk_rt(t)->task_params.utilization = container_list[i]->f_util + u_extra / remaining;
                 }
         }
 
@@ -1053,6 +1050,7 @@ static enum hrtimer_restart task_deadline_callback(struct hrtimer* timer) {
         struct task_struct *t = container_of(timer, struct task_struct, edfsc_deadline_timer);
 
         BUG_ON(is_container(t));
+        // This is true only if set to be migrating from container_boundary
         if (tsk_rt(t)->edfsc_params.move_to) {
                 // Migrate here if the task is not late, otherwise migrate in job_complete
                 if (!is_released(t, litmus_clock()) || budget_exhausted(t))