網(wǎng)格計算中Min-Min算法及改進(jìn)算法的研究

摘要：討論了Min-Min算法、QoS guided Min-Min算法以及基于任務(wù)優(yōu)先級的QoS guided Min-Min算法，并分析了實驗仿真結(jié)果。

關(guān)鍵詞：網(wǎng)格計算；任務(wù)調(diào)度；Min-Min算法；實驗仿真

0 引言

網(wǎng)格計算任務(wù)調(diào)度就是根據(jù)一定的調(diào)度規(guī)則和調(diào)度策略，把用戶提交的一組任務(wù)，按照一定執(zhí)行時序分配到網(wǎng)絡(luò)上并行分布系統(tǒng)的多個計算節(jié)點上，以最小化并行應(yīng)用程序的執(zhí)行時間，使整個網(wǎng)格系統(tǒng)的資源利用率達(dá)到最高。網(wǎng)格計算任務(wù)調(diào)度的好壞在很大程度上取決于它的調(diào)度算法的有效性和效率。良好的任務(wù)調(diào)度算法是實現(xiàn)高效使用共享資源的重要保障之一。

在網(wǎng)格計算環(huán)境下的任務(wù)調(diào)度算法中，Min-Min算法是一個重要的網(wǎng)格調(diào)度算法，許多算法都以Min-Min算法為基礎(chǔ)，并且都以Min-Min算法作為其比較優(yōu)劣的對象。

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

1.1 Min-Min算法思想

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

1.2 Min-Min算法的不足之處

Min-Min算法總是優(yōu)先調(diào)度短任務(wù)，以最快的速度減少調(diào)度隊列中的任務(wù)，盡量縮短所有任務(wù)的完成時間，當(dāng)機(jī)器空閑時一些執(zhí)行時間較長的任務(wù)才能得以執(zhí)行，這樣便導(dǎo)致了主機(jī)負(fù)載不均衡，利用率降低。因為當(dāng)網(wǎng)絡(luò)傳輸?shù)葪l件對局部任務(wù)調(diào)度影響很小的時候，整個網(wǎng)格處在一個異構(gòu)的環(huán)境中，這時候機(jī)器的處理能力將完全決定了任務(wù)的調(diào)度策略。換句話說，如果某個節(jié)點的計算能力大于同一個局域網(wǎng)內(nèi)其它節(jié)點的時候，所有調(diào)度到這個局部的任務(wù)都會調(diào)度到這臺機(jī)器上去，其它機(jī)器則長期處于空閑狀態(tài)，大量的任務(wù)處在等待調(diào)度的狀態(tài)，造成局部的負(fù)載嚴(yán)重不平衡。

2 基于服務(wù)質(zhì)量的QoS guided Min-Min算法

2.1 QoS guided Min-Min算法思想

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

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

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

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

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

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

(1)QoS Guided Min-Min算法仍然屬于靜態(tài)調(diào)度算法，只能對現(xiàn)存任務(wù)集合進(jìn)行調(diào)度，而不能對動態(tài)變化的任務(wù)集合進(jìn)行調(diào)度，算法適用的范圍不大。

(2)在QoS guided Min-Min算法中，僅以帶寬作為QoS評判標(biāo)準(zhǔn)進(jìn)行調(diào)度，忽視了QoS的其它方面，可能造成高性能計算機(jī)(屬于高QoS資源)被低QoS任務(wù)占據(jù)，網(wǎng)格中其它的一些低QoS資源空閑，而那個需要進(jìn)行高性能計算的高Qos任務(wù)需要等待低QoS任務(wù)執(zhí)行完畢才能執(zhí)行的結(jié)果。這種現(xiàn)象嚴(yán)重浪費了網(wǎng)格資源。

3 基于任務(wù)優(yōu)先級的QoS guided Min-Min算法

3.1 算法思想

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

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

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

(3)運用Min-Min算法調(diào)度各任務(wù)段中的任務(wù)。其中長任務(wù)段具有較高的優(yōu)先級，首先被調(diào)度到處理能力強(qiáng)的資源上。

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

3.2 算法的不足之處與優(yōu)點

該算法的不足之處在于，N的不同取值會導(dǎo)致任務(wù)分配的均衡度與算法的執(zhí)行效率之間的矛盾出現(xiàn)。

算法的優(yōu)點在于調(diào)度時將特殊任務(wù)先進(jìn)行處理，將它們分配到所需的特殊資源上執(zhí)行，避免了這些特殊資源被普通任務(wù)占用而特殊任務(wù)需要等待的現(xiàn)象。同時在Min-Min算法中，考慮了任務(wù)數(shù)據(jù)的傳輸時間。對任務(wù)進(jìn)行了排序，同時又考慮了QoS因素，從很大程度上節(jié)省了調(diào)度時間。

4 仿真實驗和結(jié)果分析

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

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

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

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

從上面三個表可以看出：

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

②隨著資源數(shù)量的增加，三種算法的執(zhí)行時間都在增加。因為隨著資源數(shù)量的增加，網(wǎng)格環(huán)境中可供使用的資源增加。計算能力提高，可供選擇的資源也隨著增加。

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

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

5 結(jié)束語

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