Linux進程調度策略的發展和演變

日期內核版本架構作者GitHubCSDN2016-06-14Linux-4.6X86 & armgatiemeLinuxDeviceDriversLinux進程管理與調度

前言

進程調度

內存中保存了對每個進程的唯一描述, 並通過若干結構與其他進程連接起來.
調度器面對的情形就是這樣, 其任務是在程序之間共享CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.

進程的分類

linux把進程區分為實時進程和非實時進程, 其中非實時進程進一步劃分為交互式進程和批處理進程
類型描述示例交互式進程(interactive process)此類進程經常與用戶進行交互, 因此需要花費很多時間等待鍵盤和鼠標操作. 當接受了用戶的輸入後, 進程必須很快被喚醒, 否則用戶會感覺系統反應遲鈍shell, 文本編輯程序和圖形應用程序批處理進程(batch process)此類進程不必與用戶交互, 因此經常在後台運行. 因為這樣的進程不必很快相應, 因此常受到調度程序的怠慢程序語言的編譯程序, 數據庫搜索引擎以及科學計算實時進程(real-time process)這些進程由很強的調度需要, 這樣的進程絕不會被低優先級的進程阻塞. 並且他們的響應時間要盡可能的短視頻音頻應用程序, 機器人控制程序以及從物理傳感器上收集數據的程序在linux中, 調度算法可以明確的確認所有實時進程的身份, 但是沒辦法區分交互式程序和批處理程序, linux2.6的調度程序實現了基於進程過去行為的啟發式算法, 以確定進程應該被當做交互式進程還是批處理進程. 當然與批處理進程相比, 調度程序有偏愛交互式進程的傾向

不同進程采用不同的調度策略

根據進程的不同分類Linux采用不同的調度策略.
對於實時進程，采用FIFO或者Round Robin的調度策略.
對於普通進程，則需要區分交互式和批處理式的不同。傳統Linux調度器提高交互式應用的優先級，使得它們能更快地被調度。而CFS和RSDL等新的調度器的核心思想是”完全公平”。這個設計理念不僅大大簡化了調度器的代碼復雜度，還對各種調度需求的提供了更完美的支持.
注意Linux通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共享一定資源（代碼和/或數據）的多個線程。因此進程調度也包含了線程調度的功能.
目前非實時進程的調度策略比較簡單, 因為實時進程值只要求盡可能快的被響應, 基於優先級, 每個進程根據它重要程度的不同被賦予不同的優先級，調度器在每次調度時, 總選擇優先級最高的進程開始執行. 低優先級不可能搶占高優先級, 因此FIFO或者Round Robin的調度策略即可滿足實時進程調度的需求.
但是普通進程的調度策略就比較麻煩了, 因為普通進程不能簡單的只看優先級, 必須公平的占有CPU, 否則很容易出現進程饑餓, 這種情況下用戶會感覺操作系統很卡, 響應總是很慢，因此在linux調度器的發展歷程中經過了多次重大變動, linux總是希望尋找一個最接近於完美的調度策略來公平快速的調度進程.

linux調度器的演變

一開始的調度器是復雜度為O(n)O(n)的始調度算法(實際上每次會遍歷所有任務，所以復雜度為O(n)), 這個算法的缺點是當內核中有很多任務時，調度器本身就會耗費不少時間，所以，從linux2.5開始引入赫赫有名的O(1)O(1)調度器
然而，linux是集全球很多程序員的聰明才智而發展起來的超級內核，沒有最好，只有更好，在O(1)O(1)調度器風光了沒幾天就又被另一個更優秀的調度器取代了，它就是CFS調度器Completely Fair Scheduler. 這個也是在2.6內核中引入的，具體為2.6.23，即從此版本開始，內核使用CFS作為它的默認調度器，O(1)O(1)調度器被拋棄了。
所以完全有理由相信，後續如果再會出現一個更優秀的調度器，CFS也不會幸免。因為linux只要最好的那個。

