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

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

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

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

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

對網(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ú)特特征，接下來對網(wǎng)格計(jì)算的應(yīng)用領(lǐng)域進(jìn)行了簡單探討。最后從網(wǎng)格任務(wù)調(diào)度的特點(diǎn)、評價(jià)指標(biāo)以及現(xiàn)有的調(diào)度算法等方面對網(wǎng)格計(jì)算的任務(wù)調(diào)度策略進(jìn)行了詳細(xì)討論。全文工作將指導(dǎo)我們未來進(jìn)一步深入研究網(wǎng)格計(jì)算。

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

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

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

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ǎng)格資源雖是分布式的，但它們卻可以充分共享，網(wǎng)格系統(tǒng)的資源可以提供給任一個網(wǎng)格用戶。資源共享是網(wǎng)格計(jì)算的目的，也是網(wǎng)格計(jì)算的核心內(nèi)容。這里的共享包括計(jì)算資源、數(shù)據(jù)庫、儀器設(shè)備以及人力資源等各類資源的共享。

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

網(wǎng)格資源由分布在互聯(lián)網(wǎng)中分屬于不同組織或個人的資源構(gòu)成。網(wǎng)格資源首先屬于資源的所有者，資源所有者對其資源具有自主管理權(quán)，這即是網(wǎng)格資源的自治性。此外，網(wǎng)格資源也必須接受網(wǎng)格系統(tǒng)的統(tǒng)一管理，否則不同的分布式資源就無法建立聯(lián)系，更無法實(shí)現(xiàn)資源的共享協(xié)同。因此，網(wǎng)格一方面允許網(wǎng)格資源的所有者對其資源進(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í)具有重要意義。與自相似性相對應(yīng)的是網(wǎng)格資源的異構(gòu)性，這表現(xiàn)在網(wǎng)格資源不僅體系結(jié)構(gòu)各異，而且類型復(fù)雜。網(wǎng)格資源不僅包括各類計(jì)算能力各異的計(jì)算機(jī)，而且包括各種類型的數(shù)據(jù)庫、儀器設(shè)備甚至人力資源。將這些異構(gòu)的計(jì)算機(jī)系統(tǒng)和類別不同的資源進(jìn)行統(tǒng)一管理，解決相互之間的通信和互操作問題，共同協(xié)作完成各類任務(wù)要求是網(wǎng)格計(jì)算技術(shù)的一個重要研究課題。

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

由于網(wǎng)格資源是分布自治的，因此網(wǎng)格環(huán)境具有動態(tài)性。某一時(shí)刻網(wǎng)格擁有的某一資源或功能在下一時(shí)刻就可能出現(xiàn)故障或者不可用，而原來沒有的資源隨著時(shí)間推移可能會隨時(shí)加入網(wǎng)格環(huán)境。網(wǎng)格管理必須解決好資源的動態(tài)性問題，當(dāng)網(wǎng)格資源動態(tài)減少或出現(xiàn)故障時(shí)，網(wǎng)格應(yīng)能夠及時(shí)采取措施，實(shí)現(xiàn)任務(wù)的自動遷移，盡可能減少用戶損失;網(wǎ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)域非常廣泛。概括來說，網(wǎng)格計(jì)算目前主要應(yīng)用在分布式超級計(jì)算、分布式儀器系統(tǒng)、高吞吐率計(jì)算、數(shù)據(jù)密集型計(jì)算、遠(yuǎn)程沉浸和信息集成等領(lǐng)域。

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

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

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

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

遠(yuǎn)程沉浸共享一個集中的虛擬環(huán)境，該環(huán)境可以是對場景或問題的真實(shí)反映，也可以是一個純粹的虛構(gòu)空間，顯然這是網(wǎng)格在信息集成領(lǐng)域的一個典型應(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)格可以存儲和處理各種海量數(shù)據(jù)信息，等等。

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

如何使網(wǎng)格充分發(fā)揮作用，使應(yīng)用獲得最大性能，這是網(wǎng)格任務(wù)調(diào)度策略要解決的問題。本節(jié)對網(wǎng)格任務(wù)調(diào)度的特點(diǎn)、評價(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)格資源的動態(tài)性、異構(gòu)性和多樣性使得網(wǎng)格任務(wù)調(diào)度要比傳統(tǒng)高性能計(jì)算復(fù)雜得多。網(wǎng)格任務(wù)調(diào)度策略應(yīng)建立隨時(shí)間變化的性能預(yù)測模型，模型應(yīng)能夠根據(jù)網(wǎng)格的動態(tài)信息來預(yù)測網(wǎng)格性能的波動。此外，網(wǎng)格任務(wù)調(diào)度還要考慮調(diào)度算法的可移植性、可擴(kuò)展性、調(diào)度效率、可重復(fù)性以及網(wǎng)格調(diào)度和本地調(diào)度之間的相互影響等一系列問題。總的來說，網(wǎng)格任務(wù)調(diào)度具有平臺異構(gòu)、規(guī)模大、非集中、不干涉網(wǎng)格節(jié)點(diǎn)的內(nèi)部調(diào)度、可擴(kuò)展以及動態(tài)自適應(yīng)等特點(diǎn)［2］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

常見的在線模式調(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個參與任務(wù)調(diào)度，算法每次將任務(wù)指派給具有最小完成時(shí)間的機(jī)器。顯然，如K=100，則全部機(jī)器參與調(diào)度，此時(shí)KPB算法等同于MCT算法;如果K=100/M，則僅一臺機(jī)器參與調(diào)度，此時(shí)KPB算法等同于MET算法。

常見的批模式調(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)度最佳，但其未來調(diào)度趨勢趨于最佳。算法首先依次找出當(dāng)前批任務(wù)中每個任務(wù)的最小最早完成時(shí)間和次小最早完成時(shí)間及各自對應(yīng)的計(jì)算資源;然后計(jì)算每個任務(wù)的次小最早完成時(shí)間和最小最早完成時(shí)間的差，即時(shí)間跨度;最后選取時(shí)間跨度最大的任務(wù)進(jìn)行調(diào)度。如此重復(fù)，直到當(dāng)前批任務(wù)全部調(diào)度完畢。

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

4 結(jié)束語

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

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

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

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

book=0,ebook=111