在之前的系列文章中，我们反复提到 CFS（Completely Fair Scheduler）的核心目标就是“公平”——通过 vruntime、权重（weight）和 PELT 等机制，确保每个进程按照其 nice 值比例公平分享 CPU 时间。

这套设计在多任务、通用服务器场景下表现优秀，但随着硬件和应用场景的演进，CFS 暴露出了一个越来越明显的短板：对延迟（latency）的支持不足。

而现在随着Linux嵌入式的高性能开发越来越普及，内核也想设计一个对latency支持更好的调度器，也就是EEVDF

本文就来聊聊 CFS 在公平性之外，为什么对延迟敏感任务的处理显得力不从心，以及为什么简单靠 nice 值或 rt class 都无法完美解决这个问题。

# CFS的不足
还记得我之前举了一个分蛋糕的例子，现在基于之前的再举一个相似的例子

想象一个幼儿园分蛋糕的场景：CFS 就像一个严格按“体重比例”分蛋糕的阿姨——你 nice 值高（权重高），就能多分一块；nice 值低，就少分一点。整体上大家都没饿着，公平得很。
但如果有个小朋友只是偶尔想吃一口（低吞吐需求），却希望“现在就要吃到”，而另一个小朋友能吃一整块但可以等会儿再吃——阿姨的规则却只知道“谁体重大谁多吃”，完全不考虑“谁更着急”。
结果就是：着急的小朋友哭了半天还没吃到（延迟高），而能等的那个反而先吃饱了（响应差）。这正是 CFS 当前在延迟敏感任务上的痛点。

CFS 的核心公式大家都很熟：
```
vruntime += delta_exec * NICE_0_LOAD / weight
```
也就是说
1. weight 越大（nice 值越低），vruntime 增长越慢 → 更容易被 pick_next_task 选中 → 获得更多 CPU 时间。
2. PELT + min_vruntime 维护了跨 CPU 的公平性。
3. nice 值本质上是“吞吐量优先级”：你想要更多 CPU 时间，就调低 nice。

这套机制对“长期公平分享 CPU”非常有效，但在“短期响应延迟”上却力不从心。

# 高实时任务的典型痛点
## 交互式任务
假设是桌面 UI、游戏输入、终端敲命令，它们对 CPU 吞吐需求很低（可能每秒只跑几 ms），但一旦有输入事件，就希望在 1–5 ms 内得到响应。
如果当前有几个 CPU 密集型任务（nice 0 或正 nice），它们 vruntime 增长慢，会持续霸占 CPU，交互任务即使 vruntime 很小，也可能被延迟十几甚至几十 ms。

## 实时任务
假设是音频处理、视频编码预处理、实时监控、飞行控制、相机链路，这些任务对吞吐要求中等，但对延迟有硬性要求（比如音频缓冲区 underrun 就会爆音）。
CFS 无法表达“我不需要很多 CPU，但需要低延迟”的诉求——nice 值只能给你更多时间片，却不能保证“尽快给我一次”。

## 混合负载的不公平性
在linux桌面上，例如大家使用的ubuntu，centos，或者麒麟系统，如果一边使用，后台一边编译代码，，CFS 会让编译任务占满大部分时间，使用的浏览器，QT程序会卡顿非常明显

# 为什么CFS自身解决不掉延迟问题
cfs的 nice 值本质上是吞吐量权重，不是延迟优先级。调低 nice（-10）→ 权重变大 → vruntime 增长慢 → 获得更多 CPU 时间（吞吐提升），但不保证“下次调度更快”。
即使 nice 很低，如果当前 vruntime 已经被其他任务拉开差距，仍然要等别人“还债”完。

CFS 的 vruntime 机制是“累计欠债还债”，不是“谁着急谁先上”。
这就好比银行贷款：nice 值高的人利息低、额度高，但排队顺序还是看谁先借的，而不是谁更急用钱。

当然，Linux 也提供了实时调度类（rt_sched_class），优先级高于 CFS，可以实现低延迟。但是有如下缺点
1. 饥饿风险：高优先级 rt 任务如果不主动 yield，会饿死所有 CFS 任务（优先级倒挂）。
2. 系统整体影响：滥用 rt 会让整个系统响应变差（键盘卡顿、鼠标延迟等）。
3. 不适合大多数延迟敏感任务：很多应用只是“偶尔低延迟”，而不是“一直高优先级”

总而言之，言而总之，社区仍选择发展eevdf，其原因是 rt class 太重了。除非你是一个对调度非常熟悉的开发者在使用rt，否则一定会存在大量的管理，错误使用等问题。

# 总结
CFS 的公平性设计非常成功，它让多任务系统在吞吐量上达到了前所未有的均衡。
但公平不等于响应快——nice 值只能告诉你“谁该多吃”，却无法回答“谁该先吃”。
在桌面、游戏、移动、软实时等场景下，延迟敏感任务越来越重要，单纯靠 rt class 或调 nice 都已力不从心。这在开发高性能交互系统或实时应用时至关重要。理解 CFS 的延迟短板，我们就能更好地选择调度策略、调优参数

# 参考
> https://lwn.net/Articles/925371/


























调度(14)-CFS调度的不足性

