易侃，王汝傳

（1. 南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003;2. 中國電子科技集團(tuán)第28研究所 C4ISR國防科技重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210007）

1 引言

數(shù)據(jù)網(wǎng)格[1]為各種數(shù)據(jù)密集型的應(yīng)用提供了一個(gè)高性能、大容量、高速傳輸?shù)牟⑿?、分布、廣域的計(jì)算平臺(tái)。在數(shù)據(jù)網(wǎng)格環(huán)境下, 任務(wù)根據(jù)任務(wù)調(diào)度的結(jié)果被提交給計(jì)算資源執(zhí)行，而任務(wù)所需要的數(shù)據(jù)首先通過檢索元數(shù)據(jù)服務(wù)和目錄服務(wù)獲取數(shù)據(jù)副本的位置，然后通過副本選擇服務(wù)和傳輸服務(wù)獲取數(shù)據(jù)。對(duì)于數(shù)據(jù)敏感的任務(wù)，數(shù)據(jù)的傳輸時(shí)間是任務(wù)完成時(shí)間的重要組成部分，因此需要副本復(fù)制管理動(dòng)態(tài)的調(diào)整副本的位置分布，使數(shù)據(jù)更接近任務(wù)所在的計(jì)算資源, 從而可以在更短的時(shí)間內(nèi)訪問數(shù)據(jù)，更快地執(zhí)行任務(wù)。

對(duì)于數(shù)據(jù)敏感任務(wù)的調(diào)度，已有很多將數(shù)據(jù)相關(guān)的因素結(jié)合到任務(wù)調(diào)度中的策略，可以將其分為3個(gè)階段：第1階段是在資源的選擇過程中考慮網(wǎng)絡(luò)的帶寬因素，如文獻(xiàn)[2～4]，但是此時(shí)任務(wù)所需的數(shù)據(jù)規(guī)模較小，任務(wù)仍屬計(jì)算密集型；第2階段是采用數(shù)據(jù)驅(qū)動(dòng)的任務(wù)調(diào)度策略，如文獻(xiàn)[5～7]，將數(shù)據(jù)的大小和數(shù)據(jù)的位置因素考慮到資源的選擇過程中，但這些方法中的數(shù)據(jù)是固定在某個(gè)資源上的單一數(shù)據(jù)；第3個(gè)階段是集中式的任務(wù)調(diào)度和數(shù)據(jù)復(fù)制管理集成策略，在任務(wù)調(diào)度考慮網(wǎng)絡(luò)帶寬和副本位置的同時(shí)，通過引入集中式的副本管理機(jī)制，動(dòng)態(tài)的創(chuàng)建數(shù)據(jù)的副本和調(diào)整副本的位置，使得任務(wù)所需要的數(shù)據(jù)更靠近它所執(zhí)行的資源，如文獻(xiàn)[8～10]所述，但是在跨多個(gè)組織域的實(shí)際的網(wǎng)格系統(tǒng)中，集中式的任務(wù)調(diào)度和數(shù)據(jù)管理，在可操作性、可靠性和性能上都存在問題，因此有必要研究分布式的任務(wù)調(diào)度和副本復(fù)制管理策略。

為此論文首先提出了數(shù)據(jù)網(wǎng)格的三層邏輯視圖，并基于此視圖引出了分布式任務(wù)調(diào)度與副本復(fù)制策略集成的中間件體系結(jié)構(gòu)，然后重點(diǎn)研究了在此分布式架構(gòu)下，基于博弈論的分布式副本復(fù)制策略，最后通過仿真試驗(yàn)驗(yàn)證分布式在線任務(wù)調(diào)度和副本復(fù)制集成策略的有效性和優(yōu)越性。

2 分布式任務(wù)調(diào)度和副本復(fù)制集成體系結(jié)構(gòu)

類比于 J2EE的三層體系結(jié)構(gòu)，數(shù)據(jù)網(wǎng)格邏輯上也可以分為3層，圖1是數(shù)據(jù)網(wǎng)格三層的邏輯視圖，其中，用戶層中的用戶是任務(wù)的發(fā)起者，計(jì)算資源層中的計(jì)算資源是應(yīng)用邏輯的執(zhí)行者，而存儲(chǔ)資源層中的存儲(chǔ)資源是應(yīng)用所需數(shù)據(jù)的管理者。雖然邏輯上是分層的，但是實(shí)際上各層之間資源在物理位置上可能是重疊的，比如用戶操作的資源可能就是一個(gè)計(jì)算資源，同樣一個(gè)計(jì)算資源也可以附帶一個(gè)海量的存儲(chǔ)資源。

