劉金波，黃海于

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

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

劉金波，黃海于

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

針對耦合分布式系統(tǒng)中一個計算模塊獨自占用某臺計算資源，導(dǎo)致其他計算模塊無法調(diào)度到該計算資源的情況，提出了一種動態(tài)任務(wù)分配的調(diào)度算法。該算法能夠根據(jù)計算任務(wù)的調(diào)度要求和計算資源的運行狀態(tài)，動態(tài)進行任務(wù)分配，使計算能力強的計算資源能夠運行更多的計算模塊，從而實現(xiàn)多計算任務(wù)調(diào)度，使多個符合調(diào)度要求的計算任務(wù)同時處于運行狀態(tài)，提高計算資源的利用率，保證了計算任務(wù)調(diào)度的有效性和高效性。仿真結(jié)果表明，該多任務(wù)動態(tài)調(diào)度算法能夠在不影響計算速度的情況下，使一臺計算資源同時為多個計算任務(wù)提供計算能力，大大提高了計算資源的利用率，并且使原本因計算資源的限制而無法運行的計算任務(wù)能夠提前開始運行，提高了計算任務(wù)調(diào)度的高效性和靈活性。

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

0 引 言

高速列車數(shù)字化仿真平臺采用分布式體系結(jié)構(gòu)[1-2]，資源管理及任務(wù)調(diào)度子系統(tǒng)是平臺下的一個子系統(tǒng)。在分布式體系結(jié)構(gòu)中[3-6]，任務(wù)調(diào)度是非常重要的一環(huán)。如何有效地利用分布式系統(tǒng)中的計算資源以及如何對現(xiàn)有的計算任務(wù)進行調(diào)度，均是任務(wù)調(diào)度子系統(tǒng)必須考慮的問題。分布式系統(tǒng)以及云計算中的調(diào)度問題一直都是研究人員研究的熱點。為解決分布式系統(tǒng)中的任務(wù)調(diào)度問題，研究人員提出了很多調(diào)度策略，例如排隊理論、圖論、決策論以及啟發(fā)式調(diào)度方法等[7-11]。

耦合分布式系統(tǒng)原有的調(diào)度算法[12]為每個計算模塊分配一臺計算資源，如果該計算模塊只占用很少的計算資源，而其他的計算模塊又不能調(diào)度到該計算資源上，不僅會造成計算資源的極大浪費，也會使得大量的計算任務(wù)處于阻塞狀態(tài)，無法進行計算。文獻[13]提出一種耦合分布式系統(tǒng)多線程任務(wù)管理算法，可以將多個計算模塊調(diào)度到一臺計算資源上。但是該算法存在三點不足：一是以多線程的方式管理各個計算模塊，多個線程共用一個端口，采用互斥的方式與耦合器進行數(shù)據(jù)交互，理論上這種方法比多進程的方式效率要低；二是這種算法只能將同一計算任務(wù)的多個計算模塊分配給一臺計算資源，實質(zhì)上是一種靜態(tài)任務(wù)調(diào)度算法；三是無法根據(jù)計算資源的實際使用情況進行任務(wù)分配，可能將多個模塊分配給一臺計算能力不佳的計算資源?？紤]到計算模塊是以進程的形式存在，一臺計算機上可以運行多個進程，一臺計算資源不應(yīng)只服務(wù)于一個計算任務(wù)，在條件允許的情況下也要為其他計算任務(wù)提供計算能力。因此，在不影響計算效率的前提下，可以考慮將多個計算模塊調(diào)度到一臺計算資源上進行計算。

基于此，文中提出了一種動態(tài)的任務(wù)調(diào)度算法。該算法可以根據(jù)當(dāng)前所有計算資源的實際使用情況以及用戶提交的計算任務(wù)，為計算任務(wù)中的每個計算模塊尋找最合適的計算資源。

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

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

該分布式系統(tǒng)主要包含客戶機、作業(yè)調(diào)度器、耦合器以及計算資源。計算任務(wù)由多個計算模塊組成，這些計算模塊經(jīng)過調(diào)度器進行調(diào)度后可以運行在多個計算資源上。

作業(yè)調(diào)度器負(fù)責(zé)接收用戶提交的計算任務(wù)并將其存放在任務(wù)隊列中，同時作業(yè)調(diào)度器也會維護一個計算資源鏈表，通過循環(huán)遍歷計算任務(wù)隊列以及計算資源隊列來對計算任務(wù)進行調(diào)度，因此高效的調(diào)度算法能夠合理地利用現(xiàn)有的計算資源，并且使盡可能多的計算任務(wù)同時處于運行狀態(tài)。

耦合器是整個分布式計算平臺的數(shù)據(jù)交互中心[14]。調(diào)度器在完成對某一個計算任務(wù)的調(diào)度后會指定一個耦合器作為該計算任務(wù)的數(shù)據(jù)交互中心和控制中心，該計算任務(wù)的所有數(shù)據(jù)都會經(jīng)過耦合器轉(zhuǎn)發(fā)到相應(yīng)的目的模塊。分布式計算平臺中可以有多個耦合器，每個耦合器也可以同時管理多個工況的耦合計算，調(diào)度器根據(jù)每個耦合器的性能狀態(tài)來進行任務(wù)的分配。

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

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

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

2.1 算法描述

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

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

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

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

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

2.2 計算資源的負(fù)載評價方法

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

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

(1)

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

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

如果某個參數(shù)過大，例如CPU的利用率已達到80%，應(yīng)該將該計算資源暫時剔除計算資源隊列。