O(n)O(n)的始調度算法

Linux2.4之前的內核調度器

早期的Linux進程調度器使用了最低的設計，它顯然不關注具有很多處理器的大型架構，更不用說是超線程了。
Linux調度器使用了環形隊列用於可運行的任務管理, 使用循環調度策略.
此調度器添加和刪除進程效率很高（具有保護結構的鎖）。簡而言之，該調度器並不復雜但是簡單快捷.
Linux版本2.2引入了調度類的概念，允許針對實時任務、非搶占式任務、非實時任務的調度策略。調度器還包括對稱多處理 (SMP) 支持。

Linux2.4的調度器

概述

在Linux2.4.18中(linux-2.5)之前的內核, 當很多任務都處於活動狀態時, 調度器有很明顯的限制. 這是由於調度器是使用一個復雜度為O(n)O(n)的算法實現的.
調度器采用基於優先級的設計，這個調度器和Linus在1992年發布的調度器沒有大的區別。該調度器的pick next算法非常簡單：對runqueue中所有進程的優先級進行依次進行比較，選擇最高優先級的進程作為下一個被調度的進程。(Runqueue是Linux 內核中保存所有就緒進程的隊列). pick next用來指從所有候選進程中挑選下一個要被調度的進程的過程。
這種調度算法非常簡單易懂: 在每次進程切換時, 內核掃描可運行進程的鏈表, 計算優先級,然胡選擇”最佳”進程來運行.
在這種調度器中, 調度任務所花費的時間是一個系統中任務個數的函數. 換而言之, 活動的任務越多, 調度任務所花費的時間越長. 在任務負載非常重時, 處理器會因調度消耗掉大量的時間, 用於任務本身的時間就非常少了。因此，這個算法缺乏可伸縮性

詳情

每個進程被創建時都被賦予一個時間片。時鐘中斷遞減當前運行進程的時間片，當進程的時間片被用完時，它必須等待重新賦予時間片才能有機會運行。Linux2.4調度器保證只有當所有RUNNING進程的時間片都被用完之後，才對所有進程重新分配時間片。這段時間被稱為一個epoch。這種設計保證了每個進程都有機會得到執行。每個epoch中，每個進程允許執行到其時間切片用完。如果某個進程沒有使用其所有的時間切片，那麼剩余時間切片的一半將被添加到新時間切片使其在下個epoch中可以執行更長時間。調度器只是迭代進程，應用goodness函數（指標）決定下面執行哪個進程。當然，各種進程對調度的需求並不相同，Linux 2.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中，很多商業的發行版本都采用了這個調度器

O(1)O(1)的調度算法

概述

由於進程優先級的最大值為139，因此MAX_PRIO的最大值取140(具體的是，普通進程使用100到139的優先級，實時進程使用0到99的優先級).
因此，該調度算法為每個優先級都設置一個可運行隊列, 即包含140個可運行狀態的進程鏈表，每一條優先級鏈表上的進程都具有相同的優先級，而不同進程鏈表上的進程都擁有不同的優先級。
除此之外, 還包括一個優先級位圖bitmap。該位圖使用一個位(bit)來代表一個優先級，而140個優先級最少需要5個32位來表示， 因此只需要一個int[5]就可以表示位圖，該位圖中的所有位都被置0，當某個優先級的進程處於可運行狀態時，該優先級所對應的位就被置1。
如果確定了優先級，那麼選取下一個進程就簡單了，只需在queue數組中對應的鏈表上選取一個進程即可。
最後，在早期的內核中，搶占是不可能的；這意味著如果有一個低優先級的任務在執行，高優先級的任務只能等待它完成。

詳情

