1.3.4 CFS调度算法

Linux实现了一种完全公平的普通任务的调度策略CFS（Completely Fair Scheduling）。CFS是通过计算进程消耗的CPU时间（标准化以后的虚拟CPU时间）来确定谁来运行，从而达到调度的公平性。CFS通过引入vruntime（虚拟运行时间）的概念来表示进程运行时间与期望运行时间的比率。vruntime越小，说明期望没有满足，需要优先调度，vruntime越大，说明已经基本满足要求了，可以晚点调度。

在上述公式中，实际运行时间就是当前任务已经完成的时间，进程权重时间就是根据进程设置的权重比换算出来的权重时间。普通进程是通过权重值来调整优先级的，优先级的大小范围是-20～19，数值越小优先级越大，意味着权重值越大。CFS就是通过prio_to_weight数组来设置权重值获取权重时间的。权重值对应的权重时间如代码清单1-2所示。

代码清单1-2 权重值对应的权重时间

如果把一个进入任务的优先级设置成0，那么vruntime的计算公式就变成：

vruntime=实际运行时间×1024/1024

vruntime相当于实际运行时间。在算法实现上，CFS采用了红黑树来存储调度的任务节点，红黑树的结构如图1-10所示。树的左边节点的vruntime值小于右边节点的vruntime值。在任务调度的时候，取下最左边的节点来运行就可以了。

图1-10 CFS红黑树结构

例如在图1-10中，CFS会调度vruntime为11的节点优先运行，之后会调度vruntime为18的节点。