eevdf 内核调度器 源码分析 （1）
简介
本文会从源码角度，简单分析eevdf（Earliest Eligible Virtual Deadline First）内核调度器。阅读本文需要一定cfs调度器的基础知识。
vruntime的变化
在cfs中，有一个虚拟运行时间的概念 vruntime, 参考函数calc_delta_fair。和真实时间相比，可以大体看作 虚拟运行时间 = 真实运行时间/权重（实际情况会复杂一些）。cfs调度器会尽量让每个调度实体虚拟时间运行时间相同，而因为每一个调度实体的权重不同，所以权重大的调度实体，分得的真实时间更多。
eevdf这个函数并没有变化。记一个任务i, 虚拟运行时间v_i, 权重为w_i, 真实运行时间s_i, 则关系为：
v_i = s_i / w_i
eevdf相比基础的cfs，又多了一个 system virtual time的概念，为：
（不会打公式，而且懒得学）
看着出现了积分，但是逻辑很简单，相当于系统所有任务的，虚拟运行时间。
真实时间在上面公式上走过了t, 但是为了好看统一一下记为s, 假设在这段时间内，没有任何的任务停止或者加入，那么下面的那个权重w_i 加和，可以记为W，W = \Sum w_i，W是系统在这段时间内，所有任务的权重之和，那么这个V就能得到：
V=s/W
对比上面的v_i = s_i / w_i， 可以看到这个V,相当于一个总任务的虚拟运行时间。
当然，系统中的任务是不停加入或停止的，所以正规的需要用积分表示，当然如果只是简单理解，用V=s/W就可以了。
那么这个V有什么用呢，这是在真实时间轴的基础上，增添了一个虚拟时间轴，虚拟时间轴的快慢与系统负载有关。通过这个虚拟时间轴，运行时间的判断就全部来到了虚拟时间上，这也是eevdf的基础。
s是真实时间，可以写作\Sum s_i * w_i, 即这段时间每一个任务经历的真实时间（仍然假设不会有任务停止开始，这样会容易理解很多，下文不再提起）
那么公式可以变为
\Sum v_i * w_i
V = --------------
W
不过 v_i * w_i 是可能溢出的，所以需要剪去一个偏移，公式为
\Sum ((v_i - v0) + v0) * w_i \Sum (v_i - v0) * w_i
V = ---------------------------- = --------------------- + v0
W W
最终这个V的计算，体现在代码中，将其分成三部分来进行计算：
v0 := cfs_rq->min_vruntime
\Sum (v_i - v0) * w_i := cfs_rq->avg_vruntime
\Sum w_i := cfs_rq->avg_load
而将这三处统一起来的函数，为avg_vruntime
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) {
/* sign flips effective floor / ceil */
if (avg < 0)
avg -= (load - 1);
avg = div_s64(avg, load);
}
return cfs_rq->min_vruntime + avg;
}
可以看出，avg_vruntime基本就是上述公式的一个计算。
到底什么是Eligible？
Eligible翻译为有资格的，合格的。eevdf每次选择，都会在合格的任务中选取有最早deadline的任务，所以合格，就是一个必要不充分条件，那么到底什么任务是合格任务呢？大体可以总结为，在某个时间点，这个任务还没有把上次分配给它的时间用完，就为合格任务。
判断一个任务是否合格的核心任务是entity_eligible，这个函数在选择下一个运行调度实体时被频繁使用。
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return (s64)(se->vruntime - cfs_rq->min_vruntime);
}
static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
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;
}
return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
}
int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return vruntime_eligible(cfs_rq, se->vruntime);
}
entity_eligible 判断逻辑很简单，但是想要读明白必须再了解几个eevdf的核心概念。
首先需要介绍lag这个概念，对于一个任务i,
lag_i = S_i - s_i
其中
S_i = w_i * V
w_i * V 是什么意思？在上面中，我们知道，
V = s/W
所以
S_i = w_i * s / W
其实也就是，各个进程通过权重，将真实时间s分割了，比如两个权重为3和7的进程，经过10s后，这时虚拟时间才过去1s，理论上权重为3的应该给他3秒钟，权重为7的理论给他7s。所以，S_i 是这个进程的应得时间。
考虑到一些进程可能停止或开始，一段时间的S，正规表示为
S_i(t1; t2) = w_i * (V_t2 - V_t1)
而lag_i 则是进程的应得时间剪去实际运行时间。
如果lag_i 大于0，说明进程比较“委屈”，本来要给他更多的时间，但是因为一些情况进程没有使用到，而lag_i 小于0 ，则说明进程较为“讨人厌”，贪婪的占用了更多时间的cpu。
那么什么是eligible？说穿了，就是lag 大于等于0。也就是这个进程的应得时间还没有使用完，可以继续被调度, 有了这个理论后，entity_eligible这个函数的逻辑就可以被推导出来了。
lag_i = S_i - s_i = w_i*(V - v_i)
--> V >= v_i
\Sum (v_i - v0) * w_i
--> --------------------- + v0 >= v_i
W
--> \Sum (v_i - v0)*w_i >= (v_i - v0)*(\Sum w_i)
同时，内核中记录lag的部分如下
static s64 entity_lag(u64 avruntime, struct sched_entity *se)
{
s64 vlag, limit;
vlag = avruntime - se->vruntime;
limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
return clamp(vlag, -limit, limit);
}
static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
SCHED_WARN_ON(!se->on_rq);
se->vlag = entity_lag(avg_vruntime(cfs_rq), se);
}
看出来，内核中记录的是vlag而不是lag，类似于vruntime，其实就是lag 除权重，
lag_i = S_i - s_i = w_i*(V - v_i)
vlag_i = V - v_i
eligible time 和 deadline time
一个任务是否是eligible，上面已经推导清了，但是eligible time又是什么。
这里有一个正经的定义
t^i_0 代表着这个任务active的时间， t代表着任务又请求一次新的时间。
t^i_0 可以理解为开始时间，在这之前状态就认为一切刚开始。那么t如何理解呢？这里和普通的cfs可能有些歧义。在一些调度中，是任务自己请求运行资源的，某个任务到时间t时，可能会再请求运行1s这样。当然，放到内核调度器中，这个是内核tick代劳的。每个tick到来，内核会为每个任务请求新的运行时间。
所以，这个公式可以翻译为，一个任务刚从时间t^i_0开始运行后，经历的第一个tick，此时时间为t, 那么 任务在这个时间段内，真实的运行时间，
相当于 t^i_0 到 e这段的真实时间。
把S_i(t1; t2) = w_i * (V_t2 - V_t1)带入，则可以得到
如果e < t，毫无疑问 S_i(t^i_0 , e ) < S_i(t^i_0 , t ), 也就是当时间t时，应当获取的运行时间会更多，这个任务时则也就更“客气”，该用的时间没有用，自然可以让其继续运行。
如果e > t， 当时间t时，发现这个任务较为“贪婪”，提前预支了自己资源，就不会给它调度。那么什么时候会给他调度呢，那就需要等到时间e了，因为到时间e, 任务就平衡了。
那么deadline time又是什么呢，定义为
S_i (e ,d) = r
这个公式可以转为
这个公式又是什么意思？首先 e 是合规时间，在这个时间节点，等到下次请求时间产生时，已经可以申请新的时间了。
r是申请的时间，事实上，在内核中这个时间是一个固定值。
deadline time的含义为，在e 到 d的这个时间点，应当把这个申请的r完成（当然，至于实际完不完的成，是另一回事了）。
为什么是从e开始？
参考上面，如果e<t ,进程在t时已经是“委屈”了，所以我们需要补偿它，就让他deadline提前一会，如果还是通过 t + t/w_i ,对于这个进程就不公平了，e> t同理。
所以，有了下面这三个公式，这也是eevdf的核心，即任务总是在deadline time前，将申请的r用完（即deadline定义保证到deadline时应得时间r，同时ve k 到ve k+1 应得正好使用了r），然后进入下一个e 。
那么内核中，面对复杂的真实情况，尤其是怎么保证在ve(k+1)时用完r， 是怎么实现的呢, 首先看核心函数 update_curr，这里只截取核心部分。
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_deadline(cfs_rq, curr);
update_min_vruntime(cfs_rq);
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
首先是计算 sum_exec_runtime 和 vruntime，这一部分和普通的cfs没有太大区别。
update_deadline 这里就不同了
static void update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
if ((s64)(se->vruntime - se->deadline) < 0)
return;
/*
* For EEVDF the virtual time slope is determined by w_i (iow.
* nice) while the request time r_i is determined by
* sysctl_sched_base_slice.
*/
se->slice = sysctl_sched_base_slice;
/*
* EEVDF: vd_i = ve_i + r_i / w_i
*/
se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
/*
* The task has consumed its request, reschedule.
*/
if (cfs_rq->nr_running > 1) {
resched_curr(rq_of(cfs_rq));
clear_buddies(cfs_rq, se);
}
}
首先判断，如果 se->vruntime 小于 se->deadline 直接就返回，因为这次deadline 还没结束，用不到更新下一次deadline 。
然后就是一个固定的 sysctl_sched_base_slice，这个值以后再详细分析。
然后就看到了，deadline的更新。
se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
对应到公式，vd_i = ve_i + r_i / w_i， 其他都好理解，为什么ve_i 会是 se->vruntime呢。
这里有一个隐含信息，那就是se->vruntime 已经大于等于 se->deadline了。并且我们有
所以se->vruntime 是大于等于ve k+1的，同时，vruntime的更新是很频繁的，我们就假设其是实时更新的，当大于deadline的一瞬，就认为是下一个ve了。
vruntime记录着任务的虚拟运行时间，当大于deadline的时候，说明正好增加了r/w（可能稍微大一点），也就是任务真实运行了r ，而应得运行时间，正也是r ，在这个时间节点，系统认为这个任务使用r这个申请时间是合理的，没问题的。
对于一个调度实体而言，se的vruntime记录着se的虚拟运行时间，deadline记录着截止时间，vruntime更新频繁，每当达到deadline，就让deadline再加 r/w ，对应vruntime可以再运行r/w虚拟时间。每当两者一对应，就再往后走。
所以内核在实现eevdf时，ve这个概念隐含在vruntime中了。
再看下一个函数 update_min_vruntime。之前说过在计算V时，为了防止溢出，会减去一个v0，不过v0用处不止于此，进程创建睡眠唤醒都是需要的。
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;
}
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;
}
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = __pick_root_entity(cfs_rq);
struct sched_entity *curr = cfs_rq->curr;
u64 vruntime = cfs_rq->min_vruntime;
if (curr) {
if (curr->on_rq)
vruntime = curr->vruntime;
else
curr = NULL;
}
if (se) {
if (!curr)
vruntime = se->min_vruntime;
else
vruntime = min_vruntime(vruntime, se->min_vruntime);
}
/* ensure we never gain time by being placed backwards. */
u64_u32_store(cfs_rq->min_vruntime,
__update_min_vruntime(cfs_rq, vruntime));
}
对比之前的cfs代码，有两处不同，1是不找left节点，因为在eevdf中，最左节点是最近deadline，而不是最小vruntime，2是，找完后，会对avg_vruntime进行更新，原因可以再看V的实现公式，v0变化了，自然也需要变化一下。
结语
本文简要介绍了eevdf的一些基础概念，公式推导，代码实现，不涉及进程睡眠唤醒等逻辑，后文会对进程睡眠等逻辑进行讲解。
标签：curr,rq,源码,内核,vruntime,eevdf,avg,cfs,se From： https://blog.csdn.net/father_yingying/article/details/143855768