郝永生，盧俊文，劉冠峰，溫 娜

(1.南京信息工程大學(xué)網(wǎng)絡(luò)信息中心,江蘇 南京 210044;2.廈門理工大學(xué)，福建 廈門 361024；3.蘇州大學(xué)先進(jìn)數(shù)據(jù)分析研究中心，江蘇 蘇州 215006；4.南京信息工程大學(xué)大氣科學(xué)學(xué)院，江蘇 南京 210044)

計(jì)算密集型與數(shù)據(jù)密集型混合網(wǎng)格作業(yè)調(diào)度算法*

郝永生1，盧俊文2，劉冠峰3，溫 娜4

(1.南京信息工程大學(xué)網(wǎng)絡(luò)信息中心,江蘇 南京 210044;2.廈門理工大學(xué)，福建 廈門 361024；3.蘇州大學(xué)先進(jìn)數(shù)據(jù)分析研究中心，江蘇 蘇州 215006；4.南京信息工程大學(xué)大氣科學(xué)學(xué)院，江蘇 南京 210044)

針對(duì)計(jì)算密集型作業(yè)與數(shù)據(jù)密集型作業(yè)混合情況，在一個(gè)作業(yè)有時(shí)間限制的動(dòng)態(tài)環(huán)境中，對(duì)傳統(tǒng)的網(wǎng)格作業(yè)調(diào)度方法進(jìn)行擴(kuò)展，提出了三種網(wǎng)格作業(yè)調(diào)度啟發(fā)式算法:Emin-min、Ebest、Esufferage。并在一個(gè)由多個(gè)Cluster組成的、通過高速網(wǎng)絡(luò)連接的網(wǎng)格模型上，對(duì)三種算法進(jìn)行驗(yàn)證。與Min-min算法的比較結(jié)果顯示：三種算法均優(yōu)于Min-min算法。與ASJS算法比較結(jié)果顯示：Emin-min減少了等待時(shí)間與作業(yè)的makespan; Esufferage算法以減少作業(yè)完成量為代價(jià)，減少了作業(yè)的等待時(shí)間及makespan; Ebest在完成作業(yè)數(shù)量上與ASJS基本保持一致，但卻增加了作業(yè)的等待時(shí)間與makespan。總體上，Emin-min具有比較大的優(yōu)勢。

計(jì)算密集；數(shù)據(jù)密集；作業(yè)調(diào)度；平均執(zhí)行時(shí)間

1 引言

傳統(tǒng)的網(wǎng)格作業(yè)調(diào)度算法，或者是針對(duì)計(jì)算密集型作業(yè)[1,2]，或者是針對(duì)數(shù)據(jù)密集型[3,4]作業(yè),只有少數(shù)網(wǎng)格作業(yè)調(diào)度算法同時(shí)考慮這兩種作業(yè)[4,5]。

基于計(jì)算密集型的網(wǎng)格作業(yè)調(diào)度方法包括：Min-min、Max-min、Sufferage、Fast-fit、Best-fit等[1,2]。Min-min的思想是：計(jì)算參與映射事件的每個(gè)任務(wù)在各個(gè)機(jī)器上的期望完成時(shí)間，找到每個(gè)任務(wù)的最早完成時(shí)間及其對(duì)應(yīng)的機(jī)器；從中找出具有最小最早完成時(shí)間的任務(wù)，將該任務(wù)指派給取最小完成時(shí)間的機(jī)器，直至所有作業(yè)完成。Max-min算法非常類似于Min-min算法，同樣要計(jì)算每一任務(wù)在任一可用機(jī)器上的最早完成時(shí)間，不同的是Max-Min算法首先調(diào)度大任務(wù)，即選擇最早完成時(shí)間最大的任務(wù)映射到所對(duì)應(yīng)的機(jī)器上。Sufferage通過計(jì)算每個(gè)作業(yè)Sufferage值，再選擇使Sufferage值最大時(shí)的作業(yè)-資源配對(duì)進(jìn)行分配。一個(gè)作業(yè)的Sufferage值指這個(gè)作業(yè)最小完成時(shí)間與次小完成時(shí)間的差，其值部分反映了如果不進(jìn)行這樣分配帶來的損失。Fast-fit試圖將作業(yè)分配給最快的資源節(jié)點(diǎn)。Best-fit總是分配給最適合的作業(yè)，即在確保完成時(shí)間(Deadline)的情況下，盡量推遲作業(yè)的完成時(shí)間。

