李 昊，謝中江，侯哲生

(1.吉林師范大學(xué)計(jì)算機(jī)學(xué)院，吉林四平136000;2.吉林凱賽生物技術(shù)有限公司，吉林吉林132021;3.吉林化工學(xué)院機(jī)電工程學(xué)院，吉林吉林132022)

網(wǎng)格計(jì)算不同于常規(guī)分布式計(jì)算，網(wǎng)格環(huán)境的異構(gòu)性和復(fù)雜性使得資源分配面臨很多不確定因素的影響，為了進(jìn)行最優(yōu)的資源分配，Martino等人提出了一些基于最優(yōu)化理論的任務(wù)調(diào)度算法，比如依據(jù)遺傳算法［1-3］、蟻群算法［4-6］、函數(shù)構(gòu)造法［7-9］等，這些算法從不同角度對(duì)任務(wù)調(diào)度最優(yōu)解進(jìn)行求解，均取得較好效果.在對(duì)任務(wù)進(jìn)行資源分配的過(guò)程中，資源的狀態(tài)并非一成不變的，一個(gè)有效的任務(wù)調(diào)度算法，應(yīng)該有效利用資源預(yù)報(bào)系統(tǒng)，對(duì)分配決策進(jìn)行及時(shí)調(diào)整.網(wǎng)格計(jì)算中可以應(yīng)用 NWS［10］、RPS［11］等基于時(shí)間序列的資源預(yù)報(bào)系統(tǒng)進(jìn)行資源狀態(tài)的實(shí)時(shí)預(yù)報(bào)及分析.基于貝葉斯決策的網(wǎng)格計(jì)算資源分配算法正是應(yīng)用了資源的預(yù)報(bào)和分析，將完全不確定型決策引入到任務(wù)調(diào)度算法中，更好的實(shí)現(xiàn)負(fù)載平衡和用戶QoS要求.

1 基于貝葉斯決策的決策模型

對(duì)用戶任務(wù)分配網(wǎng)格資源，可以看成是完全不確定型決策問(wèn)題，網(wǎng)格計(jì)算的主要特點(diǎn)是網(wǎng)格結(jié)構(gòu)的異構(gòu)性、網(wǎng)格服務(wù)質(zhì)量的不確定性，當(dāng)用戶提交任務(wù)，任務(wù)運(yùn)行情況取決于資源分配算法的優(yōu)劣，當(dāng)用戶任務(wù)有明確的完成時(shí)間要求時(shí)，資源分配不當(dāng)會(huì)帶來(lái)一定的風(fēng)險(xiǎn).在分配決策過(guò)程中可能會(huì)出現(xiàn)多種無(wú)法預(yù)料的狀態(tài)，這些事件出現(xiàn)的概率估計(jì)的正確程度直接影響到?jīng)Q策中收益期望值.為了更好的進(jìn)行決策，在條件許可的情況下，可以進(jìn)一步補(bǔ)充一些新的信息.補(bǔ)充信息可以通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)以及網(wǎng)格應(yīng)用程序執(zhí)行性能監(jiān)控和預(yù)報(bào)系統(tǒng)獲得.獲得新信息后，可以根據(jù)這些補(bǔ)充信息修正原來(lái)狀態(tài)時(shí)間出現(xiàn)的概率，并利用修正的概率分布重新進(jìn)行決策.由于這種概率修正主要根據(jù)貝葉斯(Bayes)定理進(jìn)行，故稱這種決策為貝葉斯決策.

1.1 分配算法的步驟

基于貝葉斯決策的網(wǎng)格計(jì)算資源分配算法通常分為3步進(jìn)行.

1.1.1 根據(jù)先驗(yàn)概率進(jìn)行決策

網(wǎng)格資源分配算法首先根據(jù)以往情況及經(jīng)驗(yàn)對(duì)這些事件出現(xiàn)的概率進(jìn)行估計(jì)，即得出先驗(yàn)概率，然后依據(jù)先驗(yàn)概率分布及期望值準(zhǔn)則做出決策，選擇出最優(yōu)方案，并得出相應(yīng)最優(yōu)期望值，記為EMV*(先).這也是多種任務(wù)調(diào)度優(yōu)化算法的調(diào)度依據(jù)部分，由此得到的調(diào)度決策是本次用戶任務(wù)調(diào)度的基礎(chǔ).

1.1.2 預(yù)驗(yàn)分析

