Linux内核源码分析-进程调度(六)-PELT(per-entity load tracking)[通俗易懂]

什么叫负载？

负载是一个瞬间值，即当前时间点存在的进程对系统产生的“压力”是怎样的。不仅仅只有正在运行的进程才会对CPU负载作出贡献，加入队列等待执行的进程也能够对CPU负载作出贡献。

背景

对于Linux内核而言，做一款好的进程调度器是一项非常具有挑战性的任务，主要原因是在进行CPU资源分配的时候必须满足如下的需求：

1、它必须是公平的

2、快速响应

3、系统的吞吐量要高

4、功耗要小

PELT算法是Linux 3.8合入的，那么在此之前，存在什么问题才引入PELT算法呢？在Linux 3.8之前，CFS以每个运行队列（runqueue，简称rq）为基础跟踪负载。但是这种方法，我们无法确定当前负载的来源。同时，即使工作负载相对稳定的情况下，在rq级别跟踪负载，其值也会产生很大变化。为了解决以上的问题，PELT算法会跟踪每个调度实体（per-scheduling entity）的负载情况。
CFS的“运行队列”实际上是有多个，每个CPU有自己的per-cpu rq。当开启组调度时，每个调度组也都有自己的运行队列。

per-entity load tracking

per-entity load tracking的引入解决了这个问题，将负载跟踪从per rq细化到per-entity的层次。所谓的调度实体就是一个进程（task se）或者调度组中的一组进程（group se）。
为了做到per-entity的负载跟踪，物理时间被分成了以1024us为一个周期。在每一个1024us的周期中，一个entity对系统负载的贡献可以根据该实体处于runnable状态（正在cpu上运行或者等待cpu调度运行）的时间来计算。如果在该周期内，runnable的时间是x，那么对系统的负载就是(x/1024)。当然，一个调度实体在一个调度周期内的负载可能会超过1，这是因为我们会累积当前实体在过去周期中的负载，当然，对于过去的负载我们在计算的时候需要乘一个衰减因子。我们如果让Li表示在周期Pi中调度实体对系统作出的负载贡献，那么一个调度实体对系统符合的总贡献可以表示为：

                           L = L0 + L1*y + L2\*y^2 + L3\*y^3

其中y就是衰减因子。通过上面的公式可以看出：

（1） 调度实体对系统符合的贡献值是一个序列之和组成
（2） 最近的负荷值拥有最大的权重
（3） 过去的负荷也会被累计，但是是以递减的方式来影响负载计算。
使用这样序列的好处是计算简单，我们不需要使用数组来记录过去的每一个周期的负荷贡献，只要把上一个周期的总负荷贡献值乘以y再加上最新周期的负荷值L0即可。

                           L = L * y + L0

上面公式中的y是一个定值，y^32=0.5。意思就是一个调度实体经过32个周期（32*1024us）对当前周期CPU的负荷贡献会衰减一半。

调度器在每个rq数据结构中，维护一个“blocked load”的成员，这个成员记录了所有阻塞状态进程对系统负荷的贡献。当一个进程阻塞了，它的负载会从总的运行负载值（runnable load）中减去并添加到总的阻塞负载值（blocked load）中。该负载可以以相同的方式衰减（即每个周期乘以y）。当阻塞的进程再次转换成运行态时，其负载值（适当进行衰减）则转移到运行负荷上来。因此，跟踪blocked load只是需要在进程状态转换过程中有一点计算量，调度器并不需要由于跟踪阻塞负载而遍历一个进入阻塞状态进程的链表。

另外一个比较繁琐的地方是对节流进程（throttled processes）负载的计算。所谓节流进程是指那些在“CFS带宽控制器”（ CFS bandwidth controller）下控制运行的进程。当这些进程用完了本周期内的CPU时间，即使它们仍然在运行状态，即使CPU空闲，调度器并不会把CPU资源分配给它们。因此节流进程不会对系统造成负荷。正因为如此，当进程处于被节流状态的时候，它们对系统负荷的贡献值不应该按照runnable进程计算。在等待下一个周期到来之前，throttled processes不能获取cpu资源，因此它们的负荷贡献值会衰减。