Venugopal S[3]針對(duì)數(shù)據(jù)密集型作業(yè)提出了一種基于集合覆蓋問題(Set Covering Probelm)的調(diào)度算法。任務(wù)由若干作業(yè)組成，不同作業(yè)需要訪問不同的數(shù)據(jù)塊，通過不同策略復(fù)制這些數(shù)據(jù)塊，達(dá)到提高執(zhí)行速度的目的。Kolodziej J等人[4]從數(shù)據(jù)復(fù)制、數(shù)據(jù)分割、數(shù)據(jù)權(quán)限控制、數(shù)據(jù)傳輸?shù)确矫鎸?duì)數(shù)據(jù)密集型作業(yè)進(jìn)行了分析，提出了數(shù)據(jù)感知模型(Data-Aware Schedulers)，并與傳統(tǒng)的數(shù)據(jù)調(diào)度算法相結(jié)合，以適應(yīng)數(shù)據(jù)密集型作業(yè)調(diào)度的要求。Chang R-S等[5]提出了一種自適應(yīng)的評(píng)分機(jī)制ASJS(Adaptive Scoring Job Scheduling algorithm)，根據(jù)資源的特性及網(wǎng)絡(luò)特性對(duì)資源評(píng)分，優(yōu)先分配給得分高的資源。Valliyamma C[6]認(rèn)為資源調(diào)度就是一種交易，交易雙方既考慮資源本身的特性(處理器速度、內(nèi)存、硬盤等)，又考慮網(wǎng)絡(luò)特性(帶寬、數(shù)據(jù)丟失率等)，雙方依據(jù)這些特性進(jìn)行資源分配。一些基于QoS(Quality of Service)[7]的網(wǎng)格作業(yè)調(diào)度算法既可用于計(jì)算密集型作業(yè)，又可用于數(shù)據(jù)密集型作業(yè)，他們往往將作業(yè)的指令數(shù)量和輸入輸出文件的大小、資源的處理速度及網(wǎng)絡(luò)帶寬當(dāng)作不同的屬性進(jìn)行分配調(diào)度。

考慮作業(yè)的時(shí)間(Deadline)[8,9]限制，使計(jì)算密集型與數(shù)據(jù)密集型作業(yè)混合情況下的調(diào)度問題變得更加困難。本文詳細(xì)分析了計(jì)算密集型與數(shù)據(jù)密集型作業(yè)混合情況下的網(wǎng)格作業(yè)調(diào)度問題，通過對(duì)傳統(tǒng)的網(wǎng)格作業(yè)調(diào)度算法進(jìn)行擴(kuò)展，提出了三種調(diào)度算法：Emin-min、Ebest、Esufferage。并在Gridsim平臺(tái)上，與ASJS及Min-min算法進(jìn)行了比較，分析了其各自的特點(diǎn)。選擇這兩個(gè)算法進(jìn)行比較的原因是：Min-min算法在過去的驗(yàn)證中顯示了比較好的性能，而ASJS算法適合于處理多種作業(yè)混合情況下的調(diào)用。

2 網(wǎng)格模型

我們采用的網(wǎng)格模型與文獻(xiàn)[5]的基本相同。假設(shè)用戶與路由器、Portal、Job Scheduler之間由高速網(wǎng)絡(luò)互連(如圖1所示)。圖1中p是數(shù)據(jù)密集型作業(yè)的比率，則計(jì)算密集型作業(yè)的比率為1-p。對(duì)于數(shù)據(jù)密集型作業(yè)，根據(jù)其文件大小又可分為大數(shù)據(jù)密集型作業(yè)(簡稱大作業(yè))及小數(shù)據(jù)密集型作業(yè)(簡稱小作業(yè))。q是大作業(yè)的比率，則小作業(yè)的比率為1-q。就全部作業(yè)而言，大作業(yè)的比率為pq，小作業(yè)比率為p(1-q)。為討論方便，做如下假設(shè)：

