完全公平調度算法分析

朱 旭, 楊 斌, 劉海濤

（西南交通大學信息科學與技術學院,四川成都 610031）

1 引言

進程調度是操作系統的核心功能,其主要目的是合理分配處理器資源。調度算法是任務調度具體的實現方法,一個好的調度算法將實現公平、效率、響應時間、周轉時間、吞吐量等多個調度目標間的平衡。自Linux 2.4調度器使用基于優先級的調度算法以來,Linux2.6開發系列的內核中又經歷了O（1）、RSDL、SD和CFS調度算法。其中CFS是Linux2.6.23內核引入的全新調度算法,相對于O（1）,CFS進行了很大改動,它以完全公平作為調度的核心思想,在性能提升的基礎上大大簡化了代碼,成為內核采用的新一代調度算法。

2 CFS概述

CFS的總體設計可以用一句話來總結:在真實的硬件上模擬“理想的多任務處理器”,使每個進程都盡可能公平的獲得CPU。為此,CFS引入了一個新概念“virtual runtime”,它描述了進程在CPU上的執行時間。在調度的過程中,CFS為了使每個進程都獲得相近的執行時間,總是選取vruntime最小,也就是執行時間最短的進程來運行,以達到各個任務執行時間的平衡。這就是CFS的核心思想,即每個進程都被公平對待。

CFS調度算法相比于O（1）算法有了很大的變化:不再跟蹤進程的睡眠時間、區分交互式進程,因此代碼中沒有那么多難以理解的經驗性公式,思路清晰簡單;新版本中增加了組調度功能,實現了對用戶和組的公平性;引入了調度類schedclass和調度實體schedu-entity的概念——調度類使不同的進程選擇不同的調度模塊,調度實體則實現了組調度的功能;不再使用優先級數組,它將所有就緒態的進程都插入紅黑樹,用紅黑樹來選擇下一個被調度的進程。圖1描述了進程的調度模型。類似于以往的調度器,它的主要工作仍舊是在就緒態的進程隊列中選擇最合適的進程來運行,不同的是,新內核中有了調度類的概念,將不同的進程放入不同的調度模塊中執行,例如:普通進程進入CFS調度模塊,實時進程進入實時調度模塊。因此,每個調度模塊都要執行調度類為它指定的一組相應的函數。這樣做的好處是,當需要修改相應進程的調度算法時,并不需要修改整個scheduler（）函數,只需要修改對應的函數。

圖1 CFS調度結構圖

3 CFS算法實現

CFS調度器的執行仍然以周期性調度函數scheduler-tick（）和主調度函數scheduler（）為基礎,根據進程的優先級調整進程的執行時間、以公平為原則實現對進程的調度,合理分配CPU資源。

3.1 周期性調度函數scheduler-tick（）

系統時鐘中斷調用scheduler-tick（）函數,更新運行隊列信息并執行與調度有關的系列操作。圖2描述了該函數主要的處理流程。

圖2 tick中斷流程圖

(1)更新本地CPU運行隊列的時間戳、負載等信息,然后轉入CFS調度類的 task-tick函數——tasktick-fair()。

(2)更新CFS運行隊列與當前執行進程的相關信息,在update-curr()中實現。此操作是中斷處理函數的核心,包含以下幾個重要步驟:

①計算當前運行進程自上次tick中斷以來的運行時間delta-exec:

delta-exec=(unsigned long)(now-curr-＞execstart)

curr-＞exec-start表示上次tick中斷時設置的時間戳,now表示本次tick發生時的時間戳。

②計算當前運行進程總的執行時間:

③根據進程的nice 值對進程的運行時間delta -exec 進行修正, 獲得進程的虛擬執行時間vrunt ime 。由于所有就緒態進程都以vruntime為鍵值插入到紅黑樹中,所以vruntime越大,鍵值越大,從而使得當前進程隨著執行時間的增加而向紅黑樹的右側移動。在每個調度點,調度器都會優先選擇vruntime小的進程——也就是紅黑樹中最左邊的葉子結點進行調度。

tick中斷里vruntime的變化歸納為以下公式:

NICE-0-LOAD表示進程nice為0時的weight值。curr-＞load.weight表示進程nice對應的weight值,nice越低,值越大,那么在執行相同時間的條件下(delta-exec相同),高優先級進程計算出的vruntime值會比低優先級進程的vruntime低。即高優級的進程就會位于紅黑樹的左邊,下次調度的時候就會被優先調度。

④更新當前進程的執行時間戳:curr-＞exec-start=now。

(3)判斷是否需要搶占當前進程,在check-preempt-tick()中實現。

①計算CFS隊列中所有進程被調度一次的時間周期period;

②計算當前進程允許占用的時間ideal-runtime;

curr-＞load.weight表示進程nice對應的weight值,而cfs-rq-＞load表示該cfs-rq的負載,進程入列時,此值增加,進程出列時,此值減小。由以上公式可以看出,系統負載越高,ideal-runtime越小;nice越大,se-＞load.weight值越小、ideal-runtime越小。也就是說優先級越高,進程執行的時間片越長;系統負載越低,進程允許執行的時間片越長。

③計算進程已占用CPU的時間

delta -exec = curr-＞sum-exec-runtime-curr-＞prev -sum-exec-runtimeprev-sum-exec-runtime表示進程被切換進CPU時的sum-exec-runtime。

④比較進程已占用CPU的時間delta-exec是否大于ideal-runtime。如果進程執行時間超過ideal-runtime時,就會調用resched-task（）設置該進程的搶占標志位,并在tick中斷返回時調用schedule（）來完成調度過程。

3.2 主調度函數scheduler（）

