linux在多核处理器上的负载均衡原理

晨曦之光 发布于 2012/03/09 15:00
阅读 3K+
收藏 0

原文出处:http://donghao.org/uii/ 

【原理】

现在互联网公司使用的都是多CPU(多核)的服务器了,Linux操作系统会自动把任务分配到不同的处理器上,并尽可能的保持负载均衡。那Linux内核是怎么做到让各个CPU的压力均匀的呢?

做一个负载均衡机制,重点在于:

1. 何时检查并调整负载情况?

2. 如何调整负载?

先看第一个问题。

如果让我这样的庸俗程序员来设计,我第一个想到的就是每隔一段时间检查一次负载是否均衡,不均则调整之,这肯定不是最高效的办法,但肯定是实现上最简单的。实际上,2.6.20版linux kernel的确使用软中断来定时调整多CPU上的压力(调用函数run_rebalance_domains),每秒1次

但每秒一次还是不能满足要求,对很多应用来说,1秒太长了,一秒钟内如果发生负载失衡对很多web应用都是不能接受的,何况其他实时应用。最好kernel能够紧跟进程的变化来调整。

那么,好,我们在进程创建和进程exit的时候检查并调整负载呢?可以,但是不完整,一个进程创建以后如果频繁的睡眠、醒来、睡眠、醒来,它这样折腾对CPU的负载是有影响的,你就不管它了吗?说到底,我们其实关注的是进程是否在使用CPU,而不是它是否诞生了。所以,我们应该在进程睡眠和醒来这两个时间点检查CPU们的负载。

再看第二个问题,怎么调整负载呢?从最繁忙的那个CPU上挪一个进程到最闲的那个CPU上,如果负载还不均衡,就再挪一个进程,如果还不均衡,继续挪....这也是个最笨的方法,但它却真的是linux CPU负载均衡的核心,不过实际的算法在此基础上有很多细化。对于Intel的CPU,压缩在同一个chip上的多核是共享同一个L2的(如下图,里面的一个Processor其实就是一个chip),如果任务能尽可能的分配在同一个chip上,L2 cache就可以继续使用,这对运行速度是有帮助的。所以除非“很不均衡”,否则尽量不要把一个chip上的任务挪到其他chip上。

于是,为了应对这种CPU core之间的异质性——在不同的core之间迁移任务,代价不同——Linux kernel引入了sched_domain和sched_group的概念。sched_domain和sched_group的具体原理,可参考刘勃的文章英文资料

【代码剖析】

SMP负载均衡检查或调整在两个内核函数里发生:

1. schedule()。当进程调用了sleep、usleep、poll、epoll、pause时,也就是调用了可能睡去的操作时都会转为内核代码里对schedule()函数的调用。

2. try_to_wake_up() 。说白了就是进程刚才睡了,现在要醒来,那醒来以后跑在哪个CPU上呢?这个选择CPU的过程,也就是负载均衡的过程。

我们先看schedule()的代码,我们忽略函数前面那些和负载均衡无关的代码(本文代码以内核2.6.20版为准):

[kernel/sched.c --> schedule() ]

  3489     cpu = smp_processor_id();
  3490     if (unlikely(!rq->nr_running)) {
   3491         idle_balance(cpu, rq);
  3492         if (!rq->nr_running) {
  3493             next = rq->idle;
  3494             rq->expired_timestamp = 0;
  3495             wake_sleeping_dependent(cpu);
  3496             goto switch_tasks;
  3497         }
  3498     }

每个CPU都有一个运行队列即这里的 rq,运行队列里放着该CPU要运行的进程,如果运行队列里没有进程了,就说明当前CPU没有可调度的任务了,那就要调用idle_balance从其它CPU上“平衡”一些(就是挪一些)进程到当前rq里。

再看 idle_balance()的实现:

[kernel/sched.c --> idle_balance()]
  2806 /*
  2807  * idle_balance is called by schedule() if this_cpu is about to become
  2808  * idle. Attempts to pull tasks from other CPUs.
  2809  */
  2810 static void idle_balance(int this_cpu, struct rq *this_rq)
  2811 {
  2812     struct sched_domain *sd;
  2813     int pulled_task = 0;
  2814     unsigned long next_balance = jiffies + 60 *  HZ;
  2815
  2816     for_each_domain(this_cpu, sd) {
  2817         unsigned long interval;
  2818
  2819         if (!(sd->flags & SD_LOAD_BALANCE))
  2820             continue;
  2821
  2822         if (sd->flags & SD_BALANCE_NEWIDLE)
  2823             /* If we've pulled tasks over stop searching: */
  2824             pulled_task = load_balance_newidle(this_cpu,
  2825                                 this_rq, sd);
  2826
  2827         interval = msecs_to_jiffies(sd->balance_interval);
  2828         if (time_after(next_balance, sd->last_balance + interval))
  2829             next_balance = sd->last_balance + interval;
  2830         if (pulled_task)
  2831             break;
  2832     }
  2833     if (!pulled_task)
  2834         /*
  2835          * We are going idle. next_balance may be set based on
  2836          * a busy processor. So reset next_balance.
  2837          */
  2838         this_rq->next_balance = next_balance;
  2839 }

