linux内核SMP负载均衡浅析

柔光的暖阳◎ 2022-06-17 03:28 196阅读 0赞

**需求**  
      在《[linux进程调度浅析][linux]》一文中提到，在SMP（对称多处理器）环境下，每个CPU对应一个run\_queue（可执行队列）。如果一个进程处于TASK\_RUNNING状态（可执行状态），则它会被加入到其中一个run\_queue（且同一时刻仅会被加入到一个run\_queue），以便让调度程序安排它在这个run\_queue对应的CPU上面运行。  
      一个CPU对应一个run\_queue这样的设计，其好处是：  
  1、一个持续处于TASK\_RUNNING状态的进程总是趋于在同一个CPU上面运行（其间，这个进程可能被抢占、然后又被调度），这有利于进程的数据被CPU所缓存，提高运行效率；  
  2、各个CPU上的调度程序只访问自己的run\_queue，避免了竞争；  
      然而，这样的设计也可能使得各个run\_queue里面的进程不均衡，造成“一些CPU闲着、一些CPU忙不过来”混乱局面。为了解决这个问题，load\_balance（负载均衡）就登场了。  
  
      load\_balance所需要做的事情就是，在一定的时机，通过将进程从一个run\_queue迁移到另一个run\_queue，来保持CPU之间的负载均衡。  
      这里的“均衡”二字如何定义？load\_balance又具体要做哪些事情呢？对于不同调度策略（实时进程 OR 普通进程），有着不同的逻辑，需要分开来看。  
  
**实时进程的负载均衡**  
      实时进程的调度是严格按照优先级来进行的。在单CPU环境下，CPU上运行着的总是优先级最高的进程，直到这个进程离开TASK\_RUNNING状态，新任的“优先级最高的进程”才开始得到运行。直到所有实时进程都离开TASK\_RUNNING状态，其他普通进程才有机会得到运行。（暂时忽略sched\_rt\_runtime\_us和sched\_rt\_period\_us的影响，见《[linux组调度浅析][linux 1]》。）  
      推广到SMP环境，假设有N个CPU，N个CPU上分别运行着的也必须是优先级最高的top-N个进程。如果实时进程不足N个，那么剩下的CPU才分给普通进程去使用。对于实时进程来说，这就是所谓的“均衡”。  
      实时进程的优先级关系是很严格的，当优先级最高的top-N个进程发生变化时，内核必须马上响应：  
  1、如果这top-N个进程当中，有一个离开TASK\_RUNNING状态、或因为优先级被调低而退出top-N集团，则原先处于(N+1)位的那个进程将进入top-N。内核需要遍历所有的run\_queue，把这个新任的top-N进程找出来，然后立马让它开始运行；  
  2、反之，如果一个top-N之外的实时进程的优先级被调高，以至于挤占了原先处于第N位的进程，则内核需要遍历所有的run\_queue，把这个被挤出top-N的进程找出来，将它正在占用的CPU让给新进top-N的那个进程去运行；  
      在这几种情况下，新进入top-N的进程和退出top-N的进程可能原本并不在同一个CPU上，那么在它得到运行之前，内核会先将其迁移到退出top-N的进程所在的CPU上。  
      具体来说，内核通过pull\_rt\_task和push\_rt\_task两个函数来完成实时进程的迁移：  
  
      pull\_rt\_task - 把其他CPU的run\_queue中的实时进程pull过来，放到当前CPU的run\_queue中。被pull过来的实时进程要满足以下条件：  
  1、进程是其所在的run\_queue中优先级第二高的（优先级最高的进程必定正在运行，不需要移动）；  
  2、进程的优先级比当前run\_queue中最高优先级的进程还要高；  
  3、进程允许在当前CPU上运行（没有亲和性限制）；