圖1 數(shù)據(jù)網(wǎng)格系統(tǒng)三層邏輯視圖

計(jì)算網(wǎng)格研究的范疇對(duì)應(yīng)于圖1第2層，應(yīng)用邏輯將會(huì)通過資源代理透明地在分布的、高性能的計(jì)算資源上執(zhí)行。當(dāng)應(yīng)用需要海量數(shù)據(jù)時(shí)，第3層的存儲(chǔ)資源將會(huì)為它提供數(shù)據(jù)支持，數(shù)據(jù)的檢索、傳輸、可靠性、一致性等都由該層的數(shù)據(jù)管理功能提供。數(shù)據(jù)網(wǎng)格需要第2層和第3層的有機(jī)集成共同為用戶透明地提供高性能的計(jì)算和存儲(chǔ)資源，其中，第2層與第3層集成的關(guān)鍵是任務(wù)調(diào)度和副本復(fù)制策略的集成。

圖2給出了數(shù)據(jù)網(wǎng)格中分布式的任務(wù)調(diào)度和副本復(fù)制集成體系結(jié)構(gòu)。用戶層有多個(gè)區(qū)域調(diào)度器（RS）接收用戶提交的任務(wù)，每個(gè)調(diào)度器負(fù)責(zé)一片自治域的任務(wù)請(qǐng)求。多個(gè)RS解決了集中式調(diào)度器的單點(diǎn)失效問題。當(dāng)某個(gè) RS的負(fù)載過重，那么可以增加新的 RS來分流任務(wù)請(qǐng)求，也可以將部分請(qǐng)求分流到其他RS，因此該體系結(jié)構(gòu)有很好的擴(kuò)展性。

在計(jì)算資源層，計(jì)算資源收到用戶任務(wù)請(qǐng)求后，本地調(diào)度器（LS）根據(jù)本地調(diào)度策略為任務(wù)分配計(jì)算單元，當(dāng)有任務(wù)包含對(duì)數(shù)據(jù)的請(qǐng)求時(shí)，本地調(diào)度器向本地副本管理器（LRM）請(qǐng)求數(shù)據(jù)，LRM判斷本地存儲(chǔ)Cache中是否包含所需數(shù)據(jù)，如果沒有則向遠(yuǎn)程存儲(chǔ)資源廣播數(shù)據(jù)請(qǐng)求，并根據(jù)確認(rèn)請(qǐng)求的返回的信息估算計(jì)算資源與存儲(chǔ)資源之間的帶寬，最后選擇訪問帶寬最大的存儲(chǔ)資源獲取數(shù)據(jù)。

在存儲(chǔ)資源層，存儲(chǔ)資源接收數(shù)據(jù)請(qǐng)求，如果包含請(qǐng)求的數(shù)據(jù)則確認(rèn)該請(qǐng)求。此外，每個(gè)存儲(chǔ)資源都包含有一個(gè)副本管理器（RM），副本管理器能夠根據(jù)數(shù)據(jù)的請(qǐng)求情況自主的運(yùn)行數(shù)據(jù)副本的復(fù)制和刪除策略。

圖2 分布式的任務(wù)和副本復(fù)制集成體系結(jié)構(gòu)

3 在線任務(wù)調(diào)度策略

網(wǎng)格中任務(wù)調(diào)度分為在線調(diào)度方式和批處理調(diào)度方式。批處理方式的任務(wù)調(diào)度算法需要較準(zhǔn)確估計(jì)任務(wù)完成時(shí)間，但是對(duì)于數(shù)據(jù)敏感的任務(wù)，由于存儲(chǔ)資源的傳輸能力的不確定，網(wǎng)絡(luò)帶寬的不確定等因素，使得副本選擇策略運(yùn)行困難，進(jìn)而副本的傳輸時(shí)間難以通過啟發(fā)式的方法估計(jì)，另外，由于每個(gè)RS只負(fù)責(zé)部分區(qū)域用戶的任務(wù)請(qǐng)求，在單位時(shí)間內(nèi)接收的任務(wù)請(qǐng)求比較少，因此任務(wù)調(diào)度算法采用在線調(diào)度方式[11]即可，即根據(jù)當(dāng)前網(wǎng)格系統(tǒng)的性能、數(shù)據(jù)的分布情況，為每個(gè)到來的任務(wù)立刻分配資源。

