Linux CFS調度算法分析

簡巖

摘要：一個操作系統的核心是進程調度。那么操作系統最重要的程序之一則是進程調度程序，同時進程調度程序也是多任務操作系統執行頻度最高的一部分，操作系統的整體性能也決定于進程調度程序的性能。本文剖析了從O(1)算法到CFS算法的演變。最后用測試工具對CFS的穩定性和計算速度進行了分析。

關鍵詞：Linux調度O(1)CFS調度器紅黑樹

1 linux進程調度的概述

所謂進程調度就是指操作系統正確的匹配CPU時間之后來準確的執行等待中的進程。怎樣從若干個可運行的進程里面找到其中最優先的進程執行的同時又能保證響應時間短、吞吐量高是進程調度的核心所在。進程調度有何時啟動調度器和調度器執行什么調度算法兩部分。

進程調度的要求就是吞吐量大、響應時間快、周轉時間短以及效率高。由進程的響應時間Linux內核可以把進程分為三類：實時進程、批處理進程和交互進程。根據這三類進程內核又產生了三種不同的調度方法：先進先出策略（SCHED_FIFD）、輪轉策略（SCHED_RR）和適合交互分時的程序（SCHED_OTHER）。

2 進程調度算法

①當CPU運行進程時，調度是被禁止的；只有當CPU處于無進程運行時，可以進入調度。

②當準備隊列空閑時，執行缺省的idle-task、進程。

③當準備隊列非空閑時，執行的進程需要調度器在準備隊列中挑選出來。這時，goodness（）函數將會從調度器在準備隊列中挑選出來的進程中計算其權值，只有權值最大才能有執行的優先級。

④如果經過goodness（）函數計算之后每個進程的權值均是0，則說明CPU所提供給實時進程的準備隊列中進程的時間片全部用光了，需要進行重置之后返回步驟①，繼續執行調度。

⑤當實時進程都執行完成之后，CPU將對普通進程開始支持。當每一個普通進程的權值均是0時，則說明CPU所提供給普通進程的準備隊列中進程的時間片全部用光了，需要進行重置之后返回步驟①，繼續執行調度。

3 linux從O(1)調度器到CFS調度器

3.1 O(1)調度器

在Linux新版本Linux2.6.22中，其內核采用的是O（1）調度器，其不僅僅能夠支持SMP并且可以確保系統的負載和處理器的數目如何變化，其判斷相對應的任務所匹配CPU所利用的時間是不變的。

有2種不同的任務是O（1）調度器的分內工作：

①計算動態任務優先級。利用公式dynamicpriority=max（100，min（staticpriority-bonus+5,139））進行計算。

②當擁有最高優先級的進程執行過程中，選擇出下一個需要進行執行的進程。CPU利用調度器對所有進程進行了任務排隊：expired數組與active數組。其數組中的某一元素寄存著該任務隊列某一優先級的指針，如果需要判斷下一個執行的進程時，并不需要將所有的隊列進行遍歷，只需要在active數組排列好的隊列中直接選擇優先級最高的進程進行執行。上述方法的復雜度是O（1）。

為了讓交互式任務的響應速度變得更快，任何一次時鐘中斷里，處于執行的任務的時間片減一，如果時間片是O的時候，將對其類型進行判斷，若是交互式任務，需要將時間片進行重置然后將active數組再次插入其中；若不是交互式任務，需要把active數組轉到expired數組中，如此便可以讓CPU優先被交互式任務所使用。當然，并不能夠將進城長期的放在active數組里面，當CPU被交互式任務占用達到了一定的數值時，將會把任務轉到expired數組中去。如果active數組處于空的狀態時，則將兩個數組進行互換，從而執行下一輪調度。

O（1）調度器的優點已經顯而易見了，與此同時其算法也存在一些不可避免的缺陷，如執行導交互式任務的時候反應速度并不理想。多任務隊列和動態優先級是O（1）調度器所應用的相對繁瑣的方法，這樣就迫使了調度器較為繁瑣以及對代碼維護的時候難度非常之大。此外，在實際使用的時候發現，相對于在類似于服務器等不存在較大的交互性應用需求的時候，在桌面應用這種對交互性要求很高的環境下，O（1）調度器的效果表現非常不理想。基于這種缺點，Ingo Molnar研發了新的完全公平調度器 (Completely Fair Scheduler，CFS)，此款調度器與O（1）調度器的框架完全不同，在Linux2.6.23版本中，就將CFS作為默認調度器進行使用。