该函数会在以下时间点被调用：  
  1、发生调度之前，如果prev进程（将要被替换下去的进程）是实时进程，且优先级高于当前run\_queue中优先级最高的实时进程（这说明prev进程已经离开TASK\_RUNNING状态了，否则它不会让位于比它优先级低的进程）；  
  2、正在运行的实时进程优先级被调低时（比如通过sched\_setparam系统调用）；  
  3、正在运行的实时进程变成普通进程时（比如通过sched\_setscheduler系统调用）；  
  
      push\_rt\_task - 把当前run\_queue中多余的实时进程推给其他run\_queue。需要满足以下条件：  
  1、每次push一个进程，这个进程的优先级在当前run\_queue中是第二高的（优先级最高的进程必定正在运行，不需要移动）；  
  2、目标run\_queue上正在运行的不是实时进程（是普通进程），或者是top-N中优先级最低的实时进程，且优先级低于被push的进程；  
  3、被push的进程允许在目标CPU上运行（没有亲和性限制）；  
  4、满足条件的目标run\_queue可能存在多个（可能多个CPU上都没有实时进程在运行），应该选择与当前CPU最具亲缘性的一组CPU中的第一个CPU所对应的run\_queue作为push的目标（顺着sched\_domain--调度域--逐步往上，找到第一个包含目标CPU的sched\_domain。见后面关于sched\_domain的描述）；  
      该函数会在以下时间点被调用：  
  1、非正在运行的普通进程变成实时进程时（比如通过sched\_setscheduler系统调用）；  
  2、发生调度之后（这时候可能有一个实时进程被更高优先级的实时进程抢占了）；  
  3、实时进程被唤醒之后，如果不能马上在当前CPU上运行（它不是当前CPU上优先级最高的进程）；  
  
      看起来，实时进程的负载均衡对于每个CPU一个run\_queue这种模式似乎有些别扭，每次需要选择一个实时进程，总是需要遍历所有run\_queue，在尚未能得到运行的实时进程之中找到优先级最高的那一个。其实，如果所有CPU共用同一个run\_queue，就没有这么多的烦恼了。为什么不这样做呢？  
  1、在CPU对run\_queue的竞争方面，“每个CPU去竞争每一个run\_queue”比“每个CPU去竞争一个总的run\_queue”略微好一些，因为竞争的粒度更小了；  
  2、在进程的移动方面，每个CPU一个run\_queue这种模式其实也不能很好的把进程留在同一个CPU上，因为严格的优先级关系使得进程必须在出现不均衡时立刻被移动。不过，一些特殊情况下进程的迁移还是有一定选择面的。比如优先级相同的时候就可以尽量不做迁移、push\_rt\_task的时候可以选择跟当前CPU最为亲近的CPU去迁移。  
  
**普通进程的负载均衡**  
      可以看出，实时进程的负载均衡性能是不会太好的。为了满足严格的优先级关系，丝毫的不均衡都是不能容忍的。所以一旦top-N的平衡关系发生变化，内核就必须即时完成负载均衡，形成新的top-N的平衡关系。这可能会使得每个CPU频繁去竞争run\_queue、进程频繁被迁移。  
      而普通进程则并不要求严格的优先级关系，可以容忍一定程度的不均衡。所以普通进程的负载均衡可以不必在进程发生变化时即时完成，而采用一些异步调整的策略。  
      普通进程的负载均衡在以下情况下会被触发：

