[Xen-devel] [PATCH v2] Modified RTDS scheduler to use an event-driven model instead of polling.

[Dagaen Golomb <dgolomb@xxxxxxxxxxxxxx>]

To do this, we create a new list that holds, for each
vcpu, the time least into the future that it may need to be
rescheduled. The scheduler chooses the lowest time off of this
list and waits until the specified time instead of running every
1 ms as it did before.

Signed-off-by: Dagaen Golomb <dgolomb@xxxxxxxxxxxxxx>
Signed-off-by: Meng Xu <mengxu@xxxxxxxxxxxxx>
---
 xen/common/sched_rt.c |  100 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 93 insertions(+), 7 deletions(-)

diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
index 4372486..cce3446 100644
--- a/xen/common/sched_rt.c
+++ b/xen/common/sched_rt.c
@@ -4,6 +4,7 @@
  *
  * by Sisu Xi, 2013, Washington University in Saint Louis
  * and Meng Xu, 2014, University of Pennsylvania
+ * and Dagaen Golomb, 2015, University of Pennsylvania
  *
  * based on the code of credit Scheduler
  */
@@ -152,6 +153,8 @@ struct rt_private {
     struct list_head sdom;      /* list of availalbe domains, used for dump */
     struct list_head runq;      /* ordered list of runnable vcpus */
     struct list_head depletedq; /* unordered list of depleted vcpus */
+    struct timer replenishment_timer;
+    unsigned NUM_CPUS;
     cpumask_t tickled;          /* cpus been tickled */
 };
 
@@ -178,6 +181,8 @@ struct rt_vcpu {
     unsigned flags;             /* mark __RTDS_scheduled, etc.. */
 };
 
+static void runq_tickle(const struct scheduler *, struct rt_vcpu *);
+
 /*
  * Domain
  */
@@ -391,13 +396,19 @@ __q_remove(struct rt_vcpu *svc)
  * Insert svc with budget in RunQ according to EDF:
  * vcpus with smaller deadlines go first.
  * Insert svc without budget in DepletedQ unsorted;
+ *
+ * Returns the position, 1-indexed, of where the item was inserted.
+ * Returns a positive index if placed on runq, and a negative index (the index
+ *   in the depletedq * -1) if placed on the depletedq
  */
-static void
+static int
 __runq_insert(const struct scheduler *ops, struct rt_vcpu *svc)
 {
     struct rt_private *prv = rt_priv(ops);
     struct list_head *runq = rt_runq(ops);
+    struct list_head *depletedq = rt_depletedq(ops);
     struct list_head *iter;
+    unsigned inserted_index = 1;
 
     ASSERT( spin_is_locked(&prv->lock) );
 
@@ -411,15 +422,77 @@ __runq_insert(const struct scheduler *ops, struct rt_vcpu 
*svc)
             struct rt_vcpu * iter_svc = __q_elem(iter);
             if ( svc->cur_deadline <= iter_svc->cur_deadline )
                     break;
+            else
+                ++inserted_index;
          }
         list_add_tail(&svc->q_elem, iter);
+        return inserted_index;
     }
     else
     {
-        list_add(&svc->q_elem, &prv->depletedq);
+        // If we are inserting into previously empty depletedq, rearm
+        //   rearm replenish timer. It will handle further scheduling until
+        //   the depletedq is empty again (if ever)
+        if( list_empty(depletedq) )
+            set_timer( &prv->replenishment_timer, svc->cur_deadline );
+
+        list_for_each(iter, depletedq)
+        {
+            struct rt_vcpu * iter_svc = __q_elem(iter);
+            if ( svc->cur_deadline <= iter_svc->cur_deadline )
+                break;
+            else
+                ++inserted_index;
+         }
+        list_add_tail(&svc->q_elem, iter);
+        return -inserted_index;
     }
 }
 
