趙英，李棟

（北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029）

網(wǎng)格通過(guò)網(wǎng)絡(luò)連接地理上分布的各種資源，形成一個(gè)對(duì)用戶相對(duì)透明的環(huán)境。在網(wǎng)格技術(shù)[1]中，任務(wù)調(diào)度是一個(gè)研究熱點(diǎn)。任務(wù)調(diào)度的目的是對(duì)所有任務(wù)進(jìn)行合理調(diào)度，使其完成時(shí)間盡可能的短，并且盡可能地提高系統(tǒng)資源的利用率。

經(jīng)典的任務(wù)調(diào)度算法有遺傳算法[2]、模擬退火算法、Suffrage[3]算法、Min-Min[4]算法、Max-Min 算法等，這些算法被廣泛應(yīng)用于網(wǎng)格任務(wù)調(diào)度。其中Min-Min算法是一種簡(jiǎn)單快速的算法，但它忽略了網(wǎng)格任務(wù)對(duì)QoS[5]的要求。本文對(duì)網(wǎng)格任務(wù)的優(yōu)先級(jí)進(jìn)行劃分和量化，結(jié)合網(wǎng)格任務(wù)的等待時(shí)間，提出了一種基于權(quán)值的改進(jìn)Min-Min網(wǎng)格任務(wù)調(diào)度算法，并通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了其有效性。

1 網(wǎng)格任務(wù)調(diào)度

與傳統(tǒng)的任務(wù)調(diào)度相比，網(wǎng)格任務(wù)調(diào)度必須針對(duì)網(wǎng)格資源的特點(diǎn)進(jìn)行[6]。網(wǎng)格資源具有以下3個(gè)特點(diǎn)：

1）異構(gòu)性 每個(gè)網(wǎng)格資源都不盡相同，主要體現(xiàn)在計(jì)算資源、存儲(chǔ)資源和網(wǎng)絡(luò)資源等方面的差異。同樣的一個(gè)任務(wù)在不同資源上執(zhí)行的時(shí)間不同，通信方式有可能不同，網(wǎng)絡(luò)延遲也會(huì)不同。

2）動(dòng)態(tài)性 網(wǎng)格資源工作時(shí)性能會(huì)不斷變化，有些時(shí)候還會(huì)出現(xiàn)故障，比如斷電等，調(diào)度必須考慮這些突發(fā)因素來(lái)適應(yīng)網(wǎng)格資源的動(dòng)態(tài)性。

3）獨(dú)立自主性 每個(gè)網(wǎng)格資源都具有獨(dú)立自主性，不受網(wǎng)格的完全控制，正是由于這個(gè)特性，網(wǎng)格資源不能專用于某個(gè)應(yīng)用。

網(wǎng)格任務(wù)調(diào)度問(wèn)題通常被認(rèn)為是一個(gè)NP問(wèn)題，其完成時(shí)間隨著任務(wù)規(guī)模的增長(zhǎng)而呈現(xiàn)指數(shù)級(jí)的增長(zhǎng)。在實(shí)際的任務(wù)調(diào)度過(guò)程中，除了要考慮完成時(shí)間這個(gè)因素外，還有一些其它重要因素也是需要考慮的：

1）經(jīng)濟(jì)原則 網(wǎng)格資源不是無(wú)償使用的，用戶在使用資源的同時(shí)應(yīng)對(duì)資源的提供者繳納一定的費(fèi)用作為補(bǔ)償。一旦涉及到利益，所有網(wǎng)格用戶的目標(biāo)是在滿足一定條件下使自己的收益最大化或者成本最小化。在網(wǎng)格任務(wù)調(diào)度的經(jīng)濟(jì)調(diào)度模型中，需要綜合考慮任務(wù)成本和執(zhí)行時(shí)間[7]，要么優(yōu)先任務(wù)成本，要么優(yōu)先執(zhí)行時(shí)間，兩者不可兼得。

