C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:546

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 顯示了這個方案。

Linux系統的調度優先級
圖 1 Linux系統的調度優先級

CFS 性能

Linux CFS 調度程序釆用高效算法,以便選擇運行下個任務。每個可運行的任務放置在紅黑樹上(這是一種平衡的、二分搜索樹,它的鍵是基于虛擬運行時間的)。這種樹如下圖所示:

紅黑樹
圖 2 紅黑樹
 
當一個任務變成可運行時,它被添加到樹上。當一個任務變成不可運行時(例如,當阻塞等待 I/O 時),它從樹上被刪除。一般來說,得到較少處理時間的任務(虛擬運行時間較小)會偏向樹的左側;得到較多處理時間的任務會偏向樹的右側。

根據二分搜索樹的性質,最左側的結點有最小的鍵值;從 CFS 調度程序角度而言,這也是具有最高優先級的任務。由于紅黑樹是平衡的,找到最左側結點會需要 O(lgN) 操作(這里 N 為樹內結點總數)。不過,為高效起見,Linux 調度程序將這個值緩存在變量 rb_leftmost 中,從而確定哪個任務運行只需檢索緩存的值。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo