基于動(dòng)態(tài)備份的容錯(cuò)網(wǎng)格任務(wù)調(diào)度

摘要：提出了一種基于自適應(yīng)備份的網(wǎng)格容錯(cuò)任務(wù)調(diào)度算法:最高百分之k備份算法。該算法對(duì)任務(wù)的安全需求和資源的信任等級(jí)進(jìn)行匹配，在系統(tǒng)安全等級(jí)較低并且網(wǎng)絡(luò)和主機(jī)可能失效的網(wǎng)格環(huán)境中進(jìn)行容錯(cuò)任務(wù)調(diào)度。調(diào)度時(shí)，該算法根據(jù)整個(gè)網(wǎng)格系統(tǒng)的安全狀況，對(duì)具有最高安全需求的百分之k的任務(wù)進(jìn)行動(dòng)態(tài)備份，任務(wù)備份數(shù)根據(jù)系統(tǒng)安全狀況自適應(yīng)變化，并對(duì)失敗的任務(wù)重新調(diào)度。仿真結(jié)果表明，該算法可以有效提高不安全網(wǎng)格環(huán)境下的任務(wù)調(diào)度成功率，具有很好的容錯(cuò)性和可擴(kuò)展性，優(yōu)于固定備份數(shù)的網(wǎng)格任務(wù)調(diào)度算法。

關(guān)鍵詞：網(wǎng)格計(jì)算;任務(wù)調(diào)度;容錯(cuò);動(dòng)態(tài)備份

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)03－0738－03

在網(wǎng)格[1]環(huán)境中，對(duì)于安全威脅的擔(dān)憂(yōu)和對(duì)遠(yuǎn)程資源不夠信任限制了將任務(wù)調(diào)度到遠(yuǎn)程主機(jī)上。在任務(wù)調(diào)度過(guò)程中，如果一個(gè)節(jié)點(diǎn)遭受攻擊，那么它的資源從該自治域外部就有可能無(wú)法訪(fǎng)問(wèn)，調(diào)度給該節(jié)點(diǎn)的任務(wù)就有可能會(huì)產(chǎn)生延遲或失敗。目前已知的大部分網(wǎng)格任務(wù)調(diào)度算法[2~4]都忽略了網(wǎng)格安全因素，假設(shè)網(wǎng)格資源100%可靠。隨著網(wǎng)格規(guī)模的擴(kuò)大，在跨自治域的網(wǎng)格任務(wù)調(diào)度過(guò)程中，必須考慮安全性這一問(wèn)題。網(wǎng)格的動(dòng)態(tài)性使得網(wǎng)格系統(tǒng)各節(jié)點(diǎn)的特性和行為無(wú)法精確預(yù)測(cè)。隨著網(wǎng)格規(guī)模的擴(kuò)大、任務(wù)執(zhí)行時(shí)間的增長(zhǎng)，網(wǎng)格系統(tǒng)的故障率將越來(lái)越高。因此，在網(wǎng)格任務(wù)調(diào)度過(guò)程中，必須保證任務(wù)調(diào)度具有自適應(yīng)性、容錯(cuò)性[5]和可擴(kuò)展性。任務(wù)備份[6]是常用的容錯(cuò)調(diào)度方法，以保證在由于節(jié)點(diǎn)本身的故障或者網(wǎng)絡(luò)延遲而導(dǎo)致任務(wù)失敗時(shí)仍然能夠成功執(zhí)行任務(wù)，并保證任務(wù)調(diào)度的成功率保持在一個(gè)較高的水平。但是目前提出的基于備份的網(wǎng)格任務(wù)調(diào)度算法中，均使用固定數(shù)目的任務(wù)備份，無(wú)法適應(yīng)網(wǎng)格環(huán)境的動(dòng)態(tài)變化，造成在網(wǎng)格安全狀況較好時(shí)執(zhí)行過(guò)多的任務(wù)備份，而在網(wǎng)格安全狀況較差時(shí)，過(guò)少的任務(wù)備份使得任務(wù)調(diào)度的成功率較低。

1相關(guān)工作

網(wǎng)格環(huán)境在內(nèi)在本質(zhì)上是不可靠的[7，8]。文獻(xiàn)[7]提出了一個(gè)失效檢測(cè)服務(wù)和一個(gè)靈活的錯(cuò)誤處理框架作為網(wǎng)格上的容錯(cuò)機(jī)制。在網(wǎng)格環(huán)境中，很多資源的利用率很低，這些空閑的資源可以用來(lái)執(zhí)行任務(wù)備份，以保證至少有一個(gè)任務(wù)備份可以成功執(zhí)行。因此，基于備份的容錯(cuò)任務(wù)調(diào)度研究較多。文獻(xiàn)[6]提出了一個(gè)在線(xiàn)的容錯(cuò)調(diào)度策略DFTS (distributed faulttolerant scheduling)。但是DFTS使用固定的兩個(gè)備份數(shù)的策略，對(duì)于網(wǎng)格環(huán)境的變化無(wú)法作出調(diào)整。本文提出一種自適應(yīng)的備份策略，根據(jù)系統(tǒng)安全狀況的變化動(dòng)態(tài)調(diào)整備份數(shù)。與固定備份數(shù)的調(diào)度策略相比，不僅提高了任務(wù)執(zhí)行的成功率，并且減少了總的備份執(zhí)行數(shù)量，節(jié)省了資源的使用。

文獻(xiàn)[9]將信任概念集成到網(wǎng)格資源管理中，并提出了一個(gè)將安全影響集成到調(diào)度算法中的信任模型。信譽(yù)度模型是在P2P網(wǎng)格和分布式安全資源訪(fǎng)問(wèn)中使用較多的一種模型，即任一資源都有一定的信譽(yù)值，信譽(yù)值的大小反映了資源的可靠性程度。其中，有集中式信譽(yù)度模型[10]和分布式信譽(yù)度與授權(quán)模型[11]。文獻(xiàn)[12]提出了基于模糊推理的節(jié)點(diǎn)信任模型，解決了節(jié)點(diǎn)信任屬性的不確定性和模糊性問(wèn)題，增強(qiáng)了大量網(wǎng)格資源節(jié)點(diǎn)間互操作的安全性。

為了使任務(wù)調(diào)度更加有效，網(wǎng)格任務(wù)必須帶有一個(gè)安全需求(security demand，SD)，而資源提供者必須帶有一個(gè)信任等級(jí)[12](trust level，TL)。本文假設(shè)網(wǎng)格用戶(hù)在提交任務(wù)時(shí)同時(shí)提交了安全需求，并通過(guò)文獻(xiàn)[12]中的模糊算法，根據(jù)資源節(jié)點(diǎn)的歷史性能評(píng)估資源節(jié)點(diǎn)的可信度，即節(jié)點(diǎn)的信任等級(jí)。當(dāng)節(jié)點(diǎn)的信任等級(jí)滿(mǎn)足任務(wù)的安全需求時(shí)，才將任務(wù)調(diào)度到該節(jié)點(diǎn)。

文獻(xiàn)[13]提出了一種基于網(wǎng)格信任模型和信任效益函數(shù)的安全驅(qū)動(dòng)的任務(wù)調(diào)度算法，但該調(diào)度算法對(duì)于不滿(mǎn)足信任需求的任務(wù)直接拋棄。在實(shí)際的網(wǎng)格環(huán)境中，在調(diào)度事件發(fā)生時(shí)，任務(wù)的安全需求和節(jié)點(diǎn)的信任等級(jí)可能不匹配，為了提高調(diào)度算法的容錯(cuò)性，應(yīng)該延遲調(diào)度這些任務(wù)，而不是直接拋棄。本文提出的基于網(wǎng)格安全的容錯(cuò)調(diào)度算法，對(duì)于安全需求暫時(shí)無(wú)法滿(mǎn)足的任務(wù)不是直接拋棄，而是在下一輪調(diào)度時(shí)再次調(diào)度該任務(wù)，直到該任務(wù)能夠被成功執(zhí)行。這樣，提高了任務(wù)調(diào)度的成功率。

2最高百分之k備份算法

由于固定的任務(wù)備份數(shù)不能適應(yīng)網(wǎng)格安全環(huán)境的動(dòng)態(tài)變化，本文提出一種自適應(yīng)的任務(wù)備份數(shù)模型，即最高百分之k備份策略，使任務(wù)備份數(shù)隨著網(wǎng)格內(nèi)所有節(jié)點(diǎn)的信任等級(jí)的變化而相應(yīng)增減。最高百分之k備份策略將待調(diào)度任務(wù)按安全需求由高到低進(jìn)行排序，然后將其中百分之k的具有最高安全需求的任務(wù)進(jìn)行備份。假設(shè)節(jié)點(diǎn)的信任等級(jí)和系統(tǒng)的信任等級(jí)已經(jīng)由文獻(xiàn)[12]提出的模糊模型計(jì)算得出。本文將系統(tǒng)的信任等級(jí)分為五級(jí)，從高到低依次為極高、較高、中等、較低、極低，被選中任務(wù)的備份數(shù)根據(jù)系統(tǒng)安全等級(jí)進(jìn)行確定。當(dāng)系統(tǒng)的安全等級(jí)變化時(shí)，備份數(shù)也相應(yīng)變化。

為了簡(jiǎn)化調(diào)度模型，進(jìn)行如下假設(shè):a)某一應(yīng)用程序已經(jīng)被分解為若干個(gè)子任務(wù)，子任務(wù)之間相互獨(dú)立;b)任務(wù)沒(méi)有截止時(shí)間限制和優(yōu)先權(quán);c)資源的實(shí)時(shí)狀態(tài)已知，且待執(zhí)行任務(wù)在任意主機(jī)上的執(zhí)行時(shí)間已知[2];d)在同一個(gè)主機(jī)上執(zhí)行的子任務(wù)遵循FCFS(firstcome，firstserved)原則，且一個(gè)主機(jī)一次只執(zhí)行一個(gè)任務(wù)，任務(wù)一旦執(zhí)行，就不能被搶斷;e)所有網(wǎng)格系統(tǒng)組件均可能失效，失效可能在任意時(shí)間點(diǎn)發(fā)生并且最終可以恢復(fù);f)節(jié)點(diǎn)失效是互相獨(dú)立的，且失效節(jié)點(diǎn)總數(shù)不超過(guò)一個(gè)給定百分比[6];g)存在一個(gè)主調(diào)度器，且主調(diào)度器維護(hù)一個(gè)job table，其中保存各任務(wù)的運(yùn)行狀態(tài)及任務(wù)-節(jié)點(diǎn)對(duì)的相關(guān)信息。當(dāng)主調(diào)度器失效以后，備用調(diào)度器可以接管主調(diào)度器的所有工作。

2．1調(diào)度流程

設(shè)M為主機(jī)集合，M={mj|j=1，2，3，…，m}，T為任務(wù)集合，T={ti| i=1，2，3，…，n}，給出如下的算法相關(guān)參數(shù):

a)SDi，任務(wù)ti的安全需求，在用戶(hù)提交任務(wù)時(shí)由用戶(hù)指定。0＜SDi＜1，0表示最低的安全需求；1表示最高的安全需求。

b)TLj，主機(jī)mj的信任等級(jí)。0≤TLj≤1，0表示節(jié)點(diǎn)非常不安全；1表示節(jié)點(diǎn)完全可信。

c)TL，系統(tǒng)的信任等級(jí)。0≤TL≤1，0表示系統(tǒng)整體安全程度非常低，節(jié)點(diǎn)完全不可信；1表示系統(tǒng)整體安全程度非常高，節(jié)點(diǎn)完全可信。系統(tǒng)的信任等級(jí)利用文獻(xiàn)[5]中的算法計(jì)算得出。

d)replica，任務(wù)備份數(shù)。

e)k，備份任務(wù)百分比，(100/n)≤k≤100。k值計(jì)算如下:

k=max(100/n，100/eTL)

在實(shí)際調(diào)度中，根據(jù)任務(wù)隊(duì)列中的任務(wù)數(shù)對(duì)k值進(jìn)行圓整。

