劉金波，黃海于

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756)

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

劉金波，黃海于

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756)

針對(duì)耦合分布式系統(tǒng)中一個(gè)計(jì)算模塊獨(dú)自占用某臺(tái)計(jì)算資源，導(dǎo)致其他計(jì)算模塊無法調(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ì)算資源的限制而無法運(yùn)行的計(jì)算任務(wù)能夠提前開始運(yùn)行，提高了計(jì)算任務(wù)調(diào)度的高效性和靈活性。

分布式系統(tǒng)；多任務(wù)；動(dòng)態(tài)分配；利用率

0 引 言

高速列車數(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)必須考慮的問題。分布式系統(tǒng)以及云計(jì)算中的調(diào)度問題一直都是研究人員研究的熱點(diǎn)。為解決分布式系統(tǒng)中的任務(wù)調(diào)度問題，研究人員提出了很多調(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)，無法進(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)度算法；三是無法根據(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ì)算資源。

1 系統(tǒng)的基本結(jié)構(gòu)

耦合分布式系統(tǒng)結(jié)構(gòu)如圖1所示。

該分布式系統(tǒng)主要包含客戶機(jī)、作業(yè)調(diào)度器、耦合器以及計(jì)算資源。計(jì)算任務(wù)由多個(gè)計(jì)算模塊組成，這些計(jì)算模塊經(jīng)過調(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ì)算資源鏈表，通過循環(huán)遍歷計(jì)算任務(wù)隊(duì)列以及計(jì)算資源隊(duì)列來對(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)過耦合器轉(zhuǎn)發(fā)到相應(yīng)的目的模塊。分布式計(jì)算平臺(tái)中可以有多個(gè)耦合器，每個(gè)耦合器也可以同時(shí)管理多個(gè)工況的耦合計(jì)算，調(diào)度器根據(jù)每個(gè)耦合器的性能狀態(tài)來進(jìn)行任務(wù)的分配。

計(jì)算資源與調(diào)度器和耦合器處在同一個(gè)局域網(wǎng)下，為大規(guī)模的計(jì)算任務(wù)提供計(jì)算能力。計(jì)算資源上需要運(yùn)行代理軟件，通過代理軟件接收調(diào)度器分配的計(jì)算任務(wù)，然后從數(shù)據(jù)庫中下載相應(yīng)的配置文件與可執(zhí)行程序，可執(zhí)行程序包含了計(jì)算任務(wù)的求解過程，代理啟動(dòng)該模塊的可執(zhí)行程序進(jìn)行計(jì)算。

客戶機(jī)是用戶與分布式計(jì)算平臺(tái)進(jìn)行交互的接口。用戶可以通過客戶機(jī)進(jìn)行計(jì)算任務(wù)的生成以及配置，同時(shí)可以將計(jì)算任務(wù)提交給調(diào)度器進(jìn)行計(jì)算，此外用戶也可以通過客戶機(jī)對(duì)某個(gè)正在運(yùn)行的計(jì)算任務(wù)進(jìn)行過程監(jiān)控。

2 動(dòng)態(tài)任務(wù)調(diào)度算法

2.1 算法描述

計(jì)算任務(wù)是由一系列的子模塊構(gòu)成，調(diào)度的過程就是為計(jì)算任務(wù)的各個(gè)子模塊尋找計(jì)算資源。動(dòng)態(tài)任務(wù)分配算法的描述如下：

(1)解析一個(gè)未被調(diào)度的計(jì)算任務(wù)；

(2)判斷其中固定IP的計(jì)算模塊能否調(diào)度成功，不能則返回到(1)，解析下一個(gè)未被調(diào)度的計(jì)算任務(wù)；

(3)調(diào)度獨(dú)占計(jì)算資源的模塊，調(diào)度失敗則返回到(1)，解析下一個(gè)未被調(diào)度的計(jì)算任務(wù)，如果調(diào)度成功，鎖定該計(jì)算資源，在該計(jì)算任務(wù)完成計(jì)算之前，該計(jì)算資源不會(huì)參與到以后任務(wù)的調(diào)度；

