基于ＧｒｉｄＳｉｍ的網格算法測試軟件開發

摘 要:針對目前絕大部分的網格任務調度實驗均建立在仿真實驗的基礎之上，而GridSim網格模擬器在支持多任務、多資源環境下的網格算法測試方面表現得越來越力不從心，開發一個便于網格研究者使用的網格算法測試軟件迫在眉睫。設計并實現了基于GridSim的網格算法測試程序，該程序包括了構建環境模塊、任務調度模塊和結果輸出模塊三個子模塊。通過實驗驗證，該程序能夠達到在多任務、多資源環境中分析、對比和驗證網格調度算法性能的目的。

關鍵詞:網格模擬器; 任務調度; 網格算法測試軟件

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3338-03

doi:10.3969/j.issn.1001-3695.2009.09.039

Development of scheduling algorithm testing software based on GridSim

LEI Bing-han HE Jun ， HE Xiang LI Qi2

(1.College of Computer Science， Sichuan University， Chengdu 610065， China; 2.Software Key Laboratory of Sichuan Province， Chengdu 610068， China)

Abstract:Presently， built most of the grid task scheduling experiments on the basis of the simulation， but GridSim behaved increasingly incompetent in support of testing the performance of grid algorithms， especially under the environment of multi-task and more resources， so the development of scheduling algorithms testing software which provided researchers with a great amount of convenience was urgently required. In response to these issues， this paper designed and implemented algorithm testing procedures which according to GridSim， the program included three modules， they were resources and tasks setting up sub-module， task scheduling sub-module， and output sub-module， respectively. Experimentally verified， the purpose of analyzing， comparing and validating the performance of algorithms under the environment of multi-task and more resources can be achieved by using this program.

Key words:grid simulator; task scheduling; scheduling algorithm testing software

考察各類網格調度算法的優缺點，結合網格實際環境[1]，設計更加適合網格調度[2，3]的算法依然是當今網格研究的重點和難點。但是在實際的網格系統中，很難實現資源負載狀態的再現或者可控制的資源負載變化，而且創建真實的網格任務也是一項繁瑣的工作[4~6]。因此固定資源環境的缺乏對于調度算法的深入研究造成了極大的阻礙，但網格模擬器的出現解決了這一問題。目前絕大部分的網格任務調度實驗均建立在仿真實驗的基礎之上，雖然能夠利用模擬器進行調度實驗，分析實驗結果，但GridSim模擬器[7]在支持多任務、多資源環境下的網格算法測試方面存在明顯不足，主要表現在以下幾個方面:a)GridSim偏重于支持計算網格的任務屬性，對服務網格的任務屬性支持不足，如任務的QoS需求[8，9];b)GridSim只提供創建單個網格任務和資源的方法，如果用戶需要在多任務、多資源環境下進行實驗，就必須自己提供創建批量任務和資源的方法;c)GridSim對經典算法(如Min-min算法、Sufferage算法[10]等)支持不足，用戶需要提供算法代碼;d)GridSim沒有提供收集和統計模擬實驗結果的方法，如果用戶期望輸出和統計實驗結果，分析算法性能，就必須自己編寫結果輸出程序。

基于系統損失和任務復雜度的網格調度算法——BSLTC算法，需要在多任務、多資源的網格環境下進行仿真實驗，因此單單依靠GridSim模擬器難以勝任，需要設計和實現符合要求的網格算法測試應用程序，以分析和驗證該算法的優越性。

鑒于以上分析的GridSim模擬器的局限[11]，本文在深入了解網格概念和特點的基礎上，設計并實現了基于GridSim網格模擬器的網格算法測試應用程序;然后通過所編寫的應用程序測試三個算法的性能。統計實驗結果驗證了該仿真實驗的可行性和有效性，為分析和改進算法性能提供依據，也為今后研究新的網格調度算法提供了平臺。

1 實驗方案設計