文件大小在[1 500 MB，3 000 MB]為大文件，其概率為q；

文件大小在[500 MB，1 500 MB]為小文件，其概率為1-q。

作業(yè)的文件大小是指輸入輸出文件大小之和。對(duì)于多個(gè)輸入輸出文件當(dāng)作一個(gè)文件對(duì)待。

Figure 1 System model圖1 系統(tǒng)結(jié)構(gòu)

作業(yè)的描述如下:jobi(ini,fsize,deadline,avi)。jobi.ini、jobi.fsize、jobi.deadline、jobi.avi分別指作業(yè)的指令數(shù)量、作業(yè)輸入輸出文件大小、作業(yè)的時(shí)間期限及作業(yè)到達(dá)時(shí)間。對(duì)于計(jì)算密集型作業(yè)，其輸入輸出的文件大小為0。資源描述如下:rj(proc,bw,avai)。rj.proc、rj.bw、rj.avai分別指資源的處理速度、網(wǎng)絡(luò)帶寬及空閑的時(shí)間點(diǎn)。假設(shè)所有資源都是空間共享(space-shared)型,即同一時(shí)間內(nèi)，一個(gè)資源只能被分配一個(gè)作業(yè)。

jobi若分配給rj，其執(zhí)行時(shí)間Ext(i,j)為：

(1)

rj的開始空閑時(shí)間為rj.avai，若jobi分配給rj，則jobi的完成時(shí)間c(i,j)為：

c(i,j)=Ext(i,j)+rj.avai

(2)

為確保作業(yè)在時(shí)間期限(deadline)前執(zhí)行完成：

(3)

如果jud(jobi,rj)的值為1，則jobi可以在rj上按照deadline要求執(zhí)行；否則,不能執(zhí)行。

若系統(tǒng)真正將jobi分配給rj，則資源rj再次可接收作業(yè)的時(shí)間rj.avai為:

rj.avai=Ext(i,j)+rj.avai

(4)

rj.avai表示資源分配作業(yè)后，下次可接收作業(yè)的時(shí)間。實(shí)際上，由于準(zhǔn)確估計(jì)作業(yè)的執(zhí)行時(shí)間是比較困難的，在實(shí)際系統(tǒng)中，這個(gè)值以作業(yè)完成時(shí)間為準(zhǔn)。

作業(yè)數(shù)量為jend，所有作業(yè)集合為：

(5)

資源數(shù)量為rend，所有資源集合為：

(6)

更一般地描述，假設(shè)每個(gè)作業(yè)有l(wèi)個(gè)屬性(這里的屬性可以包括帶寬、內(nèi)存、CPU速度等)，則J描述如下：

(7)

同樣，資源也具有l(wèi)個(gè)屬性,資源描述如下：

(8)

RJ是一個(gè)l×l矩陣，若資源ri的所有屬性均滿足jobj的要求，則RJ(i,j)=1;若ri存在屬性不能滿足jobj的要求，則RJ(i,j)=0。jobj在ri上可以被執(zhí)行的條件是：

(?temp)ri.atttemp>jobj.atttemp,1

(9)

根據(jù)公式(3)，令：

RJ(i,j)=jud(jobi,rj)

(10)

3 具有截止時(shí)間的作業(yè)調(diào)度算法

在網(wǎng)格中，作業(yè)調(diào)度問題是一個(gè)NP問題，一般借助啟發(fā)式算法解決。傳統(tǒng)的以最小作業(yè)完成時(shí)間為目標(biāo)的批處理啟發(fā)算法包括Min-min、Max-min、Fast-fit、Best-fit、Sufferage等等。本節(jié)以Min-min、Best-fit、Sufferage算法為框架，提出了計(jì)算密集型作業(yè)和數(shù)據(jù)密集型作業(yè)混合情況下的三種啟發(fā)式算法，即Emin-min、Ebest、Esufferage。