1、当前进程离开TASK\_RUNNING状态（进入睡眠或退出），而对应的run\_queue中已无进程可用时。这时触发负载均衡，试图从别的run\_queue中pull一个进程过来运行；  
  2、每隔一定的时间，启动负载均衡过程，试图发现并解决系统中不均衡；  
      另外，对于调用exec的进程，它的地址空间已经完全重建了，当前CPU上已经不会再缓存对它有用的信息。这时内核也会考虑负载均衡，为它们找一个合适的CPU。  
  
      那么，对于普通进程来说，“均衡”到底意味着什么呢？  
      在单CPU环境下，处于TASK\_RUNNING状态的进程会以其优先级为权重，瓜分CPU时间。优先级越高的进程，权重越高，分得的CPU时间也就越多。在CFS调度（完全公平调度，针对普通进程的调度程序）中，这里的权重被称作load。假设某个进程的load为m，所有处于TASK\_RUNNING状态的进程的load之和为M，那么这个进程所能分到的CPU时间是m/M。比如系统中有两个TASK\_RUNNING状态的进程，一个load为1、一个load为2，总的load是1+2=3。则它们分到的CPU时间分别是1/3和2/3。  
      推广到SMP环境，假设有N个CPU，那么一个load为m的进程所能分到的CPU时间应该是N\*m/M（如果不是，则要么这个进程挤占了别的进程的CPU时间、要么是被别的进程挤占）。对于普通进程来说，这就是所谓的“均衡”。  
      那么，如何让进程能够分到N\*m/M的CPU时间呢？其实，只需要把所有进程的load平分到每一个run\_queue上，使得每个run\_queue的load（它上面的进程的load之和）都等于M/N，这样就好了。于是，每个run\_queue的load就成了是否“均衡”的判断依据。  
  
      下面看看load\_balance里面做些什么。注意，不管load\_balance是怎样被触发的，它总是在某个CPU上被执行。而load\_balance过程被实现得非常简单，只需要从最繁忙（load最高）的run\_queue中pull几个进程到当前run\_queue中（只pull，不push），使得当前run\_queue与最繁忙的run\_queue得到均衡（使它们的load接近于所有run\_queue的平均load），仅此而已。load\_balance并不需要考虑所有run\_queue全局的均衡，但是当load\_balance在各个CPU上分别得到运行之后，全局的均衡也就实现了。这样的实现极大程度减小了负载均衡的开销。  
  
      load\_balance的过程大致如下：  
  1、找出最繁忙的一个run\_queue；  
  2、如果找到的run\_queue比本地run\_queue繁忙，且本地run\_queue的繁忙程度低于平均水平，那么迁移几个进程过来，使两个run\_queue的load接近平均水平。反之则什么都不做；  
  
      在比较两个run\_queue繁忙程度的问题上，其实是很有讲究的。这个地方很容易想当然地理解为：把run\_queue中所有进程的load加起来，比较一下就OK了。而实际上，需要比较的往往并不是实时的load。  
      这就好比我们用top命令查看CPU占用率一样，top命令默认1秒刷新一次，每次刷新你将看到这1秒内所有进程各自对CPU的占用情况。这里的占用率是个统计值，假设有一个进程在这1秒内持续运行了100毫秒，那么我们认为它占用了10%的CPU。如果把1秒刷新一次改成1毫秒刷新一次呢？那么我们将有90%的机率看到这个进程占用0%的CPU、10%的机率占用100%的CPU。而无论是0%、还是100%，都不是这个进程真实的CPU占用率的体现。必须把一段时间以内的CPU占用率综合起来看，才能得到我们需要的那个值。  
      run\_queue的load值也是这样。有些进程可能频繁地在TASK\_RUNNING和非TASK\_RUNNING状态之间变换，导致run\_queue的load值不断抖动。光看某一时刻的load值，我们是体会不到run\_queue的负载情况的，必须将一段时间内的load值综合起来看才行。于是，run\_queue结构中维护了一个保存load值的数组：  
unsigned long cpu\_load\[CPU\_LOAD\_IDX\_MAX\] （目前CPU\_LOAD\_IDX\_MAX值为5）  
      每个CPU上，每个tick的时钟中断会调用到update\_cpu\_load函数，来更新该CPU所对应的run\_queue的cpu\_load值。这个函数值得罗列一下：  
   
/\* this\_load就是run\_queue实时的load值 \*/  
unsigned long this\_load = this\_rq->load.weight;  
for (i = 0, scale = 1; i < CPU\_LOAD\_IDX\_MAX; i++, scale += scale) \{  
    unsigned long old\_load = this\_rq->cpu\_load\[i\];  
    unsigned long new\_load = this\_load;  
    /\* 因为最终结果是要除以scale的，这里相当于上取整 \*/  
    if (new\_load > old\_load)  
        new\_load += scale-1;  
    /\* cpu\_load\[i\] = old\_load + (new\_load - old\_load) / 2^i \*/  
    this\_rq->cpu\_load\[i\] = (old\_load\*(scale-1) + new\_load) >> i;  
\}  
  
cpu\_load\[i\] = old\_load + (new\_load - old\_load) / 2^i。i值越大，cpu\_load\[i\]受load的实时值的影响越小，代表着越长时间内的平均负载情况。而cpu\_load\[0\]就是实时的load。  
   
      尽管我们需要的是一段时间内的综合的负载情况，但是，为什么不是保存一个最合适的统计值，而要保存这么多的值呢？这是为了便于在不同场景下选择不同的load。如果希望进行进程迁移，那么应该选择较小的i值，因为此时的cpu\_load\[i\]抖动比较大，容易发现不均衡；反之，如果希望保持稳定，那么应该选择较大的i值。  
      那么，什么时候倾向于进行迁移、什么时候又倾向于保持稳定呢？这要从两个维度来看：  
      第一个维度，是当前CPU的状态。这里会考虑三种CPU状态：  
  1、CPU刚进入IDLE（比如说CPU上唯一的TASK\_RUNNING状态的进程睡眠去了），这时候是很渴望马上弄一个进程过来运行的，应该选择较小的i值；  
  2、CPU处于IDLE，这时候还是很渴望弄一个进程过来运行的，但是可能已经尝试过几次都无果了，故选择略大一点的i值；  
  3、CPU非IDLE，有进程正在运行，这时候就不太希望进程迁移了，会选择较大的i值；  
      第二个维度，是CPU的亲缘性。离得越近的CPU，进程迁移所造成的缓存失效的影响越小，应该选择较小的i值。比如两个CPU是同一物理CPU的同一核心通过SMT（超线程技术）虚拟出来的，那么它们的缓存大部分是共享的。进程在它们之间迁移代价较小。反之则应该选择较大的i值。（后面将会看到[Linux][]通过调度域来管理CPU的亲缘性。）  
      至于具体的i的取值，就是具体策略的问题了，应该是根据经验或实验结果得出来的，这里就不赘述了。  
  
