【原
理】
现在互联网公司使用的都是多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实现上基本一样，就不累述了。
这
里没有探讨进程优先级和进程负载的计算方法，因为太复杂我也不太理解，以后看代码如果有心得，再与大家分享。