在考慮到作業(yè)具有deadline的情況下，采用緊迫型作業(yè)優(yōu)先調(diào)度原則，即如果能保證作業(yè)在deadline前完成的資源有限，那么立即調(diào)度這個(gè)作業(yè)。實(shí)際應(yīng)用中，以可以按要求執(zhí)行這個(gè)作業(yè)的資源比率rrat為準(zhǔn)。如果小于這個(gè)比率，那么這個(gè)作業(yè)是緊迫型作業(yè)，立即執(zhí)行。

3.1Emin-min

算法思想：首先根據(jù)公式 (1)和公式(2)，對(duì)每個(gè)作業(yè)計(jì)算在各個(gè)資源上的完成時(shí)間，取最小值的作業(yè)-資源對(duì)進(jìn)行分配，更新被分配資源的下次可用時(shí)間Ext(i,j)，直至所有滿足條件的作業(yè)被完成。這里滿足條件是指先前能被執(zhí)行的作業(yè)，有些作業(yè)因?yàn)橛衐eadline要求，等待時(shí)間超過期限，導(dǎo)致不能被執(zhí)行。

算法1Emin-min

輸入：資源集合R及作業(yè)集合J;

輸出：作業(yè)分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 計(jì)算 jud(jobi,rj)；

8.Ifjud(jobi,rj)==1

9. 計(jì)算Ext(i,j)；

10.If(minvalue> Ext(i,j))

11. selectr= rj;

12. selectj= jobi;

13. minvalue= Ext(i,j);

14.Endif

15.Endif

16.Endfor

17.Endfor

18. 將selectj分配給selectr；

19. 更新selectj.avai;

20. 對(duì)緊迫型作業(yè)進(jìn)行調(diào)度；

21.While(所有適合要求的作業(yè)都被完成)

算法中，minvalue用于記錄最小的完成時(shí)間，selectr和selectj分別記錄最小完成時(shí)間時(shí)所選擇的資源和作業(yè)。第2～第4行是算法初始化，第5～第7行尋找執(zhí)行時(shí)間最小的資源-作業(yè)配對(duì)，第18～第20行完成資源分配。

3.2 Ebest

為了得到一個(gè)更好的調(diào)度效果，使更多的作業(yè)能被執(zhí)行，我們優(yōu)先考慮時(shí)間期限緊迫的作業(yè)。jobi若分配給rj，其執(zhí)行完成時(shí)間為c(i，j)，其與jobi.deadline的差距ts(i,j)反映了這個(gè)作業(yè)的緊迫程度。

ts(i,j)=jobi.deadline-c(i,j)

(11)

若ts(i，j)<0，則說明這樣分配不能保證作業(yè)在指定時(shí)間內(nèi)完成，選擇其值為非負(fù)且最小的作業(yè)-資源進(jìn)行映射。算法描述如下:

算法2Ebest

輸入：資源集合R及作業(yè)集合J;

輸出：作業(yè)分配方案。

1.Do

2. minvalue=0;

3. selectr=-1;

4. selectj=-1;

5.Foreveryjobi∈J

6.Foreveryrj∈R

7. 計(jì)算ts(i,j)；

8.If((minvalue> ts(i,j) &ts(i,j)>=0) )

4. selectr= rj;

5. selectj= jobi;

6. minvalue= ts(i,j);

7.Endif

8.Endfor

9.Endfor

10. 將selectj分配給selectr；

11. 更新selectj.avai;

12. 對(duì)緊迫型作業(yè)進(jìn)行調(diào)度；

13.While(所有適合要求的作業(yè)都被完成)

