網(wǎng)格計(jì)算技術(shù)及其任務(wù)調(diào)度策略研究

鄧見(jiàn)光 潘曉衡 袁華強(qiáng)

(1．東莞理工學(xué)院 工程技術(shù)研究院，廣東東莞 523808;2．華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510006)

網(wǎng)格計(jì)算技術(shù)及其任務(wù)調(diào)度策略研究

鄧見(jiàn)光1，2潘曉衡1袁華強(qiáng)1

(1．東莞理工學(xué)院 工程技術(shù)研究院，廣東東莞 523808;2．華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510006)

對(duì)網(wǎng)格計(jì)算技術(shù)及其任務(wù)調(diào)度策略進(jìn)行了論述與總結(jié)。首先介紹了網(wǎng)格計(jì)算技術(shù)的起源和網(wǎng)格系統(tǒng)應(yīng)具備的基本條件，然后論述了網(wǎng)格計(jì)算不同于傳統(tǒng)分布式計(jì)算的獨(dú)特特征，接下來(lái)對(duì)網(wǎng)格計(jì)算的應(yīng)用領(lǐng)域進(jìn)行了簡(jiǎn)單探討。最后從網(wǎng)格任務(wù)調(diào)度的特點(diǎn)、評(píng)價(jià)指標(biāo)以及現(xiàn)有的調(diào)度算法等方面對(duì)網(wǎng)格計(jì)算的任務(wù)調(diào)度策略進(jìn)行了詳細(xì)討論。全文工作將指導(dǎo)我們未來(lái)進(jìn)一步深入研究網(wǎng)格計(jì)算。

網(wǎng)格計(jì)算;分布式計(jì)算;任務(wù)調(diào)度;負(fù)載均衡

目前關(guān)于網(wǎng)格計(jì)算的研究已經(jīng)取得了很大的進(jìn)步，然而其還沒(méi)有一個(gè)能夠被普遍認(rèn)可的定義。Foster等人指出，網(wǎng)格是一種由軟、硬件構(gòu)成的基礎(chǔ)設(shè)施，它支持一種一致、可靠、普遍和廉價(jià)接入的計(jì)算能力［1］，旨在于動(dòng)態(tài)異構(gòu)的虛擬組織之間實(shí)現(xiàn)資源共享和協(xié)同解決問(wèn)題。具體來(lái)說(shuō)，網(wǎng)格系統(tǒng)應(yīng)同時(shí)滿足三個(gè)條件，首先，其應(yīng)在非集中控制的環(huán)境中協(xié)同使用資源;其次，網(wǎng)格系統(tǒng)必須使用開(kāi)放、標(biāo)準(zhǔn)、通用的協(xié)議以及接口;最后網(wǎng)格系統(tǒng)應(yīng)提供非平凡的計(jì)算能力和服務(wù)質(zhì)量。

網(wǎng)格系統(tǒng)是一個(gè)分布式的計(jì)算環(huán)境，它集成了世界上眾多的閑置資源，實(shí)現(xiàn)了網(wǎng)絡(luò)上所有計(jì)算的連通和資源的共享，有效地突破了過(guò)去強(qiáng)加在單個(gè)計(jì)算資源之上的計(jì)算能力以及地域的限制;其通過(guò)充分協(xié)同利用世界范圍內(nèi)閑置的計(jì)算資源，實(shí)現(xiàn)真正意義的資源共享與協(xié)作，從而為人們提供一種全新的方式來(lái)使用計(jì)算資源和解決復(fù)雜問(wèn)題。

1 網(wǎng)格的特點(diǎn)

網(wǎng)格計(jì)算系統(tǒng)具有許多獨(dú)特的特點(diǎn)［2］，這些特點(diǎn)主要表現(xiàn)在以下方面。

1.1 網(wǎng)格資源的分布和共享

