[转]鼠眼再看Linux调度器［2］

四、CFS。

    CFS现在还是非常新的调度实现，并且本人水平也十分有限，有鉴于此，这里很可能存在不当的地方甚至错误，权当抛砖引玉，不妥之处还请诸位有识之士不吝指正。

        在讨论CFS之前，我们先回顾一下现有的调度器实现：这是一个巧妙的双优先级数组方案。为了尽量避免出现“过期数组”中的任务出现饥饿现象，内核使用了一些启发式的方法判断是否出现了饥饿。在绝大多数情况下，这个实现给了我们非常好的交互性体验。不过，可惜在个别情况下仍会出现明显的饥饿现象，更致命的是，这个问题是完全可以重现的。躲躲闪闪修修补补终究不是解决问题之道。用Ingo的话说，问题的根源在于调度器没有一种机制可以跟踪使用者的“眼球”－－从而不能及时获得哪些任务是最希望尽快处理的，哪些任务是可以暂缓处理的这种线索。现有的调度器试图使用启发式方法解决这个问题，但并不完美。这种情况下，尽量的公平可能就是一种可行的方案了，Con Kolivas的RDSL／SD调度方案也从实践上证明了这个方案是可行的。不过，CFS使用了与之完全不同的方法实现“公平”的概念。

        我们已经知道了CFS是“完全公平调度”的缩写，那究竟什么是“公平”呢？首先，“公平”绝不意味着“相等”，也就是说在分配处理器资源时，不能简单地将系统内所有任务都一视同仁，而要区别对待。这是因为系统内的任务本身就不是平等的，例如许多内核线程生来用来应付某种比较紧急的情况的，它们理应比普通的用户空间任务更优越一些（事实上CFS的早期版本确实会引起某些内核线程的饥饿）。从另一方面上看，绝对公平也是不可能实现的，CFS所关注的是时间上相对长程（long-term）的公平（也可看成是总体上的，统计上的公平），在每个小的时间区间很可能看起来并不是公平的，引起这种现象的可能是需要对以往的不公平作补偿、系统的负载发生变化、实现方法限制等诸多原因。此外，公平也应该是层次化的。不过，现在CFS并没有支持这种性质的公平，所以这里先按下不谈。所以说，CFS中的“C”和“F”其实都不是绝对的。

        在实现公平的方法上，社区内也发生过激烈的讨论。讨论的导火索也是我们也试图解决的老大难问题：如何处理X窗口系统的服务器。一派认为X服务器是一个特殊的应用程序，它很大程度上影响了GUI的使用体验，甚至于它还自己直接访问硬件（主要是显示卡），我们有充足的理由对其进行特殊处理，更具体地，就是让使用者自己去提升X服务器的静态优先级。甚至，CFS的有些版本曾经利用X服务器自行硬件访问的行为自动对X服务器做一些调度上的奖励（通过截获ioperm()系统调用）；另一派试图找到一种全能的公平调度方法，它们认为X并没有多少代表性，许多服务器类任务的运行时间都是因为处理客户端的要求而消耗的。“实践是检验真理的唯一标准”，最终，新版本的CFS使得完美主义派占得了上风。这次讨论的成果远不仅于此，yield的语义得到了改进，我们有了一个新的系统调用yield_to()；在C／S这种情景下，由IPC引起特殊的优先级反转现象也做了一些讨论，甚至还出现了一个原型补丁；最重要地，对分组化的调度做了初步的探讨，这也是Srivatsa Vaddagiri所提交的分组化调度补丁的主要契机之一。分组化的调度（group scheduling，不要和gang scheduling混淆）是个非常有意思的方向，它一个可见的用武之地就是对虚拟化提供强有力的支持，对调度有兴趣的读者我衷心推荐跟踪它的发展。

        那么，如何达到“公平”呢？假设一个单处理器系统内有三个运行参数完全相同并且同等重要的任务，在理想的公平条件下，它们在应该同时开始同时完成。但恐怕只有在多维时间的条件下，这种处理器才可能制造出来的～ 所以，必然会有任务的开始执行时间被延迟了，为了做到公平，它在占用处理器时也要将这部分时间找补回来。这样，依据什么指标选择要占用处理器的任务的问题就得到解决了：我们只需要选择等待处理器时间最长的任务那个就行了，即，要占用处理器时间最长的那个。那么如何确定任务占用时间的上限呢？在系统满负荷时，最大只能分配其指定配额。那么，如何确定配额呢？简单地按任务数量分割的“大锅饭”显然与上面刚刚介绍的关于公平和相等的讨论相矛盾。某个处理器上各种任务的权重才是更好的指标，它可以包纳任务权值（重要程度）不同的情形。不过，暂且等等！只是“某个处理器上”吗？那多处理器间的公平怎么办呢？答案，那是负载均衡部分的责任，稍后我们再简单提一下CFS如何对负载均衡支持的。

        注意，上段有一句：“在系统满负荷时，最大只能分配其指定配额。”那么，在系统不是满负荷时呢？显然我们不想因为“配额”的原因就是让处理器空闲着。例如：当处理器上有两个任务就是纯计算任务（不休眠的那种），两者的权重相等，也就是公平的情况下，它们应该分别占有50％的处理器时间。如果其中一个任务早于另一个提前结束了，我们可不希望剩下的一个还是只能使用50％的处理器时间。那么，有办法可以达到这个要求吗？

        当然有！实际上不仅仅在处理器调度上有这种要求，在分组交换网络等领域上也有类似需求，这类调度有一个名字：work-conserving调度。Virtual Clock就是其中一种兼具实现容易和表现优异两种优点的方法。它首先出现在应用于分组网络的论文中，但当然我们会在处理器调度的场景下解释它：

    
        在这种方法里，除了实际的时钟，每个处理器所对应的运行队列还维护着一个虚拟时钟。它的前进步伐与该处理器上的任务权重成反比。也就是说当系统内有多个任务时，虚拟时钟的步调就按总权重大小成比例地慢下来，也即虚拟时间单元会按比例变长。例如：如果系统内有两个就绪任务，一个权值为1，另一个权值为2，这种情况下虚拟时间单元就是3个实际时间单元。在每个虚拟时间单元内这两个任务应该分别获得1／3和2／3的处理器时间。每个任务也都有自己的虚拟时钟，它们的前进步伐与自己的权重成反比。套用上面的例子，第一个任务的虚拟时钟单元与实际时间单元相同，为1；第二个任务的为1／2。请注意这样一个事实：在每个虚拟时间单元结束时，如果任务得到正常的公平待遇了，它们的虚拟时钟与运行队列的虚拟时钟是相同的。否则，如果任务的虚拟时钟慢于运行队列的，就说明该任务需要补偿了，反而就应该遏制该任务了。在最简单的情况下，我们通常选择具有最小虚拟时钟的任务就可以做到不错的公平了。如果你没有理解这段虚拟时钟的介绍，下面使用这种最小虚拟时钟调度的例子应该会有所帮助：（任务1、2、3的权重分别为1、2、3）

