四、CFS。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. __pick_next_task_fair()，這是完成取“下一個要占用處理器任務(wù)”功能的實際函數(shù)。如前所述，它取等待處理器時間最長（task_struct->fair_key最小）的那個任務(wù)。在實現(xiàn)上，就是取紅黑樹內(nèi)左下角的那個結(jié)點，這里還有一點點優(yōu)化處理，類似于內(nèi)核在處理VMA時所做的那樣。

2. 不要被這個函數(shù)名稱中的“wait”所迷惑，它不是指任務(wù)狀態(tài)中的那個“休眠”，而是指停留于運行隊列的行為。CFS內(nèi)有幾個函數(shù)名稱是以“update_stat”作為前綴。但不要因為它們的名字而忽略它們，它們更新的不單單是統(tǒng)計信息，很多是CFS的關(guān)鍵參數(shù)。但在本場景下，這個函數(shù)沒做對調(diào)度行為有任何影響的操作，只是計算了一個最長停留時間，它用在顯示任務(wù)的運行時統(tǒng)計信息時。

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

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

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

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

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

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

1. 如果要加入運行隊列的任務(wù)不是當(dāng)前任務(wù)，就說明它是一個新來者。那么，這個任務(wù)在運行隊列中的等待就開始了。update_stats_wait_start()就是來辦理相關(guān)手續(xù)的，其實就是記錄時間戳。這樣我們就知道它在運行隊列里究竟等待了多長時間了。如果由于某種原因，這個任務(wù)沒有得到處理器就被從運行隊列中除名了，這個時間戳就用來計算它在運行隊列中待了多長時間，將之補償在task_struct->wait_runtime中。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、參考材料：

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

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

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

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

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

     http://www.

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

    LKML