網(wǎng)格計(jì)算資源跨越的地域較廣，涉及的規(guī)模巨大，因此其是一種分布式計(jì)算。網(wǎng)格資源的分布性使得其必須解決好資源分配、任務(wù)調(diào)度、安全通信、實(shí)時(shí)性保障等問(wèn)題。另外，網(wǎng)格資源雖是分布式的，但它們卻可以充分共享，網(wǎng)格系統(tǒng)的資源可以提供給任一個(gè)網(wǎng)格用戶。資源共享是網(wǎng)格計(jì)算的目的，也是網(wǎng)格計(jì)算的核心內(nèi)容。這里的共享包括計(jì)算資源、數(shù)據(jù)庫(kù)、儀器設(shè)備以及人力資源等各類資源的共享。

1.2 網(wǎng)格資源的自治與統(tǒng)一管理

網(wǎng)格資源由分布在互聯(lián)網(wǎng)中分屬于不同組織或個(gè)人的資源構(gòu)成。網(wǎng)格資源首先屬于資源的所有者，資源所有者對(duì)其資源具有自主管理權(quán)，這即是網(wǎng)格資源的自治性。此外，網(wǎng)格資源也必須接受網(wǎng)格系統(tǒng)的統(tǒng)一管理，否則不同的分布式資源就無(wú)法建立聯(lián)系，更無(wú)法實(shí)現(xiàn)資源的共享協(xié)同。因此，網(wǎng)格一方面允許網(wǎng)格資源的所有者對(duì)其資源進(jìn)行自主管理，另一方面又要求網(wǎng)格資源必須接受網(wǎng)格系統(tǒng)的統(tǒng)一管理。

1.3 自相似性與資源異構(gòu)

網(wǎng)格的自相似性表現(xiàn)在網(wǎng)格的局部與整體相似，網(wǎng)格的自相似性在構(gòu)建和研究網(wǎng)格時(shí)具有重要意義。與自相似性相對(duì)應(yīng)的是網(wǎng)格資源的異構(gòu)性，這表現(xiàn)在網(wǎng)格資源不僅體系結(jié)構(gòu)各異，而且類型復(fù)雜。網(wǎng)格資源不僅包括各類計(jì)算能力各異的計(jì)算機(jī)，而且包括各種類型的數(shù)據(jù)庫(kù)、儀器設(shè)備甚至人力資源。將這些異構(gòu)的計(jì)算機(jī)系統(tǒng)和類別不同的資源進(jìn)行統(tǒng)一管理，解決相互之間的通信和互操作問(wèn)題，共同協(xié)作完成各類任務(wù)要求是網(wǎng)格計(jì)算技術(shù)的一個(gè)重要研究課題。

1.4 網(wǎng)格環(huán)境的動(dòng)態(tài)性

由于網(wǎng)格資源是分布自治的，因此網(wǎng)格環(huán)境具有動(dòng)態(tài)性。某一時(shí)刻網(wǎng)格擁有的某一資源或功能在下一時(shí)刻就可能出現(xiàn)故障或者不可用，而原來(lái)沒(méi)有的資源隨著時(shí)間推移可能會(huì)隨時(shí)加入網(wǎng)格環(huán)境。網(wǎng)格管理必須解決好資源的動(dòng)態(tài)性問(wèn)題，當(dāng)網(wǎng)格資源動(dòng)態(tài)減少或出現(xiàn)故障時(shí)，網(wǎng)格應(yīng)能夠及時(shí)采取措施，實(shí)現(xiàn)任務(wù)的自動(dòng)遷移，盡可能減少用戶損失;網(wǎng)格資源的動(dòng)態(tài)增加則要求網(wǎng)格具有可擴(kuò)展性，即應(yīng)允許新的資源隨時(shí)加入網(wǎng)格，并可以和原有資源融合在一起，共同發(fā)揮作用。

2 網(wǎng)格計(jì)算的應(yīng)用領(lǐng)域

網(wǎng)格計(jì)算的應(yīng)用領(lǐng)域非常廣泛。概括來(lái)說(shuō)，網(wǎng)格計(jì)算目前主要應(yīng)用在分布式超級(jí)計(jì)算、分布式儀器系統(tǒng)、高吞吐率計(jì)算、數(shù)據(jù)密集型計(jì)算、遠(yuǎn)程沉浸和信息集成等領(lǐng)域。