(4)調(diào)度所有的一般模塊，優(yōu)先將一般模塊調(diào)度給空閑的計(jì)算資源，如果沒有空閑的計(jì)算資源，則將所有的可用計(jì)算資源按照負(fù)載評(píng)價(jià)方法進(jìn)行排序，選擇最合適的計(jì)算資源。

2.2 計(jì)算資源的負(fù)載評(píng)價(jià)方法

調(diào)度器在進(jìn)行任務(wù)的調(diào)度時(shí)，需要對(duì)每臺(tái)計(jì)算資源的計(jì)算能力進(jìn)行評(píng)價(jià)，計(jì)算負(fù)載參數(shù)W,以此來判斷當(dāng)前的計(jì)算資源能否用于任務(wù)調(diào)度。對(duì)一臺(tái)計(jì)算資源的評(píng)價(jià)主要通過以下幾個(gè)參數(shù)來進(jìn)行衡量：CPU利用率M；網(wǎng)絡(luò)流量S；內(nèi)存利用率U;磁盤利用率D。在判斷過程中需要綜合衡量各個(gè)參數(shù)對(duì)調(diào)度任務(wù)的影響，負(fù)載參數(shù)的計(jì)算公式如下：

W=X1*M+X2*S+X3*U+X4*D

(1)

其中,xi(x1+x2+x3+x4=1且xi>0)分別為CPU的利用率、網(wǎng)絡(luò)流量、內(nèi)存利用率、磁盤利用率對(duì)應(yīng)的權(quán)值。

為這些參數(shù)設(shè)置不同的權(quán)值可以使某個(gè)參數(shù)影響到最終的調(diào)度結(jié)果。例如，如果希望將計(jì)算任務(wù)調(diào)度到通信狀況良好的計(jì)算資源上，可以將x2的權(quán)值調(diào)大，以此來影響任務(wù)的調(diào)度。負(fù)載值越大，說明該計(jì)算節(jié)點(diǎn)計(jì)算任務(wù)越繁重，不應(yīng)該優(yōu)先被分配計(jì)算任務(wù)。

如果某個(gè)參數(shù)過大，例如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)存利用率、磁盤利用率的均值，然后根據(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)確性。

2.3 調(diào)度參數(shù)的設(shè)置

動(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ì)算資源；具體來說，需要設(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)行配置。

2.4 動(dòng)態(tài)任務(wù)分配算法流程

調(diào)度器運(yùn)行過程中會(huì)循環(huán)掃描任務(wù)隊(duì)列和計(jì)算資源列表，在分配的過程中，如果該計(jì)算模塊是獨(dú)占計(jì)算資源模塊，則需要將該模塊占用的計(jì)算資源鎖定，在該模塊未完成計(jì)算之前，其他的計(jì)算模塊無法調(diào)度到該計(jì)算資源。調(diào)度算法的流程如圖2所示。

每次的調(diào)度過程總是優(yōu)先將計(jì)算模塊調(diào)度給空閑的計(jì)算資源，當(dāng)沒有空閑的計(jì)算資源時(shí)，再嘗試將模塊分配給已經(jīng)有計(jì)算任務(wù)的計(jì)算資源。計(jì)算資源匹配算法流程如圖3所示。

資源匹配算法主要針對(duì)非固定IP和非獨(dú)占計(jì)算資源的一般模塊，通過采用式(1)的資源負(fù)載評(píng)價(jià)方法篩選出合適的資源。算法描述如下：

(1)遍歷每臺(tái)計(jì)算資源的心跳信號(hào)鏈表，找到心跳信號(hào)步數(shù)大于50的計(jì)算資源，心跳信號(hào)小于50步表示該計(jì)算資源剛剛分配計(jì)算任務(wù)，不參與此次調(diào)度；

(2)取最近的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ò)流量與磁盤使用率分別占0.2的權(quán)值，以此來估算每臺(tái)計(jì)算資源的負(fù)載；

圖3 資源匹配算法

(3)找到負(fù)載值最小的計(jì)算資源，將計(jì)算模塊分配給該計(jì)算資源。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

為了驗(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ì)算資源。

3.2 實(shí)驗(yàn)結(jié)果與分析