這里可以將作業(yè)的deadline當(dāng)作作業(yè)一個(gè)屬性處理，此作業(yè)在某個(gè)資源上的完成時(shí)間當(dāng)作這個(gè)資源的一個(gè)屬性對(duì)待。第2～第4行是算法初始化，第5～第7行尋找使公式(11)取最小值的資源-作業(yè)配對(duì)，第15～第17行完成資源分配。

3.3 Esufferage

算法思想：分別計(jì)算每個(gè)作業(yè)的最小完成時(shí)間和次小完成時(shí)間，選擇兩者值相差最大的作業(yè)-資源進(jìn)行配對(duì)。

算法3Esufferage

輸入：資源集合R及作業(yè)集合J;

輸出：作業(yè)分配方案。

1.Do

2. maxvalue=0;

3. selectr=-1;

4. selectj=-1;

5. first(i)記錄jobi最小完成時(shí)間；

6. second(i)記錄jobi次小完成時(shí)間；

7.Foreveryjobi∈J

8.Foreveryrj∈R

9. 計(jì)算c(i,j)；

10.Endfor

11.Endfor

12. 計(jì)算first(i),i∈{1,2,…,jend}；

13. 計(jì)算second(i),i∈{1,2,…,jend}；

14.Foreveryjobi∈J

15.If(maxvalue<(second(i)- first(i)) )

16. selectr= rj;

17. selectj= jobi;

18. maxvalue=max(second(i)-first(i));

19.Endif

20.Endfor

21. 將selectj 分配給selectr；

22. 更新selectj.avai;

23. 對(duì)緊迫型作業(yè)進(jìn)行調(diào)度；

24.While(所有適合要求的作業(yè)都被完成)

maxvalue記錄最小完成時(shí)間與次小完成時(shí)間差的最大值。first(i)、second(i)分別記錄jobi最小完成時(shí)間及次小完成時(shí)間。第2～第4行是算法初始化，第5～第13行計(jì)算每個(gè)作業(yè)的最小完成時(shí)間和次小完成時(shí)間，第14～第20行尋找最小完成時(shí)間與次小完成時(shí)間的最大差值，第21～第23行進(jìn)行資源分配并更新資源狀況。

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

采用Gridsim[10]作為模擬器，Gridsim可以實(shí)現(xiàn)比較復(fù)雜的網(wǎng)格調(diào)度模擬?；贖aoY等人[8]先前的工作，對(duì)于Gridsim進(jìn)行了關(guān)于時(shí)間期限的擴(kuò)展。因此，采用Gridsim模擬數(shù)據(jù)密集型作業(yè)和計(jì)算密集型作業(yè)的混合調(diào)度。

作業(yè)數(shù)量為10 000，作業(yè)到達(dá)速率為20、22、24、26、28、30。數(shù)據(jù)密集型作業(yè)的比率(p)為0.30、0.50、0.70。大數(shù)據(jù)密集型作業(yè)比率(q)為0.30，0.50，0.70。作業(yè)需要傳輸?shù)奈募笮?jobi.ini)是[500，3 000](單位：百萬條指令)的一個(gè)整數(shù)，大數(shù)據(jù)密集型作業(yè)的文件大小(jobi.fsize)是[1 500MB,3 000MB]的一個(gè)隨機(jī)整數(shù)，小數(shù)據(jù)密集型作業(yè)的文件大小(jobi.fsize)是[500MB，1500MB]的一個(gè)隨機(jī)整數(shù)。系統(tǒng)有50個(gè)資源節(jié)點(diǎn)。資源帶寬(rj.bw)是[1.1，1.2，1.3，1.4，1.5]中的一個(gè)數(shù)值(單位Gs)，資源處理速度是[5，15]的一個(gè)隨機(jī)整數(shù)。作業(yè)的deadline是[1，5]的一個(gè)隨機(jī)整數(shù)。這些參數(shù)均服從均勻分布。模擬結(jié)果是10次模擬所得平均數(shù)。在實(shí)驗(yàn)中采用緊迫型作業(yè)優(yōu)先調(diào)度原則，令rrat=20%。ASJS對(duì)于資源的帶寬屬性和計(jì)算能力屬性分配不同的權(quán)重，根據(jù)ChangR-S[5]的模擬結(jié)果，其權(quán)重取值如表1所示。