分布式超級(jí)計(jì)算是指將分布在不同地點(diǎn)的各類計(jì)算資源用高速網(wǎng)絡(luò)連接起來(lái)，形成比單臺(tái)超級(jí)計(jì)算機(jī)強(qiáng)大得多的計(jì)算系統(tǒng)。目前許多復(fù)雜問(wèn)題在任何一臺(tái)超級(jí)計(jì)算機(jī)上都無(wú)法完成其計(jì)算任務(wù)，網(wǎng)格系統(tǒng)可以把分布在世界各地的閑置資源集中起來(lái)，協(xié)同解決復(fù)雜的大規(guī)模問(wèn)題。

分布式儀器系統(tǒng)是指基于網(wǎng)格來(lái)管理分布在世界各地的貴重儀器設(shè)備，通過(guò)網(wǎng)格計(jì)算環(huán)境提供一種遠(yuǎn)程訪問(wèn)儀器設(shè)備的手段，從而在方便用戶的同時(shí)提高貴重儀器設(shè)備的利用率。

高性能計(jì)算主要關(guān)注系統(tǒng)的計(jì)算速度和效率，而高吞吐率計(jì)算和高性能計(jì)算不同，它主要關(guān)注一個(gè)較長(zhǎng)時(shí)間段內(nèi)系統(tǒng)所完成的總?cè)蝿?wù)量。實(shí)際應(yīng)用中，許多問(wèn)題對(duì)計(jì)算速度要求并不高，但對(duì)系統(tǒng)整體的吞吐率要求則比較苛刻。網(wǎng)格可以將大量閑置的計(jì)算資源集中起來(lái)提供給那些對(duì)時(shí)間不敏感的問(wèn)題，共同完成大量計(jì)算，實(shí)現(xiàn)較高的系統(tǒng)吞吐率。

當(dāng)用于數(shù)據(jù)密集型計(jì)算時(shí)，網(wǎng)格更側(cè)重于數(shù)據(jù)的存儲(chǔ)、傳輸和處理。許多高能物理實(shí)驗(yàn)、航空航天計(jì)算、天氣預(yù)測(cè)等都屬于數(shù)據(jù)密集型計(jì)算問(wèn)題。對(duì)于該類問(wèn)題，數(shù)據(jù)的采集、處理、分析、存儲(chǔ)，以及可視化設(shè)備的安置等往往是分散的，求解該類問(wèn)題往往會(huì)產(chǎn)生很大的通信和計(jì)算需求。網(wǎng)格系統(tǒng)通過(guò)集成眾多分散的閑置資源可以很好地求解這類問(wèn)題。

遠(yuǎn)程沉浸共享一個(gè)集中的虛擬環(huán)境，該環(huán)境可以是對(duì)場(chǎng)景或問(wèn)題的真實(shí)反映，也可以是一個(gè)純粹的虛構(gòu)空間，顯然這是網(wǎng)格在信息集成領(lǐng)域的一個(gè)典型應(yīng)用。此外，網(wǎng)格技術(shù)還可以應(yīng)用于科學(xué)研究領(lǐng)域。例如，應(yīng)用于生物醫(yī)學(xué)，網(wǎng)格能夠?yàn)樗幤费邪l(fā)提供強(qiáng)大的計(jì)算能力;運(yùn)用于工程領(lǐng)域，基于網(wǎng)格可以進(jìn)行復(fù)雜的仿真與設(shè)計(jì);運(yùn)用于數(shù)據(jù)搜集分析，使用網(wǎng)格可以存儲(chǔ)和處理各種海量數(shù)據(jù)信息，等等。

3 網(wǎng)格計(jì)算的任務(wù)調(diào)度策略

如何使網(wǎng)格充分發(fā)揮作用，使應(yīng)用獲得最大性能，這是網(wǎng)格任務(wù)調(diào)度策略要解決的問(wèn)題。本節(jié)對(duì)網(wǎng)格任務(wù)調(diào)度的特點(diǎn)、評(píng)價(jià)指標(biāo)以及現(xiàn)有的網(wǎng)格任務(wù)調(diào)度算法進(jìn)行討論。

3.1 網(wǎng)格任務(wù)調(diào)度的特點(diǎn)

