網格計算中Min-Min算法及改進算法的研究

摘要：討論了Min-Min算法、QoS guided Min-Min算法以及基于任務優先級的QoS guided Min-Min算法，并分析了實驗仿真結果。

關鍵詞：網格計算；任務調度；Min-Min算法；實驗仿真

0 引言

網格計算任務調度就是根據一定的調度規則和調度策略，把用戶提交的一組任務，按照一定執行時序分配到網絡上并行分布系統的多個計算節點上，以最小化并行應用程序的執行時間，使整個網格系統的資源利用率達到最高。網格計算任務調度的好壞在很大程度上取決于它的調度算法的有效性和效率。良好的任務調度算法是實現高效使用共享資源的重要保障之一。

在網格計算環境下的任務調度算法中，Min-Min算法是一個重要的網格調度算法，許多算法都以Min-Min算法為基礎，并且都以Min-Min算法作為其比較優劣的對象。

1 基于最短完成時間的Min-Min算法

1.1 Min-Min算法思想

該算法是一個比較傳統、經典的任務調度算法，它的主要調度原則就是將具有最短完成時間的任務分配到對應的資源上，保證以最短的時間執行完所有的任務。任務調度問題的本質是在一個由m個需要調度的任務、n個可用的任務執行單元(主機或集群)以及由k個數據存儲單元構成的網格環境下，把m個任務T-{T1，T2，…Tm}以合理的方式調度到n個主機H={H1，H2，…，Hn)上去，使得總執行時間盡可能小。m個任務在n個不同機器上的預測執行時間ETC(Expected Time to Compute)是一個m×n的矩陣，矩陣元素ETC(i，j)表示第i個任務在第j臺機器上的預測執行時間，矩陣中的每一行代表某一任務在n臺機器上的不同執行時間，每一列代表在同一臺機器上m個任務的不同執行時間。

1.2 Min-Min算法的不足之處

Min-Min算法總是優先調度短任務，以最快的速度減少調度隊列中的任務，盡量縮短所有任務的完成時間，當機器空閑時一些執行時間較長的任務才能得以執行，這樣便導致了主機負載不均衡，利用率降低。因為當網絡傳輸等條件對局部任務調度影響很小的時候，整個網格處在一個異構的環境中，這時候機器的處理能力將完全決定了任務的調度策略。換句話說，如果某個節點的計算能力大于同一個局域網內其它節點的時候，所有調度到這個局部的任務都會調度到這臺機器上去，其它機器則長期處于空閑狀態，大量的任務處在等待調度的狀態，造成局部的負載嚴重不平衡。

2 基于服務質量的QoS guided Min-Min算法

2.1 QoS guided Min-Min算法思想

該算法把任務對帶寬的要求考慮進去，將其作為選擇資源的一個標準。首先在網格資源中，將主機分為兩類，一類是具有高QoS的主機群，另一類具備低QoS或者不具備QoS的主機群；其次，類似地將用戶提交的任務也分為兩類，具有高Qos要求的任務和具備低Q05或者不具備QoS要求的任務。該算法先對高QoS任務使用Min-Min算法進行調度，將其分配到高Qos資源上執行；然后再對低Qos任務使用Min-Min算法進行調度，將其分配到所有網格資源上執行。這種算法優先調度高QoS任務，避免了高QoS資源被低Qo$任務占據而得不到調度的問題。

設有m個需要調度的任務、n個可用的任務執行單元(主機或集群)和k個數據存儲單元構成的網格環境，構造元任務集合為M；CTij為任務Ti在主機Mj上的完成時刻；ETij為任務Ti在主機Mj上的執行時間；Dj為主機Mi的下一個可用時刻，也就是下一個任務的開始時刻；則有CTij=CTij+Dj。該算法的步驟如下：

(1)首先根據性能預測模型和需調度的任務的要求。按照一定順序依次計算出每個任務在每個主機E的執行時間鞏。

(2)對元任務集合M中有高Qos要求的任務使用Min-Min算法依次進行匹配，直到這些任務全部映射完，并更新所有的Dj和CTij。

(3)對元任務集合M中剩下的任務使用Min-Min算法進行匹配，直到這些任務全部映射完。

2.2 QoS guided Min-Min算法的不足之處

(1)QoS Guided Min-Min算法仍然屬于靜態調度算法，只能對現存任務集合進行調度，而不能對動態變化的任務集合進行調度，算法適用的范圍不大。