3.2 CFS 調度器

3.2.1 算法的主要思想

CFS并沒有采用以往的將進程進行排列分組以及進行動態的優先級分類，也沒有采用睡眠時間的概念，同時也沒有將任務分為交互任務和其他，CFS則是引入了一個新的概念——紅黑樹；所謂紅黑樹就利用時間來計算一個鍵值從而來選擇下一個執行進程，進而利用全部進程所對CPU所利用的時間狀態來調度任務。全部的準備狀態中的進程被賦予的鍵值數值被放在紅黑樹的葉子節點上，按照鍵值從小到大一次排列在從左到右。在任何一個調度點上，調度器會從紅黑樹排列好的進程從左至右的對CPU進行進程的調度，這種執行的復雜度為O（log2N）。

在所有的時鐘中斷上面，其首要的任務是更新調度信息，其次是對紅黑樹上的排列好的進程進行進一步的調整。當檢測到正在執行的進程并不是最左邊的進程時，將對其進行need_resched標記，當執行中斷返回的時候就要利用scheduler_tick（）來完成對進程的切換，如果沒有這個過程，CPU將會被一直占用。

3.2.2 紅黑樹

CFS依靠進程的虛擬運行時間作為其變量，進而使用紅黑樹把每一個準備好執行的進程排列成“runqueue”。CFS將之前一直運用的FIFO以及Hash映射形式的線性“qunqueue”徹底移除，每一個runqueue都是利用紅黑樹來進行組成的。

紅黑樹的特點也是非常明顯的：首先，紅黑樹上的每一個節點都能夠保證一項規律，那就是該節點的左邊節點永遠小于該幾點，相對的右邊的節點就大于該節點，這就是之所以紅黑樹從左至右依次增大的效果；其次，紅黑樹上分布的所有節點都是均勻的，絕對不會出現不均勻的情況；最后，其操作代價非常低，插入、查找以及刪除的代價都是0（logn）。在CFS實際的應用中，表現最為突出的還是第一條特點。

該算法中，每一個節點都作為virtual_runtime鍵值植入到紅黑樹里面，當有進程需要進行執行的時候，將鍵值進行更新之后植入到紅黑樹，之后從左至右的一次進行執行進程。

當CFS進行調度的過程中，其復雜度是O（logn），可是因為CFS具有實現代價低的特點，實際執行的過程中，反應速度反而快了很多。此外，Linux中的CFS還賦予了很多可操作性的功能，像可以進行靈活配置的調整選項等，這樣可以讓用戶在任何情況之下都能夠得到最好的性能體驗。

3.2.3 源代碼分析

我們參考內核2. 6. 24 源代碼中的sched. c 和sched_fair. c來分析:

Scheduler_tick()函數是Sched.c中的一個函數，Scheduler_tick()函數改變當前的時間值與clock 值后CPU會刷新當前的負載情況，最后調用sched_class函數和task_tick( ) 函數。

static void task_tick_fair(struct rq* rq，struct task_struct * curr)

{

struct cfs_rq* cfs_rq;

struct sched_entity* se = ＆curr － > se;

for_each_sched_entity(se) {

cfs_rq = cfs_rq_of(se);

entity_tick(cfs_rq，se);

}

}

task_tick_fair函數的目的是使待調度任務執行entity_tick()函數:

static void entity_tick( struct cfs_rq * cfs_rq，struct sched _entity *

curr)

用函數dequeue_entity( )與enqueue_entity( )的主要目的是在紅黑樹里把任務刪除在插入到紅黑樹里用來調整任務在紅黑樹里的位置。_pick_next_entity()函數是返回到CFS中紅黑樹的最左邊的葉子節點，如果發現這個節點它不是當前的任務，那么就調用_check_preempt_

curr_fair( ) 設置調度標志，當中斷返回時就會調用schedule_tick() 進行調度，替換當前任務。

參考文獻：

[1]杜慧江.Linux內核2.6.24的CFS調度器分析[J].計算機應用與軟件，2010(2).

[2]馮宇.Linux進程調度算法分析[J].計算機與現代化，2009(6).

[3]張永選.Linux 2.6 內核調度機制剖析與改進[J].計算機系統應用，2009(11).

endprint