發布時間：所屬分類：計算機職稱論文瀏覽：1次
摘 要： 摘要:在多核系統中，針對Linux的調度算法對交互式任務響應實時不足的問題，設計并提出了一種改進的交互式、多層次的任務調度GAS模型.該模型通過相近度對CPU實現分組，組內的CPU共享任務隊列;通過改進多任務時負載均衡與任務遷移的開銷，降低了交互式場景下任
摘要:在多核系統中，針對Linux的調度算法對交互式任務響應實時不足的問題，設計并提出了一種改進的交互式、多層次的任務調度GAS模型.該模型通過相近度對CPU實現分組，組內的CPU共享任務隊列;通過改進多任務時負載均衡與任務遷移的開銷，降低了交互式場景下任務的響應時長，提高了Linux多核多任務的任務執行性能;通過喚醒任務優先執行的機制，提高了交互任務的響應效率.實驗結果表明，在不同任務數情況下，GAS算法的平均響應時長和最大響應時長都優于BFS算法和CFS算法.
關鍵詞:多核系統;任務遷移;任務隊列;交互式任務;負載均衡
Linux由于其優秀的可擴展性和安全穩定性，使其在PC家用機、嵌入式等領域占據很大市場份額，Linux的調度算法也力求支持不同的領域場景.但PC家用機主要側重于任務低響應時長，巨型機主要側重于高吞吐量，嵌入式主要側重于低開銷，而多核領域的實時交互響應則非現有Linux調度策略所擅長[1].主要是Linux的CFS(CompletelyFairSchedule)算法側重于實現高吞吐量，對于實時響應、快速喚醒等要求難以滿足.
針對多核實時任務調度響應慢的問題，文獻[2]提出了利用緩存增加任務之間的競爭性以提高任務輪詢的效率，增強多任務響應效率，但該算法的開銷較高.文獻[3]提出了讓多核共享同一任務隊列以降低實時交互的響應時長的BFS(BrainFuckSchedule)算法，該算法雖然能夠有效的降低響應時長但當任務數偏多時則因為多隊列競爭開銷大，效率明顯下降.基于此，提出了基于任務分組的GAS(GroupTaskSchedule)調度策略，將相近的任務分配至同一組內，以降低組內任務切換時CPU遷移開銷，同時可以根據負載情況進行組間的均衡處理.
1GAS整體設計
為了解決BFS難以適用于多任務情況中，GAS按照任務相近性進行分組配置，一般多核系統中任務相近度分為四種情況:(1)非統一內存訪問間(NonUniformMemoryAccessArchitecture，NUMA)具有獨立的內存空間;(2)同一個NUMA結點內占用不同CPU，但獨占Cache;(3)占據一個CPU內的不同核，獨占不同的L1_Cache，但多任務共享L2_Cache;(4)共享同一個處理核，且共享L1_Cache[4-5].
存儲介質的訪問時長各為:內存為75ns±25，L1_Cache為1ns，L2_Cache為3ns～10ns，將任務訪問時長相近的分配到組內，使CPU的任務遷移導致存儲空間的刷新時間會降低.GAS算法為每個組創建了紅黑樹結構實現的任務管理隊列，為每個CPU創建雙向鏈表結構的任務喚醒隊列，結構如圖1所示.
當新建任務時需要先計算任務的虛擬結束時間vdeadline，計算公式如式(1)所示，其中jiffies表示當前時間，prio_ration表征任務的優先級，rr_interva表示時間片長.
vdeadline=jiffies+prio_ration×rr_interval(1)
后將任務插入到CPU隊列紅黑樹中，首先檢查隊所有列數中是否存在空閑CPU或在執行的任務的vdeadline大于新的時間，則觸發中斷將任務加入到該CPU任務隊列中.
當需要進行任務喚醒操作時，如果是睡眠前vdeadline不改變，并檢查各Group內的CPU是否已經空閑或任務的vdeadline大于新的時間，則在CPU的雙向鏈表中插入該任務，并觸發中斷將任務加入到該CPU任務隊列中.
GAS模型的調度操作流程分為下面兩個步驟.
(1)通過周期調度器scheduler_tick計算各任務運行時長，如果超時則添加調度標記，如果各Group間任務負載失衡，則進行Group任務重新分組和遷移;
(2)scheduler()函數實現了將任務插入到對應Group的隊列紅黑樹中，如果任務的時間片已結束則刷新時間片和vdeadline，在進行調度時優先選擇CPU的雙向鏈表.
任務調度時要先查看雙向鏈表，再索引紅黑樹，如果任務滿足喚醒條件則加入到雙向鏈表中并啟動中斷機制加入到CPU中，該機制降低了喚醒任務的響應時長，提高了效率.如果現有K個CPU、M個任務、N個Group，則任務新建與任務喚醒的時間復雜度為O(K/N+lg(M/N)，插入和刪除任務的時間復雜度為O(lg(M/N)，調度的開銷一般為O(lg(M/N).
2GAS算法實現
2.1分組設計
Linux內置的調度模塊初始化函數是sched_init()[6]，GAS算法的初始化策略是通過為每個CPU創建指向主任務隊列的指針和指向高級任務隊列的指針.為了實現分組的功能，GAS模型為每個CPU創建二維數組，用于存儲CPU和其余CPU的相近性關系，GAS模型對處理器中的CPU進行遍歷，實現CPU的自適應分組.
Linux內置的用于初始化任務遷移函數是migration_init()，如果GAS模型發現CPU與其他組的CPU相近度更高，則將該CPU重新選定分組.同一個分組內的CPU由于共享L2_Cache，所以在同一個分組內遷移任務的開銷更低.如果自動分配的分組不能滿足要求，也可以通過sysset_mainq_cpu()函數實現人工手動調整CPU的任務隊列，實現更合理的分組.
2.2調度函數設計與實現
2.2.1周期調度函數設計
GAS算法的周期調度函數scheduler_tick()在BFS算法的基礎上改進了多任務時的負載均衡管理，以提高多任務存在時的并行能力，負載均衡的代價是任務均衡調度期間需要對執行隊列加鎖、調用任務遷移功能等操作，所以負載均衡的次數要盡量降低且執行時需要選擇合適的時機.
GAS算法按照CPU、CORE、PHY和NUMA四個層次進行遍歷，將遍歷的結果保存到紅黑樹型結構中.GAS從最底層開始進行遍歷，直到遍歷完最高層的節點為止.任務的調度和分組的粒度有關，如果分組時將核內的所有CPU置于一個組內，則索引的最低級別是CORE，與粒度掛鉤的機制也降低了負載均衡的負擔和復雜度.
2.2.2調度器函數設計
Linux系統中提取任務至執行態使用scheduler()函數，首先查看雙向鏈表，之后索引紅黑樹.如果雙向鏈表中存在任務，則雙向鏈表中任務的vdeadline已經按照由小至大的順序進行排序，所以直接選取第一個任務作為待執行任務即可;如果沒有任務，則從紅黑樹中選取最左側葉子節點作為待執行節點.之后繼續掃描，直至所有任務執行完畢.如果經過掃描發現隊列中沒有待執行的任務，則將對應的CPU標記為空閑狀態.
2.3任務喚醒
執行任務喚醒的一個關鍵步驟是選取CPU，GAS模型使用數組維持CPU相近度的管理，在選取CPU時，最優先選取被標記為空閑狀態的CPU;如無空閑狀態的CPU，則遍歷所有CPU，索引出相似度最高的空閑CPU執行，否則選取vdeadline比自身大的CPU.任務在被喚醒后，需要分配至主任務隊列中，之后按照隊列與分組對應關系分配CPU，找到CPU后將任務插入到對應的任務隊列中等待調用執行.
3實驗與結果分析
本文選取的Linux系統版本為centos6.3，內核版本為Linux3.6.2，處理器配置為4核8CPU的IntelCorei7-67003.4GHz.系統性能檢測工具選用Interbench-0.31，Interbench能夠有效采集和監測系統的響應時長數據.
如圖2和圖3所示，分別為BFS算法、CFS算法和GAS算法的平均響應時長對比結果和最大響應時長的對比結果，任務數量的取值區間為8～48，每次增長8個任務.從圖中可以看出，GAS算法的最大響應時長和平均響應時長都較優于BFS算法和CFS算法.
4結論針對Linux系統在交互式任務場景下的任務響應實時不足的問題，設計并實現了改進的交互式、多層次的任務調度GAS模型.通過Group內共享任務隊列、喚醒任務優先執行等機制的設計，降低了交互式場景下任務的響應時長，提高了Linux多核多任務的任務執行性能.通過Interbench工具的性能檢測發現，交互式任務場景下改進的GAS算法的性能較CFS算法、BFS算法的性能更高.
相關期刊推薦：《西安文理學院學報(自然科學版)》(季刊)創刊于1994年，是經國家新聞出版署批準國內外公開發行的綜合性學術刊物，國內外公開發行。主要刊登生命科學、數學及應用數學、物理學、化學與化學工程、機械電子技術、計算機科學與技術、環境資源與地理科學等方面有創新、有參考價值的研究論文、綜述和研究進展，具有領先水平的科研成果，學術報告和動態等.讀者對象為科研工作者、高等學校教師和研究生等。