上一篇文章中介绍了 accumulate_sum 函数，此函数实现了load_sum/runnable_sum/util_sum的计算，而实际上的计算方式是 decay_load，本文介绍decay_load函数

另一方面accumulate_sum也使用了__accumulate_pelt_segments函数来计算新值贡献，本文一并介绍清楚
# __accumulate_pelt_segments
此函数的实现如下
```
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
         *
         *              inf        inf
         *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )
         *              n=0        n=p
         */
        c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;

        return c1 + c2 + c3;
}
```
此函数比较清晰，首先使用了 decay_load 计算`d1*y^p`周期的衰减，然后使用LOAD_AVG_MAX这个速算值，如下
```
1024 × Σ(y^n, n=1 到 p-1)
```
最终就是上文提到的
```
d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0
```
在此函数中我们记作
```
c1 + c2 + c3
```
所以此函数我们的重点是解析c2
```
c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
```
首先我们看看我们计算的目标
```
c2 = 1024 × (y¹ + y² + y³ + ... + y^{p-1})
```
我们先以始为终的方式认为
```
LOAD_AVG_MAX = 1024 * Σ(y^n, n=0 到 n)
```
那么 `decay_load(LOAD_AVG_MAX, periods)` 就是 
```
1024 * Σ(y^n, n=p)
```
那么两值相减就是
```
1024 * Σ(y^n, n=0 到 p) = 1024 * Σ(y^n, n=0 到 n) - 1024 * Σ(y^n, n=p)
```
我们要求的c2是
```
Σ(y^n, n=1 到 p-1) = 1024 * Σ(y^n, n=0 到 p) - 1024 * y^0
```
那就就得到了
```
c2 = 1024 * ((y0 + y² + y³ + ... + y^{n}) - (y0 + y² + y³ + ... + y^{p}) - (y0))
```
进入代码转换就是
```
c2 = 1024 * (LOAD_AVG_MAX / 1024 - decay_load(LOAD_AVG_MAX, periods) / 1024 - 1);
```
## LOAD_AVG_MAX 
好了，那么我们继续关注 LOAD_AVG_MAX 这个宏，为什么它假设成立，我们看假设
```
LOAD_AVG_MAX = 1024 * Σ(y^n, n=0 到 n)
或
LOAD_AVG_MAX = 1024 * (y0 + y² + y³ + ... + y^{n})
```
我们看代码的定义
```
#define LOAD_AVG_MAX pelt_load_avg_max
int pelt_load_avg_max = PELT32_LOAD_AVG_MAX;
#define PELT32_LOAD_AVG_MAX 47742
```
所以我们看 47742 这个值怎么预先计算的
我们先看y这个常量
```
y^32 = 0.5
y = 0.9786
```
按照我们之前分析的，LOAD_AVG_MAX等效于
```
LOAD_AVG_MAX / 1024 = (y0 + y² + y³ + ... + y^{n})
```
因为y = 0.9786， 所以此公式是收敛的，我们一定可以获取一个收敛值。下面开始计算，假设`S = LOAD_AVG_MAX / 1024 `
```
S = 1 + y + y² + y³ + ... + y^{n}
S * y = y + y2 + y3 + ... + y^{n+1}
S - S * y = (1 + y + y² + y³ + ... + y^{n}) - (y + y2 + y3 + ... + y^{n+1})
```
我们假设取n为无限值先，那么n=n+1，可以得到近似如下
```
S * (1 - y) = 1
S = 1 / (1 - y)
```
我们要计算的是LOAD_AVG_MAX，这里把1024代入
```
LOAD_AVG_MAX = 1024 / (1 - y)
```
然后我们把y代入
```
y = 2^(-1/32)
LOAD_AVG_MAX = 1024 / (1 - 2^(-1/32)) = 47742
```
所以内核直接预先计算了 LOAD_AVG_MAX 为 47742。

到这里，我们就完全明白了__accumulate_pelt_segments的计算过程，下面看decay_load
# decay_load
首先看函数原型
```
/*
 * Approximate:
 *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
 */
static u64 decay_load(u64 val, u64 n)
{
        unsigned int local_n;

        if (unlikely(n > LOAD_AVG_PERIOD * 63))
                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.
         */
        if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
                val >>= local_n / LOAD_AVG_PERIOD;
                local_n %= LOAD_AVG_PERIOD;
        }

        val = mul_u64_u32_shr(val, pelt_runnable_avg_yN_inv[local_n], 32);
        return val;
}
```
我们知道 decay_load 用来计算就旧值衰减 `u y^p`，所以输入参数是`val, n`，下面看LOAD_AVG_PERIOD的定义
```
#define LOAD_AVG_PERIOD pelt_load_avg_period
int pelt_load_avg_period = PELT32_LOAD_AVG_PERIOD;
#define PELT32_LOAD_AVG_PERIOD 32
```
如果local_n大于等于32，那么将local_n除以32后，这样可以速算y^32的部分，因为其值是0.5。解释如下
```
y^n = y^(32*n/32) * y^(n%32)
```
这种展开就是为了让 `y^32 = 0.5` 能够速算为如下
```
y^n = 0.5^(n/32) * y^(n%32)
```
## pelt_runnable_avg_yN_inv
上面通过代码分析描述了decay_load的目的，其计算就是简单将`y^n`拆解成`0.5^(n/32) * y^(n%32)`，而实际计算的时候，还依赖另一个速算表pelt_runnable_avg_yN_inv，我们先看其定义
```
pelt_runnable_avg_yN_inv = pelt32_runnable_avg_yN_inv;
static const u32 pelt32_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,
};
```
这个是y^(-n)的速算值，n的取值范围是0-31。为什么要这样速算呢，如下

