共计 8544 个字符，预计需要花费 22 分钟才能阅读完成。
后面的调度学习都是默认在单个 CPU 上的调度策略。咱们晓得为了 CPU 之间缩小“烦扰”，每个 CPU 上都有一个工作队列。运行的过程种可能会呈现有的 CPU 很忙，有的 CPU 很闲，如下图所示：
为了防止这个问题的呈现，Linux 内核实现了 CPU 可运行过程队列之间的负载平衡。
因为负载平衡是在多个核上的平衡，所以在解说负载平衡之前，咱们先看下多核的架构。
将 task 从负载较重的 CPU 上转移到负载绝对较轻的 CPU 上执行，这个过程就是负载平衡的过程。
多核架构
这里以 Arm64 的 NUMA(Non Uniform Memory Access) 架构为例，看下多核架构的组成。
从图中能够看出，这是非一致性内存拜访。每个 CPU 拜访 local memory，速度更快，提早更小。因为 Interconnect 模块的存在，整体的内存会形成一个内存池，所以 CPU 也能拜访 remote memory，然而绝对 local memory 来说速度更慢，提早更大。
咱们晓得一个多外围的 SOC 片上零碎，内部结构是很简单的。内核采纳 CPU 拓扑构造来形容一个 SOC 的架构，应用调度域和调度组来形容 CPU 之间的档次关系。
LinuxC++ 后盾服务器开发架构师收费学习地址
【文章福利】：小编整顿了一些集体感觉比拟好的学习书籍、视频材料共享在群文件外面，有须要的能够自行添加哦！~ 点击退出（须要自取）
CPU 拓扑
每一个 CPU 都会保护这么一个构造体实例，用来形容 CPU 拓扑。
struct cpu_topology {
int thread_id;
int core_id;
int cluster_id;
cpumask_t thread_sibling;
cpumask_t core_sibling;
};
thread_id: 从 mpidr_el1 寄存器中获取
core_id：从 mpidr_el1 寄存器中获取
cluster_id：从 mpidr_el1 寄存器中获取
thread_sibling：以后 CPU 的兄弟 thread。core_sibling：以后 CPU 的兄弟 Core，即在同一个 Cluster 中的 CPU。能够通过 /sys/devices/system/cpu/cpuX/topology 查看 cpu topology 的信息。cpu_topology 构造体是通过函数 parse_dt_topology() 解析 DTS 中的信息建设的:
kernel_init() -> kernel_init_freeable() -> smp_prepare_cpus() -> init_cpu_topology() -> parse_dt_topology()
static int __init parse_dt_topology(void)
{
struct device_node *cn, *map;
int ret = 0;
int cpu;
cn = of_find_node_by_path("/cpus"); ------(1)
if (!cn) {pr_err("No CPU information found in DT\n");
return 0;
}
/*
* When topology is provided cpu-map is essentially a root
* cluster with restricted subnodes.
*/
map = of_get_child_by_name(cn, "cpu-map"); ------(2)
if (!map)
goto out;
ret = parse_cluster(map, 0); ------(3)
if (ret != 0)
goto out_map;
topology_normalize_cpu_scale();
/*
* Check that all cores are in the topology; the SMP code will
* only mark cores described in the DT as possible.
*/
for_each_possible_cpu(cpu)
if (cpu_topology[cpu].cluster_id == -1)
ret = -EINVAL;
out_map:
of_node_put(map);
out:
of_node_put(cn);
return ret;
}找到 dts 中 cpu topology 的根节点 “/cpus”
找到 “cpu-map” 节点
解析 “cpu-map” 中的 cluster
以 i.mx8qm 为例，topology 为：”4A53 + 2A72”，dts 中定义如下：
# imx8qm.dtsi
cpus: cpus {
#address-cells = <2>;
#size-cells = <0>;
A53_0: cpu@0 {
device_type = "cpu";
compatible = "arm,cortex-a53", "arm,armv8";
reg = <0x0 0x0>;
clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A53_L2>;
operating-points-v2 = <&a53_opp_table>;
#cooling-cells = <2>;
};
A53_1: cpu@1 {
device_type = "cpu";
compatible = "arm,cortex-a53", "arm,armv8";
reg = <0x0 0x1>;
clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A53_L2>;
operating-points-v2 = <&a53_opp_table>;
#cooling-cells = <2>;
};
A53_2: cpu@2 {
device_type = "cpu";
compatible = "arm,cortex-a53", "arm,armv8";
reg = <0x0 0x2>;
clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A53_L2>;
operating-points-v2 = <&a53_opp_table>;
#cooling-cells = <2>;
};
A53_3: cpu@3 {
device_type = "cpu";
compatible = "arm,cortex-a53", "arm,armv8";
reg = <0x0 0x3>;
clocks = <&clk IMX_SC_R_A53 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A53_L2>;
operating-points-v2 = <&a53_opp_table>;
#cooling-cells = <2>;
};
A72_0: cpu@100 {
device_type = "cpu";
compatible = "arm,cortex-a72", "arm,armv8";
reg = <0x0 0x100>;
clocks = <&clk IMX_SC_R_A72 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A72_L2>;
operating-points-v2 = <&a72_opp_table>;
#cooling-cells = <2>;
};
A72_1: cpu@101 {
device_type = "cpu";
compatible = "arm,cortex-a72", "arm,armv8";
reg = <0x0 0x101>;
clocks = <&clk IMX_SC_R_A72 IMX_SC_PM_CLK_CPU>;
enable-method = "psci";
next-level-cache = <&A72_L2>;
operating-points-v2 = <&a72_opp_table>;
#cooling-cells = <2>;
};
A53_L2: l2-cache0 {compatible = "cache";};
A72_L2: l2-cache1 {compatible = "cache";};
cpu-map {
cluster0 {
core0 {cpu = <&A53_0>;};
core1 {cpu = <&A53_1>;};
core2 {cpu = <&A53_2>;};
core3 {cpu = <&A53_3>;};
};
cluster1 {
core0 {cpu = <&A72_0>;};
core1 {cpu = <&A72_1>;};
};
};
};
通过 parse_dt_topology()，update_siblings_masks() 解析后失去 cpu_topology 的值为：
CPU0: cluster_id = 0, core_id = 0
CPU1: cluster_id = 0, core_id = 1
CPU2: cluster_id = 0, core_id = 2
CPU3: cluster_id = 0, core_id = 3
CPU4: cluster_id = 1, core_id = 0
CPU5: cluster_id = 1, core_id = 1
调度域和调度组
在 Linux 内核中，调度域应用 sched_domain 构造示意，调度组应用 sched_group 构造示意。
调度域 sched_domain
struct sched_domain {
struct sched_domain *parent;
struct sched_domain *child;
struct sched_group *groups;
unsigned long min_interval;
unsigned long max_interval;
...
};parent：因为调度域是分层的，下层调度域是上层的调度域的父亲，所以这个字段指向的是以后调度域的下层调度域。
child：如上所述，这个字段用来指向以后调度域的上层调度域。
groups：每个调度域都领有一批调度组，所以这个字段指向的是属于以后调度域的调度组列表。
min_interval/max_interval：做平衡也是须要开销的，不能时刻去查看调度域的平衡状态，这两个参数定义了查看该 sched domain 平衡状态的工夫距离的范畴
sched_domain 是分成两个 level，base domain 称为 MC domain（multi core domain），顶层 domain 称为 DIE domain。
调度组 sched_group
struct sched_group {
struct sched_group *next;
unsigned int group_weight;
...
struct sched_group_capacity *sgc;
unsigned long cpumask[0];};
next：指向属于同一个调度域的下一个调度组。
group_weight：该调度组中有多少个 cpu。
sgc：该调度组的算力信息。
cpumask：用于标记属于以后调度组的 CPU 列表（每个位示意一个 CPU）。
为了缩小锁的竞争，每一个 CPU 都有本人的 MC domain、DIE domain 以及 sched_group，并且造成了 sched_domain 之间的层级构造，sched_group 的环形链表构造。CPU 对应的调度域和调度组可通过在设施模型文件 /proc/sys/kernel/sched_domain 里查看。
具体的 sched_domain 的初始化代码剖析如下：
kernel_init() -> kernel_init_freeable() -> sched_init_smp() -> init_sched_domains(cpu_active_mask) -> build_sched_domains(doms_cur[0], NULL)
static int
build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
{
enum s_alloc alloc_state;
struct sched_domain *sd;
struct s_data d;
int i, ret = -ENOMEM;
alloc_state = __visit_domain_allocation_hell(&d, cpu_map); ------(1)
if (alloc_state != sa_rootdomain)
goto error;
/* Set up domains for CPUs specified by the cpu_map: */
for_each_cpu(i, cpu_map) {
struct sched_domain_topology_level *tl;
sd = NULL;
for_each_sd_topology(tl) {sd = build_sched_domain(tl, cpu_map, attr, sd, i); ------(2)
if (tl == sched_domain_topology)
*per_cpu_ptr(d.sd, i) = sd;
if (tl->flags & SDTL_OVERLAP)
sd->flags |= SD_OVERLAP;
}
}
/* Build the groups for the domains */
for_each_cpu(i, cpu_map) {for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {sd->span_weight = cpumask_weight(sched_domain_span(sd));
if (sd->flags & SD_OVERLAP) {if (build_overlap_sched_groups(sd, i))
goto error;
} else {if (build_sched_groups(sd, i)) ------(3)
goto error;
}
}
}
......
/* Attach the domains */
rcu_read_lock();
for_each_cpu(i, cpu_map) {int max_cpu = READ_ONCE(d.rd->max_cap_orig_cpu);
int min_cpu = READ_ONCE(d.rd->min_cap_orig_cpu);
sd = *per_cpu_ptr(d.sd, i);
if ((max_cpu < 0) || (cpu_rq(i)->cpu_capacity_orig >
cpu_rq(max_cpu)->cpu_capacity_orig))
WRITE_ONCE(d.rd->max_cap_orig_cpu, i);
if ((min_cpu < 0) || (cpu_rq(i)->cpu_capacity_orig <
cpu_rq(min_cpu)->cpu_capacity_orig))
WRITE_ONCE(d.rd->min_cap_orig_cpu, i);
cpu_attach_domain(sd, d.rd, i); ------(4)
}
rcu_read_unlock();
if (!cpumask_empty(cpu_map))
update_asym_cpucapacity(cpumask_first(cpu_map));
ret = 0;
error:
__free_domain_allocs(&d, alloc_state, cpu_map); ------(5)
return ret;
}在每个 tl 档次，给每个 CPU 调配 sd、sg、sgc 空间
遍历 cpu_map 里所有 CPU，创立与物理拓扑构造对应的多级调度域
遍历 cpu_map 里所有 CPU, 创立调度组
将每个 CPU 的 rq 与 rd(root_domain) 进行绑定
free 掉调配失败或者调配胜利多余的内存
所以，可运行过程队列与调度域和调度组的关系如下图所示：
总结
这里用一张图来总结下 CPU 拓扑，调度域初始化的过程，如下所示：
依据曾经生成的 CPU 拓扑，调度域和调度组，最终能够生成如下图所示的关系图。
在下面的构造中，顶层的 DIE domain 笼罩了零碎中所有的 CPU，4 个 A53 是 Cluster 0，共享 L2 cache，两外 2 个 A72 是 Cluster 1，共享 L2 cache。那么每个 Cluster 能够认为是一个 MC 调度域，右边的 MC 调度域中有 4 个调度组，左边的 MC 调度域中有 2 个调度组，每个调度组中只有 1 个 CPU。整个 SOC 能够认为是高一级别的 DIE 调度域，其中有两个调度组，Cluster 0 属于一个调度组，Cluster 1 属于另一个调度组。跨 Cluster 的负载平衡是须要革除 L2 cache 的，开销是很大的，因而 SOC 级别的 DIE 调度域进行负载平衡的开销比 MC 调度域更大一些。
到目前为止，咱们曾经将内核的调度域构建起来了，CFS 能够利用 sched_domain 来实现多核间的负载平衡了。
何时做负载平衡？
CFS 工作的负载均衡器有两种：
一种是针对 busy CPU 的 periodic balancer，用于过程在 busy CPU 上的平衡
一种是针对 idle CPU 的 idle balancer，用于把 busy CPU 上的过程平衡到 idle CPU 上来。
periodic balancer：周期性负载平衡是在时钟中断 scheduler_tick 中，找到该 domain 中最忙碌的 sched group 和 CPU runqueue，将其上的工作 pull 到本 CPU，以便让零碎的负载处于平衡的状态。
nohz idle balancer：当其余的 CPU 曾经进入 idle，本 CPU 工作太重，须要通过 IPI 将其余 idle 的 CPU 唤醒来进行负载平衡。
new idle balancer：本 CPU 上没有工作执行，马上要进入 idle 状态的时候，看看其余 CPU 是否须要帮忙，来从 busy cpu 上 pull 工作，让整个零碎的负载处于平衡状态。
负载平衡的根本过程
当一个 CPU 上进行负载平衡的时候，总是从 base domain 开始，查看其所属 sched group 之间的负载平衡状况，如果有不平衡状况，那么会在该 CPU 所属 Cluster 之间进行迁徙，以便保护 Cluster 内各个 CPU 的工作负载平衡。
load_balance 是解决负载平衡的外围函数，它的处理单元是一个调度域，其中会蕴含对调度组的解决。
static int load_balance(int this_cpu, struct rq *this_rq,
struct sched_domain *sd, enum cpu_idle_type idle,
int *continue_balancing)
{
......
redo:
if (!should_we_balance(&env)) {
*continue_balancing = 0;
goto out_balanced;
}
group = find_busiest_group(&env); ------(1)
if (!group) {schedstat_inc(sd->lb_nobusyg[idle]);
goto out_balanced;
}
busiest = find_busiest_queue(&env, group); ------(2)
if (!busiest) {schedstat_inc(sd->lb_nobusyq[idle]);
goto out_balanced;
}
BUG_ON(busiest == env.dst_rq);
schedstat_add(sd->lb_imbalance[idle], env.imbalance);
env.src_cpu = busiest->cpu;
env.src_rq = busiest;
ld_moved = 0;
if (busiest->nr_running > 1) {
env.flags |= LBF_ALL_PINNED;
env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running);
more_balance:
rq_lock_irqsave(busiest, &rf);
update_rq_clock(busiest);
cur_ld_moved = detach_tasks(&env); ------(3)
rq_unlock(busiest, &rf);
if (cur_ld_moved) {attach_tasks(&env); ------(4)
ld_moved += cur_ld_moved;
}
local_irq_restore(rf.flags);
if (env.flags & LBF_NEED_BREAK) {
env.flags &= ~LBF_NEED_BREAK;
goto more_balance;
}
......
}
......
out:
return ld_moved;
}找到该 domain 中最忙碌的 sched group
在这个最忙碌的 group 中筛选最忙碌的 CPU runqueue, 作为 src
从这个队列中抉择工作来迁徙，而后把被选中的工作从其所在的 runqueue 中移除
从最忙碌的 CPU runqueue 中 pull 一些工作到以后可运行队列 dst