從名字就可以看出O(1)調度器主要解決了以前版本中的擴展性問題。
O(1)調度算法所花費的時間為常數，與當前系統中的進程個數無關。
此外Linux 2.6內核支持內核態搶占，因此更好地支持了實時進程。
相對於前任，O(1)調度器還更好地區分了交互式進程和批處理式進程。
Linux 2.6內核也支持三種調度策略。其中SCHED_FIFO和SCHED_RR用於實時進程，而SCHED_NORMAL用於普通進程。
O(1)調度器在兩個方面修改了Linux 2.4調度器，一是進程優先級的計算方法；二是pick next算法。
O(1)調度器跟蹤運行隊列中可運行的任務（實際上，每個優先級水平有兩個運行隊列，一個用於活動任務，一個用於過期任務）， 這意味著要確定接下來執行的任務，調度器只需按優先級將下一個任務從特定活動的運行隊列中取出即可。

普通進程的優先級計算

不同類型的進程應該有不同的優先級。每個進程與生俱來（即從父進程那裡繼承而來）都有一個優先級，我們將其稱為靜態優先級。普通進程的靜態優先級范圍從100到139，100為最高優先級，139 為最低優先級，0－99保留給實時進程。當進程用完了時間片後，系統就會為該進程分配新的時間片（即基本時間片），靜態優先級本質上決定了時間片分配的大小。
靜態優先級和基本時間片的關系如下：
靜態優先級<120，基本時間片=max((140-靜態優先級)*20, MIN_TIMESLICE)
靜態優先級>=120，基本時間片=max((140-靜態優先級)*5, MIN_TIMESLICE)
其中MIN_TIMESLICE為系統規定的最小時間片。從該計算公式可以看出，靜態優先級越高（值越低），進程得到的時間片越長。其結果是，優先級高的進程會獲得更長的時間片，而優先級低的進程得到的時間片則較短。進程除了擁有靜態優先級外，還有動態優先級，其取值范圍是100到139。當調度程序選擇新進程運行時就會使用進程的動態優先級，動態優先級和靜態優先級的關系可參考下面的公式：
動態優先級=max(100 , min(靜態優先級 – bonus + 5) , 139)
從上面看出，動態優先級的生成是以靜態優先級為基礎，再加上相應的懲罰或獎勵(bonus)。這個bonus並不是隨機的產生，而是根據進程過去的平均睡眠時間做相應的懲罰或獎勵。
所謂平均睡眠時間（sleep_avg，位於task_struct結構中）就是進程在睡眠狀態所消耗的總時間數，這裡的平均並不是直接對時間求平均數。平均睡眠時間隨著進程的睡眠而增長，隨著進程的運行而減少。因此，平均睡眠時間記錄了進程睡眠和執行的時間，它是用來判斷進程交互性強弱的關鍵數據。如果一個進程的平均睡眠時間很大，那麼它很可能是一個交互性很強的進程。反之，如果一個進程的平均睡眠時間很小，那麼它很可能一直在執行。另外，平均睡眠時間也記錄著進程當前的交互狀態，有很快的反應速度。比如一個進程在某一小段時間交互性很強，那麼sleep_avg就有可能暴漲（當然它不能超過 MAX_SLEEP_AVG），但如果之後都一直處於執行狀態，那麼sleep_avg就又可能一直遞減。理解了平均睡眠時間，那麼bonus的含義也就顯而易見了。交互性強的進程會得到調度程序的獎勵（bonus為正），而那些一直霸占CPU的進程會得到相應的懲罰（bonus為負）。其實bonus相當於平均睡眠時間的縮影，此時只是將sleep_avg調整成bonus數值范圍內的大小。可見平均睡眠時間可以用來衡量進程是否是一個交互式進程。如果滿足下面的公式，進程就被認為是一個交互式進程：
動態優先級≤3*靜態優先級/4 + 28
平均睡眠時間是進程處於等待睡眠狀態下的時間，該值在進程進入睡眠狀態時增加，而進入RUNNING狀態後則減少。該值的更新時機分布在很多內核函數內：時鐘中斷scheduler_tick()；進程創建；進程從TASK_INTERRUPTIBLE狀態喚醒；負載平衡等。

