现在基于EEVDF的社区patch进行逐一解析，尽可能抓住重点来介绍eevdf

# [PATCH 01/15] 
添加两个参数avg_vruntime 和 avg_load
```
@@ -554,6 +554,9 @@ struct cfs_rq {
 	unsigned int		idle_nr_running;   /* SCHED_IDLE */
 	unsigned int		idle_h_nr_running; /* SCHED_IDLE */
 
+	s64			avg_vruntime;
+	u64			avg_load;
+
 	u64			exec_clock;
 	u64			min_vruntime;
```
核心说明
```
/*
 * Compute virtual time from the per-task service numbers:
 *
 * Fair schedulers conserve lag:
 *
+ *   \Sum lag_i = 0
 *
 * Where lag_i is given by:
 *
 *   lag_i = S - s_i = w_i * (V - v_i)
 *
 * Where S is the ideal service time and V is it's virtual time counterpart.
 */
```
这个注释很容易理解，上篇论文提过，lag为S-s，因为引入了V，所以是w * (v-vi)，然后我们要满足sum(lag)=0，所以可以转换公式如下
```
 /* Therefore:
 *
 *   \Sum lag_i = 0
 *   \Sum w_i * (V - v_i) = 0
 *   \Sum w_i * V - w_i * v_i = 0
 *
 * From which we can solve an expression for V in v_i (which we have in
 * se->vruntime):
 *
 *       \Sum v_i * w_i   \Sum v_i * w_i
 *   V = -------------- = --------------
 *          \Sum w_i            W
 *
 * Specifically, this is the weighted average of all entity virtual runtimes.
 */
```
因为sum(lag)=0，所以得到v的公式是
$$
V = \frac{\sum_i w_i * v_i}{\sum_i w_i} = \frac{\sum_i w_i * v_i}{W}
$$
```
 /*
  * [[ NOTE: this is only equal to the ideal scheduler under the condition
  *          that join/leave operations happen at lag_i = 0, otherwise the
  *          virtual time has non-continguous motion equivalent to:
  *
  *	      V +-= lag_i / W
  *
  *	    Also see the comment in place_entity() that deals with this. ]]
  *
  * However, since v_i is u64, and the multiplcation could easily overflow
  * transform it into a relative form that uses smaller quantities:
  *
  * Substitute: v_i == (v_i - v0) + v0
  *
  *     \Sum ((v_i - v0) + v0) * w_i   \Sum (v_i - v0) * w_i
  * V = ---------------------------- = --------------------- + v0
  *                  W                            W
  *
  * Which we track using:
  *
  *                    v0 := cfs_rq->min_vruntime
  * \Sum (v_i - v0) * w_i := cfs_rq->avg_vruntime
  *              \Sum w_i := cfs_rq->avg_load
  *
  * Since min_vruntime is a monotonic increasing variable that closely tracks
  * the per-task service, these deltas: (v_i - v), will be in the order of the
  * maximal (virtual) lag induced in the system due to quantisation.
  *
  * Also, we use scale_load_down() to reduce the size.
  *
  * As measured, the max (key * weight) value was ~44 bits for a kernel build.
  */
```
为了避免u64的overflow，所以引用一个替代`v_i == (v_i - v0) + v0`，代入原公式如下
$$
V = \frac{\sum_i w_i * v_i}{W} = \frac{\sum_i w_i * (v_i - v0) + \sum_i w_i * v0}{W} = \frac{\sum_i w_i * (v_i - v0)}{W} + v0
$$
这里将公式对接到代码上
```
 v0                  = cfs_rq->min_vruntime
 sum(v_i - v0) * w_i = cfs_rq->avg_vruntime
 sum(w_i)            = cfs_rq->avg_load
```
对于`v_i - v0`的函数如下
```
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return (s64)(se->vruntime - cfs_rq->min_vruntime);
}
```
那么`cfs_rq->avg_vruntime`和`cfs_rq->avg_load`的计算函数就是
```
static void
avg_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	unsigned long weight = scale_load_down(se->load.weight);
	s64 key = entity_key(cfs_rq, se);

	cfs_rq->avg_vruntime += key * weight;
	cfs_rq->avg_load += weight;
}

static void
avg_vruntime_sub(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	unsigned long weight = scale_load_down(se->load.weight);
	s64 key = entity_key(cfs_rq, se);

	cfs_rq->avg_vruntime -= key * weight;
	cfs_rq->avg_load -= weight;
}
```
随着时间的推移，min_vruntime会不断更新，所以函数如下
```
static u64 __update_min_vruntime(struct cfs_rq *cfs_rq, u64 vruntime)
{
	u64 min_vruntime = cfs_rq->min_vruntime;
	/*
	 * open coded max_vruntime() to allow updating avg_vruntime
	 */
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta > 0) {
		avg_vruntime_update(cfs_rq, delta);
		min_vruntime = vruntime;
	}
	return min_vruntime;
}
```
同样的avg_vruntime 也会随着时间更新，所以函数如下
```
static inline
void avg_vruntime_update(struct cfs_rq *cfs_rq, s64 delta)
{
	/*
	 * v' = v + d ==> avg_vruntime' = avg_runtime - d*avg_load
	 */
	cfs_rq->avg_vruntime -= cfs_rq->avg_load * delta;
}
```
还记得计算V的公式吗，如下
$$
V = \frac{\sum_i w_i * (v_i - v0)}{W} + v0 = 
$$
其实就是
```
V = cfs_rq->avg_vruntime / cfs_rq->avg_load + cfs_rq->min_vruntime
```
所以对于V的函数实现如下
```
u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	s64 avg = cfs_rq->avg_vruntime;
	long load = cfs_rq->avg_load;

	if (curr && curr->on_rq) {
		unsigned long weight = scale_load_down(curr->load.weight);

		avg += entity_key(cfs_rq, curr) * weight;
		load += weight;
	}

	if (load)
		avg = div_s64(avg, load);

	return cfs_rq->min_vruntime + avg;
}
```
和之前的CFS的计算vruntime一致，我们要在enqueue和dequeue的时候主动update_curr，这里直接调用add/sub来更新V，如下
```
@@ -642,12 +767,14 @@ static inline bool __entity_less(struct
  */
 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	avg_vruntime_add(cfs_rq, se);
 	rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
+	avg_vruntime_sub(cfs_rq, se);
 }
 
 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
@@ -3379,6 +3506,8 @@ static void reweight_entity(struct cfs_r
 		/* commit outstanding execution time */
 		if (cfs_rq->curr == se)
 			update_curr(cfs_rq);
+		else
+			avg_vruntime_sub(cfs_rq, se);
 		update_load_sub(&cfs_rq->load, se->load.weight);
 	}
 	dequeue_load_avg(cfs_rq, se);
@@ -3394,9 +3523,11 @@ static void reweight_entity(struct cfs_r
 #endif
 
 	enqueue_load_avg(cfs_rq, se);
-	if (se->on_rq)
+	if (se->on_rq) {
 		update_load_add(&cfs_rq->load, se->load.weight);
-
+		if (cfs_rq->curr != se)
+			avg_vruntime_add(cfs_rq, se);
+	}
 }

```
# 总结
这里介绍了eevdf的第一个patch，其作用是添加了avg_vruntime和avg_load，并结合论文提供了v的计算函数

