LKD（Linux内核设计与实现） Chapter 4 Process Scheduling

一个理想化的多任务CPU能够同时执行所有任务，每个任务依据优先级权重分得应得的计算资源。但这样的CPU是不存在的，只能通过某种手段模拟。为此，CFS调度器设计了一个参数叫Virtual Runtime（简称vruntime）来记录当前任务所获得的运行时间。背后的道理是，相同优先级的任务所获得vruntime应该相同，某个任务获得少了，说明该任务受到不公平对待，应给其更多调度机会。

数据结构

CFS相关的数据结构主要定义在kernel/sched/sched.h 。

单个任务的的时间统计是放在struct task_struct/struct sched_entity下：

所有可以运行的任务以vruntime为键值按小到大排序构成一个timeline。Timeline使用一个红黑树来组织，树最左边的节点为vruntime最小的任务。红黑树的根节点以及最左节点都放在CFS的runqueue结构体struct cfs_rq中：

虚拟时钟

vruntime的更新是通过update_curr函数（定义在kernel/sched/fair.c）。update_curr计算当前任务获得的执行时间，累计其vruntime。此外，update_curr还做了一个动作：执行更新min_vruntime。

min_vruntime定义在struct cfs_rq中，这是个只增不减的值，主要作用是为新进任务的vruntime提供一个参照。如果直接把新进任务的vruntime设为0，会与现有的vruntime产生较大差距，导致调度器分配过多资源给新进任务。合适的做法是给新进任务设置一个足够小的vruntime，让其能够较快被调度。但初始调度之后，就能进入常态，和其他任务一样根据公平性来调度。所以min_vruntime是用来正常化（normalize）vruntime的。

Nice权重

vruntime之所以和任务获得的真实执行时间不一样，是因为它是以Nice值为权重加权计算出来的值。累计vruntime的时候需除以权重再累加。Nice值高的任务，权重低，vruntime就累计得快；nice值低的任务，权重高，vruntime累计得慢。所以Nice值低的任务就能获得更多真实执行时间。

update_curr调用calc_delta_fair函数对vruntime的累加进行加权。权重序列以几何级数方式散开，从而保证nice值的比较优先级，即两个任务获得CPU比例只和相应nice值的差别有关系，和nice值的绝对值没有关系。