1.6如何均衡
要实现多核系统的负载均衡，主要依靠 task 在不同 CPU 之间的迁移（migration），也就是将一个 task 从负载较重的 CPU 上转移到负载相对较轻的 CPU 上去执行。从 CPU 的 runqueue 上取下来的这个动作，称为 "pull"，放到另一个 CPU 的 runqueue 上去，则称之为 "push"。
但是迁移是有代价的，而且这个迁移的代价还不一样。AMP 系统里每个 CPU 的 capacity 可能不同，而 SMP 系统里看起来每个 CPU 都是一样的，按理好像应该视作一个数组，拉通来调度。但现实是：现代 SMP 的拓扑结构，决定了 CPU 之间的 cache 共享是不同的，cache 共享越多，迁移的“阻力”越小，反之就越大。
在同一个物理 core 的两个 logical CPU 之间迁移，因为共享 L1 和 L2 cache，阻力相对较小。对于NUMA系统，如果是在同一 node 中的两个物理 core 之间迁移，共享的是 L3 cache 和内存，损失就会增大（AMD 的 Zen 系列芯片存在同一 node 的物理 core 不共享 L3 的情况）。更进一步，在不同 node 之间的迁移将付出更大的代价。
就像一个人换工作的时候，往往会优先考虑同一个公司的内部职位，因为只是转岗的话，公司内的各种环境都是熟悉的。再是考虑同一个城市的其他公司，因为不用搬家嘛。可能最后才是考虑其他城市/国家的，毕竟 relocate 牵扯的事情还是蛮多的。
【文章福利】小编推荐自己的Linux内核技术交流群:【 865977150】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！
二、负载均衡的软件架构
负载均衡的整体软件结构图如下：
负载均衡模块主要分两个软件层次：核心负载均衡模块和class-specific均衡模块。内核对不同的类型的任务有不同的均衡策略，普通的CFS（complete fair schedule）任务和RT、Deadline任务处理方式是不同的，由于篇幅原因，本文主要讨论CFS任务的负载均衡。
为了更好的进行CFS任务的均衡，系统需要跟踪CFS任务负载、各个sched group的负载及其CPU算力（可用于CFS任务运算的CPU算力）。跟踪任务负载是主要有两个原因：
（1）判断该任务是否适合当前CPU算力
（2）如果判定需要均衡，那么需要在CPU之间迁移多少的任务才能达到平衡？有了任务负载跟踪模块，这个问题就比较好回答了。
为了更好的进行高效的均衡，我们还需要构建调度域的层级结构（sched domain hierarchy），图中显示的是二级结构（这里给的是逻辑结构，实际内核中的各个level的sched domain是per cpu的）。手机场景多半是二级结构，支持NUMA的服务器场景可能会形成更复杂的结构。通过DTS和CPU topo子系统，我们可以构建sched domain层级结构，用于具体的均衡算法。
在手机平台上，负载均衡会进行两个level：MC domain的均衡和DIE domain的均衡。在MC domain上，我们会对跟踪每个CPU负载状态（sched group只有一个CPU）并及时更新其算力，使得每个CPU上有其匹配的负载。在DIE domain上，我们会跟踪cluster上所有负载（每个cluster对应一个sched group）以及cluster的总算力，然后计算cluster之间负载的不均衡状况，通过inter-cluster迁移让整个DIE domain进入负载均衡状态。
有了上面描述的基础设施，那么什么时候进行负载均衡呢？这主要和调度事件相关，当发生任务唤醒、任务创建、tick到来等调度事件的时候，我们可以检查当前系统的不均衡情况，并酌情进行任务迁移，以便让系统负载处于平衡状态。
负载均衡成本开销
首先需要了解下CPU核心之间的数据流通信原理，这样就能大概知道CPU中的Core之间的进程迁移之间的开销
由于NUMA是以层次关系呈现，因此在执行进程的负载均衡也会呈现不同的成本开销。进程在同一个物理Core上的逻辑Core之前迁移开销最小；
如果在不同的物理Core之间迁移,如果每个物理Core拥有私有的L1 Cache,共享L2 Cache,进程迁移后就无法使用原来的L1 Cache，进程迁移到新的Core上缺失L1 Cache数据，这就需要进程的状态数据需要在CPU Core之间进行通信获取这些数据，根据上图CPU的通信模式可以了解，成本代价是蛮大的。
内核采用调度域解决现代多CPU多核的问题，调度域是具有相同属性和调度策略的处理器集合，任务进程可以在它们内部按照某种策略进行调度迁移。
进程在多CPU的负载均衡也是针对调度域的，调度域根据超线程、多核、SMP、NUMA等系统架构划分为不同的等级，不同的等级架构通过指针链接在一起，从而形成树状结构；在进程的负载均衡过程中，从树的叶子节点往上遍历，直到所有的域中的负载都是平衡的。目前内核进程调度按照如下的原则进行,这些原则都是按照cpu架构以及通信路径来进行的。
三、如何做负载均衡
3.1一个CPU拓扑示例
我们以一个4小核+4大核的处理器来描述CPU的domain和group：
在上面的结构中，sched domain是分成两个level，base domain称为MC domain（multi core domain），顶层的domain称为DIE domain。顶层的DIE domain覆盖了系统中所有的CPU，小核cluster的MC domain包括所有小核cluster中的cpu，同理，大核cluster的MC domain包括所有大核cluster中的cpu。
对于小核MC domain而言，其所属的sched group有四个，cpu0、1、2、3分别形成一个sched group，形成了MC domain的sched group环形链表。不同CPU的MC domain的环形链表首元素（即sched domain中的groups成员指向的那个sched group）是不同的，对于cpu0的MC domain，其groups环形链表的顺序是0-1-2-3，对于cpu1的MC domain，其groups环形链表的顺序是1-2-3-0，以此类推。大核MC domain也是类似，这里不再赘述。
对于非base domain而言，其sched group有多个cpu，覆盖其child domain的所有cpu。例如上面图例中的DIE domain，它有两个child domain，分别是大核domain和小核domian，因此，DIE domain的groups环形链表有两个元素，分别是小核group和大核group。不同CPU的DIE domain的环形链表首元素（即链表头）是不同的，对于cpu0的DIE domain，其groups环形链表的顺序是（0,1,2,3）--（4,5,6,7），对于cpu6的MC domain，其groups环形链表的顺序是（4,5,6,7）--（0,1,2,3），以此类推。
为了减少锁的竞争，每一个cpu都有自己的MC domain和DIE domain，并且形成了sched domain之间的层级结构。在MC domain，其所属cpu形成sched group的环形链表结构，各个cpu对应的MC domain的groups成员指向环形链表中的自己的cpu group。在DIE domain，cluster形成sched group的环形链表结构，各个cpu对应的DIE domain的groups成员指向环形链表中的自己的cluster group。
3.2负载均衡的基本过程
负载均衡不是一个全局CPU之间的均衡，实际上那样做也不现实，当系统的CPU数量较大的时候，很难一次性的完成所有CPU之间的均衡，这也是提出sched domain的原因之一。我们以周期性均衡为例来描述负载均衡的基本过程。当一个CPU上进行周期性负载均衡的时候，我们总是从base domain开始（对于上面的例子，base domain就是MC domain），检查其所属sched group之间（即各个cpu之间）的负载均衡情况，如果有不均衡情况，那么会在该cpu所属cluster之间进行迁移，以便维护cluster内各个cpu core的任务负载均衡。
有了各个CPU上的负载统计以及CPU的算力信息，我们很容易知道MC domain上的不均衡情况。为了让算法更加简单，Linux内核的负载均衡算法只允许CPU拉任务，这样，MC domain的均衡大致需要下面几个步骤：
- （1）找到MC domain中最繁忙的sched group
- （2）找到最繁忙sched group中最繁忙的CPU（对于MC domain而言，这一步不存在，毕竟其sched group只有一个cpu）
- （3）从选中的那个繁忙的cpu上拉取任务，具体拉取多少的任务到本CPU runqueue上是和不均衡的程度相关，越是不均衡，拉取的任务越多。
完成MC domain均衡之后，继续沿着sched domain层级结构向上检查，进入DIE domain，在这个level的domain上，我们仍然检查其所属sched group之间（即各个cluster之间）的负载均衡情况，如果有不均衡的情况，那么会进行inter-cluster的任务迁移。基本方法和MC domain类似，只不过在计算均衡的时候，DIE domain不再考虑单个CPU的负载和算力，它考虑的是：
- （1）该sched group的负载，即sched group中所有CPU负载之和
- （2）该sched group的算力，即sched group中所有CPU算力之和
3.3其他需要考虑的事项
之所以要进行负载均衡主要是为了系统整体的throughput，避免出现一核有难，七核围观的状况。然而，进行负载均衡本身需要额外的算力开销，为了降低开销，我们为不同level的sched domain定义了时间间隔，不能太密集的进行负载均衡。之外，我们还定义了不均衡的门限值，也就是说domain的group之间如果有较小的不均衡，我们也是可以允许的，超过了门限值才发起负载均衡的操作。很显然，越高level的sched domain其不均衡的threashhold越高，越高level的均衡会带来更大的性能开销。
在引入异构计算系统之后，任务在placement的时候可以有所选择。如果负载比较轻，或者该任务对延迟要求不高，我们可以放置在小核CPU执行，如果负载比较重或者该该任务和用户体验相关，那么我们倾向于让它在算力更高的CPU上执行。为了应对这种状况，内核引入了misfit task的概念。一旦任务被标记了misfit task，那么负载均衡算法要考虑及时的将该任务进行upmigration，从而让重载任务尽快完成，或者提升该任务的执行速度，从而提升用户体验。
除了性能，负载均衡也会带来功耗的收益。例如系统有4个CPU，共计8个进入执行态的任务（负载相同）。这些任务在4个CPU上的排布有两种选择：
- （1）全部放到一个CPU上
- （2）每个CPU runqueue挂2个任务
负载均衡算法会让任务均布，从而带来功耗的收益。虽然方案一中有三个CPU是处于idle状态的，但是那个繁忙CPU运行在更高的频率上。而方案二中，由于任务均布，CPU处于较低的频率运行，功耗会比方案一更低。
四、负载均衡场景分析
4.1整体的场景描述
在linux内核中，为了让任务均衡的分布在系统的所有CPU上，我们主要考虑下面三个场景：
（1）负载均衡（load balance）。通过搬移cpu runqueue上的任务，让各个CPU上的负载匹配CPU算力。
（2）任务放置（task placement）。当阻塞的任务被唤醒的时候，确定该任务应该放置在那个CPU上执行
（3）主动均衡（active upmigration）。当一个低算力CPU的runqueue中出现misfit task的时候，如果该任务持续执行，那么负载均衡无能为力，因为它只负责迁移runnable状态的任务。这种场景下，active upmigration可以把当前正在运行的misfit task向上迁移到算力更高的CPU上去。
4.2Task placement
任务放置主要发生在：
- （1）唤醒一个新fork的线程
- （2）Exec一个线程的时候
- （3）唤醒一个阻塞的进程
在上面的三个场景中都会调用select_task_rq来为task选择一个适合的CPU core。
4.3Load balance
Load balance主要有三种：
（1）在tick中触发load balance。我们称之tick load balance或者periodic load balance。具体的代码执行路径是：
（2）调度器在pick next的时候，当前cfs runque中没有runnable，只能执行idle线程，让CPU进入idle状态。我们称之new idle load balance。具体的代码执行路径是：
（3）其他的cpu已经进入idle，本CPU任务太重，需要通过ipi将其idle的cpu唤醒来进行负载均衡。我们称之nohz idle load banlance，具体的代码执行路径是：
如果没有dynamic tick特性，那么其实不需要进行nohz idle load balance，因为tick会唤醒处于idle的cpu，从而周期性tick就可以覆盖这个场景。
4.4Active upmigration
主动迁移是Load balance的一种特殊场景。在负载均衡中，只要运用适当的同步机制（持有一个或者多个rq lock），runnable的任务可以在各个CPU runqueue之间移动，然而running的任务是例外，它不挂在CPU runqueue中，load balance无法覆盖。为了能够迁移running状态的任务，内核提供了Active upmigration的方法（利用stop machine调度类）。这个feature原生内核没有提供，故不再详述。
精品文章推荐阅读：