首先使用原有的調(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 運(yùn)行車線弓用時(shí)對(duì)比

表2 運(yùn)行分布式人臉識(shí)別用時(shí)對(duì)比

由表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)。

4 結(jié)束語

詳細(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)度的效率。

[1] 張衛(wèi)華.高速列車耦合大系統(tǒng)動(dòng)力學(xué)理論與實(shí)踐[M].北京：科學(xué)出版社，2013：144-151.

[2] 萬春陽，黃海于.分布式仿真系統(tǒng)的數(shù)據(jù)監(jiān)控軟件的實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013,23(9):14-17.

[3] D' Angelo G,Marzolla M.New trends in parallel and distributed simulation:from many-cores to cloud computing[J].Simulation Modelling Practice and Theory,2014,49:320-335.

[4] 郭奇勝，徐享忠.計(jì)算機(jī)仿真[M].北京：國(guó)防工業(yè)出版社，2011：208-243.

[5] Fujimoto R M.Parallel and distributed simulation[C]//Proceedings of the 1999 winter simulation conference.[s.l.]:ACM,1999:122-131.

[6] Fujimoto R M.Distributed simulation system[C]//Proceedings of the 2003 winter simulation conference.[s.l.]:IEEE,2003:124-134.

[7] 楊巖巖.分布式耦合仿真系統(tǒng)故障的分析與研究[D].成都：西南交通大學(xué)，2013.

[8] 王 濤，劉大昕.一種啟發(fā)式與/或優(yōu)先約束任務(wù)調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2007,28(3):504-509.

[9] 王占杰，劉晶晶.基于多Agent的分布式多目標(biāo)任務(wù)調(diào)度機(jī)制研究[J].大連理工大學(xué)學(xué)報(bào),2011,51(5):755-760.

[10] Hagras T,Janecek J.A high performance,low complexity algorithm for compile-time task scheduling in heterogeneous system[C]//Proceedings of the 18th international parallel and distributed processing symposium.Santa Fe:IEEE,2004:107-115.

[11] Abdllash S,Lesser V.Modeling task allocation using a decision theoretic model[C]//Proceedings of international conference on autonomous agents and multiagent systems.New York:ACM,2005:719-726.

[12] 向 鵬，黃海于.耦合分布式仿真中任務(wù)調(diào)度的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013,23(12)：78-81.

[13] 張 宇,黃海于.耦合分布式系統(tǒng)多線程任務(wù)管理算法[J].成都大學(xué)學(xué)報(bào)：自然科學(xué)版，2012,31(3)：251-253.

[14] 杜志強(qiáng),黃海于.分布式仿真系統(tǒng)通信故障檢測(cè)和恢復(fù)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(11):172-176.

ADynamicSchedulingAlgorithmwithMulti-tasksforDistributedCoupledSystems

LIU Jin-bo，HUANG Hai-yu

(School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China)

In a coupling-distributed system,one calculation task is distributed in a single computing node so that other tasks cannot be distributed in the same computing node,even with a strong computing power.A new dynamic task assignment algorithm is proposed.It can assign calculation task according to the scheduling requirements of computing task and running state of computing resources,which makes calculation resources with powerful computing capable of running more calculation modules for implementation of multi-tasks scheduling,and which enables computing tasks of meeting scheduling needs in the running state simultaneously,improving the utilization of computational resources and ensure the effectiveness and efficiency of scheduling.The simulation shows that the proposed algorithm can greatly improve the utilization of computing resources,not only ensuring the computing speed but also providing computing power for multiple computational tasks at the same time.The computational tasks that cannot be performed due to conditional constraints can run in time,thus improving the efficiency and flexibility of the scheduling system.

distributed system;multi-task;dynamic assignment;utilization

TP302

A

1673-629X(2017)12-0016-04

10.3969/j.issn.1673-629X.2017.12.004

2016-12-17

2017-04-20 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

“十一五”國(guó)家科技支撐計(jì)劃(2009BAG12A01-A01)

劉金波(1991-)，男，碩士研究生，研究方向?yàn)榉植际接?jì)算、云計(jì)算；黃海于，副教授，研究方向?yàn)檐浖o線電、分布式計(jì)算、游戲開發(fā)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1556.066.html