从上面的计算公式 L = L0 + L1*y + L2*y^2 + L3*y^3我们也可以看出，经常需要计算val*y^n的值，因此内核提供decay_load(u64 val, u64 n)函数用于计算第n个周期的衰减值。为了避免浮点数运算，采用移位和乘法运算提高计算速度。decay_load(val, n) = val * y^n * 2^32>>32。我们将y^n*2^32的值提前计算出来保存在数组runnable_avg_yN_inv中。
由于y^32=0.5，因此我们只需要计算y*2^32 ~ y^31*2^32的值保存到数组中即可。当n大于31的时候，我们可以借助y^32=0.5公式间接计算。例如y^33*2^32 = y32*y*2^32=0.5*y*2^32=0.5*runnable_avg_yN_inv[1]。

/*
 * 为计算负载贡献衰变值使用的中间数组
 * runnable_avg_yN_inv[n] = (2^32 -1) * (y^n) = (1<<32 -1) * (y^n) ;
 * 因为在32位操作系统下unsigned long是4个字节，无法存储2^32这么大,所以会近似使用2^32 -1
 */
static const u32 runnable_avg_yN_inv[] __maybe_unused = { 
   
	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,
};

runnable_avg_yN_inv数组每个值的计算有个函数如下：

// 计算runnable_avg_yN_inv数组的值
void calc_runnable_avg_yN_inv(void)
{ 
   
	int i;
	unsigned int x;

	/* To silence -Wunused-but-set-variable warnings. */
	printf("static const u32 runnable_avg_yN_inv[] __maybe_unused = {");
	for (i = 0; i < HALFLIFE; i++) { 
   
		x = ((1UL<<32)-1)*pow(y, i);  // (2^32 -1) * (y^n) = (1<<32 -1) * (y^n) 

		if (i % 6 == 0) printf("\n\t");
		printf("0x%8x, ", x);
	}
	printf("\n};\n\n");
}

现在我们正式来看一下decay_load()函数：

#define LOAD_AVG_PERIOD 32

/*
 * 用于计算第n个周期的衰减值，
 * val*y^n，其中 y^32 = 0.5,即y=0.97857206; 
 * (val是某个1024us内的负载值，n代表经过了n个1024us周期后，当时的负载对现在的影响，影响不是瞬间消失，是个逐渐衰减的过程)。
 * 
 * 为了避免浮点数计算，val*y^n = val*y^n*2^32>>32 = val*runnable_avg_yN_inv[n]>>32;
 */
static u64 decay_load(u64 val, u64 n)
{
	unsigned int local_n;

	if (unlikely(n > LOAD_AVG_PERIOD * 63))  // 我们认为经过LOAD_AVG_PERIOD * 63周期，即经过2016个周期衰减为0。y^n=0, 即n>2016
		return 0;

	/* after bounds checking we can collapse to 32-bit */
	local_n = n;

	/*
	 * As y^PERIOD = 1/2, we can combine
	 *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
	 * With a look-up table which covers y^n (n<PERIOD)
	 *
	 * To achieve constant time decay_load.
	 */
	/*
	 * decay_load(val,n)
	 *   当n<32，val * y^n = val * y^n * 2^32 >> 32 = val * runnable_avg_yN_inv[n] >> 32;
	 *   当n>=32 && n <64，val * y^n = val * y^32 * y^(n-32) * 2^32 >> 32 = val * 1/2 *runnable_avg_yN_inv[n-32] >> 32 = ; (当n大于等于32的时候，就需要根据y^32=0.5这个前提条件来计算y^n的值)，
	 *   通用方法处理n>=32：val * y^n * 2^32 >> 32  = val * (y^32)^(n/32) * y^(n%32) * 2^32 >> 32  = val*(1/2)^(n/32) * y^(n%32)*2^32 >> 32 = (val >> (n / LOAD_AVG_PERIOD)) * runnable_avg_yN_inv[n%32] >> 32。
	 */
	if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
		val >>= local_n / LOAD_AVG_PERIOD;  // (local_n / LOAD_AVG_PERIOD) 等于几，则val需要乘以几个y^32(0.5)，即val向右移动几位。
		local_n %= LOAD_AVG_PERIOD;  // local_n对LOAD_AVG_PERIOD取余后的值为最后不足32个周期的部分。
	}

	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);  // val * runnable_avg_yN_inv[local_n] >> 32
	return val;
}