本文期望在多任務、多資源的網格模擬環境中，分別采用Min-min、Sufferage和BSLTC算法來對任務進行調度;收集模擬實驗數據，分析各個算法的性能，驗證BSLTC算法在最優跨度、服務質量、負載均衡三方面表現出來的優越性。

模擬實驗的執行流程如圖1所示。

圖1中，矩形框表示執行過程，平行四邊形框表示數據。模擬實驗的執行步驟如下:

a)初始化網格環境，建立各種性能的異構資源。在GridSim中，虛擬資源具有豐富的屬性，所屬地區、系統架構、操作系統、計算機數、處理單元數、處理單元每秒運算能力、網絡帶寬、負載情況等均可設定，充分體現了網格資源的異構情況。

b)創建虛擬任務。GridSim中的任務屬性包括運算量、輸入文件大小和輸出文件大小等，本實驗在繼承這些屬性的基礎上，添加了緊迫性QoS需求屬性和最低處理能力需求屬性。

c)通過GridSim信息服務，獲取當前資源信息。根據資源的總運算能力、任務的運算量和任務的最低處理能力需求，預測任務的執行時間，獲得ETC矩陣。

d)將任務的緊迫性QoS需求和ETC矩陣輸入調度模塊。調度模塊調用不同的算法，生成各個算法對應的任務分配表，然后調用GridSim中的接口，提交任務到對應資源執行。

e)任務執行完畢后，獲取執行任務的資源信息、任務的開始時間、完成時間以及任務的屬性，提交給輸出模塊，格式化輸出執行結果和統計結果。

依據以上執行過程，可以將本文基于GridSim的網格調度算法測試模塊劃分為三個子模塊(圖2):

a)構建環境子模塊，作用是創建用于模擬實驗的網格任務和網格資源;b)任務調度子模塊，實現采用不同調度算法將任務分配到資源，為模擬實驗的任務調度提供依據;c)結果輸出子模塊，作用是收集和統計模擬實驗結果，驗證算法性能。

2 模擬應用程序的實現

以下各個類是在JDK 1.5.0的環境下，引用gridsimtoolkit-4.0工具包實現。

2.1 各個類之間的關系

應用程序的main函數位于GridSimApp類中，GridSimApp類繼承了GridSim。以下是程序的運行過程。

函數main() 中執行的操作:

a)調用GridSim的靜態方法GridSim.init來初始化。

b)創建一個ResourceFactory對象，生成指定數量的隨機資源。所生成資源將通過GridResource.init方法向該GridSim包的GIS注冊。

c)初始化GridSim的靜態成員gridletfactory，實例化一個GridletFactory對象，調用該對象的createGridlet()方法，按照指定個數創建三組具有相同屬性的NewGridlet對象，供三個GridSimApp對象使用。

d)輸出任務和資源信息到文本文件。

e)實例化三個GridSimApp對象，對象name屬性分別為MIN-MIN，SUFFERAGE和BSLTC。GridSimApp對象中執行的如下操作:

(a)初始化GridSimApp對象的屬性，然后執行body()中的代碼。

(b)調用GridSimApp. getGridResourceList方法，從GIS獲取所有資源信息。

(c)創建ETC_Factory對象，根據資源信息和任務信息，產生ETC矩陣。

(d)創建Scheduler對象，根據算法名稱、ETC矩陣和任務信息調用對應算法，生成任務—資源分配表和資源—任務列表。

(e)調用GridSimApp. gridletSubmit方法，按照資源—任務列表，提交任務到對應資源執行。

(f)調用GridSimApp.gridletReceive方法，接收任務的執行情況信息。

(g)創建ResultOutput對象，收集所有任務的執行信息。

(h)創建ResultStatistic對象，調用ResultOutput對象所收集的信息，計算makespan、負載均衡值和不同QoS需求的任務執行情況。

(i)輸出ResultStatistic對象的統計結果到文本文件。

f)調用GridSim.startGridSimulation()方法啟動網格模擬。

2.2 任務和資源創建類

