改進的Min-Min網格任務調度算法

趙英，李棟

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

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

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

1 網格任務調度

與傳統的任務調度相比，網格任務調度必須針對網格資源的特點進行[6]。網格資源具有以下3個特點：

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

2）動態性 網格資源工作時性能會不斷變化，有些時候還會出現故障，比如斷電等，調度必須考慮這些突發因素來適應網格資源的動態性。

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

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

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

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

3）負載均衡 在網格任務調度中，要盡可能的使得每個網格資源上都有任務在運行，也就是充分利用網格資源。對網格資源的主機負載進行預測，然后根據預測的結果對網格任務進行調度并執行[9]，在實現負載均衡的同時也會縮短總任務的完成時間，效率也會得到提高。

2 Min-Min調度算法

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

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

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

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

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

3 基于權值改進的調度算法

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

3.1 權值計算

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

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

3.2 任務調度

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

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

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

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

4 算法仿真與結果分析

文中采用GridSim[10]來模擬一個網格環境，在相同的環境條件下，分別用Min-Min調度算法與改進后的算法進行比較。

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

圖1 不同優先級的等待時間Fig.1 Waiting time of different priorities

圖2對應在同優先級情況下的短任務等待時間的模擬結果。圖3對應在同優先級情況下的中任務等待時間的模擬結果。圖4對應在同優先級情況下的長任務等待時間的模擬結果。由圖可知，改進后的算法與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 結 論

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

[1]史文翀，曾文華.網格技術的發展與其應用研究[J].計算機與數字工程，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].計算機應用，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網格調度算法[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]張海賓，唐琳莎，劉立祥.網格調度綜述[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].信息與電子工程，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相似度的網格任務調度算法[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]程宏兵.基于資源預測的網格任務調度模型[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.