以上的參數(shù)信息由運行在計算資源上的代理軟件獲取，以固定的時間間隔以心跳信號的形式發(fā)送給調(diào)度器。調(diào)度器為每臺計算資源保留最近五十步的心跳信號，每次進行任務(wù)調(diào)度時，取最近20步的心跳信號，計算CPU利用率、網(wǎng)絡(luò)流量、內(nèi)存利用率、磁盤利用率的均值，然后根據(jù)上述公式計算每臺計算資源的負(fù)載值，選取負(fù)載最低的計算資源進行任務(wù)分配。為了保證評價的準(zhǔn)確性，每當(dāng)一個計算任務(wù)調(diào)度成功后，調(diào)度器端會清空該計算任務(wù)占用的計算模塊所對應(yīng)的心跳信號，以保證數(shù)據(jù)的準(zhǔn)確性。

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

動態(tài)任務(wù)分配算法能夠?qū)⒉煌嬎闳蝿?wù)的模塊調(diào)度到同一臺計算資源上，因此調(diào)度器需要盡可能多地了解計算任務(wù)中每個計算模塊的計算要求。例如，某個模塊的運行對內(nèi)存要求很高或者對實時性要求很高，可以將其設(shè)置為獨占計算資源；具體來說，需要設(shè)置的參數(shù)有：該計算模塊是否獨立運行；運行至少需要多大的內(nèi)存；對操作系統(tǒng)的要求，例如運行于Windows或者Linux系統(tǒng)下；運行在哪個IP地址的計算資源上等。以上這些參數(shù)均作為某個模塊的調(diào)度參數(shù)，會影響到調(diào)度結(jié)果。這些調(diào)度參數(shù)由用戶在構(gòu)建計算任務(wù)時為每個計算模塊進行配置。

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

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

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

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

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

(2)取最近的20步心跳信號，按照式(1)計算每臺計算資源的負(fù)載值。在當(dāng)前的耦合分布式計算平臺中，優(yōu)先考慮內(nèi)存利用率以及CPU利用率的影響。其中內(nèi)存利用率與CPU利用率分別占0.3的權(quán)值，網(wǎng)絡(luò)流量與磁盤使用率分別占0.2的權(quán)值，以此來估算每臺計算資源的負(fù)載；

圖3 資源匹配算法

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

3 實 驗

3.1 實驗環(huán)境

為了驗證耦合分布式系統(tǒng)多任務(wù)動態(tài)調(diào)度算法的有效性，構(gòu)建了如下的實驗環(huán)境：仿真計算采用八臺計算資源，其中一臺運行調(diào)度器，一臺充當(dāng)耦合器，剩下的六臺作為計算資源。所有的計算機全運行在百兆局域網(wǎng)內(nèi)，同時提交一個分布式人臉識別和車線弓計算任務(wù)。其中在人臉識別的計算任務(wù)中，三個人臉識別模塊是獨占并且綁定固定IP的計算模塊，車線弓的計算任務(wù)需要三臺計算資源。按照原有的算法，運行這兩個計算任務(wù)至少需要九臺空閑的計算資源才能進行計算，而按照新的算法，理論上只需要六臺空閑的計算資源。

3.2 實驗結(jié)果與分析

首先使用原有的調(diào)度算法。由于計算資源數(shù)量的限制，對兩個計算任務(wù)分兩次提交，單獨測試計算時間，然后再采用動態(tài)任務(wù)分配算法，同時提交車線弓與分布式人臉識別的計算任務(wù)，測試兩種計算任務(wù)在兩種調(diào)度算法下的運行時間。表1列出了采用兩種調(diào)度算法完成車線弓計算任務(wù)的計算時間。表2列出了分布式人臉識別計算任務(wù)運行所用的時間。

表1 運行車線弓用時對比

表2 運行分布式人臉識別用時對比

由表1和表2可以看出，兩種計算任務(wù)的運行時間相差不大，但是動態(tài)任務(wù)調(diào)度算法相比原調(diào)度算法可以節(jié)省三臺計算資源，同時能夠保證更多的計算任務(wù)都處于運行狀態(tài)。

4 結(jié)束語

詳細(xì)介紹了耦合分布式系統(tǒng)動態(tài)任務(wù)分配算法的實現(xiàn)。仿真結(jié)果顯示，該動態(tài)任務(wù)分配算法能夠根據(jù)每臺計算資源的實際負(fù)載情況進行動態(tài)的任務(wù)調(diào)度，能夠?qū)崿F(xiàn)計算資源的合理利用，同時保證計算任務(wù)的計算速度不會受到太大影響，從而提高了計算資源的使用效率，同時也使得盡可能多的計算任務(wù)同時進行，提高了任務(wù)調(diào)度的效率。

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

[2] 萬春陽，黃海于.分布式仿真系統(tǒng)的數(shù)據(jù)監(jiān)控軟件的實現(xiàn)[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] 郭奇勝，徐享忠.計算機仿真[M].北京：國防工業(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].小型微型計算機系統(tǒng)，2007,28(3):504-509.

[9] 王占杰，劉晶晶.基于多Agent的分布式多目標(biāo)任務(wù)調(diào)度機制研究[J].大連理工大學(xué)學(xué)報,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)度的研究與實現(xiàn)[J].計算機技術(shù)與發(fā)展，2013,23(12)：78-81.

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

[14] 杜志強,黃海于.分布式仿真系統(tǒng)通信故障檢測和恢復(fù)研究[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ò)出版時間

時間：2017-08-01

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

劉金波(1991-)，男，碩士研究生，研究方向為分布式計算、云計算；黃海于，副教授，研究方向為軟件無線電、分布式計算、游戲開發(fā)。

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