其中mul_u64_u32_shr函数的实现如下：

static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
{
	return (u64)(((unsigned __int128)a * mul) >> shift);
}

如何记录负载信息

Linux使用struct sched_avg结构体来记录负载信息，每个调度实体se以及cfs就绪队列中都包含一个struct sched_avg结构体变量来记录负载信息。

struct sched_entity { 
   
	struct sched_avg		avg;  // 负载信息
}
struct cfs_rq { 
   
	struct sched_avg	avg;  // 平均负载
}

/* * 记录调度实体se或者就绪队列cfs rq的负载信息 * runnable: 在就绪队列上，即se->on_rq == 1。 * running：cfs_rq上正在运行的se是当前se,cfs_rq->curr == se。 * blocking: 阻塞或者休眠状态。 */
struct sched_avg { 
   

	/* * last_update_time是上次更新的时间点，结合当前的时间值，我们可以计算delta并更新*_sum和*_avg。 * 对task se而言，还有一种特殊情况就是迁移到新的CPU，这时候需要将last_update_time设置为0以便新cpu上可以重新开始计算负载。 * 此外，新任务的last_update_time也会设置为0。 * 若使能组调度，在task group之间迁移任务也使用的是相同的机制，见task_move_group_fair()。 */
	u64				last_update_time;  // 上一次负载更新时间，用于计算时间间隔。

	u64				load_sum;   // 负载贡献,累计runable和block衰减负载。
	u64				runnable_load_sum;  // 只记录runnable状态负载贡献,累计runnable衰减负载。
	u32				util_sum;  // running状态负载贡献,累计running衰减时间总和,是右移过10位的。

	u32				period_contrib;  // 记录的是上次更新负载时不足1024us周期的时间（d3），下次计算时需要将这个时间加上算周期。
	

	/* * 针对task se，runnable_load_avg和load_avg的值是没有差别的。 * 但是对于就绪队列负载来说，二者就有不一样的意义。load_avg代表就绪队列平均负载，其包含睡眠进程的负载贡献。runnable_load_avg只包含就绪队列上所有可运行进程的负载贡献 */
	unsigned long			load_avg;  // 平均负载，(load_sum*load->weight)/最大衰减值
	unsigned long			runnable_load_avg;  // runnable状态平均负载贡献。
	unsigned long			util_avg;  // running状态的比值，util_avg 的定义：util_avg = running% * SCHED_CAPACITY_SCALE。

	/* * 任务阻塞后，其负载会不断衰减。 * 如果一个重载任务阻塞太长时间，那么根据标准PELT算法计算出来的负载会非常的小，当该任务被唤醒重新参与调度的时候，由于负载较小会让调度器做出错误的判断。 * 因此引入了util_est，记录阻塞之前的load_avg信息。 */
	struct util_est			util_est;  // task唤醒的时候预估的负载
} ____cacheline_aligned;

调度实体se初始化

调度实体se初始化函数是init_entity_runnable_average()，代码如下:

/*
 * 调度实体se初始化函数
 */