+static void replenishment_handler(void* data)
+{
+    const struct scheduler *ops = data;
+    struct rt_private *prv = rt_priv(ops);
+    struct list_head *depletedq = rt_depletedq(ops);
+    struct list_head *iter;
+    struct list_head *tmp;
+    struct rt_vcpu *svc = NULL;
+    s_time_t now = NOW();
+    int new_position = 0;
+    unsigned long flags;
+
+    spin_lock_irqsave(&prv->lock, flags);
+
+    // Replenish the vCPU that triggered this, and resort it into runq
+    list_for_each_safe(iter, tmp, depletedq)
+    {
+        svc = __q_elem(iter);
+        if ( now >= svc->cur_deadline )
+        {
+            rt_update_deadline(now, svc);
+            __q_remove(svc); /* remove from depleted queue */
+            new_position = __runq_insert(ops, svc); /* add to runq */
+        }
+        else break; // leave list_for_each_safe
+    }
+
+    // If we become one of top [# CPUs] in the runq, tickle it
+    // TODO: make this work when multiple tickles are required
+    if ( new_position > 0 && new_position <= prv->NUM_CPUS )
+        runq_tickle(ops, svc);
+
+    // Use first item on deletedq to schedule next replenishment.
+    // If no replenishments are pending, disable timer for now
+    if( !list_empty(depletedq) )
+    {
+        struct rt_vcpu * soonest_to_replenish = __q_elem(depletedq->next);
+        set_timer( &prv->replenishment_timer,
+                   soonest_to_replenish->cur_deadline );
+    }
+
+    spin_unlock_irqrestore(&prv->lock, flags);
+}
+
 /*
  * Init/Free related code
  */
@@ -427,6 +500,7 @@ static int
 rt_init(struct scheduler *ops)
 {
     struct rt_private *prv = xzalloc(struct rt_private);
+    int cpu = 0;
 
     printk("Initializing RTDS scheduler\n"
            "WARNING: This is experimental software in development.\n"
@@ -450,6 +524,15 @@ rt_init(struct scheduler *ops)
     INIT_LIST_HEAD(&prv->runq);
     INIT_LIST_HEAD(&prv->depletedq);
 
+    // Replenishment timer, for now always on CPU 0
+    init_timer(&prv->replenishment_timer, replenishment_handler, ops, 0);
+    // Calculate number of pCPUs present.
+    // Note: assumes does not change online.
+    for_each_present_cpu(cpu)
+    {
+        ++(prv->NUM_CPUS);
+    }
+    
     cpumask_clear(&prv->tickled);
 
     ops->sched_data = prv;
@@ -466,6 +549,8 @@ rt_deinit(const struct scheduler *ops)
 {
     struct rt_private *prv = rt_priv(ops);
 
+    kill_timer(&prv->replenishment_timer);
+
     ASSERT( _cpumask_scratch && nr_rt_ops > 0 );
 
     if ( (--nr_rt_ops) == 0 )
@@ -653,8 +738,7 @@ rt_vcpu_remove(const struct scheduler *ops, struct vcpu *vc)
     BUG_ON( sdom == NULL );
 
     lock = vcpu_schedule_lock_irq(vc);
-    if ( __vcpu_on_q(svc) )
-        __q_remove(svc);
+    __q_remove(svc);
     vcpu_schedule_unlock_irq(lock, vc);
 
     if ( !is_idle_vcpu(vc) )
@@ -838,6 +922,7 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
 {
     const int cpu = smp_processor_id();
     struct rt_private *prv = rt_priv(ops);
+    struct list_head *runq = rt_runq(ops);
     struct rt_vcpu *const scurr = rt_vcpu(current);
     struct rt_vcpu *snext = NULL;
     struct task_slice ret = { .migrated = 0 };
@@ -848,8 +933,6 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
     /* burn_budget would return for IDLE VCPU */
     burn_budget(ops, scurr, now);
 
-    __repl_update(ops, now);
-
     if ( tasklet_work_scheduled )
     {
         snext = rt_vcpu(idle_vcpu[cpu]);
@@ -889,7 +972,10 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
         }
     }
 
-    ret.time = MIN(snext->budget, MAX_SCHEDULE); /* sched quantum */
+    /* Use minimum from runq */
+    ret.time = MAX_SCHEDULE;
+    if( !list_empty(runq) )
+        ret.time = __q_elem(runq->next)->cur_deadline;
     ret.task = snext->vcpu;
 
     /* TRACE */
-- 
1.7.9.5


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel