廖大強(qiáng),鄒 杜,印 鑒

(1.南華工商學(xué)院信息中心,廣州510507;2.華南理工大學(xué)廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室,廣州510640;

3.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院,廣州510275)

一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法

廖大強(qiáng)1,鄒 杜2,印 鑒3

(1.南華工商學(xué)院信息中心,廣州510507;2.華南理工大學(xué)廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室,廣州510640;

3.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院,廣州510275)

容錯(cuò)機(jī)制中基于任務(wù)數(shù)量的平均調(diào)度策略在處理跨度和服務(wù)質(zhì)量方面存在不足,為此,提出一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法,進(jìn)而給出層次式集群系統(tǒng)的設(shè)計(jì)方案。在任務(wù)調(diào)度過程中引入任務(wù)剩余執(zhí)行時(shí)間、任務(wù)價(jià)值密度、費(fèi)用預(yù)算以及處理跨度的概念,以縮短任務(wù)處理跨度,提高服務(wù)質(zhì)量。實(shí)驗(yàn)結(jié)果表明,與原機(jī)制調(diào)度策略和Max-Min算法相比,該算法在任務(wù)完成率、價(jià)值實(shí)現(xiàn)率和處理速率方面具有優(yōu)勢。利用該算法對(duì)原機(jī)制進(jìn)行改進(jìn),能夠有效提高系統(tǒng)的任務(wù)執(zhí)行效率。

任務(wù)調(diào)度;價(jià)值密度;費(fèi)用預(yù)算;處理跨度;高可用性;網(wǎng)格計(jì)算

1 概述

任務(wù)調(diào)度是集群系統(tǒng)的核心技術(shù),其實(shí)質(zhì)是對(duì)資源進(jìn)行規(guī)則的分配。在分布式系統(tǒng)中,節(jié)點(diǎn)在大部分時(shí)間內(nèi)都處于資源低利用狀態(tài),即使當(dāng)系統(tǒng)負(fù)載較大,也有出現(xiàn)部分資源空閑的狀態(tài),若不對(duì)系統(tǒng)資源進(jìn)行充分利用,勢必沒有充分發(fā)揮處理節(jié)點(diǎn)的運(yùn)算能力。因此,對(duì)任務(wù)進(jìn)行規(guī)則性的分配,提高負(fù)載均衡率是必要的[1]。對(duì)于系統(tǒng)而言,任務(wù)實(shí)時(shí)調(diào)度能夠提高系統(tǒng)的運(yùn)行效率,降低任務(wù)的錯(cuò)失率,從而一定程度地提高系統(tǒng)的可靠性與可用性[2]。在目前的實(shí)時(shí)調(diào)度算法中,根據(jù)系統(tǒng)分類,可分為單處理機(jī)調(diào)度、集中式多處理機(jī)調(diào)度和分布式調(diào)度;根據(jù)任務(wù)集種類分類,可以分為周期性任務(wù)調(diào)度算法、非周期任務(wù)調(diào)度算法與混合性任務(wù)調(diào)度算法。高可用集群系統(tǒng)的任務(wù)集屬于偶發(fā)性的任務(wù)集,其特點(diǎn)在于任務(wù)的到達(dá)時(shí)間、到達(dá)數(shù)量都是突發(fā)性且無法預(yù)知的。在分布式調(diào)度算法中,網(wǎng)格調(diào)度算法是一種將資源通過互聯(lián)網(wǎng)聯(lián)合起來組成一臺(tái)“超級(jí)計(jì)算機(jī)”進(jìn)行任務(wù)處理的任務(wù)調(diào)度策略,其特點(diǎn)主要有面向異構(gòu)資源、分布式的、不干預(yù)本地調(diào)度策略等。該算法的目標(biāo)包括最優(yōu)跨度、負(fù)載均衡、服務(wù)質(zhì)量、經(jīng)濟(jì)原則等,其主要思想在于使任務(wù)集能夠在最短時(shí)間內(nèi)以最優(yōu)的服務(wù)質(zhì)量得到完成[3]。

通過網(wǎng)格調(diào)度算法的調(diào)度,能夠保證系統(tǒng)處理節(jié)點(diǎn)隨時(shí)處于最優(yōu)的運(yùn)算效率狀態(tài),使隨時(shí)到達(dá)的任務(wù)集都可以在最短時(shí)間內(nèi)以最優(yōu)的質(zhì)量得到完成,從而解決偶發(fā)性任務(wù)到達(dá)時(shí)間和數(shù)量無法預(yù)測的問題。因此,網(wǎng)格調(diào)度算法可以很好地應(yīng)用于層次式集群系統(tǒng),使系統(tǒng)實(shí)時(shí)性和可靠性得到進(jìn)一步的提高。本文提出一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法,該算法以網(wǎng)格調(diào)度原理為基礎(chǔ),在任務(wù)分配過程中,結(jié)合任務(wù)的剩余執(zhí)行時(shí)間及價(jià)值密度對(duì)任務(wù)集進(jìn)行排序,優(yōu)先對(duì)剩余執(zhí)行時(shí)間小且價(jià)值密度高的任務(wù)進(jìn)行調(diào)度,并綜合考慮資源處理速率和費(fèi)用因素,通過加權(quán)運(yùn)算對(duì)兩者進(jìn)行優(yōu)先級(jí)計(jì)算,將任務(wù)分配至優(yōu)先級(jí)較高的資源上。

2 網(wǎng)格調(diào)度

2.1 網(wǎng)格調(diào)度特點(diǎn)

網(wǎng)格計(jì)算是當(dāng)今計(jì)算機(jī)科學(xué)領(lǐng)域最新興起的一項(xiàng)有很高學(xué)術(shù)價(jià)值和應(yīng)用價(jià)值的研究課題之一,它通過Internet將分散在各地的各種資源通過Internet連接起來,構(gòu)成一個(gè)巨型計(jì)算機(jī),并為使用者提供存儲(chǔ)、數(shù)據(jù)計(jì)算和資源訪問等各種服務(wù),這樣將各地閑置的資源通過網(wǎng)絡(luò)整合起來,減小了資源的孤獨(dú)性,為使用者提供了方便的服務(wù),也減小了計(jì)算的耗費(fèi)[4]。目前許多科研機(jī)構(gòu)都在對(duì)網(wǎng)格的各個(gè)方面進(jìn)行研究,根據(jù)不同的項(xiàng)目,對(duì)網(wǎng)格的定義也不同,比如有些國外的學(xué)術(shù)雜志中成為“Internet2”或“第二代互聯(lián)網(wǎng)”。同時(shí)這2個(gè)名詞也是2個(gè)研究項(xiàng)目的名稱,其所研究的內(nèi)容與網(wǎng)格一致,只不過所研究的重點(diǎn)有所區(qū)別[5]。

2.2 網(wǎng)格調(diào)度目標(biāo)

作為分布式系統(tǒng)的一種形式,網(wǎng)格的核心在于任務(wù)的調(diào)度,它可以描述為合理解決計(jì)算任務(wù)在地理分布的各種資源之間的動(dòng)態(tài)調(diào)度,使各資源能夠得到充分利用。由于任務(wù)調(diào)度為NP完全問題,因此現(xiàn)今對(duì)其的研究一般為尋找近似的最優(yōu)解[6],其具體目標(biāo)包括以下4個(gè)方面:

(1)最優(yōu)跨度。跨度指完成一個(gè)任務(wù)集所需要的時(shí)間,也就是從第一個(gè)任務(wù)至最后一個(gè)任務(wù)完成的時(shí)間間隔,它是網(wǎng)格調(diào)度中最重要的目標(biāo)之一?？缍仍蕉叹驼f明任務(wù)處理越快,表明調(diào)度策略效果越好[7]。對(duì)于用戶來講,調(diào)度的跨度必定是越短越好?？梢?實(shí)現(xiàn)最優(yōu)跨度是用戶和網(wǎng)格系統(tǒng)的共同目標(biāo)。

(2)服務(wù)質(zhì)量(Quality of Service,QoS)?？梢哉f,QoS為調(diào)度算法的共同目標(biāo),網(wǎng)格為用戶提供的服務(wù),其優(yōu)劣是通過服務(wù)質(zhì)量來衡量,好的服務(wù)質(zhì)量能夠保證用戶提交的任務(wù)在高效率、低錯(cuò)誤率的狀態(tài)下完成,所以在任務(wù)管理與任務(wù)分配時(shí),服務(wù)質(zhì)量是其考慮的重點(diǎn)之一。

(3)負(fù)載均衡。在分布式系統(tǒng)中,其關(guān)鍵的問題在于各節(jié)點(diǎn)間的負(fù)載均衡率。網(wǎng)格系統(tǒng)在此方面的需求更加擴(kuò)大化,由于網(wǎng)格環(huán)境的龐大與復(fù)雜性,對(duì)于調(diào)度的負(fù)載均衡性是一個(gè)非常重要的問題[7]。

(4)經(jīng)濟(jì)原則。網(wǎng)格的地理分布是廣泛而且復(fù)雜的,并且有異構(gòu)性的特點(diǎn),對(duì)于這樣的環(huán)境,其各節(jié)點(diǎn)所提供的服務(wù)與價(jià)格也存在較大的差異,根據(jù)經(jīng)濟(jì)原則,由于資源的異構(gòu)性必定使各資源的價(jià)格產(chǎn)生差異[8],因此網(wǎng)格任務(wù)調(diào)度滿足交易雙方的利益,使消費(fèi)雙方互惠互利,這樣才能使網(wǎng)格得到持久地發(fā)展。

2.3 經(jīng)典網(wǎng)格調(diào)度算法分析

網(wǎng)格任務(wù)的調(diào)度屬于NP完全問題,最優(yōu)的調(diào)度算法在目前仍難以實(shí)現(xiàn),所以,為取得一個(gè)好的調(diào)度策略,經(jīng)常采用的方法為尋找接近于最優(yōu)解的方式,其中比較經(jīng)典的網(wǎng)格調(diào)度算法有 Min-Min算法、Min-Max算法、遺傳算法等[9]。

(1)Min-Min算法:該算法首先計(jì)算任務(wù)集中所有任務(wù)在現(xiàn)有資源上的預(yù)期執(zhí)行時(shí)間,然后選擇具有最小值的任務(wù)將其分配到能最早完成它的機(jī)器上,分配完成后,將此任務(wù)從任務(wù)集中刪除,并重復(fù)上述過程,直至任務(wù)集為空[10]。

(2)Min-Max算法:該算法類似于Min-Min算法,但由于Min-Min算法總是優(yōu)先調(diào)度執(zhí)行時(shí)間短的任務(wù),因此對(duì)于長度比較長的任務(wù)來說,需要等待的時(shí)間也比較久,而Min-Min算法有個(gè)比較嚴(yán)重的缺點(diǎn),那就是它的負(fù)載平衡性較差[11]。這里用它與Min-Max算法做一個(gè)理想化的比較。假定有如下3個(gè)任務(wù)和3個(gè)資源主機(jī),各任務(wù)在各主機(jī)上期望執(zhí)行時(shí)間如表1所示。

表1 任務(wù)對(duì)應(yīng)資源的預(yù)期執(zhí)行時(shí)間 ms

基于該資源列表,分別使用Min-Min算法和Min-Max算法進(jìn)行調(diào)度,調(diào)度結(jié)果如圖1所示。

圖1 Min-Min算法與Min-Max算法調(diào)度示例

從圖1中可以看出,Min-Max算法較Min-Min有更好的負(fù)載均衡性,其調(diào)度跨度方面的性能更優(yōu)于Min-Min算法。

(3)遺傳算法:該算法是一種生物進(jìn)化論與遺傳變異理論相結(jié)合的模擬生物進(jìn)化的搜索算法。算法流程如圖2所示。

圖2 遺傳算法流程

遺傳算法優(yōu)點(diǎn)在于具有與領(lǐng)域無關(guān)的群體性全局搜索能力,有效避免了算法陷入局部最優(yōu)的情況發(fā)生;利用概率機(jī)制進(jìn)行迭代,具有隨機(jī)性;使用評(píng)價(jià)函數(shù)啟發(fā)搜索,過程簡單;可擴(kuò)展性強(qiáng),與其他的技術(shù)容易結(jié)合形成優(yōu)化算法。而其缺點(diǎn)在于對(duì)系統(tǒng)的反饋信息沒有充分利用,其搜索的隨機(jī)性較高,并且算法的求解會(huì)產(chǎn)生大量的冗余迭代,從而延長了最優(yōu)解收斂時(shí)間,影響到調(diào)度的效率[12]。

3 基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法

針對(duì)系統(tǒng)偶發(fā)式任務(wù)模型,網(wǎng)格調(diào)度算法可以在一定程度上解決任務(wù)到達(dá)時(shí)間無法預(yù)知的問題,且能夠保證任務(wù)完成的質(zhì)量與速率,可以較好地應(yīng)用于高可用集群系統(tǒng)中,因此,本文提出一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法。

3.1 任務(wù)集與資源集描述

設(shè)T={T1,T2,…,Tn}為網(wǎng)格作業(yè)的任務(wù)集,用一個(gè)五元組來表示Tj=＜IDj,aj,Lj,vj,Dj＞。其中,IDj表示任務(wù)Tj的標(biāo)識(shí);aj表示任務(wù)到達(dá)的時(shí)間;Lj表示任務(wù)的長度,其單位為百萬指令(MI);vj表示任務(wù)的價(jià)值;Dj表示任務(wù)的截止期,即任務(wù)的完成時(shí)間期限。

設(shè)R={R1,R2,…,Rm}為網(wǎng)格環(huán)境中的資源集,其單個(gè)資源用一個(gè)3元組來表示:Rj=＜IDj,MIPSj,pricej＞。其中,IDj表示資源的編號(hào);MIPSj表示資源rj的處理速率;pricej表示資源rj單位時(shí)間的價(jià)格。

3.2 優(yōu)先級(jí)運(yùn)算

根據(jù)上述任務(wù)集的描述,任務(wù)tj的價(jià)值密度VDj如式(1)所示。

VDj的大小決定任務(wù)的優(yōu)先級(jí),其值越大,則優(yōu)先級(jí)越高。

設(shè)當(dāng)前時(shí)間為t,由式(1)可得任務(wù)Tj的剩余執(zhí)行時(shí)間Sj,如式(2)所示。

任務(wù)剩余執(zhí)行時(shí)間越小,則表示其該任務(wù)越緊急。

考慮剩余執(zhí)行時(shí)間與任務(wù)價(jià)值2個(gè)因素,根據(jù)式(1)與式(2)來定義本算法任務(wù)調(diào)度順序的優(yōu)先級(jí)Pj,如式(3)所示。

Pj表示任務(wù)Tj在其剩余執(zhí)行時(shí)間內(nèi)單位時(shí)間的價(jià)值密度,單位時(shí)間內(nèi)任務(wù)價(jià)值率越大,則優(yōu)先級(jí)越高,調(diào)度時(shí)對(duì)優(yōu)先級(jí)大的任務(wù)進(jìn)行優(yōu)先調(diào)度,這樣使得價(jià)值大且時(shí)間緊急的任務(wù)優(yōu)先得到處理,從而減小任務(wù)的錯(cuò)失率并提高任務(wù)的價(jià)值實(shí)現(xiàn)率。

3.3 網(wǎng)格調(diào)度預(yù)算費(fèi)用的選擇范圍

對(duì)于用戶來說,任務(wù)調(diào)度的費(fèi)用預(yù)算是其考慮的主要因素之一,這里給出一種費(fèi)用預(yù)算區(qū)間的計(jì)算方法,其思想如下:從理論上講,若任務(wù)集T中的任務(wù)能夠絕對(duì)地負(fù)載均衡到資源集R上,也就是說資源集中所有的資源能同時(shí)并行工作并在同一時(shí)刻將分配到的任務(wù)完成,這樣資源的運(yùn)行效率達(dá)到最高,從而也使任務(wù)集處理時(shí)間跨度取得最優(yōu)。設(shè)這種情況下每個(gè)資源的處理時(shí)間為T,資源集R可得處理整個(gè)任務(wù)集所需的總費(fèi)用Price如式(4)所示。

由于每個(gè)資源的處理時(shí)間為t,而每個(gè)資源的處理速率已知,為MIPSj,則可以得出任務(wù)集T中所有任務(wù)的長度和L如式(5)所示。

由式(4)與式(5)綜合可以得出,在理想狀態(tài)下,任務(wù)集T的單位長度耗費(fèi)如式(6)所示。

由于資源集中單個(gè)資源的價(jià)格與運(yùn)行速率為已知,因此平均長度耗費(fèi)Average為一個(gè)可以計(jì)算出的常數(shù),這個(gè)值代表了理想狀態(tài)也就是任務(wù)執(zhí)行的最快速率下的任務(wù)耗費(fèi),而對(duì)于用戶來說,費(fèi)用預(yù)算越高,其任務(wù)的處理速率應(yīng)該越快,故若用戶的費(fèi)用預(yù)算高出這個(gè)耗費(fèi)是無意義的,所以這個(gè)費(fèi)用的值應(yīng)該為用戶費(fèi)用預(yù)算的最大值,設(shè)為Bmax。

在資源集R中,必定存在一個(gè)單位長度價(jià)格最低的資源,設(shè)為資源Rk,則若將任務(wù)集T中所有的任務(wù)全部都分配到該資源上,最終的調(diào)度結(jié)果則為該任務(wù)集調(diào)度的費(fèi)用最優(yōu)策略。則資源Rk的單位長度價(jià)格為用戶預(yù)算費(fèi)用的最低值,即Bmin如式(7)所示。

由以上定義得出,用戶的預(yù)算費(fèi)用選擇區(qū)間為[Bmin,Bmax]。

3.4 任務(wù)調(diào)度費(fèi)用優(yōu)先級(jí)與速率優(yōu)先級(jí)

假設(shè)任務(wù)Ti為任務(wù)集T中第i個(gè)被調(diào)度的任務(wù),任務(wù)ti對(duì)應(yīng)資源集中資源k的調(diào)度費(fèi)用如式(8)所示。

