英语

容量感知调度

1. CPU 容量

1.1 介绍

传统的同构 SMP 平台由完全相同的 CPU 组成。而异构平台则由具有不同性能特征的 CPU 组成 - 在这样的平台上,并非所有 CPU 都可以被认为是相同的。

CPU 容量是衡量 CPU 可以达到的性能的指标,相对于系统中性能最高的 CPU 进行了标准化。 异构系统也称为非对称 CPU 容量系统,因为它们包含不同容量的 CPU。

最大可实现性能(IOW,即最大 CPU 容量)的差异源于两个因素

  • 并非所有 CPU 都可能具有相同的微架构 (µarch)。

  • 使用动态电压和频率调整 (DVFS),并非所有 CPU 都可以物理上达到更高的工作性能点 (OPP)。

Arm big.LITTLE 系统是这两者的一个例子。 大 CPU 比 LITTLE CPU 更注重性能(更多流水线阶段、更大的缓存、更智能的预测器等),并且通常可以达到比 LITTLE CPU 更高的 OPP。

CPU 性能通常以每秒百万指令 (MIPS) 表示,也可以表示为每个 Hz 可达到的给定数量的指令,从而得出

capacity(cpu) = work_per_hz(cpu) * max_freq(cpu)

1.2 调度器术语

调度器中使用两个不同的容量值。 CPU 的 原始容量 是其最大可达到的容量,即其最大可达到的性能水平。 此原始容量由函数 arch_scale_cpu_capacity() 返回。 CPU 的 容量 是其 原始容量,并减去了一些可用性能的损失(例如,处理 IRQ 所花费的时间)。

请注意,CPU 的 容量 仅供 CFS 类使用,而 原始容量 则与类无关。 为了简洁起见,本文档的其余部分将交替使用术语 容量原始容量

1.3 平台示例

1.3.1 相同的 OPP

考虑一个假设的双核非对称 CPU 容量系统,其中

  • work_per_hz(CPU0) = W

  • work_per_hz(CPU1) = W/2

  • 所有 CPU 均以相同的固定频率运行

根据上述容量定义

  • capacity(CPU0) = C

  • capacity(CPU1) = C/2

为了与 Arm big.LITTLE 进行类比,CPU0 将是 big,而 CPU1 将是 LITTLE。

对于周期性地执行固定工作量的 workload,您将获得如下执行跟踪

CPU0 work ^
          |     ____                ____                ____
          |    |    |              |    |              |    |
          +----+----+----+----+----+----+----+----+----+----+-> time

CPU1 work ^
          |     _________           _________           ____
          |    |         |         |         |         |
          +----+----+----+----+----+----+----+----+----+----+-> time

CPU0 在系统中具有最高的容量 (C),并在 T 个时间单位内完成固定数量的工作 W。 另一方面,CPU1 的容量是 CPU0 的一半,因此仅在 T 中完成 W/2。

1.3.2 不同的最大 OPP

通常,具有不同容量值的 CPU 也具有不同的最大 OPP。 考虑与上述相同的 CPU(即,相同 work_per_hz())

  • max_freq(CPU0) = F

  • max_freq(CPU1) = 2/3 * F

这会产生

  • capacity(CPU0) = C

  • capacity(CPU1) = C/3

执行与 1.3.1 中描述的相同工作负载,每个 CPU 以其最大频率运行,导致

CPU0 work ^
          |     ____                ____                ____
          |    |    |              |    |              |    |
          +----+----+----+----+----+----+----+----+----+----+-> time

                           workload on CPU1
CPU1 work ^
          |     ______________      ______________      ____
          |    |              |    |              |    |
          +----+----+----+----+----+----+----+----+----+----+-> time

1.4 表示注意事项

应该注意的是,使用单个值来表示 CPU 性能差异在某种程度上是一个有争议的点。 两种不同 µarch 之间的相对性能差异在整数运算中可能是 X%,在浮点运算中可能是 Y%,在分支中可能是 Z%,依此类推。 尽管如此,目前使用这种简单方法的结果令人满意。

2. 任务利用率

2.1 介绍

容量感知调度需要用 CPU 容量来表示任务的需求。 每个调度器类都可以不同地表达这一点,虽然任务利用率是 CFS 特有的,但为了引入更通用的概念,在这里描述它是很方便的。

任务利用率是一个百分比,旨在表示任务的吞吐量要求。 它的一个简单近似值是任务的占空比,即

task_util(p) = duty_cycle(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

IOW,

  • 如果 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 容量值。 将此公式应用于上述示例会产生 25% 的 CPU 不变任务利用率。

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. 调度器拓扑

在构建 sched domains 期间,调度器将确定系统是否显示非对称 CPU 容量。 如果是这样的话

  • 将启用 sched_asym_cpucapacity 静态键。

  • 将在跨越所有唯一 CPU 容量值的最低 sched_domain 级别设置 SD_ASYM_CPUCAPACITY_FULL 标志。

  • 将为跨越具有任何范围的不对称性的 CPU 的任何 sched_domain 设置 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 选择。 IOW,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 选择可以被 Energy Aware Scheduling (EAS) 所掩盖,该调度在 Energy Aware Scheduling 中进行了描述。

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 密集型,IOW task_util(p) > capacity(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 上。