adaptive: increase+decrease goodness

Complete reweighting rules.

1 files changed, 151 insertions, 30 deletions

diff --git a/kernel/sched_adaptive.c b/kernel/sched_adaptive.c
index eab569b04e..de58c0b414 100644
--- a/kernel/sched_adaptive.c
+++ b/kernel/sched_adaptive.c
@@ -11,7 +11,7 @@
  * what is going on here.
  *
  * Block et al., "Feedback-Controlled Adaptive Multiprocessor Real-Time
- * Systems", 2008.
+ * Systems", submitted to RTAS 2008.
  */
 
 #include <linux/percpu.h>
@@ -93,11 +93,8 @@
  * __take_ready).
  */
 
-/* TODO: 
- *      - export weight error on task completion
- *      - 
- */
-
+static void unlink(struct task_struct* t);
+static void adaptive_job_arrival(struct task_struct* task);
 
 /* cpu_entry_t - maintain the linked and scheduled state
  */
@@ -140,6 +137,10 @@ static fp_t	task_error_threshold;
 /* optimizer time snapshot */
 jiffie_t        opt_time;
 
+/* Delayed weight increase notification list.
+ * This list gets clobbered on each optimizer run.
+ */
+static LIST_HEAD(adaptive_inc_list);
 
 /******************************************************************************/
 /*                             SORT ORDERS                                    */
@@ -184,22 +185,137 @@ static void set_service_level(struct task_struct* t, unsigned int level)
         t->rt_param.basic_params.period = new->period;    
         t->rt_param.basic_params.exec_cost = _round(_mul(new->weight, 
                                                          FP(new->period)));
+
+        /* TODO: post signal! */
+
         sched_trace_service_level_change(t);
         TRACE_TASK(t, "service level %u activated\n", level);
 }
 
-/* t is eligible for reweighting now */
-static void enact_weight_change(struct task_struct* t)
+/* call this _before_ updating deadline and release of t */
+static void update_weight_estimate(struct task_struct* t)
 {
-       
+        fp_t nw;
+        jiffie_t sl_period, exec_time;
+        
+        nw        = t->rt_param.opt_nw;
+        exec_time = t->rt_param.times.exec_time;
+        sl_period = get_sl(t, get_opt_sl(t)).period;
+        
+        t->rt_param.predictor_state.estimate =
+                _div( _max(_mul(nw, FP(sl_period)), FP(exec_time)),
+                      FP(get_deadline(t) - get_last_release(t)));
 }
 
-/* t has to weight some, it must be halted */
-static void prepare_delayed_weight_change(struct task_struct* t)
+
+static void decrease_weight(struct task_struct* t)
 {
+        fp_t ow, nw;
+        jiffie_t last, period, delay;
+
+        ow = get_sl(t, get_cur_sl(t)).weight;
+        nw = get_sl(t, get_opt_sl(t)).weight;
+        last = t->rt_param.times.last_release;  
+        period = reweighted_period(ow, nw, t->rt_param.times.exec_time,
+                                   t->rt_param.times.deadline, last);
+                
+        /* necessary delay has already been computed by optimizer */
+        delay = t->rt_param.opt_change;
         
+        update_weight_estimate(t);
+
+        if (!delay)
+                t->rt_param.times.last_release = opt_time;
+        t->rt_param.times.release      = opt_time + delay;
+        t->rt_param.times.deadline     = opt_time + delay + period;
+
+        set_service_level(t, get_opt_sl(t));
+
+        /* take out of queue/link structure */
+        unlink(t);
+        /* present as a new job */
+        adaptive_job_arrival(t);                                        
+}
+
+
+static void increase_weight(struct task_struct* t)
+{
+        fp_t ow, nw;
+        jiffie_t last, period, delay;
+
+        ow = get_sl(t, get_cur_sl(t)).weight;
+        nw = get_sl(t, get_opt_sl(t)).weight;
+        last = t->rt_param.times.last_release;  
+        period = reweighted_period(ow, nw, t->rt_param.times.exec_time,
+                                   t->rt_param.times.deadline, last);
+
+        if (t->rt_param.opt_change == 0) {
+                /* can be enacted now */
+                if (is_under_allocated(t) || 
+                    time_before(opt_time + period, get_deadline(t)))
+                        /* do it now */
+                        delay = 0;
+                else {
+                        if (is_under_allocated(t)) {
+                                t->rt_param.opt_change += opt_time;
+                                /* The next job release will notice that opt !=
+                                 * sl and initiate a weight change.
+                                 */
+                                return;
+                        } else
+                                /* nope, wait for equal point */
+                                delay = inc_equal_point_delay(t);
+                }
+
+                update_weight_estimate(t);
+
+                if (!delay)
+                        t->rt_param.times.last_release = opt_time;
+                t->rt_param.times.release      = opt_time + delay;
+                t->rt_param.times.deadline     = opt_time + delay + period;
+                
+                set_service_level(t, get_opt_sl(t));
+                
+                /* take out of queue/link structure */
+                unlink(t);
+                /* present as a new job */
+                adaptive_job_arrival(t);                                        
+                                
+        } else {
+                /* must wait until capacity is released */
+                t->rt_param.opt_change += opt_time;
+                list_insert(&t->rt_param.opt_list, &adaptive_inc_list, 
+                            by_enactment_time);
+        }
 }
 