void init_entity_runnable_average(struct sched_entity *se)
{
	struct sched_avg *sa = &se->avg;

	memset(sa, 0, sizeof(*sa));

	/*
	 * Tasks are initialized with full load to be seen as heavy tasks until
	 * they get a chance to stabilize to their real load level.
	 * Group entities are initialized with zero load to reflect the fact that
	 * nothing has been attached to the task group yet.
	 */

	/*
	 * 针对task se的初始化，runnable_load_avg和load_avg的值是和se的权重（se->load.weight）相等。
	 * 根据上面的注释也可以知道，runnable_load_avg和load_avg在后续的负载计算中累加的最大值其实就是当前se的权重值，
	 * 也就意味着，runnable_load_avg和load_avg的值可以间接的表明当前task se的繁重程度。
	 */
	/*
	 * 这个if语句，group se进不去，则runnable_load_avg和load_avg的值为memset后的结果，即为0。这也意味着当前task group中没有任何task需要调度。
	 */
	if (entity_is_task(se))
		sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight);    


    /*
	 * runnable_weight成员主要是针对group se提出的。对于task se来说，runnable_weight就是se的weight，二者的值完全一样。
	 * runnable_weight虽然现在初始化为se的权重值，但是在后续的代码中会不断更新runnable_weight的值。
	 * runnable_weight是se权重的一部分，表示组cfs_rq的可运行部分的实体的权重总和。
	 */
	se->runnable_weight = se->load.weight;

	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
}

计算当前负载贡献

计算公式

我们先来看一个简单的例子，假设一个task从0us开始运行，运行了1000us后，在当前时间片内负载贡献就是1000。然后接着又运行了40us，此时负载贡献是多少呢？因为运行了40us后总的时间变成了1000+40=1024+16，我们在前面说过前一个周期对后一个周期的负荷贡献是衰减的，则时间负载变成了：1024*y+16。如果后面再接着运行了3960us，则总的时间变成了1000+40+3960=1024+1024+1024+1024+904，则此时的负载变成了1024*y^4+1024*y^3+1024*y^2+1024*y^1+904。
现在我们来假设一个通用的场景，假设上一时刻负载贡献是u，经历d时间后的负载贡献如何计算呢？根据上面的例子，我们可以把时间d分成3部分：d1是离当前时间最远（不完整的）period 的剩余部分（比如第一个例子中1000缺的那24us），d2 是完整period时间（第二个例子中，中间那三个1024），而d3是（不完整的）当前 period 的剩余部分（第一个例子中的16）。假设时间d是经过p个周期（d=d1+d2+d3, p=1+d2/1024）。d1，d2，d3 的示意图如下：

/*
 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
 *
 *                           p-1
 * u' = (u + d1)*y^p + 1024*\Sum y^n + d3*y^0
 *                           n=1
 *
 *    = u*y^p +					(Step 1)
 *
 *                     p-1
 *      d1*y^p + 1024*\Sum y^n + d3*y^0		(Step 2)
 *                     n=1
 */

上面将结果分为Step1和Step2是为了和接下来我们要说的代码实现对应起来。

代码实现

以上公式在代码中由两部分实现，accumulate_sum()函数计算总的负载，在函数中decay_load()函数负责计算step1部分，然后调用__accumulate_pelt_segments()函数计算step2部分。
我们先来看总的负载贡献计算函数accumulate_sum()：