# 参考
> https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/
> https://lore.kernel.org/lkml/20230531124603.654144274@infradead.org/

调度(17)-EEVDF补丁解析1

这篇论文是 EEVDF 算法的理论基石，Linux 6.6+ 内核的 EEVDF 实现基本就是基于它来的。
本文根据论文描述的内容进行介绍

# EEVDF的提出
现代操作系统的调度器类型分为两类
* 比例份额
* 实时调度

很明显，这种归类下，可以得出如下结论
1. 步幅调度，CFS调度这类，属于比例份额，它要做到的事公平的让程序分配到应有的份额
2. FIFO，EDF这类，属于实时调度，这类调度器基于事件驱动模型，例如EDF通过截止事件来决定任务的优先级

```
In this paper we propose a new scheduler (called Earliest Eligible Virtual Deadline First (EEVDF)which, while retaining all the advantages of the proportional share schedulers, provides strong timeliness guarantees for the service time received by a client. In this way, our algorithm provides a unied approach for scheduling continuous media, interactive and batch applications.
```

而EEVDF要解决的问题是保留了比例份额的优势的前提上，融合实时调度通过截止时间来保证及时性。这样的情况下，调度器在多媒体和交互式以及批处理三类型的任务上都能够统一的使用一种调度策略满足其需求