f)queue_max，節(jié)點(diǎn)主機(jī)允許的CPU隊(duì)列的最大長(zhǎng)度。

g)queue，節(jié)點(diǎn)主機(jī)實(shí)際的CPU運(yùn)行隊(duì)列長(zhǎng)度。

h)avail，滿(mǎn)足任務(wù)ti的信任需求并且CPU隊(duì)列不超過(guò)queue_max的主機(jī)數(shù)。

i)active，當(dāng)前活動(dòng)的備份數(shù)。

最高百分之k備份策略的調(diào)度過(guò)程如下:調(diào)度器定時(shí)對(duì)任務(wù)池中的任務(wù)進(jìn)行調(diào)度。計(jì)算所有任務(wù)的安全需求SDi、節(jié)點(diǎn)的信任等級(jí)TLj、系統(tǒng)信任等級(jí)TL和任務(wù)備份數(shù)replica，當(dāng)系統(tǒng)安全等級(jí)由極高到極低變化時(shí)， replica分別取0、1、2、3、4(實(shí)驗(yàn)結(jié)果表明，當(dāng)任務(wù)備份數(shù)大于4時(shí)，系統(tǒng)性能顯著下降)。對(duì)于任務(wù)集合中的所有任務(wù)，按照安全需求由高到低的順序進(jìn)行排序。對(duì)于安全需求最高的百分之k的任務(wù)進(jìn)行備份，每個(gè)任務(wù)的備份數(shù)為replica；對(duì)于沒(méi)有備份的任務(wù)，可以認(rèn)為其備份數(shù)為0，即replica=0。調(diào)度時(shí)，將任務(wù)調(diào)度到CPU運(yùn)行隊(duì)列沒(méi)有超出CPU隊(duì)列的最大長(zhǎng)度且滿(mǎn)足任務(wù)安全需求的信任等級(jí)最高的replica+1個(gè)節(jié)點(diǎn)上，然后從任務(wù)集合中刪除該任務(wù)。如果可供調(diào)度的主機(jī)數(shù)不夠，則將任務(wù)插入到下一次調(diào)度的任務(wù)集合中，并從當(dāng)前任務(wù)集合中刪除該任務(wù)。對(duì)剩余的任務(wù)重復(fù)上述過(guò)程，直到當(dāng)前任務(wù)集合為空。最高百分之k備份調(diào)度算法的偽代碼描述如下:

when scheduling event occurs {

compute SDi，TLj ，TL and replica

sort the tasks descendingly by its SDi

replicate the kpercent highestSDi tasks in the task set with replica replications

set replica=0 if the task is not replicated

for each task in T

schedule the task to replica+1 machines with queueSD

delete the task from T

update job table

if avail

insert the task into next scheduling tasks set

delete the task from T

update job table

end if

end for

}

該算法充分考慮了網(wǎng)格系統(tǒng)的安全狀況的動(dòng)態(tài)性。在生成每次的任務(wù)調(diào)度方案之前，均對(duì)節(jié)點(diǎn)信任等級(jí)和系統(tǒng)信任等級(jí)進(jìn)行計(jì)算，以保證任務(wù)備份數(shù)與網(wǎng)格系統(tǒng)的安全狀況相適應(yīng)。由于k值僅在[36.8，100]之間變化，對(duì)于k無(wú)法取值的[0，36.8)中，則由任務(wù)備份數(shù)replica的自適應(yīng)取值來(lái)保證整個(gè)任務(wù)調(diào)度算法的自適應(yīng)性和容錯(cuò)性。

2．2任務(wù)備份管理