首先我们知道y^32=0.5，我的目的是计算`val * y^n`，那么可以拆解如下
```
val * y^n = val / y^(32-n) * y^32 ~= val * y^(-n) / 2^32
```
所以 pelt32_runnable_avg_yN_inv 就是 `y^(-n)`, 这样只需要统计获取n从0-31的所有值进行计算进行代入，也就是如下
```
val * y^n = val * pelt32_runnable_avg_yN_inv / 2^32
```
# 总结
本文介绍了CFS中计算累加和以及旧值衰减的计算公式和速查表解释。可以看到，cfs中通过内置预先计算好的表来屏蔽复杂运算的耗时，而计算的过程中，通过一定的数据近似尽可能的获得了累加和和旧值衰减的较准确值。

我们在开发调度的时候，这些东西不需要取修改，因为是社区经过统计得出来得有效经验值，但是为了更清晰得了解调度，这个详细得计算细节还是要扣清楚的。










调度(13)-CFS调度PELT(2)

PELT的全称为: Per-Entity Load Tracking, 根据直面意思,这是基于se的load tracking, PELT能够提供提供当前系统基于per-entity的负载情况. 具体点说就是通过用指数衰减的方式，把历史运行时间转化为当前负载预测，帮助负载均衡、CPU调频和能耗管理。
# 为什么需要 PELT 
在之前的文章<调度(10)-CFS调度reweight>中可以看到,calc_group_shares函数在实际计算的时候引用了PELT的计算值,根据此,我们可以看到如果没有PELT,可能有如下问题
1. **响应延迟**：任务负载突变时，调度器反应迟钝
2. **精度不足**：无法区分短时爆发和持续高负载

主要原因是,如果按照传统计算平均值的方式,那么只能统计过去一段时间的平均值,而PELT能够实时的了解per-entity的负载情况

PELT 于 2013 年在 Linux 3.8 内核中引入，是 Vincent Guittot 等开发者的重要贡献, 彻底改变了 CFS 的负载感知能力。 

# PELT原理
PELT使用以过去的状态统计现在的负载的思路进行设计,它通过wall clock视为1ms(1024份)为单位` 1ms (actually, 1024µs)`在每个1ms的区间内,一个se对系统的新增的负载贡献取决于se_runable在rq上的时间比例,除此之外,之前的entity对系统产生的负载也会通过指数衰减累计下来,用作每次计算负载的参数,以公式的方式记录为如下
```
L_t = l_t + (y*l_{t-1}) + (y^2*l_{t-2}) ... + (y^t*l_0)
```
这里l_x是每个period记录的负载值,L_t是t时刻下计算总负载的值,y是计算的衰减因子,其默认y的固定值为
```
y^32 = 0.5
```
这里计算y是0.9786

此时我们计算L_t-1的公式,如下
```
L_{t-1} = l_{t-1} + (y*l_{t-2}) + (y^2*l_{t-3}) ... + (y^{t-1}*l_0)
```
我们将Lt-1乘y,可以计算为
```
y*L_{t-1} = y*l_{t-1} + (y^2*l_{t-2}) + (y^3*l_{t-3}) ... + (y^{t}*l_0)
```
拿这个公式和最上面L_t计算,可以得到递归公式如下
```
L_t = l_t + y * L{t_1}
```
关于此公式,内核也提供了注释说明,如下
```
/*
 * We can represent the historical contribution to runnable average as the
 * coefficients of a geometric series.  To do this we sub-divide our runnable
 * history into segments of approximately 1ms (1024us); label the segment that
 * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
 *
 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
 *      p0            p1           p2
 *     (now)       (~1ms ago)  (~2ms ago)
 *
 * Let u_i denote the fraction of p_i that the entity was runnable.
 *
 * We then designate the fractions u_i as our co-efficients, yielding the
 * following representation of historical load:
 *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
 *
 * We choose y based on the with of a reasonably scheduling period, fixing:
 *   y^32 = 0.5
 *
 * This means that the contribution to load ~32ms ago (u_32) will be weighted
 * approximately half as much as the contribution to load within the last ms
 * (u_0).
 *
 * When a period "rolls over" and we have new u_0`, multiplying the previous
 * sum again by y is sufficient to update:
 *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
 *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
 */
