改進的Min-Min網(wǎng)格任務調(diào)度算法

趙英，李棟

（北京化工大學 信息科學與技術學院，北京 100029）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 基于權值改進的調(diào)度算法

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

3.1 權值計算

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

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

3.2 任務調(diào)度

在每次決定調(diào)度的時候都需要重新計算當前任務集合中所有任務的權值，選擇權值最高的任務調(diào)度到完成該任務最快的資源上。

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

則任務i在所有資源上的預測完成時間為：

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

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

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

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

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

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

圖2 短任務等待時間Fig.2 Waiting time of short task

圖3 中任務等待時間Fig.3 Waiting time of middle task

圖4 長任務等待時間Fig.4 Waiting time of long task

綜合分析以上3個圖，改進后的算法隨著等待時間的增加，中任務和長任務的權值提高較快，從而占用了短任務的服務時間，增加了短任務的等待時間。不過，從圖中可以看出，雖然短任務的等待時間有一定的增加，但是中任務和長任務的等待時間的減少程度就比較明顯。

5 結(jié) 論

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

[1]史文翀，曾文華.網(wǎng)格技術的發(fā)展與其應用研究[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]李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法[J].計算機應用，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改進的Min-Min網(wǎng)格調(diào)度算法[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].計算機工程與設計，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)濟機制的網(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)格任務調(diào)度算法[J].重慶郵電大學學報，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]程宏兵.基于資源預測的網(wǎng)格任務調(diào)度模型[J].計算機應用，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.