宅男
分类： Android平台
2017-07-07 16:57:14
这一篇准备介绍一下CFS的PELT（per entity load tracking）。这一套用来量化进程的负载的模型。这套模型在__update_load_avg函数上面的注释中有详细的解释。
其主要思想是将进程的运行时间切分为以1ms为单位的时间片段。过去的每一个时间片段对于进程负载的影响也不同。为了便于计算，将1ms设置为1024us。
* [<- 1024us="" -="">|<- 1024us="" -="">|<- 1024us="" -="">| ...
* p0 p1 p2
* (now) (~1ms ago) (~2ms ago)
假设了一个时间因子y，那么进程的负载可以表示为：
u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
那么这个时间因子是多少呢？linux内核将其设置为 y^32 = 0.5 .即没隔32ms，其影响力为原来的一半。
那么最大的负载（load）是多少呢？1024(1+y+y2 + y3 + ... ) = 1024*(y/1-y) = 47742
所以内核定义了几个宏
#define LOAD_AVG_PERIOD 32
#define LOAD_AVG_MAX 47742 /* maximum possible load avg */
#define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_AVG_MAX */
其中LOAD_AVG_PERIOD为32，即每隔32ms，衰减一半。LOAD_AVG_MAX为最大的load值。LOAD_AVG_MAX_N为达到LAOD_AVG_MAX，进程所需要连续运行的时间。
下面直接进入函数。
static u32 __compute_runnable_contrib(u64 n)
{
u32 contrib = 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;
为了方便计算，linux预设值了一个算好的数组。
/*
* Precomputed \Sum y^k { 1<=k<=n }. These are floor(true_value) to prevent
* over-estimates when re-combining.
*/
static const u32 runnable_avg_yN_sum[] = {
0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
};
其中计算的值是在不同N值下，1024（y+y2 + y3 + ... ) 计算出来的值。
由于每隔32ms需要衰减一半，所以只需要计算32个值就可以了。
再次回到代码。
if (likely(n <= LOAD_AVG_PERIOD))
return runnable_avg_yN_sum[n];
else if (unlikely(n >= LOAD_AVG_MAX_N))
return LOAD_AVG_MAX;
如果n值小于等于32，直接从预先算好的数组获取就可以了，如果N值大于LOAD_AVG_MAX_N，就获得了最大load值LOAD_AVG_MAX。
/* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
do {
contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
n -= LOAD_AVG_PERIOD;
} while (n > LOAD_AVG_PERIOD);
contrib = decay_load(contrib, n);
return contrib + runnable_avg_yN_sum[n];
do while循环中，每隔32ms衰减一半，并加上最近的这32ms中的load值。
contrib = decay_load(contrib, n)用于计算contrib在经过n个ms之后剩余多少。
从decay_load这个函数的注释就可以看出来这段函数的作用。
/*
* Approximate:
* val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
*/
static __always_inline u64 decay_load(u64 val, u64 n)
再次回到__update_load_avg用于计算一个进程的对于load的贡献。
其中weight是指进程的weight值。
static __always_inline int
__update_load_avg(u64 now, int cpu, struct sched_avg *sa,
unsigned long weight, int running, struct cfs_rq *cfs_rq)
{
u64 delta, scaled_delta, periods;
u32 contrib;
unsigned int delta_w, scaled_delta_w, decayed = 0;
unsigned long scale_freq, scale_cpu;
delta = now - sa->last_update_time;
//last_update_time为上一次更新load的时间。
/*
* This should only happen when time goes backwards, which it
* unfortunately does during sched clock init when we swap over to TSC.
*/
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;
if (!delta)
return 0;
由于PELT中是为ms以及us为单位计算load值的，而内核的时间是以ns为单位的。
所以需要将ns转变成us，为了计算简单，以1us=1024ns来计算。
scale_freq = arch_scale_freq_capacity(NULL, cpu);
scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
/* delta_w is the amount already accumulated against our next period */
delta_w = sa->period_contrib;
由于超过1024也就是1ms。就需要衰减。所以这边需要判断delta+sa->period_contrib.
if (delta + delta_w >= 1024) {
decayed = 1;
/* how much left for next period will start over, we don't know yet */
sa->period_contrib = 0;
/*
* Now that we know we're crossing a period boundary, figure
* out how much from delta we need to complete the current
* period and accrue it.
*/
delta_w = 1024 - delta_w;
scaled_delta_w = cap_scale(delta_w, scale_freq);
if (weight) {
sa->load_sum += weight * scaled_delta_w;
if (cfs_rq) {
cfs_rq->runnable_load_sum +=
weight * scaled_delta_w;
}
}
if (running)
sa->util_sum += scaled_delta_w * scale_cpu;
delta -= delta_w;
/* Figure out how many additional periods this update spans */
periods = delta / 1024;
delta %= 1024;
sa->load_sum = decay_load(sa->load_sum, periods + 1);
if (cfs_rq) {
cfs_rq->runnable_load_sum =
decay_load(cfs_rq->runnable_load_sum, periods + 1);
}
sa->util_sum = decay_load((u64)(sa->util_sum), periods + 1);
/* Efficiently calculate \sum (1..n_period) 1024*y^i */
contrib = __compute_runnable_contrib(periods);
contrib = cap_scale(contrib, scale_freq);
if (weight) {
sa->load_sum += weight * contrib;
if (cfs_rq)
cfs_rq->runnable_load_sum += weight * contrib;
}
if (running)
sa->util_sum += contrib * scale_cpu;
}
这里面涉及到sa的两个成员变量：util_sum，load_sum。
其中util_sum指task出于running状态的load，其中util是指utilization，后面根据CPU使用率的情况调整频率的时候，需要用到该变量。而load_sum是指出于runnable（包括running）时间的load。
其中arch_scale_freq_capacity为
#define
unsigned long cpufreq_scale_freq_capacity(struct sched_domain *sd, int cpu)
{
return per_cpu(freq_scale, cpu);
}
下面是计算freq_scale的代码。
unsigned long scale = (cur << SCHED_CAPACITY_SHIFT) / policy->max;
//根据max freq来计算当前频率对应的capacity，最大值为1024.
struct cpufreq_cpuinfo *cpuinfo = &policy->cpuinfo;
int cpu;
pr_debug("cpus %*pbl cur/cur max freq %lu/%u kHz freq scale %lu\n",
cpumask_pr_args(policy->cpus), cur, policy->max, scale);
for_each_cpu(cpu, policy->cpus)
per_cpu(freq_scale, cpu) = scale;
另外arch_scale_cpu_capacity
#define
由于B-L架构存在CPU之间的性能差异，所以除了计算当前freq带来的归一化的系数。CPU之间的差异同样影响load的计算。就是用来计算CPU的影响因子。
所以在调用__update_load_avg计算task的load的时候，需要同时考虑当前frequency以及CPU带来的影响。
PELT几乎是fair的核心。它同时决定了scheduler的两大核心，即选择那个task，选择那个CPU。
（1） 从rq上调用pick_next_task选择下一个可执行的fair task时，需要选择vruntime最小的进程或者group，如果是group的话，继续递归下去从group中选择vruntime最小的。直到选择到一个task为止。
（2） 为new task或者wake up的task选择rq的时候，需要选择一个idlest的CPU，即整体负载load最小的rq。
如果仔细查看select_task_rq_fair函数就会发现这套代码基本是为SMP架构设计的。现在只是简单的打了一些补丁而已，其实并不适合于现在手机上普遍使用的BL架构的SOC。因为这里面基本只考虑的load的影响，没有考虑BL中大小核的功耗的差异，因为大小核之间在功耗以及IPC相关差异比较明显。到底怎么量化需要另外一套模型。
同时PELT也是不太适合于手机等设备的，PELT根据运行时间来计算历史累计的负载。存在两方面的问题
（1） PELT在计算一个task的累积影响时存在很大的延迟，注意上面提到的LOAD_AVG_MAX_N宏，即一个100%的task从创建开始，需要持续出于runnable状态345ms才能达到最大load值。
（2） 同样由于只计算runnable的累计load，如果一旦task由于某种原因进入sleep状态，那么其load值就急剧衰减，大约213ms就衰减为0.
这两个影响使得PELT并不适用于对于时间比较敏感的设备，如手机，平板电脑等等。
当然CFS里面的代码太多，而且太过于繁杂，很多都是关于cgroup以及load balance相关的，在后面会一点点剖析。