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

[Meng Xu <xumengpanda@xxxxxxxxx>]

Hi Dario,

[Since I have commented on this thread in previous email, I just
top-post it for reminder.]

Just in case, this email is out of your radar... :-)

I had discussed this patch with Dagaen as shown in
http://www.gossamer-threads.com/lists/xen/devel/386651

You don't need any detailed comment for this patch. We only need your
confirmation if this is in the correct direction and there is not
"serious" design issue in this implementation.

Once we are confirmed with that, we can send the next version with the
minor stuffs (such as coding style) done soon.


2015-06-27 12:46 GMT-07:00 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
>



Thanks,

Meng


-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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