耦合分布式系統(tǒng)多任務動態(tài)調度算法

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