* [PATCH 0/1] Improved RTDS scheduler
@ 2015-12-31 9:45 Tianyang Chen
2015-12-31 9:45 ` [PATCH 1/1] " Tianyang Chen
0 siblings, 1 reply; 7+ messages in thread
From: Tianyang Chen @ 2015-12-31 9:45 UTC (permalink / raw)
To: xen-devel
Cc: ian.campbell, dario.faggioli, Tianyang Chen, ian.jackson,
george.dunlap, Meng Xu, jbeulich, Dagaen Golomb
Current RTDS scheduler is time driven and is called every 1ms. During each scheduler call, the repl_update() scans both runq and depeletedq, which might not be necessary every 1ms.
Since each vcpu is implemented as a deferable server, budget is preserved during its period and refilled in the next. It is not necessary to check every 1ms as the current design does. The replenishment is needed at the nearest next period(nearest current_deadline) of all runnable vcpus.
This improved design tries to reduce scheduler invocation by using an event driven approach;rt_schedule() will return a value when the scheduler needs to be called next time. In addition, the sched_rt will have one dedicated timer to handle replenishment when necessary. In other words, the budget replenishment and scheduler decision(rt_schedule) are separated.
Based on previous decision between Dario, Dagaen and Meng, the improved design can be implemented/modified as follows:
rt_schedule(): picks the highest runnable vcpu based on cpu affinity and ret.time will be passed to schedule().
rt_vcpu_wake(): when a vcpu is awake, it tickles instead of picking one from runq.
rt_context_saved(): when context switching is finished, the preempted vcpu will be put back into the runq. Picking from runq and tickling are removed.
repl_handler(): a timer handler which is reprogrammed to fire at the nearest vcpu deadline to replenish vcpus on depeletedq while keeping the runq sorted. When the replenishment is done, each replenished vcpu in the runq should tickle a pcpu to see if it needs to preempt any running vcpus.
An extra field to record the last replenishing time will be added.
schedule.c SCHEDULE_SOFTIRQ:
rt_schedule():
[spin_lock]
burn_budget(scurr)
snext = runq_pick()
[spin_unlock]
sched_rt.c TIMER_SOFTIRQ
replenishment_timer_handler()
[spin_lock]
<for_each_depleted_vcpu(i, i.repl_time < NOW()) {
replenish(i)
runq_tickle(i)
}>
program_timer()
[spin_lock]
The transient behavior should be noted. It happens between a vcpu tickles and a pcpu actually picks it. As previous discussions, this is unavoidable.
Previous discussions:
http://lists.xenproject.org/archives/html/xen-devel/2015-06/msg02629.html
Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu>
Signed-off-by: Meng Xu <mengxu@cis.upenn.edu>
Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu>
*** BLURB HERE ***
Tianyang Chen (1):
Improved RTDS scheduler
0000-cover-letter.patch | 16 +++
0001-Improved-RTDS-scheduler.patch | 280 ++++++++++++++++++++++++++++++++++++
bak | 62 ++++++++
xen/common/sched_rt.c | 159 +++++++++++---------
4 files changed, 453 insertions(+), 64 deletions(-)
create mode 100644 0000-cover-letter.patch
create mode 100644 0001-Improved-RTDS-scheduler.patch
create mode 100644 bak
--
1.7.9.5
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH 1/1] Improved RTDS scheduler 2015-12-31 9:45 [PATCH 0/1] Improved RTDS scheduler Tianyang Chen @ 2015-12-31 9:45 ` Tianyang Chen 2016-01-04 11:42 ` Ian Campbell 0 siblings, 1 reply; 7+ messages in thread From: Tianyang Chen @ 2015-12-31 9:45 UTC (permalink / raw) To: xen-devel Cc: ian.campbell, dario.faggioli, Tianyang Chen, ian.jackson, george.dunlap, Meng Xu, jbeulich, Dagaen Golomb Budget replenishment is now handled by a dedicated timer which is triggered at the most imminent release time of all runnable vcpus. Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> --- 0000-cover-letter.patch | 16 +++ 0001-Improved-RTDS-scheduler.patch | 280 ++++++++++++++++++++++++++++++++++++ bak | 62 ++++++++ xen/common/sched_rt.c | 159 +++++++++++--------- 4 files changed, 453 insertions(+), 64 deletions(-) create mode 100644 0000-cover-letter.patch create mode 100644 0001-Improved-RTDS-scheduler.patch create mode 100644 bak diff --git a/0000-cover-letter.patch b/0000-cover-letter.patch new file mode 100644 index 0000000..f5aca91 --- /dev/null +++ b/0000-cover-letter.patch @@ -0,0 +1,16 @@ +From 25ca27ea281885eb9873244a11f08e6987efb36e Mon Sep 17 00:00:00 2001 +From: Tianyang Chen <tiche@seas.upenn.edu> +Date: Thu, 31 Dec 2015 04:05:21 -0500 +Subject: [PATCH] *** SUBJECT HERE *** + +*** BLURB HERE *** + +Tianyang Chen (1): + Improved RTDS scheduler + + xen/common/sched_rt.c | 159 +++++++++++++++++++++++++++++-------------------- + 1 file changed, 95 insertions(+), 64 deletions(-) + +-- +1.7.9.5 + diff --git a/0001-Improved-RTDS-scheduler.patch b/0001-Improved-RTDS-scheduler.patch new file mode 100644 index 0000000..02cb1f7 --- /dev/null +++ b/0001-Improved-RTDS-scheduler.patch @@ -0,0 +1,280 @@ +From 25ca27ea281885eb9873244a11f08e6987efb36e Mon Sep 17 00:00:00 2001 +From: Tianyang Chen <tianyangpenn@gmail.com> +Date: Thu, 31 Dec 2015 01:55:19 -0500 +Subject: [PATCH] Improved RTDS scheduler + +Budget replenishment is now handled by a dedicated timer which is +triggered at the most imminent release time of all runnable vcpus. + +Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> +Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> +Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> +--- + xen/common/sched_rt.c | 159 +++++++++++++++++++++++++++++-------------------- + 1 file changed, 95 insertions(+), 64 deletions(-) + +diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c +index 4372486..d522272 100644 +--- a/xen/common/sched_rt.c ++++ b/xen/common/sched_rt.c +@@ -16,6 +16,7 @@ + #include <xen/delay.h> + #include <xen/event.h> + #include <xen/time.h> ++#include <xen/timer.h> + #include <xen/perfc.h> + #include <xen/sched-if.h> + #include <xen/softirq.h> +@@ -147,6 +148,16 @@ static unsigned int nr_rt_ops; + * Global lock is referenced by schedule_data.schedule_lock from all + * physical cpus. It can be grabbed via vcpu_schedule_lock_irq() + */ ++ ++/* dedicated timer for replenishment */ ++static struct timer repl_timer; ++ ++/* controls when to first start the timer*/ ++static int timer_started; ++ ++/* handler for the replenishment timer */ ++static void repl_handler(void *data); ++ + struct rt_private { + spinlock_t lock; /* the global coarse grand lock */ + struct list_head sdom; /* list of availalbe domains, used for dump */ +@@ -426,6 +437,7 @@ __runq_insert(const struct scheduler *ops, struct rt_vcpu *svc) + static int + rt_init(struct scheduler *ops) + { ++ const int cpu = smp_processor_id(); + struct rt_private *prv = xzalloc(struct rt_private); + + printk("Initializing RTDS scheduler\n" +@@ -454,6 +466,8 @@ rt_init(struct scheduler *ops) + + ops->sched_data = prv; + ++ init_timer(&repl_timer, repl_handler, ops, 0); ++ + return 0; + + no_mem: +@@ -473,6 +487,9 @@ rt_deinit(const struct scheduler *ops) + xfree(_cpumask_scratch); + _cpumask_scratch = NULL; + } ++ ++ kill_timer(&repl_timer); ++ + xfree(prv); + } + +@@ -635,6 +652,13 @@ rt_vcpu_insert(const struct scheduler *ops, struct vcpu *vc) + + /* add rt_vcpu svc to scheduler-specific vcpu list of the dom */ + list_add_tail(&svc->sdom_elem, &svc->sdom->vcpu); ++ ++ if(!timer_started) ++ { ++ /* the first vcpu starts the timer for the first time*/ ++ timer_started = 1; ++ set_timer(&repl_timer,svc->cur_deadline); ++ } + } + + /* +@@ -792,44 +816,6 @@ __runq_pick(const struct scheduler *ops, const cpumask_t *mask) + } + + /* +- * Update vcpu's budget and +- * sort runq by insert the modifed vcpu back to runq +- * lock is grabbed before calling this function +- */ +-static void +-__repl_update(const struct scheduler *ops, s_time_t now) +-{ +- struct list_head *runq = rt_runq(ops); +- struct list_head *depletedq = rt_depletedq(ops); +- struct list_head *iter; +- struct list_head *tmp; +- struct rt_vcpu *svc = NULL; +- +- list_for_each_safe(iter, tmp, runq) +- { +- svc = __q_elem(iter); +- if ( now < svc->cur_deadline ) +- break; +- +- rt_update_deadline(now, svc); +- /* reinsert the vcpu if its deadline is updated */ +- __q_remove(svc); +- __runq_insert(ops, svc); +- } +- +- 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 */ +- __runq_insert(ops, svc); /* add to runq */ +- } +- } +-} +- +-/* + * schedule function for rt scheduler. + * The lock is already grabbed in schedule.c, no need to lock here + */ +@@ -848,7 +834,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 ) + { +@@ -889,7 +874,7 @@ rt_schedule(const struct scheduler *ops, s_time_t now, bool_t tasklet_work_sched + } + } + +- ret.time = MIN(snext->budget, MAX_SCHEDULE); /* sched quantum */ ++ ret.time = snext->budget; /* invoke the scheduler next time */ + ret.task = snext->vcpu; + + /* TRACE */ +@@ -1033,10 +1018,6 @@ rt_vcpu_wake(const struct scheduler *ops, struct vcpu *vc) + { + struct rt_vcpu * const svc = rt_vcpu(vc); + s_time_t now = NOW(); +- struct rt_private *prv = rt_priv(ops); +- struct rt_vcpu *snext = NULL; /* highest priority on RunQ */ +- struct rt_dom *sdom = NULL; +- cpumask_t *online; + + BUG_ON( is_idle_vcpu(vc) ); + +@@ -1074,14 +1055,7 @@ rt_vcpu_wake(const struct scheduler *ops, struct vcpu *vc) + /* insert svc to runq/depletedq because svc is not in queue now */ + __runq_insert(ops, svc); + +- __repl_update(ops, now); +- +- ASSERT(!list_empty(&prv->sdom)); +- sdom = list_entry(prv->sdom.next, struct rt_dom, sdom_elem); +- online = cpupool_scheduler_cpumask(sdom->dom->cpupool); +- snext = __runq_pick(ops, online); /* pick snext from ALL valid cpus */ +- +- runq_tickle(ops, snext); ++ runq_tickle(ops, svc); + + return; + } +@@ -1094,10 +1068,6 @@ static void + rt_context_saved(const struct scheduler *ops, struct vcpu *vc) + { + struct rt_vcpu *svc = rt_vcpu(vc); +- struct rt_vcpu *snext = NULL; +- struct rt_dom *sdom = NULL; +- struct rt_private *prv = rt_priv(ops); +- cpumask_t *online; + spinlock_t *lock = vcpu_schedule_lock_irq(vc); + + clear_bit(__RTDS_scheduled, &svc->flags); +@@ -1108,15 +1078,8 @@ rt_context_saved(const struct scheduler *ops, struct vcpu *vc) + if ( test_and_clear_bit(__RTDS_delayed_runq_add, &svc->flags) && + likely(vcpu_runnable(vc)) ) + { ++ /* only insert the pre-empted vcpu back*/ + __runq_insert(ops, svc); +- __repl_update(ops, NOW()); +- +- ASSERT(!list_empty(&prv->sdom)); +- sdom = list_entry(prv->sdom.next, struct rt_dom, sdom_elem); +- online = cpupool_scheduler_cpumask(sdom->dom->cpupool); +- snext = __runq_pick(ops, online); /* pick snext from ALL cpus */ +- +- runq_tickle(ops, snext); + } + out: + vcpu_schedule_unlock_irq(lock, vc); +@@ -1167,6 +1130,74 @@ rt_dom_cntl( + return rc; + } + ++static void repl_handler(void *data){ ++ unsigned long flags; ++ s_time_t now = NOW(); ++ s_time_t min_repl = LONG_MAX; /* max time used in comparison*/ ++ struct scheduler *ops = data; ++ 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; ++ struct list_head *tmp; ++ struct rt_vcpu *svc = NULL; ++ ++ spin_lock_irqsave(&prv->lock,flags); ++ ++ stop_timer(&repl_timer); ++ ++ list_for_each_safe(iter, tmp, runq) ++ { ++ svc = __q_elem(iter); ++ if ( now < svc->cur_deadline ) ++ break; ++ rt_update_deadline(now, svc); ++ /* scan the runq to find the min release time ++ * this happens when vcpus on runq miss deadline ++ */ ++ if( min_repl> svc->cur_deadline ) ++ { ++ min_repl = svc->cur_deadline; ++ } ++ /* reinsert the vcpu if its deadline is updated */ ++ __q_remove(svc); ++ __runq_insert(ops, svc); ++ } ++ ++ list_for_each_safe(iter, tmp, depletedq) ++ { ++ svc = __q_elem(iter); ++ if ( now >= svc->cur_deadline ) ++ { ++ rt_update_deadline(now, svc); ++ ++ /* scan the delp_q to find the minimal release time */ ++ if(min_repl > svc->cur_deadline) ++ { ++ min_repl = svc->cur_deadline; ++ } ++ __q_remove(svc); ++ __runq_insert(ops, svc); ++ runq_tickle(ops, svc); ++ } ++ } ++ ++ /* if timer was triggered but none of the vcpus ++ * need to be refilled, set the timer to be the ++ * default period + now ++ */ ++ if(min_repl == LONG_MAX) ++ { ++ set_timer(&repl_timer, now + RTDS_DEFAULT_PERIOD); ++ } ++ else ++ { ++ /* reprogram the timer using the most imminent release time*/ ++ set_timer(&repl_timer, min_repl); ++ } ++ spin_unlock_irqrestore(&prv->lock,flags); ++} ++ + static struct rt_private _rt_priv; + + const struct scheduler sched_rtds_def = { +-- +1.7.9.5 + diff --git a/bak b/bak new file mode 100644 index 0000000..fa7b197 --- /dev/null +++ b/bak @@ -0,0 +1,62 @@ +From 25ca27ea281885eb9873244a11f08e6987efb36e Mon Sep 17 00:00:00 2001 +From: Tianyang Chen <tiche@seas.upenn.edu> +Date: Thu, 31 Dec 2015 03:42:33 -0500 +Subject: [PATCH 0/1] Improved RTDS scheduler + +Current RTDS scheduler is time driven and is called every 1ms. During each scheduler call, the repl_update() scans both runq and depeletedq, which might not be necessary every 1ms. + +Since each vcpu is implemented as a deferable server, budget is preserved during its period and refilled in the next. It is not necessary to check every 1ms as the current design does. The replenishment is needed at the nearest next period(nearest current_deadline) of all runnable vcpus. + +This improved design tries to reduce scheduler invocation by using an event driven approach;rt_schedule() will return a value when the scheduler needs to be called next time. In addition, the sched_rt will have one dedicated timer to handle replenishment when necessary. In other words, the budget replenishment and scheduler decision(rt_schedule) are separated. + +Based on previous decision between Dario, Dagaen and Meng, the improved design can be implemented/modified as follows: + +rt_schedule(): picks the highest runnable vcpu based on cpu affinity and ret.time will be passed to schedule(). + +rt_vcpu_wake(): when a vcpu is awake, it tickles instead of picking one from runq. + +rt_context_saved(): when context switching is finished, the preempted vcpu will be put back into the runq. Picking from runq and tickling are removed. + +repl_handler(): a timer handler which is reprogrammed to fire at the nearest vcpu deadline to replenish vcpus on depeletedq while keeping the runq sorted. When the replenishment is done, each replenished vcpu in the runq should tickle a pcpu to see if it needs to preempt any running vcpus. + + +An extra field to record the last replenishing time will be added. + +schedule.c SCHEDULE_SOFTIRQ: + rt_schedule(): + [spin_lock] + burn_budget(scurr) + snext = runq_pick() + [spin_unlock] + + +sched_rt.c TIMER_SOFTIRQ + replenishment_timer_handler() + [spin_lock] + <for_each_depleted_vcpu(i, i.repl_time < NOW()) { + replenish(i) + runq_tickle(i) + }> + program_timer() + [spin_lock] + +The transient behavior should be noted. It happens between a vcpu tickles and a pcpu actually picks it. As previous discussions, this is unavoidable. + +Previous discussions: +http://lists.xenproject.org/archives/html/xen-devel/2015-06/msg02629.html + +Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> +Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> +Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> + + + +Tianyang Chen (1): + Improved RTDS scheduler + + xen/common/sched_rt.c | 159 +++++++++++++++++++++++++++++-------------------- + 1 file changed, 95 insertions(+), 64 deletions(-) + +-- +1.7.9.5 + diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c index 4372486..d522272 100644 --- a/xen/common/sched_rt.c +++ b/xen/common/sched_rt.c @@ -16,6 +16,7 @@ #include <xen/delay.h> #include <xen/event.h> #include <xen/time.h> +#include <xen/timer.h> #include <xen/perfc.h> #include <xen/sched-if.h> #include <xen/softirq.h> @@ -147,6 +148,16 @@ static unsigned int nr_rt_ops; * Global lock is referenced by schedule_data.schedule_lock from all * physical cpus. It can be grabbed via vcpu_schedule_lock_irq() */ + +/* dedicated timer for replenishment */ +static struct timer repl_timer; + +/* controls when to first start the timer*/ +static int timer_started; + +/* handler for the replenishment timer */ +static void repl_handler(void *data); + struct rt_private { spinlock_t lock; /* the global coarse grand lock */ struct list_head sdom; /* list of availalbe domains, used for dump */ @@ -426,6 +437,7 @@ __runq_insert(const struct scheduler *ops, struct rt_vcpu *svc) static int rt_init(struct scheduler *ops) { + const int cpu = smp_processor_id(); struct rt_private *prv = xzalloc(struct rt_private); printk("Initializing RTDS scheduler\n" @@ -454,6 +466,8 @@ rt_init(struct scheduler *ops) ops->sched_data = prv; + init_timer(&repl_timer, repl_handler, ops, 0); + return 0; no_mem: @@ -473,6 +487,9 @@ rt_deinit(const struct scheduler *ops) xfree(_cpumask_scratch); _cpumask_scratch = NULL; } + + kill_timer(&repl_timer); + xfree(prv); } @@ -635,6 +652,13 @@ rt_vcpu_insert(const struct scheduler *ops, struct vcpu *vc) /* add rt_vcpu svc to scheduler-specific vcpu list of the dom */ list_add_tail(&svc->sdom_elem, &svc->sdom->vcpu); + + if(!timer_started) + { + /* the first vcpu starts the timer for the first time*/ + timer_started = 1; + set_timer(&repl_timer,svc->cur_deadline); + } } /* @@ -792,44 +816,6 @@ __runq_pick(const struct scheduler *ops, const cpumask_t *mask) } /* - * Update vcpu's budget and - * sort runq by insert the modifed vcpu back to runq - * lock is grabbed before calling this function - */ -static void -__repl_update(const struct scheduler *ops, s_time_t now) -{ - struct list_head *runq = rt_runq(ops); - struct list_head *depletedq = rt_depletedq(ops); - struct list_head *iter; - struct list_head *tmp; - struct rt_vcpu *svc = NULL; - - list_for_each_safe(iter, tmp, runq) - { - svc = __q_elem(iter); - if ( now < svc->cur_deadline ) - break; - - rt_update_deadline(now, svc); - /* reinsert the vcpu if its deadline is updated */ - __q_remove(svc); - __runq_insert(ops, svc); - } - - 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 */ - __runq_insert(ops, svc); /* add to runq */ - } - } -} - -/* * schedule function for rt scheduler. * The lock is already grabbed in schedule.c, no need to lock here */ @@ -848,7 +834,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 ) { @@ -889,7 +874,7 @@ rt_schedule(const struct scheduler *ops, s_time_t now, bool_t tasklet_work_sched } } - ret.time = MIN(snext->budget, MAX_SCHEDULE); /* sched quantum */ + ret.time = snext->budget; /* invoke the scheduler next time */ ret.task = snext->vcpu; /* TRACE */ @@ -1033,10 +1018,6 @@ rt_vcpu_wake(const struct scheduler *ops, struct vcpu *vc) { struct rt_vcpu * const svc = rt_vcpu(vc); s_time_t now = NOW(); - struct rt_private *prv = rt_priv(ops); - struct rt_vcpu *snext = NULL; /* highest priority on RunQ */ - struct rt_dom *sdom = NULL; - cpumask_t *online; BUG_ON( is_idle_vcpu(vc) ); @@ -1074,14 +1055,7 @@ rt_vcpu_wake(const struct scheduler *ops, struct vcpu *vc) /* insert svc to runq/depletedq because svc is not in queue now */ __runq_insert(ops, svc); - __repl_update(ops, now); - - ASSERT(!list_empty(&prv->sdom)); - sdom = list_entry(prv->sdom.next, struct rt_dom, sdom_elem); - online = cpupool_scheduler_cpumask(sdom->dom->cpupool); - snext = __runq_pick(ops, online); /* pick snext from ALL valid cpus */ - - runq_tickle(ops, snext); + runq_tickle(ops, svc); return; } @@ -1094,10 +1068,6 @@ static void rt_context_saved(const struct scheduler *ops, struct vcpu *vc) { struct rt_vcpu *svc = rt_vcpu(vc); - struct rt_vcpu *snext = NULL; - struct rt_dom *sdom = NULL; - struct rt_private *prv = rt_priv(ops); - cpumask_t *online; spinlock_t *lock = vcpu_schedule_lock_irq(vc); clear_bit(__RTDS_scheduled, &svc->flags); @@ -1108,15 +1078,8 @@ rt_context_saved(const struct scheduler *ops, struct vcpu *vc) if ( test_and_clear_bit(__RTDS_delayed_runq_add, &svc->flags) && likely(vcpu_runnable(vc)) ) { + /* only insert the pre-empted vcpu back*/ __runq_insert(ops, svc); - __repl_update(ops, NOW()); - - ASSERT(!list_empty(&prv->sdom)); - sdom = list_entry(prv->sdom.next, struct rt_dom, sdom_elem); - online = cpupool_scheduler_cpumask(sdom->dom->cpupool); - snext = __runq_pick(ops, online); /* pick snext from ALL cpus */ - - runq_tickle(ops, snext); } out: vcpu_schedule_unlock_irq(lock, vc); @@ -1167,6 +1130,74 @@ rt_dom_cntl( return rc; } +static void repl_handler(void *data){ + unsigned long flags; + s_time_t now = NOW(); + s_time_t min_repl = LONG_MAX; /* max time used in comparison*/ + struct scheduler *ops = data; + 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; + struct list_head *tmp; + struct rt_vcpu *svc = NULL; + + spin_lock_irqsave(&prv->lock,flags); + + stop_timer(&repl_timer); + + list_for_each_safe(iter, tmp, runq) + { + svc = __q_elem(iter); + if ( now < svc->cur_deadline ) + break; + rt_update_deadline(now, svc); + /* scan the runq to find the min release time + * this happens when vcpus on runq miss deadline + */ + if( min_repl> svc->cur_deadline ) + { + min_repl = svc->cur_deadline; + } + /* reinsert the vcpu if its deadline is updated */ + __q_remove(svc); + __runq_insert(ops, svc); + } + + list_for_each_safe(iter, tmp, depletedq) + { + svc = __q_elem(iter); + if ( now >= svc->cur_deadline ) + { + rt_update_deadline(now, svc); + + /* scan the delp_q to find the minimal release time */ + if(min_repl > svc->cur_deadline) + { + min_repl = svc->cur_deadline; + } + __q_remove(svc); + __runq_insert(ops, svc); + runq_tickle(ops, svc); + } + } + + /* if timer was triggered but none of the vcpus + * need to be refilled, set the timer to be the + * default period + now + */ + if(min_repl == LONG_MAX) + { + set_timer(&repl_timer, now + RTDS_DEFAULT_PERIOD); + } + else + { + /* reprogram the timer using the most imminent release time*/ + set_timer(&repl_timer, min_repl); + } + spin_unlock_irqrestore(&prv->lock,flags); +} + static struct rt_private _rt_priv; const struct scheduler sched_rtds_def = { -- 1.7.9.5 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH 1/1] Improved RTDS scheduler 2015-12-31 9:45 ` [PATCH 1/1] " Tianyang Chen @ 2016-01-04 11:42 ` Ian Campbell 2016-01-04 13:48 ` Meng Xu 0 siblings, 1 reply; 7+ messages in thread From: Ian Campbell @ 2016-01-04 11:42 UTC (permalink / raw) To: Tianyang Chen, xen-devel Cc: dario.faggioli, ian.jackson, george.dunlap, Meng Xu, jbeulich, Dagaen Golomb On Thu, 2015-12-31 at 04:45 -0500, Tianyang Chen wrote: > Budget replenishment is now handled by a dedicated timer which is > triggered at the most imminent release time of all runnable vcpus. > > Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> > Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> > Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> > --- > 0000-cover-letter.patch | 16 +++ > 0001-Improved-RTDS-scheduler.patch | 280 ++++++++++++++++++++++++++++++++++++ > bak | 62 ++++++++ I assume you didn't actually intend to commit those ;-) (In general single patches do not require a separate cover letter unless the required context contains a large amount of information which is not appropriate for the commit message of the actual change, I'll leave it to you and the scheduler maintainers to decide how much of your cover letter it would be appropriate to move to the commit message). Ian. _______________________________________________ Xen-devel mailing list Xen-devel@lists.xen.org http://lists.xen.org/xen-devel ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/1] Improved RTDS scheduler 2016-01-04 11:42 ` Ian Campbell @ 2016-01-04 13:48 ` Meng Xu 2016-01-04 14:04 ` Ian Campbell 2016-01-04 14:36 ` Dario Faggioli 0 siblings, 2 replies; 7+ messages in thread From: Meng Xu @ 2016-01-04 13:48 UTC (permalink / raw) To: Ian Campbell Cc: Dario Faggioli, Tianyang Chen, Ian Jackson, George Dunlap, Meng Xu, Jan Beulich, xen-devel, Dagaen Golomb On Mon, Jan 4, 2016 at 7:42 PM, Ian Campbell <ian.campbell@citrix.com> wrote: > On Thu, 2015-12-31 at 04:45 -0500, Tianyang Chen wrote: >> Budget replenishment is now handled by a dedicated timer which is >> triggered at the most imminent release time of all runnable vcpus. >> >> Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> >> Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> >> Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> >> --- >> 0000-cover-letter.patch | 16 +++ >> 0001-Improved-RTDS-scheduler.patch | 280 ++++++++++++++++++++++++++++++++++++ >> bak | 62 ++++++++ > > I assume you didn't actually intend to commit those ;-) No. This version was sent by mistake. Please ignore this version. :-( Tianyang sent another version (v2) with the subject "[PATCH V2 1/1] Improved RTDS scheduler". > > (In general single patches do not require a separate cover letter unless > the required context contains a large amount of information which is not > appropriate for the commit message of the actual change, I'll leave it to > you and the scheduler maintainers to decide how much of your cover letter > it would be appropriate to move to the commit message). The cover letter is supposed to explain the design idea of the improved RTDS scheduler so that reviewers could (potentially) save time in reviewing the patch, we think. :-) Probably, the commit message should be refined and self-contained? Thank you very much for your comments and suggestions! Best, Meng -- ----------- Meng Xu PhD Student in Computer and Information Science University of Pennsylvania http://www.cis.upenn.edu/~mengxu/ ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/1] Improved RTDS scheduler 2016-01-04 13:48 ` Meng Xu @ 2016-01-04 14:04 ` Ian Campbell 2016-01-04 14:36 ` Dario Faggioli 1 sibling, 0 replies; 7+ messages in thread From: Ian Campbell @ 2016-01-04 14:04 UTC (permalink / raw) To: Meng Xu Cc: Dario Faggioli, Tianyang Chen, Ian Jackson, George Dunlap, Meng Xu, Jan Beulich, xen-devel, Dagaen Golomb On Mon, 2016-01-04 at 21:48 +0800, Meng Xu wrote: > > (In general single patches do not require a separate cover letter > > unless > > the required context contains a large amount of information which is > > not > > appropriate for the commit message of the actual change, I'll leave it > > to > > you and the scheduler maintainers to decide how much of your cover > > letter > > it would be appropriate to move to the commit message). > > The cover letter is supposed to explain the design idea of the > improved RTDS scheduler so that reviewers could (potentially) save > time in reviewing the patch, we think. :-) > Probably, the commit message should be refined and self-contained? If I were maintainer of this code I would likely ask that a bunch of the information from the cover letter (i..e anything which would still be relevant to a code archaeologist in 6 months or 10 years) was moved into the commit message, but I'm not maintainer of this code. Ian. ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/1] Improved RTDS scheduler 2016-01-04 13:48 ` Meng Xu 2016-01-04 14:04 ` Ian Campbell @ 2016-01-04 14:36 ` Dario Faggioli 2016-01-06 7:11 ` Tianyang Chen 1 sibling, 1 reply; 7+ messages in thread From: Dario Faggioli @ 2016-01-04 14:36 UTC (permalink / raw) To: Meng Xu, Ian Campbell Cc: Tianyang Chen, Ian Jackson, George Dunlap, Meng Xu, Jan Beulich, xen-devel, Dagaen Golomb [-- Attachment #1.1: Type: text/plain, Size: 4526 bytes --] On Mon, 2016-01-04 at 21:48 +0800, Meng Xu wrote: > On Mon, Jan 4, 2016 at 7:42 PM, Ian Campbell <ian.campbell@citrix.com > > wrote: > > On Thu, 2015-12-31 at 04:45 -0500, Tianyang Chen wrote: > > > Budget replenishment is now handled by a dedicated timer which is > > > triggered at the most imminent release time of all runnable > > > vcpus. > > > > > > Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> > > > Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> > > > Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> > > > --- > > > 0000-cover-letter.patch | 16 +++ > > > 0001-Improved-RTDS-scheduler.patch | 280 > > > ++++++++++++++++++++++++++++++++++++ > > > bak | 62 ++++++++ > > > > I assume you didn't actually intend to commit those ;-) > > No. This version was sent by mistake. Please ignore this version. :-( > > Tianyang sent another version (v2) with the subject "[PATCH V2 1/1] > Improved RTDS scheduler". > Indeed. BTW, I'm back today from Winter Holidays. I'll give a look at this series as soon as practical. I'll comment directly on V2, with the only exception of this very email. So, first of all, Cc list (which is the same here and in V2): how have the names of the people that are in there been picked? The patch is only about xen/common/sched_rt.c. As per MAINTAINERS, the maintainer of the code hosted in that file is just me. Surely it's a good thing to also include George, as he's the other maintainer of scheduling in general. All the other people, though, should not be bothered by being copied directly... Especially IanC and IanJ, I'd say. > > (In general single patches do not require a separate cover letter > > unless > > the required context contains a large amount of information which > > is not > > appropriate for the commit message of the actual change, I'll leave > > it to > > you and the scheduler maintainers to decide how much of your cover > > letter > > it would be appropriate to move to the commit message). > > The cover letter is supposed to explain the design idea of the > improved RTDS scheduler so that reviewers could (potentially) save > time in reviewing the patch, we think. :-) > Probably, the commit message should be refined and self-contained? > That's true. In particular, the "context", defined as summary of what happened and have been discussed on the mailing list before, during previous submissions, etc., definitely belongs to a cover letter. High level design ideas and concepts, also do, e.g., in order to avoid ending up with commit changelogs that are all several pages long! :-) All that being said, we certainly want patches' subject lines and changelogs to be descriptive of at least what is being done, and why. If we commit this as it is right now, here it is what we'll find in `git log': Improved RTDS scheduler Budget replenishment is now handled by a dedicated timer which is triggered at the most imminent release time of all runnable vcpus. Which won't, I'm quite sure about it, be that much useful when looking at it, say, in 3 years! :-D I know, finding the proper balance of what's better put where is not always super easy, especially at the beginning... but that's part of the process of cooking a good patch (series) :-) A few suggestions: - we want tags in the subject. E.g., in this case, something like "xen: sched: Improved RTDS scheduler" - avoid (in both subject and changelog) generic terms like "improve" "fix", etc., unless you can explain more specifically to what they refer... I mean, pretty much all commits that touch sched_rt.c can have "Improve RTDS" as a subject, can't they? (Unless we decide to commit something making things deliberately worse!! :-)) In this case, e.g. (although, perhaps a bit long): "xen: sched: convert RTDS from time to event driven model" - as Ian said, there are information in the cover letter that can well be moved in the changelog, making it a lot more useful, and not less refined or self contained. Thanks and Regards, Dario -- <<This happens because I choose it to happen!>> (Raistlin Majere) ----------------------------------------------------------------- Dario Faggioli, Ph.D, http://about.me/dario.faggioli Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK) [-- Attachment #1.2: This is a digitally signed message part --] [-- Type: application/pgp-signature, Size: 181 bytes --] [-- Attachment #2: Type: text/plain, Size: 126 bytes --] _______________________________________________ Xen-devel mailing list Xen-devel@lists.xen.org http://lists.xen.org/xen-devel ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 1/1] Improved RTDS scheduler 2016-01-04 14:36 ` Dario Faggioli @ 2016-01-06 7:11 ` Tianyang Chen 0 siblings, 0 replies; 7+ messages in thread From: Tianyang Chen @ 2016-01-06 7:11 UTC (permalink / raw) To: Dario Faggioli, Meng Xu; +Cc: xen-devel, George Dunlap, Dagaen Golomb, Meng Xu On 1/4/2016 9:36 AM, Dario Faggioli wrote: > On Mon, 2016-01-04 at 21:48 +0800, Meng Xu wrote: >> On Mon, Jan 4, 2016 at 7:42 PM, Ian Campbell <ian.campbell@citrix.com >>> wrote: >>> On Thu, 2015-12-31 at 04:45 -0500, Tianyang Chen wrote: >>>> Budget replenishment is now handled by a dedicated timer which is >>>> triggered at the most imminent release time of all runnable >>>> vcpus. >>>> >>>> Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu> >>>> Signed-off-by: Meng Xu <mengxu@cis.upenn.edu> >>>> Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu> >>>> --- >>>> 0000-cover-letter.patch | 16 +++ >>>> 0001-Improved-RTDS-scheduler.patch | 280 >>>> ++++++++++++++++++++++++++++++++++++ >>>> bak | 62 ++++++++ >>> >>> I assume you didn't actually intend to commit those ;-) >> >> No. This version was sent by mistake. Please ignore this version. :-( >> >> Tianyang sent another version (v2) with the subject "[PATCH V2 1/1] >> Improved RTDS scheduler". >> > Indeed. BTW, I'm back today from Winter Holidays. I'll give a look at > this series as soon as practical. > > I'll comment directly on V2, with the only exception of this very > email. > > So, first of all, Cc list (which is the same here and in V2): how have > the names of the people that are in there been picked? > Dario: I picked the names based on previous discussion threads between you, Meng and Dagaen. Now I have changed who will be cc'ed so they won't be bothered. > The patch is only about xen/common/sched_rt.c. As per MAINTAINERS, the > maintainer of the code hosted in that file is just me. Surely it's a > good thing to also include George, as he's the other maintainer of > scheduling in general. > > All the other people, though, should not be bothered by being copied > directly... Especially IanC and IanJ, I'd say. > >>> (In general single patches do not require a separate cover letter >>> unless >>> the required context contains a large amount of information which >>> is not >>> appropriate for the commit message of the actual change, I'll leave >>> it to >>> you and the scheduler maintainers to decide how much of your cover >>> letter >>> it would be appropriate to move to the commit message). >> >> The cover letter is supposed to explain the design idea of the >> improved RTDS scheduler so that reviewers could (potentially) save >> time in reviewing the patch, we think. :-) >> Probably, the commit message should be refined and self-contained? >> > That's true. In particular, the "context", defined as summary of what > happened and have been discussed on the mailing list before, during > previous submissions, etc., definitely belongs to a cover letter. > There are pages of discussions on the current design and we figured we should make a cover page to summarize it and put more details in. > High level design ideas and concepts, also do, e.g., in order to avoid > ending up with commit changelogs that are all several pages long! :-) > > All that being said, we certainly want patches' subject lines and > changelogs to be descriptive of at least what is being done, and why. > If we commit this as it is right now, here it is what we'll find in > `git log': > > Improved RTDS scheduler > > Budget replenishment is now handled by a dedicated timer which is > triggered at the most imminent release time of all runnable vcpus. > > Which won't, I'm quite sure about it, be that much useful when looking > at it, say, in 3 years! :-D > > I know, finding the proper balance of what's better put where is not > always super easy, especially at the beginning... but that's part of > the process of cooking a good patch (series) :-) > > A few suggestions: > > - we want tags in the subject. E.g., in this case, something like > "xen: sched: Improved RTDS scheduler" > > - avoid (in both subject and changelog) generic terms like "improve" > "fix", etc., unless you can explain more specifically to what they > refer... I mean, pretty much all commits that touch sched_rt.c can > have "Improve RTDS" as a subject, can't they? (Unless we decide to > commit something making things deliberately worse!! :-)) > Good call. > In this case, e.g. (although, perhaps a bit long): > "xen: sched: convert RTDS from time to event driven model" > > - as Ian said, there are information in the cover letter that can > well be moved in the changelog, making it a lot more useful, and > not less refined or self contained. > Here is what I propose, please let me know your thoughts: Cover letter: 1. How this patch could improve RTDS 2. Summary of previous discussion Current RTDS scheduler is time driven and is called every 1ms. During each scheduler call, the repl_update() scans both runq and depeletedq, which might not be necessary every 1ms. Since each vcpu is implemented as a deferable server, budget is preserved during its period and refilled in the next. It is not necessary to check every 1ms as the current design does. The replenishment is needed at the nearest next period(nearest current_deadline) of all runnable vcpus. This improved design tries to reduce scheduler invocation by using an event driven approach;rt_schedule() will return a value when the scheduler needs to be called next time. In addition, the sched_rt will have one dedicated timer to handle replenishment when necessary. In other words, the budget replenishment and scheduler decision(rt_schedule) are separated. ---------------------------------------------------------------------- Changelog: 1. Changed/removed functions 2. Function graphs for handler and rt_schedule xen: sched: convert RTDS from time to event driven model Budget replenishment and enforcement are separated by adding a replenishment timer, which fires at the next most imminent release time of all runnable vcpus. repl_handler(): a timer handler which is reprogrammed to fire at the nearest vcpu deadline to replenish vcpus on runq and depeletedq. When the replenishment is done, each replenished vcpu in the runq should tickle a pcpu to see if it needs to preempt any running vcpus. rt_schedule(): picks the highest runnable vcpu based on cpu affinity and ret.time will be passed to schedule(). repl_update() has been removed. The following functions have major changes: rt_vcpu_wake(): when a vcpu is awake, it tickles instead of picking one from runq. rt_context_saved(): when context switching is finished, the preempted vcpu will be put back into the runq. Picking from runq and tickling are removed. schedule.c SCHEDULE_SOFTIRQ: rt_schedule(): [spin_lock] burn_budget(scurr) snext = runq_pick() [spin_unlock] sched_rt.c TIMER_SOFTIRQ replenishment_timer_handler() [spin_lock] <for_each_depleted_vcpu(i, i.repl_time < NOW()) { replenish(i) runq_tickle(i) }> program_timer() [spin_lock] Thanks, Tianyang Chen > Thanks and Regards, > Dario > ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2016-01-06 7:11 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-12-31 9:45 [PATCH 0/1] Improved RTDS scheduler Tianyang Chen 2015-12-31 9:45 ` [PATCH 1/1] " Tianyang Chen 2016-01-04 11:42 ` Ian Campbell 2016-01-04 13:48 ` Meng Xu 2016-01-04 14:04 ` Ian Campbell 2016-01-04 14:36 ` Dario Faggioli 2016-01-06 7:11 ` Tianyang Chen
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.