基于ＧｒｉｄＳｉｍ模擬器的網(wǎng)格資源調(diào)度算法的研究

摘要：網(wǎng)格資源調(diào)度策略是網(wǎng)格計算領域中的關鍵研究方向之一，網(wǎng)格模擬器是資源調(diào)度策略優(yōu)化和改進研究的重要平臺，本文研究了GridSim模擬器，對此模擬器的整個框架結(jié)構(gòu)和運行機制作了闡述，本文對基礎的Minmin算法和QoS Guided Min-min算法進行研究和改進，并通過基于GridSim包設計了應用程序?qū)Ω倪M后的算法進行了相應的模擬。模擬研究結(jié)果表明，改進后的算法在任務平均完成時間上優(yōu)于以前的算法。

關鍵詞：網(wǎng)格；GridSim；Minmin算法；QoS Guided Min-min算法

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)25-1431-03

Research on Resource Scheduling Strategies for Gird based on GridSim

DONG Shi1， ZHOU Ding-ding2

(1.UESTC， School of Computer， Chengdu 610054， China; 2. ZKNU， Experiment Center， Zhoukou 466001， China)

Abstract: Grid resource scheduling strategy is an important component of researching fields in the grid computation.Grid simulator is an important platform about research on optimizing and amelioration of resource scheduled strategy. This text studied GridSim and set forth the whole framework and running mechanism. In addition， this text studied the Minmin arithmetic and QoS Guided Min-min arithmetic.Put forward improving on them. Designed a application based on GridSim package， and the application simulated new arithmetic.Research result indicated that new arithmetic excelled former arithmetic on average completely time of task.

Key words: Grid; GridSim; Minmin strategies; QoS Guided Min-min strategies

1 引言

網(wǎng)格資源調(diào)度策略是網(wǎng)格計算領域中的關鍵研究方向之一，在網(wǎng)格計算中，通過采取適合于網(wǎng)格任務特征和資源特點的調(diào)度策略，將網(wǎng)格計算中的資源分配給匹配的網(wǎng)格任務，從而使網(wǎng)格資源利用率最大化。本文對GridSim[1]模擬器的深入探討和研究，并對目前基礎的Minmin算法和QoS Guided Min-min算法進行了研究，提出一些不足，對Minmin算法和QoS Guided Min-min算法進行改進。

2 GridSim模擬器

GridSim[1]由澳大利亞墨爾本大學Rajkumar Buyya領導開發(fā)，它的首要目標是通過模擬來研究基于計算經(jīng)濟模型的有效資源分配方法。GridSim通過資源的“買”和“賣”來引入“經(jīng)濟模型”，從而達到控制網(wǎng)格資源的使用的目的。圖1顯示了GridSim的體系結(jié)構(gòu)。

GridSim是在SimJava[2]的基礎上開發(fā)的，它提供豐富的函數(shù)庫以支持模擬網(wǎng)格環(huán)境中的異構(gòu)資源（時間共享和空間共享）、用戶、應用程序、用戶代理和調(diào)度器。網(wǎng)格資源、用戶和用戶代理被視為不同的實體，它們通過消息事件（輸入和輸出）來進行通信。除了通過手工編程來實現(xiàn)模擬外，GridSim還提供了一套圖形接口工具Visual Modeler[3]（VM）幫助用戶配置網(wǎng)格環(huán)境并產(chǎn)生相應的代碼。仿真結(jié)束后，用戶可以調(diào)用GridSim中的稱為GridStatistics的庫函數(shù)來收集各種模擬的統(tǒng)計資料。

GridSim模擬的主要流程如下：初始化各個離散對象→啟動仿真→資源的注冊→代理broker向信息中心查詢資源→broker映像計算→提交任務→資源處理任務→資源返回結(jié)果→結(jié)束仿真。按照這一過程可以對采用不同策略時的網(wǎng)格資源調(diào)度進行模擬。

3 MinMin算法研究