**调度域**  
      前面已经多次提到了调度域（sched\_domain）。在复杂的SMP系统中，为了描述CPU与CPU之间的亲缘关系，引入了调度域。  
      两个CPU之间的亲缘关系主要有以下几种：  
  1、超线程。超线程CPU是一个可以“同时”执行几个线程的CPU。就像[操作系统][Link 1]通过进程调度能够让多个进程“同时”在一个CPU上运行一样，超线程CPU也是通过这样的分时复用技术来实现几个线程的“同时”执行的。这样做之所以能够提高执行效率，是因为CPU的速度比内存速度快很多（一个数量级以上）。如果cache不能命中，CPU在等待内存的时间内将无事可做，可以切换到其他线程去执行。这样的多个线程对于操作系统来说就相当于多个CPU，它们共享着大部分的cache，非常之亲近；  
  2、同一物理CPU上的不同核心。现在的多核CPU大多属于这种情况，每个CPU核心都有独立执行程序的能力，而它们之间也会共享着一些cache；  
  3、同一NUMA结点上的CPU；  
  4、不同NUMA结点上的CPU；  
      在NUMA（非一致性内存体系）中，CPU和RAM以“结点”为单位分组。当CPU访问与它同在一个结点的“本地”RAM芯片时，几乎不会有竞争，访问速度通常很快。相反的，CPU访问它所属结点之外的“远程”RAM芯片就会非常慢。  
     （调度域可以支持非常复杂的硬件系统，但是我们通常遇到的SMP一般是：一个物理CPU包含N个核心。这种情况下，所有CPU之间的亲缘性都是相同的，引入调度域的意义其实并不大。）  
  
      进程在两个很亲近的CPU之间迁移，代价较小，因为还有一部分cache可以继续使用；在属于同一NUMA结点上的两个CPU之间迁移，虽然cache会全部丢失，但是好歹内存访问的速度是相同的；如果进程在属于不同NUMA结点的两个CPU之间迁移，那么这个进程将在新NUMA结点的CPU上被执行，却还是要访问旧NUMA结点的内存（进程可以迁移，内存却没法迁移），速度就要慢很多了。  
  
      通过调度域的描述，内核就可以知道CPU与CPU的亲缘关系。对于关系远的CPU，尽量少在它们之间迁移进程；而对于关系近的CPU，则可以容忍较多一些的进程迁移。  
      对于实时进程的负载均衡，调度域的作用比较小，主要是在push\_rt\_task将当前run\_queue中的实时进程推到其他run\_queue时，如果有多个run\_queue可以接收实时进程，则按照调度域的描述，选择亲缘性最高的那个CPU对应的run\_queue（如果这样的CPU有多个，那么约定选择编号最小那一个）。所以，下面着重讨论普通进程的负载均衡。  
  
      首先，调度域具体是如何描述CPU之间的亲缘关系的呢？假设系统中有两个物理CPU、每个物理CPU有两个核心、每个核心又通过超线程技术虚拟出两个CPU，则调度域的结构如下：

![Center][]

1、一个调度域是若干CPU的集合，这些CPU都是满足一定的亲缘关系的（比如至少是属于同一NUMA结点的）；  
  2、调度域之间存在层次关系，一个调度域可能包括多个子调度域，每个子调度域包含了父调度域的一个CPU子集，并且子调度域中的CPU满足比父调度域更严格的亲缘关系（比如父调度域中的CPU至少是属于同一NUMA结点的，子调度域中的CPU至少是属于同一物理CPU的）；  
  3、每个CPU分别具有其对应的一组sched\_domain结构，这些调度域处于不同层次，但是都包含了这个CPU；  
  4、每个调度域被依次划分成多个组，每个组代表调度域的一个CPU子集；  
  5、最低层次的调度域包含了亲缘性最近的几个CPU、而最低层次的调度组则只包含一个CPU；