實時進程的優先級計算

實時進程的優先級由sys_sched_setschedule()設置。該值不會動態修改，而且總是比普通進程的優先級高。在進程描述符中用rt_priority域表示。

pick next算法

普通進程的調度選擇算法基於進程的優先級，擁有最高優先級的進程被調度器選中。
2.4中，時間片counter同時也表示了一個進程的優先級。2.6中時間片用任務描述符中的time_slice域表示，而優先級用prio（普通進程）或者rt_priority（實時進程）表示。調度器為每一個CPU維護了兩個進程隊列數組：指向活動運行隊列的active數組和指向過期運行隊列的expire數組。數組中的元素著保存某一優先級的進程隊列指針。系統一共有140個不同的優先級，因此這兩個數組大小都是140。它們是按照先進先出的順序進行服務的。被調度執行的任務都會被添加到各自運行隊列優先級列表的末尾。每個任務都有一個時間片，這取決於系統允許執行這個任務多長時間。運行隊列的前100個優先級列表保留給實時任務使用，後40個用於用戶任務，參見下圖：

當需要選擇當前最高優先級的進程時，2.6調度器不用遍歷整個runqueue，而是直接從active數組中選擇當前最高優先級隊列中的第一個進程。假設當前所有進程中最高優先級為50（換句話說，系統中沒有任何進程的優先級小於50）。則調度器直接讀取 active[49]，得到優先級為50的進程隊列指針。該隊列頭上的第一個進程就是被選中的進程。這種算法的復雜度為O(1)，從而解決了2.4調度器的擴展性問題。為了實現O(1)算法active數組維護了一個由5個32位的字（140個優先級）組成的bitmap，當某個優先級別上有進程被插入列表時，相應的比特位就被置位。 sched_find_first_bit()函數查詢該bitmap，返回當前被置位的最高優先級的數組下標。在上例中sched_find_first_bit函數將返回49。在IA處理器上可以通過bsfl等指令實現。可見查找一個任務來執行所需要的時間並不依賴於活動任務的個數，而是依賴於優先級的數量。這使得 2.6 版本的調度器成為一個復雜度為 O(1) 的過程，因為調度時間既是固定的，而且也不會受到活動任務個數的影響。
為了提高交互式進程的響應時間，O(1)調度器不僅動態地提高該類進程的優先級，還采用以下方法：每次時鐘tick中斷時，進程的時間片(time_slice)被減一。當time_slice為0時，表示當前進程的時間片用完，調度器判斷當前進程的類型，如果是交互式進程或者實時進程，則重置其時間片並重新插入active數組。如果不是交互式進程則從active數組中移到expired數組，並根據上述公式重新計算時間片。這樣實時進程和交互式進程就總能優先獲得CPU。然而這些進程不能始終留在active數組中，否則進入expire數組的進程就會產生饑餓現象。當進程已經占用CPU時間超過一個固定值後，即使它是實時進程或者交互式進程也會被移到expire數組中。當active數組中的所有進程都被移到expire數組中後，調度器交換active數組和expire數組。因此新的active數組又恢復了初始情況，而expire數組為空，從而開始新的一輪調度。
Linux 2.6調度器改進了前任調度器的可擴展性問題，schedule()函數的時間復雜度為O(1)。這取決於兩個改進：
pick next算法借助於active數組，無需遍歷runqueue；
消了定期更新所有進程counter的操作，動態優先級的修改分布在進程切換，時鐘tick中斷以及其它一些內核函數中進行。
O(1)調度器區分交互式進程和批處理進程的算法與以前雖大有改進，但仍然在很多情況下會失效。有一些著名的程序總能讓該調度器性能下降，導致交互式進程反應緩慢。例如fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c等。而且O(1)調度器對NUMA支持也不完善。為了解決這些問題，大量難以維護和閱讀的復雜代碼被加入Linux2.6.0的調度器模塊，雖然很多性能問題因此得到了解決，可是另外一個嚴重問題始終困擾著許多內核開發者，那就是代碼的復雜度問題。很多復雜的代碼難以管理並且對於純粹主義者而言未能體現算法的本質。
為了解決O(1)調度器面臨的問題以及應對其他外部壓力, 需要改變某些東西。這種改變來自Con Kolivas的內核補丁staircase scheduler（樓梯調度算法），以及改進的RSDL（Rotating Staircase Deadline Scheduler）。它為調度器設計提供了一個新的思路。Ingo Molnar在RSDL之後開發了CFS，並最終被2.6.23內核采用。接下來我們開始介紹這些新一代調度器。