數(shù)據(jù)網(wǎng)格中，在線調(diào)度方式的任務(wù)調(diào)度算法的目標(biāo)是：將任務(wù) ti調(diào)度到使其完成時(shí)間最短的資源上，即 ? mj∈ M , Min(Cij)，其中， Cij表示任務(wù) ti在資源 mj上的完成時(shí)間。 Cij= eij+ rj， eij代表任務(wù)ti在計(jì)算資源 mj上的執(zhí)行時(shí)間， eij= c puij+ n etij，即任務(wù)的執(zhí)行時(shí)間為任務(wù)所花費(fèi)的 CPU時(shí)間與任務(wù)所需數(shù)據(jù)的傳輸時(shí)間之和，其中，任務(wù) ti數(shù)據(jù)在計(jì)算資源 mj上的準(zhǔn)備時(shí)間是任務(wù)ti所需的數(shù)據(jù)集合；在以完成時(shí)間為指標(biāo)的任務(wù)調(diào)度策略中，由于網(wǎng)絡(luò)帶寬的不確定性，通常對(duì)數(shù)據(jù)傳輸時(shí)間的估計(jì)采用數(shù)據(jù)傳輸?shù)钠骄鶐挘虼甩j是傳輸數(shù)據(jù) fk到計(jì)算資源 mj的平均帶寬，但如果任務(wù)所需要的數(shù)據(jù)就在計(jì)算資源 mj內(nèi)，那么傳輸該數(shù)據(jù)的時(shí)間為0。而 rj代表任務(wù)在計(jì)算資源 mj上的等待時(shí)間，即該資源上等待隊(duì)列中所有任務(wù)的執(zhí)行時(shí)間之和。

4 副本復(fù)制的博弈模型

每個(gè)存儲(chǔ)資源中的副本管理器確定在何時(shí)，對(duì)哪一個(gè)副本進(jìn)行復(fù)制。對(duì)于前一個(gè)問題，由于計(jì)算資源的數(shù)據(jù)管理器廣播數(shù)據(jù)請(qǐng)求，因此每個(gè)存儲(chǔ)資源的副本管理器能夠統(tǒng)計(jì)固定周期內(nèi)每個(gè)數(shù)據(jù)的請(qǐng)求次數(shù)，進(jìn)而可以獲得每個(gè)數(shù)據(jù)的請(qǐng)求頻率，其中具有最高請(qǐng)求頻率的數(shù)據(jù)，被稱為熱點(diǎn)數(shù)據(jù)，它是被存儲(chǔ)資源復(fù)制的候選。當(dāng)同時(shí)滿足如下2個(gè)條件時(shí)存儲(chǔ)資源將啟動(dòng)數(shù)據(jù)復(fù)制程序：

1) 存儲(chǔ)資源中不存在該候選數(shù)據(jù)；

2) 候選數(shù)據(jù)請(qǐng)求頻率滿足某個(gè)閾值。

對(duì)于后一個(gè)問題，實(shí)際上是多個(gè)存儲(chǔ)資源之間競爭復(fù)制熱點(diǎn)數(shù)據(jù)的策略選擇問題，而博弈論[12]為解決此類非協(xié)作競爭實(shí)體的策略選擇提供了很好的思路?，F(xiàn)以2個(gè)存儲(chǔ)資源 s1、 s2競爭一個(gè)熱點(diǎn)數(shù)據(jù)為例，給出該2人博弈的正則形式：存儲(chǔ)資源s1、 s2的策略空間都是{0,1}，其中，1代表復(fù)制，0代表不復(fù)制。采用不同策略組合的 s1、 s2的效益顯示在圖3的括號(hào)內(nèi)，依據(jù)剔除嚴(yán)格劣策略的方法可知，當(dāng) s1選擇0，而 s2選擇1時(shí)，該博弈獲得Nash均衡解。當(dāng)博弈的參與者從2個(gè)存儲(chǔ)資源擴(kuò)展為m個(gè)時(shí)，可以定義這m個(gè)存儲(chǔ)資源數(shù)據(jù)復(fù)制的 Nash均衡?，F(xiàn)假設(shè)：

