Min—Min任務調度算法的研究與仿真

摘 要：文章首先對Min-Min算法進行分析，介紹了算法的思想和執行過程。然后使用GridSim模擬器對算法模擬實現，給出了算法的JAVA實現代碼，并統計了Min-Min算法實驗結果的完成時間。

關鍵詞：Min-Min算法；任務調度；GridSim模擬器

1 概述

在網格計算中，大量的計算任務被調度到資源上，如何使任務得到最少的完成時間，在很大程度上是由它的調度算法所決定的[1]。良好的任務調度算法是任務調度的重要組成部分。目前，關于網格計算的任務調度算法，國內外學者已經取得了大量的研究成果。這些調度算法大多是基于啟發式的思想來解決問題的，比如有遺傳算法、螞蟻算法、Min-Min算法、Max-Min算法等[2]。由于Min-Min算法是一個經典的任務調度算法，文章對Min-Min算法進行研究，然后用模擬器對算法模擬實現。

2 Min-Min算法

為了研究的方便，文章進行了如下的定義：

（1）假設網格任務集為Tasks={T1，T2，T3，... ，Tn}，集合內有n個待調度的獨立任務。

（2）網格資源集為Hosts={H1，H2，H3，...，Hm}，該資源集合內有m個資源。設資源Hj的就緒時間（即資源最早的可以使用的時間）為R（j）。

（3）任務Ti在資源Hj上的完成時間定義為ECT（i，j），定義任務在資源上的執行時間為ETC（i，j）。

（4）從上面定義得出，一個任務Ti在資源Hj上的完成時間計算公式如下：

ECT（i，j）=ETC（i，j）+R（j）

（5）n個任務在m個資源上的ETC可以用一個n×m的矩陣來表示，矩陣元素ETC（i，j）表示第i個任務在第j個資源上的執行時間，該矩陣的一行表示任務Ti在資源集合Hosts中所有資源的執行時間，一列表示在同一資源上n個任務的執行時間。

Min-Min算法的思想是：首先，計算出任務列表中所有任務在所有資源上的最小完成時間。其次，從這些最小完成時間中找出一個值最小的，把這個最小時間對應的任務資源對找出來，把該任務提交給該資源執行，從任務列表中刪除這個任務。最后，更新最小完成時間矩陣。重復以上步驟，直到任務列表為空。該算法的目的是將任務指派給不僅完成它最早的，而且執行它最快的機器，使得全部的任務完成時間最小[3]。該算法的執行過程如下：

（1）計算任務集合中的任務Ti在m個資源上的完成時

間，得到n×m的ECT矩陣。

如果任務集合Tasks不為空時，重復以下步驟直到任務全部調度。

（2）得出每個任務的最小完成時間即ECT（i，j），把這些最小完成時間放入一個集合M內，然后找出這個集合內最小的值，根據最小值所對應的任務資源對（i，j），這就是任務到資源的映射。

（3）把該任務Ti提交到對應的資源Hj上執行，同時還要更新此ECT矩陣。

3 Min-Min算法的模擬實現

文章采用GridSim模擬器對該算法進行仿真實驗，GridSim工具包設計的實體類有：Gridlet類、User類、Broker類、Resource類、GIS類等[4]。Gridlet類是用來對任務進行描述的，包含的屬性有任務ID，任務的狀態，任務的計算量。User類是描述網格上的用戶，一個用戶有唯一的ID。Broker類是用戶的代理。Resource類是描述網格上異構資源的類，通常一個資源類包括多個Machine類，一個Machine類由多個PE組成。GIS是網格的信息服務中心，它負責資源的發現、注冊和管理的功能。使用模擬器編寫一個MyTest繼承GridSim類，然后編寫Min-Min算法如下關鍵代碼：

int JOB_NUM = 10， RES_NUM = 4；// 任務數與資源數

double ETC[][] = new double[JOB_NUM][RES_NUM]；

double CT[][] = new double[JOB_NUM][RES_NUM]；

double R[] = new double[RES_NUM]； //資源就緒時間數組

int MAX_JOB_RUN_TIME = 0x7ffffff；

double minCT[] = new double[JOB_NUM]； //任務的最小完成時間數組

int host_minCT[] = new int[JOB_NUM]； // 任務最小完成時間對應的主機

int scheduled = 0； // 調度的任務數，初始為0；

int min_minCT_index=0； //具有最小完成時間的任務索引號

while （scheduled < JOB_NUM） {

for （int i = 0； i < JOB_NUM； i++）

{ // 計算每個任務的預測完成時間CT[i][j]

Gridlet gridlet= （Gridlet） list_.get（i）；

for （int j = 0； j < RES_NUM； j++） {

int mip = resCharS[j].getMIPSRating（）；

if （ETC[i][j] ==Double.MAX_VALUE）

{

CT[i][j] = ETC[i][j]；

} else

{

ETC[i][j]=gridlet.getGridletLength（）/mip；

CT[i][j] = ETC[i][j] + R[j]； // CT[i][j]

}

}

}

for （int i = 0； i < JOB_NUM； i++）

{

for （int j = 0； j < RES_NUM； j++）

{

if （CT[i][j] < minCT[i]）

{

minCT[i] = CT[i][j]； // 計算minCT

host_minCT[i] = j； // 計算host_minCT

}

}

}

for （int i = 0； i < JOB_NUM； i++）

{

if （（minCT[i] ！= 0） （minCT[i] < minCT

[min_minCT_index]））

{

min_minCT_index = i；

}

}

Gridlet gridlet = （Gridlet） this.list_.get（min_minCT_index）；

super.gridletSubmit（gridlet，resourceID[host_minCT[min_minCT_index]]）；

//提交任務到資源

R[host_minCT[min_minCT_index]]+= minCT[min_minCT_index]；

scheduled++；

}

根據以上代碼進行仿真實驗，任務數JOB_NUM為50，資源數RES_NUM為10，仿真實驗進行100次，用Min-Min算法進行任務調度，得到的Makespan去平均值。經模擬實驗計算出Makespan的值為550。

當JOB_NUM為100，RES_NUM為10，采用以上同樣的方式調度，計算出Makespan的值為1000。當JOB_NUM為150，資源數RES_NUM為10，得出的模擬結果Makespan的值為1620。當任務數JOB_NUM為200，資源數RES_NUM為10，得出的模擬結果Makespan的值為2100。

由以上的實驗，我們可以得到如圖1模擬結果，其中橫坐標表示任務數，縱坐標為整個調度系統所有的時間。

4 結束語

基于以上對Min-Min算法的分析，我們可以得出Min-Min算法由于對任務選擇執行它最快的資源，因此，它的完成時間較快。在今后的網格計算研究中，還需要考慮其它的因素，比如經濟原則、負載均衡和服務質量，對改進后的算法使用GridSim模擬器進行仿真驗證。

參考文獻

[1]王建鋒.網格計算的應用及發展前景[J].大眾科技，2005.

[2]Ian Foster， Carl Kesselman. The Grid： Blueprint for a New Computing Infrastrueture[M].Morgan Kaufmann Publishers，1999：1-30.

[3]王向慧.網格計算中任務調度算法的改進[D].2009.

[4]吳淞.基于網格仿真平臺GRIDSIM的任務調度算法[D].

2006.