+static void delayed_increase_weight(void)
+{
+        struct list_head *p, *extra;
+        struct task_struct* t;
+
+        opt_time = jiffies;
+        list_for_each_safe(p, extra, &adaptive_inc_list) {
+                t = list_entry(p, struct task_struct, rt_param.opt_list);
+                if (time_before_eq(t->rt_param.opt_change, opt_time)) {
+                        list_del(p);
+                        /* prevent recursion */
+                        t->rt_param.opt_change = 0;
+                        /* this takes care of everything */
+                        increase_weight(t);
+                } else                  
+                        /* list is sorted */
+                        break;
+        }
+}
+
+static void change_weight(struct task_struct* t)
+{
+        if (get_cur_sl(t) < get_opt_sl(t))
+                increase_weight(t);
+        else
+                decrease_weight(t);
+}
 
 /******************************************************************************/
 /*                               OPTIMIZER                                    */
@@ -293,7 +409,7 @@ void adaptive_optimize(void)
                 list_del(p);
                 if (t->rt_param.opt_level < get_cur_sl(t)) {
                         list_add(p, &dec);
-                        t->rt_param.opt_change = decrease_enactment_time(t);
+                        t->rt_param.opt_change = decrease_delay(t);
                 } else if (t->rt_param.opt_level > get_cur_sl(t)) {
                         list_add(p, &inc);
                         t->rt_param.opt_change = 0;
@@ -378,18 +494,11 @@ void adaptive_optimize(void)
          *    delayed. Also convert change fields to actual timestamp for to be
          *    nice to the scheduler_tick().
          */
-        list_for_each_safe(p, extra, &list) {
-                
+        INIT_LIST_HEAD(&adaptive_inc_list);
+        list_for_each_safe(p, extra, &list) {           
                 t  = list_entry(p, struct task_struct, rt_param.opt_list);
                 list_del(p);
-                if (t->rt_param.opt_change == 0)
-                        /* enact change now */
-                        enact_weight_change(t);
-                else {
-                        /* fixup: make it a real timestamp */
-                        t->rt_param.opt_change += opt_time;
-                        prepare_delayed_weight_change(t);
-                }
+                change_weight(t);
         }
 
         last_optimizer_run = jiffies;
@@ -471,7 +580,7 @@ static noinline void link_task_to_cpu(struct task_struct* linked,
 /* unlink - Make sure a task is not linked any longer to an entry
  *          where it was linked before. Must hold adaptive_lock.
  */
-static noinline void unlink(struct task_struct* t)
+static void unlink(struct task_struct* t)
 {
         cpu_entry_t *entry;
 
@@ -555,7 +664,7 @@ static noinline void requeue(struct task_struct* task)
 }
 
 /* adaptive_job_arrival: task is either resumed or released */
-static noinline void adaptive_job_arrival(struct task_struct* task)
+static void adaptive_job_arrival(struct task_struct* task)
 {
         cpu_entry_t* last;
 
@@ -594,6 +703,19 @@ static noinline  void adaptive_release_jobs(void)
                         set_rt_flags(queued, RT_F_RUNNING);
                         queued->rt_param.times.last_release = 
                                 queued->rt_param.times.release;
+                        
+                        /* check for delayed weight increase */
+                        if (get_opt_sl(queued) != get_cur_sl(queued) &&
+                            time_before_eq(queued->rt_param.opt_change, jiffies)) {
+                                opt_time = jiffies;
+                                set_service_level(queued, get_opt_sl(queued));
+                                queued->rt_param.times.deadline = 
+                                        get_last_release(queued) + 
+                                        get_rt_period(queued);
+                                queued->rt_param.predictor_state.estimate = 
+                                        queued->rt_param.opt_nw;
+                        }
+
                         sched_trace_job_release(queued);
                         adaptive_job_arrival(queued);
                 } 
@@ -629,14 +751,12 @@ static reschedule_check_t adaptive_scheduler_tick(void)
                 if (time_before_eq(last_optimizer_run + optimizer_period, jiffies)) {
                         TRACE("adaptive: optimizing due to period threshold\n");
                         adaptive_optimize();
-                } else if (is_realtime(t) && 
-                         get_cur_sl(t) != get_opt_sl(t) &&
-                         time_before_eq(t->rt_param.opt_change, jiffies)) {
-                        opt_time = jiffies;
-                        enact_weight_change(t);
                 }
 
-                /* (2) try to release pending jobs */
+                /* (2) enact delayed weight increases */
+                delayed_increase_weight();
+
+                /* (3) try to release pending jobs */
                 adaptive_release_jobs();
 
                 /* we don't need to check linked != scheduled since
@@ -665,6 +785,7 @@ static noinline void job_completion(struct task_struct *t)
 
         actual_weight = _frac(t->rt_param.times.exec_time, 
                               t->rt_param.basic_params.period);
+        sched_trace_weight_error(t, actual_weight);
         old_estimate = get_est_weight(t);
         update_estimate(&t->rt_param.predictor_state, actual_weight, 
                         fc_a, fc_b);