1) 存儲(chǔ)資源集合為 S = { s1, s2,… ,sm}，它是博弈的參與者，每個(gè)參與者的策略空間都是{0,1}，其中，1代表復(fù)制，0代表不復(fù)制；

2) 計(jì)算資源集合為 M = { m1, m2,… ,mn}；

3) 數(shù)據(jù)集合為 F = { f1, f2, … , fh}；

4) 數(shù)據(jù) fk在存儲(chǔ)資源 si的狀態(tài)為 rik∈ { 0,1}，其中，0代表不存在，1代表存在。

圖3 2人博弈的正則形式

定義1 數(shù)據(jù)復(fù)制的Nash均衡。

設(shè) m個(gè)存儲(chǔ)資源競爭熱點(diǎn)數(shù)據(jù) fk的博弈的標(biāo)準(zhǔn)式G = { s1, … , sm;u1,… ,um}，如果策略組合 { r *1k,…,r *mk}滿足對(duì)每一個(gè)存儲(chǔ)資源 si,r *ik是它針對(duì)其他m- 1 個(gè)存儲(chǔ)資源所選策略 { r *1k,… ,r *i-1k,r *i+1k,… ,r *mk}的最優(yōu)反應(yīng)策略，則稱該策略組合{r*1k,… ,r*mk}是該博弈的一個(gè)Nash均衡解。即

上述定義中效益函數(shù)iu并沒有確定。通常資源以獲取最大的資源利用率為目標(biāo)，因此每個(gè)存儲(chǔ)資源都希望計(jì)算資源盡可能從它這里訪問數(shù)據(jù)。假設(shè)計(jì)算資源im從存儲(chǔ)資源js訪問數(shù)據(jù)kf的概率為

其中，lij表示計(jì)算資源mi與存儲(chǔ)資源sj之間的帶寬，因此從存儲(chǔ)資源sj訪問數(shù)據(jù)fk的平均時(shí)延為上述概率的期望：

根據(jù)此定義可假設(shè)如果計(jì)算資源從某個(gè)存儲(chǔ)資源訪問數(shù)據(jù) fk的時(shí)延越小，那么計(jì)算資源選擇該存儲(chǔ)資源訪問數(shù)據(jù) fk的可能性越大。由于在博弈的策略選擇中，通常如果一個(gè)策略的效益越大那么該策略越好，因此取式（2）中| fk| /lij的倒數(shù)，即從存儲(chǔ)資源 sj訪問數(shù)據(jù) fk的平均時(shí)延重新定義為

令Rj= { rj1, rj2,… rjk, … ,rjh}代表存儲(chǔ)資源 sj中副本的狀態(tài)，若 rjl= 1 ，表示數(shù)據(jù) fl已存儲(chǔ)在 sj中，而 rjl= 0 表示不存在。由于存儲(chǔ)資源 sj的效益只與其存儲(chǔ)狀態(tài) Rj相關(guān)，因此存儲(chǔ)資源 sj的效益函數(shù)uj定義為

根據(jù)納什定理，若m是有限的，那么該博弈至少純?cè)谝粋€(gè) Nash均衡，均衡可能包含混合策略。對(duì)于m個(gè)人，m大于2的博弈，尋找納什均衡問題不再是一個(gè)線性復(fù)雜度的問題[13]。

5 Best-Rely算法

由于每個(gè)存儲(chǔ)資源的空間都是有限的，因此每個(gè)存儲(chǔ)資源在復(fù)制熱點(diǎn)數(shù)據(jù)之前都必須檢查其存儲(chǔ)空間是否已滿。如果其存儲(chǔ)空間已滿，那么數(shù)據(jù)替換算法如 LRU算法將被執(zhí)行以獲得足夠的存儲(chǔ)空間。根據(jù)式（3），顯然如果每個(gè)存儲(chǔ)資源的空間都是無限的，那么當(dāng)它們復(fù)制所有的數(shù)據(jù)將獲得最大的效益。然而，存儲(chǔ)空間的有限性假設(shè)使得復(fù)制一個(gè)新的副本需要滿足：

每個(gè)存儲(chǔ)資源在復(fù)制數(shù)據(jù)前，可以計(jì)算復(fù)制前后的存儲(chǔ)資源效益，如果存儲(chǔ)資源復(fù)制數(shù)據(jù)后的效益高于復(fù)制前的效益，那么該存儲(chǔ)資源就復(fù)制該數(shù)據(jù)否則不復(fù)制，稱存儲(chǔ)資源單方面選擇效益高的策略為最優(yōu)反應(yīng)（Best-Reply）策略?？梢宰C明當(dāng)每個(gè)存儲(chǔ)資源都采用最優(yōu)反應(yīng)策略，那么該策略組合是上述博弈的均衡解。

證明 對(duì)于m個(gè)存儲(chǔ)資源 { s1, …,si,…,sm}，每個(gè)存儲(chǔ)資源中副本的狀態(tài)為 { R1, … ,Ri,…,Rm}，假設(shè)在復(fù)制數(shù)據(jù) fk以及刪除一些數(shù)據(jù)后，副本的狀態(tài)變?yōu)?{ R1′, …,Ri′ ,…,Rm′}。由 Best-Reply算法的定義可知：

每個(gè)存儲(chǔ)資源的 RPM 將自動(dòng)運(yùn)行 Best-Reply算法以確定是否復(fù)制新的數(shù)據(jù)文件，算法描述見算法1。第2)～6)步統(tǒng)計(jì)所有文件的訪問頻率，并選擇訪問頻率最高的文件kf；第7)～10)步設(shè)置存儲(chǔ)資源的狀態(tài) Rj；第11)步計(jì)算存儲(chǔ)資源當(dāng)前的效益函數(shù)；第 13)～20)步假設(shè)復(fù)制文件 fk，存儲(chǔ)資源的狀態(tài)從Rj轉(zhuǎn)到 R'j，并計(jì)算新狀態(tài)下存儲(chǔ)資源的效益函數(shù)；第21)～24）步如果存儲(chǔ)資源復(fù)制文件 fk后能夠提升效益，那么就復(fù)制該文件，并刪除被替換的文件。算法Best-Reply描述如下。

算法1 存儲(chǔ)資源sj的Best-Reply算法

6 仿真實(shí)驗(yàn)

6.1 仿真平臺(tái)

為驗(yàn)證不同任務(wù)調(diào)度算法和副本復(fù)制集成策略的對(duì)任務(wù)執(zhí)行性能的影響，擬對(duì)如下的算法組合進(jìn)行仿真實(shí)驗(yàn)：

1) 在線任務(wù)調(diào)度算法，但無副本復(fù)制算法，簡記為OTS；

2) 集中式任務(wù)調(diào)度和副本復(fù)制集成策略[9]，簡記為OTS+CDR；

3) 分布式的在線任務(wù)調(diào)度算法與總復(fù)制（AR,always replica）副本復(fù)制集成策略，簡記為OTS+AR；

4)分布式在線任務(wù)調(diào)度算法與Best-Reply（BR）算法的集成策略，簡記為OTS+BR。

為此，設(shè)計(jì)并開發(fā)了一個(gè)基于GridSim[14]的網(wǎng)格任務(wù)調(diào)度仿真平臺(tái)（GJSSP, grid job scheduler simulation platform），GJSSP能夠可視化地創(chuàng)建、改變和保存網(wǎng)格仿真環(huán)境，其內(nèi)建的用戶系統(tǒng)，任務(wù)調(diào)度系統(tǒng)和副本復(fù)制管理系統(tǒng)能夠使算法的設(shè)計(jì)人員只需關(guān)心算法設(shè)計(jì)本身。GJSSP的主界面如圖4所示，其中，圓形代表一個(gè)資源，長方形代表一個(gè)路由器，每條線代表一條鏈路。這3個(gè)組件都能夠被隨意拖動(dòng)并且可以修改其屬性。在點(diǎn)擊“generator”按鈕后，GJSSP將產(chǎn)生一系列配置文件，這些配置文件將在仿真執(zhí)行前被解析并創(chuàng)建相應(yīng)的GridSim實(shí)體對(duì)象。

圖4 GJSSP主界面

