从源码到实践：彻底剖析Linux进程负载均衡机制
在当今的计算机领域，多核CPU早已成为主流配置。从早期的单核处理器到如今的 8 核、16 核甚至更多核心的CPU，硬件性能得到了极大提升。这种多核架构为计算机系统带来了强大的并行处理能力，使得多个任务可以同时高效运行。然而，多核 CPU 的性能优势并非能自动实现，如何充分利用这些核心资源，让各个进程在不同核心上合理分配与运行，成为了操作系统必须解决的关键问题。
在众多操作系统中，Linux 以其开源、稳定和高效等特点，被广泛应用于服务器、嵌入式设备以及超级计算机等领域。而 Linux 内核进程 CPU 负载均衡机制，就是其充分发挥多核 CPU 性能的核心技术之一。这一机制就像是一位智能的调度大师，时刻监控着系统中各个进程的运行状态以及各个 CPU 核心的负载情况，然后巧妙地将进程分配到最合适的 CPU 核心上运行，确保系统资源得到充分利用，避免出现某些核心忙得不可开交，而另一些核心却闲置无事的尴尬局面。
接下来，就让我们一起深入探索 Linux 内核进程 CPU 负载均衡机制，揭开它神秘的面纱，了解它是如何在幕后默默工作，为我们带来高效稳定的系统体验的。
一、CPU负载均衡机制
1.1什么是 CPU 负载
在深入探讨 Linux 内核进程 CPU 负载均衡机制之前，我们先来明确一个关键概念 ——CPU 负载。CPU 负载常常容易与 CPU 使用率、利用率混淆 ，这里我们来详细区分一下。CPU 利用率是指 CPU 处于忙碌状态的时间占总时间的比例。比如在 1000ms 的时间窗口内，如果 CPU 执行任务的时间为 500ms，处于空闲（idle）状态的时间也是 500ms，那么该时间段内 CPU 的利用率就是 50%。在 CPU 利用率未达到 100% 时，利用率与负载大致相等。
但当 CPU 利用率达到 100% 时，利用率就无法准确反映 CPU 负载状况了。因为此时不同 CPU 上的运行队列（runqueue）中等待执行的任务数目可能不同，直观来说，runqueue 中挂着 10 个任务的 CPU，其负载明显要比挂着 5 个任务的 CPU 更重。
早期，CPU 负载是用 runqueue 深度来描述的，也就是运行队列中等待执行的任务数量。不过这种方式比较粗略，例如 CPU A 和 CPU B 上都挂了 1 个任务，但 A 上的任务是重载任务，B 上的是经常处于睡眠（sleep）状态的轻载任务，仅依据 runqueue 深度来判断 CPU 负载就不准确了。
现代调度器通常使用 CPU runqueue 上所有任务负载之和来表示 CPU 负载 ，这样一来，对 CPU 负载的跟踪就转变为对任务负载的跟踪。在 3.8 版本的 Linux 内核中，引入了 PELT（per entity load tracking）算法，该算法能够跟踪每一个调度实体（sched entity）的负载，将负载跟踪算法从基于每个 CPU（per-CPU）进化到基于每个调度实体（per-entity）。PELT 算法不仅能知晓 CPU 的负载情况，还能明确负载来自哪个调度实体，从而实现更精准的负载均衡。
1.2何为均衡
明确了 CPU 负载的概念后，我们再来谈谈 “均衡”。负载均衡并非简单地将系统的总负载平均分配到各个 CPU 上。实际上，我们必须充分考虑系统中各个 CPU 的算力，使每个 CPU 所承担的负载与其算力相匹配。例如，在一个拥有 6 个小核和 2 个大核的系统中，假设系统总负载为 800，如果简单地给每个 CPU 分配 100 的负载，这其实是不均衡的，因为大核 CPU 能够提供更强的计算能力。
那么，什么是 CPU 算力（capacity）呢？算力是用来描述 CPU 能够提供的计算能力。在相同频率下，微架构为 A77 的 CPU 算力显然大于 A57 的 CPU。如果 CPU 的微架构相同，那么最大频率为 2.2GHz 的 CPU 算力肯定大于最大频率为 1.1GHz 的 CPU。通常，确定了微架构和最大频率，一个 CPU 的算力就基本确定了。虽然 Cpufreq 系统会根据当前的 CPU 利用率来调节 CPU 的运行频率，但这并不会改变 CPU 的算力，只有当 CPU 的最大运行频率发生变化时（比如触发温控，限制了 CPU 的最大频率），CPU 的算力才会随之改变。
在考虑 CFS（Completely Fair Scheduler，完全公平调度器）任务的均衡时，还需要把 CPU 用于执行实时任务（RT，Real - Time）和中断请求（irq）的算力去掉，使用该 CPU 可用于 CFS 的算力 。所以，CFS 任务均衡中使用的 CPU 算力是一个不断变化的值，需要经常更新。为了便于对比 CPU 算力和任务负载，我们采用归一化的方式，将系统中处理能力最强且运行在最高频率的 CPU 算力设定为 1024，其他 CPU 的算力则根据其微架构和运行频率进行相应调整。
有了任务负载和 CPU 算力，看似就能完成负载均衡工作了，但实际情况更为复杂。当负载不均衡时，任务需要在 CPU 之间迁移，而不同形态的迁移会产生不同的开销。比如，一个任务在小核集群内的 CPU 之间迁移，其性能开销肯定小于从小核集群的 CPU 迁移到大核集群的开销。因此，为了更有效地执行负载均衡，调度域（scheduling domain）和调度组（scheduling group）的概念被引入。调度域是一组 CPU 的集合，这些 CPU 在拓扑结构、性能等方面具有相似性；调度组则是在调度域内，根据更细粒度的规则划分的 CPU 集合。通过合理划分调度域和调度组，可以更精准地控制任务在 CPU 之间的迁移，降低迁移开销，实现更高效的负载均衡。
1.3何为负载
「负载」可不等同于 CPU 占用率，它衡量的是已经 ready，但在一段时间内得不到执行机会的任务数量。如果把CPU 比做车道的话，当有车辆排队等着进入这个车道，那负载就大于 1，反之则小于 1，它体现的其实是一种拥塞程度。
在 Linux 系统中，使用 "top" 或者 "w" 命令可以看到最近 1 分钟、5 分钟和 15 分钟的平均负载（没有做归一化处理，需要自己除以 CPU 的数目）。借助不同统计时段的平均负载值，还可以观察出负载变化的趋势。
一般认为，负载值大于 0.7 就应该引起注意，但对于 Linux 系统来说，情况可能有所不同，因为 Linux 中统计的负载值，除了处于就绪态的任务，还包括了处于 uninterruptible 状态、等待 I/O 的任务。
所以确切地说它不仅是 CPU load，而是 system load。如果因为 uninterruptible 的任务较多造成负载值看起来偏高，实际的系统在使用上也不见得就会出现明显的卡顿。
负载均衡有两种方式：pull, push
pull拉：负载轻的CPU，从负载繁重的CPU pull tasks来运行。这应该是主要的方式，因为不应该让负载本身就繁重的CPU执行负载均衡任务。相应的为load balance。push推：负载重的CPU，向负载轻的CPU，推送tasks由其帮忙执行。相应的为active balance。但是迁移是有代价的。在同一个物理CPU的两个logical core之间迁移，因为共享cache，代价相对较小。如果是在两个物理CPU之间迁移，代价就会增大。更进一步，对于NUMA系统，在不同node之间的迁移将带来更大的损失；这其实形成了一个调度上的约束，在Linux中被实现为"sched domain"，并以hierarchy的形式组织。处于同一内层domain的，迁移可以更频繁地进行，越往外层，迁移则应尽可能地避免。
1.4负载均衡的作用
负载均衡在 Linux 系统中起着至关重要的作用，对系统性能和稳定性有着显著的提升。如果没有有效的负载均衡机制，当系统中某个 CPU 核心的负载过高，而其他核心却闲置时，就会导致整个系统性能下降。高负载的核心可能会因为任务过多而出现响应变慢、处理延迟等问题，严重时甚至可能导致系统崩溃。
例如，在一个 Web 服务器中，如果所有的 HTTP 请求处理任务都集中在某一个 CPU 核心上，随着请求量的增加，这个核心很快就会不堪重负，服务器的响应时间会大幅延长，用户访问网站时会感觉到明显的卡顿，甚至无法访问。
而通过负载均衡机制，将这些任务均匀地分配到各个 CPU 核心上，每个核心都能充分发挥其计算能力，共同承担系统的工作负载。这样不仅可以避免单个核心过度劳累，还能大大提高系统的整体处理能力和响应速度。以刚才的 Web 服务器为例，负载均衡机制会将 HTTP 请求合理地分发到多个 CPU 核心上进行处理，每个核心都能高效地处理一部分请求，服务器就能快速响应用户的访问，提升用户体验。
负载均衡还有助于提高系统资源的利用率。在多核 CPU 系统中，每个核心都是宝贵的资源。通过负载均衡，能够确保这些资源得到充分利用，避免出现资源闲置浪费的情况。当一个 CPU 核心的负载过高时，负载均衡机制会将部分任务迁移到其他相对空闲的核心上，使得整个系统的资源分配更加合理，从而提高系统的整体运行效率。这就好比一个工厂里有多个工人（CPU 核心），如果所有的工作都交给一个工人做，其他工人却闲着没事干，那显然是对人力资源的浪费。而通过合理的任务分配（负载均衡），让每个工人都能承担适量的工作，就能充分发挥整个工厂的生产能力。
1.5为何均衡
作为OS的心跳，只要不是NO_HZ的CPU，tick都会如约而至，这为判断是否需要均衡提供了一个绝佳的时机。不过，如果在每次tick时钟中断都去做一次balance，那开销太大了，所以balance的触发是有一个周期要求的。当tick到来的时候，在scheduler_tick函数中会调用trigger_load_balance来触发周期性负载均衡，相关的代码如下：
进行调度和均衡本身也是需要消耗CPU的资源，因此比较适合交给idle的CPU来完成，idle_cpu被选中的这个idle CPU被叫做"idle load balancer"。
系统中有多个idle的cpu，如何选择执行nohz idle balance的那个CPU呢？
如果不考虑功耗，那么就从所有idle cpu中选择一个就可以了，但是在异构的系统中，我们应该要考虑的更多，如果idle cpu中有大核也有小核，是选择大核还是选择小核？大核CPU虽然算力强，但是功耗高。如果选择小核，虽然能省功耗，但是提供的算力是否足够。标准内核选择的最简单的算法：随便选择一个idle cpu（也就是idle cpu mask中的第一个）。
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 牵扯的事情还是蛮多的。
二、CPU负载均衡机制原理
2.1相关数据结构与关键函数
在 Linux 内核进程 CPU 负载均衡机制中，有一些关键的数据结构和函数起着至关重要的作用。
runqueue 队列是其中一个重要的数据结构。在多处理器系统中，每个 CPU 都拥有自己的 runqueue 队列 ，这个队列就像是一个任务等待执行的 “候诊室”，里面存放着处于运行状态（run）的进程链表。当一个进程准备好运行时，它就会被加入到某个 CPU 的 runqueue 队列中。例如，当我们在系统中启动一个新的应用程序时，该程序对应的进程就会被添加到某个 CPU 的 runqueue 队列里，等待 CPU 的调度执行。
调度域（sched domain）和调度组（sched group）负载均衡的复杂性主要和复杂的系统拓扑有关。由于当前CPU很忙，我们把之前运行在该CPU上的一个任务迁移到新的CPU上的时候，如果迁移到新的CPU是和原来的CPU在不同的cluster中，性能会受影响（因为会cache会变冷）。但是对于超线程架构，cpu共享cache，这时候超线程之间的任务迁移将不会有特别明显的性能影响。
NUMA上任务迁移的影响又不同，我们应该尽量避免不同NUMA node之间的任务迁移，除非NUMA node之间的均衡达到非常严重的程度。总之，一个好的负载均衡算法必须适配各种cpu拓扑结构。为了解决这些问题，linux内核引入了sched_domain的概念。
调度组： 调度组是组成调度域的基本单位，在最小的调度域中一个cpu core是一个调度组，在最大的调度域中，一个NUMA结点内的所有cpu core成一个调度组。
sched_domain（调度域）也是一个核心数据结构。为了适应多种多处理器模型，Linux 引入了调度域及组的概念。一个调度域可以包含其他的调度域或者多个组 ，它是一组 CPU 的集合，这些 CPU 在拓扑结构、性能等方面具有相似性。通过调度域，内核能够更好地管理和协调不同 CPU 之间的负载均衡。
例如，在一个具有多个 CPU 核心的系统中，可能会根据 CPU 的性能和拓扑关系，将某些核心划分为一个调度域，这样在进行负载均衡时，可以优先在这个调度域内进行任务的迁移和分配，减少跨调度域迁移带来的开销。
调度域的数据结构定义如下：
调度域并不是一个平层结构，而是根据CPU拓扑形成层级结构。相对应的，负载均衡也不是一蹴而就的，而是会在多个sched domain中展开（例如从base domain开始，一直到顶层sched domain，逐个domain进行均衡）。
内核中struct sched_domain来描述调度域，其主要的成员如下：
Parent和child：Sched domain会形成层级结构，parent和child建立了不同层级结构的父子关系。对于base domain而言，其child等于NULL，对于top domain而言，其parent等于NULL。groups：一个调度域中有若干个调度组，这些调度组形成一个环形链表，groups成员就是链表头。min_interval和max_interval：做均衡也是需要开销的，我们不可能时刻去检查调度域的均衡状态，这两个参数定义了检查该sched domain均衡状态的时间间隔范围。busy_factor：正常情况下，balance_interval定义了均衡的时间间隔，如果cpu繁忙，那么均衡要时间间隔长一些，即时间间隔定义为busy_factor x balance_interval。imbalance_pct：调度域内的不均衡状态达到了一定的程度之后就开始进行负载均衡的操作。imbalance_pct这个成员定义了判定不均衡的门限。cache_nice_tries：这个成员应该是和nr_balance_failed配合控制负载均衡过程的迁移力度。当nr_balance_failed大于cache_nice_tries的时候，负载均衡会变得更加激进。nohz_idle：每个cpu都有其对应的LLC sched domain，而LLC SD记录对应cpu的idle状态（是否tick被停掉），进一步得到该domain中busy cpu的个数，体现在（sd->shared->nr_busy_cpus）。flags：调度域标志，下面有表格详细描述。level：该sched domain在整个调度域层级结构中的level。Base sched domain的level等于0，向上依次加一。last_balance：上次进行balance的时间点。通过基础均衡时间间隔（）和当前sd的状态可以计算最终的均衡间隔时间（get_sd_balance_interval），last_balance加上这个计算得到的均衡时间间隔就是下一次均衡的时间点。balance_interval：定义了该sched domain均衡的基础时间间隔nr_balance_failed：本sched domain中进行负载均衡失败的次数。当失败次数大于cache_nice_tries的时候，我们考虑迁移cache hot的任务，进行更激进的均衡操作。max_newidle_lb_cost：在该domain上进行newidle balance的最大时间长度（即newidle balance的开销）。最小值是sysctl_sched_migration_cost。next_decay_max_lb_cost：max_newidle_lb_cost会记录最近在该sched domain上进行newidle balance的最大时间长度，这个max cost不是一成不变的，它有一个衰减过程，每秒衰减1%，这个成员就是用来控制衰减的。avg_scan_cost：平均扫描成本调度域并不是一个平层结构，而是根据CPU拓扑形成层级结构。相对应的，负载均衡也不是一蹴而就的，而是会在多个sched domain中展开（例如从base domain开始，一直到顶层sched domain，逐个domain进行均衡）。具体如何进行均衡（自底向上还是自顶向下，在哪些domain中进行均衡）是和均衡类型和各个sched domain设置的flag相关，具体细节后面会描述。
在指定调度域内进行均衡的时候不考虑系统中其他调度域的CPU负载情况，只考虑该调度域内的sched group之间的负载是否均衡。对于base doamin，其所属的sched group中只有一个cpu，对于更高level的sched domain，其所属的sched group中可能会有多个cpu core。
与之相关的是 sched_group（调度组），一个组通常包含一个或者多个 CPU 。组的数据结构通过cpumask_t来表示该组所包含的 CPU，还通过next指针将多个sched_group串到调度域的链表上面。其数据结构定义如下：
在函数方面，load_balance函数是实现负载均衡的关键函数之一。当系统检测到 CPU 负载不均衡时，就会调用load_balance函数。它的主要工作是寻找最繁忙的 CPU 组中的最繁忙的 CPU ，然后将其进程迁移一部分到其他相对空闲的 CPU 上。例如，在一个四核系统中，如果发现 CPU0 的负载过高，而 CPU1、CPU2 和 CPU3 相对空闲，load_balance函数就会尝试从 CPU0 的 runqueue 队列中挑选一些进程，迁移到 CPU1、CPU2 或 CPU3 的 runqueue 队列中，以实现负载的均衡。
rebalance_tick函数也在负载均衡中扮演着重要角色。每经过一次时钟中断，scheduler_tick函数就会调用rebalance_tick函数 。rebalance_tick函数会从最底层的调度域开始，一直到最上层的调度域进行检查，对于每个调度域，它会查看是否到了调用load_balance函数的时间。如果到了合适的时间，就会触发负载均衡操作。同时，它还会根据当前 CPU 的 idle 状态和sched_domain的参数来确定调用load_balance的时间间隔。
当 CPU 处于空闲状态时，会以较高的频率调用load_balance（可能 1、2 个时钟节拍） ，以便尽快将其他 CPU 上的任务迁移过来，充分利用空闲的 CPU 资源；而当 CPU 处于忙碌状态时，则会以较低的频率调用load_balance（可能 10 - 100ms ），避免过度频繁的负载均衡操作影响系统性能。
2.3任务调度算法（以 CFS 为例）
在 Linux 内核中，任务调度算法是实现 CPU 负载均衡的核心部分，其中完全公平调度（CFS，Completely Fair Scheduler）算法被广泛应用于普通进程的调度。
CFS 算法的核心思想是将任务看作红黑树节点进行排序和调度 ，以实现公平的 CPU 资源分配。在 CFS 中，每个进程都有一个虚拟运行时间（vruntime）的概念，这个虚拟运行时间是衡量进程已经获得的 CPU 服务量的指标。当新创建一个任务时，会赋予其初始的 vruntime 值 ；随着程序的执行，vruntime 会不断累加。
对于等待更长时间未被执行过的轻载任务来说，其 vruntime 值会相对较低，这样的任务会被放置于红黑树的左侧位置，以便尽快得到 CPU 的服务机会。这就好比在一场比赛中，那些等待起跑时间较长的选手（任务），会被安排在更有利的起跑位置（红黑树左侧），从而更有可能先起跑（先获得 CPU 执行时间）。
CFS 调度器选取待运行的下一个进程时，会选择具有最小 vruntime 的任务 ，因为这个任务的虚拟运行时间最短，也就意味着它获得的 CPU 时间最少，最需要被调度执行。而红黑树这种数据结构的特性使得每次插入、删除操作都能保持在 O (log n) 的时间复杂度 ，从而保证了在大量进程存在的情况下，依然能高效地查找和调度具有最小 vruntime 的任务。例如，在一个拥有 1000 个进程的系统中，CFS 调度器通过红黑树能够快速地找到 vruntime 最小的进程，将其调度到 CPU 上执行，而不会因为进程数量的增加导致调度效率大幅下降。
在考虑 CPU 核心负载差异分配任务方面，CFS 算法会综合多个因素。首先，它会关注每个 CPU 核心的负载情况，尽量将任务分配到负载较轻的核心上。如果某个 CPU 核心的 runqueue 队列中任务过多，负载较重，CFS 调度器会尝试将新的任务分配到其他负载相对较轻的核心上，以避免某个核心过度繁忙。其次，CFS 算法还会考虑进程的特性，比如进程的优先级（通过 nice 值体现） 。较高的 nice 值（较低的优先级）进程会获得更低的处理器使用权重 ，在分配任务时，会相对优先调度 nice 值较低（优先级较高）的进程，以保证系统中重要任务能够及时得到执行。
2.4负载均衡的触发时机
负载均衡的触发时机对于保证系统性能至关重要，Linux 内核主要通过以下两种情况来触发负载均衡。
（1)当某个 CPU 的 runqueue 为空时当某个 CPU 的 runqueue 队列中一个可运行进程都没有时，就说明这个 CPU 处于空闲状态，无事可做。这时，为了充分利用 CPU 资源，系统会从其他 CPU 的 runqueue 中获取任务 。例如，在一个双核系统中，假设 CPU0 上的 runqueue 队列中有多个可运行进程，而 CPU1 的 runqueue 队列为空。
那么，CPU1 就会调用load_balance函数，发现在 CPU0 上还有许多进程等待运行，于是它会从 CPU0 上的可运行进程里找到优先级最高的进程，将其拿到自己的 runqueue 里开始执行。这样，原本空闲的 CPU1 就可以利用起来，分担系统的工作负载，提高系统的整体处理能力。
(2)周期性检查每经过一个时钟节拍，内核会调用scheduler_tick函数 ，这个函数会执行许多重要的任务，例如减少当前正在执行的进程的时间片，以确保每个进程都能公平地获得 CPU 时间。在scheduler_tick函数的结尾处，则会调用rebalance_tick函数 ，rebalance_tick函数决定了以什么样的频率执行负载均衡。
具体来说，rebalance_tick函数会从当前 CPU 所属的调度域开始，依次遍历各个更高级的调度域。对于每个调度域，它会检查是否满足调用load_balance函数的条件。这里的条件主要基于时间间隔和负载情况。每个调度域都有一个balance_interval参数 ，表示负载均衡进行的时间间隔。同时，还会根据当前 CPU 的 idle 状态来调整这个时间间隔。
当 idle 标志位是SCHED_IDLE时，表示当前 CPU 处理器空闲 ，此时会以很高的频率来调用load_balance（通常是 1、2 个时钟节拍） ，因为空闲的 CPU 需要尽快获取任务来执行，避免资源浪费；反之，表示当前 CPU 并不空闲，会以很低的频率调用load_balance（一般是 10 - 100ms ），因为在 CPU 忙碌时，频繁进行负载均衡操作可能会增加系统开销，影响系统性能。
例如，假设一个调度域的balance_interval设置为 50ms ，当 CPU 处于忙碌状态时，rebalance_tick函数会每隔 50ms 检查一次是否需要进行负载均衡。如果当前时间戳与上次执行负载均衡的时间戳之差大于等于 50ms ，并且经过一系列的负载检查和判断，发现存在负载不均衡的情况，就会调用load_balance函数进行负载均衡操作，将任务从负载重的 CPU 迁移到负载轻的 CPU 上，以实现系统负载的均衡。
三、负载均衡的软件架构
负载均衡模块主要分两个软件层次：核心负载均衡模块和class-specific均衡模块。内核对不同的类型的任务有不同的均衡策略，普通的CFS（complete fair schedule）任务和RT、Deadline任务处理方式是不同的，由于篇幅原因，本文主要讨论CFS任务的负载均衡。
为了更好的进行CFS任务的均衡，系统需要跟踪CFS任务负载、各个sched group的负载及其CPU算力（可用于CFS任务运算的CPU算力）。跟踪任务负载是主要有两个原因：
判断该任务是否适合当前CPU算力如果判定需要均衡，那么需要在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架构以及通信路径来进行的。
四、CPU负载均衡机制实现方式
4.1如何做负载均衡
我们以一个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。
4.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的均衡大致需要下面几个步骤：
找到MC domain中最繁忙的sched group找到最繁忙sched group中最繁忙的CPU（对于MC domain而言，这一步不存在，毕竟其sched group只有一个cpu）从选中的那个繁忙的cpu上拉取任务，具体拉取多少的任务到本CPU runqueue上是和不均衡的程度相关，越是不均衡，拉取的任务越多。完成MC domain均衡之后，继续沿着sched domain层级结构向上检查，进入DIE domain，在这个level的domain上，我们仍然检查其所属sched group之间（即各个cluster之间）的负载均衡情况，如果有不均衡的情况，那么会进行inter-cluster的任务迁移。基本方法和MC domain类似，只不过在计算均衡的时候，DIE domain不再考虑单个CPU的负载和算力，它考虑的是：
该sched group的负载，即sched group中所有CPU负载之和该sched group的算力，即sched group中所有CPU算力之和4.3线程的负载均衡
在 Linux 内核进程 CPU 负载均衡机制中，线程的负载均衡是确保系统高效运行的关键环节，它主要针对实时（RT，Real - Time）任务和普通任务采取不同的策略。
⑴RT 任务RT 任务对时间的要求极为严格，需要确保能够及时响应和执行。在 Linux 系统中，对于 RT 任务的负载均衡，采用了一种高效的分配方式，即把 n 个优先级最高的 RT 任务自动分配到 n 个核上 。这是因为 RT 任务的实时性要求决定了它们需要尽快得到 CPU 的执行机会，将这些高优先级的 RT 任务分散到多个核心上，可以避免任务之间的竞争和延迟，确保每个任务都能在最短的时间内得到处理。
在实际实现过程中，主要通过pull_rt_task和push_rt_task这两个函数来完成任务的迁移操作 。当系统中出现新的高优先级 RT 任务时，会调用push_rt_task函数，将任务推送到相对空闲的 CPU 核心上，以确保任务能够及时执行；而当某个 CPU 核心上的 RT 任务执行完毕，或者负载过高需要调整时，则会调用pull_rt_task函数，从其他核心上拉取合适的 RT 任务到当前核心，从而实现负载的均衡。这种基于任务优先级的分配方式，能够充分利用多核 CPU 的并行处理能力，保证 RT 任务的实时性需求，使得系统在处理对时间敏感的任务时，能够保持高效稳定的运行状态。
⑵普通任务普通任务的负载均衡则主要通过周期性负载均衡、idle 时负载均衡以及 fork 和 exec 时负载均衡这几种方式来实现。
周期性负载均衡是在时钟 tick 到来时进行的 。每当时钟 tick 发生，系统就会检查各个核的负载情况，优先让空闲核工作。如果发现某个核处于空闲状态，而其他核负载较重，就会从负载重的核中pull任务到空闲核，或者将空闲核的任务push给负载较轻的核 。例如，在一个四核系统中，假设 CPU0 和 CPU1 负载较高，而 CPU2 和 CPU3 处于空闲状态。当时钟 tick 到来时，系统会检测到这种负载不均衡的情况，然后从 CPU0 和 CPU1 的 runqueue 队列中挑选一些普通任务，迁移到 CPU2 和 CPU3 上执行，这样就能让各个核都能参与到任务处理中，避免出现部分核过度忙碌，而部分核闲置的情况，从而实现系统负载的均衡。
idle 时负载均衡是当某个核进入 idle 状态时触发的 。当一个核进入 idle 状态，说明它当前没有可执行的任务，处于空闲状态。此时，这个核会主动去检查其他核的负载情况，如果发现其他核有任务在运行，就会主动从其他核pull任务过来执行 。例如，在一个八核系统中，假设 CPU5 进入 idle 状态，它会查看其他七个核的 runqueue 队列，发现 CPU3 上有较多的普通任务在等待执行，那么 CPU5 就会从 CPU3 的 runqueue 队列中选取一些任务，将其迁移到自己的队列中并开始执行，这样可以充分利用空闲的 CPU 资源，提高系统的整体处理能力。
fork 和 exec 时负载均衡则与新进程的创建和执行密切相关 。当系统执行 fork 操作创建一个新进程，或者通过 exec 函数族执行新的程序时，会把新创建的进程放到最闲的核上去运行 。这是因为新进程在启动阶段可能需要进行一些初始化操作，将其分配到最闲的核上，可以避免对其他正在忙碌执行任务的核造成额外的负担，同时也能让新进程尽快获得 CPU 资源，顺利完成初始化和后续的执行操作。例如，当我们在系统中启动一个新的应用程序时，系统会根据各个核的负载情况，将这个新程序对应的进程分配到当前负载最轻的核上运行，确保新进程能够高效启动和运行。
4.4中断负载均衡
在 Linux 系统中，负载不仅来源于进程，中断也是重要的负载来源之一。中断分为硬件中断和软中断，它们在系统运行中起着不同但又紧密相关的作用。
硬件中断通常是由外部设备（如网卡、硬盘、键盘等）引发的信号，用于通知 CPU 有需要立即处理的事件 。例如，当网卡接收到数据时，会产生一个硬件中断，通知 CPU 有新的数据到达需要处理。硬件中断的处理时间一般较短，在 Linux 2.6.34 版本之后，内核不再支持中断嵌套 。
当硬件中断发生并完成数据接收等操作后，通常会调用软中断来进行后续的处理，比如处理 TCP/IP 包 。软中断可以嵌套，它主要负责处理那些可以稍微延迟处理的任务，是对硬件中断未完成工作的一种推后执行机制。在top命令中，hi表示硬中断时间（isr，屏蔽中断），si表示软中断 。当网络流量较大时，CPU 花在硬中断和软中断上的时间会比较多，此时就需要进行中断的负载均衡，以确保系统的高效运行。
在新网卡多队列的情况下，实现中断负载均衡可以通过设置中断亲和性来完成 。例如，在一个 4 核的系统中，如果网卡有 4 个队列，每个队列都可以单独产生中断，并且硬件支持负载均衡 。那么可以将一个队列绑定到一个核上，通过将每个中断号分别设置 affinity，绑定到指定 CPU，就能让所有 CPU 都参与到网卡发送包服务中 。
比如，通过查看/proc/interrupts文件找到与网卡相关的中断号，然后使用命令sudo sh -c “echo 3 > /proc/irq/124/smp_affinity”，就可以将中断号为 124 的中断绑定到 CPU3 上 。这样，当网卡的不同队列产生中断时，就会被分配到不同的 CPU 核心上进行处理，避免了所有中断都集中在一个核心上，从而实现了中断的负载均衡，提高了系统处理网络数据的能力。
然而，有些网卡只有一个队列，这种情况下，单个核抛出的软中断只能在这个核上运行，导致一个队列抛出的软中断（如 TCP/IP 层处理）只能在这一个核执行，其他核会处于空闲状态，无法充分利用多核 CPU 的优势。为了解决这个问题，Google 推出了 RPS（Receive Packet Steering）补丁 。RPS 补丁的原理是由单一 CPU 核响应硬件中断，然后将大量网络接收包通过多核间中断方式分发给其他空闲核 。
例如，在一个单核网卡队列收包的系统中，默认情况下收包操作只在 CPU0 上执行。通过设置 RPS，如echo 3 > /sys/class/net/eth0/queues/rx-0/rps_cpus，可以将收包操作均衡到 CPU0 和 CPU1 上 。这样，当大量网络数据包到达时，原本只能由一个核处理的任务，现在可以由多个核共同处理，大大提高了系统处理网络数据的效率，实现了软中断的负载均衡，充分发挥了多核 CPU 的性能优势。
4.5其他需要考虑的事项
之所以要进行负载均衡主要是为了系统整体的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处于较低的频率运行，功耗会比方案一更低。
