• 碩博初稿查重系統(tǒng) 498.00元/篇
  ? 語(yǔ)種：中文,英文,小語(yǔ)種? 適用：雜志社投稿，職稱論文? 簡(jiǎn)介：碩博初稿檢測(cè)（一般習(xí)慣叫做碩博預(yù)審版），論文查重檢測(cè)上千萬篇中文文獻(xiàn)，超百萬篇各類獨(dú)家文獻(xiàn)，超百萬港澳臺(tái)地區(qū)學(xué)術(shù)文獻(xiàn)過千...

  開始檢測(cè)
• 維普查重(大學(xué)生版） 4.00元/千字
  ? 語(yǔ)種：中文,英文? 適用：雜志社投稿，職稱論文? 簡(jiǎn)介：學(xué)位論文查重,維普大學(xué)生版論文查重系統(tǒng)：高校，雜志社指定系統(tǒng)，可檢測(cè)期刊發(fā)表，大學(xué)生，碩博等論文。檢測(cè)報(bào)告支持PDF、網(wǎng)...

  開始檢測(cè)
• 本科高校內(nèi)部版系統(tǒng) 288.00元/篇
  ? 語(yǔ)種：中文,英文,小語(yǔ)種? 適用：雜志社投稿，職稱論文? 簡(jiǎn)介：比定稿版少大學(xué)生聯(lián)合比對(duì)庫(kù)，其他數(shù)據(jù)庫(kù)一致。出結(jié)果快，價(jià)格相對(duì)低廉，不支持驗(yàn)證，適合在修改中期使用，定稿推薦PMLC?！?..

  開始檢測(cè)
• 萬方論文查重系統(tǒng) 4.00元/千字
  ? 語(yǔ)種：中文? 適用：雜志社投稿，職稱論文? 簡(jiǎn)介：畢業(yè)論文查重,萬方查重系統(tǒng)，涵蓋期刊、學(xué)位論文、學(xué)術(shù)成果、學(xué)術(shù)會(huì)議論文的大型網(wǎng)絡(luò)數(shù)據(jù)庫(kù)；比肩中國(guó)知網(wǎng)的學(xué)術(shù)數(shù)據(jù)庫(kù)。最多支...

  開始檢測(cè)

摘要:在多核系統(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í)長(zhǎng)，提高了Linux多核多任務(wù)的任務(wù)執(zhí)行性能;通過喚醒任務(wù)優(yōu)先執(zhí)行的機(jī)制，提高了交互任務(wù)的響應(yīng)效率.實(shí)驗(yàn)結(jié)果表明，在不同任務(wù)數(shù)情況下，GAS算法的平均響應(yīng)時(shí)長(zhǎng)和最大響應(yīng)時(shí)長(zhǎng)都優(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í)長(zhǎng)，巨型機(jī)主要側(cè)重于高吞吐量，嵌入式主要側(cè)重于低開銷，而多核領(lǐng)域的實(shí)時(shí)交互響應(yīng)則非現(xiàn)有Linux調(diào)度策略所擅長(zhǎng)[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)爭(zhēng)性以提高任務(wù)輪詢的效率，增強(qiáng)多任務(wù)響應(yīng)效率，但該算法的開銷較高.文獻(xiàn)[3]提出了讓多核共享同一任務(wù)隊(duì)列以降低實(shí)時(shí)交互的響應(yīng)時(shí)長(zhǎng)的BFS(BrainFuckSchedule)算法，該算法雖然能夠有效的降低響應(yīng)時(shí)長(zhǎng)但當(dāng)任務(wù)數(shù)偏多時(shí)則因?yàn)槎嚓?duì)列競(jìng)爭(zhē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í)長(zhǎng)各為:內(nèi)存為75ns±25，L1_Cache為1ns，L2_Cache為3ns～10ns，將任務(wù)訪問時(shí)長(zhǎng)相近的分配到組內(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í)間片長(zhǎng).

　　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í)長(zhǎng)，如果超時(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í)長(zhǎng)，提高了效率.如果現(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)核版本為L(zhǎng)inux3.6.2，處理器配置為4核8CPU的IntelCorei7-67003.4GHz.系統(tǒng)性能檢測(cè)工具選用Interbench-0.31，Interbench能夠有效采集和監(jiān)測(cè)系統(tǒng)的響應(yīng)時(shí)長(zhǎng)數(shù)據(jù).

　　如圖2和圖3所示，分別為BFS算法、CFS算法和GAS算法的平均響應(yīng)時(shí)長(zhǎng)對(duì)比結(jié)果和最大響應(yīng)時(shí)長(zhǎng)的對(duì)比結(jié)果，任務(wù)數(shù)量的取值區(qū)間為8～48，每次增長(zhǎng)8個(gè)任務(wù).從圖中可以看出，GAS算法的最大響應(yīng)時(shí)長(zhǎng)和平均響應(yīng)時(shí)長(zhǎng)都較優(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í)長(zhǎng)，提高了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)國(guó)家新聞出版署批準(zhǔn)國(guó)內(nèi)外公開發(fā)行的綜合性學(xué)術(shù)刊物，國(guó)內(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é)校教師和研究生等。

知網(wǎng)論文查重：http://m.jiarunkj.com