在網(wǎng)格中，大量任務(wù)共享各種網(wǎng)格資源，網(wǎng)格資源的動(dòng)態(tài)性、異構(gòu)性和多樣性使得網(wǎng)格任務(wù)調(diào)度要比傳統(tǒng)高性能計(jì)算復(fù)雜得多。網(wǎng)格任務(wù)調(diào)度策略應(yīng)建立隨時(shí)間變化的性能預(yù)測(cè)模型，模型應(yīng)能夠根據(jù)網(wǎng)格的動(dòng)態(tài)信息來(lái)預(yù)測(cè)網(wǎng)格性能的波動(dòng)。此外，網(wǎng)格任務(wù)調(diào)度還要考慮調(diào)度算法的可移植性、可擴(kuò)展性、調(diào)度效率、可重復(fù)性以及網(wǎng)格調(diào)度和本地調(diào)度之間的相互影響等一系列問(wèn)題。總的來(lái)說(shuō)，網(wǎng)格任務(wù)調(diào)度具有平臺(tái)異構(gòu)、規(guī)模大、非集中、不干涉網(wǎng)格節(jié)點(diǎn)的內(nèi)部調(diào)度、可擴(kuò)展以及動(dòng)態(tài)自適應(yīng)等特點(diǎn)［2］。

3.2 網(wǎng)格任務(wù)調(diào)度的評(píng)價(jià)指標(biāo)

網(wǎng)格調(diào)度的目標(biāo)是實(shí)現(xiàn)對(duì)大量用戶任務(wù)的最優(yōu)調(diào)度，提高網(wǎng)格系統(tǒng)的總體吞吐率。具體來(lái)說(shuō)，網(wǎng)格任務(wù)調(diào)度的性能可從總執(zhí)行時(shí)間、負(fù)載均衡性、服務(wù)質(zhì)量以及經(jīng)濟(jì)性原則等幾個(gè)方面來(lái)進(jìn)行衡量。任務(wù)總執(zhí)行時(shí)間越小說(shuō)明調(diào)度策略越好，任務(wù)調(diào)度的一個(gè)重要目標(biāo)就是希望得到最小的總執(zhí)行時(shí)間。負(fù)載均衡是指網(wǎng)格系統(tǒng)中各資源之間的負(fù)載平衡情況，一個(gè)優(yōu)秀的調(diào)度方案應(yīng)使各類網(wǎng)格資源都充分發(fā)揮作用，最大限度地利用網(wǎng)格資源，使任務(wù)盡可能快地完成。另外隨著網(wǎng)格服務(wù)逐步由無(wú)償演變?yōu)楦顿M(fèi)，任務(wù)調(diào)度也必須考慮其經(jīng)濟(jì)性，合理的任務(wù)調(diào)度策略應(yīng)在保證一定服務(wù)質(zhì)量的同時(shí)，盡可能地減少用戶開(kāi)支。

3.3 網(wǎng)格任務(wù)調(diào)度算法

目前已有的任務(wù)調(diào)度算法眾多，根據(jù)調(diào)度算法的執(zhí)行時(shí)間，可將其分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩大類［3］。靜態(tài)調(diào)度是指所有網(wǎng)格任務(wù)與計(jì)算資源之間的映射關(guān)系在執(zhí)行調(diào)度之前即全部確定;動(dòng)態(tài)調(diào)度與靜態(tài)調(diào)度不同，其部分任務(wù)到計(jì)算資源的映射關(guān)系在調(diào)度執(zhí)行期間才根據(jù)具體情況確定下來(lái)。下面分別介紹。

3.3.1 靜態(tài)任務(wù)調(diào)度

目前 常 用 的 靜 態(tài) 調(diào) 度 算 法 有 OLB［4］、MET［5］、 MCT［6］、 Min-min［7］、 Max-min［8］、 Duplex［9］、GA［10］、SA［11］以及蟻群算法［12］等。

OLB(Opportunistic load balancing)即機(jī)會(huì)負(fù)載均衡，這是一種典型的靜態(tài)調(diào)度算法。其做法是把任務(wù)隨機(jī)地分配給下一個(gè)就緒機(jī)器;若同時(shí)存在多個(gè)就緒機(jī)器，就把任務(wù)隨機(jī)地分配給其中的一個(gè)。該算法簡(jiǎn)單直觀，然而其不考慮任務(wù)的執(zhí)行時(shí)間和機(jī)器的期望完成時(shí)間，因此可能會(huì)導(dǎo)致較大的時(shí)間跨度。