从子 sched_domain到父sched_domain遍历该CPU对应的domain(2816行),并调用load_balance_newidle,我们继续:

[kernel/sched.c --> load_balance_newidle()]
2730 static int
  2731 load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
  2732 {
  2733     struct sched_group *group;
  2734     struct rq *busiest = NULL;
  2735     unsigned long imbalance;
  2736     int nr_moved = 0;
  2737     int sd_idle = 0;
  2738     cpumask_t cpus = CPU_MASK_ALL;
  2739
  2740     /*
  2741      * When power savings policy is enabled for the parent domain, idle
  2742      * sibling can pick up load irrespective of busy siblings. In this case,
  2743      * let the state of idle sibling percolate up as IDLE, instead of
  2744      * portraying it as NOT_IDLE.
  2745      */
  2746     if (sd->flags & SD_SHARE_CPUPOWER &&
  2747         !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
  2748         sd_idle = 1;
  2749
  2750     schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
  2751 redo:
  2752     group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE,
  2753                    &sd_idle, &cpus, NULL);
  2754     if (!group) {
  2755         schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
  2756         goto out_balanced;
  2757     }
  2758
  2759     busiest = find_busiest_queue(group, NEWLY_IDLE, imbalance,
  2760                 &cpus);
  2761     if (!busiest) {
  2762         schedstat_inc(sd, lb_nobusyq[NEWLY_IDLE]);
  2763         goto out_balanced;
  2764     }
  2765
  2766     BUG_ON(busiest == this_rq);
  2767
  2768     schedstat_add(sd, lb_imbalance[NEWLY_IDLE], imbalance);
  2769
  2770     nr_moved = 0;
  2771     if (busiest->nr_running > 1) {
  2772         /* Attempt to move tasks */
  2773         double_lock_balance(this_rq, busiest);
  2774         nr_moved = move_tasks(this_rq, this_cpu, busiest,
  2775                     minus_1_or_zero(busiest->nr_running),
  2776                     imbalance, sd, NEWLY_IDLE, NULL);

原来就是我们上面说的“笨办法”,针对当前CPU所属的每个domain(从子到父),找到该 sched_domain里最忙的sched_group(2752行),再从该group里找出最忙的运行队列(2759行),最后从该“最忙”运行队列里挑出几个进程到当前CPU的运行队列里。move_tasks函数到底挪多少进程到当前CPU是由第4和第5个参数决定的,第4个参数是指最多挪多少个进程,第5个参数是指最多挪多少“压力”。有了这两个参数限制,就不会挪过头了(即把太多进程挪到当前CPU,造成新的不均衡)。

举个例子,假如有一台8核的机器,两个CPU插槽,也就是两个chip,每个chip上4个核,再假设现在core 4最忙,core 0第二忙,如图:
按照 刘勃的文章里的提法,首先是core domain,即Processor 0属于domain 1,Processor 1属于domain 2,其中domain 1包含4个sched_group,每个group对应一个core,如下图(group未画出):
假如现在是 Core 3 在执行idle_balance,则先在domain 1里找最忙的group,找到第二忙的group是core 0(core 4不在domain 1里,所以不会找到它),再从core 0里找最忙的runqueue(运行队列),core 0就一个运行队列,所以直接就是它对应的runqueue了,然后从该runqueue里挪出几个任务到Core 3,这一层domain的均衡做完了。

接着是domain  1的父domain,即 cpu_domain,下图的domain 0:
这个domain 0包含了两个group,每个group对应一个chip,即每个group对应了4个core。
在domain 0找最繁忙的group,显然会找到Processor1 对应的group(因为core 4超忙),那么继续在Processor 1里找最忙的runqueue,于是找到core 4,最后从core 4的runqueue里挑出几个任务挪到core 3,。
这样,整个系统8个核都基本平衡了。

也许有人要问,为什么是从子domain到父domain这样遍历,而不是倒过来,从父到子遍历呢?这是因为子domain通常都是在一个chip上,任务的很多数据在共享的L2 cache上,为了不让其失效,有必要尽量让任务保持在一个chip上。

也许还有人要问:如果core 3本来就是最忙的core,它如果运行idle_balance,会发生什么?答案是什么也不会发生。因为在find_busiest_group函数里,如果发现最忙的是“本CPU”,那么就直接返回NULL,也就不再做任何事。
那core 3岂不永远是最忙的了?呵呵,大家忘了,系统里总有闲的CPU(哪怕是相对比较闲),它总会执行schedule(),就算它从不调用sleep从不睡眠,时钟中断也会迫使其进程切换,进而调用schedule,进而将繁忙CPU的任务揽一部分到自己身上。这样,谁最闲,谁早晚会从忙人身上揽活儿过来,所以忙人不会永远最忙,闲人也不会永远最闲,所以就平等,就均衡了。

再看try_to_wake_up():
[kernel/sched.c --> try_to_wake_up()]
1398 static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
  1399 {
            ......
  1417
  1418     cpu = task_cpu(p);
  1419     this_cpu = smp_processor_id();
  1420
  1421 #ifdef CONFIG_SMP
  1422     if (unlikely(task_running(rq, p)))
  1423         goto out_activate;
  1424
  1425     new_cpu = cpu;
  1426
  1427     schedstat_inc(rq, ttwu_cnt);
   1428     if (cpu == this_cpu) {
  1429         schedstat_inc(rq, ttwu_local);
  1430         goto out_set_cpu;
  1431     }

变量this_cpu和变量cpu有什么区别?变量this_cpu是实际运行这个函数的处理器(“目标处理器”),而变量cpu是进程p在睡眠之前运行的处理器??为了方便我们暂且称之为“源处理器”。当然,这两个处理器也可能是同一个,比如进程p在处理器A上运行,然后睡眠,而运行try_to_wake_up的也是处理器A,其实这样就最好了,进程p在处理器A里cache的数据都不用动,直接让A运行p就行了??这就是1428行的逻辑。

如果this_cpu和cpu不是同一个处理器,那么代码继续:
  1447     if (this_sd) {
  1448         int idx = this_sd->wake_idx;
  1449         unsigned int imbalance;
  1450
  1451         imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
  1452
   1453         load = source_load(cpu, idx);
  1454         this_load = target_load(this_cpu, idx);
  1455
  1456         new_cpu = this_cpu; /* Wake to this CPU if we can */
  1457
  1458         if (this_sd->flags & SD_WAKE_AFFINE) {
  1459             unsigned long tl = this_load;
  1460             unsigned long tl_per_task;
  1461
  1462             tl_per_task = cpu_avg_load_per_task(this_cpu);
  1463
  1464             /*
  1465              * If sync wakeup then subtract the (maximum possible)
  1466              * effect of the currently running task from the load
  1467              * of the current CPU:
  1468              */
  1469             if (sync)
  1470                 tl -= current->load_weight;
  1471
   1472             if ((tl <= load &&
  1473                 tl + target_load(cpu, idx) <= tl_per_task) ||
  1474                 100*(tl + p->load_weight) <= imbalance*load) {
  1475                 /*
  1476                  * This domain has SD_WAKE_AFFINE and
  1477                  * p is cache cold in this domain, and
  1478                  * there is no bad imbalance.
  1479                  */
  1480                 schedstat_inc(this_sd, ttwu_move_affine);
  1481                 goto out_set_cpu;
  1482             }
  1483         }

计算出“目标处理器”和“源处理器”各自的负载( 1453行和1454行),再计算“目标处理器”上的每任务平均负载  tl_per_task,最后进行判断:如果“目标处理器”的负载小于“源处理器”的负载且两处理器负载相加都比 tl_per_task小的话,唤醒的进程转为“目标处理器”执行。还有一种情况就是1474行的判断,如果“目标处理器”的负载加上被唤醒的进程的负载后,还比“源处理器”的负载(乘以imbalance后)的小的话,也要把唤醒的进程转为“目标处理器”执行。如果两个因素都不满足,那还是由p进程原来呆的那个CPU(即”源处理器“)继续来处理吧。

有点儿绕,是吧?其实代码虽绕,用意是简单的:

1472行-1473行其实是这样一个用意:如果“目标处理器”的负载很小,小得即使把压力全给到“源处理器”上去也不会超过“源处理器”上的平均任务负载,那么这“目标处理器”的负载是真的很小,值得把p进程挪过来。
1474行的用意则是:如果我们真的把p进程挪到“目标处理器”以后,“目标处理器”的压力也不比“源处理器”大多少,所以,还是值得一挪。

说来说去,还是那个笨原则:把任务从最忙的CPU那儿转到很闲的CPU这儿。

我们已经看过了睡眠和醒来时的内核函数,那么软中断里的 run_rebalance_domains又干了些什么呢?其实也很简单,它调用了load_balance函数,而这个函数和load_balance_newidle实现上基本一样,就不累述了。

这里没有探讨进程优先级和进程负载的计算方法,因为太复杂我也不太理解,以后看代码如果有心得,再与大家分享。

 


原文链接:http://blog.csdn.net/21aspnet/article/details/1534304
加载中
返回顶部
顶部