泰晓科技 -- 聚焦 Linux - 追本溯源，见微知著！
网站地址：https://tinylab.org

儿童Linux系统，可打字编程学数理化
请稍侯

“茴”字有几种写法：系统负载是怎样计算的？（三）

Chen Jie 创作于 2017/07/23
打赏

By Chen Jie of TinyLab.org 2017-07-23 00:00:00

前情回顾

前俩篇从 /proc/loadavg 和负载均衡场景，来体会“负载”是如何定义的。直接把当前计数输出，可能出现这一时刻与下一时刻的巨大波动，换言之，指标很快过期，失去意义。

故而各种负载指标，其实是 最近一段时间的“均值” —— 历史值占“一部分比例”，当前时刻占“一部分比例”。例如，在 /proc/loadavg 中 “0.20 0.18 0.12 1/80 11206”，前三个值是就是最近 1 分钟，5 分钟和 15 分钟的负载均值：

  • 负载 == “采样时，D + R 的任务总数”
  • 采样周期 5s
  • 采样那会 的最近 1 分钟 / 5 分钟 / 10 分钟均值
  • 1 分钟：历史值 * e^(-5/60) + 当前值 * (1.0 - e^(-5/60))
  • 5 分钟：历史值 * e^(-5/300) + 当前值 * (1.0 - e^(-5/300))
  • 15 分钟：历史值 * e^(-5/900) + 当前值 * (1.0 - e^(-5/900))

负载均衡场面比较大，我们躲在 find_busiest_queue() 中，观察对 “busiest” 定义 —— 对于每个 CPU：加权平均负载 / CPU 虚拟算力

  • 加权平均负载，采样周期 1ms：
    • 周期内：累加 “R 状态的任务”时长 * 任务优先级 * CPU 频率缩放系数
    • 多周期平均：a + a1 * q + a2 * q^2 …; // aN 代表距今前 N 个周期，q^32 = 0.5
  • CPU 虚拟算力，固有算力基础上，剔除 RT 开销。剔除方法：
    • 累加 RT 时长 * CPU 频率缩放系数
    • 每 500ms 为一周期
    • 距今 N 周期，则 累加值 >> N （←_← 跨周期边界，跳崖式衰减；一次跨地越多，坠地越快）
    • 计算 RT 时间占比
    • 1.0 - RT 时间占比，是为折扣系数 —— 固有算力上打折，即为虚拟算力

具体细节参见「系统负载是怎样计算的？（一）」以及「系统负载是怎样计算的？（二）」。后篇对加权平均负载的计算函数 __update_load_avg()，留了若干疑问为线索：

  1. 任务们在队列中呆了一段时间，便是负载（当前 CPU 的 TODO list）。计算时，负载已经随 CPU freq 缩放，那不错。但还要据任务的 weight 缩放，weight 定义为何？
  2. 历史的负载值（非本周期），如何随时间衰减？
  3. LOAD_AVG_MAX 的值为何是 47742？

普通任务的 weight 定义

CFS 中，任务 nice 级别，最终换算成了权重（weight）。越“重”，则虚拟时间（vruntime）流逝越慢：

update_curr()
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;
	...
	delta_exec = now - curr->exec_start;
	curr->exec_start = now;
	...
	
	// curr->vruntime += delta_exec * NICE_0_LOAD / NICE_OF_THIS_TASK_LOAD;
	curr->vruntime += calc_delta_fair(delta_exec, curr);

例如，32 位系统上，NICE_0_LOAD 为 1024（没错，又是一个 10 位整数模拟小数），NICE_-19_LOAD 为 71755，故而一个 nice=-19 任务，其时间流逝速度为默认情况的 1.427%。

“越重时间流逝越慢”的效应，按照伪科学类比法，就好像相对论重力越强时间流逝越慢：

image

为上图作简单注解，时间间隔是通过周期性重复过程来衡量，例如光的频率。从地球上一点向高空观察者发送一束光，由于逃离重力场光损失能量（频率变慢），故而高空观察者看到了频率红移的光（时间间隔拉长）。即在高空观察者看来，地表的时间流逝慢。

