四、CFS。

    CFS現(xiàn)在還是非常新的調(diào)度實(shí)現(xiàn)，并且本人水平也十分有限，有鑒于此，這里很可能存在不當(dāng)?shù)牡胤缴踔铃e(cuò)誤，權(quán)當(dāng)拋磚引玉，不妥之處還請(qǐng)諸位有識(shí)之士不吝指正。

        在討論CFS之前，我們先回顧一下現(xiàn)有的調(diào)度器實(shí)現(xiàn)：這是一個(gè)巧妙的雙優(yōu)先級(jí)數(shù)組方案。為了盡量避免出現(xiàn)“過(guò)期數(shù)組”中的任務(wù)出現(xiàn)饑餓現(xiàn)象，內(nèi)核使用了一些啟發(fā)式的方法判斷是否出現(xiàn)了饑餓。在絕大多數(shù)情況下，這個(gè)實(shí)現(xiàn)給了我們非常好的交互性體驗(yàn)。不過(guò)，可惜在個(gè)別情況下仍會(huì)出現(xiàn)明顯的饑餓現(xiàn)象，更致命的是，這個(gè)問(wèn)題是完全可以重現(xiàn)的。躲躲閃閃修修補(bǔ)補(bǔ)終究不是解決問(wèn)題之道。用Ingo的話說(shuō)，問(wèn)題的根源在于調(diào)度器沒(méi)有一種機(jī)制可以跟蹤使用者的“眼球”－－從而不能及時(shí)獲得哪些任務(wù)是最希望盡快處理的，哪些任務(wù)是可以暫緩處理的這種線索?，F(xiàn)有的調(diào)度器試圖使用啟發(fā)式方法解決這個(gè)問(wèn)題，但并不完美。這種情況下，盡量的公平可能就是一種可行的方案了，Con Kolivas的RDSL／SD調(diào)度方案也從實(shí)踐上證明了這個(gè)方案是可行的。不過(guò)，CFS使用了與之完全不同的方法實(shí)現(xiàn)“公平”的概念。

        我們已經(jīng)知道了CFS是“完全公平調(diào)度”的縮寫(xiě)，那究竟什么是“公平”呢？首先，“公平”絕不意味著“相等”，也就是說(shuō)在分配處理器資源時(shí)，不能簡(jiǎn)單地將系統(tǒng)內(nèi)所有任務(wù)都一視同仁，而要區(qū)別對(duì)待。這是因?yàn)橄到y(tǒng)內(nèi)的任務(wù)本身就不是平等的，例如許多內(nèi)核線程生來(lái)用來(lái)應(yīng)付某種比較緊急的情況的，它們理應(yīng)比普通的用戶空間任務(wù)更優(yōu)越一些（事實(shí)上CFS的早期版本確實(shí)會(huì)引起某些內(nèi)核線程的饑餓）。從另一方面上看，絕對(duì)公平也是不可能實(shí)現(xiàn)的，CFS所關(guān)注的是時(shí)間上相對(duì)長(zhǎng)程（long-term）的公平（也可看成是總體上的，統(tǒng)計(jì)上的公平），在每個(gè)小的時(shí)間區(qū)間很可能看起來(lái)并不是公平的，引起這種現(xiàn)象的可能是需要對(duì)以往的不公平作補(bǔ)償、系統(tǒng)的負(fù)載發(fā)生變化、實(shí)現(xiàn)方法限制等諸多原因。此外，公平也應(yīng)該是層次化的。不過(guò)，現(xiàn)在CFS并沒(méi)有支持這種性質(zhì)的公平，所以這里先按下不談。所以說(shuō)，CFS中的“C”和“F”其實(shí)都不是絕對(duì)的。

        在實(shí)現(xiàn)公平的方法上，社區(qū)內(nèi)也發(fā)生過(guò)激烈的討論。討論的導(dǎo)火索也是我們也試圖解決的老大難問(wèn)題：如何處理X窗口系統(tǒng)的服務(wù)器。一派認(rèn)為X服務(wù)器是一個(gè)特殊的應(yīng)用程序，它很大程度上影響了GUI的使用體驗(yàn)，甚至于它還自己直接訪問(wèn)硬件（主要是顯示卡），我們有充足的理由對(duì)其進(jìn)行特殊處理，更具體地，就是讓使用者自己去提升X服務(wù)器的靜態(tài)優(yōu)先級(jí)。甚至，CFS的有些版本曾經(jīng)利用X服務(wù)器自行硬件訪問(wèn)的行為自動(dòng)對(duì)X服務(wù)器做一些調(diào)度上的獎(jiǎng)勵(lì)（通過(guò)截獲ioperm()系統(tǒng)調(diào)用）；另一派試圖找到一種全能的公平調(diào)度方法，它們認(rèn)為X并沒(méi)有多少代表性，許多服務(wù)器類任務(wù)的運(yùn)行時(shí)間都是因?yàn)樘幚砜蛻舳说囊蠖牡??！皩?shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)”，最終，新版本的CFS使得完美主義派占得了上風(fēng)。這次討論的成果遠(yuǎn)不僅于此，yield的語(yǔ)義得到了改進(jìn)，我們有了一個(gè)新的系統(tǒng)調(diào)用yield_to()；在C／S這種情景下，由IPC引起特殊的優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象也做了一些討論，甚至還出現(xiàn)了一個(gè)原型補(bǔ)??；最重要地，對(duì)分組化的調(diào)度做了初步的探討，這也是Srivatsa Vaddagiri所提交的分組化調(diào)度補(bǔ)丁的主要契機(jī)之一。分組化的調(diào)度（group scheduling，不要和gang scheduling混淆）是個(gè)非常有意思的方向，它一個(gè)可見(jiàn)的用武之地就是對(duì)虛擬化提供強(qiáng)有力的支持，對(duì)調(diào)度有興趣的讀者我衷心推薦跟蹤它的發(fā)展。

        那么，如何達(dá)到“公平”呢？假設(shè)一個(gè)單處理器系統(tǒng)內(nèi)有三個(gè)運(yùn)行參數(shù)完全相同并且同等重要的任務(wù)，在理想的公平條件下，它們?cè)趹?yīng)該同時(shí)開(kāi)始同時(shí)完成。但恐怕只有在多維時(shí)間的條件下，這種處理器才可能制造出來(lái)的～所以，必然會(huì)有任務(wù)的開(kāi)始執(zhí)行時(shí)間被延遲了，為了做到公平，它在占用處理器時(shí)也要將這部分時(shí)間找補(bǔ)回來(lái)。這樣，依據(jù)什么指標(biāo)選擇要占用處理器的任務(wù)的問(wèn)題就得到解決了：我們只需要選擇等待處理器時(shí)間最長(zhǎng)的任務(wù)那個(gè)就行了，即，要占用處理器時(shí)間最長(zhǎng)的那個(gè)。那么如何確定任務(wù)占用時(shí)間的上限呢？在系統(tǒng)滿負(fù)荷時(shí)，最大只能分配其指定配額。那么，如何確定配額呢？簡(jiǎn)單地按任務(wù)數(shù)量分割的“大鍋飯”顯然與上面剛剛介紹的關(guān)于公平和相等的討論相矛盾。某個(gè)處理器上各種任務(wù)的權(quán)重才是更好的指標(biāo)，它可以包納任務(wù)權(quán)值（重要程度）不同的情形。不過(guò)，暫且等等！只是“某個(gè)處理器上”嗎？那多處理器間的公平怎么辦呢？答案，那是負(fù)載均衡部分的責(zé)任，稍后我們?cè)俸?jiǎn)單提一下CFS如何對(duì)負(fù)載均衡支持的。

        注意，上段有一句：“在系統(tǒng)滿負(fù)荷時(shí)，最大只能分配其指定配額?！蹦敲矗谙到y(tǒng)不是滿負(fù)荷時(shí)呢？顯然我們不想因?yàn)椤芭漕~”的原因就是讓處理器空閑著。例如：當(dāng)處理器上有兩個(gè)任務(wù)就是純計(jì)算任務(wù)（不休眠的那種），兩者的權(quán)重相等，也就是公平的情況下，它們應(yīng)該分別占有50％的處理器時(shí)間。如果其中一個(gè)任務(wù)早于另一個(gè)提前結(jié)束了，我們可不希望剩下的一個(gè)還是只能使用50％的處理器時(shí)間。那么，有辦法可以達(dá)到這個(gè)要求嗎？

        當(dāng)然有！實(shí)際上不僅僅在處理器調(diào)度上有這種要求，在分組交換網(wǎng)絡(luò)等領(lǐng)域上也有類似需求，這類調(diào)度有一個(gè)名字：work-conserving調(diào)度。Virtual Clock就是其中一種兼具實(shí)現(xiàn)容易和表現(xiàn)優(yōu)異兩種優(yōu)點(diǎn)的方法。它首先出現(xiàn)在應(yīng)用于分組網(wǎng)絡(luò)的論文中，但當(dāng)然我們會(huì)在處理器調(diào)度的場(chǎng)景下解釋它：

        從上可知，運(yùn)行隊(duì)列上的虛擬時(shí)鐘實(shí)際上就是把判斷公平與否的標(biāo)尺。對(duì)，這就是CFS使用虛擬時(shí)鐘的方針！這個(gè)時(shí)鐘用rq結(jié)構(gòu)的fair_clock成員表示，在函數(shù)update_curr()內(nèi)維護(hù)著它的前進(jìn)步伐。

    “單個(gè)處理器上的權(quán)重”，內(nèi)核中用rq結(jié)構(gòu)上的raw_weighted_load表示。它是該處理器上所有任務(wù)的load_weight成員之和。nice為0（靜態(tài)優(yōu)先級(jí)為120）的任務(wù)的load_weight為1024，以此為基礎(chǔ)，nice每變化1個(gè)單位，load_weight就遞增20％，例如nice為2的任務(wù)的load_weight就是655（1024x80%x80%）。對(duì)應(yīng)到處理器的占用率上，相臨的nice值相差10％，也就是nice值減一，就可以得到10％的處理器占用率的提升。實(shí)際上，內(nèi)核里還有一種根據(jù)該處理器的運(yùn)行歷史情況計(jì)算的負(fù)載（rq->cpu_load[]），這種方法更準(zhǔn)確一些，但波動(dòng)也更大些，為了抵消這種瞬時(shí)波動(dòng)性所帶來(lái)的不良影響，內(nèi)核對(duì)每一個(gè)處理器計(jì)算了多種粒度的負(fù)載結(jié)果，新版本的CFS沒(méi)有使用這種方法。

        前面說(shuō)到的“等待處理器的時(shí)間”（代碼中為task_struct->wait_runtime），是按任務(wù)進(jìn)入就緒隊(duì)列之時(shí)開(kāi)始計(jì)算的，這符合直覺(jué)，不過(guò)，新版本的CFS也對(duì)休眠于可中斷狀態(tài)（TASK_INTERRUPTIBLE）的任務(wù)給予補(bǔ)償，這樣做的原因是因?yàn)?/FONT>I／O操作而休眠的任務(wù)大多處于此狀態(tài)。任務(wù)狀態(tài)間的切換本來(lái)就是由內(nèi)核維護(hù)的，記錄這兩種時(shí)間戳對(duì)于內(nèi)核來(lái)說(shuō)是非常容易的。

        無(wú)論是什么調(diào)度方法，它要解決的無(wú)非就是挑選哪個(gè)任務(wù)、為其分配多少CPU時(shí)間兩個(gè)基本問(wèn)題，CFS的對(duì)應(yīng)解決方法是：

     1、挑選那個(gè)等待處理器時(shí)間最長(zhǎng)的任務(wù)占用處理器。這樣，在挑選任務(wù)的過(guò)程中已經(jīng)全然沒(méi)有了優(yōu)先級(jí)的參與，只有時(shí)間因素參與其中，這樣，任務(wù)隊(duì)列就很自然地是某種按時(shí)間排序的數(shù)據(jù)結(jié)構(gòu)了，CFS選擇了用紅黑樹(shù)表示運(yùn)行隊(duì)列。紅黑樹(shù)，一種二叉平衡查找樹(shù)變體，它的左右子樹(shù)高差是有可能大于1的，所以，紅黑樹(shù)不是嚴(yán)格意義上的平衡二叉樹(shù)（也即AVL），但因?yàn)閷?duì)之進(jìn)行平衡的代價(jià)較低，其平均統(tǒng)計(jì)性能要強(qiáng)于AVL。和大多數(shù)查找二叉樹(shù)一樣，紅黑樹(shù)中較小的鍵值也是在左子樹(shù)保存。紅黑樹(shù)鍵值的差不多就是插入時(shí)運(yùn)行隊(duì)列虛擬時(shí)間與“等待處理器時(shí)間”之差，即rq->fair_clock-task_struct->wait_runtime。這樣，CFS選擇任務(wù)時(shí)，只需要選擇紅黑樹(shù)內(nèi)最左小角的那個(gè)。在task_struct結(jié)構(gòu)上用fair_key成員表示這個(gè)鍵值。

      2、按照任務(wù)權(quán)值所代表的負(fù)載（task_struct->load_weight）占該處理器上總負(fù)載（rq->raw_weigthed_load）的比例計(jì)算要分配給任務(wù)的處理器時(shí)間。這樣，分配給任務(wù)的處理器時(shí)間就不是固定的了。系統(tǒng)內(nèi)也沒(méi)有硬性規(guī)定占用處理器的時(shí)間上限，具體運(yùn)行多少時(shí)間是根據(jù)處理器負(fù)載及時(shí)變化的。我理解，這就是Ingo聲稱CFS內(nèi)沒(méi)有“時(shí)間片”概念的最本質(zhì)原因。那么，它要如何及時(shí)變化才能體現(xiàn)出“公平”呢？呵呵，和我一起往下看吧。

      CFS提供了一系列微調(diào)其行為的配置參數(shù)，在下面的討論中只針對(duì)默認(rèn)配置，有興趣的讀者想要擴(kuò)展開(kāi)來(lái)，我認(rèn)為也是比較容易的。我在列舉代碼分支時(shí)去掉了非默認(rèn)分支，甚至對(duì)分支條件的判斷。也許你已經(jīng)迫不急待地想看看CFS的實(shí)現(xiàn)了，上面我們介紹過(guò)的“調(diào)度類”的幾個(gè)關(guān)鍵方法，CFS是這樣填補(bǔ)上去的：

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,     /* ...... */ };

    其中最簡(jiǎn)單的就是pick_next_task_fair()了：