2）QoS（Quality of Service）要求 在網(wǎng)格計(jì)算中，向用戶提供有質(zhì)量保障的服務(wù)是很重要的。不同的網(wǎng)格用戶會(huì)要求不同的QoS，QoS一般是指網(wǎng)格任務(wù)的價(jià)格、安全性、穩(wěn)定性、成功率、優(yōu)先級(jí)等[8]。沒(méi)有QoS的任務(wù)調(diào)度的效率是很低的。

3）負(fù)載均衡 在網(wǎng)格任務(wù)調(diào)度中，要盡可能的使得每個(gè)網(wǎng)格資源上都有任務(wù)在運(yùn)行，也就是充分利用網(wǎng)格資源。對(duì)網(wǎng)格資源的主機(jī)負(fù)載進(jìn)行預(yù)測(cè)，然后根據(jù)預(yù)測(cè)的結(jié)果對(duì)網(wǎng)格任務(wù)進(jìn)行調(diào)度并執(zhí)行[9]，在實(shí)現(xiàn)負(fù)載均衡的同時(shí)也會(huì)縮短總?cè)蝿?wù)的完成時(shí)間，效率也會(huì)得到提高。

2 Min-Min調(diào)度算法

當(dāng)前大部分調(diào)度算法研究都集中于獨(dú)立型任務(wù)調(diào)度，這類(lèi)調(diào)度算法假設(shè)任務(wù)之間不存在依賴關(guān)系，任務(wù)的預(yù)期執(zhí)行時(shí)間可知。在眾多靜態(tài)獨(dú)立啟發(fā)式算法中，Min-Min算法是一個(gè)相對(duì)簡(jiǎn)單、快速、有效的算法，該算法的主要思想如下：

假設(shè)網(wǎng)格環(huán)境是由n個(gè)需要調(diào)度的任務(wù)T={T1，T2，…，Tn}和m個(gè)資源R={R1，R2，…Rm}組成。當(dāng)集合T不為空時(shí)，循環(huán)執(zhí)行如下操作直到集合T為空：1）對(duì)集合T中的每一個(gè)任務(wù)分別計(jì)算出它在所有網(wǎng)格資源上的最小完成時(shí)間，可以得到最小完成時(shí)間數(shù)組M；2）從數(shù)組M中選出完成時(shí)間最小的任務(wù)進(jìn)行調(diào)度；3）從集合T中刪除被調(diào)度的任務(wù)。如果集合T為空，則退出調(diào)度過(guò)程。

表1中列出了5個(gè)任務(wù)，3個(gè)網(wǎng)格資源以及相應(yīng)的ETC（Expected Time to Compute）矩陣的值，其中∞表示該任務(wù)在該資源上無(wú)法運(yùn)行，也就是說(shuō)任務(wù)T5只能在資源R2上執(zhí)行，可以認(rèn)為任務(wù)T5具有很高的服務(wù)質(zhì)量要求。由Min-Min調(diào)度算法可以得出調(diào)度的結(jié)果以及調(diào)度的順序：任務(wù)T3調(diào)度到資源R1上，任務(wù)T2調(diào)度到資源R1上，任務(wù)T4調(diào)度到資源R1上，任務(wù)T5調(diào)度到資源R2上，任務(wù)T1調(diào)度到資源R1上。從調(diào)度的結(jié)果中可以看出大部分的任務(wù)都在資源R1上運(yùn)行，而資源R3一直空閑。從調(diào)度的順序中可以發(fā)現(xiàn)任務(wù)的調(diào)度順序是按任務(wù)預(yù)期執(zhí)行時(shí)間從小到大的順序排列的。

表1 任務(wù)在資源上的預(yù)期執(zhí)行時(shí)間Tab.1 Expected execution time of task

盡管Min-Min算法可以有效地進(jìn)行調(diào)度，但是從調(diào)度的結(jié)果中能看出算法缺點(diǎn)：1）忽略了網(wǎng)格任務(wù)的QoS要求；2）每次調(diào)度總是先調(diào)度預(yù)期執(zhí)行時(shí)間最短的任務(wù)，并且總是將任務(wù)調(diào)度到完成本任務(wù)最快的資源上，執(zhí)行時(shí)間相對(duì)較長(zhǎng)的任務(wù)得不到立即執(zhí)行，這樣很容易導(dǎo)致系統(tǒng)的負(fù)載不均衡。

