朱 旭, 楊 斌, 劉海濤

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,四川成都 610031）

1 引言

進(jìn)程調(diào)度是操作系統(tǒng)的核心功能,其主要目的是合理分配處理器資源。調(diào)度算法是任務(wù)調(diào)度具體的實(shí)現(xiàn)方法,一個(gè)好的調(diào)度算法將實(shí)現(xiàn)公平、效率、響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間、吞吐量等多個(gè)調(diào)度目標(biāo)間的平衡。自Linux 2.4調(diào)度器使用基于優(yōu)先級(jí)的調(diào)度算法以來,Linux2.6開發(fā)系列的內(nèi)核中又經(jīng)歷了O（1）、RSDL、SD和CFS調(diào)度算法。其中CFS是Linux2.6.23內(nèi)核引入的全新調(diào)度算法,相對(duì)于O（1）,CFS進(jìn)行了很大改動(dòng),它以完全公平作為調(diào)度的核心思想,在性能提升的基礎(chǔ)上大大簡(jiǎn)化了代碼,成為內(nèi)核采用的新一代調(diào)度算法。

2 CFS概述

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

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

圖1 CFS調(diào)度結(jié)構(gòu)圖

3 CFS算法實(shí)現(xiàn)

CFS調(diào)度器的執(zhí)行仍然以周期性調(diào)度函數(shù)scheduler-tick（）和主調(diào)度函數(shù)scheduler（）為基礎(chǔ),根據(jù)進(jìn)程的優(yōu)先級(jí)調(diào)整進(jìn)程的執(zhí)行時(shí)間、以公平為原則實(shí)現(xiàn)對(duì)進(jìn)程的調(diào)度,合理分配CPU資源。

3.1 周期性調(diào)度函數(shù)scheduler-tick（）

系統(tǒng)時(shí)鐘中斷調(diào)用scheduler-tick（）函數(shù),更新運(yùn)行隊(duì)列信息并執(zhí)行與調(diào)度有關(guān)的系列操作。圖2描述了該函數(shù)主要的處理流程。

圖2 tick中斷流程圖

(1)更新本地CPU運(yùn)行隊(duì)列的時(shí)間戳、負(fù)載等信息,然后轉(zhuǎn)入CFS調(diào)度類的 task-tick函數(shù)——tasktick-fair()。

(2)更新CFS運(yùn)行隊(duì)列與當(dāng)前執(zhí)行進(jìn)程的相關(guān)信息,在update-curr()中實(shí)現(xiàn)。此操作是中斷處理函數(shù)的核心,包含以下幾個(gè)重要步驟:

①計(jì)算當(dāng)前運(yùn)行進(jìn)程自上次tick中斷以來的運(yùn)行時(shí)間delta-exec:

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

curr-＞exec-start表示上次tick中斷時(shí)設(shè)置的時(shí)間戳,now表示本次tick發(fā)生時(shí)的時(shí)間戳。

②計(jì)算當(dāng)前運(yùn)行進(jìn)程總的執(zhí)行時(shí)間:

③根據(jù)進(jìn)程的nice 值對(duì)進(jìn)程的運(yùn)行時(shí)間delta -exec 進(jìn)行修正, 獲得進(jìn)程的虛擬執(zhí)行時(shí)間vrunt ime 。由于所有就緒態(tài)進(jìn)程都以vruntime為鍵值插入到紅黑樹中,所以vruntime越大,鍵值越大,從而使得當(dāng)前進(jìn)程隨著執(zhí)行時(shí)間的增加而向紅黑樹的右側(cè)移動(dòng)。在每個(gè)調(diào)度點(diǎn),調(diào)度器都會(huì)優(yōu)先選擇vruntime小的進(jìn)程——也就是紅黑樹中最左邊的葉子結(jié)點(diǎn)進(jìn)行調(diào)度。

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

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

④更新當(dāng)前進(jìn)程的執(zhí)行時(shí)間戳:curr-＞exec-start=now。

(3)判斷是否需要搶占當(dāng)前進(jìn)程,在check-preempt-tick()中實(shí)現(xiàn)。

①計(jì)算CFS隊(duì)列中所有進(jìn)程被調(diào)度一次的時(shí)間周期period;

②計(jì)算當(dāng)前進(jìn)程允許占用的時(shí)間ideal-runtime;

curr-＞load.weight表示進(jìn)程nice對(duì)應(yīng)的weight值,而cfs-rq-＞load表示該cfs-rq的負(fù)載,進(jìn)程入列時(shí),此值增加,進(jìn)程出列時(shí),此值減小。由以上公式可以看出,系統(tǒng)負(fù)載越高,ideal-runtime越小;nice越大,se-＞load.weight值越小、ideal-runtime越小。也就是說優(yōu)先級(jí)越高,進(jìn)程執(zhí)行的時(shí)間片越長(zhǎng);系統(tǒng)負(fù)載越低,進(jìn)程允許執(zhí)行的時(shí)間片越長(zhǎng)。

③計(jì)算進(jìn)程已占用CPU的時(shí)間

delta -exec = curr-＞sum-exec-runtime-curr-＞prev -sum-exec-runtimeprev-sum-exec-runtime表示進(jìn)程被切換進(jìn)CPU時(shí)的sum-exec-runtime。

