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

怼烎@ 2022-02-03 03:53 236阅读 0赞

# \[kernel\] linux在多核处理器上的负载均衡原理 #

转载自:[http://rdc.taobao.com/blog/cs/?p=379][http_rdc.taobao.com_blog_cs_p_379]

现在互联网公司使用的都是多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上。

![Intel MUlti-Core CPU][]

于是，为了应对这种CPU core之间的异质性??在不同的core之间迁移任务，代价不同??Linux kernel引入了sched\_domain和sched\_group的概念。sched\_domain和sched\_group的具体原理，可参考[刘勃的文章][Link 1]和[英文资料][Link 2]。

## 【代码剖析】 ##

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第二忙，如图：

![image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2884034c687b942b29389fb0f680e1d1b18][]

按照 [刘勃的文章][Link 1]里的提法，首先是core domain，即Processor 0属于domain 1，Processor 1属于domain 2，其中domain 1包含4个sched\_group，每个group对应一个core，如下图（group未画出）：

![image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df288fc159409f04c52a7b7e01d78b4d1f172][]

假如现在是 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：

![image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2889394903d65f7c60901be74699310c7fc][]

这个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_rdc.taobao.com_blog_cs_p_379]: http://rdc.taobao.com/blog/cs/?p=379
[Intel MUlti-Core CPU]: http://writer.zoho.com/image.do?imgurl=27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df28829bd57fa5258b45e3aa927bb6c54f8a6
[Link 1]: http://www.ibm.com/developerworks/cn/linux/l-cn-schldom/index.html
[Link 2]: http://book.opensourceproject.org.cn/kernel/kernel3rd/opensource/0596005652/understandlk-chp-7-sect-5.html
[image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2884034c687b942b29389fb0f680e1d1b18]: http://writer.zoho.com/image.do?imgurl=27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2884034c687b942b29389fb0f680e1d1b18
[image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df288fc159409f04c52a7b7e01d78b4d1f172]: http://writer.zoho.com/image.do?imgurl=27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df288fc159409f04c52a7b7e01d78b4d1f172
[image.do_imgurl_27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2889394903d65f7c60901be74699310c7fc]: http://writer.zoho.com/image.do?imgurl=27c929fe53698e0d9b3cb46b35d4e45dcc3ce9803a0e8d54b8a55f66891df2889394903d65f7c60901be74699310c7fc