仿真所需主要的配置文件及其屬性，如表1所示，其中，1代表只有一個(gè)配置文件，*表示可以由1個(gè)或多個(gè)配置文件，表中的作業(yè)屬性配置文件和文件屬性配置文件是通過工具自動(dòng)生成，主要參數(shù)如表中所示，其他配置文件是通過GJSSP的可視化界面配置。

表1 配置文件及其屬性

6.2 仿真結(jié)果

在任務(wù)的計(jì)算量和數(shù)據(jù)量都是海量的情況下，對(duì)數(shù)據(jù)復(fù)制策略影響最大的是數(shù)據(jù)文件總量與存儲(chǔ)空間總量的比例。因此，擬對(duì)該比例λ為1/10和1/100的2種情況，前者存儲(chǔ)空間相對(duì)與數(shù)據(jù)總量較小，而后者則相對(duì)較大，在如下2個(gè)指標(biāo)上進(jìn)行討論：

根據(jù)圖5和圖6，由于OTS沒有采用副本的復(fù)制策略，數(shù)據(jù)總是從某些固定存儲(chǔ)資源獲取，需要過多的數(shù)據(jù)請(qǐng)求時(shí)間，因此無論存儲(chǔ)資源是否充裕，它的平均任務(wù)用時(shí)最多。當(dāng)λ=1/100時(shí)，OTS+AR的用時(shí)最少，這主要因?yàn)橛?jì)算資源所需要的數(shù)據(jù)總是被復(fù)制到離它最近的存儲(chǔ)資源上，在存儲(chǔ)空間充裕時(shí)能夠顯著的減少數(shù)據(jù)請(qǐng)求時(shí)間，但當(dāng)λ=1/10時(shí)，總復(fù)制策略對(duì)任務(wù)的執(zhí)行起到反作用，平均完成作業(yè)時(shí)間顯著增長。另外，利用OTS+BR算法的平均任務(wù)完成時(shí)間始終比利用OTS+CDR算法多，這主要是因?yàn)樵诜抡姝h(huán)境下集中式副本復(fù)制策略在估算計(jì)算資源和網(wǎng)絡(luò)資源的性能較為精確，因此副本位置的優(yōu)化比較準(zhǔn)確，而分布式的副本復(fù)制策略只根據(jù)有限信息優(yōu)化副本位置，與全局優(yōu)化策略相比效果較差。

圖5 當(dāng)λ=1/10時(shí)的任務(wù)平均完成時(shí)間

圖6 當(dāng)λ=1/100時(shí)的任務(wù)平均完成時(shí)間

由于平均網(wǎng)絡(luò)負(fù)載越小、越穩(wěn)定，那么算法越好。根據(jù)圖7，當(dāng)λ=1/100時(shí)，OTS算法的平均網(wǎng)絡(luò)負(fù)載較高，且呈緩慢下降態(tài)勢，但是其負(fù)載仍然要優(yōu)于OTS+CDR算法和OTS+BR算法。利用OTS+BR算法的平均網(wǎng)絡(luò)負(fù)載較低但不夠穩(wěn)定。當(dāng)λ=1/10時(shí)，利用 OTS算法的平均網(wǎng)絡(luò)負(fù)載形狀變化不大，相反利用 OTS+AR算法的平均網(wǎng)絡(luò)負(fù)載形狀變化很大，即 OTS+AR算法對(duì)存儲(chǔ)資源的空間大小較為敏感，而圖7所示利用OTS+CDR與OTS+BR算法的平均網(wǎng)絡(luò)負(fù)載對(duì)于存儲(chǔ)資源空間的大小較不敏感。因此OTS+BR算法與OTS+CDR算法相比，雖然增加了一定任務(wù)平均完成時(shí)間，但是它具有更好的擴(kuò)展性，仿真結(jié)果表明它完全可以取代OTS+CDR算法。

圖7 平均網(wǎng)絡(luò)負(fù)載比較

7 結(jié)束語