(2)在QoS guided Min-Min算法中，僅以帶寬作為QoS評判標準進行調度，忽視了QoS的其它方面，可能造成高性能計算機(屬于高QoS資源)被低QoS任務占據，網格中其它的一些低QoS資源空閑，而那個需要進行高性能計算的高Qos任務需要等待低QoS任務執行完畢才能執行的結果。這種現象嚴重浪費了網格資源。

3 基于任務優先級的QoS guided Min-Min算法

3.1 算法思想

在網格計算中對所有任務都賦予相應的優先級，有些任務對執行的時間要求很嚴格，而有些任務只須考慮滿足用戶費用要求，基于任務優先級的QoS guided Min-Miia算法可以使所有的任務獲得最短的任務完成時間，盡管用戶支付的費用并不一定最低，但不會超出用戶容忍期限。算法簡要描述如下：

(1)根據任務長度對任務進行降序排序，形成一個有序序列。

(2)根據序列的情況，將任務序列分為n段。

(3)運用Min-Min算法調度各任務段中的任務。其中長任務段具有較高的優先級，首先被調度到處理能力強的資源上。

與基于最短完成時間的Min-Min算法不同的是改進后的算法在調度執行前先根據任務長度進行排序，執行時間長的任務較早被調度，然后在每個任務段內運用基于最短完成時間的Min-Min算法。假設需要被調度的任務包含若干執行時間短的任務和若干執行時間長的任務，那么執行時間長的任務集合將會首先被調度到處理能力強的資源上執行，而后再調度執行時間短的任務。當任務隊列中短任務數多于長任務數時，在執行長任務的同時能執行若干短任務，這樣任務的整體執行時間可能只由長任務來決定，而長任務又被分配到了最佳的資源上，所以會使總的任務執行時間縮短。算法的第二步是將任務序列分為N段，N值的選擇很關鍵。一方面，N值越大負載越趨均衡；另一方面，N值過大會使Min-Min算法降低效率。

3.2 算法的不足之處與優點

該算法的不足之處在于，N的不同取值會導致任務分配的均衡度與算法的執行效率之間的矛盾出現。

算法的優點在于調度時將特殊任務先進行處理，將它們分配到所需的特殊資源上執行，避免了這些特殊資源被普通任務占用而特殊任務需要等待的現象。同時在Min-Min算法中，考慮了任務數據的傳輸時間。對任務進行了排序，同時又考慮了QoS因素，從很大程度上節省了調度時間。

4 仿真實驗和結果分析

為了驗證以上幾種算法的有效性，我們在不同的情況下對它們的性能進行了仿真實驗，采用澳大利亞墨爾本大學開發的網格資源模擬器GridSim對算法進行模擬。仿真實驗的目的是對Min-Min算法、QoS guided Min-Min算法和任務優先級的QoS guided Min-Min算法進行比較。仿真實驗根據任務數、資源數和特殊任務的百分比不同分為三種情況：

(1)任務數20，資源數10，具體仿真數據情況見表l。

(2)任務數40，資源數20，具體仿真數據情況見表2。

(3)任務數60，資源數30，具體仿真數據情況見表3。

從上面三個表可以看出：

①不管任務量的多少，QoS guided Min-Min算法相對于Min-Min算法在執行效率上平均提高10％左右，而基于任務優先級的Qos guided Min-Min算法相對于QoS guidedMin-Min算法在執行效率上平均提高3.5％左右。

②隨著資源數量的增加，三種算法的執行時間都在增加。因為隨著資源數量的增加，網格環境中可供使用的資源增加。計算能力提高，可供選擇的資源也隨著增加。

③不管特殊資源百分比是多少，改進后的算法性能均有提高。當進行任務調度時，如果任務對資源有特殊要求，滿足該要求的資源數量也會隨著特殊資源百分比的增加而增加。因此不管采用何種算法，任務的完成時間都會隨著特殊資源百分比的增加而減小。

④不管分段數N是多少，改進后的算法性能均有提高。無論任務數和資源數為多少，總是在N值為4時算法性能最好。因此，任務序列通常都分為4段。

5 結束語

網格任務的調度是一個非常復雜、重要且具有挑戰性的問題。筆者分析研究了網格計算中常用的任務調度算法，并采用網格模擬器Gridsim針對這些算法進行了仿真實驗。仿真結果表明，改進后的調度算法具有較高的性能，能夠更加真實地體現并滿足用戶的需要。