MET(Minimum execution time)即最小執(zhí)行時(shí)間，它總是將任務(wù)指派給執(zhí)行最快的機(jī)器，因此可以保證每個(gè)任務(wù)都花費(fèi)最少的執(zhí)行時(shí)間，然而同時(shí)也容易導(dǎo)致大多數(shù)任務(wù)總是在幾個(gè)性能最好的機(jī)器上執(zhí)行，使得計(jì)算資源之間負(fù)載不均衡。

MCT(Minimum completion time)即最早完成時(shí)間，該算法總是將任務(wù)分配給具有最早完成時(shí)間的計(jì)算資源，它可以保證調(diào)度的任務(wù)盡快執(zhí)行結(jié)束和計(jì)算資源負(fù)載均衡。然而由于該算法并非將任務(wù)指派給執(zhí)行最快的機(jī)器，因此可能會(huì)增加全部任務(wù)的最大完成時(shí)間。

Min－min算法首先計(jì)算每個(gè)任務(wù)在各個(gè)機(jī)器上的期望完成時(shí)間，獲得每個(gè)任務(wù)在所有機(jī)器上的最早完成時(shí)間，然后將具有最小最早完成時(shí)間的任務(wù)指派給相應(yīng)的機(jī)器;指派后更新對(duì)應(yīng)機(jī)器的就緒時(shí)間，并將已指派的任務(wù)從任務(wù)集中刪除。重復(fù)上述過(guò)程，直至全部任務(wù)調(diào)度完畢。Max－min算法與Min－min類似，其區(qū)別在于Max－min首先調(diào)度長(zhǎng)任務(wù)，即首先調(diào)度具有最大最早完成時(shí)間的任務(wù)。

Duplex算法是Min－min與Max－min的結(jié)合，其對(duì)兩者進(jìn)行比較，并選擇調(diào)度效果較好的方案執(zhí)行任務(wù)調(diào)度。Duplex算法在Min－min和Max－min二者中的任意一個(gè)執(zhí)行效果較好的情況下即能夠得到不錯(cuò)的調(diào)度性能。

遺傳算法 (Genetic algorithm，GA)將問(wèn)題的解構(gòu)造成染色體，并基于染色體的進(jìn)化來(lái)求取問(wèn)題的最優(yōu)解。算法根據(jù)適者生存法則，首先構(gòu)造一群染色體，然后基于某種適應(yīng)度函數(shù)從中選擇能夠較好適應(yīng)環(huán)境的若干染色體進(jìn)行復(fù)制，并通過(guò)交叉、變異操作產(chǎn)生新一代能夠更好適應(yīng)環(huán)境的染色體群。迭代上述過(guò)程，通過(guò)不斷進(jìn)化，最后將染色體群收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，即問(wèn)題的最優(yōu)解。

模擬退火算法 (Simulated Annealing，SA)來(lái)源于固體的退火原理。固體加熱時(shí)，其內(nèi)部粒子隨溫度升高逐漸變?yōu)闊o(wú)序狀，固體冷卻時(shí)粒子漸趨有序，并在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能變?yōu)樽钚　Ｓ霉腆w降溫過(guò)程模擬任務(wù)調(diào)度問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T描述控制參數(shù)t，即得到求解任務(wù)調(diào)度問(wèn)題的模擬退火算法。由初始解i和控制參數(shù)初始值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“計(jì)算新解→計(jì)算目標(biāo)函數(shù)值→接受或拒絕”的迭代過(guò)程，逐步減小t值，迭代終止時(shí)即得到調(diào)度問(wèn)題的解。