而在此任務(wù)被調(diào)度之前有i-1個(gè)任務(wù)已經(jīng)被調(diào)度,設(shè)之前被調(diào)度的任務(wù)其總耗費(fèi)為Cbefore、任務(wù)總長度為Lbefore、調(diào)度跨度為Sbefore,則在此任務(wù)被調(diào)度以后,調(diào)度總耗費(fèi)相應(yīng)會(huì)增加,為Cbefore+Ci,k,任務(wù)總長度l增加為Lbefore+li,則此時(shí)的任務(wù)調(diào)度平均長度耗費(fèi)Averagei如式(9)所示。

由于資源集中不同的資源其價(jià)格也不同,因此對(duì)于不同的資源,其對(duì)應(yīng)的耗費(fèi)也不同,也就是說在式(9)中Ci,k的值隨著選擇的資源不同而不同,因此,Averagei的值取決于任務(wù)Ti被分配到的資源價(jià)格,顯然Averagei與用戶預(yù)算費(fèi)用越接近,用戶則越滿意,設(shè)Budget為用戶費(fèi)用預(yù)算,Costsim為任務(wù)Ti分配以后總體調(diào)度平均長度耗費(fèi)與用戶預(yù)算的近似度,設(shè)Costsim={Costsim1,Costsim2,…,Costsimm-1,Costsimm},綜合式(9),可得Costsimk如式(10)所示。

在調(diào)度過程中,優(yōu)先將任務(wù)調(diào)度至此近似度值大的資源上,最終所獲得的任務(wù)調(diào)度平均長度耗費(fèi)將是一個(gè)與用戶費(fèi)用預(yù)算近似的值,從而很好地滿足用戶的需求。對(duì)于優(yōu)先級(jí)的計(jì)算如下:根據(jù)資源集中資源的數(shù)量m,設(shè)置m個(gè)優(yōu)先級(jí),每個(gè)任務(wù)調(diào)前,按照式(10)進(jìn)行計(jì)算,得到m個(gè)近似值,按照近似值的大小排序,近似值最小的賦予最小的優(yōu)先級(jí),然后資源優(yōu)先級(jí)的大小按照順序依次遞增。

若僅考慮用戶預(yù)算方面的因素,以上的優(yōu)先級(jí)調(diào)度可以很好地滿足用戶的需求,但是一般來說,對(duì)于一個(gè)任務(wù)集的調(diào)度,用戶所關(guān)注的并不僅僅是費(fèi)用一個(gè)方面的因素,任務(wù)集處理的時(shí)間跨度也是其考慮的重點(diǎn)因素之一。本文以上述定義為基礎(chǔ),設(shè)資源集中各資源處理所分配到的任務(wù)所需的時(shí)間集為ProcessTime,ProcessTime={Proc1,Proc2,…,Procm},設(shè)在任務(wù)Ti被調(diào)度前,資源處理時(shí)間集為ProcessTimei-1,則此時(shí)的調(diào)度跨度Sbefore應(yīng)該為ProcessTimei-1中的最大值max(ProcessTimei-1),在任務(wù)Ti被調(diào)度后,其對(duì)應(yīng)的調(diào)度主機(jī)上的運(yùn)行時(shí)間會(huì)相應(yīng)增加,從而對(duì)跨度的大小產(chǎn)生影響。設(shè)Ti調(diào)度到資源上后對(duì)應(yīng)的跨度集為Span,Span={Span1,Span2,…,Spanm},對(duì)跨度集合進(jìn)行大小排序,然后根據(jù)其順序來為資源分配跨度優(yōu)先級(jí),設(shè)優(yōu)先級(jí)為Ps,若跨度值大小一樣,則處理時(shí)間較小的資源優(yōu)先調(diào)度。

由上文可知,對(duì)于任務(wù)Ti,其調(diào)度到資源的費(fèi)用優(yōu)先級(jí)為Pc,跨度優(yōu)先級(jí)為Ps,則將2個(gè)優(yōu)先級(jí)進(jìn)行加權(quán)運(yùn)算,得到任務(wù)的實(shí)際調(diào)度優(yōu)先級(jí)p如式(11)所示。

其中,0＜a＜1為加權(quán)系數(shù)。則當(dāng)a=0時(shí),該算法為完全考慮調(diào)度跨度的策略,當(dāng)a=1時(shí),該算法變?yōu)閮H考慮調(diào)度費(fèi)用的調(diào)度策略,當(dāng)a去中間值時(shí),則為綜合考慮2個(gè)因素的調(diào)度策略。本文取a的值為5.2,表示調(diào)度過程中,任務(wù)分配優(yōu)先考慮費(fèi)用預(yù)算,其次考慮跨度。

