曹 越,顧乃杰,任開(kāi)新,張 旭,吳志強(qiáng)

(中國(guó)科學(xué)技術(shù)大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.安徽省計(jì)算與通信軟件重點(diǎn)實(shí)驗(yàn)室;c.先進(jìn)技術(shù)研究院,合肥230027)

一種面向多核系統(tǒng)的Linux任務(wù)調(diào)度算法

曹 越a,b,c,顧乃杰a,b,c,任開(kāi)新a,b,c,張 旭a,b,c,吳志強(qiáng)a,b,c

(中國(guó)科學(xué)技術(shù)大學(xué)a.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;b.安徽省計(jì)算與通信軟件重點(diǎn)實(shí)驗(yàn)室;c.先進(jìn)技術(shù)研究院,合肥230027)

針對(duì)Linux任務(wù)調(diào)度算法在多核系統(tǒng)中交互性能差的問(wèn)題,提出一種分組任務(wù)調(diào)度算法GFS。根據(jù)多核系統(tǒng)硬件特性,自動(dòng)配置物理距離近的一組CPU共享一個(gè)任務(wù)運(yùn)行隊(duì)列,通過(guò)平衡組內(nèi)CPU對(duì)任務(wù)運(yùn)行隊(duì)列的訪問(wèn)競(jìng)爭(zhēng)與任務(wù)遷移的代價(jià),實(shí)現(xiàn)組間任務(wù)運(yùn)行隊(duì)列的負(fù)載均衡,減少調(diào)度延遲。通過(guò)優(yōu)先調(diào)度喚醒任務(wù),加快多核系統(tǒng)中交互任務(wù)的響應(yīng)速度。測(cè)試結(jié)果表明,在不同任務(wù)負(fù)載下,GFS能夠明顯降低交互任務(wù)的平均響應(yīng)時(shí)間,從而有效提高多核系統(tǒng)交互應(yīng)用的調(diào)度性能。

多核系統(tǒng);調(diào)度算法;交互性能;自動(dòng)配置;喚醒任務(wù);負(fù)載均衡

1 概述

Linux操作系統(tǒng)由于具有良好的穩(wěn)定性和安全性,在超級(jí)計(jì)算機(jī)、PC、嵌入式系統(tǒng)等領(lǐng)域都有廣泛應(yīng)用,但是不同系統(tǒng)的調(diào)度目標(biāo)不同[1],如超級(jí)計(jì)算機(jī)主要考慮優(yōu)化任務(wù)的吞吐量,PC主要考慮減少任務(wù)響應(yīng)時(shí)間,Linux的目標(biāo)是支持所有應(yīng)用場(chǎng)景,使得其調(diào)度算法很難完全滿足所有系統(tǒng)的需求。

目前,多核技術(shù)在交互性能要求高的場(chǎng)景,如即時(shí)通信(Instant Messaging,IM)服務(wù)器、Web服務(wù)器上的應(yīng)用越來(lái)越多。交互任務(wù)需要和用戶進(jìn)行交互,經(jīng)常等待用戶輸入而處于睡眠狀態(tài),一旦喚醒應(yīng)該盡快執(zhí)行,獲取用戶輸入并交互,否則影響用戶體驗(yàn)。對(duì)于這類(lèi)任務(wù),調(diào)度目標(biāo)是減少任務(wù)響應(yīng)時(shí)間[2],而Linux在設(shè)計(jì)上側(cè)重考慮超級(jí)計(jì)算機(jī),其調(diào)度算法CFS(Completely Fair Schedule)偏向于提高任務(wù)的吞吐量,導(dǎo)致算法對(duì)多核系統(tǒng)的交互任務(wù)調(diào)度效率不高[3]。

針對(duì)多核系統(tǒng)的交互任務(wù)調(diào)度問(wèn)題,目前有較多研究。文獻(xiàn)[4]提出一種基于緩存競(jìng)爭(zhēng)優(yōu)化的調(diào)度算法,利用性能監(jiān)測(cè)單元刻畫(huà)任務(wù)的緩存競(jìng)爭(zhēng)強(qiáng)弱,通過(guò)輪詢優(yōu)化任務(wù)調(diào)度順序,避免在同一個(gè)CPU上同時(shí)運(yùn)行多個(gè)緩存競(jìng)爭(zhēng)力強(qiáng)的任務(wù),從而提高調(diào)度效率,但是該算法需要計(jì)算任務(wù)的緩存競(jìng)爭(zhēng)特性并進(jìn)行任務(wù)重分配,帶來(lái)了額外的調(diào)度開(kāi)銷(xiāo)。文獻(xiàn)[5]提出一種全局調(diào)度算法BFS(Brain Fuck Schedule),所有CPU共享一個(gè)任務(wù)運(yùn)行隊(duì)列,不需要負(fù)載均衡操作,任務(wù)可以在所有CPU上運(yùn)行,算法可以減少交互任務(wù)的響應(yīng)時(shí)間,但是可擴(kuò)展性較差,在系統(tǒng)CPU數(shù)或任務(wù)數(shù)比較多時(shí)由于隊(duì)列訪問(wèn)競(jìng)爭(zhēng)代價(jià)增大,導(dǎo)致調(diào)度效率明顯下降。本文提出一種分組任務(wù)調(diào)度算法GFS(Group Fair Schedule),自動(dòng)配置親緣關(guān)系近的一組CPU共享一個(gè)任務(wù)運(yùn)行隊(duì)列,任務(wù)在組內(nèi)CPU間遷移代價(jià)較小,在系統(tǒng)負(fù)載嚴(yán)重不均衡時(shí)可以進(jìn)行組間任務(wù)遷移以提高調(diào)度效率,并通過(guò)優(yōu)先調(diào)度喚醒任務(wù),減少交互任務(wù)的響應(yīng)時(shí)間。