# 服务滞后
我们按照比例份额来计算一个任务的应有份额，那么其计算应该如下

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

很好理解，就是自身权重占总权重的比值

但实际调度的过程中，我们不可能简单的任务一个任务的应该开始运行时间和实际开始运行时间一致，那么我们把这两个值相减，提供一个新的概念叫做lag。

![image.png](/static/img/8812388516f9b471d8bd2bc22603114e.image.webp)

这里Si就是理论认为的运行时间，而si是实际获得的运行时间，将`Si-si`就是我们称作的lag。

在上一文中我们介绍了一个linux很好的通俗化含义，就是欠条。那么这个lag就很好理解了。

我调度器按照比例分给你任务，但是等你真的运行的时候，肯定存在滞后，那么这个滞后时间是你欠我的，我要找你要回来。

# EEVDF Algorithm
虚拟时间的定义

![image.png](/static/img/7f1f6e800a84755ba1e69d00bdb87b55.image.webp)

直观的看

* 当竞争激烈（总权重很大）时，虚拟时间走得慢。
* 当竞争减少（总权重变小）时，虚拟时间走得快。

如果虚拟时间的概念引入了，那么我们计算`Si-si`就可以简单的认为是两个时间点的虚拟时间相减乘以权重

![image.png](/static/img/2b4440c58611974cc7743ff039e26dc6.image.webp)

现在为了计算虚拟时间，再关联两个新的时间
* Ve： virtual eligible time，合格时间，所谓合格，就是应获得的时间等于其在发出请求前已获得的服务时间。我们称作合格，那么合格时间就是，不合格时间到合格时间的这个差值。如果lag是负数，那么它已经不合格了，我们等到它再次合格的时间，就是Ve
* Vd： virtual deadline， 截止时间，这个不用解释了

我们看Ve的计算

![image.png](/static/img/697e9239c9a37e34d4d4350fbf5e2cc5.image.webp)

就是 `T0的虚拟数据V + 实际运行实际si / 权重`

这里我们看si的值，如果si已经开始运行了，那么Ve是合格的，这是没问题的   
如果si是负数，那么Ve是不合格的，我们得让Vt继续推进，使得Ve合格

再看Vd的计算

![image.png](/static/img/80536205884e6a391354889a0fffbc89.image.webp)

就是 `合格时间Ve + 申请的runtime / 权重`

# 示例

![image.png](/static/img/06945ff95bce583c0d71396d958542da.image.webp)

这里假设有两个client，他们的权重都是2，对于的r分别是r1=2，r2=1，时间的粒度是1。那么分析如下
* t=0： 只有client1，Ve1=0，Vd1=Ve+r1/w1=0+2/2=1
* t=1： V1=1/2=0.5
* t=1： Ve2=V1=0.5，Vd2=Ve2+1/2=1，此时我们看到Vd1和Vd2都是1，下一次其实可以任意挑选client1和client2
* t=2： client2的Ve2=Vd1=1，Vd2=Ve2+1/2=1.5，此时Ve2是1，但是V1是0.5，优先级降低，让client1运行
* t=3： client1完成，Ve1=Vd1=1，Vd1=Ve1+2/2=2，由于client 2 的dl比client1要早，1.5<2，所以运行clietn2

以此类推

# 公平性分析
在实际场景中，公平性在EEVDF是通过lag来衡量vt的计算，如下

![image.png](/static/img/20dac4065d1447a75f63a976e7937e12.image.webp)

假设三个client在t0没有lag，此时client3在t时刻离开，那么计算lag的方法为

$$
lag_i(t) = S_i(t_0,t) - s_i(t_0, t) \\
  = \int_{t_0}^{t_1}f_i(\tau)d\tau - s_i(t_0, t) \\
  = w_i \frac{t - t_0}{w_1 + w_2 + w_3} - s_i(t_0, t) -- (1)