/* * 计算单次调度的负载贡献。 * delta：此次调度的时间 * sa：调度实体se或者就绪队列cfs_rq的负载信息 */
static __always_inline u32
accumulate_sum(u64 delta, struct sched_avg *sa,
	       unsigned long load, unsigned long runnable, int running)
{ 
   
	u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
	u64 periods;

    /* * 我们可以把时间d分成3和部分：d1是离当前时间最远（不完整的）period 的剩余部分，d2 是完整period时间，而d3是（不完整的）当前 period 的剩余部分。 * 假设时间d是经过p个周期（d=d1+d2+d3, p=1+d2/1024）。 * period_contrib记录的是上次更新负载时不足1024us周期的时间（d3），下次计算时需要将这个时间加上算周期,这样除以1024之后得到就是真正的p值，而不需要+1。 * 比如上次是进程第一次运行，即从第一个1024us周期开始从头运行，运行了1034us，这轮调度结束时会记录period_contrib为1034-1024=10， * 下一轮调度开始时计算周期就需要考虑上次的这个10,但是也只是仅仅计算周期的时候时候考虑这个10,算负载的时候这个10不需要计算，因为这个10已经包含在上一次的负载u中，负载u只需要跟着乘以y^p就行。 */
	delta += sa->period_contrib;  
	periods = delta / 1024; /* A period is 1024us (~1ms) */  // 计算经过了多少个1024us周期。

	/* * Step 1: decay old *_sum if we crossed period boundaries. * 计算u*y^p */
	if (periods) { 
   
		sa->load_sum = decay_load(sa->load_sum, periods);  // 计算之前负载对现在的影响，即做负载衰减计算，为公式中的 u*y^p
		sa->runnable_load_sum =
			decay_load(sa->runnable_load_sum, periods);  // 计算之前runnable状态进程贡献的负载对现在的影响，一样也是做负载衰减计算。
		sa->util_sum = decay_load((u64)(sa->util_sum), periods);  // 计算之前running状态进程贡献的负载对现在的影响，一样也是做负载衰减计算。

		/* * Step 2 * p-1 * d1 y^p + 1024 \Sum y^n + d3 y^0 * n=1 */
		delta %= 1024;  // delta的值代表d3
		if (load) { 
   
			/* * This relies on the: * * if (!load) * runnable = running = 0; * * clause from ___update_load_sum(); this results in * the below usage of @contrib to dissapear entirely, * so no point in calculating it. */

			/* * 计算当前这一次调度贡献的负载。 * p-1 * d1*y^p + 1024 \Sum y^n + d3*y^0 * n=1 * * d1：1024 - sa->period_contrib * p：periods * d3：delta */
			contrib = __accumulate_pelt_segments(periods,
					1024 - sa->period_contrib, delta);
		}
	}
	sa->period_contrib = delta;  // 更新period_contrib为本次最后不足1024us的那部分(d3)。
    

	/* * 对于se来说： * load：se是否在就绪队列上 * runnable：se是否在就绪队列上 * running：se是否在当前CPU上执行 * 对于blocked se来说： * load：0 * runnable：0 * running：0 */
	/* * （下面的三个“+=”表示在新的这段时间区间内，se的权重产生的负载贡献） */
	if (load)
		sa->load_sum += load * contrib;  // load_sum的最大值为LOAD_AVG_MAX - 1024 + se->period_contrib。
	if (runnable)
		sa->runnable_load_sum += runnable * contrib;  // load_sum的最大值为LOAD_AVG_MAX - 1024 + se->period_contrib
	if (running)
		sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;

	return periods;
}

Step1关于 “u*y^p” 的计算函数decay_load()：

#define LOAD_AVG_PERIOD 32

/* * 用于计算第n个周期的衰减值， * val*y^n，其中 y^32 = 0.5,即y=0.97857206; * (val是某个1024us内的负载值，n代表经过了n个1024us周期后，当时的负载对现在的影响，影响不是瞬间消失，是个逐渐衰减的过程)。 * * 为了避免浮点数计算，val*y^n = val*y^n*2^32>>32 = val*runnable_avg_yN_inv[n]>>32; */
static u64 decay_load(u64 val, u64 n)
{ 
   
	unsigned int local_n;

	if (unlikely(n > LOAD_AVG_PERIOD * 63))  // 我们认为经过LOAD_AVG_PERIOD * 63周期，即经过2016个周期衰减为0。y^n=0, 即n>2016
		return 0;

	/* after bounds checking we can collapse to 32-bit */
	local_n = n;

	/* * As y^PERIOD = 1/2, we can combine * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD) * With a look-up table which covers y^n (n<PERIOD) * * To achieve constant time decay_load. */
	/* * decay_load(val,n) * 当n<32，val * y^n = val * y^n * 2^32 >> 32 = val * runnable_avg_yN_inv[n] >> 32; * 当n>=32 && n <64，val * y^n = val * y^32 * y^(n-32) * 2^32 >> 32 = val * 1/2 *runnable_avg_yN_inv[n-32] >> 32 = ; (当n大于等于32的时候，就需要根据y^32=0.5这个前提条件来计算y^n的值)， * 通用方法处理n>=32：val * y^n * 2^32 >> 32 = val * (y^32)^(n/32) * y^(n%32) * 2^32 >> 32 = val*(1/2)^(n/32) * y^(n%32)*2^32 >> 32 = (val >> (n / LOAD_AVG_PERIOD)) * runnable_avg_yN_inv[n%32] >> 32。 */
	if (unlikely(local_n >= LOAD_AVG_PERIOD)) { 
   
		val >>= local_n / LOAD_AVG_PERIOD;  // (local_n / LOAD_AVG_PERIOD) 等于几，则val需要乘以几个y^32(0.5)，即val向右移动几位。
		local_n %= LOAD_AVG_PERIOD;  // local_n对LOAD_AVG_PERIOD取余后的值为最后不足32个周期的部分。
	}

	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);  // val * runnable_avg_yN_inv[local_n] >> 32
	return val;
}

                                              p-1
