Linux進程排程策略（CFS排程）詳解

Linux 進程排程有一個有趣歷史。在 2.5 版本之前，Linux 核心採用傳統 UNIX 排程演算法。然而，由於這個演算法並沒有考慮 SMP 系統，因此它並不足夠支援 SMP 系統。此外，當有大量的可執行進程時，系統效能表現欠佳。

在核心 V2.5 中，排程程式進行了大改，採用了稱為 O(1) 的排程演算法，它的執行時間為常數，與系統內任務數量無關。O(1) 排程程式也增加了對 SMP 系統的支援，包括處理器親和性和處理器間的負載平衡。然而，在實踐中，雖然在 SMP 系統上 O(1) 排程程式具有出色的效能，但是在許多桌面計算機系統上互動進程的響應時間卻欠佳。

在核心 V2.6 的開發中，排程程式再次修改；在核心 V2.6.23 的發布中，完全公平排程程式（CFS）成為預設的 Linux 排程演算法。

Linux 系統的排程基於排程類。每個類都有一個特定優先順序。核心針對不同的排程類，採用不同的排程演算法，以便滿足系統與進程的需要。例如，用於 Linux 伺服器的排程準則，也許不同於移動裝置的。為了確定應執行哪個進程，排程程式從最高優先順序排程類中選擇具有最高優先順序的任務。

Linux 標準核心實現兩個排程類：採用 CFS 排程演算法的預設排程類和實時排程類。這裡分別討論這些。當然，新排程類也可新增。

CFS 排程程式並不採用嚴格規則來為一個優先順序分配某個長度的時間片，而是為每個任務分配一定比例的 CPU 處理時間。每個任務分配的具體比例是根據友好值來計算的。友好值的範圍從 -20 到 +19，數值較低的友好值表示較高的相對優先順序。具有較低友好值的任務，與具有較高友好值的任務相比，會得到更高比例的處理器處理時間。預設友好值為 0。

友好一詞源自如下想法：當一個任務增加了它的友好值，如從 0 至 +10，該任務通過降低優先順序，進而對其他任務更加友好。

CFS 沒有使用離散的時間片，而是採用目標延遲，這是每個可執行任務應當執行一次的時間間隔。根據目標延遲，按比例分配 CPU 時間。除了預設值和最小值外，隨著系統內的活動任務數量超過了一定閾值，目標延遲可以增加。

CFS 排程程式沒有直接分配優先順序。相反，它通過每個任務的變數 vruntime 以便維護虛擬執行時間，進而記錄每個任務執行多久。虛擬執行時間與基於任務優先順序的衰減因子有關，更低優先順序的任務比更高優先順序的任務具有更高衰減速率。對於正常優先順序的任務（友好值為 0），虛擬執行時間與實際物理執行時間是相同的。

因此，如果一個預設優先順序的任務執行 200ms，則它的虛擬執行時間也為 200ms。然而，如果一個較低優先順序的任務執行 200ms，則它的虛擬執行時間將大於 200ms。同樣，如果一個更高優先順序的任務執行 200ms，則它的虛擬執行時間將小於 200ms。當決定下步執行哪個任務時，排程程式只需選擇具有最小虛擬執行時間的任務。此外，一個更高優先順序的任務如成為可執行，就會搶占低優先順序任務。

下面分析一下 CFS 排程程式是如何工作的。假設有兩個任務，它們具有相同的友好值。一個任務是 I/O 密集型而另一個為 CPU 密集型。通常，I/O 密集型任務在執行很短時間後就會阻塞以便等待更多的 I/O；而 CPU 密集型任務只要有在處理器上執行的機會，就會用完它的時間片。

因此，I/O 密集型任務的虛擬執行時間最終將會小於 CPU 密集型任務的，從而使得 I/O 密集型任務具有更高的優先順序。這時，如果 CPU 密集型任務在執行，而 I/O 密集型任務變得有資格可以執行（如該任務所等待的 I/O 已成為可用)，那麼 I/O 密集型任務就會搶占 CPU 密集型任務。

Linux 也實現了實時排程。採用 SCHED_FIFO 或 SCHED_RR 實時策略來排程的任何任務，與普通（非實時的）任務相比，具有更高的優先順序。

Linux 採用兩個單獨的優先順序範圍，一個用於實時任務，另一個用於正常任務。實時任務分配的靜態優先順序為 0?99，而正常任務分配的優先順序為 100?139。

這兩個值域合併成為一個全域性的優先順序方案，其中較低數值表明較高的優先順序。正常任務，根據它們的友好值，分配一個優先順序；這裡 -20 的友好值對映到優先順序 100，而 +19 的友好值對映到 139。圖 1 顯示了這個方案。

---