/* 功能：獲得要占用處理器的下一個(gè)任務(wù) */ 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()，這是完成取“下一個(gè)要占用處理器任務(wù)”功能的實(shí)際函數(shù)。如前所述，它取等待處理器時(shí)間最長(zhǎng)（task_struct->fair_key最?。┑哪莻€(gè)任務(wù)。在實(shí)現(xiàn)上，就是取紅黑樹(shù)內(nèi)左下角的那個(gè)結(jié)點(diǎn)，這里還有一點(diǎn)點(diǎn)優(yōu)化處理，類似于內(nèi)核在處理VMA時(shí)所做的那樣。

2. 不要被這個(gè)函數(shù)名稱中的“wait”所迷惑，它不是指任務(wù)狀態(tài)中的那個(gè)“休眠”，而是指停留于運(yùn)行隊(duì)列的行為。CFS內(nèi)有幾個(gè)函數(shù)名稱是以“update_stat”作為前綴。但不要因?yàn)樗鼈兊拿侄雎运鼈儯鼈兏碌牟粏螁问墙y(tǒng)計(jì)信息，很多是CFS的關(guān)鍵參數(shù)。但在本場(chǎng)景下，這個(gè)函數(shù)沒(méi)做對(duì)調(diào)度行為有任何影響的操作，只是計(jì)算了一個(gè)最長(zhǎng)停留時(shí)間，它用在顯示任務(wù)的運(yùn)行時(shí)統(tǒng)計(jì)信息時(shí)。