2 相關(guān)知識(shí)

2.1 Linux調(diào)度器

Linux調(diào)度器主要有2種核心操作:周期調(diào)度函數(shù)scheduler_tick和主調(diào)度函數(shù)schedule[6]。前者在時(shí)鐘中斷處理中被調(diào)用,負(fù)責(zé)定期更新調(diào)度相關(guān)的統(tǒng)計(jì)信息。后者在任務(wù)睡眠、終止或者從中斷、異常及系統(tǒng)調(diào)用返回時(shí)被調(diào)用,完成實(shí)際的任務(wù)調(diào)度。

2.2 CFS任務(wù)調(diào)度算法

自Linux2.6.23內(nèi)核發(fā)布以來(lái),Linux采用CFS作為任務(wù)調(diào)度算法[7]。算法基本思想是在真實(shí)硬件上模擬理想的多任務(wù)處理器,使所有任務(wù)盡可能公平獲得CPU[8]。

為實(shí)現(xiàn)這種思想,CFS引入虛擬運(yùn)行時(shí)間來(lái)表示任務(wù)在CPU上的執(zhí)行時(shí)間。為使每個(gè)任務(wù)獲得相近的執(zhí)行時(shí)間,調(diào)度器每次選取虛擬運(yùn)行時(shí)間最小的任務(wù)進(jìn)入運(yùn)行。運(yùn)行時(shí),高優(yōu)先級(jí)任務(wù)虛擬運(yùn)行時(shí)間增長(zhǎng)速度比低優(yōu)先級(jí)任務(wù)慢,從而獲得更多的調(diào)度機(jī)會(huì)。每個(gè)CPU維持一個(gè)以紅黑樹(shù)為數(shù)據(jù)結(jié)構(gòu)的任務(wù)運(yùn)行隊(duì)列,紅黑樹(shù)的節(jié)點(diǎn)名稱為任務(wù)名稱,鍵值為任務(wù)虛擬運(yùn)行時(shí)間,如圖1所示。

圖1 CFS任務(wù)運(yùn)行隊(duì)列架構(gòu)

由于任務(wù)運(yùn)行隊(duì)列以紅黑樹(shù)作為數(shù)據(jù)結(jié)構(gòu),隊(duì)列中虛擬運(yùn)行時(shí)間最小的任務(wù)為紅黑樹(shù)最左側(cè)的任務(wù)。

任務(wù)新建時(shí),任務(wù)虛擬運(yùn)行時(shí)間為紅黑樹(shù)最左側(cè)任務(wù)的虛擬運(yùn)行時(shí)間加上與隊(duì)列負(fù)載有關(guān)的一個(gè)經(jīng)驗(yàn)值;任務(wù)喚醒時(shí),虛擬運(yùn)行時(shí)間調(diào)整為紅黑樹(shù)最左側(cè)任務(wù)的虛擬運(yùn)行時(shí)間減去與睡眠時(shí)間有關(guān)的一個(gè)經(jīng)驗(yàn)值。將新任務(wù)插入紅黑樹(shù)并更新隊(duì)列負(fù)載,如果CPU沒(méi)有運(yùn)行任務(wù),或者當(dāng)前運(yùn)行任務(wù)虛擬運(yùn)行時(shí)間比新任務(wù)大,則置位CPU調(diào)度標(biāo)志,下次中斷或者系統(tǒng)調(diào)用返回時(shí)檢測(cè)到調(diào)度標(biāo)志置位會(huì)調(diào)用schedule函數(shù)完成調(diào)度。

CFS調(diào)度器核心操作的主要流程如下:

