調度器的主要工作是在所有 RUNNING 進程中選擇最合適的一個。作為一個通用操作系統，Linux 調度器將進程分為了三類：
交互進程：此類進程有大量的人機交互，因此進程不斷地處於睡眠狀態，等待用戶輸入。典型的應用比如編輯器 vi。此類進程對系統響應時間要求比較高，否則用戶會感覺系統反應遲緩。
批處理進程：此類進程不需要人機交互，在後台運行，需要占用大量的系統資源。但是能夠忍受響應延遲。比如編譯器。
實時進程：實時對調度延遲的要求最高，這些進程往往執行非常重要的操作，要求立即響應並執行。比如視頻播放軟件或飛機飛行控制系統。對於實時進程，采用 FIFO 或者 Round Robin 的調度策略。對於普通進程，則需要區分交互式和批處理式的不同。
注：傳統 Linux 調度器提高交互式應用的優先級，使得它們能更快地被調度。而 CFS 和 RSDL 等新的調度器的核心思想是“完全公平”。這個設計理念不僅大大簡化了調度器的代碼復雜度，還對各種調度需求的提供了更完美的支持。
linux2.4調度器發展史
Linux2.4.18 中使用的調度器采用基於優先級的設計，這個調度器和 Linus 在 1992 年發布的調度器沒有大的區別。該調度器的 pick next 算法非常簡單：對 runqueue 中所有進程的優先級進行依次進行比較，選擇最高優先級的進程作為下一個被調度的進程。(Runqueue 是 Linux 內核中保存所有就緒進程的隊列) 。術語 pick next 用來指從所有候選進程中挑選下一個要被調度的進程的過程。
每個進程被創建時都被賦予一個時間片。時鐘中斷遞減當前運行進程的時間片，當進程的時間片被用完時，它必須等待重新賦予時間片才能有機會運行。Linux2.4 調度器保證只有當所有 RUNNING 進程的時間片都被用完之後，才對所有進程重新分配時間片。這段時間被稱為一個 epoch。這種設計保證了每個進程都有機會得到執行。
實時進程：實時進程的優先級是靜態設定的，而且始終大於普通進程的優先級。因此只有當 runqueue 中沒有實時進程的情況下，普通進程才能夠獲得調度。實時進程采用兩種調度策略：SCHED_FIFO 和 SCHED_RR。
普通進程：對於普通進程，調度器傾向於提高交互式進程的優先級，因為它們需要快速的用戶響應。普通進程的優先級主要由進程描述符中的 Counter 字段決定 (還要加上 nice 設定的靜態優先級) 。
注：當所有 RUNNING 進程的時間片被用完之後，調度器將重新計算所有進程的 counter 值，所有進程不僅包括 RUNNING 進程，也包括處於睡眠狀態的進程。處於睡眠狀態的進程的 counter 本來就沒有用完，在重新計算時，他們的 counter 值會加上這些原來未用完的部分，從而提高了它們的優先級。交互式進程經常因等待用戶輸入而處於睡眠狀態，當它們重新被喚醒並進入 runqueue 時，就會優先於其它進程而獲得 CPU。從用戶角度來看，交互式進程的響應速度就提高了。
這個調度器存在以下缺點：
可擴展性不好：調度器選擇進程時需要遍歷整個 runqueue 從中選出最佳人選，因此該算法的執行時間與進程數成正比。另外每次重新計算 counter 所花費的時間也會隨著系統中進程數的增加而線性增長，當進程數很大時，更新 counter 操作的代價會非常高，導致系統整體的性能下降。
高負載系統上的調度性能比較低：2.4的調度器預分配給每個進程的時間片比較大，因此在高負載的服務器上，該調度器的效率比較低，因為平均每個進程的等待時間於該時間片的大小成正比。
交互式進程的優化並不完善：Linux2.4識別交互式進程的原理基於以下假設，即交互式進程比批處理進程更頻繁地處於SUSPENDED狀態。然而現實情況往往並非如此，有些批處理進程雖然沒有用戶交互，但是也會頻繁地進行IO操作，比如一個數據庫引擎在處理查詢時會經常地進行磁盤IO，雖然它們並不需要快速地用戶響應，還是被提高了優先級。當系統中這類進程的負載較重時，會影響真正的交互式進程的響應時間。
對實時進程的支持不夠：Linux2.4內核是非搶占的，當進程處於內核態時不會發生搶占，這對於真正的實時應用是不能接受的。
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算法。Linux2.6調度器改進了前任調度器的可擴展性問題，schedule()函數的時間復雜度為O(1)。這取決於兩個改進：
一．Pick next算法借助於active數組，無需遍歷runqueue；
二．取消了定期更新所有進程counter的操作，動態優先級的修改分布在進程切換，時鐘tick中斷以及其它一些內核函數中進行。
O(1)調度器區分交互式進程和批處理進程的算法與以前雖大有改進，但仍然在很多情況下會失效。有一些著名的程序總能讓該調度器性能下降，導致交互式進程反應緩慢：
樓梯算法SD
樓梯算法(SD)在思路上和O(1)算法有很大不同，它拋棄了動態優先級的概念。而采用了一種完全公平的思路。前任算法的主要復雜性來自動態優先級的計算，調度器根據平均睡眠時間和一些很難理解的經驗公式來修正進程的優先級以及區分交互式進程。這樣的代碼很難閱讀和維護。
樓梯算法思路簡單，但是實驗證明它對應交互式進程的響應比其前任更好，而且極大地簡化了代碼。和O(1)算法一樣，樓梯算法也同樣為每一個優先級維護一個進程列表，並將這些列表組織在active數組中。當選取下一個被調度進程時，SD算法也同樣從active數組中直接讀取。與O(1)算法不同在於，當進程用完了自己的時間片後，並不是被移到expire數組中。而是被加入active數組的低一優先級列表中，即將其降低一個級別。不過請注意這裡只是將該任務插入低一級優先級任務列表中，任務本身的優先級並沒有改變。當時間片再次用完，任務被再次放入更低一級優先級任務隊列中。就象一部樓梯，任務每次用完了自己的時間片之後就下一級樓梯。
從實現角度看，SD基本上還是沿用了O(1)的整體框架，只是刪除了O(1)調度器中動態修改優先級的復雜代碼；還淘汰了expire數組，從而簡化了代碼。它最重要的意義在於證明了完全公平這個思想的可行性。
RSDL算法
RSDL重新引入了expire數組。它為每一個優先級都分配了一個 “組時間配額”， 我們將組時間配額標記為Tg；同一優先級的每個進程都擁有同樣的"優先級時間配額"本文中用Tp表示，以便於後續描述。當進程用完了自身的Tp時，就下降到下一優先級進程組中。這個過程和SD相同，在RSDL中這個過程叫做minor rotation。請注意Tp不等於進程的時間片，而是小於進程的時間片。下圖表示了minor rotation。進程從priority1的隊列中一步一步下到priority140之後回到priority2的隊列中，這個過程如下圖左邊所示，然後從priority 2開始再次一步一步下樓，到底後再次反彈到priority3隊列中，如圖1所示。
查看本欄目更多精彩內容：http://www.bianceng.cn/OS/unix/
在SD算法中，處於樓梯底部的低優先級進程必須等待所有的高優先級進程執行完才能獲得CPU。因此低優先級進程的等待時間無法確定。RSDL中，當高優先級進程組用完了它們的Tg(即組時間配額)時，無論該組中是否還有進程Tp尚未用完，所有屬於該組的進程都被強制降低到下一優先級進程組中。這樣低優先級任務就可以在一個可以預計的未來得到調度。從而改善了調度的公平性。這就是RSDL中Deadline代表的含義。進程用完了自己的時間片time_slice時（下圖中T2），將放入expire數組中它初始的優先級隊列中(priority 1)。
當active數組為空，或者所有的進程都降低到最低優先級時就會觸發major rotation：。Major rotation交換active數組和expire數組，所有進程都恢復到初始狀態，再一次從新開始minor rotation的過程。
CFS算法
CFS是最終被內核采納的調度器。它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區分交互式進程。它將所有的進程都統一對待，這就是公平的含義。CFS的算法和實現都相當簡單，眾多的測試表明其性能也非常優越。
按照作者Ingo Molnar的說法："CFS百分之八十的工作可以用一句話概括：CFS在真實的硬件上模擬了完全理想的多任務處理器"。在“完全理想的多任務處理器“下，每個進程都能同時獲得CPU的執行時間。當系統中有兩個進程時，CPU的計算時間被分成兩份，每個進程獲得50%。然而在實際的硬件上，當一個進程占用CPU時，其它進程就必須等待。這就產生了不公平。
CFS對以前的調度器進行了很大改動。用紅黑樹代替優先級數組；用完全公平的策略代替動態優先級策略；引入了模塊管理器；它修改了原來Linux2.6.0調度器模塊70%的代碼。結構更簡單靈活，算法適應性更高。相比於RSDL，雖然都基於完全公平的原理，但是它們的實現完全不同。相比之下，CFS更加清晰簡單，有更好的擴展性。
CFS還有一個重要特點，即調度粒度小。CFS之前的調度器中，除了進程調用了某些阻塞函數而主動參與調度之外，每個進程都只有在用完了時間片或者屬於自己的時間配額之後才被搶占。而CFS則在每次tick都進行檢查，如果當前進程不再處於紅黑樹的左邊，就被搶占。在高負載的服務器上，通過調整調度粒度能夠獲得更好的調度性能。