实际时钟	运行队列 虚拟时钟	任务1 虚拟时钟	任务2 虚拟时钟	任务3 虚拟时钟
0	0	0	0	0
1	0.17	1	0	0
2	0.34	1	0.5	0
3	0.5	1	0.5	0.33
4	0.67	1	0.5	0.67
5	0.83	1	1	0.67
6	1	1	1	1

        从上可知，运行队列上的虚拟时钟实际上就是把判断公平与否的标尺。对，这就是CFS使用虚拟时钟的方针！这个时钟用rq结构的fair_clock成员表示，在函数update_curr()内维护着它的前进步伐。

    “单个处理器上的权重”，内核中用rq结构上的raw_weighted_load表示。它是该处理器上所有任务的load_weight成员之和。nice为0（静态优先级为120）的任务的load_weight为1024，以此为基础，nice每变化1个单位，load_weight就递增20％，例如nice为2的任务的load_weight就是655（1024x80%x80%）。对应到处理器的占用率上，相临的nice值相差10％，也就是nice值减一，就可以得到10％的处理器占用率的提升。实际上，内核里还有一种根据该处理器的运行历史情况计算的负载（rq->cpu_load[]），这种方法更准确一些，但波动也更大些，为了抵消这种瞬时波动性所带来的不良影响，内核对每一个处理器计算了多种粒度的负载结果，新版本的CFS没有使用这种方法。

        前面说到的“等待处理器的时间”（代码中为task_struct->wait_runtime），是按任务进入就绪队列之时开始计算的，这符合直觉，不过，新版本的CFS也对休眠于可中断状态（TASK_INTERRUPTIBLE）的任务给予补偿，这样做的原因是因为I／O操作而休眠的任务大多处于此状态。任务状态间的切换本来就是由内核维护的，记录这两种时间戳对于内核来说是非常容易的。

        无论是什么调度方法，它要解决的无非就是挑选哪个任务、为其分配多少CPU时间两个基本问题，CFS的对应解决方法是：

     1、挑选那个等待处理器时间最长的任务占用处理器。这样，在挑选任务的过程中已经全然没有了优先级的参与，只有时间因素参与其中，这样，任务队列就很自然地是某种按时间排序的数据结构了，CFS选择了用红黑树表示运行队列。红黑树，一种二叉平衡查找树变体，它的左右子树高差是有可能大于1的，所以，红黑树不是严格意义上的平衡二叉树（也即AVL），但因为对之进行平衡的代价较低，其平均统计性能要强于AVL。和大多数查找二叉树一样，红黑树中较小的键值也是在左子树保存。红黑树键值的差不多就是插入时运行队列虚拟时间与“等待处理器时间”之差，即rq->fair_clock-task_struct->wait_runtime。这样，CFS选择任务时，只需要选择红黑树内最左小角的那个。在task_struct结构上用fair_key成员表示这个键值。

      2、按照任务权值所代表的负载（task_struct->load_weight）占该处理器上总负载（rq->raw_weigthed_load）的比例计算要分配给任务的处理器时间。这样，分配给任务的处理器时间就不是固定的了。系统内也没有硬性规定占用处理器的时间上限，具体运行多少时间是根据处理器负载及时变化的。我理解，这就是Ingo声称CFS内没有“时间片”概念的最本质原因。那么，它要如何及时变化才能体现出“公平”呢？呵呵，和我一起往下看吧。

      CFS提供了一系列微调其行为的配置参数，在下面的讨论中只针对默认配置，有兴趣的读者想要扩展开来，我认为也是比较容易的。我在列举代码分支时去掉了非默认分支，甚至对分支条件的判断。也许你已经迫不急待地想看看CFS的实现了，上面我们介绍过的“调度类”的几个关键方法，CFS是这样填补上去的：

