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

成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供嘉興網(wǎng)站建設(shè)、嘉興做網(wǎng)站、嘉興網(wǎng)站設(shè)計(jì)、嘉興網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、嘉興企業(yè)網(wǎng)站模板建站服務(wù)，十載嘉興做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

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;
}

很顯然，要把紅黑樹最左下角的進(jìn)程和另外兩個(gè)進(jìn)程，即next和last最比較，next是搶占失敗的進(jìn)程，而last則是搶占成功后被搶占的進(jìn)程，這三個(gè)進(jìn)程到底哪一個(gè)是最優(yōu)的next進(jìn)程呢？Linux CFS實(shí)現(xiàn)的判決條件是：
1.盡可能滿足需要?jiǎng)偙粏拘训倪M(jìn)程搶占其它進(jìn)程的需求；
2.盡可能減少以上這種搶占帶來(lái)的緩存刷新的影響。
Linux CFS實(shí)現(xiàn)是怎么做到的呢？Linux保存了兩個(gè)變量，即搶占失敗的進(jìn)程和搶占成功后被搶占的進(jìn)程，在權(quán)衡的時(shí)候，優(yōu)先選擇的順序是：
搶占成功后被搶占的進(jìn)程>搶占失敗的進(jìn)程>紅黑樹最左下角的進(jìn)程

到底能不能選擇前兩個(gè)進(jìn)程，則是wakeup_preempt_entity函數(shù)來(lái)決定的，代碼太多無(wú)益，看下面的圖解即可：

這個(gè)CFS的細(xì)節(jié)在Linux 2.6.23最初實(shí)現(xiàn)CFS時(shí)并沒(méi)有實(shí)現(xiàn)。因此從最樸素的時(shí)×××始，你才能逐漸理解細(xì)節(jié)的來(lái)龍去脈，看Changelog是有好處的。不得不說(shuō)，讀史使人明智。