蟻群算法通過(guò)模擬螞蟻覓食行為來(lái)進(jìn)行問(wèn)題的求解。螞蟻覓食時(shí)會(huì)在其經(jīng)過(guò)的路徑上釋放一種信息素，其他螞蟻會(huì)感知到這種信息素的存在并選擇信息素多的路徑通過(guò)，而信息素隨著時(shí)間延長(zhǎng)會(huì)逐漸揮發(fā)。初始階段，所有路徑上的螞蟻數(shù)量相當(dāng)，隨著時(shí)間的延長(zhǎng)，較短路徑上的信息素增加較快;接下來(lái)其他螞蟻選擇較短路徑通過(guò)的概率增大，最終所有的螞蟻都將選擇最短的路徑通過(guò)。蟻群算法具有并發(fā)性和可擴(kuò)展性，將某一時(shí)刻所有影響網(wǎng)格資源狀態(tài)的因素都由信息素來(lái)描述，即可快速求解網(wǎng)格任務(wù)調(diào)度問(wèn)題。

除了上述算法，靜態(tài)的網(wǎng)格任務(wù)調(diào)度算法還有很多，如結(jié)合了GA和SA的遺傳模擬退火算法 (Genetic simulated annealing，GSA)［13］、啟發(fā)式的 A*算法［14］、基于解空間搜索的 Tabu 算法［15］等等。

3.3.2 動(dòng)態(tài)任務(wù)調(diào)度

現(xiàn)有的動(dòng)態(tài)調(diào)度算法可分為在線模式 (On－line mode)和批模式 (Batch mode)兩大類［16］。在線模式是指當(dāng)調(diào)度器收到一個(gè)任務(wù)時(shí)立即為其指派計(jì)算資源;而在批模式下，調(diào)度器收到一個(gè)任務(wù)后并不立即為其分配計(jì)算資源，只有當(dāng)?shù)竭_(dá)任務(wù)組成一批并且影射事件到達(dá)后，調(diào)度器才為這些任務(wù)指派計(jì)算資源。

常見(jiàn)的在線模式調(diào)度算法有MCT、MET、OLB、SA、KPB等算法。其中MCT、MET、OLB的做法和靜態(tài)調(diào)度類似。SA算法 (Switching algorithm)基于應(yīng)用負(fù)載在計(jì)算資源間的分布情況，周期性地使用MCT和MET算法實(shí)施調(diào)度，因此SA算法同時(shí)具有MCT和MET的特點(diǎn)。K最優(yōu)調(diào)度 (K－percent best，KPB)在執(zhí)行調(diào)度時(shí)僅考慮部分可用的計(jì)算資源。設(shè)M為可用資源數(shù)目，K滿足100/M≤K≤100，則1≤KM/100≤M。KPB算法從全部可用資源中選取KM/100個(gè)參與任務(wù)調(diào)度，算法每次將任務(wù)指派給具有最小完成時(shí)間的機(jī)器。顯然，如K=100，則全部機(jī)器參與調(diào)度，此時(shí)KPB算法等同于MCT算法;如果K=100/M，則僅一臺(tái)機(jī)器參與調(diào)度，此時(shí)KPB算法等同于MET算法。

常見(jiàn)的批模式調(diào)度算法有Min－min、Max－min、快速貪吃算法、最大時(shí)間跨度算法等。其中Min－min、Max－min的做法和靜態(tài)調(diào)度類似。快速貪吃算法根據(jù)到達(dá)順序依次從當(dāng)前批中選擇任務(wù)，并計(jì)算該任務(wù)的期望執(zhí)行時(shí)間;然后將當(dāng)前具有最小期望完成時(shí)間的計(jì)算資源指派給該任務(wù)。最大時(shí)間跨度算法不保證當(dāng)前調(diào)度最佳，但其未來(lái)調(diào)度趨勢(shì)趨于最佳。算法首先依次找出當(dāng)前批任務(wù)中每個(gè)任務(wù)的最小最早完成時(shí)間和次小最早完成時(shí)間及各自對(duì)應(yīng)的計(jì)算資源;然后計(jì)算每個(gè)任務(wù)的次小最早完成時(shí)間和最小最早完成時(shí)間的差，即時(shí)間跨度;最后選取時(shí)間跨度最大的任務(wù)進(jìn)行調(diào)度。如此重復(fù)，直到當(dāng)前批任務(wù)全部調(diào)度完畢。

