剛剛發(fā)布的 2.6.23 內(nèi)核中包含了一個重要的變化，用CFS替代了以前的調(diào)度器。CFS 被合并到 mainline之前，關(guān)于內(nèi)核調(diào)度器還有一個重要的 patch：RSDL。最終 2.6.23 決定將 CFS 合并到 mainline 而放棄了RSDL。為什么要引入新的調(diào)度器，CFS 和 RSDL有什么聯(lián)系和區(qū)別？本文試圖對內(nèi)核調(diào)度算法的發(fā)展歷史做一個簡要介紹，希望能對上述問題的理解有所幫助。
引言
進程調(diào)度是操作系統(tǒng)的核心功能。調(diào)度器只是是調(diào)度過程中的一部分，進程調(diào)度是非常復(fù)雜的過程，需要多個系統(tǒng)協(xié)同工作完成。本文所關(guān)注的僅為調(diào)度器，它的主要工作是在所有 RUNNING 進程中選擇最合適的一個。作為一個通用操作系統(tǒng)，Linux 調(diào)度器將進程分為三類：
交互式進程
此類進程有大量的人機交互，因此進程不斷地處于睡眠狀態(tài)，等待用戶輸入。典型的應(yīng)用比如編輯器 vi。此類進程對系統(tǒng)響應(yīng)時間要求比較高，否則用戶會感覺系統(tǒng)反應(yīng)遲緩。
批處理進程
此類進程不需要人機交互，在后臺運行，需要占用大量的系統(tǒng)資源。但是能夠忍受響應(yīng)延遲。比如編譯器。
實時進程
實時對調(diào)度延遲的要求最高，這些進程往往執(zhí)行非常重要的操作，要求立即響應(yīng)并執(zhí)行。比如視頻播放軟件或飛機飛行控制系統(tǒng)，很明顯這類程序不能容忍長時間的調(diào)度延遲，輕則影響電影放映效果，重則機毀人亡。
根 據(jù)進程的不同分類 Linux 采用不同的調(diào)度策略。對于實時進程，采用 FIFO 或者 Round Robin的調(diào)度策略。對于普通進程，則需要區(qū)分交互式和批處理式的不同。傳統(tǒng) Linux 調(diào)度器提高交互式應(yīng)用的優(yōu)先級，使得它們能更快地被調(diào)度。而 CFS和 RSDL 等新的調(diào)度器的核心思想是“完全公平”。這個設(shè)計理念不僅大大簡化了調(diào)度器的代碼復(fù)雜度，還對各種調(diào)度需求的提供了更完美的支持。
在探討CFS和RSDL之前，我們首先回顧一下Linux2.4和Linux2.6.0中所使用的調(diào)度器。
內(nèi)核調(diào)度器的簡單歷史
2.1 Linux2.4 的調(diào)度器
Linux2.4.18中使用的調(diào)度器采用基于優(yōu)先級的設(shè)計，這個調(diào)度器和 Linus 在 1992 年發(fā)布的調(diào)度器沒有大的區(qū)別。該調(diào)度器的 pick next算法非常簡單：對 runqueue 中所有進程的優(yōu)先級進行依次進行比較，選擇最高優(yōu)先級的進程作為下一個被調(diào)度的進程。(Runqueue 是Linux 內(nèi)核中保存所有就緒進程的隊列) 。術(shù)語 pick next 用來指從所有候選進程中挑選下一個要被調(diào)度的進程的過程。
每 個進程被創(chuàng)建時都被賦予一個時間片。時鐘中斷遞減當(dāng)前運行進程的時間片，當(dāng)進程的時間片被用完時，它必須等待重新賦予時間片才能有機會運行。Linux2.4 調(diào)度器保證只有當(dāng)所有 RUNNING 進程的時間片都被用完之后，才對所有進程重新分配時間片。這段時間被稱為一個epoch。這種設(shè)計保證了每個進程都有機會得到執(zhí)行。
各種進程對調(diào)度的需求并不相同，Linux2.4 調(diào)度器主要依靠改變進程的優(yōu)先級，來滿足不同進程的調(diào)度需求。事實上，所有后來的調(diào)度器都主要依賴修改進程優(yōu)先級來滿足不同的調(diào)度需求。
實時進程
實時進程的優(yōu)先級是靜態(tài)設(shè)定的，而且始終大于普通進程的優(yōu)先級。因此只有當(dāng) runqueue 中沒有實時進程的情況下，普通進程才能夠獲得調(diào)度。
實 時進程采用兩種調(diào)度策略：SCHED_FIFO 和 SCHED_RR。FIFO 采用先進先出的策略，對于所有相同優(yōu)先級的進程，最先進入runqueue 的進程總能優(yōu)先獲得調(diào)度；Round Robin 采用更加公平的輪轉(zhuǎn)策略，使得相同優(yōu)先級的實時進程能夠輪流獲得調(diào)度。
普通進程
對 于普通進程，調(diào)度器傾向于提高交互式進程的優(yōu)先級，因為它們需要快速的用戶響應(yīng)。普通進程的優(yōu)先級主要由進程描述符中的 Counter 字段決定(還要加上 nice 設(shè)定的靜態(tài)優(yōu)先級) 。進程被創(chuàng)建時子進程的 counter 值為父進程 counter值的一半，這樣保證了任何進程不能依靠不斷地 fork() 子進程從而獲得更多的執(zhí)行機會。
Linux2.4調(diào)度器是如何提高交互式進程的優(yōu)先級的呢？如前所述，當(dāng)所有 RUNNING 進程的時間片被用完之后，調(diào)度器將重新計算所有進程的 counter值，所有進程不僅包括 RUNNING 進程，也包括處于睡眠狀態(tài)的進程。處于睡眠狀態(tài)的進程的 counter本來就沒有用完，在重新計算時，他們的 counter值會加上這些原來未用完的部分，從而提高了它們的優(yōu)先級。交互式進程經(jīng)常因等待用戶輸入而處于睡眠狀態(tài)，當(dāng)它們重新被喚醒并進入 runqueue時，就會優(yōu)先于其它進程而獲得 CPU。從用戶角度來看，交互式進程的響應(yīng)速度就提高了。
該調(diào)度器的主要缺點：
可擴展性不好： 調(diào)度器選擇進程時需要遍歷整個 runqueue 從中選出最佳人選，因此該算法的執(zhí)行時間與進程數(shù)成正比。另外每次重新計算 counter所花費的時間也會隨著系統(tǒng)中進程數(shù)的增加而線性增長，當(dāng)進程數(shù)很大時，更新 counter 操作的代價會非常高，導(dǎo)致系統(tǒng)整體的性能下降。
高負載系統(tǒng)上的調(diào)度性能比較低：2.4的調(diào)度器預(yù)分配給每個進程的時間片比較大，因此在高負載的服務(wù)器上，該調(diào)度器的效率比較低，因為平均每個進程的等待時間于該時間片的大小成正比。
交互式進程的優(yōu)化并不完善：Linux2.4識別交互式進程的原理基于以下假設(shè)，即交互式進程比批處理進程更頻繁地處于SUSPENDED狀態(tài)。然而現(xiàn)實情況往往并非如此，有些批處理進程雖然沒有用 戶交互，但是也會頻繁地進行IO操作，比如一個數(shù)據(jù)庫引擎在處理查詢時會經(jīng)常地進行磁盤IO，雖然它們并不需要快速地用戶響應(yīng)，還是被提高了優(yōu)先級。當(dāng)系 統(tǒng)中這類進程的負載較重時，會影響真正的交互式進程的響應(yīng)時間。
對實時進程的支持不夠：Linux2.4內(nèi)核是非搶占的，當(dāng)進程處于內(nèi)核態(tài)時不會發(fā)生搶占，這對于真正的實時應(yīng)用是不能接受的。
為了解決這些問題，Ingo Molnar開發(fā)了新的O(1)調(diào)度器，在CFS和RSDL之前，這個調(diào)度器不僅被Linux2.6采用，還被backport到Linux2.4中，很多商業(yè)的發(fā)行版本都采用了這個調(diào)度器。
2.2 Linux2.6的O(1)調(diào)度器
從 名字就可以看出O(1)調(diào)度器主要解決了以前版本中的擴展性問題。O(1)調(diào)度算法所花費的時間為常數(shù)，與當(dāng)前系統(tǒng)中的進程個數(shù)無關(guān)。此外Linux2.6內(nèi)核支持內(nèi)核態(tài)搶占，因此更好地支持了實時進程。相對于前任，O (1) 調(diào)度器還更好地區(qū)分了交互式進程和批處理式進程。
Linux2.6內(nèi)核也支持三種調(diào)度策略。其中SCHED_FIFO和SCHED_RR用于實時進程，而SCHED_NORMAL用于普通進程。O(1)調(diào)度器在兩個方面修改了Linux2.4調(diào)度器，一是進程優(yōu)先級的計算方法；二是pick next算法。
2.2.1 進程的優(yōu)先級計算
普通進程的優(yōu)先級計算
普通進程優(yōu)先級是動態(tài)計算的，計算公式中包含了靜態(tài)優(yōu)先級。一般來講，靜態(tài)優(yōu)先級越高，進程所能分配到的時間片越長，用戶可以通過nice系統(tǒng)調(diào)用修改進程的靜態(tài)優(yōu)先級。
動態(tài)優(yōu)先級由公式一計算得出：
公式一
dynamic priority = max (100, min ( static priority – bonus +5, 139))
|
其中bonus 取決于進程的平均睡眠時間。由此可以看出，在linux2.6中，一個普通進程的優(yōu)先級和平均睡眠時間的關(guān)系為：平均睡眠時間越長，其bonus越大，從而得到更高的優(yōu)先級。
平均睡眠時間也被用來判斷進程是否是一個交互式進程。如果滿足下面的公式，進程就被認為是一個交互式進程：
公式二
Dynamic priority ≤ 3 x static priority /4 + 28
|
平均睡眠時間是進程處于等待睡眠狀態(tài)下的 時間，該值在進程進入睡眠狀態(tài)時增加，而進入RUNNING狀態(tài)后則減少。該值的更新時機分布在很多內(nèi)核函數(shù)內(nèi)：時鐘中斷scheduler_tick ()；進程創(chuàng)建；進程從TASK_INTERRUPTIBLE狀態(tài)喚醒；負載平衡等。
實時進程的優(yōu)先級計算
實時進程的優(yōu)先級由sys_sched_setschedule()設(shè)置。該值不會動態(tài)修改，而且總是比普通進程的優(yōu)先級高。在進程描述符中用rt_priority域表示。
2.2.2 pick next算法
普 通進程的調(diào)度選擇算法基于進程的優(yōu)先級，擁有最高優(yōu)先級的進程被調(diào)度器選中。2.4中，時間片counter同時也表示了一個進程的優(yōu)先級。2.6中時間 片用任務(wù)描述符中的time_slice域表示，而優(yōu)先級用prio（普通進程）或者rt_priority（實時進程）表示。
調(diào)度器為每一個CPU維護了兩個進程隊列數(shù)組：active數(shù)組和expire數(shù)組。數(shù)組中的元素著保存某一優(yōu)先級的進程隊列指針。系統(tǒng)一共有140個不同的優(yōu)先級，因此這兩個數(shù)組大小都是140。
當(dāng) 需要選擇當(dāng)前最高優(yōu)先級的進程時，2.6調(diào)度器不用遍歷整個runqueue，而是直接從active數(shù)組中選擇當(dāng)前最高優(yōu)先級隊列中的第一個進程。假設(shè) 當(dāng)前所有進程中最高優(yōu)先級為50(換句話說，系統(tǒng)中沒有任何進程的優(yōu)先級小于50)。則調(diào)度器直接讀取active[49]，得到優(yōu)先級為50的進程隊列 指針。該隊列頭上的第一個進程就是被選中的進程。這種算法的復(fù)雜度為O(1)，從而解決了2.4調(diào)度器的擴展性問題。
為 了實現(xiàn)上述算法active數(shù)組維護了一個bitmap，當(dāng)某個優(yōu)先級別上有進程被插入列表時，相應(yīng)的比特位就被置位。Sched_find_first_bit()函數(shù)查詢該bitmap，返回當(dāng)前被置位的最高優(yōu)先級的數(shù)組下標(biāo)。在上例中sched_find_first_bit函數(shù)將返回49。在IA處理器上可以通過bsfl等指令實現(xiàn)。
為了提高交互式進程的響應(yīng)時間，O(1)調(diào)度器不僅動態(tài)地提高該類進程的優(yōu)先級，還采用以下方法：
每 次時鐘tick中斷中，進程的時間片(time_slice)被減一。當(dāng)time_slice為0時，調(diào)度器判斷當(dāng)前進程的類型，如果是交互式進程或者實 時進程，則重置其時間片并重新插入active數(shù)組。如果不是交互式進程則從active數(shù)組中移到expired數(shù)組。這樣實時進程和交互式進程就總能 優(yōu)先獲得CPU。然而這些進程不能始終留在active數(shù)組中，否則進入expire數(shù)組的進程就會產(chǎn)生饑餓現(xiàn)象。當(dāng)進程已經(jīng)占用CPU時間超過一個固定 值后，即使它是實時進程或者交互式進程也會被移到expire數(shù)組中。
當(dāng)active數(shù)組中的所有進程都被移到expire數(shù)組中后，調(diào)度器交換active數(shù)組和expire數(shù)組。當(dāng)進程被移入expire數(shù)組時，調(diào)度器會重置其時間片，因此新的active數(shù)組又恢復(fù)了初始情況，而expire數(shù)組為空，從而開始新的一輪調(diào)度。
2.2.3 O(1)調(diào)度器小節(jié)
Linux2.6調(diào)度器改進了前任調(diào)度器的可擴展性問題，schedule()函數(shù)的時間復(fù)雜度為O(1)。這取決于兩個改進：
一．Pick next算法借助于active數(shù)組，無需遍歷runqueue；
二．取消了定期更新所有進程counter的操作，動態(tài)優(yōu)先級的修改分布在進程切換，時鐘tick中斷以及其它一些內(nèi)核函數(shù)中進行。
O(1)調(diào)度器區(qū)分交互式進程和批處理進程的算法與以前雖大有改進，但仍然在很多情況下會失效。有一些著名的程序總能讓該調(diào)度器性能下降，導(dǎo)致交互式進程反應(yīng)緩慢：
fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c
這些不足催生了Con Kolivas的樓梯調(diào)度算法SD，以及后來的改進版本RSDL。Ingo Molnar在RSDL之后開發(fā)了CFS，并最終被2.6.23內(nèi)核采用。接下來我們開始介紹這些新一代調(diào)度器。
3 新一代調(diào)度器
Linux2.6.0發(fā)布之前，很多人都擔(dān)心調(diào)度器存在的問題將阻礙新版本的發(fā)布。它對于交互式應(yīng)用仍然存在響應(yīng)性差的問題，對NUMA支持也不完善。為了解決這些問題，大量 難以維護和閱讀的復(fù)雜代碼被加入Linux2.6.0的調(diào)度器模塊，雖然很多性能問題因此得到了解決，可是另外一個嚴重問題始終困擾著許多內(nèi)核開發(fā)者。那 就是代碼的復(fù)雜度問題。
Con Kolivas，在2004年提出了第一個改進調(diào)度器設(shè)計的patch：staircase scheduler。為調(diào)度器設(shè)計提供了一個新的思路。之后的RSDL和CFS都基于SD的許多基本思想。本章中，我們將簡要探討這三個主要的調(diào)度器算法。
3.1 樓梯調(diào)度算法 staircase scheduler
樓梯算法(SD)在思路上和O(1)算法有很大不同，它拋棄了動態(tài)優(yōu)先級的概念。而采用了一種完全公平的思路。前任算法的主要復(fù)雜性來自動態(tài)優(yōu)先級的計算，調(diào)度器根據(jù)平均睡眠時間和一些很難理解的經(jīng)驗公式來修正進程的優(yōu)先級以及區(qū)分交互式進程。這樣的代碼很難閱讀和維護。
樓梯算法思路簡單，但是實驗證明它對應(yīng)交互式進程的響應(yīng)比其前任更好，而且極大地簡化了代碼。
和O(1)算法一樣，樓梯算法也同樣為每一個優(yōu)先級維護一個進程列表，并將這些列表組織在active數(shù)組中。當(dāng)選取下一個被調(diào)度進程時，SD算法也同樣從active數(shù)組中直接讀取。
與O (1)算法不同在于，當(dāng)進程用完了自己的時間片后，并不是被移到expire數(shù)組中。而是被加入active數(shù)組的低一優(yōu)先級列表中，即將其降低一個級 別。不過請注意這里只是將該任務(wù)插入低一級優(yōu)先級任務(wù)列表中，任務(wù)本身的優(yōu)先級并沒有改變。當(dāng)時間片再次用完，任務(wù)被再次放入更低一級優(yōu)先級任務(wù)隊列中。 就象一部樓梯，任務(wù)每次用完了自己的時間片之后就下一級樓梯。
任務(wù)下到最低一級樓梯時，如果時間片再次用完， 它會回到初始優(yōu)先級的下一級任務(wù)隊列中。比如某進程的優(yōu)先級為1，當(dāng)它到達最后一級臺階140后，再次用完時間片時將回到優(yōu)先級為2的任務(wù)隊列中，即第二 級臺階。不過此時分配給該任務(wù)的time_slice將變成原來的2倍。比如原來該任務(wù)的時間片time_slice為10ms，則現(xiàn)在變成了20ms。 基本的原則是，當(dāng)任務(wù)下到樓梯底部時，再次用完時間片就回到上次下樓梯的起點的下一級臺階。并給予該任務(wù)相同于其最初分配的時間片。總結(jié)如下：
設(shè)任務(wù)本身優(yōu)先級為P，當(dāng)它從第N級臺階開始下樓梯并到達底部后，將回到第N+1級臺階。并且賦予該任務(wù)N+1倍的時間片。
以上描述的是普通進程的調(diào)度算法，實時進程還是采用原來的調(diào)度策略，即FIFO或者Round Robin。
樓梯算法能避免進程饑餓現(xiàn)象，高優(yōu)先級的進程會最終和低優(yōu)先級的進程競爭，使得低優(yōu)先級進程最終獲得執(zhí)行機會。
對于交互式應(yīng)用，當(dāng)進入睡眠狀態(tài)時，與它同等優(yōu)先級的其他進程將一步一步地走下樓梯，進入低優(yōu)先級進程隊列。當(dāng)該交互式進程再次喚醒后，它還留在高處的樓梯臺階上，從而能更快地被調(diào)度器選中，加速了響應(yīng)時間。
樓梯算法的優(yōu)點
從實現(xiàn)角度看，SD基本上還是沿用了O(1)的整體框架，只是刪除了O(1)調(diào)度器中動態(tài)修改優(yōu)先級的復(fù)雜代碼；還淘汰了expire數(shù)組，從而簡化了代碼。它最重要的意義在于證明了完全公平這個思想的可行性。
3.2 RSDL（The Rotating Staircase Deadline Schedule）
RSDL也是由Con Kolivas開發(fā)的，它是對SD算法的改進。核心的思想還是“完全公平”。沒有復(fù)雜的動態(tài)優(yōu)先級調(diào)整策略。
RSDL重新引入了expire數(shù)組。它為每一個優(yōu)先級都分配了一個 “組時間配額”， 我們將組時間配額標(biāo)記為Tg；同一優(yōu)先級的每個進程都擁有同樣的"優(yōu)先級時間配額"本文中用Tp表示，以便于后續(xù)描述。
當(dāng) 進程用完了自身的Tp時，就下降到下一優(yōu)先級進程組中。這個過程和SD相同，在RSDL中這個過程叫做minor rotation。請注意Tp不等于進程的時間片，而是小于進程的時間片。下圖表示了minor rotation。進程從priority1的隊列中一步一步下到priority140之后回到priority2的隊列中，這個過程如下圖左邊所示， 然后從priority 2開始再次一步一步下樓，到底后再次反彈到priority3隊列中，如圖1所示。
圖 1.
在SD算法中，處于樓梯底部的低優(yōu)先級進程必須等待所有的高優(yōu)先級進程執(zhí)行完才能獲得CPU。因此低優(yōu)先級進程的等待時間無法確定。RSDL中，當(dāng)高優(yōu)先級進程 組用完了它們的Tg(即組時間配額)時，無論該組中是否還有進程Tp尚未用完，所有屬于該組的進程都被強制降低到下一優(yōu)先級進程組中。這樣低優(yōu)先級任務(wù)就 可以在一個可以預(yù)計的未來得到調(diào)度。從而改善了調(diào)度的公平性。這就是RSDL中Deadline代表的含義。
進程用完了自己的時間片time_slice時（下圖中T2），將放入expire數(shù)組中它初始的優(yōu)先級隊列中(priority 1)。
圖 2
當(dāng)active數(shù)組為空，或者所有的進程都降低到最低優(yōu)先級時就會觸發(fā)major rotation：。Major rotation交換active數(shù)組和expire數(shù)組，所有進程都恢復(fù)到初始狀態(tài)，再一次從新開始minor rotation的過程。
RSDL對交互式進程的支持
和SD同樣的道理，交互式進程在睡眠時間時，它所有的競爭者都因為minor rotation而降到了低優(yōu)先級進程隊列中。當(dāng)它重新進入RUNNING狀態(tài)時，就獲得了相對較高的優(yōu)先級，從而能被迅速響應(yīng)。
3.3 CFS 完全公平調(diào)度器
CFS是最終被內(nèi)核采納的調(diào)度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區(qū)分交互式進程。它將所有的進程都統(tǒng)一對待，這就是公平的含義。CFS的算法和實現(xiàn)都相當(dāng)簡單，眾多的測試表明其性能也非常優(yōu)越。
按 照作者Ingo Molnar的說法："CFS百分之八十的工作可以用一句話概括：CFS在真實的硬件上模擬了完全理想的多任務(wù)處理器"。在“完全理想的多任務(wù)處理器“下，每個進程都能同時獲得CPU的執(zhí)行時間。當(dāng)系統(tǒng)中有兩個進程時，CPU的計算時間被分成兩份，每個進程獲得50%。然而在實際的硬件上，當(dāng)一個進程 占用CPU時，其它進程就必須等待。這就產(chǎn)生了不公平。
假設(shè)runqueue中有n個進程，當(dāng)前進程運行了10ms。在“完全理想的多任務(wù)處理器”中，10ms應(yīng)該平分給n個進程(不考慮各個進程的nice值)，因此當(dāng)前進程應(yīng)得的時間是(10/n)ms，但 是它卻運行了10ms。所以CFS將懲罰當(dāng)前進程，使其它進程能夠在下次調(diào)度時盡可能取代當(dāng)前進程。最終實現(xiàn)所有進程的公平調(diào)度。下面將介紹CFS實現(xiàn)的 一些重要部分，以便深入地理解CFS的工作原理。
CFS如何實現(xiàn)pick next
CFS拋棄了active/expire數(shù)組，而使用紅黑樹選取下一個被調(diào)度進程。所有狀態(tài)為RUNABLE的進程都被插入紅黑樹。在每個調(diào)度點，CFS調(diào)度器都會選擇紅黑樹的最左邊的葉子節(jié)點作為下一個將獲得cpu的進程。
tick中斷
在CFS中，tick中斷首先更新調(diào)度信息。然后調(diào)整當(dāng)前進程在紅黑樹中的位置。調(diào)整完成后如果發(fā)現(xiàn)當(dāng)前進程不再是最左邊的葉子，就標(biāo)記need_resched標(biāo)志，中斷返回時就會調(diào)用scheduler()完成進程切換。否則當(dāng)前進程繼續(xù)占用CPU。從這里可以看到CFS拋棄了傳統(tǒng)的時間片概念。Tick中斷 只需更新紅黑樹，以前的所有調(diào)度器都在tick中斷中遞減時間片，當(dāng)時間片或者配額被用完時才觸發(fā)優(yōu)先級調(diào)整并重新調(diào)度。
紅黑樹鍵值計算
理解CFS的關(guān)鍵就是了解紅黑樹鍵值的計算方法。該鍵值由三個因子計算而得：一是進程已經(jīng)占用的CPU時間；二是當(dāng)前進程的nice值；三是當(dāng)前的cpu負載。
進 程已經(jīng)占用的CPU時間對鍵值的影響最大，其實很大程度上我們在理解CFS時可以簡單地認為鍵值就等于進程已占用的CPU時間。因此該值越大，鍵值越大， 從而使得當(dāng)前進程向紅黑樹的右側(cè)移動。另外CFS規(guī)定，nice值為1的進程比nice值為0的進程多獲得10%的CPU時間。在計算鍵值時也考慮到這個 因素，因此nice值越大，鍵值也越大。
CFS為每個進程都維護兩個重要變量：fair_clock和wait_runtime。在本文中，我們將為每個進程維護的變量稱為進程級變量，為每個CPU維護的稱作CPU級變量，為每個runqueue維護的稱為runqueue級變量。
進程插入紅黑樹的鍵值即為fair_clock – wait_runtime。
fair_clock從其字面含義上講就是一個進程應(yīng)獲得的CPU時間，即等于進程已占用的CPU時間除以當(dāng)前runqueue中的進程總數(shù)；wait_runtime是進程 的等待時間。它們的差值代表了一個進程的公平程度。該值越大，代表當(dāng)前進程相對于其它進程越不公平。
對于交互式任務(wù)，wait_runtime長時間得不到更新，因此它能擁有更高的紅黑樹鍵值，更靠近紅黑樹的左邊。從而得到快速響應(yīng)。
紅黑樹是平衡樹，調(diào)度器每次總最左邊讀出一個葉子節(jié)點，該讀取操作的時間復(fù)雜度是O(LgN)。
調(diào)度器管理器
為 了支持實時進程，CFS提供了調(diào)度器模塊管理器。各種不同的調(diào)度器算法都可以作為一個模塊注冊到該管理器中。不同的進程可以選擇使用不同的調(diào)度器模塊。2.6.23中，CFS實現(xiàn)了兩個調(diào)度算法，CFS算法模塊和實時調(diào)度模塊。對應(yīng)實時進程，將使用實時調(diào)度模塊。對應(yīng)普通進程則使用CFS算法。Ingo Molnar還邀請Con Kolivas可以將RSDL/SD寫成一個調(diào)度算法模塊。
CFS源代碼分析
Sched.c中scheduler_tick()函數(shù)會被時鐘中斷直接調(diào)用。它首先更新runqueue級變量clock；然后調(diào)用CFS的tick處理函數(shù)task_tick_fair()。task_tick_fair在sched_fair.c中。它主要的工作是調(diào)用entity_tick()
函數(shù)entiry_tick源代碼如下：
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *next;
dequeue_entity(cfs_rq, curr, 0);
enqueue_entity(cfs_rq, curr, 0);
next = __pick_next_entity(cfs_rq);
if (next == curr)
return;
__check_preempt_curr_fair(cfs_rq, next, curr,
sched_granularity(cfs_rq));
}
|
首先調(diào)用dequeue_entity ()函數(shù)將當(dāng)前進程從紅黑樹中刪除，再調(diào)用enqueue_entity（）重新插入。這兩個動作就調(diào)整了當(dāng)前進程在紅黑樹中的位置。_pick_next_entity()返回紅黑樹中最左邊的節(jié)點，如果不再是當(dāng)前進程，就調(diào)用_check_preempt_curr_fair。該函 數(shù)設(shè)置調(diào)度標(biāo)志，當(dāng)中斷返回時就會調(diào)用schedule()進行調(diào)度。
函數(shù)enqueue_entity()的源碼如下:
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
{
/*
* Update the fair clock.
*/
update_curr(cfs_rq);
if (wakeup)
enqueue_sleeper(cfs_rq, se);
update_stats_enqueue(cfs_rq, se);
__enqueue_entity(cfs_rq, se);
}
|
它的第一個工作是更新調(diào)度信息。然后將進程插入紅黑樹中。其中update_curr()函數(shù)是核心。完成調(diào)度信息的更新。
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq_curr(cfs_rq);
unsigned long delta_exec;
if (unlikely(!curr))
return;
delta_exec = (unsigned long)(rq_of(cfs_rq)->clock - curr->exec_start);
curr->delta_exec += delta_exec;
if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) {
__update_curr(cfs_rq, curr);
curr->delta_exec = 0;
}
curr->exec_start = rq_of(cfs_rq)->clock;
}
|
該函數(shù)首先統(tǒng)計當(dāng)前進程所獲得的CPU時 間，rq_of(cfs_rq)->clock值在tick中斷中被更新，curr->exec_start就是當(dāng)前進程開始獲得CPU時的 時間戳。兩值相減就是當(dāng)前進程所獲得的CPU時間。將該變量存入curr->delta_exec中。然后調(diào)用__update_curr()
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long delta, delta_exec, delta_fair, delta_mine;
struct load_weight *lw = &cfs_rq-load;
unsigned long load = lw->weight;
delta_exec = curr->delta_exec;
schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
curr->sum_exec_runtime += delta_exec;
cfs_rq->exec_clock += delta_exec;
if (unlikely(!load)) return;
delta_fair = calc_delta_fair(delta_exec, lw);
delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw);
if (cfs_rq->sleeper_bonus > sysctl_sched_min_granularity) {
delta = min((u64)delta_mine, cfs_rq->sleeper_bonus);
delta = min(delta, (unsigned long)(
(long)sysctl_sched_runtime_limit - curr->wait_runtime));
cfs_rq->sleeper_bonus -= delta;
delta_mine -= delta;
}
cfs_rq->fair_clock += delta_fair;
add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec);
}
|
__update_curr()的主要工 作就是更新前面提到的fair_clock和wait_runtime。這兩個值的差值就是后面進程插入紅黑樹的鍵值。變量Delta_exec保存了前 面獲得的當(dāng)前進程所占用的CPU時間。函數(shù)calc_delta_fair()根據(jù)cpu負載（保存在lw變量中），對delta_exec進行修正，然 后將結(jié)果保存到delta_fair變量中，隨后將fair_clock增加delta_fair。函數(shù)calc_delta_mine()根據(jù)nice值（保存在curr->load.weight中）和cpu負載修正delta_exec，將結(jié)果保存在delta_mine中。根據(jù)源代碼中的注 釋，delta_mine就表示當(dāng)前進程應(yīng)該獲得的CPU時間。
隨后將delta_fair加給fair_clock而將delta_mine-delta_exec加給wait_runtime。函數(shù)add_wait_runtime中兩次將wait_runtime減去delta_mine-delta_exec。由于calc_delt_xx()函數(shù)對delta_exec僅做了較小的修 改，為了討論方便，我們可以忽略它們對delta_exec的修改。最終的結(jié)果可以近似看成fair_clock增加了一倍的delta_exec，而wait_runtime減小了兩倍的delta_exec。因此鍵值fair_clock-wait_runtime最終增加了一倍的delta_exec值。鍵值增加，使得當(dāng)前進程再次插入紅黑樹中就向右移動了。
CFS小結(jié)
以 上的討論看出CFS對以前的調(diào)度器進行了很大改動。用紅黑樹代替優(yōu)先級數(shù)組；用完全公平的策略代替動態(tài)優(yōu)先級策略；引入了模塊管理器；它修改了原來Linux2.6.0調(diào)度器模塊70%的代碼。結(jié)構(gòu)更簡單靈活，算法適應(yīng)性更高。相比于RSDL，雖然都基于完全公平的原理，但是它們的實現(xiàn)完全不同。相 比之下，CFS更加清晰簡單，有更好的擴展性。
CFS還有一個重要特點，即調(diào)度粒度小。CFS之前的調(diào)度器 中，除了進程調(diào)用了某些阻塞函數(shù)而主動參與調(diào)度之外，每個進程都只有在用完了時間片或者屬于自己的時間配額之后才被搶占。而CFS則在每次tick都進行 檢查，如果當(dāng)前進程不再處于紅黑樹的左邊，就被搶占。在高負載的服務(wù)器上，通過調(diào)整調(diào)度粒度能夠獲得更好的調(diào)度性能。
4 總結(jié)
通過對Linux調(diào)度器歷史發(fā)展的探討，能進一步了解CFS調(diào)度器開發(fā)的背景知識。其實目前任何調(diào)度器算法都還無法滿足所有應(yīng)用的需要，CFS也有一些負 面的測試報告。我們相信隨著Linux的不斷發(fā)展，還會出現(xiàn)新的調(diào)度算法，讓我們拭目以待。有抱負的程序員也可以嘗試著在這個領(lǐng)域為Linux作出貢獻。
參考資料