```
# 数据结构
## sched_avg
```
/*
 * The load/runnable/util_avg accumulates an infinite geometric series
 * (see __update_load_avg_cfs_rq() in kernel/sched/pelt.c).
 *
 * [load_avg definition]
 *
 *   load_avg = runnable% * scale_load_down(load)
 *
 * [runnable_avg definition]
 *
 *   runnable_avg = runnable% * SCHED_CAPACITY_SCALE
 *
 * [util_avg definition]
 *
 *   util_avg = running% * SCHED_CAPACITY_SCALE
 *
 * where runnable% is the time ratio that a sched_entity is runnable and
 * running% the time ratio that a sched_entity is running.
 *
 * For cfs_rq, they are the aggregated values of all runnable and blocked
 * sched_entities.
 *
 * The load/runnable/util_avg doesn't directly factor frequency scaling and CPU
 * capacity scaling. The scaling is done through the rq_clock_pelt that is used
 * for computing those signals (see update_rq_clock_pelt())
 *
 * N.B., the above ratios (runnable% and running%) themselves are in the
 * range of [0, 1]. To do fixed point arithmetics, we therefore scale them
 * to as large a range as necessary. This is for example reflected by
 * util_avg's SCHED_CAPACITY_SCALE.
 *
 * [Overflow issue]
 *
 * The 64-bit load_sum can have 4353082796 (=2^64/47742/88761) entities
 * with the highest load (=88761), always runnable on a single cfs_rq,
 * and should not overflow as the number already hits PID_MAX_LIMIT.
 *
 * For all other cases (including 32-bit kernels), struct load_weight's
 * weight will overflow first before we do, because:
 *
 *    Max(load_avg) <= Max(load.weight)
 *
 * Then it is the load_weight's responsibility to consider overflow
 * issues.
 */
struct sched_avg {
        u64                             last_update_time;
        u64                             load_sum;
        u64                             runnable_sum;
        u32                             util_sum;
        u32                             period_contrib;
        unsigned long                   load_avg;
        unsigned long                   runnable_avg;
        unsigned long                   util_avg;
        struct util_est                 util_est;
} ____cacheline_aligned;
```
这里记录每一个period(1024us)的负载信息,分别信息解释如下
* last_update_time: 上次更新负载统计的时间戳
* load_sum: 负载的累加和（未衰减的原始值）
* runnable_sum: 可运行状态时间的累加和
* util_sum: 实际运行状态时间的累加和
* period_contrib: 当前周期内已贡献的时间比例份额
* load_avg: 平均负载
* runnable_avg: 平均runnable任务比例(1024计算)
* util_avg: 平均利用率
* util_est: 平均利用率的快速预估值

## ___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;
	/*
	 * 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;

	sa->last_update_time += delta << 10;

	/*
	 * running is a subset of runnable (weight) so running can't be set if
	 * runnable is clear. But there are some corner cases where the current
	 * se has been already dequeued but cfs_rq->curr still points to it.
	 * This means that weight will be 0 but not running for a sched_entity
	 * but also for a cfs_rq if the latter becomes idle. As an example,
	 * this happens during idle_balance() which calls
	 * update_blocked_averages().
	 *
	 * Also see the comment in accumulate_sum().
	 */
	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.
	 */
	if (!accumulate_sum(delta, sa, load, runnable, running))
		return 0;

	return 1;
}
```
`___update_load_sum`函数将sched_avg的_sum更新,其中input的load/runnable/running对于sched_avg的load_sum/runnable_sum/util_sum,所以我们需要看函数accumulate_sum的实现
## accumulate_sum
```
/*
 * Accumulate the three separate parts of the sum; d1 the remainder
 * of the last (incomplete) period, d2 the span of full periods and d3
 * the remainder of the (incomplete) current period.
 *
 *           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
 */
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;

	delta += sa->period_contrib;
	periods = delta / 1024; /* A period is 1024us (~1ms) */

	/*
	 * Step 1: decay old *_sum if we crossed period boundaries.
	 */
	if (periods) {
		sa->load_sum = decay_load(sa->load_sum, periods);
		sa->runnable_sum =
			decay_load(sa->runnable_sum, periods);
		sa->util_sum = decay_load((u64)(sa->util_sum), periods);

		/*
		 * Step 2
		 */
		delta %= 1024;
		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.
			 */
			contrib = __accumulate_pelt_segments(periods,
					1024 - sa->period_contrib, delta);
		}
	}
	sa->period_contrib = delta;

	if (load)
		sa->load_sum += load * contrib;
	if (runnable)
		sa->runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT;
	if (running)
		sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;

	return periods;
}
```
### Step 1: 旧值衰减
通过`decay_load`函数计算`u y^p `,包含三个值
* load_sum: 负载和的衰减值
* runnable_sum: 可运行和的衰减值
* util_sum: 利用率和衰减值

### Step 2: 新值贡献
通过`__accumulate_pelt_segments`计算新值贡献`d1 y^p + 1024 \Sum y^n + d3 y^0`,然后将其相加就是负载和,如下
* load_sum: += load * contrib
* runnable_sum: += runnable * contrib
* util_sum: += contrib

### 注释解释
假设有一个se再上一个时刻的load为u,经过delta时间后,我们尝试更新load,此时怎么计算这个delta的衰减呢?之前我们讨论的公式是将load乘以一个y的衰减量,但实际的代码分成了三个步骤
* d1: 在上次计算时,还差d1时间可以凑满一个period
* d2: p_contrub --> d1 后,剩下可形成的最大整数倍period(k*period)
* d3: p_contrub --> d1 --> d2,剩下不满一周期的时间