Minmin算法是啟發(fā)式算法中的經(jīng)典算法。對于傳統(tǒng)的Min-Min、Max-Min、A*和GA等靜態(tài)啟發(fā)式算法，Tracy D.Bra等人已經(jīng)做了詳細的研究[3]。結(jié)果表明，GA算法在不同ETC矩陣下的性能是好的，Min-Min和A*次之。并且Tracy D.Braun的研究表明：對于每個ETC矩陣G算法的平均執(zhí)行時間是60秒，而A*算法是20分鐘。由于算法中各項參數(shù)是通過NWS等服務得到的一個提前預測值，因此在參數(shù)隨時間劇烈變化的網(wǎng)格環(huán)境下GA或A*的計算時間會顯得很長，從而得到的調(diào)度策略也很不合理。特別是當有主機的性能出現(xiàn)突變時，算法性能會變得更為低下。Min-Min算法仍然是目前網(wǎng)格調(diào)度算法的研究基礎之一，該算法的主要思想如下：

當需要調(diào)度的任務集合非空時，反復執(zhí)行如下操作直至集合為空。

(1) 對集合中每一個等待分配的任務T，分別計算出把該任務分配到n臺機器上的最小完成時間。假設任務在第k臺機器上的完成時間為最小，記為Min Ti(I)=MCT(i，k)，可得到一個含有m個元素的一維數(shù)組Min-Time；

(2) 設第a個元素是Min Time數(shù)組中最小的，其對應的主機為b，把任務a分配到機器b上；

(3) 從任務集合中把任務a刪除，同時更新MCT矩陣。Max－Min算法的實現(xiàn)思路和Min-Min很相似，只是把上面第2步找MinTime數(shù)組中最小的元素改為最大的元素。Min-min，Max－min，Sufferage，Xsufferage等基本啟發(fā)算法模式如下：

1) while there are tasks to schedule

2) for all task i to schedule

3) for all host j

4) Compute CTi，j=CT(task i，host j)

5) end for

6) Compute metrici=f1(CTi，1，CTi，2，……)

7) end for

8) Select best metric match(m，n)=f2(metric1，metric2，)

9) Compute minimum CTm，n

10) Schedule task m on n

11) end while

眾所周知，min－min算法的一個最大的毛病就是負載不平衡，這是因為當網(wǎng)絡傳輸?shù)葪l件對局部任務調(diào)度影響很小的時候整個網(wǎng)格處在一個異構(gòu)的環(huán)境中，這時候機器的處理能力將完全體現(xiàn)任務的調(diào)度策略，換句話說，如果某個節(jié)點的計算能力大于同處于一個局域網(wǎng)內(nèi)的其它節(jié)點的時候，所有調(diào)度到這個局部的任務都會調(diào)度到這臺機器上去，引起其它機器長期處于空閑狀態(tài)，而大量的任務處在等待調(diào)度的狀態(tài)，使得這臺機器負載過大，造成局部的負載嚴重不平衡。

3.1 Sufferage算法

該算法的主要思想如下：

1) 初始時各個主機上的已分配任務隊列為空；

2) 當待調(diào)度的網(wǎng)格任務集合為非空時，反復執(zhí)行如下操作直至集合為空：

a) 對集合中每一個等待分配的任務T，根據(jù)ETC(Ti，Hj)和START(Hj)分別計算出把該任務分配到n臺主機上執(zhí)行相應的最小完成時間。假設任務Ti在主機Hj上的完成時間為最小，記為Min-Time(i)=C(Ti，Hj)，可得到一個含有m個元素的一維數(shù)組Min-Time[m]；

b) 遍歷存放每個任務的最早完成時間的一維數(shù)組Min-Time，找到其中的最小值和次小值并獲得其相應的任務和主機的編號，計算該任務的Sufferage的值，將該任務分配到相應的主機上；

c) 根據(jù)該主機上的已分配任務隊列中每個任務的Sufferage值排序，將那些Sufferage值小于該任務Ti的己分配任務從已分配任務列表中刪除，添加到待調(diào)度網(wǎng)格任務集合中；

d) 從待分配的任務集合中把任務t刪除，同時更新ETC(Ti，Hj)、START(Hj)、Comp(Ti，Hj)等矩陣。

3.2 QoS Guided Min-min算法

