# HG changeset patch
# User Keir Fraser <keir@xxxxxxx>
# Date 1293179514 0
# Node ID 65b63f5af281362ada388f2689a347ab6a2d28ab
# Parent 41d1affef5969003eb3cb5f6313421c12db4d0c2
credit2: Introduce a loadavg-based load balancer
This is a first-cut at getting load balancing. I'm first working on
looking at behavior I want to get correct; then, once I know what kind
of behavior works well, then I'll work on getting it efficient.
The general idea is when balancing runqueues, look for the runqueue
whose loadavg is the most different from ours (higher or lower).
Then, look for a transaction which will bring the loads closest
together: either pushing a vcpu, pulling a vcpu, or swapping them.
Use the per-vcpu load to calculate the expected load after the
exchange.
The current algorithm looks at every combination, which is O(N^2).
That's not going to be suitable for workloads with large numbers of
vcpus (such as highly consolidated VDI deployments). I'll make a more
efficient algorithm once I've experimented and determined what I think
is the best load-balancing behavior.
At the moment, balance from a runqueue every time the credit resets.
Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>
---
xen/common/sched_credit2.c | 213 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 213 insertions(+)
diff -r 41d1affef596 -r 65b63f5af281 xen/common/sched_credit2.c
--- a/xen/common/sched_credit2.c Fri Dec 24 08:31:24 2010 +0000
+++ b/xen/common/sched_credit2.c Fri Dec 24 08:31:54 2010 +0000
@@ -1104,6 +1104,216 @@ out_up:
return new_cpu;
}
+static void balance_load(const struct scheduler *ops, int cpu, s_time_t now)
+{
+ struct csched_private *prv = CSCHED_PRIV(ops);
+ int i, max_delta_rqi = -1;
+ struct list_head *push_iter, *pull_iter;
+
+ /* NB: Modified by consider() */
+ s_time_t load_delta;
+ struct csched_vcpu * best_push_svc=NULL, *best_pull_svc=NULL;
+ /* NB: Read by consider() */
+ struct csched_runqueue_data *lrqd;
+ struct csched_runqueue_data *orqd;
+
+ void consider(struct csched_vcpu *push_svc,
+ struct csched_vcpu *pull_svc)
+ {
+ s_time_t l_load, o_load, delta;
+
+ l_load = lrqd->b_avgload;
+ o_load = orqd->b_avgload;
+ if ( push_svc )
+ {
+ /* What happens to the load on both if we push? */
+ l_load -= push_svc->avgload;
+ o_load += push_svc->avgload;
+ }
+ if ( pull_svc )
+ {
+ /* What happens to the load on both if we pull? */
+ l_load += pull_svc->avgload;
+ o_load -= pull_svc->avgload;
+ }
+
+ delta = l_load - o_load;
+ if ( delta < 0 )
+ delta = -delta;
+
+ if ( delta < load_delta )
+ {
+ load_delta = delta;
+ best_push_svc=push_svc;
+ best_pull_svc=pull_svc;
+ }
+ }
+
+ void migrate(struct csched_vcpu *svc, struct csched_runqueue_data *trqd)
+ {
+ if ( test_bit(__CSFLAG_scheduled, &svc->flags) )
+ {
+ d2printk("d%dv%d %d-%d a\n", svc->vcpu->domain->domain_id,
svc->vcpu->vcpu_id,
+ svc->rqd->id, trqd->id);
+ /* It's running; mark it to migrate. */
+ svc->migrate_rqd = trqd;
+ set_bit(_VPF_migrating, &svc->vcpu->pause_flags);
+ set_bit(__CSFLAG_runq_migrate_request, &svc->flags);
+ }
+ else
+ {
+ int on_runq=0;
+ /* It's not running; just move it */
+ d2printk("d%dv%d %d-%d i\n", svc->vcpu->domain->domain_id,
svc->vcpu->vcpu_id,
+ svc->rqd->id, trqd->id);
+ if ( __vcpu_on_runq(svc) )
+ {
+ __runq_remove(svc);
+ update_load(ops, svc->rqd, svc, -1, now);
+ on_runq=1;
+ }
+ __runq_deassign(svc);
+ svc->vcpu->processor = first_cpu(trqd->active);
+ __runq_assign(svc, trqd);
+ if ( on_runq )
+ {
+ update_load(ops, svc->rqd, svc, 1, now);
+ runq_insert(ops, svc->vcpu->processor, svc);
+ runq_tickle(ops, svc->vcpu->processor, svc, now);
+ }
+ }
+ }
+
+
+ /*
+ * Basic algorithm: Push, pull, or swap.
+ * - Find the runqueue with the furthest load distance
+ * - Find a pair that makes the difference the least (where one
+ * on either side may be empty).
+ */
+
+ /* Locking:
+ * - pcpu schedule lock should be already locked
+ */
+ lrqd = RQD(ops, cpu);
+
+ __update_runq_load(ops, lrqd, 0, now);
+
+retry:
+ if ( !spin_trylock(&prv->lock) )
+ return;
+
+ load_delta = 0;
+
+ for_each_cpu_mask(i, prv->active_queues)
+ {
+ s_time_t delta;
+
+ orqd = prv->rqd + i;
+
+ if ( orqd == lrqd
+ || !spin_trylock(&orqd->lock) )
+ continue;
+
+ __update_runq_load(ops, orqd, 0, now);
+
+ delta = lrqd->b_avgload - orqd->b_avgload;
+ if ( delta < 0 )
+ delta = -delta;
+
+ if ( delta > load_delta )
+ {
+ load_delta = delta;
+ max_delta_rqi = i;
+ }
+
+ spin_unlock(&orqd->lock);
+ }
+
+ /* Minimize holding the big lock */
+ spin_unlock(&prv->lock);
+
+ if ( max_delta_rqi == -1 )
+ goto out;
+
+ /* Don't bother with load differences less than 25%. */
+ if ( load_delta < (1ULL<<(prv->load_window_shift - 2)) )
+ goto out;
+
+ /* Try to grab the other runqueue lock; if it's been taken in the
+ * meantime, try the process over again. This can't deadlock
+ * because if it doesn't get any other rqd locks, it will simply
+ * give up and return. */
+ orqd = prv->rqd + max_delta_rqi;
+ if ( !spin_trylock(&orqd->lock) )
+ goto retry;
+
+ /* Make sure the runqueue hasn't been deactivated since we released
prv->lock */
+ if ( unlikely(orqd->id < 0) )
+ goto out_up;
+
+ /* Look for "swap" which gives the best load average
+ * FIXME: O(n^2)! */
+
+ /* Reuse load delta (as we're trying to minimize it) */
+ list_for_each( push_iter, &lrqd->svc )
+ {
+ int inner_load_updated = 0;
+ struct csched_vcpu * push_svc = list_entry(push_iter, struct
csched_vcpu, rqd_elem);
+
+ __update_svc_load(ops, push_svc, 0, now);
+
+ /* Skip this one if it's already been flagged to migrate */
+ if ( test_bit(__CSFLAG_runq_migrate_request, &push_svc->flags) )
+ continue;
+
+ list_for_each( pull_iter, &orqd->svc )
+ {
+ struct csched_vcpu * pull_svc = list_entry(pull_iter, struct
csched_vcpu, rqd_elem);
+
+ if ( ! inner_load_updated )
+ {
+ __update_svc_load(ops, pull_svc, 0, now);
+ }
+
+ /* Skip this one if it's already been flagged to migrate */
+ if ( test_bit(__CSFLAG_runq_migrate_request, &pull_svc->flags) )
+ continue;
+
+ consider(push_svc, pull_svc);
+ }
+
+ inner_load_updated = 1;
+
+ /* Consider push only */
+ consider(push_svc, NULL);
+ }
+
+ list_for_each( pull_iter, &orqd->svc )
+ {
+ struct csched_vcpu * pull_svc = list_entry(pull_iter, struct
csched_vcpu, rqd_elem);
+
+ /* Skip this one if it's already been flagged to migrate */
+ if ( test_bit(__CSFLAG_runq_migrate_request, &pull_svc->flags) )
+ continue;
+
+ /* Consider pull only */
+ consider(NULL, pull_svc);
+ }
+
+ /* OK, now we have some candidates; do the moving */
+ if ( best_push_svc )
+ migrate(best_push_svc, orqd);
+ if ( best_pull_svc )
+ migrate(best_pull_svc, lrqd);
+
+out_up:
+ spin_unlock(&orqd->lock);
+
+out:
+ return;
+}
+
static int
csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc)
{
@@ -1437,7 +1647,10 @@ csched_schedule(
/* Check for the reset condition */
if ( snext->credit <= CSCHED_CREDIT_RESET )
+ {
reset_credit(ops, cpu, now);
+ balance_load(ops, cpu, now);
+ }
/* Clear the idle mask if necessary */
if ( cpu_isset(cpu, rqd->idle) )
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog
|
Home