[Xen-devel] [PATCH 14 of 16] credit2: Introduce a loadavg-based load balancer

[George Dunlap <george.dunlap@xxxxxxxxxxxxx>]

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>

diff -r 648a4a86b8c8 -r dca9ad897502 xen/common/sched_credit2.c
--- a/xen/common/sched_credit2.c        Thu Dec 23 12:26:58 2010 +0000
+++ b/xen/common/sched_credit2.c        Thu Dec 23 12:27:14 2010 +0000
@@ -1104,6 +1104,216 @@
     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 @@
 
         /* 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-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel