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?操作系統的一款衍生產品中。

?