struct sched_class fair_sched_class __read_mostly = {
    .enqueue_task        = enqueue_task_fair,
    .dequeue_task        = dequeue_task_fair,
    .pick_next_task        = pick_next_task_fair,
    .task_tick        = task_tick_fair,
    /* ...... */
};

    其中最简单的就是pick_next_task_fair()了：

/* 功能：获得要占用处理器的下一个任务 */
static struct task_struct * pick_next_task_fair(struct rq *rq, u64 now)
{
1>    struct task_struct *p = __pick_next_task_fair(rq);

2>    update_stats_wait_end(rq, p, now);
3>    update_stats_curr_start(rq, p, now);

    return p;
}


1. __pick_next_task_fair()，这是完成取“下一个要占用处理器任务”功能的实际函数。如前所述，它取等待处理器时间最长（task_struct->fair_key最小）的那个任务。在实现上，就是取红黑树内左下角的那个结点，这里还有一点点优化处理，类似于内核在处理VMA时所做的那样。

2. 不要被这个函数名称中的“wait”所迷惑，它不是指任务状态中的那个“休眠”，而是指停留于运行队列的行为。CFS内有几个函数名称是以“update_stat”作为前缀。但不要因为它们的名字而忽略它们，它们更新的不单单是统计信息，很多是CFS的关键参数。但在本场景下，这个函数没做对调度行为有任何影响的操作，只是计算了一个最长停留时间，它用在显示任务的运行时统计信息时。

3. 这个函数的行为很简单，它只是保存了任务p的开始运行时间（exec_start），它是update_curr()完成必要功能的重要输入，而后者是CFS的重要实现环节。

/* 功能：时钟中断内的调度处理 */
static void task_tick_fair(struct rq *rq, struct task_struct *curr)
{
    struct task_struct *next;
1>    u64 now = __rq_clock(rq);

2>    dequeue_task_fair(rq, curr, 0, now);
    enqueue_task_fair(rq, curr, 0, now);

3>    next = __pick_next_task_fair(rq);
    if (next == curr)
        return;

4>    if ((curr == rq->idle) || (rt_prio(next->prio) &&
                    (next->prio < curr->prio)))
        resched_task(curr);
    else
5>        __check_preempt_curr_fair(rq, next, curr,
                     sysctl_sched_granularity);
}


