CFS任务的负载均衡（概述）

CFS任务的负载均衡（概述）

我们描述负载均衡的系列文章一共三篇，第一篇是框架部分，即本文，主要描述了负载均衡相关的原理、场景和框架。后面的两篇是对均衡代码的情景分析，通过对tick balance、new idle balance和task placement等几个典型的负载均衡来呈现其实现细节，稍后发布，敬请期待。

本文出现的内核代码来自Linux5.10.61，如果有兴趣，读者可以配合代码阅读本文。

一、什么是负载均衡

1、什么是CPU负载（load）

CPU load是一个很容易和CPU usage混淆的概念。CPU usage是CPU忙闲的比例，例如在一个周期为1000ms的窗口中观察CPU的情况，如果500ms的时间在执行任务，500ms的时间处于idle状态，那么在这个窗口中CPU的usage是50%。CPU usage是一个直观的概念，

所见即所得，然而它不能用来对比。

例如一个任务在小核300MHz频率下执行1000ms，看到CPU usage是100%，同样的任务，在大核3GHz下的执行50ms，CPU usage是5%。

这种场景下，同样的任务，load是一样的，但是CPU usage差别很大。CPU 利用率（utility）是另外一个容易混淆的概念。Utility和usage的共同点都是考虑了running time，区别是Utility进行了归一化，即把running time归一化到了系统中最大算力（超大核最高频率）上的执行时间。为了能和CPU capacity进行运算，utility还归一化到了1024。

CPU load和utility一样，都进行了归一化，但是概念还是不同的。Utility是一个和busy time（运行时间）相关的量，在CPU利用率没有达到100%的时候，利用率基本上等于负载，利用率高的时候负载也大，一旦当CPU利用率达到了100%的时候，利用率其实是无法给出CPU负载的状况，因为大家的利用率都是100%，利用率相等，但是并不意味着CPUs的负载也是相等的，因为这时候不同CPU上runqueue中等待执行的任务数目不同，直觉上runque上挂着10任务的CPU承压比挂着5个任务的CPU的负载要更重一些。因此，早期的CPU负载是使用runqueue深度来描述的。

3.8版本的linux内核引入了PELT算法来跟踪每一个sched entity的负载，把负载跟踪的算法从per-CPU进化到per-entity。PELT算法不但能知道CPU的负载，而且知道负载来自哪一个调度实体，从而可以更精准的进行负载均衡。

2、什么是均衡

对于负载均衡而言，并不是把整个系统的负载平均的分配到系统中的各个CPU上。实际上，我们还是必须要考虑系统中各个CPU的算力，让CPU获得和其算力匹配的负载。例如在一个6个小核+2个大核的系统中，整个系统如果有800的负载，那么每个CPU上分配100的负载其实是不均衡的，因为大核CPU可以提供更强的算力。

什么是CPU算力（capacity），所谓算力就是描述CPU的能够提供的计算能力。在同样的频率下，一个微架构是A77的CPU显然算力要大于A57的CPU。如果CPU的微架构都是一样的，那么一个最大频率是2.2GHz的CPU算力肯定是大于最大频率是1.1GHz的CPU。因此，确定了微架构和最大频率，一个CPU的算力就基本确定了。struct rq数据结构中有两个和算力相关的成员：

Cpufreq系统会根据当前的CPU util来调节CPU当前的运行频率，也许触发温控，限制了该CPU的最大频率，但这并不能改变cpu_capacity_orig。本文主要描述CFS任务的均衡（RT的均衡不考虑负载，是在另外的维度），因此均衡需要考虑的CPU算力是cpu_capacity，这个算力需要把CPU用于执行rt、dl、irq的算力以及温控损失的算力去掉，即该CPU可用于CFS任务的算力。

因此，CFS任务均衡中使用的CPU算力（cpu_capacity成员）其实一个不断变化的值，需要经常更新（参考update_cpu_capacity函数）。为了让CPU算力和utility可以对比，实际上我们采用了归一化的方式，即系统中处理能力最强的CPU运行在最高频率的算力是1024，其他的CPU算力根据微架构和最大运行频率相应的进行调整。

有了各个任务负载，将runqueue中的任务负载累加起来就可以得到CPU负载，配合系统中各个CPU的算力，看起来我们就可以完成负载均衡的工作，然而事情没有那么简单，当负载不均衡的时候，任务需要在CPU之间迁移，不同形态的迁移会有不同的开销。

例如一个任务在小核cluster上的CPU之间的迁移所带来的性能开销一定是小于任务从小核cluster的CPU迁移到大核cluster的开销。因此，为了更好的执行负载均衡，我们需要构建和CPU拓扑相关的数据结构，也就是调度域和调度组的概念。

3、调度域（sched domain）和调度组（sched group）

负载均衡的复杂性主要和复杂的系统拓扑有关。由于当前CPU很忙，我们把之前运行在该CPU上的一个任务迁移到新的CPU上的时候，如果迁移到新的CPU是和原来的CPU在不同的cluster中，性能会受影响（因为会cache会变冷）。但是对于超线程架构，cpu共享cache，这时候超线程之间的任务迁移将不会有特别明显的性能影响。NUMA上任务迁移的影响又不同，我们应该尽量避免不同NUMA node之间的任务迁移，除非NUMA node之间的均衡达到非常严重的程度。总之，一个好的负载均衡算法必须适配各种cpu拓扑结构。为了解决这些问题，linux内核引入了sched_domain的概念。

内核中struct sched_domain来描述调度域，其主要的成员如下：