Min—Min任務(wù)調(diào)度算法的研究與仿真

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

關(guān)鍵詞：Min-Min算法；任務(wù)調(diào)度；GridSim模擬器

1 概述

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

2 Min-Min算法

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

（1）假設(shè)網(wǎng)格任務(wù)集為Tasks={T1，T2，T3，... ，Tn}，集合內(nèi)有n個待調(diào)度的獨立任務(wù)。

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

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

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

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

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

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

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

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

如果任務(wù)集合Tasks不為空時，重復(fù)以下步驟直到任務(wù)全部調(diào)度。

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

（3）把該任務(wù)Ti提交到對應(yīng)的資源Hj上執(zhí)行，同時還要更新此ECT矩陣。

3 Min-Min算法的模擬實現(xiàn)

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

int JOB_NUM = 10， RES_NUM = 4；// 任務(wù)數(shù)與資源數(shù)

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

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

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

int MAX_JOB_RUN_TIME = 0x7ffffff；

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

int host_minCT[] = new int[JOB_NUM]； // 任務(wù)最小完成時間對應(yīng)的主機

int scheduled = 0； // 調(diào)度的任務(wù)數(shù)，初始為0；

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

while （scheduled < JOB_NUM） {

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

{ // 計算每個任務(wù)的預(yù)測完成時間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]]）；

//提交任務(wù)到資源

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

scheduled++；

}

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

當(dāng)JOB_NUM為100，RES_NUM為10，采用以上同樣的方式調(diào)度，計算出Makespan的值為1000。當(dāng)JOB_NUM為150，資源數(shù)RES_NUM為10，得出的模擬結(jié)果Makespan的值為1620。當(dāng)任務(wù)數(shù)JOB_NUM為200，資源數(shù)RES_NUM為10，得出的模擬結(jié)果Makespan的值為2100。

由以上的實驗，我們可以得到如圖1模擬結(jié)果，其中橫坐標(biāo)表示任務(wù)數(shù)，縱坐標(biāo)為整個調(diào)度系統(tǒng)所有的時間。

4 結(jié)束語

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

參考文獻

[1]王建鋒.網(wǎng)格計算的應(yīng)用及發(fā)展前景[J].大眾科技，2005.

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

[3]王向慧.網(wǎng)格計算中任務(wù)調(diào)度算法的改進[D].2009.

[4]吳淞.基于網(wǎng)格仿真平臺GRIDSIM的任務(wù)調(diào)度算法[D].

2006.