1. 在现有的调度实现中，任务队列首先按动态优先级排序。一般的Linux任务有40种优先级别。而CFS则完全是以时间组织运行队列，对比现有的调度实现CFS的“优先级”安排就相当于“无级变速”。但是深究起来，CFS的“变速器”也是有级的，其粒度取决于CFS所能感知的实际时间单元长度，它越精细CFS的“变速器”就更无级化，“公平”也更会理想化。这里的__rq_lock()就是CFS用于感知时间的“传感器”，获取到的时间以纳秒计，不过我们也要保持清醒的头脑，它仅仅是为纳秒为单位，并不是真正分辨到每个纳秒。

2. 恐怕所有的调度方法都不会放过时钟中断这个时机调整当前任务的运行时参数。调整过程之后，还要根据这些新参数调整它在运行队列中的位置（先删除再重新插入）。在现有调度实现中，我们是在“小运行队列”之间切换（例子见rt_mutex_setprio()），但在CFS内，我们是在红黑树上玩“滑梯”游戏。这两个函数我们稍后就会介绍。

3. 使用变量next保存现在运行队列中最合适占有处理器的任务。如果next与这个处理器上的当前任务相同，就说明当前任务还有资格使用处理器。后面的代码也就没有意义了，于是就直接返回了。

4. 这条语句做两个检查：如果处理器现在无事可做（即正运行着空闲任务）；或者，新任务是实时任务且比当前任务优先级更高，就直接使用resched_task(curr)做一个记号，使得当前任务稍后放弃处理器，让贤。

5. 因为CFS是以很精细的时间作为基础决定选择下一个调度任务的，并且它没有固定时间片的概念。所以就很有可能发生任务频繁切换的情况。这是我们不愿见到的：它增大了调度过程对系统的负担，也会使cache的利用率下降。__check_preempt_curr_fair()保证了当前任务占用处理器的时间有一个最小下限。这个下限是受两个因素影响：一个是运行时配置（通过sysctl），一个是当前任务与新任务的等待处理器时间之差的大小，这个函数的实现很直观，我们不再跟踪进去了。


/* 功能：将任务p加入到运行队列rq内。 */
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, u64 now)
{
1>    update_curr(rq, now);

2>    if (wakeup) {
        /* ...... */
    }
3>    update_stats_enqueue(rq, p, now);
4>    __enqueue_task_fair(rq, p);
}

1.将一个任务加入运行队列的时候，处理器上的负载也发生了变化，所以此时也是调整当前任务的运行时参数的好时机，update_curr()就是来干调整这个活计的，解释见后。
2.上面说到，新版本的CFS对处于可中断休眠状态会做一些额外奖励。这里跳过的代码就是该功能实现。有兴趣的读者可以自行阅读。
3.在加入运行队列之前，需要更新这个任务的“统计信息”。与之对应，还有一个在任务出队之前调用的 update_stats_dequeue ()。这两个函数和下面就要介绍的update_curr()是CFS核心逻辑的主要实现点。
4.这是将任务实际插入到红黑树运行队列中的函数。

    dequeue_task_fair()的逻辑与这个函数非常相似，我们就略过不看了。

static inline void
update_stats_enqueue(struct rq *rq, struct task_struct *p, u64 now)
{
    s64 key;

1>    if (p != rq->curr)
        update_stats_wait_start(rq, p, now);
2>    key = rq->fair_clock;

3>    if (likely(p->load_weight == NICE_0_LOAD)) {
        key -= p->wait_runtime;
    } else {
4>        if (p->wait_runtime < 0)
            key -= div64_s(p->wait_runtime * NICE_0_LOAD, p->load_weight);
        else
            key -= div64_s(p->wait_runtime * p->load_weight, NICE_0_LOAD);
    }
5>    p->fair_key = key;
}


1. 如果要加入运行队列的任务不是当前任务，就说明它是一个新来者。那么，这个任务在运行队列中的等待就开始了。update_stats_wait_start()就是来办理相关手续的，其实就是记录时间戳。这样我们就知道它在运行队列里究竟等待了多长时间了。如果由于某种原因，这个任务没有得到处理器就被从运行队列中除名了，这个时间戳就用来计算它在运行队列中待了多长时间，将之补偿在task_struct->wait_runtime中。

2. rq->fair_lock，就是这个处理器上的虚拟时钟；key是这个任务在红黑树运行队列中的键值，接着向下看；

3. 对于最常见的nice=0任务，计算key值：key -= p->wait_runtime。wait_runtime就是该任务以前在运行队列中等待时间，也就是在任务上次用完处理器后所剩的“资产”。key值越小，任务越富，越有可能早得到下次使用处理器的机会。

4. 以下代码是根据任务的“赢利情况”和系统内的负载，计算任务的“净资产”。对于“超支”的任务，就加点税：

   
5. 对于“欠收”的任务，我们给一些“福利”：

     6. p->fair_key就是在红黑树内使用的键值了。

     update_stats_dequeue()的逻辑相对简单，它也调用了update_curr()，我们就不再介绍了。经过这一番代码的打击，估计有些读者已经被以上有些麻烦的调用路径搞得些晕头转向了，看看下面的“地图”应该会清晰些：

    OK，最后再看看这个update_curr()重要函数：

static inline void update_curr(struct rq *rq, u64 now)
{
    unsigned long load = rq->raw_weighted_load;
    u64 delta_exec, delta_fair, delta_mine;
    struct task_struct *curr = rq->curr;

1>    if (curr->sched_class != &fair_sched_class || curr == rq->idle)
        return;

2>    delta_exec = now - curr->exec_start;

3>    curr->exec_start = now;

1>    if (!load)
        return;

4>    if (unlikely(sysctl_sched_load_smoothing & 1))
        if (unlikely(test_tsk_thread_flag(curr, TIF_NEED_RESCHED)))
            return;

5>    delta_fair = delta_exec * NICE_0_LOAD;
    delta_fair += load >> 1;
    do_div(delta_fair, load);

6>    delta_mine = delta_exec * curr->load_weight;
    delta_mine += load >> 1;
    do_div(delta_mine, load);

7>    rq->fair_clock += delta_fair;

8>    add_wait_runtime(rq, curr, delta_mine-delta_exec);
}


1. 在三种条件下更新当前任务的运行时信息是没有意义的：当前任务不在CFS管辖范围之内；当前处理器处于初始化或空闲状态。此时，这个函数就直接返回了。

2. delta_exec保存了自上次更新完exec_start之后，当前任务的实际执行时间。那么什么时候更新exec_start呢？上面说到的pick_next_task_fair()是一个地方，另一个地方就是update_curr()自己。再看看什么地方调用update_curr() ，如果追踪一下，就会发现简直太多了，不过幸亏原始代码在这里有处注释:)：只要负载（可能）发生了变化，我们就修改exec_start。这也符合我们在enqueue_task_fair()中的分析。

3. 将当前时间赋予exec_start，即启动下一个“采样周期”。

4. 如果当前任务是已经被标记为要让出处理器就提前从函数返回。这时再按正常的逻辑走只是浪费处理器资源。

5. 根据实际执行时间计算虚拟时钟的增量delta_fair。其中加了rq->raw_weighted_load >> 1，是用来四舍五入的小技巧。这个结果稍后作为虚拟时钟的增量。

6. delta_mine就是在delta_fair这个时段内，任务“应该”占用的时间。这对应于任务自己虚拟时钟的步伐长度。关于如何使用它的进一步解释见8。

7. 运行队列虚拟时钟的前进增量delta_fair。

8. 调整wait_runtime，因为delta_mine基本上总是小于delta_fair ，所以多数情况下是在减少wait_runime。这样，对应的fair_key就会逐渐增大（见update_stats_enqueue() 和task_tick_fair()），任务的财富逐渐减少，最终导致这个任务失去其在红黑树运行队列内最左下端的“宝座”，从而被迫让出处理器。从概念上讲，每个周期(两次exec_start更新之间的时间间隔)之间，CFS只应该分配给这个任务(task_struct->load_weigth/rq->raw_weighted_load)％的处理器时间（也就是delta_mine）。但是下次更新exec_start的时间是不可能准确预言的，所以不可能直接实现这种分配方案，我们只能在更长的时间尺度上做到按比例分配。如果影响时间分配呢？我们只要按比例地将任务的fair_key在时间轴上向后移就能达到目的了，而wait_runtime与fair_key是直接相关的，所以减少wait_runtime其实也就是向后移了fair_key，这便是这条语句的真正用意了。虽然因为虚拟时钟的缘故这里做定量的分析有些麻烦，但是定性的分析还是很容易的：读者可以试着推导一下如果task_struct->load_weight分别是较大或者较小的数值，上述几个因素delta_mine、wait_runtime、fair_key分别会向哪个方向变化。想必经过这一番思考读者一定能体会此处是如何影响处理器时间分配的。

        那么，我们能否归纳出一个数学公式清楚地表明wait_runtime和nice是如何影响处理器占用时间的呢？我试图做过这样的尝试，但以失败告终。在简单的情况（UP，静态负载）下，或者通过数学推导，或者通过实验，我们能够知道单单使用最小虚拟时钟调度就可以做到按load_weight比例的公平。但按照最大wait_runtime调度则做不到按load_weight比例的公平：即相同的load_weight增量，得不到相同增量的处理器时间，但在相同增量的前提下，此时两者的对应关系还是有保证的。现有CFS内load_weight的增量幅度是20％，我尝试过修改它为10％，30％，40％：没有一个可以达到类似于现有的10％处理器时间增量的效果的。看起来，这个20％的load_weight增量更像是一个经验值。所以，我觉得不太可能存在一个简单的线性关系公式。

        最后，有些读者可能对在使用CFS时“常规动态优先级”是如何处理的有些好奇，我想下面的代码足以解惑了：关于平均休眠时间（sleep_avg）的奖惩处理完全消失了，可见，CFS内根本没有“动态优先级”的概念，在CFS内扮演与之对应的角色是fair_key（本质上是就是以时间为计量）。

 

static inline int __normal_prio(struct task_struct *p)
{
    return p->static_prio;
}


        行文将近结束，大家应该已经大致了解了单处理器上CFS的工作原理了。但是在多处理器时呢？仔细观察CFS的实现，尤其是update_curr()中，我们可以知道，虚拟时钟只有在系统内有程序运行时才会流逝，这只是处理器间虚拟时钟不一致的其中一个原因。做负载均衡处理器间迁移任务时，就需要显式地处理这种时间差，否则就会破坏目标处理器上的“平衡”，下面就是处理这种时间差的代码，逻辑很清楚，我就不再地说详细解释它了：

void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
{
    int old_cpu = task_cpu(p);
    struct rq *old_rq = cpu_rq(old_cpu), *new_rq = cpu_rq(new_cpu);
    u64 clock_offset, fair_clock_offset;

    clock_offset = old_rq->clock - new_rq->clock;
    fair_clock_offset = old_rq->fair_clock - new_rq->fair_clock;

    if (p->wait_start)
        p->wait_start -= clock_offset;
    /* ...... */
    task_thread_info(p)->cpu = new_cpu;
}

五、参考材料：

        除了内核自带的一些相关文档外，以下另外一些有价值的资源：

        ＜＜Real-time Systems＞＞ 作者Jane W.S. Liu

        第八章详细讨论了优先级反转方面的内容。实际上，我觉得这本书是现在市面上能够找到的最好的介绍实时系统调度的书了。更幸运的是，可以同时买到中文翻译和影印版。这本书中关于EDF的介绍对我阅读RTAI的代码也起了很大的帮助作用。不过看这本书需要些耐心，数学的内容不少哦。强烈建议同时收藏中英文两本。

        ＜＜算法I－IV（C实现）：数据结构、排序和搜索＞＞ 作者 Robert Sedgewick

        作者师从算法大师Knuth。在我能找到的若干本算法书里，这本书对红黑树的概念介绍是最好的。如果你只死记硬背过一堆关于红黑树的定理，而没有听说过2-3-4树的话，也许你真没有理解好红黑树，应该看看这本书。不过这本书只能找到英文版的，似乎讲C＋＋语言实现的版本有中文版，但我没有看过，无法评价。

     http://

       这个网站上收集了一些LKML上关于CFS的讨论，还经过一些整理，虽然并不完整，但可读性好多了。这里值得看看，尤其是关于CFS和EEVDF的讨论，值得一读。EEVDF论文的下载链接也可以在这找到。但这里能找到的信息，在LKML上都可以得到。

    LKML

       网上有许多地方有LKML的archieve，有些Site甚至支持查找功能，这使得我们不用订阅也能读到大侠们的墨迹。如果想详细了解CFS成长过程的话，LKML是唯一的通天之路。除了Linus和Ingo，下面这三位大侠如果出手，可要留意一下他们的招式呀：Peter Williams、William Lee Irwin III 、Ting Yang。