論文首先提出了3層的分布式任務(wù)調(diào)度和數(shù)據(jù)管理體系結(jié)構(gòu)，在此分布式體系結(jié)構(gòu)下，對(duì)在線任務(wù)調(diào)度算法和基于博弈論的副本復(fù)制的集成策略在自行研發(fā)的網(wǎng)格仿真平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)，并同其他3類算法組合在平均任務(wù)完成時(shí)間和平均網(wǎng)絡(luò)負(fù)載2個(gè)指標(biāo)上進(jìn)行了比較。結(jié)果表明：1)僅僅在線任務(wù)調(diào)度算法不能滿足數(shù)據(jù)密集型任務(wù)對(duì)執(zhí)行性能的要求，其平均任務(wù)完成時(shí)間最高，網(wǎng)絡(luò)負(fù)載不平衡；2）總復(fù)制的副本復(fù)制算法雖然在存儲(chǔ)空間充分時(shí)具有最少的平均任務(wù)完成時(shí)間和最低的網(wǎng)絡(luò)負(fù)載，但是當(dāng)存儲(chǔ)空間較小時(shí)，上述指標(biāo)均呈現(xiàn)明顯的增長；3）分布式的 OTS+BR算法在調(diào)度效果上比集中式的OTS+CDR稍差，但其平均網(wǎng)絡(luò)負(fù)載對(duì)存儲(chǔ)空間大小不敏感，而且算法的擴(kuò)展性更好，因此完全可以替代集中式的OTS+CDR算法。

[1] SRIKUMAR V, BUYYA R, RAMAMOHANARAO K. A taxonomy of data grids for distributed data sharing, management, and processing[J].ACM Computing Surveys, 2006,38(1)∶ 3-13.

[2] BEAUMONT O, CARTER L, FERRANTE J, et al. Bandwidth-centric allocation of independent tasks on heterogeneous platforms[A]. International Parallel and Distributed Processing Symposium[C]. Marriott Marina, Fort Lauderdale, Florida, 2002. 79-88.

[3] LARS-OLOF B, HANS-ULRICH H, CESAR A. Performance issues of bandwidth reservations for grid computing[A]. 15th Symposium on Computer Architecture and High Performance Computing(SBAC-PAD'03)[C]. Sao Paulo, Brazil, 2003. 82-91.

[4] 季一木, 王汝傳. 基于粒子群的網(wǎng)格任務(wù)調(diào)度算法研究[J].通信學(xué)報(bào),2007,28(10)∶ 60-67.JI Y M, WANG R C. Study on PSO algorithm in solving grid task scheduling[J]. Journal on Communications, 2007,28(10)∶ 60-67.

[5] SIVARAMAKRISHNAN N, TAHSIN K, UMIT C, et al. Database support for data-driven scientific applications in the grid[J]. Parallel Processing Letters, 2003,13(2)∶ 245 -271.

[6] LE H. CODDINGTON P, WENDELBORN A. A data-aware resource broker for data grid[J]. Lecture Notes in Computer Science, 2004,32(22)∶ 73-82.

[7] KOSAR T. A new paradigm in data intensive computing∶ stork and the data-aware schedulers[J]. Challenges of Large Applications in Distributed Environments, 2006, 25(4)∶ 5-12.

[8] NHAN N, SANG B. Combination of replication and scheduling in data grids[J]. IJCSNS International Journal of Computer Science and Network Security, 2007,7(3)∶ 304-308.

[9] CHAKRABARTI A, SHUBHASHIS S. Scalable and distributed mechanisms for integrated scheduling and replication in data grids[J].Distributed Computing and Networking, 2008,8(2)∶ 227-238.

[10] NHAN N, DANG H, LIM S. Improvement of data grid's performance by combining job scheduling with dynamic replication strategy[A].Grid and Cooperative Computing 2007(GCC 2007)[C]. Urumchi, Xinjiang, China, 2007.513-520.

[11] MAHESWARAM M, ALI S, SIEGEL H, et al. Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems[A]. Heterogeneous Computing Workshop(HCW99)[C].1999.30-44.

[12] 施錫銓. 博弈論[M]. 上海∶ 上海財(cái)經(jīng)大學(xué)出版社, 2000.SHI X Q. Game Theory[M]. Shanghai∶ Shanghai Finance University Press,2000.

[13] CONSTANTINOS D, PAUL W, CHRISTOS H. The complexity of computing a nash equilibrium[A]. Proceedings of STOC (2006)[C].Seattle, WA, USA, 2005. 89-97.

[14] MURSHED, RAJKUMAR B, MANZUR. Gridsim∶ a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing[J]. Concurrency and Computation∶Practice and Experience (CCPE), 2002,14∶ 13-15.