綜上，對(duì)網(wǎng)格任務(wù)調(diào)度算法進(jìn)行了詳細(xì)介紹。其中，靜態(tài)調(diào)度算法相對(duì)簡(jiǎn)單，算法開(kāi)銷小，對(duì)數(shù)據(jù)的依賴性不高;盡管如此，該類算法實(shí)時(shí)性不高，并且可能會(huì)導(dǎo)致資源負(fù)載不均衡。與靜態(tài)算法相比，動(dòng)態(tài)調(diào)度能夠有效處理計(jì)算資源的負(fù)載評(píng)估、作業(yè)選擇以及任務(wù)遷移等問(wèn)題，因此動(dòng)態(tài)調(diào)度算法能夠較好地保證負(fù)載均衡，但同時(shí)動(dòng)態(tài)調(diào)度算法需要付出較高的系統(tǒng)開(kāi)銷。

4 結(jié)束語(yǔ)

本文對(duì)網(wǎng)格計(jì)算技術(shù)及其任務(wù)調(diào)度策略進(jìn)行了探討。網(wǎng)格計(jì)算是針對(duì)復(fù)雜的科學(xué)計(jì)算問(wèn)題而產(chǎn)生的一種新型計(jì)算模式，由于網(wǎng)格計(jì)算資源分散在世界各地，其資源的動(dòng)態(tài)性、異構(gòu)性和多樣性使得網(wǎng)格任務(wù)調(diào)度問(wèn)題要比傳統(tǒng)高性能計(jì)算復(fù)雜得多。網(wǎng)格任務(wù)的調(diào)度策略應(yīng)具有動(dòng)態(tài)自適應(yīng)性，此外調(diào)度算法還應(yīng)綜合考慮可移植性、可擴(kuò)展性、服務(wù)質(zhì)量、負(fù)載均衡以及網(wǎng)格調(diào)度和本地調(diào)度之間的相互影響等問(wèn)題。根據(jù)上述指標(biāo)，本文對(duì)當(dāng)前現(xiàn)有的網(wǎng)格任務(wù)調(diào)度算法進(jìn)行了深入而詳細(xì)的討論。本文工作將為我們未來(lái)對(duì)網(wǎng)格計(jì)算技術(shù)進(jìn)行更深入的研究奠定基礎(chǔ)。

［1］徐志輝，陳渝，劉鵬．網(wǎng)格計(jì)算［M］．北京：清華大學(xué)出版社，2002．

［2］羅紅，慕德俊，鄧智群，等．網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述［J］．計(jì)算機(jī)應(yīng)用研究，2005，22(5)：16－19．

［3］Tracy D B，Howard J S，Noah B，et al．A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems［J］．Journal of parallel and distributed computing，2001，61(6)：810 － 837．

［4］Noriyuki F，Kenichi H．A comparison among grid scheduling algorithms for independent coarse－grained tasks［J］．Proceedings of the 04’symposium on applications and the internet－ workshops，2004：674 －680．

［5］Richard F，Michael G，Stephen A，et al．Scheduling resources in multi-user，heterogeneous，computing environments with smartnet．Proc［M］．of the 7thIEEE heterogeneous computing workshop．1998：184－199．

［6］徐志偉，馮百明，李偉．網(wǎng)格計(jì)算技術(shù)［M］．北京：電子工業(yè)出版社，2004．

［7］Liu Jue-fu，Li Gang．An improved Min-min grid tasks scheduling algorithm based on Qos constraints．Proceedings of the 2010 int［M］．conference on optics photonics and energy engineering．2010：281－283．

［8］Muthucumaru M，Shoukat A，Howard J，et al．Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems［M］．Proceedings of the 8thheterogeneous computing workshop．Washington，USA，1999：30 －44．

［9］Cheng S T，Hsieh M T，Chen B F．Fairness-based scheduling algorithm for time division duplex mode IEEE 802．16 broadband wireless access systems［J］．IET communications，2010，4(9)：1065 －1072．

［10］Vincenzo D，Marco M．Scheduling in a grid computing environment using genetic algorithms．Proceedings of the 16th international parallel and distributed processing symposium［M］．Florida，US，2002：235 －239．

［11］Ajith A，Rajkumar B，Nath B．Nature＇s heuristics for scheduling jobs on computational grids．Proc．of the 8th international conference on advanced computing and communications［M］．Cochin，India，2000：45 －52．