3 基于權(quán)值改進(jìn)的調(diào)度算法

針對(duì)Min-Min算法在調(diào)度網(wǎng)格任務(wù)時(shí)的缺點(diǎn)，文中提出了一種帶權(quán)值的Min-Min改進(jìn)算法。該算法中的權(quán)值由優(yōu)先級(jí)和等待時(shí)間兩部分組成。系統(tǒng)采用權(quán)值的高低來(lái)進(jìn)行任務(wù)的調(diào)度。

3.1 權(quán)值計(jì)算

設(shè)有n個(gè)任務(wù)，m個(gè)網(wǎng)格資源，第i個(gè)任務(wù)的優(yōu)先級(jí)為p（i），等待時(shí)間為 t（i），權(quán)值為 w（i）。根據(jù) ETC 矩陣（ETC[i，j]表示第i個(gè)任務(wù)在第j個(gè)資源上執(zhí)行完成所需要的時(shí)間）可以得出第i個(gè)任務(wù)的權(quán)值為：

其中：α是一個(gè)平衡系數(shù)（0<α<1）。

3.2 任務(wù)調(diào)度

在每次決定調(diào)度的時(shí)候都需要重新計(jì)算當(dāng)前任務(wù)集合中所有任務(wù)的權(quán)值，選擇權(quán)值最高的任務(wù)調(diào)度到完成該任務(wù)最快的資源上。

假設(shè)在上一個(gè)任務(wù)調(diào)度時(shí)刻，wt（j）為資源j的剩余任務(wù)所需要的時(shí)間。經(jīng)過(guò)Δt的時(shí)間，進(jìn)入下一個(gè)調(diào)度時(shí)刻，wt（j）也需要相應(yīng)的更新：

則任務(wù)i在所有資源上的預(yù)測(cè)完成時(shí)間為：

從f（j）中找出最小值所屬的資源，此時(shí)的資源就是任務(wù)i所要調(diào)度的資源。

4 算法仿真與結(jié)果分析

文中采用GridSim[10]來(lái)模擬一個(gè)網(wǎng)格環(huán)境，在相同的環(huán)境條件下，分別用Min-Min調(diào)度算法與改進(jìn)后的算法進(jìn)行比較。

圖1對(duì)應(yīng)改進(jìn)后的算法的低、中、高3種不同優(yōu)先級(jí)的任務(wù)等待時(shí)間的模擬結(jié)果。從圖中可以看出，低優(yōu)先級(jí)的任務(wù)等待時(shí)間最長(zhǎng)，高優(yōu)先級(jí)的任務(wù)等待時(shí)間最短，這說(shuō)明改進(jìn)后的算法滿足了任務(wù)的優(yōu)先級(jí)要求。

圖1 不同優(yōu)先級(jí)的等待時(shí)間Fig.1 Waiting time of different priorities

圖2對(duì)應(yīng)在同優(yōu)先級(jí)情況下的短任務(wù)等待時(shí)間的模擬結(jié)果。圖3對(duì)應(yīng)在同優(yōu)先級(jí)情況下的中任務(wù)等待時(shí)間的模擬結(jié)果。圖4對(duì)應(yīng)在同優(yōu)先級(jí)情況下的長(zhǎng)任務(wù)等待時(shí)間的模擬結(jié)果。由圖可知，改進(jìn)后的算法與Min-Min算法相比，短任務(wù)的等待時(shí)間變長(zhǎng)，而中任務(wù)和長(zhǎng)任務(wù)的等待時(shí)間變短。

圖2 短任務(wù)等待時(shí)間Fig.2 Waiting time of short task

圖3 中任務(wù)等待時(shí)間Fig.3 Waiting time of middle task

圖4 長(zhǎng)任務(wù)等待時(shí)間Fig.4 Waiting time of long task