Linux 2.6的新一代調度器CFS

樓梯調度算法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數組，從而簡化了代碼。它最重要的意義在於證明了完全公平這個思想的可行性。

RSDL(Rotating Staircase Deadline Scheduler)

RSDL也是由Con Kolivas開發的，它是對SD算法的改進。核心的思想還是”完全公平”。沒有復雜的動態優先級調整策略。RSDL重新引入了expire數組。它為每一個優先級都分配了一個 “組時間配額”，記為Tg；同一優先級的每個進程都擁有同樣的”優先級時間配額”，用Tp表示。當進程用完了自身的Tp時，就下降到下一優先級進程組中。這個過程和SD相同，在RSDL中這個過程叫做minor rotation（次輪詢）。請注意Tp不等於進程的時間片，而是小於進程的時間片。下圖表示了minor rotation。進程從priority1的隊列中一步一步下到priority140之後回到priority2的隊列中，這個過程如下圖左邊所示，然後從priority 2開始再次一步一步下樓，到底後再次反彈到priority3隊列中，如下圖所示。

在SD算法中，處於樓梯底部的低優先級進程必須等待所有的高優先級進程執行完才能獲得CPU。因此低優先級進程的等待時間無法確定。RSDL中，當高優先級進程組用完了它們的Tg(即組時間配額)時，無論該組中是否還有進程Tp尚未用完，所有屬於該組的進程都被強制降低到下一優先級進程組中。這樣低優先級任務就可以在一個可以預計的未來得到調度。從而改善了調度的公平性。這就是RSDL中Deadline代表的含義。
進程用完了自己的時間片time_slice時（下圖中T2），將放入expire數組指向的對應初始優先級隊列中(priority 1)。

當active數組為空，或者所有的進程都降低到最低優先級時就會觸發主輪詢major rotation。Major rotation交換active數組和expire數組，所有進程都恢復到初始狀態，再一次從新開始minor rotation的過程。
RSDL對交互式進程的支持：和SD同樣的道理，交互式進程在睡眠時間時，它所有的競爭者都因為minor rotation而降到了低優先級進程隊列中。當它重新進入RUNNING狀態時，就獲得了相對較高的優先級，從而能被迅速響應。

完全公平的調度器CFS

