后面的调度学习都是默认在单个 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.dtsicpus: 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 intbuild_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