3.5 算法調(diào)度流程

基于以上定義,算法的具體調(diào)度過程的步驟如下:

Step 1 對(duì)任務(wù)集中的任務(wù)按式(3)進(jìn)行優(yōu)先級(jí)計(jì)算,并對(duì)所有任務(wù)按照優(yōu)先級(jí)值的大小進(jìn)行排序;

Step 2 取出隊(duì)首也就是優(yōu)先級(jí)最高的任務(wù);

Step 3 根據(jù)式(11)計(jì)算資源優(yōu)先級(jí);

Step 4 將任務(wù)分配給優(yōu)先級(jí)最高的資源;

Step 5 從任務(wù)集中刪除該任務(wù);

Step 6 判斷任務(wù)集中是否還有任務(wù),若有則返回Step2,否則,調(diào)度完成。

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

本文對(duì)上述基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法,結(jié)合Min-Min算法以及原機(jī)制所采用的調(diào)度策略進(jìn)行實(shí)驗(yàn),在此節(jié)中對(duì)這3種策略的調(diào)度結(jié)果進(jìn)行展示并作出對(duì)比和分析。

4.1 實(shí)驗(yàn)環(huán)境

操作系統(tǒng):Windows xp 32 bit;

內(nèi)存:4.0 GB;

處理器:Intel(r)Core(tm)2Duo CPU,2.53 EHz;

集成開發(fā)工具:Eelipse6.5;

jdk版本:1.5;

仿真工具:Girdsim4.1;

數(shù)據(jù)庫:Oracle9i。

4.2 GridSim仿真工具簡介

GridSim由澳大利亞墨爾本大學(xué)Rajkumar Buyya領(lǐng)導(dǎo)開發(fā),它用Java語言開發(fā),是一種模擬網(wǎng)絡(luò)資源的仿真工具,其主要用于研究基于計(jì)算經(jīng)濟(jì)模型的有效資源分配方法。是網(wǎng)格計(jì)算研究中使用最為廣泛的工具之一。

4.3 仿真環(huán)境配置

4.3.1 資源的建立

使用GridSim建立5個(gè)價(jià)格和處理速率都不同的資源,對(duì)資源的處理能力、網(wǎng)絡(luò)帶寬,以及資源單位時(shí)間的價(jià)格進(jìn)行初始化。將本地資源調(diào)度策略設(shè)置為SPACE_SHARED,這種策略的思想為先到達(dá)的任務(wù)先處理,后到達(dá)的任務(wù)等待前面的任務(wù)完成以后再開始處理。資源的相關(guān)配置如表2所示。

表2 資源配置

4.3.2 任務(wù)集的建立

生成5個(gè)任務(wù)集進(jìn)行實(shí)驗(yàn),其任務(wù)集中包含的任務(wù)數(shù)量依次為200,500,1 000,1 500,2 000。在GridSim中對(duì)于任務(wù)生成,其最主要的初始化元素為任務(wù)長度,實(shí)驗(yàn)中在區(qū)間[5,20]內(nèi)隨機(jī)取一個(gè)值作為任務(wù)的長度,單位為MIP(兆指令)。仿真基于這5個(gè)任務(wù)集,對(duì)基于優(yōu)先級(jí)的調(diào)度算法、Min-Max算法和原機(jī)制的調(diào)度策略進(jìn)行對(duì)比實(shí)驗(yàn)。

4.4 實(shí)驗(yàn)結(jié)果及分析

根據(jù)表2所示的資源配置,結(jié)合式(6)與式(7)可得出預(yù)算費(fèi)用的區(qū)間應(yīng)為[0.5,0.567]。實(shí)驗(yàn)中以0.002為間隔在費(fèi)用預(yù)算區(qū)間內(nèi)取樣作為預(yù)算費(fèi)用進(jìn)行調(diào)度仿真。

圖3為基于特定預(yù)算費(fèi)用下平均長度耗費(fèi)的均值?？梢钥闯?最終耗費(fèi)與費(fèi)用預(yù)算基本上呈線性關(guān)系,且兩者的值極為接近,其精確度達(dá)到1‰,所以,經(jīng)過算法的調(diào)度,其最終的調(diào)度費(fèi)用將會(huì)得到用戶較好的認(rèn)可。

圖3 費(fèi)用預(yù)算下的最終調(diào)度費(fèi)用平均值

圖3數(shù)據(jù)表明,本文算法在費(fèi)用預(yù)算方面具有不錯(cuò)的性能,能夠很好地滿足用戶的需求,而用戶對(duì)于其費(fèi)用需求得到滿足的情況下,任務(wù)處理的速率也是其關(guān)注的重要因素之一。

