CFS浏览

CFS介绍
    自从2.6.23之后，linux采用了新的调度方式，称为：Completely Fair Scheduler（完全公平调度程序）缩写为CFS.
    完全公平调度程序（CFS）试图按照对 CPU 时间的 “最大需求（gravest need）” 运行任务；这有助于确保每个进程可以获得对 CPU 的公平共享。如果某个任务休眠时间 “非常短”，那么 CFS 不会将该任务视为休眠任务 — 短暂休眠的进程可能会获得一些额外时间，但是决不会超过它的未休眠时间。
Con Kolivas 证明了实现 “公平调度” 不会与交互性的延迟目标相冲突。他已经使用 RSDL/SD 调度程序证明，公平性可以很轻易地实现，不需要使用复杂的启发式处理来判断进程的交互性。
    CFS 没有使用优先级数组，它去掉了 vanilla 调度程序的数组切换工件。RSDL 和 CFS 之间的重要区别包括以下几点：
    1、RSDL 基于 “严格的公平性” 概念；然而，CFS 还考虑到交互式进程的休眠时间长度，因此，短暂休眠进程对 CPU 时间的占用会略微多一些。
    2、RSDL 使用诸如 vanilla 调度程序这样的优先级队列，而 CFS 没有使用。
    3、RSDL 和 vanilla 调度程序会受到数组切换工件的影响，而 CFS 不会。
CFS 不会跟踪休眠时间，也不会使用启发式处理识别交互式任务 — 它仅仅确保在既定时间内，对于一定数量的可运行进程，每个进程获得公平的 CPU 占用。


CFS工作原理
    CFS 调度程序使用安抚（appeasement）策略确保公平性。当某个任务进入运行队列后，将记录当前时间，当某个进程等待 CPU 时，将对这个进程的 wait_runtime 值加一个数，这个数取决于运行队列当前的进程数。当执行这些计算时，也将考虑不同任务的优先级值。 将这个任务调度到 CPU 后，它的 wait_runtime 值开始递减，当这个值递减到其他任务成为红黑树的最左侧任务时，当前任务将被抢占。通过这种方式，CFS 努力实现一种理想 状态，即 wait_runtime 值为 0！
    CFS 维护任务运行时（相对于运行队列级时钟，称为 fair_clock(cfs_rq->fair_clock)），它在某个实际时间的片段内运行，因此，对于单个任务可以按照理想的速度运行。
 例如，如果具有 4 个可运行的任务，那么 fair_clock 将按照实际时间速度的四分之一增加。每个任务将设法跟上这个速度。这是由分时多任务处理的量子化特性决定的。也就是说，在任何一个时间段内只有一个任务可以运行；因此，其他进程在时间上的拖欠将增大（wait_runtime）。因此，一旦某个任务进入调度，它将努力赶上它所欠下的时间（并且要比所欠时间多一点，因为在追赶时间期间，fair_clock 不会停止计时）。
    加权任务引入了优先级。假设我们有两个任务：其中一个任务占用 CPU 的时间量是另一个任务的两倍，比例为 2:1。执行数学转换后，对于权重为 0.5 的任务，时间流逝的速度是以前的两倍。我们根据 fair_clock 对树进行排队。
    请注意，CFS 没有使用时间片（time slices），至少，没有优先使用。CFS 中的时间片具有可变的长度并且动态确定。
    对于负载平衡程序，调度模块实现了迭代器，使用它遍历由调度模块管理的所有任务，从而进行负载平衡。

CFS阅读建议
     通过代码的阅读可以更清晰的了解CFS的工作原理和调度方式。建议通过两种方式来阅读：
    1、阅读 /Documentation 中的相关文档，了解大概情况
    2、阅读源代码，通过部分代码的阅读和尝试修改来完善对CFS的认识。