容量感知调度
1. CPU容量
1.1 简介
传统的同质 SMP 平台由纯粹相同的 CPU 组成。另一方面，异构平台由具有不同性能特征的 CPU 组成 - 在这样的平台上，并非所有 CPU 都可以被视为相等。
CPU 容量是衡量 CPU 可达到的性能的指标，与系统中性能最强的 CPU 进行了归一化。异构系统也被称为不对称 CPU 容量系统，因为它们包含具有不同容量的 CPU。
最大可达性能（即最大 CPU 容量）的差异源自两个因素：
- 并非所有 CPU 可能具有相同的微架构（µarch）。
- 通过动态电压和频率调节（DVFS），并非所有 CPU 可能在物理上达到更高的操作性能点（OPP）。
Arm big.LITTLE 系统就是这样的一个例子。大核心 CPU 比 LITTLE 核心更注重性能（拥有更多的流水线阶段、更大的缓存、更智能的预测器等），通常可以达到比 LITTLE 核心更高的 OPP。
CPU 性能通常以每秒百万条指令数（MIPS）来表示，也可以表示为每赫兹可达到的指令数量，从而得到以下公式：
容量（CPU）= 每赫兹工作量（CPU）* 最大频率（CPU）
1.2 调度器术语
调度器内部使用两个不同的容量值。CPU 的 capacity_orig 是其最大可达容量，即其最大可达性能水平。CPU 的 capacity 是其 capacity_orig 减去一些可用性能损失（例如处理 IRQ 所花费的时间）。
请注意，CPU 的 capacity 仅打算供 CFS 类使用，而 capacity_orig 则与类别无关。本文档的其余部分将为简洁起见将术语 capacity 与 capacity_orig 互换使用。
1.3 平台示例
1.3.1 相同的 OPPs
考虑一个假想的双核不对称 CPU 容量系统，其中：
- work_per_hz(CPU0) = W
- work_per_hz(CPU1) = W/2
- 所有 CPU 都以相同的固定频率运行
根据上述容量的定义：
- capacity(CPU0) = C
- capacity(CPU1) = C/2
以 Arm big.LITTLE 为例，CPU0 将是大核心，而 CPU1 将是 LITTLE 核心。
对于一个周期性执行固定量工作负载，将得到一个执行跟踪，如下所示：
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU1 work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU0 在系统中具有最高的容量（C），在 T 单位时间内完成了固定量的工作 W。另一方面，CPU1 的容量是 CPU0 的一半，因此在 T 单位时间内只完成了 W/2 的工作。
1.3.2 不同的最大 OPPs
通常，具有不同容量值的 CPU 也具有不同的最大 OPPs。考虑上述相同的 CPU（即相同的 work_per_hz()）：
- max_freq(CPU0) = F
- max_freq(CPU1) = 2/3 * F
这导致：
- capacity(CPU0) = C
- capacity(CPU1) = C/3
在每个 CPU以其最大频率运行的情况下，执行与 1.3.1 中描述的相同工作负载将导致：
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
workload on CPU1
CPU1 work ^
| ______________ ______________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
1.4 表示注意事项
值得注意的是，使用单个值来表示 CPU 性能差异在某种程度上是有争议的。不同 µarch 之间的相对性能差异可能在整数运算上为 X%，浮点运算上为 Y%，分支操作上为 Z%，等等。尽管如此，目前使用这种简单方法得到的结果仍然令人满意。
2. 任务利用率
2.1 简介
容量感知调度需要表达任务对 CPU 容量的需求。每个调度器类可以以不同的方式表达这一点，虽然任务利用率是特定于 CFS 的，但在这里描述它是为了引入更通用的概念。
任务利用率是一个百分比，旨在表示任务的吞吐量需求。它的一个简单近似值是任务的工作周期，即：
任务利用率（p）= 工作周期（p）
在具有固定频率的 SMP 系统上，100% 的利用率意味着任务是一个忙循环。相反，10% 的利用率暗示着它是一个小的周期性任务，它花费的时间比执行时间更多。变化的 CPU 频率和不对称的 CPU 容量使这变得更加复杂；接下来的部分将对此进行扩展。
2.2 频率不变性
需要考虑的一个问题是，工作负载的工作周期直接受到 CPU 当前运行的 OPP 的影响。考虑在给定频率 F 下运行周期性工作负载：
CPU work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
这导致 duty_cycle(p) == 25%。
现在，考虑以频率 F/2 运行相同的工作负载：
CPU work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
这导致 duty_cycle(p) == 50%，尽管任务在两次执行中的行为完全相同（即执行相同量的工作）。
可以使用以下公式使任务利用率信号成为频率不变的：
task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu))
将此公式应用于上述两个示例，得到的是一个频率不变的任务利用率为 25%。
2.3 CPU 不变性
CPU 容量对任务利用率有类似的影响，即在不同容量值的 CPU 上运行相同的工作负载将产生不同的工作周期。
考虑 1.3.2 中描述的系统，即：
- capacity(CPU0) = C
- capacity(CPU1) = C/3
在每个 CPU 上以其最大频率执行给定的周期性工作负载将导致：
CPU0 work ^
| ____ ____ ____
| | | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
CPU1 work ^
| ______________ ______________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
换句话说，
- 如果 p 在 CPU0 上以其最大频率运行，则 duty_cycle(p) == 25%
- 如果 p 在 CPU1 上以其最大频率运行，则 duty_cycle(p) == 75%
可以使用以下公式使任务利用率信号成为 CPU 不变的：
task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity)
其中 max_capacity 是系统中最高的 CPU 容量值。将此公式应用于上述示例，得到的是一个 CPU 不变的任务利用率为 25%。
2.4 不变的任务利用率
为了获得真正不变的信号，任务利用率需要同时具有频率和 CPU 不变性。因此，对于给定的任务 p，同时具有 CPU 和频率不变性的任务利用率的伪公式如下：
curr_frequency(cpu) capacity(cpu)
task_util_inv(p) = duty_cycle(p) * ------------------- * -------------
max_frequency(cpu) max_capacity
换句话说，不变的任务利用率描述了任务的行为，就好像它在系统中以最高容量的 CPU 上以最大频率运行一样。
在接下来的部分中提到的任务利用率将暗示其不变形式。
2.5 利用率估计
没有水晶球，任务行为（因此任务利用率）在任务首次变为可运行状态时无法准确预测。CFS 类维护了一些基于 Per-Entity Load Tracking (PELT) 机制的 CPU 和任务信号，其中之一产生了平均利用率（而不是瞬时利用率）。
这意味着，尽管容量感知调度标准将考虑“真实”的任务利用率（使用水晶球），但实现只能使用其估算值。
3. 容量感知调度要求
3.1 CPU 容量
Linux 目前无法自行确定 CPU 容量，因此需要将此信息传递给它。架构必须为此定义 arch_scale_cpu_capacity()。
arm、arm64 和 RISC-V 架构直接将此映射到 arch_topology 驱动程序的 CPU 缩放数据，该数据源自于 capacity-dmips-mhz CPU 绑定；参见 Documentation/devicetree/bindings/cpu/cpu-capacity.txt。
3.2 频率不变性
如 2.2 中所述，容量感知调度需要频率不变的任务利用率。架构必须为此定义 arch_scale_freq_capacity(cpu)。
实现此函数需要弄清楚每个 CPU 运行的频率。实现此功能的一种方法是利用硬件计数器，其增量速率随 CPU 当前频率的变化而变化（在 x86 上为 APERF/MPERF，在 arm64 上为 AMU）。另一种方法是直接连接到 cpufreq 频率转换，当内核意识到切换到的频率时（arm/arm64 也采用了这种方法）。
4. 调度器拓扑
在构建调度域时，调度器将确定系统是否具有不对称的 CPU 容量。如果是这种情况：
- 将启用 sched_asym_cpucapacity 静态关键字。
- 将在跨越所有唯一 CPU 容量值的最低调度域级别上设置 SD_ASYM_CPUCAPACITY_FULL 标志。
- 对于跨越任何不对称范围的 CPU 的任何调度域，将设置 SD_ASYM_CPUCAPACITY 标志。
sched_asym_cpucapacity 静态关键字旨在保护为不对称 CPU 容量系统提供服务的代码段。但请注意，该关键字是系统范围的。想象一下使用 cpusets 的以下设置：
capacity C/2 C
________ ________
/ \ / \
CPUs 0 1 2 3 4 5 6 7
\__/ \______________/
cpusets cs0 cs1
这可以通过以下方式创建：
mkdir /sys/fs/cgroup/cpuset/cs0
echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems
mkdir /sys/fs/cgroup/cpuset/cs1
echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus
echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems
echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance
由于系统中存在 CPU 容量不对称性，将启用 sched_asym_cpucapacity 静态关键字。然而，CPU 0-1 的 sched_domain 层次跨越单个容量值：在该层次结构中未设置 SD_ASYM_CPUCAPACITY，它描述了一个 SMP 岛屿，应该被视为这样处理。
因此，保护为不对称 CPU 容量提供服务的代码路径的“规范”模式是：
- 检查 sched_asym_cpucapacity 静态关键字
- 如果它已启用，则还要检查 sched_domain 层次结构中是否存在 SD_ASYM_CPUCAPACITY（如果相关，即代码路径针对特定 CPU 或其组）
5. 容量感知调度实现
5.1 CFS
5.1.1 容量适应性
CFS 的主要容量调度标准是：
task_util(p) < capacity(task_cpu(p))
这通常被称为容量适应性标准，即 CFS 必须确保任务“适合”其 CPU。如果违反了这一标准，任务将需要完成的工作量超过其 CPU 的提供能力：它将成为 CPU 绑定型任务。
此外，uclamp 允许用户空间通过 sched_setattr() 或 cgroup 接口（请参阅控制组 v2）指定任务的最小和最大利用率值。正如其名称所暗示的那样，这可以用于限制前述标准中的 task_util()。
5.1.2 唤醒 CPU 选择
CFS 任务唤醒 CPU 选择遵循上述的容量适应性标准。除此之外，uclamp 用于限制任务利用率值，这使得用户空间对 CFS 任务的 CPU 选择具有更多的影响力。换句话说，CFS 唤醒 CPU 选择搜索满足以下条件的 CPU：
clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu)
通过使用 uclamp，用户空间可以例如通过给予较低的 uclamp.max 值，允许一个繁忙循环（100% 利用率）在任何 CPU 上运行。相反，它可以通过给予较高的 uclamp.min 值，强制一个小的周期性任务（例如 10% 利用率）在性能最高的 CPU 上运行。
注意
CFS 中的唤醒 CPU 选择可能会被能量感知调度（EAS）所取代，有关能量感知调度的信息请参见能量感知调度。
5.1.3 负载平衡
在唤醒 CPU 选择中的一个病态情况是，当任务很少或根本不休眠时，它很少或根本不会唤醒。考虑：
w == wakeup event
capacity(CPU0) = C
capacity(CPU1) = C / 3
workload on CPU0
CPU work ^
| _________ _________ ____
| | | | | |
+----+----+----+----+----+----+----+----+----+----+-> time
w w w
workload on CPU1
CPU work ^
| ____________________________________________
| |
+----+----+----+----+----+----+----+----+----+----+->
w
这个工作负载应该在 CPU0 上运行，但如果任务满足以下条件之一：
- 从一开始就被错误地调度（初始利用率估计不准确）
- 从一开始就被正确地调度，但突然需要更多的处理能力
那么它可能会成为 CPU 绑定型任务，即任务利用率(task_util(p)) > CPU 容量(task_cpu(p))；CPU 容量调度标准被违反，并且可能没有更多的唤醒事件通过唤醒 CPU 选择来修复这个问题。
处于这种情况的任务被称为“不匹配”任务，并且处理这种情况的机制具有相同的名称。不匹配任务迁移利用了 CFS 负载平衡器，更具体地说是活动负载平衡部分（用于迁移当前正在运行的任务）。当进行负载平衡时，如果可以将不匹配任务迁移到具有比当前 CPU 更大容量的 CPU 上，则会触发不匹配的活动负载平衡。
5.2 RT
5.2.1 唤醒 CPU 选择
RT 任务的唤醒 CPU 选择搜索满足以下条件的 CPU：
task_uclamp_min(p) <= capacity(task_cpu(cpu))
同时仍然遵循常规的优先级约束。如果没有候选 CPU 能够满足这个容量条件，则遵循严格基于优先级的调度，并忽略 CPU 容量。
5.3 DL
5.3.1 唤醒 CPU 选择
DL 任务的唤醒 CPU 选择搜索满足以下条件的 CPU：
task_bandwidth(p) < capacity(task_cpu(p))
同时仍然遵守常规的带宽和截止时间约束。如果没有候选 CPU 能够满足这个容量条件，则任务将保留在其当前的 CPU 上。