(1)scheduler_tick函數(shù)計(jì)算運(yùn)行任務(wù)的虛擬運(yùn)行時(shí)間,根據(jù)隊(duì)列負(fù)載信息計(jì)算運(yùn)行任務(wù)允許的虛擬運(yùn)行時(shí)間,如果虛擬運(yùn)行時(shí)間超出允許值,則置位CPU調(diào)度標(biāo)志,在時(shí)鐘中斷返回重新調(diào)度[9]。如果任務(wù)運(yùn)行隊(duì)列間負(fù)載嚴(yán)重失衡,則進(jìn)行任務(wù)遷移使負(fù)載均衡。

(2)schedule函數(shù)清理調(diào)度標(biāo)志,計(jì)算運(yùn)行任務(wù)的虛擬運(yùn)行時(shí)間,插入紅黑樹(shù)中,再選取紅黑樹(shù)最左側(cè)的任務(wù),切換上下文執(zhí)行新任務(wù)。

假設(shè)系統(tǒng)中有M個(gè)CPU、N個(gè)任務(wù)。任務(wù)新建、插入、刪除和調(diào)度時(shí)間復(fù)雜度為O(lg(N/M)),各類(lèi)操作效率均較高。但是CFS需要頻繁判斷執(zhí)行負(fù)載均衡,任務(wù)遷移時(shí)會(huì)進(jìn)行任務(wù)運(yùn)行隊(duì)列加解鎖, Cache和內(nèi)存刷新等操作導(dǎo)致性能下降。此外,任務(wù)插入CPU對(duì)應(yīng)的任務(wù)運(yùn)行隊(duì)列后,除非發(fā)生負(fù)載均衡,否則只能在該CPU上執(zhí)行,喚醒任務(wù)不能轉(zhuǎn)移到其他滿足調(diào)度條件的CPU上執(zhí)行,影響了交互任務(wù)響應(yīng)時(shí)間。

2.3 BFS任務(wù)調(diào)度算法

BFS是Android操作系統(tǒng)采用的任務(wù)調(diào)度算法。BFS為每個(gè)任務(wù)分配一個(gè)時(shí)間片和虛擬最后期限,調(diào)度器每次選取虛擬最后期限最小的任務(wù)進(jìn)入運(yùn)行。所有的CPU共享一個(gè)全局的雙鏈表式的任務(wù)運(yùn)行隊(duì)列,如圖2所示。

圖2 BFS任務(wù)運(yùn)行隊(duì)列架構(gòu)

任務(wù)的虛擬最后期限計(jì)算公式為:

vdeadline=jiffies+prio_ratio×rr_interval

其中,jiffies是當(dāng)前時(shí)鐘時(shí)間;rr_interval為任務(wù)時(shí)間片長(zhǎng)度,固定為6 ms;prio_ratio是與任務(wù)優(yōu)先級(jí)有關(guān)的參數(shù),優(yōu)先級(jí)越高對(duì)應(yīng)的prio_ratio值越小。

當(dāng)新建任務(wù)時(shí),根據(jù)上述公式計(jì)算任務(wù)虛擬最后期限;任務(wù)喚醒時(shí),保持睡眠前的虛擬最后期限不變。將新任務(wù)插入雙鏈表末尾,檢查所有CPU,如果存在空閑的CPU,或者存在運(yùn)行任務(wù)虛擬最后期限大于新任務(wù)的CPU,則置位該CPU的調(diào)度標(biāo)志并發(fā)送處理器間中斷引發(fā)重新調(diào)度。

BFS調(diào)度器核心操作的主要流程如下:

(1)scheduler_tick函數(shù)計(jì)算當(dāng)前運(yùn)行任務(wù)的運(yùn)行時(shí)間,如果任務(wù)用完自己的時(shí)間片,則置位調(diào)度標(biāo)志。

(2)schedule函數(shù)清理調(diào)度標(biāo)志,將運(yùn)行任務(wù)插入雙鏈表末尾,如果運(yùn)行任務(wù)已經(jīng)用完時(shí)間片,重新裝填任務(wù)的時(shí)間片,根據(jù)公式重新計(jì)算虛擬最后期限。掃描整個(gè)雙鏈表,選取可在CPU上運(yùn)行并且具有最小虛擬最后期限的任務(wù),切換上下文執(zhí)行新任務(wù)。

假設(shè)系統(tǒng)中有M個(gè)CPU、N個(gè)任務(wù)。任務(wù)插入和刪除時(shí)間復(fù)雜度為O(1),新建和喚醒時(shí)間復(fù)雜度為O(M),調(diào)度時(shí)間復(fù)雜度為O(N)。任務(wù)喚醒時(shí),如果有滿足調(diào)度條件的CPU,通知該CPU重新調(diào)度,減少了交互任務(wù)的響應(yīng)時(shí)間,所有CPU共享任務(wù)運(yùn)行隊(duì)列因此不需要負(fù)載均衡。不足之處是當(dāng)系統(tǒng)中CPU數(shù)目較多時(shí)隊(duì)列競(jìng)爭(zhēng)訪問(wèn)延時(shí)比較大,任務(wù)數(shù)目較多時(shí)調(diào)度效率很低。此外,CPU間親緣關(guān)系比較遠(yuǎn),例如在不同的NUMA節(jié)點(diǎn)上時(shí),任務(wù)在CPU間遷移導(dǎo)致Cache或內(nèi)存刷新的代價(jià)可能超過(guò)在原CPU上等待調(diào)度的代價(jià),影響調(diào)度性能。