用戶任務(wù)開(kāi)始調(diào)度，分配資源進(jìn)行計(jì)算，資源的性能狀態(tài)和負(fù)載開(kāi)始變化，依據(jù)之前信息的調(diào)度算法將無(wú)法適應(yīng)新的變化，此時(shí)需要及時(shí)補(bǔ)充新的信息，在NWS等系統(tǒng)中，分布在資源上的sensor將周期返回狀態(tài)信息，并進(jìn)行資源預(yù)報(bào).在補(bǔ)充新信息之前，對(duì)補(bǔ)充新信息是否合算做出分析，從而決定是否補(bǔ)充新信息.

1.1.3 后驗(yàn)分析

根據(jù)獲得的新信息，對(duì)先驗(yàn)概率分布進(jìn)行修正，得到后驗(yàn)概率分布，在此基礎(chǔ)上做出決策，并計(jì)算出補(bǔ)充信息的價(jià)值.

1.2 分配算法的收益分析

因?yàn)樾阅鼙O(jiān)控和預(yù)報(bào)系統(tǒng)的預(yù)報(bào)準(zhǔn)確程度以及本身就消耗掉的資源都是我們要考慮的因素.在Nimord/G［12］等基于經(jīng)濟(jì)學(xué)資源分配和任務(wù)調(diào)度系統(tǒng)中，補(bǔ)充新信息意味著額外的費(fèi)用開(kāi)銷，采用了新信息則要求有明顯的收益.下面給出收益分析的具體方法.

1.2.1 確定已有的資源狀態(tài)θi，給出資源系統(tǒng)對(duì)應(yīng)狀態(tài)出現(xiàn)的概率值.根據(jù)當(dāng)前狀態(tài)進(jìn)行最優(yōu)調(diào)度算法的計(jì)算，確定調(diào)度方案dj在每種資源狀態(tài)θi的效益值uij，根據(jù)期望值準(zhǔn)則，計(jì)算各方案效益期望值:

相應(yīng)最優(yōu)方案及期望值

1.2.2 接下來(lái)的預(yù)驗(yàn)分析中，要估算出完全信息的價(jià)值(任何信息的價(jià)值均不會(huì)超過(guò)完全信息的價(jià)值)，并以它作為標(biāo)準(zhǔn).當(dāng)完全信息預(yù)報(bào)出現(xiàn)θk狀態(tài)時(shí)，問(wèn)題變成確定性決策問(wèn)題.最優(yōu)方案顯然應(yīng)由下式確定:

在完全信息下，決策所能獲得的最大收益期望值:

EPPI和EMV*(先)的差額即由于理想化的預(yù)報(bào)資源狀態(tài)，而即使調(diào)整調(diào)度策略而帶來(lái)的收益值，定義為完全信息的價(jià)值，記為EVPI:

1.2.3 很顯然，準(zhǔn)確的預(yù)知資源接下來(lái)的狀態(tài)是不可能的，調(diào)度算法只能根據(jù)預(yù)報(bào)系統(tǒng)返回的狀態(tài)信息或者預(yù)報(bào)信息對(duì)之前的信息進(jìn)行修正.通常，補(bǔ)充的新信息是通過(guò)對(duì)x1、x2、……、xs共s個(gè)狀態(tài)進(jìn)行調(diào)查、實(shí)驗(yàn)，預(yù)報(bào)其中哪種情況將出現(xiàn)，同時(shí)通過(guò)資料獲取條件概率P(xi|θj)，即實(shí)際出現(xiàn)狀態(tài)θj而預(yù)報(bào)xj的概率.

在已知先驗(yàn)概率 p(θi)(i=1，2，…，m)及條件概率 P(xi| θj)(i=1，2，…，s;j=1，2，…，m)的基礎(chǔ)上，利用貝葉斯公式可計(jì)算出修正概率，即后驗(yàn)概率:

根據(jù)計(jì)算的后驗(yàn)概率，可預(yù)先做出決策的框架.假設(shè)補(bǔ)充信息預(yù)報(bào)將出現(xiàn)xk狀態(tài)，則用后驗(yàn)修正概率分布 P(θi|xk)(j=1，2，…，m)，計(jì)算各方案的期望收益值，并依據(jù)期望值準(zhǔn)則進(jìn)行決策，得

一旦得到補(bǔ)充信息預(yù)報(bào)，即可按上述方式進(jìn)行決策.需要注意的是，補(bǔ)充信息通常具有不確定性，因而，這樣的信息是不完全的，或說(shuō)不是絕對(duì)準(zhǔn)確的，因此，與完全信息相比，補(bǔ)充信息的價(jià)值不會(huì)大于完全信息的價(jià)值.

2 算法實(shí)現(xiàn)與分析

