容量感知调度
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 上。