3 GFS算法設(shè)計(jì)

為解決BFS隨系統(tǒng)CPU和任務(wù)數(shù)目增多響應(yīng)時(shí)間增加較快的問(wèn)題,本文提出GFS算法。算法沿用BFS虛擬最后期限和時(shí)間片的設(shè)計(jì)和計(jì)算方法,并支持自動(dòng)配置一組CPU共享一個(gè)任務(wù)運(yùn)行隊(duì)列。通過(guò)對(duì)任務(wù)運(yùn)行隊(duì)列的分組配置,綜合考慮隊(duì)列訪問(wèn)競(jìng)爭(zhēng)、任務(wù)遷移和負(fù)載均衡代價(jià),更好地適應(yīng)實(shí)際硬件和負(fù)載的需求。

GFS依照CPU之間的親緣關(guān)系進(jìn)行分組配置。一般多核系統(tǒng)CPU之間的親緣關(guān)系由遠(yuǎn)及近有以下4種:

(1)不同NUMA節(jié)點(diǎn),它們有獨(dú)立的內(nèi)存。

(2)同一NUMA節(jié)點(diǎn)上的不同處理器,它們共享內(nèi)存,但是有獨(dú)立的Cache。

(3)同一處理器上的不同核,它們共享L2 Cache,但是有獨(dú)立的L1Cache。

(4)同一核上的不同超線程,它們共享L1 Cache。

不同的存儲(chǔ)器訪問(wèn)時(shí)間不同:內(nèi)存訪存時(shí)間為50 ns～100 ns,L2 Cache訪存時(shí)間為3 ns～10 ns,L1 Cache訪存時(shí)間約為1ns[10],將親緣關(guān)系近的CPU配置到一個(gè)分組,任務(wù)在組內(nèi)CPU間遷移運(yùn)行導(dǎo)致CPU間存儲(chǔ)刷新代價(jià)較小。GFS為每個(gè)分組分配一棵紅黑樹(shù)作為主任務(wù)運(yùn)行隊(duì)列,為每個(gè)CPU分配一個(gè)順序雙鏈表作為存儲(chǔ)可調(diào)度喚醒任務(wù)的高級(jí)任務(wù)運(yùn)行隊(duì)列,如圖3所示。

圖3 GFS任務(wù)運(yùn)行隊(duì)列架構(gòu)

當(dāng)新建任務(wù)時(shí),根據(jù)公式計(jì)算虛擬最后期限。將新任務(wù)插入CPU所在分組的紅黑樹(shù)中,檢查本分組內(nèi)所有CPU,如果存在空閑的CPU,或者運(yùn)行任務(wù)虛擬最后期限大于新任務(wù)的CPU,則置位該CPU的調(diào)度標(biāo)志并發(fā)送處理器間中斷引發(fā)重新調(diào)度。

任務(wù)喚醒時(shí),保持睡眠前虛擬最后期限不變。檢查本分組內(nèi)所有CPU,如果存在空閑的CPU,或者運(yùn)行任務(wù)虛擬最后期限大于新任務(wù)的CPU,則將新任務(wù)插入該CPU對(duì)應(yīng)的順序雙鏈表中,置位該CPU的調(diào)度標(biāo)志并發(fā)送處理器間中斷引發(fā)重新調(diào)度,否則將新任務(wù)插入分組對(duì)應(yīng)的紅黑樹(shù)中。

GFS調(diào)度器核心操作的主要流程分析如下:

(1)scheduler_tick函數(shù)計(jì)算運(yùn)行任務(wù)的運(yùn)行時(shí)間,如果任務(wù)用完時(shí)間片則置位調(diào)度標(biāo)志。如果各分組隊(duì)列間負(fù)載嚴(yán)重失衡,進(jìn)行分組間任務(wù)遷移。

(2)schedule函數(shù)清理調(diào)度標(biāo)志,將運(yùn)行任務(wù)插入CPU所在分組的紅黑樹(shù)中,如果運(yùn)行任務(wù)用完時(shí)間片,重新裝填時(shí)間片和虛擬最后期限。調(diào)度時(shí),優(yōu)先選取CPU對(duì)應(yīng)的順序雙鏈表中的任務(wù),如果順序雙鏈表為空,則選取紅黑樹(shù)最左側(cè)的可運(yùn)行任務(wù),切換上下文執(zhí)行新任務(wù)。

