本文將回顧一下 Linux 2.6 的任務調度器及其最重要的一些屬性。在深入介紹調度器的詳細信息之前，讓我們先來理解一下調度器的基本目標。
什麼是調度器？
通常來說，操作系統是應用程序和可用資源之間的媒介。典型的資源有內存和物理設備。但是 CPU 也可以認為是一個資源，調度器可以臨時分配一個任務在上面執行（單位是時間片）。調度器使得我們同時執行多個程序成為可能，因此可以與具有各種需求的用戶共享 CPU。
調度器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調度器還需要面對一些互相沖突的目標，例如既要為關鍵實時任務最小化響應時間，又要最大限度地提高 CPU 的總體利用率。下面我們來看一下 Linux 2.6 調度程序是如何實現這些目標的，並與以前的調度器進行比較。
早期 Linux 調度器的問題
O-notation 的重要性O-notation 可以告訴我們一個算法會占用多少時間。一個 O(n) 算法所需要的時間依賴於輸入的多少（與 n 是線性關系），而 O(n^2) 則是輸入數量的平方。O(1) 與輸入無關，可以在固定的時間內完成操作。
在 2.6 版本的內核之前，當很多任務都處於活動狀態時，調度器有很明顯的限制。這是由於調度器是使用一個復雜度為 O(n) 的算法實現的。在這種調度器中，調度任務所花費的時間是一個系統中任務個數的函數。換而言之，活動的任務越多，調度任務所花費的時間越長。在任務負載非常重時，處理器會因調度消耗掉大量的時間，用於任務本身的時間就非常少了。因此，這個算法缺乏可伸縮性。
在對稱多處理系統（SMP）中，2.6 版本之前的調度器對所有的處理器都使用一個運行隊列。這意味著一個任務可以在任何處理器上進行調度 —— 這對於負載均衡來說是好事，但是對於內存緩存來說卻是個災難。例如，假設一個任務正在 CPU-1 上執行，其數據在這個處理器的緩存中。如果這個任務被調度到 CPU-2 上執行，那麼數據就需要先在 CPU-1 使其無效，並將其放到 CPU-2 的緩存中。
以前的調度器還使用了一個運行隊列鎖；因此在 SMP 系統中，選擇一個任務執行就會阻礙其他處理器操作這個運行隊列。結果是空閒處理器只能等待這個處理器釋放出運行隊列鎖，這樣會造成效率的降低。
最後，在早期的內核中，搶占是不可能的；這意味著如果有一個低優先級的任務在執行，高優先級的任務只能等待它完成。
Linux 2.6 調度器簡介
2.6 版本的調度器是由 Ingo Molnar 設計並實現的。Ingo 從 1995 年開始就一直參與 Linux 內核的開發。他編寫這個新調度器的動機是為喚醒、上下文切換和定時器中斷開銷建立一個完全 O(1) 的調度器。觸發對新調度器的需求的一個問題是 Java? 虛擬機（JVM）的使用。Java 編程模型使用了很多執行線程，在 O(n) 調度器中這會產生很多調度負載。O(1) 調度器在這種高負載的情況下並不會受到太多影響，因此 JVM 可以有效地執行。
2.6 版本的調度器解決了以前調度器中發現的 3 個主要問題（O(n) 和 SMP 可伸縮性的問題），還解決了其他一些問題。現在我們將開始探索一下 2.6 版本的調度器的基本設計。
主要的調度結構
首先我們來回顧一下 2.6 版本的調度器結構。每個 CPU 都有一個運行隊列，其中包含了 140 個優先級列表，它們是按照先進先出的順序進行服務的。被調度執行的任務都會被添加到各自運行隊列優先級列表的末尾。每個任務都有一個時間片，這取決於系統允許執行這個任務多長時間。運行隊列的前 100 個優先級列表保留給實時任務使用，後 40 個用於用戶任務（參見圖 1）。我們稍後將來看一下為什麼這種區別非常重要。
圖 1. Linux 2.6 調度器的運行隊列結構
除了 CPU 的運行隊列（稱為活動運行隊列（active runqueue））之外，還有一個過期運行隊列。當活動運行隊列中的一個任務用光自己的時間片之後，它就被移動到過期運行隊列（eXPired runqueue） 中。在移動過程中，會對其時間片重新進行計算（因此會體現其優先級的作用；稍後會更詳細地介紹）。如果活動運行隊列中已經沒有某個給定優先級的任務了，那麼指向活動運行隊列和過期運行隊列的指針就會交換，這樣就可以讓過期優先級列表變成活動優先級的列表。
調度器的工作非常簡單：它在優先級最高的隊列中選擇一個任務來執行。為了使這個過程的效率更高，內核使用了一個位圖來定義給定優先級列表上何時存在任務。因此，在大部分體系架構上，會使用一條 find-first-bit-set 指令在 5 個 32 位的字（140 個優先級）中哪一位的優先級最高。查找一個任務來執行所需要的時間並不依賴於活動任務的個數，而是依賴於優先級的數量。這使得 2.6 版本的調度器成為一個復雜度為 O(1) 的過程，因為調度時間既是固定的，而且也不會受到活動任務個數的影響。
更好地支持 SMP 系統
那麼什麼是 SMP 呢？SMP 是一種體系架構，其中多個 CPU 可以用來同時執行各個任務，它與傳統的非對稱處理系統不同，後者使用一個 CPU 來執行所有的任務。SMP 體系架構對多線程的應用程序非常有益。
盡管優先級調度在 SMP 系統上也可以工作，但是它這種大鎖體系架構意味著當一個 CPU 選擇一個任務進行分發調度時，運行隊列會被這個 CPU 加鎖，其他 CPU 只能等待。2.6 版本的調度器不是使用一個鎖進行調度；相反，它對每個運行隊列都有一個鎖。這樣允許所有的 CPU 都可以對任務進行調度，而不會與其他 CPU 產生競爭。
另外，由於每個處理器都有一個運行隊列，因此任務通常都是與 CPU 密切相關的，可以更好地利用 CPU 的熱緩存。
任務搶占
Linux 2.6 版本調度器的另外一個優點是它允許搶占。這意味著當高優先級的任務准備運行時低優先級的任務就不能執行了。調度器會搶占低優先級的進程，並將這個進程放回其優先級列表中，然後重新進行調度。
但是請等一下，還有更多功能呢！
似乎 2.6 版本調度器的 O(1) 特性和搶占特性還不夠，這個調度器還提供了動態任務優先級和 SMP 負載均衡功能。下面就讓我們來討論一下這些功能都是什麼，以及它們分別提供了哪些優點。
動態任務優先級
為了防止任務獨占 CPU 從而會餓死其他需要訪問 CPU 的任務，Linux 2.6 版本的調度器可以動態修改任務的優先級。這是通過懲罰 CPU 綁定的任務而獎勵 I/O 綁定的任務實現的。I/O 綁定的任務通常使用 CPU 來設置 I/O，然後就睡眠等待 I/O 操作完成。這種行為為其他任務提供了 CPU 的訪問能力。
用戶響應能力更好與用戶進行通信的任務都是交互型的，因此其響應能力應該比非交互式任務更好。由於與用戶的通信（不管是向標准輸出上發送數據，還是通過標准輸入等待輸入數據）都是 I/O 綁定型的，因此提高這些任務的優先級可以獲得更好的交互式響應能力。
由於 I/O 綁定型的任務對於 CPU 訪問來說是無私的，因此其優先級減少（獎勵）最多 5 個優先級。CPU 綁定的任務會通過將其優先級增加最多 5 個優先級進行懲罰。
任務到底是 I/O 綁定的還是 CPU 綁定的，這是根據交互性 原則確定的。任務的交互性指標是根據任務執行所花費的時間與睡眠所花費的時間的對比程度進行計算的。注意，由於 I/O 任務先對 I/O 進行調度，然後再進行睡眠，因此 I/O 綁定的任務會在睡眠和等待 I/O 操作完成上面花費更多的時間。這會提高其交互性指標。
有一點值得注意，優先級的調整只會對用戶任務進行，對於實時任務來說並不會對其優先級進行調整。
SMP 負載均衡
在 SMP 系統中創建任務時，這些任務都被放到一個給定的 CPU 運行隊列中。通常來說，我們無法知道一個任務何時是短期存在的，何時需要長期運行。因此，最初任務到 CPU 的分配可能並不理想。
為了在 CPU 之間維護任務負載的均衡，任務可以重新進行分發：將任務從負載重的 CPU 上移動到負載輕的 CPU 上。Linux 2.6 版本的調度器使用負載均衡（load balancing） 提供了這種功能。每隔 200ms，處理器都會檢查 CPU 的負載是否不均衡；如果不均衡，處理器就會在 CPU 之間進行一次任務均衡操作。
這個過程的一點負面影響是新 CPU 的緩存對於遷移過來的任務來說是冷的（需要將數據讀入緩存中）。
記住 CPU 緩存是一個本地（片上）內存，提供了比系統內存更快的訪問能力。如果一個任務是在某個 CPU 上執行的，與這個任務有關的數據都會被放到這個 CPU 的本地緩存中，這就稱為熱的。如果對於某個任務來說，CPU 的本地緩存中沒有任何數據，那麼這個緩存就稱為冷的。
不幸的是，保持 CPU 繁忙會出現 CPU 緩存對於遷移過來的任務為冷的情況。
挖掘更多潛能
2.6 版本調度器的源代碼都很好地封裝到了 /usr/src/linux/kernel/sched.c 文件中。我們在表 1 中對在這個文件中可以找到的一些有用的函數進行了總結。
表 1. Linux 2.6 調度器的功能 函數名 函數說明 schedule 調度器主函數。調度優先級最高的任務執行。 load_balance 檢查 CPU，查看是否存在不均衡的情況，如果不均衡，就試圖遷移任務。 effective_prio 返回任務的有效優先級（基於靜態策略，但是可以包含任何獎勵和懲罰）。 recalc_task_prio 根據任務的空閒時間確定對任務的獎勵或懲罰。 source_load 適當地計算源 CPU（任務從中遷移出的 CPU）的負載。 target_load 公平地計算目標 CPU（任務可能遷移到的 CPU）的負載。 migration_thread 在 CPU 之間遷移任務的高優先級的系統線程。
運行隊列的結構也可以在 /usr/src/linux/kernel/sched.c 文件中找到。2.6 版本的調度器還可以提供一些統計信息（如果啟用了 CONFIG_SCHEDSTATS）。這些統計信息可以從 /proc 文件系統中的 /proc/schedstat 看到，它為系統中的每個 CPU 都提供了很多數據，包括負載均衡和進程遷移的統計信息。
展望
Linux 2.6 調度器從早先的 Linux 調度器已經跨越了一大步。它極大地改善了最大化利用 CPU 的能力，同時還為用戶提供了很好的響應體驗。搶占和對多處理器體系架構的更好支持使整個系統更接近於多桌面和實時系統都非常有用的操作系統。Linux 2.8 版本的內核現在談論還為時尚早，但是從 2.6 版本的變化中，我們可以期望會有更多的好東西。