3. 這個(gè)函數(shù)的行為很簡(jiǎn)單，它只是保存了任務(wù)p的開(kāi)始運(yùn)行時(shí)間（exec_start），它是update_curr()完成必要功能的重要輸入，而后者是CFS的重要實(shí)現(xiàn)環(huán)節(jié)。

/* 功能：時(shí)鐘中斷內(nèi)的調(diào)度處理 */ 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. 在現(xiàn)有的調(diào)度實(shí)現(xiàn)中，任務(wù)隊(duì)列首先按動(dòng)態(tài)優(yōu)先級(jí)排序。一般的Linux任務(wù)有40種優(yōu)先級(jí)別。而CFS則完全是以時(shí)間組織運(yùn)行隊(duì)列，對(duì)比現(xiàn)有的調(diào)度實(shí)現(xiàn)CFS的“優(yōu)先級(jí)”安排就相當(dāng)于“無(wú)級(jí)變速”。但是深究起來(lái)，CFS的“變速器”也是有級(jí)的，其粒度取決于CFS所能感知的實(shí)際時(shí)間單元長(zhǎng)度，它越精細(xì)CFS的“變速器”就更無(wú)級(jí)化，“公平”也更會(huì)理想化。這里的__rq_lock()就是CFS用于感知時(shí)間的“傳感器”，獲取到的時(shí)間以納秒計(jì)，不過(guò)我們也要保持清醒的頭腦，它僅僅是為納秒為單位，并不是真正分辨到每個(gè)納秒。