在不同費(fèi)用預(yù)算下任務(wù)的調(diào)度跨度結(jié)果如圖4所示?？梢钥闯?隨著費(fèi)用預(yù)算的增大,本文算法對(duì)任務(wù)的調(diào)度跨度隨之減小。當(dāng)接近最小費(fèi)用預(yù)算時(shí),其任務(wù)處理跨度值較大,從而任務(wù)被較快地執(zhí)行。

圖4 不同費(fèi)用預(yù)算下的調(diào)度跨度

而當(dāng)費(fèi)用預(yù)算為0.567時(shí),本文算法得到最優(yōu)速率執(zhí)行跨度,將其與Min-Max算法和原機(jī)制調(diào)度策略進(jìn)行對(duì)比實(shí)驗(yàn),結(jié)果如圖5所示。

從以上結(jié)果可以看出,本文算法在跨度方面具有較好的性能,而且與原機(jī)制的調(diào)度策略相比,它在跨度方面優(yōu)勢較為明顯,將本文算法應(yīng)用與該容錯(cuò)機(jī)制中,能明顯提高系統(tǒng)的運(yùn)行效率,在任務(wù)到達(dá)時(shí),能夠以更快的速率得到處理。

由圖6可以看出,本文算法的錯(cuò)失數(shù)量明顯低于其余兩者,這是由于本算法考慮到任務(wù)剩余執(zhí)行時(shí)間的調(diào)度結(jié)果所致,而Max-Min算法在此之后的任務(wù)錯(cuò)失率在三者中為最高,這種結(jié)果產(chǎn)生的原因在于Max-Min算法優(yōu)先對(duì)任務(wù)長度較大的任務(wù)進(jìn)行調(diào)度,以致占用了大量的任務(wù)處理時(shí)間,使得同一時(shí)間內(nèi)被處理的任務(wù)數(shù)量減少,并且算法完全未考慮服務(wù)質(zhì)量方面的因素,故使得其在任務(wù)完成率方面表現(xiàn)較差。

圖5 3種算法的調(diào)度跨度

圖6 3種算法任務(wù)錯(cuò)失數(shù)量占總價(jià)值比例

從任務(wù)實(shí)現(xiàn)價(jià)值占總?cè)蝿?wù)價(jià)值的比例結(jié)果來看,3種算法對(duì)200個(gè)任務(wù)的任務(wù)集的總價(jià)值實(shí)現(xiàn)率都在100%,本文算法隨著任務(wù)錯(cuò)失率的增加,其價(jià)值的實(shí)現(xiàn)率較其他兩者明顯要高,從而表明優(yōu)先對(duì)價(jià)值密度大的任務(wù)進(jìn)行調(diào)度,進(jìn)一步提高了算法的服務(wù)質(zhì)量,具體如圖7所示。

圖7 3種算法任務(wù)實(shí)現(xiàn)價(jià)值占總價(jià)值比例

從以上的仿真實(shí)驗(yàn)結(jié)果可以看出,較原機(jī)制的調(diào)度策略而言,本文算法在任務(wù)完成率、價(jià)值實(shí)現(xiàn)率、任務(wù)處理速率等多方面均有較大改善,故利用此算法對(duì)原機(jī)制進(jìn)行改進(jìn),系統(tǒng)將具有更好的可用性。

5 結(jié)束語

針對(duì)傳統(tǒng)基于任務(wù)數(shù)量的平均調(diào)度在跨度、服務(wù)質(zhì)量等方面存在的缺陷,提出基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法對(duì)原機(jī)制進(jìn)行改進(jìn)。通過對(duì)本文算法、原機(jī)制調(diào)度策略以及Max-Min算法的三者進(jìn)行對(duì)比實(shí)驗(yàn)及分析,證明算法在服務(wù)質(zhì)量、任務(wù)處理速率方面具有較好的性能,能夠有效提高系統(tǒng)任務(wù)執(zhí)行的效率。下一步可針對(duì)算法在費(fèi)用預(yù)算方面的特性做進(jìn)一步的應(yīng)用,若根據(jù)系統(tǒng)負(fù)載的情況,動(dòng)態(tài)調(diào)整費(fèi)用預(yù)算,在負(fù)載較低時(shí),降低費(fèi)用預(yù)算,將任務(wù)優(yōu)先分配到成本較低的節(jié)點(diǎn)上,使成本高、速率快的節(jié)點(diǎn)能節(jié)省更多的資源來處理其他事務(wù)。反之,增加費(fèi)用預(yù)算,保證任務(wù)的完成率。

