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