轉自http://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html?ca=drs-cn-0125
Linux 排程器簡史
早期的 Linux 排程器使用了最低的設計，它顯然不關注具有很多處理器的大型架構，更不用說是超線程了。1.2 Linux 排程器使用了環形隊列用于可運作的任務管理，使用循環排程政策。 此排程器添加和删除程序效率很高（具有保護結構的鎖）。簡而言之，該排程器并不複雜但是簡單快捷。
Linux 版本 2.2 引入了排程類的概念，允許針對實時任務、非搶占式任務、非實時任務的排程政策。 2.2 排程器還包括對稱多處理 (SMP) 支援。
2.4 核心包含了相對簡單的排程器，按 O(N) 的時間間隔運作（在排程事件期間它會疊代每個任務）。2.4 排程器将時間分割成 epoch，每個 epoch 中，每個任務允許執行到其時間切片用完。如果某個任務沒有使用其所有的時間切片，那麼 剩餘時間切片的一半将被添加到新時間切片使其在下個 epoch 中可以執行更長時間。 排程器隻是疊代任務，應用 goodness 函數（名額）決定下面執行哪個任務。盡管這種方法比較簡單，但是卻比較低效、缺乏可擴充性而且不适合用在實時系統中。它還缺少利用新硬體架構（比如多核處理器）的能力。
早期的 2.6 排程器，叫做 O(1) 排程器，它旨在解決 2.4 排程器存在的問題 — 該排程器不需要疊代整個任務清單來确定要排程的下一個任務（是以得名 O(1)，這意味着它效率更高，擴充性更好）。O(1) 排程器跟蹤運作隊列中可運作的任務（實際上，每個優先級水準有兩個運作隊列 — 一個用于活動任務，一個用于過期任務）， 這意味着要确定接下來執行的任務，排程器隻需按優先級将下一個任務從特定活動的運作隊列中取出即可）。 O(1) 排程器擴充性更好而且包含互動性，提供了大量啟示用于确定任務是受 I/O 限制還是受處理器限制。 但是 O(1) 排程器在核心中很笨拙。需要大量代碼計算啟示，難以管理并且對于純粹主義者而言未能展現算法的本質。
為了解決 O(1) 排程器面臨的問題以及應對其他外部壓力， 需要改變某些東西。這種改變來自 Con Kolivas 的核心更新檔，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 這包含了他在 staircase 排程器方面的早期工作。這些工作的成果就是一個設計簡單的排程器，包含了公平性和界限内延遲。 Kolivas 的排程器吸引了很多人（并且很多人呼籲将其包含在目前的 2.6.21 主流核心中），很顯然排程器的變革即将發生。 Ingo Molnar，O(1) 排程器的創造者，然後圍繞 Kolivas 的一些思想開發了基于 CFS 的排程器。我們來剖析一下 CFS，從較高的層次上看看它是如何運作的。
------------------------------------------------------------------------------------------------------------------------------
CFS 概述
CFS 背後的主要想法是維護為任務提供處理器時間方面的平衡（公平性）。這意味着應給程序配置設定相當數量的處理器。分給某個任務的時間失去平衡時（意味着一個或多個任務相對于其他任務而言未被給予相當數量的時間），應給失去平衡的任務配置設定時間，讓其執行。
要實作平衡，CFS 在叫做虛拟運作時 的地方維持提供給某個任務的時間量。任務的虛拟運作時越小， 意味着任務被允許通路伺服器的時間越短 — 其對處理器的需求越高。CFS 還包含睡眠公平概念以便確定那些目前沒有運作的 任務（例如，等待 I/O）在其最終需要時獲得相當份額的處理器。
但是與之前的 Linux 排程器不同，它沒有将任務維護在運作隊列中，CFS 維護了一個以時間為順序的紅黑樹（參見圖 1）。 紅黑樹 是一個樹，具有很多有趣、有用的屬性。首先，它是自平衡的，這意味着樹上沒有路徑比任何其他路徑長兩倍以上。 第二，樹上的運作按 O(log n) 時間發生（其中 n 是樹中節點的數量）。這意味着您可以快速高效地插入或删除任務。
圖 1. 紅黑樹示例
任務存儲在以時間為順序的紅黑樹中（由
sched_entity
對象表示），對處理器需求最多的任務 （最低虛拟運作時）存儲在樹的左側，處理器需求最少的任務（最高虛拟運作時）存儲在樹的右側。 為了公平，排程器然後選取紅黑樹最左端的節點排程為下一個以便保持公平性。任務通過将其運作時間添加到虛拟運作時， 說明其占用 CPU 的時間，然後如果可運作，再插回到樹中。這樣，樹左側的任務就被給予時間運作了，樹的内容從右側遷移到左側以保持公平。 是以，每個可運作的任務都會追趕其他任務以維持整個可運作任務集合的執行平衡。
------------------------------------------------------------------------------------------------------------------------------
CFS 内部原理
Linux 内的所有任務都由稱為
task_struct
的任務結構表示。該結構（以及其他相關内容）完整地描述了任務并包括了任務的目前狀态、其堆棧、程序辨別、優先級（靜态和動态）等等。您可以在 ./linux/include/linux/sched.h 中找到這些内容以及相關結構。 但是因為不是所有任務都是可運作的，您在
task_struct
中不會發現任何與 CFS 相關的字段。 相反，會建立一個名為
sched_entity
的新結構來跟蹤排程資訊（參見圖 2）。
圖 2. 任務和紅黑樹的結構層次
各種結構的關系如 圖 2 所示。樹的根通過
rb_root
元素通過
cfs_rq
結構（在 ./kernel/sched.c 中）引用。紅黑樹的葉子不包含資訊，但是内部節點代表一個或多個可運作的任務。紅黑樹的每個節點都由
rb_node
表示，它隻包含子引用和父對象的顔色。
rb_node
包含在
sched_entity
結構中，該結構包含
rb_node
引用、負載權重以及各種統計資料。最重要的是，
sched_entity
包含
vruntime
（64 位字段），它表示任務運作的時間量，并作為紅黑樹的索引。 最後，
task_struct
位于頂端，它完整地描述任務并包含
sched_entity
結構。
就 CFS 部分而言，排程函數非常簡單。 在 ./kernel/sched.c 中，您會看到通用
schedule()
函數，它會先搶占目前運作任務（除非它通過
yield()
代碼先搶占自己）。注意 CFS 沒有真正的時間切片概念用于搶占，因為搶占時間是可變的。 目前運作任務（現在被搶占的任務）通過對
put_prev_task
調用（通過排程類）傳回到紅黑樹。 當
schedule
函數開始确定下一個要排程的任務時，它會調用
pick_next_task
函數。此函數也是通用的（在 ./kernel/sched.c 中），但它會通過排程器類調用 CFS 排程器。 CFS 中的
pick_next_task
函數可以在 ./kernel/sched_fair.c（稱為
pick_next_task_fair()
）中找到。 此函數隻是從紅黑樹中擷取最左端的任務并傳回相關
sched_entity
。通過此引用，一個簡單的
task_of()
調用确定傳回的
task_struct
引用。通用排程器最後為此任務提供處理器。
------------------------------------------------------------------------------------------------------------------------------
優先級和 CFS
CFS 不直接使用優先級而是将其用作允許任務執行的時間的衰減系數。 低優先級任務具有更高的衰減系數，而高優先級任務具有較低的衰減系數。 這意味着與高優先級任務相比，低優先級任務允許任務執行的時間消耗得更快。 這是一個絕妙的解決方案，可以避免維護按優先級排程的運作隊列。
CFS 組排程
CFS 另一個有趣的地方是組排程 概念（在 2.6.24 核心中引入）。組排程是另一種為排程帶來公平性的方式，尤其是在處理産生很多其他任務的任務時。 假設一個産生了很多任務的伺服器要并行化進入的連接配接（HTTP 伺服器的典型架構）。不是所有任務都會被統一公平對待， CFS 引入了組來處理這種行為。産生任務的伺服器程序在整個組中（在一個層次結構中）共享它們的虛拟運作時，而單個任務維持其自己獨立的虛拟運作時。這樣單個任務會收到與組大緻相同的排程時間。您會發現 /proc 接口用于管理程序層次結構，讓您對組的形成方式有完全的控制。使用此配置，您可以跨使用者、跨程序或其變體配置設定公平性。
排程類和域
與 CFS 一起引入的是排程類概念（可以回顧 圖 2）。每個任務都屬于一個排程類，這決定了任務将如何排程。 排程類定義一個通用函數集（通過
sched_class
），函數集定義排程器的行為。例如，每個排程器提供一種方式， 添加要排程的任務、調出要運作的下一個任務、提供給排程器等等。每個排程器類都在一對一連接配接的清單中彼此相連，使類可以疊代（例如， 要啟用給定處理器的禁用）。一般結構如圖 3 所示。注意，将任務函數加入隊列或脫離隊列隻需從特定排程結構中加入或移除任務。 函數
pick_next_task
選擇要執行的下一個任務（取決于排程類的具體政策）。
圖 3. 排程類圖形視圖
但是不要忘了排程類是任務結構本身的一部分（參見 圖 2）。這一點簡化了任務的操作，無論其排程類如何。例如， 以下函數用 ./kernel/sched.c 中的新任務搶占目前運作任務（其中
curr
定義了目前運作任務，
rq
代表 CFS 紅黑樹而
p
是下一個要排程的任務）：
static inline void check_preempt( struct rq *rq, struct task_struct *p )
{
rq->curr->sched_class->check_preempt_curr( rq, p );
} 如果此任務正使用公平排程類，則
check_preempt_curr()
将解析為
check_preempt_wakeup()
。 您可以在 ./kernel/sched_rt.c, ./kernel/sched_fair.c 和 ./kernel/sched_idle.c 中檢視這些關系。
排程類是排程發生變化的另一個有趣的地方，但是随着排程域的增加，功能也在增加。 這些域允許您出于負載平衡和隔離的目的将一個或多個處理器按層次關系分組。 一個或多個處理器能夠共享排程政策（并在其之間保持負載平衡）或實作獨立的排程政策進而故意隔離任務。
其他排程器
繼續研究排程，您将發現正在開發中的排程器将會突破性能和擴充性的界限。Con Kolivas 沒有被他的 Linux 經驗羁絆，他開發出了另一個 Linux 排程器，其縮寫為：BFS。該排程器據說在 NUMA 系統以及移動裝置上具有更好的性能， 并且被引入了 Android 作業系統的一款衍生産品中。