scheduler（）是真正實現調度的函數,它由主動和被動兩種方式調用。scheduler（）的主要功能是在運行隊列中選出下一個被調度的進程,并更新運行隊列的調度信息。圖3描述了schedule（）函數的主要工作流程。它的工作集中在put-prev-task（）和pick-next-task（）兩個函數上。在CFS調度模塊中,put-prev-task（）對應的函數為put-prev-task-fair（）,pick-next-task（）對應的函數為pick-next-task-fair（）。

（1）禁用內核搶占、初始化局部變量、執行相關鎖操作及清除調度標志位等工作。

（2）將當前執行進程放回運行隊列,在putprev-task-fair（）中實現。

①更新 cfs-rq和當前運行進程的信息update-curr（）。

②將當前進程插入紅黑樹,其排序的鍵值key為 se-＞vruntime-cfs-rq-＞min-vruntime（在-enqueue-entity（）實現）。

（3）選出下一個被調度的進程,并將CPU分配給這個進程（在pick-next-task-fair（）中實現）。

①選擇下一個要調度的進程（在pick-nextentity（）中實現）。

首先選出紅黑樹最左側的結點se,然后進行兩次條件判斷,最終決定下一個被調度的進程。

判斷1:是否被cfs-rq-＞next搶占

cfs-rq-＞next是被喚醒的進程。內核要優先調度被喚醒的進程,比如說A在等待一件事情,這件事情發生了,所以將A喚醒,當然是希望A盡快去處理這件事情比較好。

判斷2:是否被cfs-rq-＞last搶占

cfs-rq-＞last是當前運行的進程。為了避免頻繁調度,內核會優先調度喚醒時的當前進程。有進程喚醒時,此時的調度比較頻繁,因為可能插入了一個較小的vruntime進程。

以上可以看出schedule（）調度的時候,會優先讓這兩個進程運行。當這兩個判斷條件都不滿足時,才會調用紅黑樹最左側的節點se運行。

那么怎樣判斷se是否被cfs-rq-＞next或cfs-rq-＞last搶占呢?（在wakeup-preempt-entity（）中實現）

當se滿足以下兩個條件時,se不會被搶占:

條件一:se-＞vruntime小于curr-＞vruntime

條件二:curr-＞vruntime-se-＞vruntime大于最小調度粒度

調度粒度,也就是進程理論上占有CPU的最短時間。因為一個機器觸發調度的點很多,可能會在很短的時間內很頻繁的檢查當前進程需不需要被切換,考慮最小調度顆粒的問題可以避免頻繁調度,浪費CPU資源。

②選出下一個被調度的進程后,用set-next-entity（）設置所選進程的相關信息。

將選擇的下一個被調度進程se從紅黑樹中移出（調用-dequeue-entity（）實現）;

更新se的開始執行時間se-＞exec-start;

更新cfs-rq上當前執行的進程為se所表示的進程cfs-rq-＞curr=se;

更新se-＞prev-sum-exec-runtime做為進程切換到CPU上的sum-exec-runtime,se-＞prev -sum-exec -runtime =se-＞sum-exec-runt ime 。

圖3 scheduler（）函數流程圖

4 CFS與O（1）算法性能比較

HackBench是由Rusty Russell提出的一種BenchMark標準測試工具,用來評估Linux進程調度器的調度性能、負載性和可擴展性。該工具創建N組進程,每組進程包括20個寫者和20個讀者,寫者通過管道向讀者發送數據,測試 N組進程管道讀寫的時間。N值越大,調度器需要調度的任務就越多,這樣就能反應出調度器的性能。在實驗中創建了 N（1-60）組進程,分別在Linux2.6.18（O（1）調度算法）和Linux2.6.24（CFS調度算法）兩個版本上作測試。實驗結果如圖4所示。從圖4可以看出,在HackBench測試程序上運行相同個數的進程時,Linux 2.6.24的平均時間比Linux2.6.18要少,而且Linux2.6.24的曲線更接近于一條直線。測試結果表明,CFS調度器比O（1）調度器具有更好的性能。

5 CFS小結

以上的討論看出CFS對以前的調度器進行了很大改動。以完全公平為核心思想,通過追蹤進程的執行時間來調度任務;使用紅黑樹代替優先級數組來選擇下一個被調度的進程;引入調度類,顯著增強了內核調度程序的可擴展性和代碼的可維護性;代碼中不再有難以理解的經驗性公式,思路清晰簡單、結構靈活、算法適應性更高。當然,任何調度算法都還無法滿足所有的應用需要,CFS也有一些負面的測試報告,由于紅黑樹的查找執行時間為O（lg N）,當調度任務大幅增加時,性能會有所下降,但CFS在總體性能上還是比O（1）調度算法有了顯著的提高。隨著Linux內核的不斷發展,Linux調度算法會進一步完善,新的調度算法更令人期待。

圖4 運行不同進程數的HackBench測試程序的平均時間

[1] 張桂蘭,王飛超.Linux內核完全公平調度器的分析及模擬[J].中國信息科技,2009,4:134-137.

[2] 高博.Linux內核調度器分析及模擬[D].杭州:浙江大學,2008.

[3] Daniel P.Bovet,Marco Cesati.深入理解Linux內核[M].南京:東南大學出版社,2006.

[4] Wolfgang Mauerer.Professional Linux Kernel Architecture[M].Wiley Publishing Inc Indianapolis,Indiana,2008.

[5] 劉謙.基于Linux的調度機制及其實時性研究[D].成都:西南交通大學,2008.

[6] 蘇新,毛萬勝.基于Linux 2.6內核進程調度策略分析[J].福建電腦,2007,（12）.