Figure 2 Average makespan of different arrival rates圖2 不同到達(dá)率下的平均makespan AMJ

p計(jì)算能力權(quán)重帶寬權(quán)重0.30.30.70.50.50.50.70.70.3

在模擬實(shí)驗(yàn)中，考察的參數(shù)包括：未完成的作業(yè)數(shù)量(UFJ)、平均等待時(shí)間(AWT)、平均makespan(AMJ)。makespan指從作業(yè)進(jìn)入等待隊(duì)列開始到作業(yè)被執(zhí)行的時(shí)間。

4.2 仿真結(jié)果與性能分析

圖2～圖4分別描述系統(tǒng)的UFJ、AWT、AMJ?？傮w上，AWT、AMJ都隨著作業(yè)到達(dá)速率、p、q的增加而增加，這是因?yàn)殡S著到達(dá)速率、p、q的增加，系統(tǒng)負(fù)載也隨著增加，使作業(yè)的makespan及等待時(shí)間增大。當(dāng)?shù)竭_(dá)速率小于22時(shí)，各個(gè)算法的完成數(shù)量總體保持相同；當(dāng)?shù)竭_(dá)速率超過26后，各個(gè)算法未完成作業(yè)數(shù)量的增加速度明顯加快，這是因?yàn)橄到y(tǒng)趨于過載狀態(tài)，不能在有效時(shí)間內(nèi)完成的作業(yè)越來越多。

AMJ(圖 2)與AWT(圖 3)具有相同的趨勢。總體上，平均等待時(shí)間與makespan隨著到達(dá)率的增加而增加。這是因?yàn)橄到y(tǒng)負(fù)載的增加延長了作業(yè)的等待時(shí)間和執(zhí)行時(shí)間。這五種算法的AMJ及AWT值從大到小的順序是：Min-min、ASJS、Ebest、Emin-min、Esufferage。與Min-min相比、Ebest、Emin-min、Esufferage三種算法的執(zhí)行時(shí)間分別減少了8.32%、15.51%、24.20%。

未完成作業(yè)的數(shù)量隨著p、q及到達(dá)率(ArrivalRate)的增加而增加。Min-min算法具有最大的未完成作業(yè)數(shù)量(如圖4所示)。與Min-min相比、Ebest、Emin-min、Esufferage三種算法的未完成作業(yè)數(shù)量分別減少了18.74%、22.18%、5.33%。這是因?yàn)镸in-min沒有考慮到資源的特性及作業(yè)的deadline，所以表現(xiàn)較差。Eminmin、Ebest、ASJS算法的未完成的作業(yè)數(shù)量基本保持一致且均小于Min-min及Esufferage。

Esufferage以丟棄部分作業(yè)為代價(jià)獲得了最小的makespan和等待時(shí)間(圖2和圖3中，Esufferage的AMJ和AWT均保持最小值)。Ebest由于總是盡量推遲作業(yè)的執(zhí)行時(shí)間，導(dǎo)致了作業(yè)的等待時(shí)間與makespan值最大，但同時(shí)也保證了系統(tǒng)完成的作業(yè)數(shù)量增加(圖2和圖3中，Ebest具有較大的AWT和AMJ。圖4中，Ebest具有較小的UFJ)。

Figure 3 Average waiting time of different arrival rates圖3 不同到達(dá)率下的平均等待時(shí)間AWT

Figure 4 Unfinished job number of different arrival rates圖4 不同到達(dá)率下的平均未完成作業(yè)數(shù)量UFJ

