• Read the fucking source code! --By 鲁迅

• A picture is worth a thousand words. --By 高尔基

1. Kernel版本：4.14

2. ARM64处理器，Contex-A53，双核

3. 使用工具：Source Insight 3.5， Visio

1. 概述

• 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 分钟的平均负载：

1. 全局CPU平均负载；

2. 运行队列CPU负载；

3. PELT（per entity load tracking）;

2. 全局CPU平均负载

2.1 基础概念

1. active task（活动任务）：只有知道活动任务数量，才能计算CPU负载，而活动任务包括了 TASK_RUNNING 和 TASK_UNINTERRUPTIBLE 两类任务。包含 TASK_UNINTERRUPTIBLE 任务的原因是，这类任务经常是在等待 I/O 请求，将其包含在内也合理；

2. NO_HZ：我们都知道 Linux 内核每隔固定时间发出 timer interrupt ，而 HZ 是用来定义1秒中的 timer interrupts 次数，HZ的倒数是tick，是系统的节拍器，每个tick会处理包括调度器、时间管理、定时器等事务。
1. 周期性的时钟中断带来的问题是，不管CPU空闲或繁忙都会触发，会带来额外的系统损耗，因此引入了NO_HZ模式，可以在 CPU 空闲时将周期性时钟关掉。在 NO_HZ 期间，活动任务数量的改变也需要考虑，而它的计算不如周期性时钟模式下直观。

2.2 流程

• 计算活动任务数，这个包括两部分：1）周期性调度中新增加的活动任务；2）在 NO_HZ 期间增加的活动任务数；

• 根据活动任务数值，再结合全局变量值avenrun[]中的old value，来计算新的CPU负载值，并最终替换掉avenrun[]中的值；

• 系统默认每隔5秒钟会计算一次负载，如果由于NO_HZ空闲而错过了下一个CPU负载的计算周期，则需要再次进行更新。比如NO_HZ空闲20秒而无法更新CPU负载，前5秒负载已经更新，需要计算剩余的3个计算周期的负载来继续更新；

2.3 计算方法

#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]，用于负载均衡；

• 其中传入的 this_load 值，为运行队列现有的平均负载值。

#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 }
};

4. PELT

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,
};

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计算调用

• 调度实体的相关操作，包括入列出列操作，都会进行负载贡献的计算；

参考文档