Linux CFS调度算法-虚拟时间
CFS调度算法：摒弃固定时间片，采用进程权重值的比重来量化计算实际运行时间，并引入虚拟时间和真实时间的概念，真实时间就是在物理时钟下实际运行的时间，虚拟时间是实际运行时间与nice值为0对应的权值的比值。
虚拟时间片引入：假设进程不存在优先级区分，那么只要保证每个进程的实际运行时间相同即可，能做到绝对公平。调度时，调度器只需要记录每个进程的实际时间,每次调度时挑出【已经运行时间最短的进程】。
然而事实上每个进程会涉及不同的优先级，此时不同的进程应该由于优先级的原因导致【真实运行时间的所占权重】不同才行，那么如何评估进程运行时间的长短？如何选择下一个进程进行调度？
由此引入虚拟运行时间【希望不同的进程根据优先级在一个调度延迟【调度延迟就是保证每一个可运行进程都至少运行一次的时间间隔】内分配的物理时间通过一个公式计算得到一个相同的值，称这个值为虚拟时间】，当选择下一个进程执行的时候，找出虚拟时间最小的进程即可。虚拟时间要保证优先级高的进程的虚拟时间过得慢一些，优先级低的进程的虚拟时间快一些。
引入虚拟运行时间，CFS中就绪队列使用一棵以虚拟时间为键的红黑树将调度实体组织起来，利用红黑树的特性，虚拟时间最短的进程在红黑树的最左端，调度器每次选择位于红黑树最左端的虚拟时间对应的调度实体参与调度。
如下所示，通过cat/proc/$pid/sched查看某个进程调度信息，第二行se.vruntime就是虚拟运行时间：
由上面的展示也可以看出来调度相关的这些信息是存储在调度实体se中，【每个进程描述符中都有每种调度类对应的调度实体，调度实体存放与该调度类相关的调度信息，并参与调度，CFS调度器对应的调度实体为struct sched_entity se,例如实时调度器对应的调度实体为struct sched_rt_entity rt】，CFS调度器的调度实体如下：
struct sched_entity
{
struct load_weight load; /* for load-balancing负荷权重，这个决定了进程在CPU上的运行时间和被调度次数 */
struct rb_node run_node;
unsigned int on_rq; /* 是否在就绪队列上 */
u64 exec_start; /* 上次启动的时间*/
u64 sum_exec_runtime;
u64 vruntime; /* 虚拟运行时间*/
u64 prev_sum_exec_runtime;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
...
};虚拟运行时间的计算关于tick:tick是周期性的时钟中断，时钟中断驱动调度器runing，其周期间隔根据硬件频率的设定相关(T=1/f)，如下：
T=1/250 = 4ms，也就说时钟中断以4ms为周期【tips:每发生一次时钟中断，jiffies的数值就加上1】,每一个进程的虚拟时间在时钟中断里面被维护，每次时钟中断都要更新当前进程的虚拟时间。更新调用的主要函数如下：
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;
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cgroup_account_cputime(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}代码逻辑比较简单：1、确定就绪队列的当前执行的调度实体
/* 确定就绪队列的当前执行进程curr */
struct sched_entity *curr = cfs_rq->curr;2、根据获取的当前执行进程，计算当前和上一次更新负荷权重时两次的时间的差值
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;3、重新更新启动时间exec_start为now,以备下次计算时使用，最后将计算出的时间差加到先前的统计时间上。
/* 重新更新启动时间exec_start为now */
curr->exec_start = now;
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
/* 将时间差加到先前统计的时间即可 */
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq, exec_clock, delta_exec);这也是通过cat /proc/$pid/sched看到的一些统计信息 4、开始计算虚拟时间
curr->vruntime += calc_delta_fair(delta_exec, curr);
5、计算虚拟时间函数calc_delta_fair如下，忽略舍入和溢出检查，calc_delta_fair函数所做的计算如下：
/*
* delta /= w
*/
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}
# define SCHED_FIXEDPOINT_SHIFT 10
#define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT)
#define NICE_0_LOAD (1L << NICE_0_LOAD_SHIFT)1024也就是Nice值为0对应的权重值，权重值在内核中是预先定义好的，如下所示:
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};通过公式和内核预先设定的权重表，可以看出来:
Nice值越高(对应的优先级越低)，权重越小，虚拟时间累加的越快(虚拟时间过得越快)，Nice值越低(对应的优先级越高)，权值越高，虚拟时间累加的越慢(虚拟时间过得越慢)。CFS的思想核心也就是这样，让每个调度实体的虚拟时间增加速度不同，使用虚拟时间来衡量调度实体在CPU上已经执行的时间。
总结： 不同优先级的进程以各自对应的速度推进虚拟时间，只要保证在一个调度延迟内虚拟时间的推进进展相同，就实现了完成公平，公平指的是相对公平，即按进程的权重给予不同的运行时间，虚拟时间越小，代表着受到了"不公平"对待，因此下一个参与调度的调度实体就是红黑树中的最左边(虚拟时间最小)的节点，如此一来既能公平选择进程，又能保证高权重进程获得较多的运行时间。关于虚拟时间还有很多其他关键点，如新加入的进程的虚拟时间如何设定、长时间阻塞或者睡眠的进程被唤醒时虚拟时间如何设定等等，将在以后的文章分析。
参考：
1 、http://www.wowotech.net/process_management/452.html
2 、https://cloud.tencent.com/developer/article/1371674?from=15425