由于調(diào)度任務(wù)時(shí),選取順序是先查看順序雙鏈表,再查看紅黑樹(shù),喚醒任務(wù)如果滿足調(diào)度條件會(huì)放入順序雙鏈表并且立即通知CPU重新調(diào)度,這種機(jī)制減少了喚醒任務(wù)的響應(yīng)時(shí)間,也使得順序雙鏈表中任務(wù)數(shù)不會(huì)很多,各項(xiàng)操作效率比較高。

假設(shè)系統(tǒng)中有M個(gè)CPU、N個(gè)任務(wù)、K個(gè)分組。任務(wù)插入及刪除時(shí)間復(fù)雜度為O(lg(N/K)),新建和喚醒時(shí)間復(fù)雜度為O(M/K+lg(N/K)),調(diào)度時(shí)間復(fù)雜度一般為O(lg(N/K))。GFS優(yōu)先調(diào)度滿足調(diào)度條件的喚醒任務(wù)讓交互任務(wù)的響應(yīng)速度較高。每組CPU競(jìng)爭(zhēng)一個(gè)主任務(wù)運(yùn)行隊(duì)列降低了競(jìng)爭(zhēng),分組內(nèi)部任務(wù)遷移代價(jià)比較小,同時(shí)在一般情況下調(diào)度效率較高。

4 GFS算法實(shí)現(xiàn)

4.1 CPU分組配置

sched_init是Linux啟動(dòng)內(nèi)核時(shí)進(jìn)行調(diào)度初始化的函數(shù)。GFS在函數(shù)中為每個(gè)CPU初始化一個(gè)主任務(wù)運(yùn)行隊(duì)列指針和一個(gè)高級(jí)任務(wù)運(yùn)行隊(duì)列指針。為支持自動(dòng)分組配置,GFS為每個(gè)CPU初始化一個(gè)數(shù)組cpu_locality,用于表示該CPU與其他CPU間的親緣關(guān)系。定義一組宏:CPU＜CORE＜PHY＜NUMA,對(duì)于每個(gè)CPU,遍歷系統(tǒng)中所有其他的CPU,如果2個(gè)CPU在同一核的不同超線程上,則將cpu_locality的相應(yīng)位設(shè)置為CPU;如果在同一處理器的不同核上,則將相應(yīng)位設(shè)置為CORE;如果在同一NUMA節(jié)點(diǎn)的不同處理器上,則將相應(yīng)位設(shè)置為PHY;否則將相應(yīng)位設(shè)置為NUMA。GFS記錄遍歷過(guò)程中獲得的CPU之間親緣關(guān)系的最大值,依此進(jìn)行分組自動(dòng)配置。

migration_init是Linux進(jìn)行任務(wù)遷移初始化的函數(shù)。GFS在函數(shù)中執(zhí)行分組配置,如果CPU之間親緣關(guān)系最大值為NUMA或PHY,則以處理器作為分組單位,通過(guò)cpu_locality數(shù)組找到同一處理器上的所有CPU劃分為一個(gè)組,否則以核作為分組單位,同一核上的所有CPU劃分為一個(gè)組。由于同一處理器上的所有CPU共享L2 Cache,這種分組配置下,任務(wù)在組內(nèi)CPU之間遷移的代價(jià)比較小,同時(shí)組內(nèi)有比較多的CPU可以選擇運(yùn)行。

自動(dòng)配置可能不完全符合系統(tǒng)要求,GFS封裝了系統(tǒng)調(diào)用sys_set_mainq_cpu實(shí)現(xiàn)重新指定CPU的主任務(wù)運(yùn)行隊(duì)列,用戶可以通過(guò)系統(tǒng)調(diào)用實(shí)現(xiàn)手動(dòng)配置CPU分組,更好發(fā)揮系統(tǒng)的硬件特性。

4.2 調(diào)度函數(shù)

4.2.1 scheduler_tick函數(shù)

GFS的scheduler_tick函數(shù)在BFS的scheduler_ tick函數(shù)末尾添加了負(fù)載均衡處理。負(fù)載均衡可以提高調(diào)度的并行性,但是執(zhí)行時(shí)需要執(zhí)行任務(wù)運(yùn)行隊(duì)列加解鎖、任務(wù)遷移等操作,對(duì)調(diào)度器性能有影響,因此應(yīng)該減少負(fù)載均衡的操作復(fù)雜程度和時(shí)機(jī)。

GFS通過(guò)調(diào)度域描述系統(tǒng)的CPU拓?fù)浣Y(jié)構(gòu)[11]。調(diào)度域表示具有相同親緣關(guān)系的CPU集合,以層次結(jié)構(gòu)組織,從下到上依次是同一核的不同超線程(CPU調(diào)度域)、同一處理器的不同核(CORE調(diào)度域)、同一NUMA節(jié)點(diǎn)的不同處理器(PHY調(diào)度域)、不同NUMA節(jié)點(diǎn)(NUMA調(diào)度域)。不同層次之間通過(guò)指針鏈接在一起,形成一種的樹(shù)狀的關(guān)系,如圖4所示。