注释配图了如下
```
 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
```
如果我们计算这次经过了多少个period,那么我们可以先加上d1前的那个周期剩余值,也就是`1024 - d1`,那么计算p个period的公式为
```
p = (1024 - d1 + (d1 + d2 + d3)) / 1024
```
因为d3不满一个周期,所以没必要减掉一个d3再去除,默认除法取整了

所以带入原公式的p值
```
u' = (u + d1) × y^p + 1024 × y^(p-1) + 1024 × y^(p-2) + ... + 1024 × y^1 + d3 × y^0
```
展开第一个括号为
```
u' = u × y^p + d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0
```
回到代码上,可以看到
1. sa->period_contrib 为 1024 - d1
2. delta 从 d1+d2+d3 更新为 1024 - d1 + (delta)
3. period 为 p,通过(1024 - d1 + (d1 + d2 + d3)) / 1024 计算
4. decay_load 为 u × y^p 的计算,后面详细介绍
5. __accumulate_pelt_segments  为d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0 的计算值,后面详细介绍
6. d3 为 delta % 1024

# 总结
本文从宏观上介绍了PETL的结构体sched_avg和sum值计算,也简单说明了PELT的公式计算,但是遗留了decay_load 和 __accumulate_pelt_segments 的详细计算的介绍.

总体而言,PELT是linux负载均衡的核心,也是cfs中不可或缺的统计信息方式,深入了解PELT对理解CFS调度精髓而言至关重要

# 参考
> https://lwn.net/Articles/531853/

调度(12)-CFS调度PELT(1)

本文介绍一下CFS的另一个关键行为,选中下一个任务运行,当任务schedule的时候,会主动调用pick_next_task函数选出下一个需要调度的进程的任务

# 代码流程
```
__schedule
  pick_next_task
    __pick_next_task_fair
      pick_next_task_fair
        pick_next_entity
        set_next_entity
  context_switch
```
# pick_next_task
函数原型如下
```
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        const struct sched_class *class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in the fair class we can
         * call that function directly, but only if the @prev task wasn't of a
         * higher scheduling class, because otherwise those loose the
         * opportunity to pull in more work from other CPUs.
         */
        if (likely(prev->sched_class <= &fair_sched_class &&
                   rq->nr_running == rq->cfs.h_nr_running)) {

                p = pick_next_task_fair(rq, prev, rf);
                if (unlikely(p == RETRY_TASK))
                        goto restart;

                /* Assumes fair_sched_class->next == idle_sched_class */
                if (!p) {
                        put_prev_task(rq, prev);
                        p = pick_next_task_idle(rq);
                }

                return p;
        }

restart:
        put_prev_task_balance(rq, prev, rf);

        for_each_class(class) {
                p = class->pick_next_task(rq);
                if (p)
                        return p;
        }

        /* The idle class should always have a runnable task: */
        BUG();
}
```
根据代码,这里实际上有两个路径.区分代码为
```
if (likely(prev->sched_class <= &fair_sched_class &&
                   rq->nr_running == rq->cfs.h_nr_running))
```
也就是上一个任务是cfs调度,且所有任务都在cfs调度类中
## 路径1: 所有任务都在cfs调度类中
直接调用pick_next_task_fair,如果没有任务了,运行idle任务.如果有任务,则将上一个任务put_prev_task放回本地队列
## 路径2: 如果有rt类型的任务
因为有rt相关的实时任务,所以先put_prev_task_balance将其负载均衡检查,让rt任务拥有更高优先级权限,降低此任务因为负载均衡导致put_prev_task的时候响应时间增加.

然后遍历所有的调度器,运行pick_next_task_fair.
# pick_next_task_fair
函数简要实现如下
```
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
again:
        if (!sched_fair_runnable(rq))
                goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
        if (!prev || prev->sched_class != &fair_sched_class)
                goto simple;

        do {
                se = pick_next_entity(cfs_rq, curr);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);

        p = task_of(se);
        /*
         * Since we haven't yet done put_prev_entity and if the selected task
         * is a different task than we started out with, try and touch the
         * least amount of cfs_rqs.
         */
        if (prev != p) {
                struct sched_entity *pse = &prev->se;

                while (!(cfs_rq = is_same_group(se, pse))) {
                        int se_depth = se->depth;
                        int pse_depth = pse->depth;

                        if (se_depth <= pse_depth) {
                                put_prev_entity(cfs_rq_of(pse), pse);
                                pse = parent_entity(pse);
                        }
                        if (se_depth >= pse_depth) {
                                set_next_entity(cfs_rq_of(se), se);
                                se = parent_entity(se);
                        }
                }

                put_prev_entity(cfs_rq, pse);
                set_next_entity(cfs_rq, se);
        }

        goto done;
simple:
#endif
        if (prev)
                put_prev_task(rq, prev);

        if (repick) {
                for_each_sched_entity(se)
                        set_next_entity(cfs_rq_of(se), se);
                goto done;
        }

        do {
                se = pick_next_entity(cfs_rq, NULL);
                set_next_entity(cfs_rq, se);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);

        p = task_of(se);

idle:
        new_tasks = newidle_balance(rq, rf);

        /*
         * Because newidle_balance() releases (and re-acquires) rq->lock, it is
         * possible for any higher priority task to appear. In that case we
         * must re-start the pick_next_entity() loop.
         */
        if (new_tasks < 0)
                return RETRY_TASK;

        if (new_tasks > 0)
                goto again;

        /*
         * rq is about to be idle, check if we need to update the
         * lost_idle_time of clock_pelt
         */
        update_idle_rq_clock_pelt(rq);

        return NULL;
}
```
## 检查是否有任务
先用sched_fair_runnable检查是否有任务,如果没任务,调用 newidle_balance,此函数会`Attempts to pull tasks from other CPUs`尝试从其他cpu上拉一个任务来运行,所以有三种情况
* newidle_balance 返回负数,但是因为newidle_balance持有锁,持锁期间担心有高优先级任务出现,所以重试 if (unlikely(p == RETRY_TASK)) goto restart;
* newidle_balance 拉到任务了,跳转again
* newidle_balance 拉不到任务,让pelt计算rq->lost_idle_time