2. 恐怕所有的調(diào)度方法都不會(huì)放過(guò)時(shí)鐘中斷這個(gè)時(shí)機(jī)調(diào)整當(dāng)前任務(wù)的運(yùn)行時(shí)參數(shù)。調(diào)整過(guò)程之后，還要根據(jù)這些新參數(shù)調(diào)整它在運(yùn)行隊(duì)列中的位置（先刪除再重新插入）。在現(xiàn)有調(diào)度實(shí)現(xiàn)中，我們是在“小運(yùn)行隊(duì)列”之間切換（例子見(jiàn)rt_mutex_setprio()），但在CFS內(nèi)，我們是在紅黑樹(shù)上玩“滑梯”游戲。這兩個(gè)函數(shù)我們稍后就會(huì)介紹。

3. 使用變量next保存現(xiàn)在運(yùn)行隊(duì)列中最合適占有處理器的任務(wù)。如果next與這個(gè)處理器上的當(dāng)前任務(wù)相同，就說(shuō)明當(dāng)前任務(wù)還有資格使用處理器。后面的代碼也就沒(méi)有意義了，于是就直接返回了。

4. 這條語(yǔ)句做兩個(gè)檢查：如果處理器現(xiàn)在無(wú)事可做（即正運(yùn)行著空閑任務(wù)）；或者，新任務(wù)是實(shí)時(shí)任務(wù)且比當(dāng)前任務(wù)優(yōu)先級(jí)更高，就直接使用resched_task(curr)做一個(gè)記號(hào)，使得當(dāng)前任務(wù)稍后放棄處理器，讓賢。