在文獻(xiàn)［13］中，已經(jīng)實(shí)現(xiàn)了結(jié)合網(wǎng)絡(luò)資源預(yù)報(bào)的網(wǎng)絡(luò)資源分配算法，采用NWS進(jìn)行網(wǎng)絡(luò)資源預(yù)報(bào).在仿真試驗(yàn)中，假設(shè)用戶任務(wù)deadline為3個(gè)時(shí)間單位，網(wǎng)格計(jì)算資源的可用性將決定用戶任務(wù)的完成情況，如果任務(wù)順利完成，產(chǎn)生效益5萬(wàn)元，不能完成將損失1萬(wàn)元，延遲運(yùn)行，每時(shí)間單位損失0.2萬(wàn)元.根據(jù)以往經(jīng)驗(yàn)，資源可用概率為30%.在該算法中，采用資源可用性預(yù)報(bào)，對(duì)資源可用的預(yù)報(bào)準(zhǔn)確率為80%，對(duì)資源不可用的預(yù)報(bào)準(zhǔn)確率為90%，預(yù)報(bào)需要支出0.08萬(wàn)元.

這里對(duì)100個(gè)用戶任務(wù)進(jìn)行隨機(jī)模擬，得出未采用貝葉斯決策和采用貝葉斯決策平均效益值，算法運(yùn)行結(jié)果如圖1所示.

可以看出，采用基于經(jīng)驗(yàn)期望值的網(wǎng)格任務(wù)調(diào)度算法，平均效益值(F1)要低于采用了貝葉斯決策的平均效益值(F2).而兩者的差值大于預(yù)報(bào)支出費(fèi)用，表明可以采用資源預(yù)報(bào)系統(tǒng)，提高決策的準(zhǔn)確性.

圖1 平均效益值計(jì)算結(jié)果

3 結(jié) 論

網(wǎng)格計(jì)算中任務(wù)分配，根據(jù)貝葉斯決策可以提高調(diào)度算法的平均效益值.在資源調(diào)度的過(guò)程中，如何增強(qiáng)資源狀態(tài)預(yù)報(bào)的準(zhǔn)確性，降低資源預(yù)報(bào)的費(fèi)用，是提高該算法優(yōu)越性需要下一步進(jìn)行的工作.

［1］MARTINO D V.Sub optimal scheduling in a GRID using genetic algorithms［A］.Parallel and Distributed Processing Symposium［C］.2003，22-26.

［2］SONG S，HWANG K，KWOK Y K.Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling［A］.Com-puters，IEEE Trcmsactions［C］.2006，703-719.

［3］林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法［J］.計(jì)算機(jī)研究與發(fā)展，2004，14(12):2195-2199.

［4］XU Z H，HOU X D，SUN J Z.Ant algorithm-based task scheduling in grid computing［A］.Electrical and Computer Engineering，2003.IEEE CCECE 2003［C］.2003，1107-1110.

［5］YAN H，SHEN X Q，LI X，et al.An improved ant algorithm for job scheduling in grid computing［A］.Machine Learning and Cybernet-ics［C］.2005，2957-2961.

［6］許智宏，孫濟(jì)洲.用螞蟻算法進(jìn)行網(wǎng)格任務(wù)調(diào)度的研究［J］.計(jì)算機(jī)應(yīng)用，2005，25(10):2236-2237.

［7］WANG T，ZHOU X S，LIU Q R，et al.OD:a general resource sched-uling algorithm for computational grid ［A］.Computer and Computa-tional Sciences，IMSCCS ＇06［C］.2006，644-647.

［8］王樹(shù)鵬，云曉春，余翔湛.基于生存性和 Makespan的多目標(biāo)任務(wù)調(diào)度算法研究［J］.通信學(xué)報(bào)，2006，27(2):42-49.

［9］季一木，王汝傳.基于粒子群的網(wǎng)格任務(wù)調(diào)度算法研究［J］.通信學(xué)報(bào)，2007，28(10):60-66.

［10］Wolski R，Spring N，Hayes J.The Network Weather Service:A Distributed Resource Performance Forecasting Service for Metacom-puting［J］.Journal of Future Generation Computing Systems，1999，15(5/6):757-768.

［11］Peter A.Dinda Hallaron D R O.Host Load Prediction Using Linear Models［J］.Cluster Computing，2000，3(4):265-280.

［12］Buyya R.Nimrod/G Problem Solving Environment and Computational Economics.Grid Computing Environments Community Practice(CP)Document［M］.Global Grid Forum(GGF)/First GGF Workshop，Amsterdam，the Netherlands，2001.

［13］武秀川，李昊，鞠九濱.基于計(jì)算經(jīng)濟(jì)模型改善網(wǎng)格資源分發(fā)和發(fā)現(xiàn)的性能［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41(10):64-66.