圖4 調(diào)度域?qū)哟谓Y(jié)構(gòu)

算法從CPU所在的最低級(jí)別調(diào)度域往上遍歷進(jìn)行負(fù)載均衡,直到遍歷完所有調(diào)度域。最低級(jí)別調(diào)度域與隊(duì)列分組配置的粒度有關(guān),例如分組時(shí)將同一核上的所有CPU放在一個(gè)組中,那么最低級(jí)別的調(diào)度域是CORE調(diào)度域,這樣需要進(jìn)行負(fù)載均衡的層數(shù)少了一層,減少了負(fù)載均衡操作的復(fù)雜度。

隨著調(diào)度域級(jí)別的提高,CPU間親緣關(guān)系疏遠(yuǎn),共享Cache或內(nèi)存減少,任務(wù)遷移刷新存儲(chǔ)的代價(jià)越大。GFS以間隔時(shí)間表示調(diào)度域的任務(wù)遷移代價(jià),調(diào)度域級(jí)別越高,任務(wù)遷移操作間隔時(shí)間越長(zhǎng)。

在scheduler_tick函數(shù)末尾判斷,如果當(dāng)前時(shí)鐘時(shí)間超過(guò)最低級(jí)別調(diào)度域負(fù)載均衡時(shí)間或者CPU運(yùn)行空閑任務(wù),則觸發(fā)一個(gè)軟中斷進(jìn)行負(fù)載均衡處理。

在軟中斷中,由rebalance_domains函數(shù)進(jìn)行負(fù)載均衡處理,rebalance_domains函數(shù)在最低級(jí)別調(diào)度域執(zhí)行任務(wù)遷移,并往上檢查當(dāng)前時(shí)鐘時(shí)間是否超過(guò)各級(jí)別調(diào)度域的負(fù)載均衡時(shí)間,如果沒(méi)有超過(guò),則函數(shù)終止,否則進(jìn)行任務(wù)遷移并繼續(xù)檢查。

load_balance函數(shù)進(jìn)行具體的任務(wù)遷移處理。函數(shù)重設(shè)調(diào)度域的負(fù)載均衡時(shí)間,找出調(diào)度域下負(fù)載最重的子調(diào)度域,在子調(diào)度域中找到負(fù)載最重的隊(duì)列,如果該隊(duì)列不同于當(dāng)前隊(duì)列,則將該隊(duì)列下的超重的任務(wù)遷移到當(dāng)前隊(duì)列上,以達(dá)到平衡。遷移過(guò)程中,如果發(fā)現(xiàn)有滿足調(diào)度條件的任務(wù),則置位相應(yīng)的調(diào)度標(biāo)志。

CFS在任務(wù)喚醒、任務(wù)創(chuàng)建時(shí)均需判斷是否執(zhí)行負(fù)載均衡,且每次操作都從CPU調(diào)度域遍歷到NUMA調(diào)度域。相對(duì)CFS,GFS的負(fù)載均衡時(shí)機(jī)減少,僅需定期進(jìn)行負(fù)載均衡和在CPU沒(méi)有運(yùn)行任務(wù)時(shí)進(jìn)行負(fù)載均衡。另外,GFS的負(fù)載均衡操作掃描的調(diào)度域?qū)訑?shù)一般少于CFS,操作復(fù)雜度降低,負(fù)載均衡性能提高。

4.2.2 schedule函數(shù)

schedule函數(shù)核心問(wèn)題為待運(yùn)行任務(wù)的選取,選取順序是先查看順序雙鏈表,再查看紅黑樹(shù)。如果順序雙鏈表中有任務(wù),由于任務(wù)已經(jīng)按照虛擬最后期限順序由小到大排好,直接選取第一項(xiàng)作為待運(yùn)行任務(wù)。如果高級(jí)任務(wù)運(yùn)行隊(duì)列中沒(méi)有任務(wù),調(diào)度器選取紅黑樹(shù)最左側(cè)的可運(yùn)行任務(wù)?？紤]到一些任務(wù)可能綁定到指定CPU上執(zhí)行,因此在紅黑樹(shù)中找到最左側(cè)的任務(wù)后,需要判斷該任務(wù)是否容許在CPU上運(yùn)行,如果可以,則選取該任務(wù)作為待運(yùn)行任務(wù),否則繼續(xù)查看該任務(wù)的后繼,直到所有任務(wù)被掃描完。

