任務調度器是任何操作系統的關鍵部分，Linux 在此領域中不斷發展和創新。在內核 2.6.23 中，推出了 Completely Fair Scheduler (CFS)。這款調度器不依賴於運行隊列而是使用紅黑樹 (red-black tree) 實現任務管理。 本文介紹 CFS 的設計思想、其實現及其與之前的 O(1) 調度器相比的優勢。
Linux 調度器是一個頗有壓力但很有趣的課題。一方面它涉及應用 Linux 的使用模型。盡管 Linux 最初開發為桌面操作系統環境，但現在在服務器、微型嵌入式設備、主機和超級計算機中都能發現它。 無疑，這些領域的調度負載有很大差異。另一方面，它要考慮平台方面的技術進步，包括架構（多處理、對稱多線程、非一致內存訪問 [NUMA] 和虛擬化）。 另外，這裡還要考慮交互性（用戶響應能力）和整體公平性之間的平衡。從這些方面很容易看出解決 Linux 中的調度問題有多難。
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) 調度器在內核中很笨拙。需要大量代碼計算啟示，難以管理並且對於純粹主義者而言未能體現算法的本質。
進程與線程Linux 通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共享一定資源（代碼和/或數據）的多個線程。
為了解決 O(1) 調度器面臨的問題以及應對其他外部壓力， 需要改變某些東西。這種改變來自 Con Kolivas 的內核補丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 這包含了他在 staircase 調度器方面的早期工作。這些工作的成果就是一個設計簡單的調度器，包含了公平性和界限內延遲。 Kolivas 的調度器吸引了很多人（並且很多人呼吁將其包含在目前的 2.6.21 主流內核中），很顯然調度器的變革即將發生。 Ingo Molnar，O(1) 調度器的創造者，然後圍繞 Kolivas 的一些思想開發了基於 CFS 的調度器。我們來剖析一下 CFS，從較高的層次上看看它是如何運行的。