該算法先對高QoS作業(yè)使用Min-min算法進行調(diào)度，將其分配到高QoS資源上執(zhí)行;然后再對低QoS作業(yè)使用Min-min算法進行調(diào)度，將其分配到所有網(wǎng)格資源上執(zhí)行。這種算法將高QoS作業(yè)優(yōu)先調(diào)度，解決了高QoS資源被低QoS作業(yè)占據(jù)的問題。

Sufferage算法是解決沒有任務有QoS要求時的一種改進Minmin算法存在負載缺陷的算法，而QoS Guided Min-min算法則是對存在任務要求（QoS）的一種改進算法。

從這兩種針對Minmin的改進算法對以上兩種的不同情況提出了各自的解決方案。但是我們?nèi)绾瓮瑫r解決這兩種情況并存時的一種情況呢。我們下面將提出一個新的解決方案。

4 Qos-Sufferage[4]算法

具體算法的思想為：

基于任務所能夠被執(zhí)行的計算資源的個數(shù)，即QosLevel向量所表示的進行分組，向量中的每一個分量作為一個Qos優(yōu)先級分組。由于QosLevel向量是一個n維向量，因此可以將所有的網(wǎng)格任務分為n組。按照QOS優(yōu)先級由高到低的順序根據(jù)ETC子矩陣SubETCi，m，對這些子矩陣中的任務采用傳統(tǒng)的sufferage算法進行調(diào)度。

算法流程的偽代碼如下：

1) 獲得所有任務在所有主機上的執(zhí)行時間并且將其保存在ETC矩陣中;

2) 根據(jù)任務的可執(zhí)行情況將m個任務分成n個QoS優(yōu)先級分組;

3) 劃分ETC并獲得SubETCi，m;

4) int i=1;

5) while(i<=n){

6) Do the Sufferage algorithm for the SubETCi，m;

7) i++;}

5 仿真設計與結(jié)果模擬

為驗證改進后的算法，本文在Windows環(huán)境下，使用eclipse研發(fā)的基于GridSim包的應用程序，進行了改進前后的資源調(diào)度算法的仿真試驗，具體配置和實驗模擬結(jié)果如下：

5.1 參數(shù)的配置

表1資源調(diào)度參數(shù)配置表

■

5.2 模擬結(jié)果

■

圖2 任務數(shù)為50時，QoS Guided Min-min與Qos-Sufferage算法的對比

■

圖3 任務數(shù)為100時，QoS Guided Min-min與Qos-Sufferage算法的對比

■

圖4 任務數(shù)為150時，QoS Guided Min-min與Qos-Sufferage算法的對比

從圖2至圖4可以看出采用Qos-Sufferage算法比QoS Guided Min-min算法，降低了平均完成時間，提高了資源調(diào)度的性能。

6 結(jié)論

網(wǎng)格資源的調(diào)度是網(wǎng)格計算中的核心問題，本文通過對GridSim模擬器的深入探討和研究，對Minmin算法和QoS Guided Min-min算法進行了研究，提出一些不足，并對Minmin算法和QoS Guided Min-min算法進行改進，在改進的算法中融入了QoS機制和Sufferage算法思想，實驗結(jié)果表明：改進后的算法，在平均完成時間上有很大的改進，提高了資源的調(diào)度性能。

參考文獻：

[1] Manzur Murshedand Rajkumar Buyya Using the GridSim Toolkit for Enabling Grid Computing Education，International Conference on Communication Networks and Distributed Systems Modeling and Simulation(CNDS2002)，January27-31，2002，San Antonio，Texas，USA.

[2] Braun， .TD.， Siegel，H.J.，Beck，N.，et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems. In:Proeeedings of the 8th IEEE Heterogeneous Computing Workshop(HCW，99).IEEE Computer Society Press，1999.15-29.

[3] Tracy D.Bruna，Howard Jay Siegel，Noah Beck. A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computnig. 2001(61):81.

[4] HE Xiaoshan，Xian-He sun，Gregor von Laszewski. A QoS Guided Scheduling Algorithm For Grid Computing[J].Journal of Computer science and Technology 2003，18(4):442-451.