網格任務調度算法Min-min的GridSim模擬實現

摘要:該文用模擬方法研究網格中的任務調度問題。首先對Min-min算法進行分析，然后用GridSim對Min-min調度算法進行模擬實現，闡述了實現過程，并統計模擬結果，對Min-min算法的MakeSpan和負載等性能進行了分析，驗證了模擬實現過程的正確性。

關鍵詞:網格計算;任務調度;Min-min;執行時間;GirdSim模擬

中圖分類號:TP393 文獻標示碼:A文章編號:1009-3044(2010)05-1052-02

GridSim Simulation of Min-min Task Scheduling Algorithm in Grid

SU Yi

(Information Center， Loudi Electric Power Bureau， Hunan Electric Power Company， Loudi 417000， China)

Abstract: The paper uses the simulation method to research the task scheduling problem in Grid. The paper firstly analyzes the Min-min task scheduling. Then Min-Min algorithm is simulated with the aid of GridSim simulation toolkit. The paper gives the implementing process and analyzes the performances of the Min-min algorithm including Makespan and load. The results validate that the simulation process is correct.

Key words: grid computing; task scheduling; Min-min; implementing time; GirdSim simulation

1 概述

網格技術經過多年的發展已經取得了比較多的研究成果。網格就是把整個國際互聯網集成為一臺巨大的超級計算機，實現全球范圍的計算資源、存儲資源、數據資源、信息資源、知識資源、專家資源、設備資源的全面共享[1]。很顯然進行網格技術的研究可以借用網絡技術的研究方法，主要有[2]:1)分析方法，就是根據一定的限制條件和合理假設，對研究對象和系統進行初步描述，抽象出研究對象的數學分析模型，利用數學分析模型對問題進行求解。2)實驗方法，就是設計出研究所需的合理硬件和軟件配置環境，建立實驗室，在現實網絡上實現對網絡協議、網絡行為和網絡性能的研究。3)模擬方法，用模擬器來來建立所研究的網格體系的模擬模型，在計算機上運行這個模型，并分析運行的輸出結果。本文就是用模擬方法研究網格中的任務調度問題。

在網格技術飛速發展的同時，網格計算中的任務調度問題也變得越來越重要，任務調度是網格計算中的基本問題之一[3]。

文章首先對Min-min算法進行分析，然后用GridSim對Min-min調度算法進行模擬實現，闡述了用GridSim進行模擬設計的過程，并統計了模擬實現的數據結果，對Min-min算法的MakeSpan和負載等性能進行了分析，驗證了本文模擬實現過程的正確性。

2 網格任務調度算法

任務調度問題的實質就是在一個由m個相互獨立的任務，n個可用的異構資源構成的網格環境下，把m個任務以合理的方式調度到n個資源上去，使得任務的完成行時間(MakeSpan)最小以及資源得到充分合理的利用[4]。

網格環境下的任務調度算法中，Min-min算法是很多研究的基礎[5]。Min-min調度算法的思想是盡可能把每一個任務分配給最早可用且執行最快的機器，Min-min算法是基于最小完成時間MCT(Minimum Completion Time)的，且在每一次映射中考慮的是全部未分配的任務。Min-min算法的主要思想[6]如下:

m個任務在n個不同資源上的最小完成時間MCT是一個m × n的矩陣，矩陣中的每一行代表某一個任務ti∈T(T={t1，t2，……tm})，在n個資源上的不同最小完成時間，每一列代表m個任務在同一個資源上的不同最小完成時間。

當需要調度的任務集合T={t1，t2，...，tm}非空時，反復執行如下操作直至任務集合T為空:

1) 對于集合T中每一個等待分配的任務ti，計算出把該任務分配到n個資源上的n個不同最小完成時間MCT(i，j)，從n個MCT(i，j)中選擇值最小的記為MinMCT(i，j)，即任務ti在資源rj上完成時間最小;

2) 選擇Tlength個任務中具有最小MinMCT(i，j)值的任務ti，將任務ti分配給相對應的資源rj;

3) 從需要調度的非空任務集合T中把任務ti刪除，同時更新MCT矩陣。

4)反復執行該過程，直至需要調度的任務集合T為空。

3 Min-min算法的GridSim模擬實現

GridSim是以工具包的形式發布的，包含SimJava，GridSim和Gridbroker。GridSim可以提供豐富而方便使用的函數庫，用戶可以模擬和創建平行分布計算系統的網格環境中的不同層次的資源(比如時間共享和空間共享)、用戶、應用程序、用戶代理和調度器以進行調度算法的設計和評估。網格資源、用戶和用戶代理被視為不同的實體，它們通過消息事件(輸入和輸出)來進行通信，或者說通過發送和接收事件來實現實體間的交互。在GridSim中每一個資源實體都要向GridInformationService提交resource的注冊。用戶實體則向信息服務的實體查詢資源信息，根據用戶設定的policy來進行任務的調度[7]。圖1是GridSim的模擬流程[8]。