［12］Xu Zhihong，Hou Xiangdan，Sun Jizhou．Ant algorithm －based task scheduling in grid computing．Proc［M］．of the IEEE Canadian conference on electrical and computer engineering，2003：1107 －1110．

［13］Marco A C，Abelardo R，Erika Y A，et al．Genetic － annealing algorithm in grid environment for scheduling problems［M］．Security － Enriched Urban Computing and Smart Grid，Springer Berlin Heidelberg，2010．

［14］Chow K，Liu B．On mapping signal processing algorithms to a heterogeneous multiprocessor system［J］．Proc．of the 1991 international conference on acoustics，speech，and signal processing，1991(3)：1585 －1588．

［15］De Falco I，Del Balio R，Tarantino E，et al．Improving search by incorporating evolution principles in parallel tabu search［J］．In IEEE Conference on Evolutionary Computation，1994(2)：823 －828．

［16］丁等，陳國(guó)良，顧鈞．計(jì)算網(wǎng)格環(huán)境下一個(gè)統(tǒng)一的資源映射策略［J］．軟件學(xué)報(bào)，2002，13(7)：1303－1308．

Grid Computing Technology and Its Task Scheduling Strategies

DENG Jian-guang1，2PAN Xiao-heng1YUAN Hua-qiang1
(1．Engineering ＆ Technology Institute，Dongguan University of Technology，Dongguan 523808，China;2．School of Computer Science ＆ Engineering，South China University of Technology，Guangzhou 510006，China)

The grid computing technology and its task scheduling strategies were discussed and summarized in detail in this paper．First，we introduced the origin of grid computing and the basic requirements which the grid system must be satisfied．Then we focused on the particular characteristics of grid computing that were different from the traditional distributed computing system，and briefly discussed the application fields of grid technology．Finally，the grid task scheduling strategy was discussed especially，which included the scheduling characteristic，the evaluation criterion，and the existing scheduling algorithm．The paper will be the guideline for our future study on grid computing．

grid computing;distributed computing;task scheduling;load balance

TP399

A

1009－0312(2012)01－0030－05

2011－06－30

國(guó)家自然科學(xué)基金 (65073145);廣東省科技計(jì)劃項(xiàng)目 (2011B061300103);東莞市科技計(jì)劃項(xiàng)目 (201010814006);東莞理工學(xué)院自然科學(xué)青年基金 (2010ZQ10)。

鄧見(jiàn)光 (1981—)，男，河南商水人，助理研究員，博士生，主要從事海量存儲(chǔ)技術(shù)、虛擬現(xiàn)實(shí)技術(shù)研究。

科學(xué)計(jì)算作為繼理論推導(dǎo)、科學(xué)實(shí)驗(yàn)之后進(jìn)行科學(xué)研究與知識(shí)發(fā)現(xiàn)的第三種手段，已經(jīng)成為更好的認(rèn)識(shí)世界的工具。隨著科學(xué)研究的不斷深入，人們迫切需要性能更高、速度更快的計(jì)算機(jī)系統(tǒng)。目前，網(wǎng)絡(luò)技術(shù)飛速發(fā)展，網(wǎng)絡(luò)帶寬日益提升;另一方面，隨著個(gè)人計(jì)算機(jī)系統(tǒng)的計(jì)算能力不斷提高，產(chǎn)生了大量的閑置計(jì)算資源。在這種背景下，一種新型的基于異構(gòu)、動(dòng)態(tài)、跨域的協(xié)同資源共享和問(wèn)題求解方式應(yīng)運(yùn)而生，這即是網(wǎng)格計(jì)算。網(wǎng)格可以把各種孤立的閑置計(jì)算資源通過(guò)互聯(lián)網(wǎng)連接起來(lái)，形成一個(gè)虛擬的超級(jí)計(jì)算機(jī)系統(tǒng)，其致力于為終端用戶提供與具體地理位置和計(jì)算資源無(wú)關(guān)的通用計(jì)算能力。網(wǎng)格的美好前景吸引了大量的研究人員投入其中，目前它已成為信息學(xué)科最熱門(mén)的研究方向之一。

book=0,ebook=111