曹 越,顧乃杰,任開新,張 旭,吳志強

(中國科學技術(shù)大學a.計算機科學與技術(shù)學院;b.安徽省計算與通信軟件重點實驗室;c.先進技術(shù)研究院,合肥230027)

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

曹 越a,b,c,顧乃杰a,b,c,任開新a,b,c,張 旭a,b,c,吳志強a,b,c

(中國科學技術(shù)大學a.計算機科學與技術(shù)學院;b.安徽省計算與通信軟件重點實驗室;c.先進技術(shù)研究院,合肥230027)

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

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

1 概述

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

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

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

2 相關(guān)知識

2.1 Linux調(diào)度器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

vdeadline=jiffies+prio_ratio×rr_interval

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

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

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

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

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

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

3 GFS算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 GFS算法實現(xiàn)

4.1 CPU分組配置

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

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

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

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

4.2.1 scheduler_tick函數(shù)

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

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

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

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

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

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

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

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

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

4.2.2 schedule函數(shù)

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

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

4.3 任務(wù)喚醒

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

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

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

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

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

為直觀反映GFS的性能,本節(jié)對CFS、BFS、緩存競爭調(diào)度算法及GFS進行性能測試。測試平臺環(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)核版本為Linux3.6.2。GFS自動配置同一核下的所有CPU為一個分組。

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

5.2 結(jié)果分析

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

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

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

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

6 結(jié)束語

本文針對Linux調(diào)度算法在多核系統(tǒng)中交互性能差的問題,設(shè)計并實現(xiàn)了一種改進的任務(wù)調(diào)度算法GFS。GFS通過CPU分組共享隊列、優(yōu)先調(diào)度喚醒任務(wù)等設(shè)計減少交互任務(wù)的響應(yīng)時間,提高多核系統(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].計算機工程與應(yīng)用,2006,42(23): 101-103.

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

[4] 夏 廈,李 俊.基于緩存競爭優(yōu)化的Linux進程調(diào)度策略[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].成都信息工程學院學報,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)實時性研究與改進[J].計算機工程,2010,36(14):288-290.

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

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

[11] 邵立松,孔金珠,戴華東.芯片級多線程處理器的操作系統(tǒng)調(diào)度研究[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

曹 越,顧乃杰,任開新,等.一種面向多核系統(tǒng)的Linux任務(wù)調(diào)度算法[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

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

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

2014-03-24

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