運(yùn)行備份任務(wù)的節(jié)點(diǎn)定時(shí)向調(diào)度器報(bào)告自己的運(yùn)行狀態(tài)。調(diào)度器一旦接收到任務(wù)備份完成的消息，就通知所有其他正在運(yùn)行該任務(wù)備份的主機(jī)，終止該任務(wù)備份的執(zhí)行，更新job table和下一次調(diào)度的任務(wù)隊(duì)列；反之，如果調(diào)度器在一定時(shí)間內(nèi)沒(méi)有接收到某節(jié)點(diǎn)的狀態(tài)報(bào)告，則認(rèn)為該節(jié)點(diǎn)已失效。如果此時(shí)活動(dòng)的任務(wù)備份數(shù)active＜replica+1，則調(diào)度器從所有未運(yùn)行該備份任務(wù)且滿(mǎn)足任務(wù)的安全需求的節(jié)點(diǎn)中，選擇replica+1-active個(gè)CPU運(yùn)行隊(duì)列最短的節(jié)點(diǎn)，將任務(wù)備份調(diào)度到該節(jié)點(diǎn)。如果可用節(jié)點(diǎn)數(shù)不夠，則查看下一次任務(wù)集合；如果其中沒(méi)有該任務(wù)，則插入該任務(wù)。

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

3．1網(wǎng)格實(shí)例

利用SimGrid軟件包進(jìn)行調(diào)度算法的仿真。網(wǎng)格中PC、集群和超級(jí)計(jì)算機(jī)的比例分別為0.92、0.06和0.02?？傊鳈C(jī)數(shù)為6 000個(gè)，單個(gè)節(jié)點(diǎn)的主機(jī)數(shù)最多不超過(guò)32個(gè)，節(jié)點(diǎn)之間的帶寬在64 kbps~64 Mbps。主機(jī)的計(jì)算能力服從正態(tài)分布，其中PC和集群的計(jì)算能力服從區(qū)間[100，400](MFlops)上的正態(tài)分布，超級(jí)計(jì)算機(jī)的計(jì)算能力服從區(qū)間[200，600](MFlops)上的正態(tài)分布。假設(shè)PC主機(jī)具有周期可用性，而集群節(jié)點(diǎn)和超級(jí)計(jì)算機(jī)不具有周期特性。PC主機(jī)的失效率服從泊松分布，失效率為λpc，集群和超級(jí)計(jì)算機(jī)的失效率分別為λcluster和λsc。

初始的節(jié)點(diǎn)信任等級(jí)由計(jì)算機(jī)生成。其中：PC主機(jī)的信任等級(jí)服從[0，1]上的正態(tài)分布；集群主機(jī)的信任等級(jí)服從[0．4，1]上的正態(tài)分布；超級(jí)計(jì)算機(jī)的信任等級(jí)服從[0．8，1]上的均勻分布；計(jì)算任務(wù)的安全需求服從[0．2，0.9]上的均勻分布；任務(wù)的期望執(zhí)行時(shí)間滿(mǎn)足[60，160](ms)上的正態(tài)分布；任務(wù)到達(dá)率服從泊松分布；平均到達(dá)速率為λtask。

3．2實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)對(duì)比提出的最高百分之k備份策略（KPR)和固定備份數(shù)的replication minmin (Rminmin)[6]算法以及不考慮安全和容錯(cuò)的minmin[2]算法的性能，包括makespan、任務(wù)調(diào)度成功率、資源使用率和任務(wù)平均等待時(shí)間。Rminmin算法的固定備份數(shù)為2，取20次試驗(yàn)結(jié)果的平均值作為性能參數(shù)的測(cè)試結(jié)果。圖1給出了仿真實(shí)驗(yàn)各算法的性能參數(shù)對(duì)比。

3．3仿真結(jié)果分析

從圖1(a)可以看出，Rminmin算法的makespan最大，minmin算法的makespan最小。這是因?yàn)閙inmin算法不考慮網(wǎng)格安全因素，計(jì)算開(kāi)銷(xiāo)較小，且不對(duì)失敗的任務(wù)重新調(diào)度;KPR算法能夠根據(jù)網(wǎng)格安全等級(jí)的變化，動(dòng)態(tài)調(diào)整備份任務(wù)數(shù)，因此makespan也較小；固定備份數(shù)的Rminmin算法的makespan最大，這主要是由于Rminmin算法不能隨著網(wǎng)格系統(tǒng)的安全等級(jí)的變化動(dòng)態(tài)調(diào)整任務(wù)備份數(shù)，使得在網(wǎng)格安全等級(jí)較高時(shí)，執(zhí)行了較多的任務(wù)備份，造成任務(wù)隊(duì)列的延長(zhǎng)，最終增加了任務(wù)的makespan。