任務和資源創建類屬于構建環境模塊，它包括三個類:

a)NewGridlet類。它是新的網格任務，繼承GridSim包中的Gridlet類，該類添加了緊迫性QoS需求屬性qosAttribute、最低MIPS(millions instruction per second)需求屬性mipsdemand，以及這兩個新屬性的設置方法和獲取方法。

b)GridletFactory類。用來創建網格任務，采用單態模式實現。GridletFactory的主要功能:按照指定數目，批量產生隨機屬性的NewGridlet對象;輸出GridletFactory所創建的所有任務的信息，為算法性能分析提供原始數據;統計任務的分布情況，即各QoS需求和各級別運算量任務的個數、所占比例，并提供獲取這些統計和輸出統計結果的方法。

c)ResourceFactory類。它是創建網格資源(GridResource)對象的類，方法createResource用多態方式實現以指定屬性創建單個GridResource實例和隨機屬性創建多個GridResource實例。編寫ResourceFactory 的目的也是為實驗所需的大量資源作準備。GridResource實例創建的過程中，將會調用父類的方法向GIS注冊。

2.3 任務調度類

該模擬應用程序的核心實現采用不同調度算法將任務分配到資源，包括兩個類:

a)ETC_Factory類。產生ETC矩陣，根據每個資源的處理能力、負載情況以及每個任務的運算量來預測生成各個任務在不同資源上的執行時間。如果任務的最低MIPS需求大于資源的總MIPS，則對應的ETC矩陣中值為Float.POSITIVE_INFINITY，視該資源不能執行該任務。

b)Scheduler類。根據輸入的ETC矩陣、任務緊迫性QoS需求和算法名稱來選擇執行調度算法，生成任務-資源分配表和資源—任務列表。類的主要方法如下面的描述:

構造函數Scheduler (float[][] ETC，string algorithm，int[]qos)。第一個參數為ETC矩陣，由ETC_Factory對象產生;第二個參數為算法名稱，構造函數將根據算法名稱調用相應的調度算法;第三個參數為任務的QoS需求向量。

私有方法min-minAlgorithm()、sufferageAlgorithm()和bsltcAlgorithm()分別實現三種調度算法。輔助方法findMin()、findSubMin()、finMin-min()、finMax-min()，為算法中獲取向量中的最小、次小值以及最小值向量中的的最小、最大值服務。

私有方法averageET()用在bsltcAlgorithm()算法中，用來求未分配任務的平均最小執行時間。

私有方法refreshMCT()的作用是在分配任務后，更新MCT矩陣，為下一次分配作準備。

私有方法reclaimMCT()是用在sufferageAlgorithm()中，當任務需要重新分配時調用該算法回滾MCT矩陣。

公有方法outputGridletSchedule()和outputResourceTaskList()分別用來輸出任務—資源對和資源—任務列表。

公有方法getRunTime()和getLoopTimes()用來獲取算法執行時間和調度次數。Min-min算法和BSLTC算法的調度次數相同，都等于任務數。Sufferage算法的次數較多。

2.4 結果輸出與統計類

該模塊包括兩個類:

a)ResultOutput類。收集任務執行情況，包括任務ID、任務運算量、執行任務的資源ID、資源的名字、資源的處理能力。任務的執行時間和完成時間，以及按照格式輸出這些信息的方法。

b)ResultStatistic類。用來統計資源執行情況。包括各個級別的緊迫性QoS任務的開始時間、各個資源的負載情況、makespan，并統計信息輸出。

矩陣letletDistribute用來記錄各緊迫性QoS任務的執行情況分布，是一個3行5列矩陣。例如，letletDistribute[2][3]表示緊迫性QoS需求為3的任務且開始執行的時間大于makespan /3，小于2×makespan/3的任務個數。

資源的負載情況用下式計算，表示任務負載偏離理想均衡負載的程度，數值越小表示負載越平衡。