Step2关于： d1y^p + 1024 \Sum y^n + d3y^0 的计算函数__accumulate_pelt_segments如下：
                                              n=1

/* * 计算当前这一次调度贡献的负载。 * p-1 * d1*y^p + 1024 \Sum y^n + d3*y^0 * n=1 * periods: 周期p，p的值为1 + d2/1024 * d1:d1 * d3:d3 */
static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
{ 
   
	u32 c1, c2, c3 = d3; /* y^0 == 1 */

	/* * c1 = d1 * y^p */
	c1 = decay_load((u64)d1, periods);


	/* p-1 * c2 = 1024 \Sum y^n * n=1 * * 当前等差数列的最大值max: * inf inf p-1 * max = 1024 \Sum y^n = 1024 ( \Sum y^n + \Sum y^n + y^0 ) * n=0 n=p n=1 * * inf inf * \Sum y^n = ( \Sum y^n ) y^p * n=p n=0 * * 开始推导: * * p-1 * c2 = 1024 \Sum y^n * n=1 * * inf inf * = 1024 ( \Sum y^n - \Sum y^n - y^0 ) * n=0 n=p * * inf inf * = 1024 * \Sum y^n - 1024 * \Sum y^n - 1024 * n=0 n=p * * inf inf * = 1024 * \Sum y^n - 1024 * ( \Sum y^n ) y^p - 1024 * n=0 n=0 * * = max - max * y^p - 1024 */
	c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;

	return c1 + c2 + c3;
}

至此，我们对于负载的计算介绍完毕。

调度实体更新负载贡献

更新调度实体负载的函数是__update_load_avg_se()：

int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)
{ 
   
	// 计算调度实体se的负载总和信息。
	// !!se->on_rq：是否在就绪队列上
	// cfs_rq->curr == se：是否正在CPU上执行 
	if (___update_load_sum(now, &se->avg, !!se->on_rq, !!se->on_rq,
				cfs_rq->curr == se)) { 
     // 计算调度实体se的负载总和信息。

		// 更新平均负载信息。例如sa->load_avg、sa->runnable_load_avg。
		___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
		cfs_se_util_change(&se->avg);
		trace_pelt_se_tp(se);
		return 1;
	}
	return 0;
}

负载的更新主要分为两部分，第一部分为更新负载总和信息，第二部分为更新平均负载信息。
更新负载总和信息函数如下为___update_load_sum：

static __always_inline int
___update_load_sum(u64 now, struct sched_avg *sa,
		  unsigned long load, unsigned long runnable, int running)
{
	u64 delta;

	delta = now - sa->last_update_time;  // delta是两次负载更新的时间差，单位是ns。
	
	if ((s64)delta < 0) {
		sa->last_update_time = now;
		return 0;
	}

	/*
	 * Use 1024ns as the unit of measurement since it's a reasonable
	 * approximation of 1us and fast to compute.
	 */
	delta >>= 10;  // 整除1024是将ns转换为us。
	if (!delta)  // PELT算法最小时间计量单位是us，如果时间差连1us都不到，就没必要衰减，直接返回即可。
		return 0;

	sa->last_update_time += delta << 10;  // 更新last_update_time，用于下一次更新负载值的时候计算delta值。

	if (!load)
		runnable = running = 0;

	/*
	 * Now we know we crossed measurement unit boundaries. The *_avg
	 * accrues by two steps:
	 *
	 * Step 1: accumulate *_sum since last_update_time. If we haven't
	 * crossed period boundaries, finish.
	 */

	/*
	 * 负载贡献计算。
	 * 因为此时的load、runnable、running非0即1，且load和runnable值相等，都表示是否在就绪队列上，所以sa->load_sum与sa->runnable_load_sum相等， 
	 *    且最大值就是LOAD_AVG_MAX - 1024 + se->period_contrib（即一直处于runnable状态）。
	 */
	if (!accumulate_sum(delta, sa, load, runnable, running))
		return 0;

	return 1;
}

