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;
    ...
};