從圖1(b)可以看出，在主機(jī)和網(wǎng)絡(luò)資源均可能失效的網(wǎng)格環(huán)境中，KPR算法的調(diào)度成功率最高， Rminmin次之，minmin算法的調(diào)度成功率最低。KPR和Rminmin由于使用了任務(wù)備份而使得調(diào)度成功率較高，對(duì)安全需求和節(jié)點(diǎn)信任等級(jí)不匹配的任務(wù)延遲一定時(shí)間后重新調(diào)度，也提高了任務(wù)調(diào)度的成功率；minmin算法由于不重啟失敗的任務(wù)，沒(méi)有容錯(cuò)性，導(dǎo)致任務(wù)調(diào)度的成功率最低。

從圖1(c)可以看出，網(wǎng)格資源使用率由高到低分別是KPR、minmin和Rminmin算法(注:同一個(gè)任務(wù)的多個(gè)備份的執(zhí)行，只算一次網(wǎng)格資源使用)。這主要是由于在不安全網(wǎng)格環(huán)境中，任務(wù)的安全需求和節(jié)點(diǎn)信任等級(jí)的不匹配往往是暫時(shí)的，KPR算法能夠根據(jù)網(wǎng)格安全狀況的變化動(dòng)態(tài)調(diào)整任務(wù)備份數(shù)，提高了網(wǎng)格資源使用率;Rminmin算法由于任務(wù)備份數(shù)無(wú)法隨著網(wǎng)格安全環(huán)境的變化而變化，對(duì)所有任務(wù)均進(jìn)行備份，導(dǎo)致過(guò)多地執(zhí)行備份任務(wù)，網(wǎng)格資源的利用率最低。

從圖1(d)可以看出，任務(wù)平均等待時(shí)間由高到低依次為Rminmin、minmin和KPR算法。Rminmin算法由于過(guò)多地復(fù)制了任務(wù)備份數(shù)而導(dǎo)致需執(zhí)行的總?cè)蝿?wù)備份數(shù)增加較多，任務(wù)的平均等待時(shí)間也最長(zhǎng)；KPR算法增加的等待時(shí)間要小于增加的任務(wù)備份的執(zhí)行時(shí)間；Minmin算法只是簡(jiǎn)單地將短任務(wù)調(diào)度到具有最先完成時(shí)間的主機(jī)上，可能造成任務(wù)負(fù)載的不平衡，適應(yīng)性較差，總體的任務(wù)平均等待時(shí)間也較大。

綜上所述， KPR算法能夠根據(jù)網(wǎng)格安全環(huán)境的變化動(dòng)態(tài)調(diào)整任務(wù)備份數(shù)，對(duì)于安全特性變化較大的網(wǎng)格系統(tǒng)具有很強(qiáng)的適應(yīng)性。尤其是在主機(jī)和網(wǎng)絡(luò)均可能失效的情況下，對(duì)失敗的任務(wù)進(jìn)行重調(diào)度，雖然增加了一定的任務(wù)執(zhí)行時(shí)間，但是顯著提高了任務(wù)執(zhí)行的成功率，并且在大規(guī)模網(wǎng)格環(huán)境下的擴(kuò)展性能很好，可適用于大規(guī)模網(wǎng)格環(huán)境下的安全和容錯(cuò)的任務(wù)調(diào)度。

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

