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