回到 CFS，nice 到 weight 的对应关系参见 sched_prio_to_weight。另，抢占发生，除了要求候选者的 vruntime 比 current 小以外，还要小出一个阀值，这个阀值计算也与 weight 相关：

  • 对于 Wake up preempt：阀值计算依赖候选者的 weight，候选者“越重”，越容易抢占。
  • 对于 Tick preempt：阀值计算依赖 current 的 weight，current “越重”，越不容易被抢占。

历史负载的衰减（decay_load）

负载值为 val，经历 n 个周期，则衰减为 val * q^n，其中 q^32 ~= 0.5：

static u64 decay_load(u64 val, u64 n)
{
	unsigned int rest_n;
	
	// LOAD_AVG_PERIOD 为 32，即 q^LOAD_AVG_PERIOD ~= 0.5
	// 换言之，每经过 32 个周期右移一位，64 位数则有：
	//   超过 32*63 个周期后，衰减为 0（或确切地说，不足一位）
	if (unlikely(n > LOAD_AVG_PERIOD * 63))
		return 0;
	
	// 转成 32bits
	rest_n = n;
	
	/*
 	 * As q^PERIOD = 1/2, we can combine
 	 *    q^n = 1/2^(n/PERIOD) * q^(n%PERIOD)
 	 * With a look-up table which covers q^n (n<PERIOD)
 	 *
 	 * To achieve constant time decay_load.
 	 */
	if (unlikely(rest_n >= LOAD_AVG_PERIOD)) {
		val >>= rest_n / LOAD_AVG_PERIOD;
		rest_n %= LOAD_AVG_PERIOD;
	}
	
	// val *= q^rest_n，其中 q^rest_n 查表得到，即 runnable_avg_yN_inv[rest_n]
	// 表中值采用 32 位整数模拟小数，故而算完需 “shift right 32”
	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[rest_n], 32);
	return val;
}

来算下神秘的 q 是多少：

# python2 -c "print 0.5 ** (1.0/32)"
# 0.978572062088
#
# python2 -c "print '0x%x' % int(  (0.5 ** (1.0/32)) ** 31 * (1<<32)  )"
# 0x82cd8698, 即 runnable_avg_yN_inv[31] 的值


由于 nohz 存在，历史（持续）负载，可能隔了好几个周期才被统计入，此时面临的是一个等比数列求和：

LOAD = weight * freq_scale * decay
decay = q^0 + q^1 + q^2 + ... q^n

decay 因子计算，对应代码为 __update_load_avg() / __compute_runnable_contrib(n)：

static u32 __compute_runnable_contrib(u64 n)
{
	u32 contrib1 = 0;
	u32 contrib2 = 0;
	
	if (likely(n <= LOAD_AVG_PERIOD))
		return runnable_avg_yN_sum[n];
	else if (unlikely(n >= LOAD_AVG_MAX_N))
		return LOAD_AVG_MAX;

	// __accumulated_sum_N32[] 为每隔 32 个周期的、一系列预先计算的、等比求和值
	contrib1 = __accumulated_sum_N32[n/LOAD_AVG_PERIOD];
	
	n %= LOAD_AVG_PERIOD;
	
	contrib1 = decay_load(contrib1, n);
	// runnable_avg_yN_sum[] 为 1-31 个预先计算的、等比求和值
	contrib2 = runnable_avg_yN_sum[n];
	
	return contrib1 + contrib2;
}

其中 LOAD_AVG_MAX 一段持续负载，能产生的“最大 decay 因子”，由无穷递降等比数列求和公式，可得为：

# python -c "print 1/(1 - 0.5 ** (1.0/32))"
# 46.6680463651
	
# 10 位整数模拟小数
# python -c "print 1/(1 - 0.5 ** (1.0/32)) * 1024"
# 47788
	
# 然而 LOAD_AVG_MAX 定义为 47742，注释介绍由 LOAD_AVG_MAX_N（345）个周期所总贡献
# 可是按 345 个周期计算得 47760

上述代码对应 4.11 版本内核，到了 4.12 版 “组织架构调整” —— __update_load_avg() 中的累计过程独立出了新函数 accumulate_sum()；其中，“补齐”、“历史（持续）负载”、“本周期” 累计过程塞入 __accumulate_pelt_segments()（仅计算因子）。


Read Related:

Read Latest: