樸素的UNIX之-Linux CFS一個注釋

本系列名為樸素的UNIX，但是也包括各個類UNIX系統的細節，本系列文章整理自本人幾年來的學習筆記，著重分析各個UNIX，類UNIX的實現思想以及感悟。
       本文比較短，只是分析一下Linux CFS調度器的一個細節。
       在進程尋找下一個將被運行的進程時，難道僅僅只是在紅黑樹上取下左下角的進程嗎？事實上最樸素的實現就是這樣，但是考慮到優化的話，就沒有這么簡單了。要 考慮CPU緩存的利用率，即如果一個進程A搶占了進程B，那么在A進程的上下文中，pick next是選擇進程B呢還是選擇紅黑樹的左下角進程呢？另外如果進程A剛被喚醒，企圖搶占進程B，但是沒有成功，那么下一個是選擇紅黑樹的左下角進程呢還 是選擇進程A呢？是的，這些都是問題。
       我們看一下pick next的實現：

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct sched_entity *se = __pick_next_entity(cfs_rq);
    struct sched_entity *left = se;

    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    /*
     * Prefer last buddy, try to return the CPU to a preempted task.
     */
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    clear_buddies(cfs_rq, se);

    return se;
}

很顯然，要把紅黑樹最左下角的進程和另外兩個進程，即next和last最比較，next是搶占失敗的進程，而last則是搶占成功后被搶占的進程，這三個進程到底哪一個是最優的next進程呢？Linux CFS實現的判決條件是：
1.盡可能滿足需要剛被喚醒的進程搶占其它進程的需求；
2.盡可能減少以上這種搶占帶來的緩存刷新的影響。
Linux CFS實現是怎么做到的呢？Linux保存了兩個變量，即搶占失敗的進程和搶占成功后被搶占的進程，在權衡的時候，優先選擇的順序是：
搶占成功后被搶占的進程>搶占失敗的進程>紅黑樹最左下角的進程

到底能不能選擇前兩個進程，則是wakeup_preempt_entity函數來決定的，代碼太多無益，看下面的圖解即可：

這個CFS的細節在Linux 2.6.23最初實現CFS時并沒有實現。因此從最樸素的時×××始，你才能逐漸理解細節的來龍去脈，看Changelog是有好處的。不得不說，讀史使人明智。