劉金波，黃海于

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

耦合分布式系統多任務動態調度算法

劉金波，黃海于

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

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

分布式系統；多任務；動態分配；利用率

0 引 言

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

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

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

1 系統的基本結構

耦合分布式系統結構如圖1所示。

該分布式系統主要包含客戶機、作業調度器、耦合器以及計算資源。計算任務由多個計算模塊組成，這些計算模塊經過調度器進行調度后可以運行在多個計算資源上。

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

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

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

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

2 動態任務調度算法

2.1 算法描述

計算任務是由一系列的子模塊構成，調度的過程就是為計算任務的各個子模塊尋找計算資源。動態任務分配算法的描述如下：

(1)解析一個未被調度的計算任務；

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

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

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

2.2 計算資源的負載評價方法

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

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

(1)

其中,xi(x1+x2+x3+x4=1且xi>0)分別為CPU的利用率、網絡流量、內存利用率、磁盤利用率對應的權值。

為這些參數設置不同的權值可以使某個參數影響到最終的調度結果。例如，如果希望將計算任務調度到通信狀況良好的計算資源上，可以將x2的權值調大，以此來影響任務的調度。負載值越大，說明該計算節點計算任務越繁重，不應該優先被分配計算任務。

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

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

2.3 調度參數的設置

動態任務分配算法能夠將不同計算任務的模塊調度到同一臺計算資源上，因此調度器需要盡可能多地了解計算任務中每個計算模塊的計算要求。例如，某個模塊的運行對內存要求很高或者對實時性要求很高，可以將其設置為獨占計算資源；具體來說，需要設置的參數有：該計算模塊是否獨立運行；運行至少需要多大的內存；對操作系統的要求，例如運行于Windows或者Linux系統下；運行在哪個IP地址的計算資源上等。以上這些參數均作為某個模塊的調度參數，會影響到調度結果。這些調度參數由用戶在構建計算任務時為每個計算模塊進行配置。

2.4 動態任務分配算法流程

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

每次的調度過程總是優先將計算模塊調度給空閑的計算資源，當沒有空閑的計算資源時，再嘗試將模塊分配給已經有計算任務的計算資源。計算資源匹配算法流程如圖3所示。

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

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

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

圖3 資源匹配算法

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

3 實 驗

3.1 實驗環境

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

3.2 實驗結果與分析

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

表1 運行車線弓用時對比

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

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

4 結束語

詳細介紹了耦合分布式系統動態任務分配算法的實現。仿真結果顯示，該動態任務分配算法能夠根據每臺計算資源的實際負載情況進行動態的任務調度，能夠實現計算資源的合理利用，同時保證計算任務的計算速度不會受到太大影響，從而提高了計算資源的使用效率，同時也使得盡可能多的計算任務同時進行，提高了任務調度的效率。

[1] 張衛華.高速列車耦合大系統動力學理論與實踐[M].北京：科學出版社，2013：144-151.

[2] 萬春陽，黃海于.分布式仿真系統的數據監控軟件的實現[J].計算機技術與發展，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].北京：國防工業出版社，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] 楊巖巖.分布式耦合仿真系統故障的分析與研究[D].成都：西南交通大學，2013.

[8] 王 濤，劉大昕.一種啟發式與/或優先約束任務調度算法[J].小型微型計算機系統，2007,28(3):504-509.

[9] 王占杰，劉晶晶.基于多Agent的分布式多目標任務調度機制研究[J].大連理工大學學報,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] 向 鵬，黃海于.耦合分布式仿真中任務調度的研究與實現[J].計算機技術與發展，2013,23(12)：78-81.

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

[14] 杜志強,黃海于.分布式仿真系統通信故障檢測和恢復研究[J].計算機技術與發展,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">網絡出版時間

時間：2017-08-01

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

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

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