accumulate_sum函数就不说了，上面有详细解释。

更新平均负载信息函数为___update_load_avg:

static __always_inline void
___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
{
	/*
	 * 理论上最大的负载值，即系统开始就一直在运行，中间也没停过，“- 1024 + sa->period_contrib”是因为最后一个周期的实际运行时间为sa->period_contrib，可能没满一个周期。
	 */
	u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;  
	/*
	 * Step 2: update *_avg.
	 */

	/*
	 *                               se->load_sum
     * se->load_avg = -------------------------------------------- * se->load.weight
     *                    LOAD_AVG_MAX - 1024 + sa->period_contrib
     *
     *                              se->runnable_load_sum
     * se->runnable_load_avg = -------------------------------------------- * se->runnable_weight
     *                           LOAD_AVG_MAX - 1024 + sa->period_contrib
	 */
	/*
	 * 对task se来说，se->load_avg和se->runnable_load_avg的值是相等的（因为，se->load_sum和se->runnable_load_sum相等，并且se->load.weight和se->runnable_weight相等），并且其值是小于等于se->load.weight。
	 * 上面这个公式左半边可以简单理解为当前se的load_sum占最大衰减值（即假设一直运行会产生的负载）的比重，然后乘以当前se的权重。(针对频繁运行的进程，load_avg的值会越来越接近权重weigh)。
	 */
	sa->load_avg = div_u64(load * sa->load_sum, divider);
	sa->runnable_load_avg =	div_u64(runnable * sa->runnable_load_sum, divider);
	WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
}

就绪队列更新负载贡献

更新就绪队列负载信息的函数是update_cfs_rq_load_avg()：

int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
{
	if (___update_load_sum(now, &cfs_rq->avg,
				scale_load_down(cfs_rq->load.weight),
				scale_load_down(cfs_rq->runnable_weight),
				cfs_rq->curr != NULL)) {

		___update_load_avg(&cfs_rq->avg, 1, 1);
		trace_pelt_cfs_tp(cfs_rq);
		return 1;
	}

	return 0;
}

per-entity load tracking有什么好处呢？

• 更精细的统计数据
    调度器现在对于负载的认知从就绪队列到了对每个进程或“调度组”。
• 负载均衡
     即把runnable进程平均分配到系统的CPU上，使每个CPU承载大致相同的负载。如果内核知道每个进程对系统负载有多大贡献，它可以很容易地计算迁移到另一个CPU的效果。这样进程迁移的结果应该更准确，从而使得负载均衡更加有合理依据。
• small-task packing patch
     small-task packing patch的目标是将“小”进程收集到系统中的部分CPU上，从而允许系统中的其他处理器进入低功耗模式（“小”进程是指处理时间短、资源占用比较少的任务，集中在部分CPU上可以减少CPU之间的切换和通信的开销）。在这种情况下，显然我们需要一种方法来计算得出哪些进程是“小”的进程。利用per-entity load tracking，内核可以轻松的进行识别。
• 基于过去预测未来
    CPU频率调节器（CPU frequency governor）和功率调节器（CPU power governor）可以利用per entity负载值来猜测在不久的将来，系统需要提供多少的CPU计算能力。

今天的文章Linux内核源码分析-进程调度(六)-PELT(per-entity load tracking)[通俗易懂]分享到此就结束了，感谢您的阅读。