[kernel] linux在多核处理器上的负载均衡原理
【转载请注明出处：http://oldblog.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实现上基本一样，就不累述了。
这里没有探讨进程优先级和进程负载的计算方法，因为太复杂我也不太理解，以后看代码如果有心得，再与大家分享。
相关文章
- [kernel] 如果在linux内核模块里用错锁？ - 08 04, 2010
- [linux] tail和poll无关 - 06 01, 2010
- [kernel] epoll里的EPOLLET标记 - 05 14, 2010
留言：