## 检查上一个任务不为cfs
`if (!prev || prev->sched_class != &fair_sched_class)`会判断没有prev或prev不是cfs,如果不是,那么走simple路径,simple路径为
* put_prev_task 将其放回本地队列
* 如果repick为1,则遍历所有se,调用set_next_entity重新选一个
* 否则逐步按组往下遍历,选择最优的se

## 如果上一个任务是cfs,且选中的任务不是prev
如果有prev,且prev是cfs中,那么任务走主路径,也叫做优化路径,其流程为
* 用pick_next_entity选中最优的se
* 用task_of拿到se的task_struct
* 如果获取的se和prev不是同一个进程
* put_prev_entity将其放回rb-tree
* 将当前se作为即将运行的se

## 如果选中的任务不是prev,且它们不在同一个组
如果它们不在一个组,那么走优化代码,最小化需要更新的层级数量,通过对于选中se的depth和prev的se的depth. 这里depth是从root开始到se所属的组的深度

举个例子
```
task_a: root-->group_a-->se_a
task_b: root-->se_a
```
那么 depth_a = 2,depth_b = 1,所以depth_a > depth_b

回到代码,两种情况
* 如果当前选中的se depth <= prev se depth,将prev放回rb-tree,然后找prev se的parent
* 如果当前选中的se depth >= prev se depth,将se放回rb-tree,然后找se的parent

可以看到,其思路是通过depth来逐步上移,直到他们depth相等,且,当depth相等的时候,se和prev se都上移一层,这样能够更新组调度下他们共属组的se
# 总结
本文介绍了pick_next_task的核心行为,如果从简单理解来看,就是单纯的找到rb-tree的最左节点,但是实际上,我们需要考虑调度组,需要考虑idle任务的场景,需要考虑遍历调度域的代码性能,需要考虑遍历组的代码性能,所以在pick_next_task中有上述的额外考虑代码.不过这些细节不用太过慌张

我们仍可以简单的认为pick_next_task找到了红黑树的最小实体.





调度(11)-CFS调度pick_next_task

在<调度(4)-CFS调度器和权重>介绍了CFS的核心点之一,weight.通过配置weight的数组,可以粗略的等比计算nice,而vruntime的实际步长就是通过weight来计算的.

同样的,在<调度(3)-调度器的设计>我们提到,cfs有大量的启发式计算,同样的,对于weight,为了维护cfs的公平性问题,会在enqueue/dequeue的时候,重新计算权重,也就是reweight,今天来简单了解一下cfs的reweight

# reweight的作用
reweight的作用是让sched_entity能根据本地负载动态调整权重，避免某个CPU过载而其他CPU空闲时出现不公平,其关键在于任务的enqueue和dequeue,如下
enqueue流程
```
enqueue_task_fair
  update_cfs_group
    calc_group_shares
    reweight_entity
```
dequeue流程
```
dequeue_task_fair
  update_cfs_group
    calc_group_shares
    reweight_entity
```
可以看到,这里的核心函数函数reweight_entity
# reweight_entity
```
static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                            unsigned long weight)
{
        if (se->on_rq) {
                /* commit outstanding execution time */
                if (cfs_rq->curr == se)
                        update_curr(cfs_rq);
                update_load_sub(&cfs_rq->load, se->load.weight);
        }
        dequeue_load_avg(cfs_rq, se);

        update_load_set(&se->load, weight);

#ifdef CONFIG_SMP
        do {
                u32 divider = get_pelt_divider(&se->avg);

                se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
        } while (0);
#endif

        enqueue_load_avg(cfs_rq, se);
        if (se->on_rq)
                update_load_add(&cfs_rq->load, se->load.weight);

}
```
简单分析一下其内容
* if (cfs_rq->curr == se) update_curr(cfs_rq); 如果就是当前se,则更新vruntime一次
* update_load_sub : 减去当前任务在cfs上的load
* dequeue_load_avg : 将当前se的load从cfs的load_avg中移除
* update_load_set: 设置新权重
* se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);: 用新的权重通过PELT重新计算负载
* enqueue_load_avg : 计算好了load_avg,入队
* update_load_add: 将其新的权重值加到当前总负载