5. 因?yàn)?/FONT>CFS是以很精細(xì)的時(shí)間作為基礎(chǔ)決定選擇下一個(gè)調(diào)度任務(wù)的，并且它沒(méi)有固定時(shí)間片的概念。所以就很有可能發(fā)生任務(wù)頻繁切換的情況。這是我們不愿見(jiàn)到的：它增大了調(diào)度過(guò)程對(duì)系統(tǒng)的負(fù)擔(dān)，也會(huì)使cache的利用率下降。__check_preempt_curr_fair()保證了當(dāng)前任務(wù)占用處理器的時(shí)間有一個(gè)最小下限。這個(gè)下限是受兩個(gè)因素影響：一個(gè)是運(yùn)行時(shí)配置（通過(guò)sysctl），一個(gè)是當(dāng)前任務(wù)與新任務(wù)的等待處理器時(shí)間之差的大小，這個(gè)函數(shù)的實(shí)現(xiàn)很直觀，我們不再跟蹤進(jìn)去了。

/* 功能：將任務(wù)p加入到運(yùn)行隊(duì)列rq內(nèi)。 */ 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.將一個(gè)任務(wù)加入運(yùn)行隊(duì)列的時(shí)候，處理器上的負(fù)載也發(fā)生了變化，所以此時(shí)也是調(diào)整當(dāng)前任務(wù)的運(yùn)行時(shí)參數(shù)的好時(shí)機(jī)，update_curr()就是來(lái)干調(diào)整這個(gè)活計(jì)的，解釋見(jiàn)后。 2.上面說(shuō)到，新版本的CFS對(duì)處于可中斷休眠狀態(tài)會(huì)做一些額外獎(jiǎng)勵(lì)。這里跳過(guò)的代碼就是該功能實(shí)現(xiàn)。有興趣的讀者可以自行閱讀。 3.在加入運(yùn)行隊(duì)列之前，需要更新這個(gè)任務(wù)的“統(tǒng)計(jì)信息”。與之對(duì)應(yīng)，還有一個(gè)在任務(wù)出隊(duì)之前調(diào)用的 update_stats_dequeue ()。這兩個(gè)函數(shù)和下面就要介紹的update_curr()是CFS核心邏輯的主要實(shí)現(xiàn)點(diǎn)。 4.這是將任務(wù)實(shí)際插入到紅黑樹(shù)運(yùn)行隊(duì)列中的函數(shù)。     dequeue_task_fair()的邏輯與這個(gè)函數(shù)非常相似，我們就略過(guò)不看了。 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. 如果要加入運(yùn)行隊(duì)列的任務(wù)不是當(dāng)前任務(wù)，就說(shuō)明它是一個(gè)新來(lái)者。那么，這個(gè)任務(wù)在運(yùn)行隊(duì)列中的等待就開(kāi)始了。update_stats_wait_start()就是來(lái)辦理相關(guān)手續(xù)的，其實(shí)就是記錄時(shí)間戳。這樣我們就知道它在運(yùn)行隊(duì)列里究竟等待了多長(zhǎng)時(shí)間了。如果由于某種原因，這個(gè)任務(wù)沒(méi)有得到處理器就被從運(yùn)行隊(duì)列中除名了，這個(gè)時(shí)間戳就用來(lái)計(jì)算它在運(yùn)行隊(duì)列中待了多長(zhǎng)時(shí)間，將之補(bǔ)償在task_struct->wait_runtime中。

