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

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

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

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

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

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

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

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

1 概述

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

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

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

2 相關知識

2.1 Linux調度器

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

2.2 CFS任務調度算法

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

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

圖1 CFS任務運行隊列架構

由于任務運行隊列以紅黑樹作為數據結構,隊列中虛擬運行時間最小的任務為紅黑樹最左側的任務。

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

CFS調度器核心操作的主要流程如下:

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

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

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

2.3 BFS任務調度算法

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

圖2 BFS任務運行隊列架構

任務的虛擬最后期限計算公式為:

vdeadline=jiffies+prio_ratio×rr_interval

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

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

BFS調度器核心操作的主要流程如下:

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

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

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

3 GFS算法設計

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

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

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

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

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

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

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

圖3 GFS任務運行隊列架構

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

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

GFS調度器核心操作的主要流程分析如下:

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

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

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

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

4 GFS算法實現(xiàn)

4.1 CPU分組配置

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

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

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

4.2 調度函數

4.2.1 scheduler_tick函數

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

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

圖4 調度域層次結構

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

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

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

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

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

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

4.2.2 schedule函數

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

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

4.3 任務喚醒

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

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

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

5 測試結果與分析

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

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

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

5.2 結果分析

不同任務負載下3種調度算法的平均響應延時、響應延時標準方差、最大響應延時如圖5～圖7所示。

圖5 不同任務負載下3種調度算法的平均響應延時

圖7 不同任務負載下3種調度算法的最大響應延時

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

6 結束語

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

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

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

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

[4] 夏 廈,李 俊.基于緩存競爭優(yōu)化的Linux進程調度策略[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] 朱 旭,楊 斌,劉海濤.完全公平調度算法分析[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內核2.6.24的CFS調度器分析[J].計算機應用與軟件,2010,27(2):166-168.

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

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