耦合分布式系統(tǒng)多任務(wù)動(dòng)態(tài)調(diào)度算法

劉金波;黃海于【摘要】針對(duì)耦合分布式系統(tǒng)中一個(gè)計(jì)算模塊獨(dú)自占用某臺(tái)計(jì)算資源，導(dǎo)致其他計(jì)算模塊無(wú)法調(diào)度到該計(jì)算資源的情況，提出了一種動(dòng)態(tài)任務(wù)分配的調(diào)度算法.該算法能夠根據(jù)計(jì)算任務(wù)的調(diào)度要求和計(jì)算資源的運(yùn)行狀態(tài)，動(dòng)態(tài)進(jìn)行任務(wù)分配，使計(jì)算能力強(qiáng)的計(jì)算資源能夠運(yùn)行更多的計(jì)算模塊，從而實(shí)現(xiàn)多計(jì)算任務(wù)調(diào)度，使多個(gè)符合調(diào)度要求的計(jì)算任務(wù)同時(shí)處于運(yùn)行狀態(tài)，提高計(jì)算資源的利用率，保證了計(jì)算任務(wù)調(diào)度的有效性和高效性.仿真結(jié)果表明,該多任務(wù)動(dòng)態(tài)調(diào)度算法能夠在不影響計(jì)算速度的情況下，使一臺(tái)計(jì)算資源同時(shí)為多個(gè)計(jì)算任務(wù)提供計(jì)算能力，大大提高了計(jì)算資源的利用率，并且使原本因計(jì)算資源的限制而無(wú)法運(yùn)行的計(jì)算任務(wù)能夠提前開(kāi)始運(yùn)行，提高了計(jì)算任務(wù)調(diào)度的高效性和靈活性.％Inacoupling-distributedsystem,onecalculationtaskisdistributedinasinglecomputingnodesothatothertaskscannotbedis-tributedinthesamecomputingnode,evenwithastrongcomputingpower.Anewdynamictaskassignmentalgorithmisproposed.Itcanassigncalculationtaskaccordingtotheschedulingrequirementsofcomputingtaskandrunningstateofcomputingresources,whichmakescalculationresourceswithpowerfulcomputingcapableofrunningmorecalculationmodulesforimplementationofmultitasksschedu-ling,andwhichenablescomputingtasksofmeetingschedulingneedsintherunningstatesimultaneously,improvingtheutilizationofcomputationalresourcesandensuretheeffectivenessandefficiencyofscheduling.Thesimulationshowsthattheproposedalgorithmcangreatlyimprovetheutilizationofcomputingresources,notonlyensuringthecomputingspeedbutalsoprovidingcomputingpowerformultiplecomputationaltasksatthesametime.Thecomputationaltasksthatcannotbeperformedduetoconditionalconstraintscanrunintime,thusimprovingtheefficiencyandflexibilityoftheschedulingsystem.【期刊名稱】《計(jì)算機(jī)技術(shù)與發(fā)展》【年(卷)，期】2017(027)012【總頁(yè)數(shù)】4頁(yè)(P16-19)【關(guān)鍵詞】分布式系統(tǒng);多任務(wù);動(dòng)態(tài)分配;利用率【作者】劉金波;黃海于【作者單位】西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都611756;西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，四川成都611756【正文語(yǔ)種】中文【中圖分類】TP302高速列車數(shù)字化仿真平臺(tái)采用分布式體系結(jié)構(gòu)［1-2］，資源管理及任務(wù)調(diào)度子系統(tǒng)是平臺(tái)下的一個(gè)子系統(tǒng)。在分布式體系結(jié)構(gòu)中［3-6］，任務(wù)調(diào)度是非常重要的一環(huán)。如何有效地利用分布式系統(tǒng)中的計(jì)算資源以及如何對(duì)現(xiàn)有的計(jì)算任務(wù)進(jìn)行調(diào)度，均是任務(wù)調(diào)度子系統(tǒng)必須考慮的問(wèn)題。分布式系統(tǒng)以及云計(jì)算中的調(diào)度問(wèn)題一直都是研究人員研究的熱點(diǎn)。為解決分布式系統(tǒng)中的任務(wù)調(diào)度問(wèn)題，研究人員提出了很多調(diào)度策略，例如排隊(duì)理論、圖論、決策論以及啟發(fā)式調(diào)度方法等［7-11］。耦合分布式系統(tǒng)原有的調(diào)度算法［12］為每個(gè)計(jì)算模塊分配一臺(tái)計(jì)算資源，如果該計(jì)算模塊只占用很少的計(jì)算資源，而其他的計(jì)算模塊又不能調(diào)度到該計(jì)算資源上，不僅會(huì)造成計(jì)算資源的極大浪費(fèi)，也會(huì)使得大量的計(jì)算任務(wù)處于阻塞狀態(tài)，無(wú)法進(jìn)行計(jì)算。文獻(xiàn)［13］提出一種耦合分布式系統(tǒng)多線程任務(wù)管理算法，可以將多個(gè)計(jì)算模塊調(diào)度到一臺(tái)計(jì)算資源上。但是該算法存在三點(diǎn)不足：一是以多線程的方式管理各個(gè)計(jì)算模塊，多個(gè)線程共用一個(gè)端口，采用互斥的方式與耦合器進(jìn)行數(shù)據(jù)交互，理論上這種方法比多進(jìn)程的方式效率要低；二是這種算法只能將同一計(jì)算任務(wù)的多個(gè)計(jì)算模塊分配給一臺(tái)計(jì)算資源，實(shí)質(zhì)上是一種靜態(tài)任務(wù)調(diào)度算法；三是無(wú)法根據(jù)計(jì)算資源的實(shí)際使用情況進(jìn)行任務(wù)分配，可能將多個(gè)模塊分配給一臺(tái)計(jì)算能力不佳的計(jì)算資源?？紤]到計(jì)算模塊是以進(jìn)程的形式存在，一臺(tái)計(jì)算機(jī)上可以運(yùn)行多個(gè)進(jìn)程，一臺(tái)計(jì)算資源不應(yīng)只服務(wù)于一個(gè)計(jì)算任務(wù)，在條件允許的情況下也要為其他計(jì)算任務(wù)提供計(jì)算能力。因此，在不影響計(jì)算效率的前提下，可以考慮將多個(gè)計(jì)算模塊調(diào)度到一臺(tái)計(jì)算資源上進(jìn)行計(jì)算?；诖?，文中提出了一種動(dòng)態(tài)的任務(wù)調(diào)度算法。該算法可以根據(jù)當(dāng)前所有計(jì)算資源的實(shí)際使用情況以及用戶提交的計(jì)算任務(wù)，為計(jì)算任務(wù)中的每個(gè)計(jì)算模塊尋找最合適的計(jì)算資源。耦合分布式系統(tǒng)結(jié)構(gòu)如圖1所示。該分布式系統(tǒng)主要包含客戶機(jī)、作業(yè)調(diào)度器、耦合器以及計(jì)算資源。計(jì)算任務(wù)由多個(gè)計(jì)算模塊組成，這些計(jì)算模塊經(jīng)過(guò)調(diào)度器進(jìn)行調(diào)度后可以運(yùn)行在多個(gè)計(jì)算資源上。作業(yè)調(diào)度器負(fù)責(zé)接收用戶提交的計(jì)算任務(wù)并將其存放在任務(wù)隊(duì)列中，同時(shí)作業(yè)調(diào)度器也會(huì)維護(hù)一個(gè)計(jì)算資源鏈表，通過(guò)循環(huán)遍歷計(jì)算任務(wù)隊(duì)列以及計(jì)算資源隊(duì)列來(lái)對(duì)計(jì)算任務(wù)進(jìn)行調(diào)度，因此高效的調(diào)度算法能夠合理地利用現(xiàn)有的計(jì)算資源，并且使盡可能多的計(jì)算任務(wù)同時(shí)處于運(yùn)行狀態(tài)。耦合器是整個(gè)分布式計(jì)算平臺(tái)的數(shù)據(jù)交互中心［14］。調(diào)度器在完成對(duì)某一個(gè)計(jì)算任務(wù)的調(diào)度后會(huì)指定一個(gè)耦合器作為該計(jì)算任務(wù)的數(shù)據(jù)交互中心和控制中心，該計(jì)算任務(wù)的所有數(shù)據(jù)都會(huì)經(jīng)過(guò)耦合器轉(zhuǎn)發(fā)到相應(yīng)的目的模塊。分布式計(jì)算平臺(tái)中可以有多個(gè)耦合器，每個(gè)耦合器也可以同時(shí)管理多個(gè)工況的耦合計(jì)算，調(diào)度器根據(jù)每個(gè)耦合器的性能狀態(tài)來(lái)進(jìn)行任務(wù)的分配。計(jì)算資源與調(diào)度器和耦合器處在同一個(gè)局域網(wǎng)下，為大規(guī)模的計(jì)算任務(wù)提供計(jì)算能力。計(jì)算資源上需要運(yùn)行代理軟件，通過(guò)代理軟件接收調(diào)度器分配的計(jì)算任務(wù)，然后從數(shù)據(jù)庫(kù)中下載相應(yīng)的配置文件與可執(zhí)行程序，可執(zhí)行程序包含了計(jì)算任務(wù)的求解過(guò)程，代理啟動(dòng)該模塊的可執(zhí)行程序進(jìn)行計(jì)算。客戶機(jī)是用戶與分布式計(jì)算平臺(tái)進(jìn)行交互的接口。用戶可以通過(guò)客戶機(jī)進(jìn)行計(jì)算任務(wù)的生成以及配置，同時(shí)可以將計(jì)算任務(wù)提交給調(diào)度器進(jìn)行計(jì)算，此外用戶也可以通過(guò)客戶機(jī)對(duì)某個(gè)正在運(yùn)行的計(jì)算任務(wù)進(jìn)行過(guò)程監(jiān)控。計(jì)算任務(wù)是由一系列的子模塊構(gòu)成，調(diào)度的過(guò)程就是為計(jì)算任務(wù)的各個(gè)子模塊尋找計(jì)算資源。動(dòng)態(tài)任務(wù)分配算法的描述如下：解析一個(gè)未被調(diào)度的計(jì)算任務(wù)；判斷其中固定IP的計(jì)算模塊能否調(diào)度成功，不能則返回到(1)，解析下一個(gè)未被調(diào)度的計(jì)算任務(wù)；調(diào)度獨(dú)占計(jì)算資源的模塊，調(diào)度失敗則返回到(1)，解析下一個(gè)未被調(diào)度的計(jì)算任務(wù)，如果調(diào)度成功，鎖定該計(jì)算資源，在該計(jì)算任務(wù)完成計(jì)算之前，該計(jì)算資源不會(huì)參與到以后任務(wù)的調(diào)度；調(diào)度所有的一般模塊，優(yōu)先將一般模塊調(diào)度給空閑的計(jì)算資源，如果沒(méi)有空閑的計(jì)算資源，則將所有的可用計(jì)算資源按照負(fù)載評(píng)價(jià)方法進(jìn)行排序，選擇最合適的計(jì)算資源。調(diào)度器在進(jìn)行任務(wù)的調(diào)度時(shí)，需要對(duì)每臺(tái)計(jì)算資源的計(jì)算能力進(jìn)行評(píng)價(jià)，計(jì)算負(fù)載參數(shù)W,以此來(lái)判斷當(dāng)前的計(jì)算資源能否用于任務(wù)調(diào)度。對(duì)一臺(tái)計(jì)算資源的評(píng)價(jià)主要通過(guò)以下幾個(gè)參數(shù)來(lái)進(jìn)行衡量：CPU利用率M；網(wǎng)絡(luò)流量S；內(nèi)存利用率U;磁盤(pán)利用率D。在判斷過(guò)程中需要綜合衡量各個(gè)參數(shù)對(duì)調(diào)度任務(wù)的影響，負(fù)載參數(shù)的計(jì)算公式如下：W=X1*M+X2*S+X3*U+X4*D其中,xi(x1+x2+x3+x4=1且xi>0)分別為CPU的利用率、網(wǎng)絡(luò)流量、內(nèi)存利用率、磁盤(pán)利用率對(duì)應(yīng)的權(quán)值。為這些參數(shù)設(shè)置不同的權(quán)值可以使某個(gè)參數(shù)影響到最終的調(diào)度結(jié)果。例如，如果希望將計(jì)算任務(wù)調(diào)度到通信狀況良好的計(jì)算資源上，可以將x2的權(quán)值調(diào)大，以此來(lái)影響任務(wù)的調(diào)度。負(fù)載值越大，說(shuō)明該計(jì)算節(jié)點(diǎn)計(jì)算任務(wù)越繁重，不應(yīng)該優(yōu)先被分配計(jì)算任務(wù)。如果某個(gè)參數(shù)過(guò)大，例如CPU的利用率已達(dá)到80%，應(yīng)該將該計(jì)算資源暫時(shí)剔除計(jì)算資源隊(duì)列。以上的參數(shù)信息由運(yùn)行在計(jì)算資源上的代理軟件獲取，以固定的時(shí)間間隔以心跳信號(hào)的形式發(fā)送給調(diào)度器。調(diào)度器為每臺(tái)計(jì)算資源保留最近五十步的心跳信號(hào)，每次進(jìn)行任務(wù)調(diào)度時(shí)，取最近20步的心跳信號(hào)，計(jì)算CPU利用率、網(wǎng)絡(luò)流量、內(nèi)存利用率、磁盤(pán)利用率的均值，然后根據(jù)上述公式計(jì)算每臺(tái)計(jì)算資源的負(fù)載值，選取負(fù)載最低的計(jì)算資源進(jìn)行任務(wù)分配。為了保證評(píng)價(jià)的準(zhǔn)確性，每當(dāng)一個(gè)計(jì)算任務(wù)調(diào)度成功后，調(diào)度器端會(huì)清空該計(jì)算任務(wù)占用的計(jì)算模塊所對(duì)應(yīng)的心跳信號(hào)，以保證數(shù)據(jù)的準(zhǔn)確性。動(dòng)態(tài)任務(wù)分配算法能夠?qū)⒉煌?jì)算任務(wù)的模塊調(diào)度到同一臺(tái)計(jì)算資源上，因此調(diào)度器需要盡可能多地了解計(jì)算任務(wù)中每個(gè)計(jì)算模塊的計(jì)算要求。例如，某個(gè)模塊的運(yùn)行對(duì)內(nèi)存要求很高或者對(duì)實(shí)時(shí)性要求很高，可以將其設(shè)置為獨(dú)占計(jì)算資源；具體來(lái)說(shuō)，需要設(shè)置的參數(shù)有：該計(jì)算模塊是否獨(dú)立運(yùn)行；運(yùn)行至少需要多大的內(nèi)存；對(duì)操作系統(tǒng)的要求，例如運(yùn)行于Windows或者Linux系統(tǒng)下；運(yùn)行在哪個(gè)IP地址的計(jì)算資源上等。以上這些參數(shù)均作為某個(gè)模塊的調(diào)度參數(shù)，會(huì)影響到調(diào)度結(jié)果。這些調(diào)度參數(shù)由用戶在構(gòu)建計(jì)算任務(wù)時(shí)為每個(gè)計(jì)算模塊進(jìn)行配置。調(diào)度器運(yùn)行過(guò)程中會(huì)循環(huán)掃描任務(wù)隊(duì)列和計(jì)算資源列表，在分配的過(guò)程中，如果該計(jì)算模塊是獨(dú)占計(jì)算資源模塊，則需要將該模塊占用的計(jì)算資源鎖定，在該模塊未完成計(jì)算之前，其他的計(jì)算模塊無(wú)法調(diào)度到該計(jì)算資源。調(diào)度算法的流程如圖2所示。每次的調(diào)度過(guò)程總是優(yōu)先將計(jì)算模塊調(diào)度給空閑的計(jì)算資源，當(dāng)沒(méi)有空閑的計(jì)算資源時(shí)，再嘗試將模塊分配給已經(jīng)有計(jì)算任務(wù)的計(jì)算資源。計(jì)算資源匹配算法流程如圖3所示。資源匹配算法主要針對(duì)非固定IP和非獨(dú)占計(jì)算資源的一般模塊，通過(guò)采用式(1)的資源負(fù)載評(píng)價(jià)方法篩選出合適的資源。算法描述如下：遍歷每臺(tái)計(jì)算資源的心跳信號(hào)鏈表，找到心跳信號(hào)步數(shù)大于50的計(jì)算資源，心跳信號(hào)小于50步表示該計(jì)算資源剛剛分配計(jì)算任務(wù)，不參與此次調(diào)度；取最近的20步心跳信號(hào)，按照式(1)計(jì)算每臺(tái)計(jì)算資源的負(fù)載值。在當(dāng)前的耦合分布式計(jì)算平臺(tái)中，優(yōu)先考慮內(nèi)存利用率以及CPU利用率的影響。其中內(nèi)存利用率與CPU利用率分別占0.3的權(quán)值，網(wǎng)絡(luò)流量與磁盤(pán)使用率分別占0.2的權(quán)值，以此來(lái)估算每臺(tái)計(jì)算資源的負(fù)載；找到負(fù)載值最小的計(jì)算資源，將計(jì)算模塊分配給該計(jì)算資源。為了驗(yàn)證耦合分布式系統(tǒng)多任務(wù)動(dòng)態(tài)調(diào)度算法的有效性，構(gòu)建了如下的實(shí)驗(yàn)環(huán)境：仿真計(jì)算采用八臺(tái)計(jì)算資源，其中一臺(tái)運(yùn)行調(diào)度器，一臺(tái)充當(dāng)耦合器，剩下的六臺(tái)作為計(jì)算資源。所有的計(jì)算機(jī)全運(yùn)行在百兆局域網(wǎng)內(nèi)，同時(shí)提交一個(gè)分布式人臉識(shí)別和車線弓計(jì)算任務(wù)。其中在人臉識(shí)別的計(jì)算任務(wù)中，三個(gè)人臉識(shí)別模塊是獨(dú)占并且綁定固定IP的計(jì)算模塊，車線弓的計(jì)算任務(wù)需要三臺(tái)計(jì)算資源。按照原有的算法，運(yùn)行這兩個(gè)計(jì)算任務(wù)至少需要九臺(tái)空閑的計(jì)算資源才能進(jìn)行計(jì)算，而按照新的算法，理論上只需要六臺(tái)空閑的計(jì)算資源。首先使用原有的調(diào)度算法。由于計(jì)算資源數(shù)量的限制，對(duì)兩個(gè)計(jì)算任務(wù)分兩次提交，單獨(dú)測(cè)試計(jì)算時(shí)間，然后再采用動(dòng)態(tài)任務(wù)分配算法，同時(shí)提交車線弓與分布式人臉識(shí)別的計(jì)算任務(wù)，測(cè)試兩種計(jì)算任務(wù)在兩種調(diào)度算法下的運(yùn)行時(shí)間。表1列出了采用兩種調(diào)度算法完成車線弓計(jì)算任務(wù)的計(jì)算時(shí)間。表2列出了分布式人臉識(shí)別計(jì)算任務(wù)運(yùn)行所用的時(shí)間。由表1和表2可以看出，兩種計(jì)算任務(wù)的運(yùn)行時(shí)間相差不大，但是動(dòng)態(tài)任務(wù)調(diào)度算法相比原調(diào)度算法可以節(jié)省三臺(tái)計(jì)算資源，同時(shí)能夠保證更多的計(jì)算任務(wù)都處于運(yùn)行狀態(tài)。詳細(xì)介紹了耦合分布式系統(tǒng)動(dòng)態(tài)任務(wù)分配算法的實(shí)現(xiàn)。仿真結(jié)果顯示，該動(dòng)態(tài)任務(wù)分配算法能夠根據(jù)每臺(tái)計(jì)算資源的實(shí)際負(fù)載情況進(jìn)行動(dòng)態(tài)的任務(wù)調(diào)度，能夠?qū)崿F(xiàn)計(jì)算資源的合理利用，同時(shí)保證計(jì)算任務(wù)的計(jì)算速度不會(huì)受到太大影響，從而提高了計(jì)算資源的使用效率，同時(shí)也使得盡可能多的計(jì)算任務(wù)同時(shí)進(jìn)行，提高了任務(wù)調(diào)度的效率。【相關(guān)文獻(xiàn)】張衛(wèi)華.高速列車耦合大系統(tǒng)動(dòng)力學(xué)理論與實(shí)踐[M].北京：科學(xué)出版社，2013:144-151.萬(wàn)春陽(yáng)，黃海于.分布式仿真系統(tǒng)的數(shù)據(jù)監(jiān)控軟件的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013,23(9):14-17.D'AngeloG,MarzollaM.Newtrendsinparallelanddistributedsimulation:frommanycorestocloudcomputing[J].SimulationModellingPracticeandTheory,2014,49:320-335.郭奇勝，徐享忠.計(jì)算機(jī)仿真[M].北京：國(guó)防工業(yè)出版社，2011:208-243.FujimotoRM.Parallelanddistributedsimulation[C]//Proceedingsofthe1999wintersimulationconference.[s.l.]:ACM,1999:122-131.FujimotoRM.Distributedsimulationsystem[C]//Proceedingsofthe2003wintersimulationconference.[s.l.]:IEEE,2003:124-134.楊巖巖.分布式耦合仿真系統(tǒng)故障的分析與研究[D].成都：西南交通大學(xué)，2013.王濤，劉大昕.一種啟發(fā)式與/或優(yōu)先約束任務(wù)調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007,28(3):504-509.王占杰，劉晶