CFS是最終被內核采納的調度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區分交互式進程。它將所有的進程都統一對待，這就是公平的含義。CFS的算法和實現都相當簡單，眾多的測試表明其性能也非常優越。
按照作者Ingo Molnar的說法（參考Documentation/scheduler/sched-design-CFS.txt），
CFS百分之八十的工作可以用一句話概括：CFS在真實的硬件上模擬了完全理想的多任務處理器。在真空的硬件上，同一時刻我們只能運行單個進程，因此當一個進程占用CPU時，其它進程就必須等待，這就產生了不公平。但是在“完全理想的多任務處理器 “下，每個進程都能同時獲得CPU的執行時間，即並行地每個進程占1/nr_running的時間。例如當系統中有兩個進程時，CPU的計算時間被分成兩份，每個進程獲得50%。假設runqueue中有n個進程，當前進程運行了10ms。在“完全理想的多任務處理器”中，10ms應該平分給n個進程(不考慮各個進程的nice值)，因此當前進程應得的時間是(10/n)ms，但是它卻運行了10ms。所以CFS將懲罰當前進程，使其它進程能夠在下次調度時盡可能取代當前進程。最終實現所有進程的公平調度。
與之前的Linux調度器不同，CFS沒有將任務維護在鏈表式的運行隊列中，它拋棄了active/expire數組，而是對每個CPU維護一個以時間為順序的紅黑樹。
該樹方法能夠良好運行的原因在於：
紅黑樹可以始終保持平衡，這意味著樹上沒有路徑比任何其他路徑長兩倍以上。
由於紅黑樹是二叉樹，查找操作的時間復雜度為O(log n)。但是除了最左側查找以外，很難執行其他查找，並且最左側的節點指針始終被緩存。
對於大多數操作（插入、刪除、查找等），紅黑樹的執行時間為O(log n)，而以前的調度程序通過具有固定優先級的優先級數組使用 O(1)。O(log n) 行為具有可測量的延遲，但是對於較大的任務數無關緊要。Molnar在嘗試這種樹方法時，首先對這一點進行了測試。
紅黑樹可通過內部存儲實現，即不需要使用外部分配即可對數據結構進行維護。
要實現平衡，CFS使用”虛擬運行時”表示某個任務的時間量。任務的虛擬運行時越小，意味著任務被允許訪問服務器的時間越短，其對處理器的需求越高。CFS還包含睡眠公平概念以便確保那些目前沒有運行的任務（例如，等待 I/O）在其最終需要時獲得相當份額的處理器。

CFS如何實現pick next

下圖是一個紅黑樹的例子。

所有可運行的任務通過不斷地插入操作最終都存儲在以時間為順序的紅黑樹中（由 sched_entity 對象表示），對處理器需求最多的任務（最低虛擬運行時）存儲在樹的左側，處理器需求最少的任務（最高虛擬運行時）存儲在樹的右側。 為了公平，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(LogN)O(LogN)

調度器管理器

為了支持實時進程，CFS提供了調度器模塊管理器。各種不同的調度器算法都可以作為一個模塊注冊到該管理器中。不同的進程可以選擇使用不同的調度器模塊。2.6.23中，CFS實現了兩個調度算法，CFS算法模塊和實時調度模塊。對應實時進程，將使用實時調度模塊。對應普通進程則使用CFS算法。CFS 調度模塊（在 kernel/sched_fair.c 中實現）用於以下調度策略：SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。對於 SCHED_RR 和 SCHED_FIFO 策略，將使用實時調度模塊（該模塊在 kernel/sched_rt.c 中實現）。

CFS組調度

CFS組調度（在 2.6.24 內核中引入）是另一種為調度帶來公平性的方式，尤其是在處理產生很多其他任務的任務時。 假設一個產生了很多任務的服務器要並行化進入的連接（HTTP 服務器的典型架構）。不是所有任務都會被統一公平對待， CFS 引入了組來處理這種行為。產生任務的服務器進程在整個組中（在一個層次結構中）共享它們的虛擬運行時，而單個任務維持其自己獨立的虛擬運行時。這樣單個任務會收到與組大致相同的調度時間。您會發現 /proc 接口用於管理進程層次結構，讓您對組的形成方式有完全的控制。使用此配置，您可以跨用戶、跨進程或其變體分配公平性。
考慮一個兩用戶示例，用戶 A 和用戶 B 在一台機器上運行作業。用戶 A 只有兩個作業正在運行，而用戶 B 正在運行 48 個作業。組調度使 CFS 能夠對用戶 A 和用戶 B 進行公平調度，而不是對系統中運行的 50 個作業進行公平調度。每個用戶各擁有 50% 的 CPU 使用。用戶 B 使用自己 50% 的 CPU 分配運行他的 48 個作業，而不會占用屬於用戶 A 的另外 50% 的 CPU 分配。
更多CFS的信息, 請參照
http://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html?ca=drs-cn-0125
另外內核文檔sched-design-CFS.txt中也有介紹。