$$

eevdf设计没有所谓的resource idle，则在t0时间中，client1和client2获得的时间为
$$
t - t_0 - s_3(t_0, t)
$$
那么对于client1和client2，其计算为
$$
S_i(t_0, t^+) = (t - t_0 - s_3(t_0, t)) \frac{w_i}{w_1 + w_2} -- (2)
$$
根据前面的公式代入
$$
lag_3(t) = w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - s_3(t_0, t) \\
s_3(t_0, t) =  w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t) -- (3)
$$
再将3代入2
$$
S_i(t_0, t^+) = (t - t_0 - ( w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t))) \frac{w_i}{w_1 + w_2} \\
= (t - t_0 + \frac{-w_3t + w_3 t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{w_1 + w_2t - w_1t_0 - w_2t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{(w_1 + w_2)(t - t_0)}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{(t - t_0)}{w_1 + w_2 + w_3}) * w_i + w_i\frac{lag_3(t)}{w1 + w2} \\
= w_i(V(t) - V(t_0)) + w_i\frac{lag_3(t)}{w1 + w2}
$$
我们可以看到client3离开时，client1和2分摊了client3的lag

所以当一个client离开，那么其Vt的计算为

$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (4)
$$

同理，当一个client加入，其Vt计算为

$$
V(t) = V(t) - \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (5)
$$

那么reweight的时候，其Vt计算为

$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i - w_j}  + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i + w_j^{'}} -- (6)
$$

所以我们可以认为EEVDF是work-conserving最优的

# 总结
本论文是eevdf的开篇基石，里面详细论证了EEVDF的优势，了解这个论文的熟悉linux eevdf来说至关重要。为了理解这个论文，我重新啃了一些里面的公式，计算过程在上文中。


# 参考
> https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564



调度(16)-EEVDF论文

EEVDF（Earliest Eligible Virtual Deadline First）为了解决上文中CFS的无法低延时的痛点而诞生的。它在保持 CFS 公平性的基础上，引入了“虚拟截止期限”和“lag”概念，让调度器既能公平分配资源，又能显著降低延迟。
本文就来详细拆解 EEVDF 的核心思路，以及它如何通过 latency-nice 值优雅平衡吞吐与响应。

# Lag
所谓lag，我们可以简单理解为欠条，谁欠得最多（lag 正值最大）谁最先玩

假设 5 个进程共享一个 CPU，nice 值相同。
理想情况下，每秒每个进程应该得到 200ms CPU 时间。  但实际运行中，由于中断、抢占、迁移等原因，每个进程得到的真实时间会有偏差。
EEVDF 把这个偏差定义为 lag：
```
lag = 理想时间 - 实际获得时间
```
1. lag > 0：进程“欠债”了，得到的 CPU 时间比应得的少 → 应该优先调度  
2. lag < 0：进程“超支”了，得到的 CPU 时间比应得的多 → 应该降低优先级  
3. lag = 0：正好公平

只有 lag ≥ 0 的进程才“eligible”（有资格被调度）。
lag < 0 的进程要等到时间继续前进、它的“应得时间”赶上“已得时间”后，才重新 eligible。这段时间差叫 eligible time。简单来说：EEVDF 通过 lag 实时追踪每个进程的“公平欠账”，让“欠得最多”的进程最先上场。

# Virtual deadline
这个很好理解，EDF调度通过实际deadline来判断截止时间，EEVDF通过虚拟截止时间来判断，EEVDF挑选 virtual deadline 最早的进程。

virtual deadline 的计算公式：
```
virtual deadline = eligible time + time slice
```
* eligible time：进程从不 eligible 到重新 eligible 所需的时间（基于 lag 追赶）
* time slice：本次分配的时间片（类似 CFS 的 sched_slice）  

这里time slice的关键在于latency-nice的影响，主要如下：
1. latency-nice 低（延迟敏感）：time slice 短 → virtual deadline 早 → 优先级高  
2. latency-nice 高（延迟不敏感）：time slice 长 → virtual deadline 晚 → 优先级低

如下图

![image.png](/static/img/597bb8640056d3e3fbefbad7401dd035.image.webp)

两个程序A和B，我们留意到A是属于latency-nice 低，time slice 短的程序，B就是latency-nice 高，time slice 长的程序，他们调度的特性就是，让延迟敏感的程序优先运行，但是切的更短。而实际上，A和B的运行时间是一致的。

这种将延迟敏感任务分成很多小片段，频繁调度的办法，换来的低延迟，而对延迟不敏感的任务，分成长片段，换来的是高吞吐，所以这完美解决了 CFS 的痛点：nice 值只管“总量”，latency-nice 可以管“响应速度”。

回到virtual deadline 的概念，我们如果latency-nice 低，那么virtual deadline低，这样也就越低延迟

在EEVDF中，可以通过sched_runtime设置一个自定义的time slice，这样用户的可操作性更强。但是需要注意关键点
* time slice小，抢占多，低延迟
* time slice大，吞吐高，延迟高

如果设置这个值，其范围是
```
0.1ms - 100ms
```
当然，如果不设置这个值，就是内核默认的经验值，和cfs的sysctl_sched_min_granularity一致，为sysctl_sched_base_slice。

其默认值为
* 0.70 msec * (1 + ilog(ncpus))

```
unsigned int sysctl_sched_base_slice            = 700000ULL;
/*
 * Increase the granularity value when there are more CPUs,
 * because with more CPUs the 'effective latency' as visible
 * to users decreases. But the relationship is not linear,
 * so pick a second-best guess by going with the log2 of the
 * number of CPUs.
 *
 * This idea comes from the SD scheduler of Con Kolivas:
 */
static unsigned int get_update_sysctl_factor(void)
{
    unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
    unsigned int factor;

    switch (sysctl_sched_tunable_scaling) {
    case SCHED_TUNABLESCALING_NONE:
        factor = 1;
        break;
    case SCHED_TUNABLESCALING_LINEAR:
        factor = cpus;
        break;
    case SCHED_TUNABLESCALING_LOG:
    default:
        factor = 1 + ilog2(cpus);
        break;
    }

    return factor;
}

static void update_sysctl(void)
{
    unsigned int factor = get_update_sysctl_factor();

#define SET_SYSCTL(name) \
    (sysctl_##name = (factor) * normalized_sysctl_##name)
    SET_SYSCTL(sched_base_slice);
#undef SET_SYSCTL
}
```
假设系统有 8 个核，那么 `factor=4`，最终的 `base_slice` 就为 `0.70ms * 4 = 2.8ms`

# 调度周期
* 在 EEVDF 的情况下，调度周期 P 的计算方法如下：
  * `W` 是所有任务的权重累计
  * s_i 是任务 `i` 的时间片（slice）
  * w_i 是任务 `i` 的权重（weight）
```
P_max = W * max(s_i / w_i)
```

* 对于某个特定任务 `i` 的平均周期 P<sub>i</sub> 是：

```
P_i = W * (s_i / w_i)
```

* 由此可见，整个 EEVDF 的调度周期，也是所有任务中平均调度周期最大的那个任务的平均调度周期。
* 每个任务公平地获得调度周期中的如下时间：

```
S_i = P * (w_i / W)
```
# 总结
CFS为了公平去实现公平，最终陷入了公平，而EEVDF为了延迟去实现低延迟，目前来看，其是EDF的Linux推广版，我们可以从解决问题的角度思考为何如此演进。

一个任务在OS上调度，你究竟要的是公平，还是要的是更低延迟的运行。

公平是一个虚幻的概念，而低延迟是目标体验。所以linux从CFS转移到EEVDF也就意味着，调度应该为了解决实际问题为根本点考虑，而不是为了理论公平，理论响应度最高来考虑设计。

当然，EEVDF可能因为低时延牺牲一定的高响应，最终取舍还是看实际OS产品落地的程序员














调度(15)-EEVDF简介

在之前的系列文章中，我们反复提到 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中通过内置预先计算好的表来屏蔽复杂运算的耗时，而计算的过程中，通过一定的数据近似尽可能的获得了累加和和旧值衰减的较准确值。

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








