背景
Read the fucking source code!
--By 鲁迅
A picture is worth a thousand words.
--By 高尔基
说明:
Kernel 版本: 4.14
ARM64 处理器, Contex-A53, 双核
使用工具: Source Insight 3.5, Visio
1. 概述
CPU 负载 (CPU load) 指的是某个时间点进程对系统产生的压力.
来张图来类比下(参考 Understanding Linux CPU Load)
CPU 的运行能力, 就如大桥的通行能力, 分别有满负荷, 非满负荷, 超负荷等状态, 这几种状态对应不同的 CPU load 值;
单 CPU 满负荷运行时 cpu_load 为 1, 当多个 CPU 或多核时, 相当于大桥有多个车道, 满负荷运行时 cpu_load 值为 CPU 数或多核数;
CPU 负载的计算(以单 CPU 为例), 假设一分钟内执行 10 个任务代表满负荷, 当一分钟给出 30 个任务时, CPU 只能处理 10 个, 剩余 20 个不能处理, cpu_load=3;
在实际系统中查看:
cat /proc/cpuinfo: 查看 CPU 信息;
cat /proc/loadavg: 查看 CPU 最近 1/5/15 分钟的平均负载:
计算 CPU 负载, 可以让调度器更好的进行负载均衡处理, 以便提高系统的运行效率. 此外, 内核中的其他子系统也可以参考这些 CPU 负载值来进行相应的调整, 比如 DVFS 等.
目前内核中, 有以下几种方式来跟踪 CPU 负载:
全局 CPU 平均负载;
运行队列 CPU 负载;
- PELT(per entity load tracking)
- ;
这也是本文需要探讨的内容, 开始吧.
2. 全局 CPU 平均负载
2.1 基础概念
先来明确两个与 CPU 负载计算相关的概念:
active task(活动任务): 只有知道活动任务数量, 才能计算 CPU 负载, 而活动任务包括了 TASK_RUNNING 和 TASK_UNINTERRUPTIBLE 两类任务. 包含 TASK_UNINTERRUPTIBLE 任务的原因是, 这类任务经常是在等待 I/O 请求, 将其包含在内也合理;
NO_HZ: 我们都知道 Linux 内核每隔固定时间发出 timer interrupt, 而 HZ 是用来定义 1 秒中的 timer interrupts 次数, HZ 的倒数是 tick, 是系统的节拍器, 每个 tick 会处理包括调度器, 时间管理, 定时器等事务. 周期性的时钟中断带来的问题是, 不管 CPU 空闲或繁忙都会触发, 会带来额外的系统损耗, 因此引入了 NO_HZ 模式, 可以在 CPU 空闲时将周期性时钟关掉. 在 NO_HZ 期间, 活动任务数量的改变也需要考虑, 而它的计算不如周期性时钟模式下直观.
2.2 流程
Linux 内核中定义了三个全局变量值 avenrun[3], 用于存放最近 1/5/15 分钟的平均 CPU 负载.
看一下计算流程:
计算活动任务数, 这个包括两部分: 1)周期性调度中新增加的活动任务; 2)在 NO_HZ 期间增加的活动任务数;
根据活动任务数值, 再结合全局变量值 avenrun[]中的 old value, 来计算新的 CPU 负载值, 并最终替换掉 avenrun[]中的值;
系统默认每隔 5 秒钟会计算一次负载, 如果由于 NO_HZ 空闲而错过了下一个 CPU 负载的计算周期, 则需要再次进行更新. 比如 NO_HZ 空闲 20 秒而无法更新 CPU 负载, 前 5 秒负载已经更新, 需要计算剩余的 3 个计算周期的负载来继续更新;
2.3 计算方法
Linux 内核中, 采用 11 位精度的定点化计算, CPU 负载 1.0 由整数 2048 表示, 宏定义如下:
- #define FSHIFT 11 /* nr of bits of precision */
- #define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */
- #define LOAD_FREQ (5*HZ+1) /* 5 sec intervals */
- #define EXP_1 1884 /* 1/exp(5sec/1min) as fixed-point */
- #define EXP_5 2014 /* 1/exp(5sec/5min) */
- #define EXP_15 2037 /* 1/exp(5sec/15min) */
计算公式如下:
load 值为旧的 CPU 负载值 avenrun[], 整个计算完成后得到新的负载值, 再更新 avenrun[];
EXP_1/EXP_5/EXP_15, 分别代表最近 1/5/15 分钟的定点化值的指数因子;
active 值, 根据读取 calc_load_tasks 的值来判断, 大于 0 则乘以 FIXED_1(2048)传入;
根据 active 和 load 值的大小关系来决定是否需要加 1, 类似于四舍五入的机制;
关键代码如下:
- active = atomic_long_read(&calc_load_tasks);
- active = active> 0 ? active * FIXED_1 : 0;
- avenrun[0] = calc_load(avenrun[0], EXP_1, active);
- avenrun[1] = calc_load(avenrun[1], EXP_5, active);
- avenrun[2] = calc_load(avenrun[2], EXP_15, active);
NO_HZ 模式下活动任务数量更改的计算
由于 NO_HZ 空闲效应而更改的 CPU 活动任务数量, 存放在全局变量 calc_load_nohz[2]中, 并且每 5 秒计算周期交替更换一次存储位置(
calc_load_read_idx/calc_load_write_idx
), 其他程序可以去读取最近 5 秒内的活动任务变化的增量值.
计算示例
假设在某个 CPU 上, 开始计算时 load=0.5, 根据 calc_load_tasks 值获取不同的 active, 中间进入 NO_HZ 模式空闲了 20 秒, 整个计算的值如下图:
3. 运行队列 CPU 负载
Linux 系统会计算每个 tick 的平均 CPU 负载, 并将其存储在运行队列中 rq->cpu_load[5], 用于负载均衡;
下图显示了计算运行队列的 CPU 负载的处理流程:
最终通过 cpu_load_update 来计算, 逻辑如下:
其中传入的 this_load 值, 为运行队列现有的平均负载值.
上图中的衰减因子, 是在 NO_HZ 模式下去进行计算的. 在没有使用 tick 时, 从预先计算的表中计算负载值. Linux 内核中定义了两个全局变量:
- #define DEGRADE_SHIFT 7
- static const u8 degrade_zero_ticks[CPU_LOAD_IDX_MAX] = {0, 8, 32, 64, 128};
- static const u8 degrade_factor[CPU_LOAD_IDX_MAX][DEGRADE_SHIFT + 1] = {
- { 0, 0, 0, 0, 0, 0, 0, 0 },
- { 64, 32, 8, 0, 0, 0, 0, 0 },
- { 96, 72, 40, 12, 1, 0, 0, 0 },
- { 112, 98, 75, 43, 15, 1, 0, 0 },
- { 120, 112, 98, 76, 45, 16, 2, 0 }
- };
衰减因子的计算主要是在 delay_load_missed()函数中完成, 该函数会返回 load * 衰减因子的值, 作为上图中的 old_load.
计算方式如下:
4. PELT
PELT, Per-entity load tracking. 在 Linux 引入 PELT 之前, CFS 调度器在计算 CPU 负载时, 通过跟踪每个运行队列上的负载来计算; 在引入 PELT 之后, 通过跟踪每个调度实体的负载贡献来计算.(其中, 调度实体: 指 task 或 task_group)
4.1 PELT 计算方法
总体的计算思路:
将调度实体的可运行状态时间(正在运行 + 等待 CPU 调度运行), 按 1024us 划分成不同的周期, 计算每个周期内该调度实体对系统负载的贡献, 最后完成累加. 其中, 每个计算周期, 随着时间的推移, 需要乘以衰减因子 y 进行一次衰减操作.
先来看一下每个调度实体的负载贡献计算公式:
当前时间点的负载贡献 = 当前时间点负载 + 上个周期负载贡献 * 衰减因子;
假设一个调度实体被调度运行, 运行时间段可以分成三个段 d1/d2/d3, 这三个段是被 1024us 的计算周期分割而成, period_contrib 是调度实体 last_update_time 时在计算周期间的贡献值,;
总体的贡献值, 也是根据 d1/d2/d3 来分段计算, 最终相加即可;
y 为衰减因子, 每隔 1024us 就乘以 y 来衰减一次;
计算的调用流程如下图:
函数主要是计算时间差, 再分成 d1/d2/d3 来分段计算处理, 最终更新相应的字段;
decay_load 函数要计算 val * y^n, 内核提供了一张表来避免浮点运算, 值存储在
runnable_avg_yN_inv
数组中;
- static const u32 runnable_avg_yN_inv[] = {
- 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
- 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
- 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
- 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
- 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
- 0x85aac367, 0x82cd8698,
- };
Linux 中使用 struct sched_avg 来记录调度实体和 CFS 运行队列的负载信息, 因此 struct sched_entity 和 struct cfs_rq 结构体中, 都包含了 struct sched_avg, 字段介绍如下:
- struct sched_avg {
- u64 last_update_time; // 上一次负载更新的时间, 主要用于计算时间差;
- u64 load_sum; // 可运行时间带来的负载贡献总和, 包括等待调度时间和正在运行时间;
- u32 util_sum; // 正在运行时间带来的负载贡献总和;
- u32 period_contrib; // 上一次负载更新时, 对 1024 求余的值;
- unsigned long load_avg; // 可运行时间的平均负载贡献;
- unsigned long util_avg; // 正在运行时间的平均负载贡献;
- };
4.2 PELT 计算调用
PELT 计算的发生时机如下图所示:
调度实体的相关操作, 包括入列出列操作, 都会进行负载贡献的计算;
PELT 的算法还在持续的改进中, 各个内核版本也存在差异, 大体的思路已经在上文中介绍到了, 细节就不再深入分析了.
来源: https://www.cnblogs.com/LoyenWang/p/12316660.html