整理代码基于Linux源码v5.12.13，后面的代码解释是我在本地ppt上直接截图贴上来的，可能有点糊。

有问题可以留言或者漂流瓶联系我。。。

调度域 & 调度组

Linux调度域主要分为三层，可以理解为下一层的调度域（domain）成为新的调度组（group）合并入上一层的调度域。

简单看一下调度域结构体里面的几个属性，后面会用得到：

1. parent/child ：父/子调度域

2. last_balance ：上次balance的时间

3. balance_interval ：balance时间间隔

CPU runqueue

每个cpu都会有一个运行队列，其上存储着在当前CPU上处于就绪和运行状态的进程。

其上的进程包含三个种类的队列，按照优先级顺序分别为dl，rt 和 cfs。

其余的结构体内包含信息如图所示，只列出了和本文相关的部分变量。

负载均衡整体流程

这部分简要介绍一下负载均衡的整体流程，不会涉及到具体代码细节。

如果只是想知道一下流程，那么看完这一段就可以直接左上角了。

1. 调度器的初始化：会对每个cpu的runqueue内容进行初始化，包括调度域，下次调度时间等等，初始化过程中会给rq结构体的next_balance赋予初值，用于后续判断是否需要进行负载均衡，该值在后续执行负载均衡函数调用之后会进行更新。

2. 定时器中断处理函数调用scheduler_tick函数，此函数是所有调度子函数的父函数，是大多数调度函数的源，在此函数内会调用trigger_load_balance函数触发负载均衡的流程。

3. 在trigger_load_balance函数内会判断是否已经到达当前cpu的rq的负载均衡时间点（next_balance），如果达到就会提交一个软中断。处理软中断时会调用相应的软中断处理函数，当前cpu就成为负载均衡的dst_cpu。

4. 在软中断处理函数中会调用函数rebalance_domains，在函数内部会对当前cpu的相关调度域进行遍历（遍历它及它的父调度域），对比是否达到了当前调度域（domain）的负载均衡时间点，从而决定是否需要真正进行负载均衡。

5. 然后在该调度域中找到最忙的调度组，在此调度组中找到最忙的cpu队列，此cpu即为负载均衡的src_cpu。

6. 接下来，就是将src cpu上的一部分负载拉取到dst cpu上即可。

具体代码调用流程

这部分会详细贴出整个负载均衡过程中函数的调用流程，对于关键的部分使用红色边框圈起来并进行了介绍。代码的截图基本上都保留对应的文件名称和代码行数，感兴趣的可以去内核源码看一看。

调度初始化：sched_init

在start_kernel中对调度器进行初始化的函数就是sched_init，初始化过程中会给next_balance赋予初值，用于后续判断是否需要进行负载均衡，该值在后续执行负载均衡函数调用之后会进行更新。

定时器调用scheduler_tick

scheduler_tick()是所有调度子函数的父函数，而其是由Linux时间子系统的tick_device调用。tick_device是一个周期性定时器，定时时间为1个tick，当触发中断后，会在中断处理函数中，调用scheduler_tick()。

而打开了tickless，即动态tick后，那么就会切换至oneshot模式，并负责调用scheduler_tick()。

注：定时器运行在单触发模式（one-shot mode），与周期模式（periodic mode）运行的定时器不同，周期模式运行的定时器，只要对它进行一次初始化操作，以后定时器就会周期的产生中断，不再需要额外的对定时器进行编程操作；而当定时器运行于单触发模式下时，每当定时器产生一次中断后就不再运行，系统再根据当前任务对时间的要求计算出定时器下一次应该产生中断的时间间隔，然后再对定时器进行编程，使它能在系统要求的将来某一时刻产生中断。在单触发模式下，定时器的定时精度能达到微秒级。不过需要注意的是，由于每次中断后都要计算下一次中断的时间，而且还要对定时器进行编程，这两个操作会降低系统的性能。

scheduler_tick

scheduler_tick 是所有调度子函数的父函数，是大多数调度函数的源。

trigger_load_balance

CPU对应的运行队列数据结构中记录了下一次周期性负载均衡的时间，当超过这个时间点后，将触发SCHED_SOFTIRQ软中断来进行负载均衡。

本质上就是判断一下当前的jiffies是不是已经比rq->next_balance值大，如果值大的话，会进一步调用raise_softirq提交一个软中断。提交的过程很简单，就是把SCHED_SOFTIRQ对应的位置位，处理软中断时检查是否位，如果置位调用相应的软中断处理函数。

关于 cpu_active ，我简单查了一下，不确定正确性：

When CPU entered 1st step, i.e. the CPU_DOWN_PREPARE, the scheduler marks it as not 'active', but it's still 'online' at the moment. Scheduler could not migrate any task to it at this time. After the CPU is totally removed, it's not 'online' anymore

软中断处理函数

没啥好说的，就是两步调用。

rebalance_domains

load_balance

先列出load_balance函数的总体流程，之后涉及到的关键函数会在之后进行详细介绍。

以上就是负载均衡执行的整体流程了。

下面简要介绍一下其中涉及到的几个函数的具体实现。

should_we_balance

该函数主要用于判断当前cpu是否需要进行负载均衡：

首先需要明确一点的是，负载均衡执行到当前cpu时，是判断当前cpu是否需要执行负载均衡从其他cpu处pull task过来，或者可以说，dst_cpu在这一轮操作中是确定的，就是当前cpu。

而should_we_balance则是用于判断当前cpu需不需要进行负载均衡。

有几种情况：

1. 如果当前cpu状态为NEWLY IDLE，即目前CPU上没有可运行的task，准备进入idle 的状态，此时需要做load balance。

2. 否则寻找当前cpu所在的调度组上的第一个空闲的cpu，然后判断这个空闲的cpu和dst_cpu（即当前cpu）是否是同一个cpu，如果是，则需要进行负载均衡，否则不需要。

3. 如果没有idle cpu的话，就判断当前cpu是否是其所在调度组的第一个cpu，如果是，则需要进行负载均衡，否则不需要。

find_businest_group

该函数的主要作用就是找到调度域内最忙的调度组。

介绍该函数之前先简单看一下两个数据结构，具体作用图里已经很清楚了哈。

然后，find_businest_group函数总体流程大致如下：

接下来简要介绍一下，其中的update_sd_lb_stats函数

update_sd_lb_stats

统计各个group的负载，并得到最businest的group