如果所有的掃描都完成后還沒(méi)發(fā)現(xiàn)待運(yùn)行任務(wù),則在對(duì)應(yīng)的主任務(wù)運(yùn)行隊(duì)列中標(biāo)記CPU為空閑CPU,新任務(wù)產(chǎn)生時(shí)可以在CPU上得到調(diào)度機(jī)會(huì)。選取的最壞時(shí)間復(fù)雜度為O(lg(N/K)((N/K)),這發(fā)生在系統(tǒng)中很多任務(wù)設(shè)置綁定到特定CPU時(shí),一般情況下任務(wù)不會(huì)指定在特定的一組CPU上執(zhí)行,因而可以在任意CPU上運(yùn)行,這時(shí)選取時(shí)間復(fù)雜度為O(lg(N/K)),效率比BFS的O(N)高。

4.3 任務(wù)喚醒

喚醒任務(wù)的關(guān)鍵在于CPU選取。GFS按照CPU親緣關(guān)系由近及遠(yuǎn)的順序,優(yōu)先選擇空閑CPU,其次選擇當(dāng)前運(yùn)行任務(wù)虛擬最后期限比自己大的CPU。

當(dāng)任務(wù)喚醒時(shí),首先找到任務(wù)所在分組的主任務(wù)運(yùn)行隊(duì)列,獲取該隊(duì)列分組的空閑可運(yùn)行CPU信息,借助cpu_locality數(shù)組遍歷并找到親緣關(guān)系最近的空閑可運(yùn)行CPU作為調(diào)度CPU。如果沒(méi)有符合調(diào)度條件的空閑CPU,則獲取該隊(duì)列分組的非空閑可運(yùn)行CPU信息,遍歷并找到親緣關(guān)系最近且當(dāng)前運(yùn)行任務(wù)虛擬最后期限大于喚醒任務(wù)的CPU作為調(diào)度CPU。

如果找到可調(diào)度的CPU,則把喚醒任務(wù)插入該CPU的高級(jí)運(yùn)行隊(duì)列,置位CPU的調(diào)度標(biāo)志并發(fā)送處理器間中斷;否則,將任務(wù)插入CPU所在分組的主運(yùn)行隊(duì)列。

5 測(cè)試結(jié)果與分析

5.1 測(cè)試環(huán)境和方法

為直觀反映GFS的性能,本節(jié)對(duì)CFS、BFS、緩存競(jìng)爭(zhēng)調(diào)度算法及GFS進(jìn)行性能測(cè)試。測(cè)試平臺(tái)環(huán)境為:CPU為4核8CPU的Intel(R)Core(TM)i7-3770 CPU@3.40 GHz,內(nèi)存2 GB;操作系統(tǒng): CentOS release 6.3,內(nèi)核版本為L(zhǎng)inux3.6.2。GFS自動(dòng)配置同一核下的所有CPU為一個(gè)分組。

本文使用Interbench-0.31工具進(jìn)行Linux交互性能測(cè)試[12]。Interbench模擬背景負(fù)載下交互任務(wù)的響應(yīng)延遲數(shù)據(jù)。本次測(cè)試的背景負(fù)載為Burn,模擬若干服務(wù)CPU任務(wù),CPU占用率為100%。交互任務(wù)為X_windows,模擬的是桌面操作任務(wù),任務(wù)隨機(jī)的睡眠及喚醒,CPU占用率與請(qǐng)求次數(shù)也不固定。任務(wù)喚醒與執(zhí)行的時(shí)間差作為響應(yīng)延時(shí),分別測(cè)試背景負(fù)載由輕到重,任務(wù)數(shù)為8,16,24,32,40,48時(shí)交互任務(wù)響應(yīng)延時(shí)的平均值、標(biāo)準(zhǔn)偏差及最大值,分析調(diào)度算法的交互性能。

5.2 結(jié)果分析

不同任務(wù)負(fù)載下3種調(diào)度算法的平均響應(yīng)延時(shí)、響應(yīng)延時(shí)標(biāo)準(zhǔn)方差、最大響應(yīng)延時(shí)如圖5～圖7所示。

圖5 不同任務(wù)負(fù)載下3種調(diào)度算法的平均響應(yīng)延時(shí)

圖7 不同任務(wù)負(fù)載下3種調(diào)度算法的最大響應(yīng)延時(shí)

可以看出,在測(cè)試平臺(tái)上,相比其他3種調(diào)度算法,GFS在不同計(jì)算任務(wù)數(shù)目的負(fù)載下交互任務(wù)的平均響應(yīng)延時(shí)和響應(yīng)延時(shí)標(biāo)準(zhǔn)方差上都有明顯改進(jìn)。在最大響應(yīng)延時(shí)上,GFS總體改進(jìn)不明顯,主要是因?yàn)閄_window類(lèi)應(yīng)用的請(qǐng)求比較隨機(jī)。綜合而言,GFS算法明顯提高了系統(tǒng)的交互性能。

6 結(jié)束語(yǔ)