2. rq->fair_lock，就是這個(gè)處理器上的虛擬時(shí)鐘；key是這個(gè)任務(wù)在紅黑樹(shù)運(yùn)行隊(duì)列中的鍵值，接著向下看；

3. 對(duì)于最常見(jiàn)的nice=0任務(wù)，計(jì)算key值：key -= p->wait_runtime。wait_runtime就是該任務(wù)以前在運(yùn)行隊(duì)列中等待時(shí)間，也就是在任務(wù)上次用完處理器后所剩的“資產(chǎn)”。key值越小，任務(wù)越富，越有可能早得到下次使用處理器的機(jī)會(huì)。

4. 以下代碼是根據(jù)任務(wù)的“贏利情況”和系統(tǒng)內(nèi)的負(fù)載，計(jì)算任務(wù)的“凈資產(chǎn)”。對(duì)于“超支”的任務(wù)，就加點(diǎn)稅：

   
5. 對(duì)于“欠收”的任務(wù)，我們給一些“福利”：

     6. p->fair_key就是在紅黑樹(shù)內(nèi)使用的鍵值了。

     update_stats_dequeue()的邏輯相對(duì)簡(jiǎn)單，它也調(diào)用了update_curr()，我們就不再介紹了。經(jīng)過(guò)這一番代碼的打擊，估計(jì)有些讀者已經(jīng)被以上有些麻煩的調(diào)用路徑搞得些暈頭轉(zhuǎn)向了，看看下面的“地圖”應(yīng)該會(huì)清晰些：

    OK，最后再看看這個(gè)update_curr()重要函數(shù)：

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. 在三種條件下更新當(dāng)前任務(wù)的運(yùn)行時(shí)信息是沒(méi)有意義的：當(dāng)前任務(wù)不在CFS管轄范圍之內(nèi)；當(dāng)前處理器處于初始化或空閑狀態(tài)。此時(shí)，這個(gè)函數(shù)就直接返回了。

2. delta_exec保存了自上次更新完exec_start之后，當(dāng)前任務(wù)的實(shí)際執(zhí)行時(shí)間。那么什么時(shí)候更新exec_start呢？上面說(shuō)到的pick_next_task_fair()是一個(gè)地方，另一個(gè)地方就是update_curr()自己。再看看什么地方調(diào)用update_curr() ，如果追蹤一下，就會(huì)發(fā)現(xiàn)簡(jiǎn)直太多了，不過(guò)幸虧原始代碼在這里有處注釋:)：只要負(fù)載（可能）發(fā)生了變化，我們就修改exec_start。這也符合我們?cè)?/FONT>enqueue_task_fair()中的分析。