ASJS采用最高評(píng)分的方式選取資源，這在計(jì)算密集與數(shù)據(jù)密集型作業(yè)情況下選擇“最快”的策略基本相同。所以，Emin-min與ASJS在各個(gè)參數(shù)上均有近似的表現(xiàn)(如圖2～圖4所示)。 Emin-min與ASJS的平均等待時(shí)間AWT、平均執(zhí)行時(shí)間AMJ、未完成作業(yè)的平均比值分別為：0.9645∶ 1，0.9828∶1，1.0155∶1。ASJS的評(píng)分雖然具有動(dòng)態(tài)性，但并沒有考慮資源的特性，評(píng)分高的資源，并不能保證所有作業(yè)都適合執(zhí)行。如果一個(gè)具有大的輸入輸出文件的作業(yè)被分配到一個(gè)帶寬小卻具有快速處理能力(資源評(píng)分高)的資源節(jié)點(diǎn)上，那么這個(gè)作業(yè)也不能在很短的時(shí)間內(nèi)完成，導(dǎo)致了作業(yè)執(zhí)行時(shí)間增加。采用緊迫型作業(yè)優(yōu)先調(diào)度的Emin-min算法，則在各個(gè)方面均表現(xiàn)出色。

5 結(jié)束語

本文提出了Esufferage、Ebest及Emin-min算法，用于混合作業(yè)的調(diào)度，并在模擬網(wǎng)格上對(duì)三個(gè)算法進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)表明，Esufferage以少完成部分作業(yè)為代價(jià)，減少了等待時(shí)間及makespan；Ebest雖然具有比較大的等待時(shí)間及makespan，但卻減少了未完成作業(yè)數(shù)量；Emin-min與ASJS相比，在保證完成作業(yè)的同時(shí)，減少了作業(yè)的平均等待時(shí)間和makespan。實(shí)驗(yàn)顯示，這三種算法均優(yōu)于傳統(tǒng)的Min-min算法。

本文在動(dòng)態(tài)環(huán)境下，對(duì)計(jì)算密集型作業(yè)和數(shù)據(jù)密集型作業(yè)進(jìn)行了分析,但缺少對(duì)QoS[9]的研究。由于不同的用戶對(duì)QoS有不同要求，對(duì)用戶的QoS偏好[12]選擇，也是一個(gè)需要進(jìn)一步研究的課題。

[1] Maheswaran M,Ali S, Siegel H J, et al. Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop,1999:30-44.

[2] Braun T D,Siegel H J,Beck N,et al. A comparison study of static mapping heuristics for a class of metatasks on heterogeneous computing systems[C]∥Proc of the 8th IEEE Heterogeneous Computing Workshop, 1999:15-29.

[3] Venugopal S, Buyya R. An SCP-based heuristic approach for scheduling distributed data-intensive applications on global grids[J]. Journal of Parallel and Distributed Computing,2008, 68(4):471-487.

[4] Kolodziej J, Xhafa F,Barolli L, et al. A taxonomy of data scheduling in data grids and data centers:Problems and intelligent resolution techniques[C]∥Proc of 2011 International Conference on Emerging Intelligent Data and Web Technologies (EIDWT),2011:63-71.

[5] Chang Ruay-Shiung, Lin Chih-Yuan, Lin C F. An adaptive scoring job scheduling algorithm for grid computing[J]. Information Sciences,2012,207:79-89,DOI:10.1016/j.ins.2012.04.019.

[6] Valliyamma C,Somasundaram T S. A grid resource brokering strategy based on resource and network performance in grid[J]. Future Generation Computer Systems,2012, 28(3):491-499.

[7] Wang W, Luo J Z,Song A B. A GQoP guaranteed grid QoS adaptive scheduling algorithm[J]. Journal of Computer Research and Development, 2011,48(7):1168-1177.(in Chinese)

[8] Hao Yong-sheng,Liu Guan-feng,Wen Na. An enhanced load balancing mechanism based on deadline control on GridSim[J].Future Generation Computer Systems,2012.28(4):657-665,DOI:10.1016/j.future.2011.10.010.

[9] Li X, Hu Z G, Hu Z J, et al. Grid workflow scheduling algorithms based on deadline Satisfaction[J]. Journal of Computer Research and Development, 2011,48(5):877-884.(in Chinese)