# reweight_task
除了enqueue和dequeue,其他所有场景设置权重可以通过对外api,reweight_task完成,reweight_task是 reweight_entity 的封装,如下
```
void reweight_task(struct task_struct *p, const struct load_weight *lw)
{
        struct sched_entity *se = &p->se;
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        struct load_weight *load = &se->load;

        reweight_entity(cfs_rq, se, lw->weight);
        load->inv_weight = lw->inv_weight;
}
```
其流程如下
```
sched_fork # fork时 
set_user_nice # set nice时
__setscheduler_params # posix api时 
  set_load_weight
    scale_load
    reweight_task
```
# calc_group_shares
我们留意到update_cfs_group会调用calc_group_shares,它的作用是真正的计算权重的地方,值得注意的是,这里权重在计算的时候叫做shares,其代码如下
```
/*
 * All this does is approximate the hierarchical proportion which includes that
 * global sum we all love to hate.
 *
 * That is, the weight of a group entity, is the proportional share of the
 * group weight based on the group runqueue weights. That is:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (1)
 *                       \Sum grq->load.weight
 *
 * Now, because computing that sum is prohibitively expensive to compute (been
 * there, done that) we approximate it with this average stuff. The average
 * moves slower and therefore the approximation is cheaper and more stable.
 *
 * So instead of the above, we substitute:
 *
 *   grq->load.weight -> grq->avg.load_avg                         (2)
 *
 * which yields the following:
 *
 *                     tg->weight * grq->avg.load_avg
 *   ge->load.weight = ------------------------------              (3)
 *                             tg->load_avg
 *
 * Where: tg->load_avg ~= \Sum grq->avg.load_avg
 *
 * That is shares_avg, and it is right (given the approximation (2)).
 *
 * The problem with it is that because the average is slow -- it was designed
 * to be exactly that of course -- this leads to transients in boundary
 * conditions. In specific, the case where the group was idle and we start the
 * one task. It takes time for our CPU's grq->avg.load_avg to build up,
 * yielding bad latency etc..
 *
 * Now, in that special case (1) reduces to:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = ----------------------------- = tg->weight   (4)
 *                         grp->load.weight
 *
 * That is, the sum collapses because all other CPUs are idle; the UP scenario.
 *
 * So what we do is modify our approximation (3) to approach (4) in the (near)
 * UP case, like:
 *
 *   ge->load.weight =
 *
 *              tg->weight * grq->load.weight
 *     ---------------------------------------------------         (5)
 *     tg->load_avg - grq->avg.load_avg + grq->load.weight
 *
 * But because grq->load.weight can drop to 0, resulting in a divide by zero,
 * we need to use grq->avg.load_avg as its lower bound, which then gives:
 *
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (6)
 *                             tg_load_avg'
 *
 * Where:
 *
 *   tg_load_avg' = tg->load_avg - grq->avg.load_avg +
 *                  max(grq->load.weight, grq->avg.load_avg)
 *
 * And that is shares_weight and is icky. In the (near) UP case it approaches
 * (4) while in the normal case it approaches (3). It consistently
 * overestimates the ge->load.weight and therefore:
 *
 *   \Sum ge->load.weight >= tg->weight
 *
 * hence icky!
 */
static long calc_group_shares(struct cfs_rq *cfs_rq)
{
        long tg_weight, tg_shares, load, shares;
        struct task_group *tg = cfs_rq->tg;

        tg_shares = READ_ONCE(tg->shares);

        load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

        tg_weight = atomic_long_read(&tg->load_avg);

        /* Ensure tg_weight >= load */
        tg_weight -= cfs_rq->tg_load_avg_contrib;
        tg_weight += load;

        shares = (tg_shares * load);
        if (tg_weight)
                shares /= tg_weight;

        /*
         * MIN_SHARES has to be unscaled here to support per-CPU partitioning
         * of a group with small tg->shares value. It is a floor value which is
         * assigned as a minimum load.weight to the sched_entity representing
         * the group on a CPU.
         *
         * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
         * on an 8-core system with 8 tasks each runnable on one CPU shares has
         * to be 15*1024*1/8=1920 instead of scale_load(MIN_SHARES)=2*1024. In
         * case no task is runnable on a CPU MIN_SHARES=2 should be returned
         * instead of 0.
         */
        return clamp_t(long, shares, MIN_SHARES, tg_shares);
}
```
首先,我们知道task_group记录了组的本身权重shares,如下
```
struct task_group {
        unsigned long           shares;
}
```
按组分配的所有任务会按照比例分配这个shares值,举个例子
* 两个CPU,每个CPU有自己的se,分别是se0,se1
* CPU0上有两个任务,权重分别是1024,2048
* CPU1上有一个任务,权重是1024

那么se0上分配的比例是`(1024+2048)/((1024+2048)+1024)`,而se1上分配的比例是`1024/((1024+2048)+1024)`

![image.png](/static/img/75caa880452365c32c932c749d2488e0.image.webp)

对于代码,分析如下
* max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);  取当前瞬时权重和PELT的平均权重的较大的那个
* tg_weight -= cfs_rq->tg_load_avg_contrib; 将当前组的权重减去本CPU之前贡献的旧值
* tg_weight += load; 再加上上述的max值
* shares = (tg_shares * load); 总份额是share值乘以上述的max
* shares /= tg_weight; 然后除以计算后的权重