3. 將當(dāng)前時(shí)間賦予exec_start，即啟動(dòng)下一個(gè)“采樣周期”。

4. 如果當(dāng)前任務(wù)是已經(jīng)被標(biāo)記為要讓出處理器就提前從函數(shù)返回。這時(shí)再按正常的邏輯走只是浪費(fèi)處理器資源。

5. 根據(jù)實(shí)際執(zhí)行時(shí)間計(jì)算虛擬時(shí)鐘的增量delta_fair。其中加了rq->raw_weighted_load >> 1，是用來(lái)四舍五入的小技巧。這個(gè)結(jié)果稍后作為虛擬時(shí)鐘的增量。

6. delta_mine就是在delta_fair這個(gè)時(shí)段內(nèi)，任務(wù)“應(yīng)該”占用的時(shí)間。這對(duì)應(yīng)于任務(wù)自己虛擬時(shí)鐘的步伐長(zhǎng)度。關(guān)于如何使用它的進(jìn)一步解釋見(jiàn)8。

7. 運(yùn)行隊(duì)列虛擬時(shí)鐘的前進(jìn)增量delta_fair。

8. 調(diào)整wait_runtime，因?yàn)?/FONT>delta_mine基本上總是小于delta_fair ，所以多數(shù)情況下是在減少wait_runime。這樣，對(duì)應(yīng)的fair_key就會(huì)逐漸增大（見(jiàn)update_stats_enqueue() 和task_tick_fair()），任務(wù)的財(cái)富逐漸減少，最終導(dǎo)致這個(gè)任務(wù)失去其在紅黑樹(shù)運(yùn)行隊(duì)列內(nèi)最左下端的“寶座”，從而被迫讓出處理器。從概念上講，每個(gè)周期(兩次exec_start更新之間的時(shí)間間隔)之間，CFS只應(yīng)該分配給這個(gè)任務(wù)(task_struct->load_weigth/rq->raw_weighted_load)％的處理器時(shí)間（也就是delta_mine）。但是下次更新exec_start的時(shí)間是不可能準(zhǔn)確預(yù)言的，所以不可能直接實(shí)現(xiàn)這種分配方案，我們只能在更長(zhǎng)的時(shí)間尺度上做到按比例分配。如果影響時(shí)間分配呢？我們只要按比例地將任務(wù)的fair_key在時(shí)間軸上向后移就能達(dá)到目的了，而wait_runtime與fair_key是直接相關(guān)的，所以減少wait_runtime其實(shí)也就是向后移了fair_key，這便是這條語(yǔ)句的真正用意了。雖然因?yàn)樘摂M時(shí)鐘的緣故這里做定量的分析有些麻煩，但是定性的分析還是很容易的：讀者可以試著推導(dǎo)一下如果task_struct->load_weight分別是較大或者較小的數(shù)值，上述幾個(gè)因素delta_mine、wait_runtime、fair_key分別會(huì)向哪個(gè)方向變化。想必經(jīng)過(guò)這一番思考讀者一定能體會(huì)此處是如何影響處理器時(shí)間分配的。

        那么，我們能否歸納出一個(gè)數(shù)學(xué)公式清楚地表明wait_runtime和nice是如何影響處理器占用時(shí)間的呢？我試圖做過(guò)這樣的嘗試，但以失敗告終。在簡(jiǎn)單的情況（UP，靜態(tài)負(fù)載）下，或者通過(guò)數(shù)學(xué)推導(dǎo)，或者通過(guò)實(shí)驗(yàn)，我們能夠知道單單使用最小虛擬時(shí)鐘調(diào)度就可以做到按load_weight比例的公平。但按照最大wait_runtime調(diào)度則做不到按load_weight比例的公平：即相同的load_weight增量，得不到相同增量的處理器時(shí)間，但在相同增量的前提下，此時(shí)兩者的對(duì)應(yīng)關(guān)系還是有保證的?，F(xiàn)有CFS內(nèi)load_weight的增量幅度是20％，我嘗試過(guò)修改它為10％，30％，40％：沒(méi)有一個(gè)可以達(dá)到類似于現(xiàn)有的10％處理器時(shí)間增量的效果的。看起來(lái)，這個(gè)20％的load_weight增量更像是一個(gè)經(jīng)驗(yàn)值。所以，我覺(jué)得不太可能存在一個(gè)簡(jiǎn)單的線性關(guān)系公式。

        最后，有些讀者可能對(duì)在使用CFS時(shí)“常規(guī)動(dòng)態(tài)優(yōu)先級(jí)”是如何處理的有些好奇，我想下面的代碼足以解惑了：關(guān)于平均休眠時(shí)間（sleep_avg）的獎(jiǎng)懲處理完全消失了，可見(jiàn)，CFS內(nèi)根本沒(méi)有“動(dòng)態(tài)優(yōu)先級(jí)”的概念，在CFS內(nèi)扮演與之對(duì)應(yīng)的角色是fair_key（本質(zhì)上是就是以時(shí)間為計(jì)量）。

 

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

        行文將近結(jié)束，大家應(yīng)該已經(jīng)大致了解了單處理器上CFS的工作原理了。但是在多處理器時(shí)呢？仔細(xì)觀察CFS的實(shí)現(xiàn)，尤其是update_curr()中，我們可以知道，虛擬時(shí)鐘只有在系統(tǒng)內(nèi)有程序運(yùn)行時(shí)才會(huì)流逝，這只是處理器間虛擬時(shí)鐘不一致的其中一個(gè)原因。做負(fù)載均衡處理器間遷移任務(wù)時(shí)，就需要顯式地處理這種時(shí)間差，否則就會(huì)破壞目標(biāo)處理器上的“平衡”，下面就是處理這種時(shí)間差的代碼，邏輯很清楚，我就不再地說(shuō)詳細(xì)解釋它了：

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