④比較進(jìn)程已占用CPU的時(shí)間delta-exec是否大于ideal-runtime。如果進(jìn)程執(zhí)行時(shí)間超過ideal-runtime時(shí),就會(huì)調(diào)用resched-task（）設(shè)置該進(jìn)程的搶占標(biāo)志位,并在tick中斷返回時(shí)調(diào)用schedule（）來完成調(diào)度過程。

3.2 主調(diào)度函數(shù)scheduler（）

scheduler（）是真正實(shí)現(xiàn)調(diào)度的函數(shù),它由主動(dòng)和被動(dòng)兩種方式調(diào)用。scheduler（）的主要功能是在運(yùn)行隊(duì)列中選出下一個(gè)被調(diào)度的進(jìn)程,并更新運(yùn)行隊(duì)列的調(diào)度信息。圖3描述了schedule（）函數(shù)的主要工作流程。它的工作集中在put-prev-task（）和pick-next-task（）兩個(gè)函數(shù)上。在CFS調(diào)度模塊中,put-prev-task（）對(duì)應(yīng)的函數(shù)為put-prev-task-fair（）,pick-next-task（）對(duì)應(yīng)的函數(shù)為pick-next-task-fair（）。

（1）禁用內(nèi)核搶占、初始化局部變量、執(zhí)行相關(guān)鎖操作及清除調(diào)度標(biāo)志位等工作。

（2）將當(dāng)前執(zhí)行進(jìn)程放回運(yùn)行隊(duì)列,在putprev-task-fair（）中實(shí)現(xiàn)。

①更新 cfs-rq和當(dāng)前運(yùn)行進(jìn)程的信息update-curr（）。

②將當(dāng)前進(jìn)程插入紅黑樹,其排序的鍵值key為 se-＞vruntime-cfs-rq-＞min-vruntime（在-enqueue-entity（）實(shí)現(xiàn)）。

（3）選出下一個(gè)被調(diào)度的進(jìn)程,并將CPU分配給這個(gè)進(jìn)程（在pick-next-task-fair（）中實(shí)現(xiàn)）。

①選擇下一個(gè)要調(diào)度的進(jìn)程（在pick-nextentity（）中實(shí)現(xiàn)）。

首先選出紅黑樹最左側(cè)的結(jié)點(diǎn)se,然后進(jìn)行兩次條件判斷,最終決定下一個(gè)被調(diào)度的進(jìn)程。

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

cfs-rq-＞next是被喚醒的進(jìn)程。內(nèi)核要優(yōu)先調(diào)度被喚醒的進(jìn)程,比如說A在等待一件事情,這件事情發(fā)生了,所以將A喚醒,當(dāng)然是希望A盡快去處理這件事情比較好。

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

cfs-rq-＞last是當(dāng)前運(yùn)行的進(jìn)程。為了避免頻繁調(diào)度,內(nèi)核會(huì)優(yōu)先調(diào)度喚醒時(shí)的當(dāng)前進(jìn)程。有進(jìn)程喚醒時(shí),此時(shí)的調(diào)度比較頻繁,因?yàn)榭赡懿迦肓艘粋€(gè)較小的vruntime進(jìn)程。

以上可以看出schedule（）調(diào)度的時(shí)候,會(huì)優(yōu)先讓這兩個(gè)進(jìn)程運(yùn)行。當(dāng)這兩個(gè)判斷條件都不滿足時(shí),才會(huì)調(diào)用紅黑樹最左側(cè)的節(jié)點(diǎn)se運(yùn)行。

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

當(dāng)se滿足以下兩個(gè)條件時(shí),se不會(huì)被搶占:

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

條件二:curr-＞vruntime-se-＞vruntime大于最小調(diào)度粒度

調(diào)度粒度,也就是進(jìn)程理論上占有CPU的最短時(shí)間。因?yàn)橐粋€(gè)機(jī)器觸發(fā)調(diào)度的點(diǎn)很多,可能會(huì)在很短的時(shí)間內(nèi)很頻繁的檢查當(dāng)前進(jìn)程需不需要被切換,考慮最小調(diào)度顆粒的問題可以避免頻繁調(diào)度,浪費(fèi)CPU資源。

②選出下一個(gè)被調(diào)度的進(jìn)程后,用set-next-entity（）設(shè)置所選進(jìn)程的相關(guān)信息。

將選擇的下一個(gè)被調(diào)度進(jìn)程se從紅黑樹中移出（調(diào)用-dequeue-entity（）實(shí)現(xiàn)）;

更新se的開始執(zhí)行時(shí)間se-＞exec-start;

更新cfs-rq上當(dāng)前執(zhí)行的進(jìn)程為se所表示的進(jìn)程cfs-rq-＞curr=se;

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

圖3 scheduler（）函數(shù)流程圖

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

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

5 CFS小結(jié)

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

圖4 運(yùn)行不同進(jìn)程數(shù)的HackBench測(cè)試程序的平均時(shí)間

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

[2] 高博.Linux內(nèi)核調(diào)度器分析及模擬[D].杭州:浙江大學(xué),2008.

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

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

[5] 劉謙.基于Linux的調(diào)度機(jī)制及其實(shí)時(shí)性研究[D].成都:西南交通大學(xué),2008.

[6] 蘇新,毛萬勝.基于Linux 2.6內(nèi)核進(jìn)程調(diào)度策略分析[J].福建電腦,2007,（12）.