在GridSim進行仿真前，必須要先進行初始化，創建用戶和創建資源，然后才能進行仿真。即創建任務→創建experiment→創建用戶和創建處理器→創建CP→創建資源特征→創建資源。GridSim的主要仿真流程是:初始化各個離散對象→ 啟動仿真→資源的注冊→broker向信息中心查詢資源→broker映射計算→提交任務→資源處理任務→資源返回結果→結束仿真。

Min-min算法的總體模擬設計過程為:通過創建資源實體和Min-min對象，啟動GridSim模擬器，在模擬器中完成任務調度，任務調度完成后，打印出調度結果。詳細過程如下:

1) 初始化GridSim包:在創建任何實體之前都需要初始化GridSim包。設置網格用戶的個數，并調用Calendar的getInstance()方法獲取當前的日期。因為網格事件是很清楚的，所以沒有必要追蹤GridSim事件，從而trace_flag設置為1。生成的報告文件的路徑，在這不需要生成報告文件，從而初始化為1。調用函數GridSim.init初始化GridSim包，并輸出提示。

2) 創建資源實體:通過調用自己定義的函數CreateGridResource()創建資源實體，并記錄資源實體個數。資源實體創建的具體過程包括創建機器列表、創建處理單元列表、創建處理單元并添加到處理單元列表中、創建機器實體、重復操作創建多臺機器、創建資源特性對象、創建網格資源對象。

3) 創建Min-min對象:通過調用自己定義的構造函數創建Min-min對象。

4) 啟動GridSim模擬器:調用GridSim包提供的startGridSimulation()函數啟動GridSim模擬器。

5) 打印輸出結果信息:當GridSim模擬器結束時，調度自定義函數printGridletList()打印出結果信息，并提示模擬器模擬任務調度完成。

4 模擬結果分析

一個好的調度策略要能夠充分使用網格環境中性能各異的各種資源，讓不同的資源都能發揮它的優勢，最大限度地利用網格資源，讓任務盡快的完成。通過對Min-min算法的設計實現，本文通過設置不同的任務數和資源數等參數來分析了算法的相關性能。驗證了Min-min算法模擬實現的正確性和理論結論與實際實現結果的一致性。

本文首先分析每種算法在任務數分別為100，300，500的情況下，隨著資源數量的增加，任務的平均總調度長度MakeSpan的變化，如圖2所示。

從圖2中可以看出Min-min算法在資源數增加時，MakeSpan值隨之減少，而在任務數增加時MakeSpan值都增加。很顯然同理論上相一致，充分說明了本文模擬實現算法的正確性。

然后分析在資源數量為5時，任務數從20以10為一個單元增加到40時每個資源上的負載情況。如圖3所示，這里我們用任務的預測執行時間來表示資源執行任務的負載。

從圖3中，我們可以看出Min-min算法每個資源上的負載很不均衡，如資源3負載過重而資源4相對來說負載較小。

通過模擬實現，更直觀的看出了Min-min算法先完成短任務，然后執行長任務，在資源分配方面，存在負載不均衡的缺點。

5 總結和展望

文章對應用網格任務調度模擬工具GridSim來實現調度算法的設計和實現進行了詳細的闡述，并設計和實現了Min-min調度算法，統計分析了算法的性能。本文工作將作為今后對網格計算中的任務調度算法的模擬實現和相關算法的比較分析工作的研究基礎。

參考文獻:

[1] 曹懷虎，余鎮危，徐壽林.網格環境中任務調度算法的研究[J].計算機工程與應用，2004(5):87-88.

[2] 周翔.關于當前若干主流網絡仿真軟件的綜述及實例應用分析[EB/OL].http://www.router.net.cn/Article/5185.html，2006-09-05.

[3] Braun T，Siegel H，Beck N，et al.A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C].In 8th IEEE Heterogeneous Computing Workshop，Eighth Volume，Issue，Apr.1999:(s)15-29.

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

[5] Tracy D，Howard Jay Siegel，Noah Beck.A comparison of eleven static heuristics for mapping a class of independenttasks onto heterogeneous distributed computing system[J].Journal of Parallel and Distributed Computing，2001(6):810-837.

[6] Wei TY，Zeng WH，Huang BB.Scheduling algorithm based on modified Min-Min in grid[J].Computer Applications，2005，25(5):1190-1192.

[7] Buyya R，Murshed M.GridSim:a Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing[J].Concurrency and Computation:Practice and Experience，2002，14(13-15):1175-1220.

[8] 董子龍.GridSim剖析[EB/OL].http://www.cad.zju.edu.cn/home/zldong/course/Grid/GridSim.pdf，2005.