可以看到,这其实是一个这样的公式
```
load = max(grq->load.weight, grq->avg.load_avg)
tg_weight = tg->load_avg - grq->tg_load_avg_contrib + load;
shares = tg->shares * load / tg_weight 
```
整合一下
```
shares = tg->shares * max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
其实就是注释的最后公式

![image.png](/static/img/19337ad3721770e9550ff030e4ebbc72.image.webp)

## 回顾注释
### Step 1: 理想公式
```
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (1)
 *                       \Sum grq->load.weight
```
首先,我们分配一个实际任务的weight理论上是这个组的shares,也就是tg->shares,但是如果直接设置这个值,那么实际上并不公平.

为了维护公平性原则,我们为一个任务分配的weight应该将shares值按照实际负载来估计,所以理论想法是
```
weight = shares * (当前CPU负载 / 组内所有CPU负载)
```
这相当于维护了任务的局部公平性原则, 也就是按照当前真实负载比例来切分shares,而不是直接用shares
### Step 2: 平均负载替换瞬时负载
```
 *                     tg->weight * grq->avg.load_avg
 *   ge->load.weight = ------------------------------              (3)
 *                             tg->load_avg
```
但是计算组内所有的CPU负载的代价比较高,我们需要一定的启发式计算,方法是将PELT计算的平均负载来替代CPU负载,也就是如下
```
grq->load.weight -> grq->avg.load_avg
```
这样就不需要反复计算组内任务的CPU负载,而是直接从PELT中取平均负载,那么对于当前CPU的平均负载为grq->avg.load_avg,而组内所有CPU的平均负载是tg->load_avg

那么这次等效替换的计算公式变更为
```
weight = shares * (当前CPU平均负载 / 组内所有CPU平均负载)
```
这样近似计算在负载比较平稳的时候效果很好，且计算成本很低。
### Step 3: 取平均负载和瞬时负载最大值
```
 *              tg->weight * grq->load.weight
 *     ---------------------------------------------------         (5)
 *     tg->load_avg - grq->avg.load_avg + grq->load.weight
```
我们看看这个将瞬时负载到平均负载的等效计算带来的负面效果:假设当前CPU下比较空闲的时候,一个新的任务诞生,那么平均负载会变化的很慢,所以Step 2的公式近似为
```
weight = shares * (当前CPU平均负载(趋于0) / 组内所有CPU平均负载(较大值))
```
那么此时这个新的任务分到的weight远比预设的shares值小. 这是问题1

再假设另一种情况,当前CPU有负载,其他任务全部空闲,那么Step 2的公式近似为
```
weight = shares * (当前CPU平均负载(较大值) / 组内所有CPU平均负载(趋于0))
```
这种情况下,任务分到的weight又因为组内所有CPU平均负载趋于0,导致远远大于shares.这是问题2

为了解决上面问题,需要为公式计算一次当前CPU上的瞬时负载,然后拿这个瞬时负载和当前CPU的平均负载取较大值,也就是`max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);`我们把这个值记作当前CPU的负载:`cfs_rq->load.weight = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg)`

我们拿cfs_rq->load.weight作为分子,而总负载拿所有CPU平均负载减去当前CPU的平均负载,再加上cfs_rq->load.weight,此时公式为
```
weight = shares * ((当前CPU平均负载和瞬时负载的最大值) / (组内所有CPU平均负载 - 当前CPU平均负载 + 当前CPU瞬时负载))
```
到这里,计算一个任务的reweight的公式完成了.
# 总结
本文介绍了reweight的作用,其也是cfs为了维护局部公平性的一种手段,当任务入队出队以及其他场景中,都需要重新计算权重,而权重的公式是将预设的shares值,按照理论想法根据负载比例分配.

最后计算方式实际上是按照平均负载的方式计算,我们回顾此公式
```
shares = tg->shares * max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
这里稍微留意一下这个比例
```
max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
因为一个瞬态负载的值往往大于平均值,也就意味着这个比值是大于1的,也就是如下
```
shares = tg->shares * (>1)
```
也就是
```
shares > tg->shares
```
也就是一个任务reweight的时候,往往比预设的组的shares更大,在<调度(4)-CFS调度器和权重>的计算公式`vruntime += delta * nice0 / weight`,weight越大则vruntime变化越小,那么长期来看任务的reweight,它其实获得的时间片反而越多,但其响应越快

也就是说,虽然reweight为了局部的公平性设计了这个公式,但实际上仔细分析此公式也是存在不公平的,一个任务不断的reweight,那么其weight越大,weight越大,那么它的vruntime变化越小,vruntime预估变化小,那么其任务获得的时间片越多,也就导致了任务被偏心的分配了更多的时间来运行,加强了其响应能力,但是局部的不公平还是存在的.

举个生活的例子,生日了分蛋糕,作为家长,最初的愿望是想平分蛋糕,但是有些小孩是饿哭来要蛋糕的,有些小孩是后面才来要蛋糕的,此时分配的蛋糕默认给饿哭的孩子多分了一点,为了不让饿哭的小孩吃了还饿,主观性的多分了一点蛋糕,那么实际上对其他小孩而言是少了蛋糕, 但是其他小孩并不会因为少一点蛋糕而饿哭,虽然这种微小局部的不公平仍然存在,但是我们没必要追求这个颗粒度上的完全公平了.


因为"满足爱哭小孩有糖吃"定理更重要