在互聯(lián)網(wǎng)安全越來(lái)越重要的今天，網(wǎng)格任務(wù)調(diào)度的安全和容錯(cuò)問(wèn)題也越來(lái)越重要。由于實(shí)際的網(wǎng)格節(jié)點(diǎn)存在著各種各樣的安全威脅，甚至失效，網(wǎng)格任務(wù)調(diào)度必須在保證盡快完成任務(wù)、提高系統(tǒng)吞吐率的同時(shí)，更應(yīng)該在網(wǎng)格安全環(huán)境較差、不信任節(jié)點(diǎn)較多的情況下，較好地完成任務(wù)，并且在節(jié)點(diǎn)失效時(shí)能夠重新調(diào)度失敗的任務(wù)，保證任務(wù)調(diào)度成功率保持在一個(gè)較高的水平。這是符合實(shí)際的網(wǎng)格計(jì)算環(huán)境的，也是可以達(dá)到的。本文提出的最高百分之k備份算法以較小的時(shí)間代價(jià)換取了較高的任務(wù)執(zhí)行成功率和容錯(cuò)性能，對(duì)于大規(guī)模網(wǎng)格環(huán)境下的安全和容錯(cuò)任務(wù)調(diào)度，具有一定的借鑒意義。

本文在對(duì)動(dòng)態(tài)備份算法的安全和容錯(cuò)性能研究中，假設(shè)各子任務(wù)之間相互獨(dú)立，不考慮任務(wù)之間的數(shù)據(jù)依賴(lài)關(guān)系和通信延遲。在實(shí)際的網(wǎng)格環(huán)境中，尤其是數(shù)據(jù)密集型網(wǎng)格應(yīng)用中，任務(wù)通信往往是串行的，而任務(wù)的計(jì)算往往是并行的。因此，任務(wù)的通信開(kāi)銷(xiāo)有時(shí)并不能忽略。在下一步的研究中將考慮任務(wù)之間的數(shù)據(jù)依賴(lài)和通信延遲，研究動(dòng)態(tài)備份算法調(diào)度具有數(shù)據(jù)依賴(lài)的非獨(dú)立任務(wù)時(shí)的安全性和容錯(cuò)性問(wèn)題。另外，任務(wù)備份百分比k的取值僅在[36.8，100]變化， 建立更加精確的k值計(jì)算模型也是下一步的研究方向。

參考文獻(xiàn)：

［1］FOSTER I，KESSELMAN C.The grid 2:blueprint for a new computing infrastructure [M].2nd ed.金海，袁平鵬，石柯，譯.北京:電子工業(yè)出版社，2004：112.

[2]BRAUN T D，HENSGEN D，F(xiàn)REUND R，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.

[3]DOGANA A，ZGNER F.Scheduling of a metatask with QoS requirements in heterogeneous computing systems [J].Journal of Parallel and Distributed Computing，2006，66(2):181196.

[4]羅紅，慕德俊，鄧智群，等.網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2005，22(5):1619.

[5]SONG Shanshan，HWANG K，KWOK Y K.Riskresilient heuristics and genetic algorithms for securityassured grid Job scheduling [J].IEEE Trans on Computers，2006，55(6):703719.

[6]ABAWAJY J H.Faulttolerant scheduling policy for grid computing systems[C]//Proc of IEEE International Parallel and Distributed Processing Symposium.Los Alamitos: IEEE Computer Society Press，2004:238－244. [7]HWANG S，KESSELMAN C.A flexible framework for fault tolerance in the grid[J].Journal of Grid Computing，2003，1(3):251－272.

[8]石宣化，金海，羌衛(wèi)中.通用網(wǎng)格容錯(cuò)框架研究[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2006，34(7):42－45.

[9]AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems [C]//Proc of International Conference on Parallel Processing.Los Alamitos: IEEE Computer Society Press，2002:47－54.

[10]RESNICK P，ZECKHAUSER R，F(xiàn)RIEDMAN E，et al.Reputation systems[J].Communications of the ACM，2000，43(12):45－48.

[11]吳毓毅，賀也平.關(guān)于網(wǎng)格計(jì)算授權(quán)機(jī)制的研究[J].計(jì)算機(jī)應(yīng)用研究，2005，22(8):81－83.

[12]SONG Shanshan，HWANG K.Trusted grid computing with security assurance and resource optimization [C]//Proc of the 17th International Conference on Parallel and Distributed Computing Systems.San Francisco:ISCA Press， 2004:110117.

[13]張偉哲，劉欣然，云曉春，等.信任驅(qū)動(dòng)的網(wǎng)格作業(yè)調(diào)度算法[J].通信學(xué)報(bào)，2006，27(2):73－79.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”