∑資源總數i=1|1-(資源i所執行的任務的總運算量/資源i的總MIPS)/(所有任務的總運算量/所有資源的總MIPS)|(1)

完成時間，即makespan，是主要的算法性能評判參數，開始執行任務調度到最后完成所有任務的時間差值，makespan越小，反映系統的執行效率越高，所有任務的總完成時間最短。

3 實驗及結果分析

本文在上述程序的基礎上進行了多次模擬實驗，以下是一次實驗的情況:50個資源，500個任務，資源隨機數種子為1，任務隨機數種子為1。按照附錄程序執行，將生成一個連續的ETC矩陣。部分ETC矩陣(1～8列，1～7行)如下:

運行程序輸出的結果如下所示:

====50個資源 500個任務 資源隨機數種子為1 任務隨機數種子為1

任務分布情況

運行結果

名稱 makespan/s負載均衡度執行時間/ms調度次數

程序輸出結果中，統計了生成任務的分布情況，包括各個級別運算量的任務分布和不同緊迫性QoS需求任務的分配情況。程序的運行結果包括makespan，按照式(1)計算的負載均衡度，調度算法執行時間以及任務調度次數。其中矩陣表示不同QoS需求的任務在各個時間段開始執行的個數，矩陣左邊為低QoS需求任務，右邊為高QoS需求任務。例如，對于Min-min算法的矩陣，第1行第5列元素表示緊迫性QoS需求為5的任務，有88個是在1/3makespan之前開始執行的。

根據以上的輸出結果，可以得到實驗的統計結果，為網格調度算法性能分析提供依據。

4 結束語

通過所編寫的應用程序測試三個算法的性能，統計實驗結果，驗證了BSLTC算法在一定的環境下具有執行速度快、makespan短和負載均衡性高的優點。在下一步的工作中，將為使用該測試應用程序的用戶提供友好的用戶界面，并對其進行優化，使之成為分析網格調度算法的通用程序。

參考文獻:

[1]都志輝，陳渝，劉鵬. 網格計算[M]. 北京:清華大學出版社，2002.

[2]王相林， 張善卿， 王景麗. 網格計算核心技術[M]. 北京:清華大學出版社，2006.

[3]羅紅，慕德俊，鄧智群. 網格計算中任務調度研究綜述[J]. 計算機應用研究，2005，22(5):16-19.

[4]BUYYA R， ABRAMSON D， GIDDY J. A case for economy grid architecture for service-oriented grid computing[C]//Proc of the 5th Heterogeneous Computing Workshop. Washington DC:IEEE Compu-ter Society，2001:776-790.

[5]TAKEFUSA A， MATSUOKS S， NAKADS H， et al. Overview of a performance evaluation system for global computing scheduling algorithms[C]//Proc of the 8th IEEE International Symposium on High Performance Distributed Computing(HPDC-8). Washington DC:IEEE Computer Society，1999:97-104.

[6]BUYYA R， MUTSHED M. GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing[J]. The Journal of Concurrency and Computation: Practice and Experience(CCPE)，2002，14(13-15):1175-1220.

[7]劉祥瑞，朱建勇，樊孝忠. 基于GridSim的網格調度模擬[J]. 計算機工程，2006，32(2):42-44.

[8]邢建兵，陶慕柳.網格QoS研究的關鍵問題及技術綜述[J]. 計算機工程與應用， 2004，44(33):8-10，14.

[9]HE Xiao-xhen， SUN Xiao-he， Von LASZEWSKI G. QoS guided min-min heuristic for grid task scheduling [J]. The Journal of Compu-ter Science and Technology， 2003， 18(4): 442-451.

[10]CASANOVA H， ZAGORODNOV A， BERMAN D. Heuristics for scheduling parameter sweep applications in grid environments[C]//Proc of the 9th Heterogeneous Computing Workshop. Washington DC:IEEE Computer Society， 2000:349-363.

[11]田翠花，常桂然，金海月，等.網格模擬技術分析[J].計算機應用研究， 2007，24(2):101-105.