綜合分析以上3個(gè)圖，改進(jìn)后的算法隨著等待時(shí)間的增加，中任務(wù)和長(zhǎng)任務(wù)的權(quán)值提高較快，從而占用了短任務(wù)的服務(wù)時(shí)間，增加了短任務(wù)的等待時(shí)間。不過(guò)，從圖中可以看出，雖然短任務(wù)的等待時(shí)間有一定的增加，但是中任務(wù)和長(zhǎng)任務(wù)的等待時(shí)間的減少程度就比較明顯。

5 結(jié) 論

文中在對(duì)Min-Min算法進(jìn)行研究之后，發(fā)現(xiàn)Min-Min算法在調(diào)度網(wǎng)格任務(wù)時(shí)沒(méi)有QoS要求，并且大任務(wù)等待時(shí)間過(guò)長(zhǎng)。為了解決這兩個(gè)問(wèn)題，提出了一種基于權(quán)值改進(jìn)的Min-Min調(diào)度算法，該算法把任務(wù)的優(yōu)先級(jí)和等待時(shí)間作為一個(gè)重要的因素。仿真實(shí)驗(yàn)證明，改進(jìn)后的算法可以在網(wǎng)格環(huán)境下實(shí)現(xiàn)較為理想的任務(wù)調(diào)度，是一種有效的任務(wù)調(diào)度算法。

[1]史文翀，曾文華.網(wǎng)格技術(shù)的發(fā)展與其應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2006（7）:59-62.SHI Wen-chong，ZENG Wen-hua.Reserch of the development of grid technology and its application[J].Comuputer&Digital Engineering，2006（7）:59-62.

[2]李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）:184-186.LI Jian-feng，PENG Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing enivironment[J].Journal of Computer Applications，2011，31（1）:184-186.

[3]Casanova H，Legrand A，Zagorodnov D，et al.Heuristics for scheduling parameter sweep applications in grid environments[C]//Cancun，Mexico:Proceeding of the 9th Heterogeneous Computing Workshop，2000:349-363.

[4]Etminani K，Naghibzadeh M.A min-min max-min selective algorithm for grid task scheduling [C]//3rd IEEE/IFIP International Conference in Central Asia，2007:1-7.

[5]吳高峰，蔣玉明，楊林.基于QoS改進(jìn)的Min-Min網(wǎng)格調(diào)度算法[J].微計(jì)算機(jī)信息，2009（27）:8-11.WU Gao-feng，JIANG Yu-ming，YANG Lin.Scheduling algorithm of modified Min-Min based on QoS in grid[J].Microcomputer Information，2009（27）:8-11.

[6]張海賓，唐琳莎，劉立祥.網(wǎng)格調(diào)度綜述[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（9）:2151-2153.ZHANG Hai-bin，TANG Lin-sha，LIU Li-xiang.Survey of grid scheduling [J].Computer Engineering and Design，2009，30（9）:2151-2153.

[7]林曉鵬，郭東輝.基于經(jīng)濟(jì)機(jī)制的網(wǎng)格資源調(diào)度分析[J].信息與電子工程，2010，8（4）:495-499.LIN Xiao-peng，GUO Dong-hui.Analysis of grid resource scheduling based on economy[J].Information and Electronic Engineering，2010，8（4）:495-499.

[8]劉宴兵，陳杰，熊仕勇.基于QoS相似度的網(wǎng)格任務(wù)調(diào)度算法[J].重慶郵電大學(xué)學(xué)報(bào)，2009，21（3）:416-420.LIU Yan-bing，CHEN Jie，XIONG Shi-yong.Grid task scheduling algorithm based on QoS similarity[J].Joural of Chongqing University of Posts and Telecommunications（Natural Science Editon），2009，21（3）:416-420.

[9]程宏兵.基于資源預(yù)測(cè)的網(wǎng)格任務(wù)調(diào)度模型[J].計(jì)算機(jī)應(yīng)用，2010，30（9）:2530-2534.CHENG Hong-bing.Task scheduling model based on resource prediction for grid computing[J].Joural of Computer Applications，2010，30（9）:2530-2534.