Linux内核进程调度器CPU负载

　　目录
　　背景 概述 全局CPU平均负载
　　2.1 基础概念
　　2.2 流程
　　2.3 计算方法 运行队列CPU负载 PELT
　　4.1 PELT计算方法
　　4.2 PELT计算调用 背景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负载计算相关的概念
　　（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  会处理包括调度器、时间管理、定时器等事务。 周期性的时钟中断带来的问题是，不管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< 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  的算法还在持续的改进中，各个内核版本也存在差异，大体的思路已经在上文中介绍到了，细节就不再深入分析了。