[1] Rosenberg A L,Yurkewych M.Guidelines for Scheduling SomeCommon Computation-dagsforInternet-based Computing[J].IEEE Transactions on Computers,2005, 54(4):428-438.

[2] 蒲 英,馬滿福,牛增軒.網(wǎng)格調(diào)度中的QoS參數(shù)容錯(cuò)[J].計(jì)算機(jī)工程,2011,37(7):44-46,49.

[3] 張海賓,唐琳莎,劉立祥.網(wǎng)格調(diào)度綜述[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(9):89-94.

[4] Shu Wanneng,Wang Jianqing.Min-Min Chromosome Genetic Algorithm for Load Balancing in Grid Computing[J].International Journal of Distributed Sensor Networks,2009,5(1):157-163.

[5] van Peteghem V,Vanhoucke M.A Genetic Algorithm for the Preemptive and Non-preemptive Multi-mode Resource-constrained Project Scheduling Problem[J]. European Journalof OperationalResearch,2010, 201(2):409-418.

[6] Sulistio A,Cibej U,Venugopal S,et al.A Toolkit for Modeling and Simulating Data Grids:All Extension to GridSim[J].Concurrency and Computation:Practice and Experience,2008,20(13):1591-1609.

[7] 羅宇平.基于Min-Min改進(jìn)后的網(wǎng)格調(diào)度算法[J].微電子學(xué)與計(jì)算機(jī),2009(3):71-75

[8] 田生偉,吐爾根·依布拉音,禹 龍.基于動(dòng)態(tài)預(yù)測和任務(wù)流整形的網(wǎng)格調(diào)度算法[J].計(jì)算機(jī)工程,2008, 34(8):120-122.

[9] He Xiaoshan,Sun Xianhe,Laszewski G.QoS Guided Min-Min Heuristic for Grid Task Scheduling[J].Journal of Computer Science and Technology,2003,(4):249-253.

[10] 徐奕奕,唐培和,鄭慶華.基于多目標(biāo)權(quán)衡的數(shù)據(jù)網(wǎng)格作業(yè)調(diào)度算法[J].廣西工學(xué)院學(xué)報(bào),2013,(4): 61-63.

[11] 莫 贊,謝 娜,賈功祥,等.基于多QoS需求驅(qū)動(dòng)的網(wǎng)格資源調(diào)度研究[J].計(jì)算機(jī)應(yīng)用研究,2012, 29(10):3904-3925.

[12] 劉剛國,羅省賢.基于指標(biāo)體系的網(wǎng)格調(diào)度算法研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):97-101.

編輯 金胡考

A Grid Scheduling Algorithm Based on Priority

LIAO Da-qiang1,ZOU Du2,YIN Jian3
(1.Information Center,Nanhua College of Industry and Commerce,Guangzhou 510507,China;
2.Guangdong Key Laboratory of Computer Network,South China University of Technology,Guangzhou 510640,China;
3.School of Information Science and Technology,Sun Yat-Sen University,Guangzhou 510275,China)

The average scheduling strategy based on task numbers in fault-tolerant has shortcoming such as processing span and Quality of Service(QoS).Aiming at this problem,this paper proposes a grid scheduling algorithm based on priority,and then puts forward the design scheme of the hierarchical cluster system.The algorithm introduces the task in the process of task scheduling,task execution time remaining concept value density,cost budget and span,to make up for the task scheduling in the treatment of two span and QoS.Experimental results show that the algorithm has better effect in the completion rate,value realization rate,treatment rate compared with the original mechanism of scheduling strategy and Max-Min algorithm.The original mechanism is improved by using this algorithm.It can effectively improve the efficiency of system task execution,and the availability of system.

task scheduling;value density;cost budget;processing span;high availability;grid computing

1000-3428(2014)10-0011-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.003

廣東省教育研究院教育研究課題基金資助項(xiàng)目(GDJY-2014-B-b243)。

廖大強(qiáng)(1984-),男,講師、碩士,主研方向:高性能計(jì)算,并行分布式計(jì)算;鄒 杜,副教授、博士;印 鑒,教授、博士、博士生導(dǎo)師。

2014-01-22

2014-03-17E-mail:liaodaqiang@gmail.com

中文引用格式:廖大強(qiáng),鄒 杜,印 鑒.一種基于優(yōu)先級(jí)的網(wǎng)格調(diào)度算法[J].計(jì)算機(jī)工程,2014,40(10):11-16.

英文引用格式:Liao Daqiang,Zou Du,Yin Jian.A Grid Scheduling Algorithm Based on Priority[J].Computer Engineering,2014,40(10):11-16.