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

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

0 引言

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

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

1 基于最短完成時(shí)間的Min-Min算法

1.1 Min-Min算法思想

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

1.2 Min-Min算法的不足之處

Min-Min算法總是優(yōu)先調(diào)度短任務(wù)，以最快的速度減少調(diào)度隊(duì)列中的任務(wù)，盡量縮短所有任務(wù)的完成時(shí)間，當(dāng)機(jī)器空閑時(shí)一些執(zhí)行時(shí)間較長的任務(wù)才能得以執(zhí)行，這樣便導(dǎo)致了主機(jī)負(fù)載不均衡，利用率降低。因?yàn)楫?dāng)網(wǎng)絡(luò)傳輸?shù)葪l件對(duì)局部任務(wù)調(diào)度影響很小的時(shí)候，整個(gè)網(wǎng)格處在一個(gè)異構(gòu)的環(huán)境中，這時(shí)候機(jī)器的處理能力將完全決定了任務(wù)的調(diào)度策略。換句話說，如果某個(gè)節(jié)點(diǎn)的計(jì)算能力大于同一個(gè)局域網(wǎng)內(nèi)其它節(jié)點(diǎn)的時(shí)候，所有調(diào)度到這個(gè)局部的任務(wù)都會(huì)調(diào)度到這臺(tái)機(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ù)對(duì)帶寬的要求考慮進(jìn)去，將其作為選擇資源的一個(gè)標(biāo)準(zhǔn)。首先在網(wǎng)格資源中，將主機(jī)分為兩類，一類是具有高QoS的主機(jī)群，另一類具備低QoS或者不具備QoS的主機(jī)群；其次，類似地將用戶提交的任務(wù)也分為兩類，具有高Qos要求的任務(wù)和具備低Q05或者不具備QoS要求的任務(wù)。該算法先對(duì)高QoS任務(wù)使用Min-Min算法進(jìn)行調(diào)度，將其分配到高Qos資源上執(zhí)行；然后再對(duì)低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個(gè)需要調(diào)度的任務(wù)、n個(gè)可用的任務(wù)執(zhí)行單元(主機(jī)或集群)和k個(gè)數(shù)據(jù)存儲(chǔ)單元構(gòu)成的網(wǎng)格環(huán)境，構(gòu)造元任務(wù)集合為M；CTij為任務(wù)Ti在主機(jī)Mj上的完成時(shí)刻；ETij為任務(wù)Ti在主機(jī)Mj上的執(zhí)行時(shí)間；Dj為主機(jī)Mi的下一個(gè)可用時(shí)刻，也就是下一個(gè)任務(wù)的開始時(shí)刻；則有CTij=CTij+Dj。該算法的步驟如下：

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

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

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

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

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

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

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

3.1 算法思想

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)和結(jié)果分析

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

從上面三個(gè)表可以看出：

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

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

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

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

5 結(jié)束語

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