五、參考材料：

        除了內(nèi)核自帶的一些相關(guān)文檔外，以下另外一些有價(jià)值的資源：

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

        第八章詳細(xì)討論了優(yōu)先級(jí)反轉(zhuǎn)方面的內(nèi)容。實(shí)際上，我覺(jué)得這本書(shū)是現(xiàn)在市面上能夠找到的最好的介紹實(shí)時(shí)系統(tǒng)調(diào)度的書(shū)了。更幸運(yùn)的是，可以同時(shí)買(mǎi)到中文翻譯和影印版。這本書(shū)中關(guān)于EDF的介紹對(duì)我閱讀RTAI的代碼也起了很大的幫助作用。不過(guò)看這本書(shū)需要些耐心，數(shù)學(xué)的內(nèi)容不少哦。強(qiáng)烈建議同時(shí)收藏中英文兩本。

        ＜＜算法I－IV（C實(shí)現(xiàn)）：數(shù)據(jù)結(jié)構(gòu)、排序和搜索＞＞作者 Robert Sedgewick

        作者師從算法大師Knuth。在我能找到的若干本算法書(shū)里，這本書(shū)對(duì)紅黑樹(shù)的概念介紹是最好的。如果你只死記硬背過(guò)一堆關(guān)于紅黑樹(shù)的定理，而沒(méi)有聽(tīng)說(shuō)過(guò)2-3-4樹(shù)的話，也許你真沒(méi)有理解好紅黑樹(shù)，應(yīng)該看看這本書(shū)。不過(guò)這本書(shū)只能找到英文版的，似乎講C＋＋語(yǔ)言實(shí)現(xiàn)的版本有中文版，但我沒(méi)有看過(guò)，無(wú)法評(píng)價(jià)。

     http://www.

       這個(gè)網(wǎng)站上收集了一些LKML上關(guān)于CFS的討論，還經(jīng)過(guò)一些整理，雖然并不完整，但可讀性好多了。這里值得看看，尤其是關(guān)于CFS和EEVDF的討論，值得一讀。EEVDF論文的下載鏈接也可以在這找到。但這里能找到的信息，在LKML上都可以得到。

    LKML

       網(wǎng)上有許多地方有LKML的archieve，有些Site甚至支持查找功能，這使得我們不用訂閱也能讀到大俠們的墨跡。如果想詳細(xì)了解CFS成長(zhǎng)過(guò)程的話，LKML是唯一的通天之路。除了Linus和Ingo，下面這三位大俠如果出手，可要留意一下他們的招式呀：Peter Williams、William Lee Irwin III 、Ting Yang。