本文針對(duì)Linux調(diào)度算法在多核系統(tǒng)中交互性能差的問(wèn)題,設(shè)計(jì)并實(shí)現(xiàn)了一種改進(jìn)的任務(wù)調(diào)度算法GFS。GFS通過(guò)CPU分組共享隊(duì)列、優(yōu)先調(diào)度喚醒任務(wù)等設(shè)計(jì)減少交互任務(wù)的響應(yīng)時(shí)間,提高多核系統(tǒng)的交互性能。下一步將在用戶態(tài)的作業(yè)調(diào)度系統(tǒng)(如Quartz的調(diào)度算法)中引入GFS,從而提升系統(tǒng)調(diào)度性能。

[1] Silberschatz A.OperatingSystemConcepts[M]. New York,USA:John Wiley&Sons Ltd.,2004.

[2] 謝偉毅,廖光燈,謝康林.Linux調(diào)度算法在桌面應(yīng)用環(huán)境中的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(23): 101-103.

[3] Groves T,Knockel J,Schulte E.BFS vs.CFS Scheduler Comparison[Z].2009.

[4] 夏 廈,李 俊.基于緩存競(jìng)爭(zhēng)優(yōu)化的Linux進(jìn)程調(diào)度策略[J].計(jì)算機(jī)工程,2013,39(4):58-61.

[5] Brain Fuck Scheduler[EB/OL].(2011-05-18).http:// en.wikipedia.org/wiki/Brain_Fuck_Scheduler#cite_ note-2.

[6] 朱 旭,楊 斌,劉海濤.完全公平調(diào)度算法分析[J].成都信息工程學(xué)院學(xué)報(bào),2010,25(1):18-21.

[7] Molnar I.Modular Scheduler Core and Completely Fair Scheduler[EB/OL].(2008-05-03).http://lwn.net/ Articles/230501.

[8] 趙 旭,夏靖波.基于RTAI的Linux系統(tǒng)實(shí)時(shí)性研究與改進(jìn)[J].計(jì)算機(jī)工程,2010,36(14):288-290.

[9] 杜慧江,王云光.Linux內(nèi)核2.6.24的CFS調(diào)度器分析[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(2):166-168.

[10] Hennessy J L,Patterson D A.計(jì)算機(jī)系統(tǒng)結(jié)構(gòu):量化研究方法[M].鄭緯民,湯志忠,汪東升,等,譯.北京:電子工業(yè)出版社,2004.

[11] 邵立松,孔金珠,戴華東.芯片級(jí)多線程處理器的操作系統(tǒng)調(diào)度研究[J].計(jì)算機(jī)工程,2009,35(15): 277-279.

[12] Kolivas C.The Homepage of Interbench[EB/OL].(2006-08-11).http://users.on.net/～ckolivas/inter-bench/.

編輯 陸燕菲

A Linux Task Scheduling Algorithm for Multi-core System

CAO Yuea,b,c,GU Naijiea,b,c,REN Kaixina,b,c,ZHANG Xua,b,c,WU Zhiqianga,b,c
(a.School of Computer Science and Technology;b.Anhui Province Key Laboratory of Computing and Communication Software; c.Institute of Advanced Technology,University of Science and Technology of China,Hefei 230027,China)

To improve interactive performance of Linux in multi-core systems,this paper designs and implements an improved task scheduling algorithm named Group Fair Schedule(GFS).According to the hardware characteristics of multi-core system,GFS allows to configure a group of CPUs with close affinity to share one task run queue automatically,so that the cost of competitive access,task migration inside a group and run queue load balance between groups can be weighed,and reduces scheduling delay.GFS gives priority to awakening tasks so that interactive performance of multi-core systems is improved.Test results show that GFS decreases the average response time of interactive tasks under different background loads,and improves interactive performance of multi-core systems effectively.

multi-core system;scheduling algorithm;interactive performance;automotive configuration;awakening task;load balance

曹 越,顧乃杰,任開(kāi)新,等.一種面向多核系統(tǒng)的Linux任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程, 2015,41(2):36-40,46.

英文引用格式:Cao Yue,Gu Naijie,Ren Kaixin,et al.A Linux Task Scheduling Algorithm for Multi-core System[J]. Computer Engineering,41(2):36-40,46.

1000-3428(2015)02-0036-05

:A

:TP311

10.3969/j.issn.1000-3428.2015.02.008

“核高基”重大專(zhuān)項(xiàng)(2009ZX01028-002-003-005);高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃基金資助項(xiàng)目(B07033)。

曹 越(1990-),男,碩士研究生,主研方向:并行計(jì)算,流程優(yōu)化;顧乃杰(通訊作者),教授、博士生導(dǎo)師;任開(kāi)新,講師;張 旭,博士研究生;吳志強(qiáng),碩士研究生。

2014-03-24

:2014-04-16E-mail:caoyue@mail.ustc.edu.cn