对于普通进程的负载均衡来说，在一个CPU上，每次触发load\_balance总是在某个sched\_domain上进行的。低层次的sched\_domain包含的CPU有着较高的亲缘性，将以较高的频率被触发load\_balance；而高层次的sched\_domain包含的CPU有着较低的亲缘性，将以较低的频率被触发load\_balance。为了实现这个，sched\_domain里面记录着每次load\_balance的时间间隔，以及下次触发load\_balance的时间。  
      前面讨论过，普通进程的load\_balance第一步是需要找出一个最繁忙的CPU，实际上这是通过两个步骤来实现的：  
  1、找出sched\_domain下最繁忙的一个sched\_group（组内的CPU对应的run\_queue的load之和最高）；  
  2、从该sched\_group下找出最繁忙的CPU；  
      可见，load\_balance实际上是实现了对应sched\_domain下的sched\_group之间的平衡。较高层次的sched\_domain包含了很多CPU，但是在这个sched\_domain上的load\_balance并不直接解决这些CPU之间的负载均衡，而只是解决sched\_group之间的平衡（这又是load\_balance的一大简化）。而最底层的sched\_group是跟CPU一一对应的，所以最终还是实现了CPU之间的平衡。  
  
**其他问题  
CPU亲和力**  
      linux下的进程可以通过sched\_setaffinity系统调用设置进程亲和力，限定进程只能在某些特定的CPU上运行。负载均衡必须考虑遵守这个限制（前面也多次提到）。  
  
**迁移线程**  
      前面说到，在普通进程的load\_balance过程中，如果负载不均衡，当前CPU会试图从最繁忙的run\_queue中pull几个进程到自己的run\_queue来。  
      但是如果进程迁移失败呢？当失败达到一定次数的时候，内核会试图让目标CPU主动push几个进程过来，这个过程叫做active\_load\_balance。这里的“一定次数”也是跟调度域的层次有关的，越低层次，则“一定次数”的值越小，越容易触发active\_load\_balance。  
      这里需要先解释一下，为什么load\_balance的过程中迁移进程会失败呢？最繁忙run\_queue中的进程，如果符合以下限制，则不能迁移：  
  1、进程的CPU亲和力限制了它不能在当前CPU上运行；  
  2、进程正在目标CPU上运行（正在运行的进程显然是不能直接迁移的）；  
     （此外，如果进程在目标CPU上前一次运行的时间距离当前时间很小，那么该进程被cache的数据可能还有很多未被淘汰，则称该进程的cache还是热的。对于cache热的进程，也尽量不要迁移它们。但是在满足触发active\_load\_balance的条件之前，还是会先试图迁移它们。）  
      对于CPU亲和力有限制的进程（限制1），即使active\_load\_balance被触发，目标CPU也不能把它push过来。所以，实际上，触发active\_load\_balance的目的是要尝试把当时正在目标CPU上运行的那个进程弄过来（针对限制2）。  
  
      在每个CPU上都会运行一个迁移线程，active\_load\_balance要做的事情就是唤醒目标CPU上的迁移线程，让它执行active\_load\_balance的回调函数。在这个回调函数中尝试把原先因为正在运行而未能迁移的那个进程push过来。为什么load\_balance的时候不能迁移，active\_load\_balance的回调函数中就可以了呢？因为这个回调函数是运行在目标CPU的迁移线程上的。一个CPU在同一时刻只能运行一个进程，既然这个迁移线程正在运行，那么期望被迁移的那个进程肯定不是正在被执行的，限制2被打破。

当然，在active\_load\_balance被触发，到回调函数在目标CPU上被执行之间，目标CPU上的TASK\_RUNNING状态的进程可能发生一些变化，所以回调函数发起迁移的进程未必就只有之前因为限制2而未能被迁移的那一个，可能更多，也可能一个没有。

[linux]: http://blog.csdn.net/ctthunagchneg/article/details/8914309
[linux 1]: http://blog.csdn.net/ctthunagchneg/article/details/8914825
[Linux]: http://lib.csdn.net/base/linux
[Link 1]: http://lib.csdn.net/base/operatingsystem
[Center]: /images/20220617/b0f754192af44cd999731e4c20083f25.png