[10] GridSim Toolkit 5.0,GridSim:A toolkit for modeling and simulating grid computing environments [EB/OL].[2013-05-01]. http://www.buyya.com/gridsim/.

[11] Albodour R, James A, Yaacob N. High level QoS-driven model for grid applications in a simulated environment[J]. Future Generation Computer Systems,2012, 28(7):1133-1144.

[12] Xiong Run-qun, Luo Jun-zhou, Song Ai-bo, et al. QoS preference-aware replica selection strategy in cloud computing[J]. Journal on Communications, 2011,32(7):93-102.(in Chinese)

附中文參考文獻(xiàn):

[7] 王巍,羅軍舟,宋愛波.一種具有GQoP保證的網(wǎng)格QoS自適應(yīng)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展,2011,48(7):1168-1177.

[9] 李璽,胡志剛,胡周君,等.基于截止時(shí)間滿意度的網(wǎng)格工作流調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展,2011,48(5):877-884.

[12] 熊潤群,羅軍舟,宋愛波,等.云計(jì)算環(huán)境下QoS 偏好感知的副本選擇策略[J].通訊學(xué)報(bào),2011,32(7):93-102.

HAOYong-sheng,born in 1980,MS,engineer,his research interest includes grid computing, and cloud computing.

盧俊文(1983-),男，福建廈門人，碩士，講師，研究方向?yàn)榫W(wǎng)格計(jì)算和云計(jì)算。E-mail:swordmenstory@163.com

LUJun-wen,born in 1983,MS,lecturer,his research interests include grid computing, and cloud computing.

劉冠峰(1983-),男，山東青島人，博士，副教授，研究方向?yàn)榫W(wǎng)格計(jì)算和云計(jì)算。E-mail:gfliu@suda.edu.cn

LIUGuan-feng,born in 1983,PhD,associate professor,his research interests include grid computing, and cloud computing.

Threegridjobschedulingmethodsheuristicsfordata-intensiveandcomputing-intensivejobs

HAO Yong-sheng1,LU Jun-wen2,LIU Guan-feng3,WEN Na4

(1.Network Center,Nanjing University of Information Science & Technology,Nanjing 210044；2.Xiamen University of Technology,Xiamen 361024;3.Soochow Advanced Data Analytics Lab,Soochow University,Suzhou 215006;4.College of Atmospherics Science,Nanjing University of Information Science & Technology,Nanjing 210044,China)

Most of the existing grid job scheduling methods focus on either data-intensive jobs or computing-intensive jobs.In the dynamic environment where every job has its deadline,we extend the traditional grid job scheduling methods to propose three new grid job scheduling methods:Emin-min,Ebest and Esufferage.The three methods are validated on the Grid model with clusters that are connected by the high speed network.Simulation results demonstrate that our proposed methods are better than Min-min.The comparison between the three methods and ASJS shows that,Emin-min reduces the waiting time and makespan,Esufferage reduces the waiting time and the makespan greatly with the sacrifice of some jobs,and Ebest gives the same performance in unfinished jobs but has a larger value in waiting time and makespan than ASJS. In general,Eminmin has a better performance than Min-min and ASJS.

computing-intensive;data-intensive;job scheduling;average makespan

1007-130X(2014)08-1423-07

2013-03-20;

：2013-05-20

福建省教育廳科技項(xiàng)目B類(JB09199)；國家自然科學(xué)基金資助項(xiàng)目(41005048)；科技部資助項(xiàng)目(GYHY201106037，GYHY200906023)

TP391.9

：A

10.3969/j.issn.1007-130X.2014.08.001

郝永生(1980-),男，安徽懷寧人，碩士，工程師，研究方向?yàn)榫W(wǎng)格計(jì)算和云計(jì)算。E-mail:hyslove@163.com

通信地址：210044 江蘇省南京市南京信息工程大學(xué)網(wǎng)絡(luò)信息中心

Address:Network Center,Nanjing University of Information Science & Technology,Nanjing 210044,Jiangsu,P.R.China