摘 要： 介紹了一種基于多Agent的網(wǎng)格資源調(diào)度方法，并提出了一種負(fù)載均衡算法設(shè)計(jì)思想，以改善網(wǎng)格環(huán)境中資源分配不均的問(wèn)題。
關(guān)鍵詞: 網(wǎng)格；Agent；資源調(diào)度；負(fù)載均衡
?
網(wǎng)格是把分布在不同地理位置上的計(jì)算資源(包括高端服務(wù)器、集群系統(tǒng)、MPP系統(tǒng)大型存儲(chǔ)設(shè)備、數(shù)據(jù)庫(kù)等)通過(guò)因特網(wǎng)整合成一臺(tái)巨大的超級(jí)計(jì)算機(jī)，實(shí)現(xiàn)各種資源的全面共享。網(wǎng)格節(jié)點(diǎn)是這些網(wǎng)格計(jì)算資源的提供者。網(wǎng)格的根本特征不是它的規(guī)模，而是資源共享，消除資源孤島。因此網(wǎng)格的關(guān)鍵技術(shù)是資源調(diào)度，如何有效地調(diào)度網(wǎng)格資源將成為網(wǎng)格系統(tǒng)是否可用的關(guān)鍵問(wèn)題。
資源調(diào)度和負(fù)載均衡是分布式系統(tǒng)設(shè)計(jì)中的關(guān)鍵問(wèn)題。傳統(tǒng)的主從節(jié)構(gòu)無(wú)法避免單點(diǎn)故障、性能瓶頸等問(wèn)題，而對(duì)等網(wǎng)絡(luò)[1]P2P是一種完全分布式的計(jì)算模型，不存在這些問(wèn)題。如果一個(gè)系統(tǒng)能保持良好的負(fù)載均衡狀態(tài)，那么該系統(tǒng)可以獲得較高的吞吐量。本文首先介紹了一種基于多Agent的網(wǎng)格資源調(diào)度方法，并在此方法的基礎(chǔ)上提出了一種負(fù)載均衡算法的設(shè)計(jì)思想。
1 基于多Agent的網(wǎng)格資源調(diào)度模型
在網(wǎng)格應(yīng)用開(kāi)發(fā)過(guò)程中，采用多Agent技術(shù)能夠提高網(wǎng)格系統(tǒng)的智能性、靈活性和健壯性。Agent具有自主性，無(wú)需進(jìn)行集中的控制就可以自主決定自己的行為，也具有交互性，相互間可以進(jìn)行協(xié)作，協(xié)同完成任務(wù)。此外，可以將較復(fù)雜的任務(wù)封裝在Agent中，由多個(gè)Agent相互協(xié)作，可以完成單個(gè)Agent或其他軟件不能完成的任務(wù)。鑒于網(wǎng)格的動(dòng)態(tài)性，需要?jiǎng)討B(tài)、有自適應(yīng)能力的調(diào)度算法來(lái)對(duì)網(wǎng)格資源進(jìn)行有效調(diào)度。
1.1? 基于多Agent的網(wǎng)格系統(tǒng)節(jié)構(gòu)圖
基于多Agent的網(wǎng)格系統(tǒng)在邏輯上可以分為4個(gè)層次，如圖1所示。系統(tǒng)中，客戶(hù)端的任務(wù)主要是確定用戶(hù)的操作請(qǐng)求，資源端負(fù)責(zé)處理用戶(hù)請(qǐng)求，網(wǎng)格中間件致力于整合各種網(wǎng)格資源。網(wǎng)格資源請(qǐng)求Agent作為用戶(hù)代理，負(fù)責(zé)協(xié)調(diào)用戶(hù)與網(wǎng)格資源Agent間的交互。其目的是使用戶(hù)無(wú)需與網(wǎng)格資源直接聯(lián)系，即可更加方便地使用所需的資源。
?
用戶(hù)通過(guò)客戶(hù)端的應(yīng)用程序提出服務(wù)請(qǐng)求，激活網(wǎng)格資源請(qǐng)求Agent。網(wǎng)格資源請(qǐng)求Agent依據(jù)用戶(hù)提出的要求，在眾多的資源提供者中進(jìn)行篩選。滿(mǎn)足用戶(hù)要求的資源可能會(huì)有多個(gè)，網(wǎng)格資源請(qǐng)求Agent可以代替用戶(hù)做出最終決策，確定一個(gè)最佳資源提供者。滿(mǎn)足要求的資源也可能不存在，此時(shí)，網(wǎng)格資源請(qǐng)求Agent可以把若干個(gè)資源進(jìn)行組合，以此得到滿(mǎn)足用戶(hù)要求的資源。任務(wù)完成后，再由網(wǎng)格資源請(qǐng)求Agent將最終節(jié)果傳給客戶(hù)端。
1.2? 基于多Agent的網(wǎng)格資源調(diào)度節(jié)構(gòu)圖
網(wǎng)格的實(shí)現(xiàn)可以依賴(lài)不同的拓?fù)涔?jié)構(gòu)，將Agent引入網(wǎng)格，并采用樹(shù)型節(jié)構(gòu)作為網(wǎng)格模型[2-6]。其優(yōu)點(diǎn)是跨域搜索資源時(shí)，可以在多項(xiàng)式時(shí)間內(nèi)完成匹配。其中，底層Agent直接管理其轄區(qū)內(nèi)的資源節(jié)點(diǎn)，記錄資源信息，采用一定的資源策略來(lái)實(shí)現(xiàn)任務(wù)和資源的匹配。上層Agent主要負(fù)載任務(wù)的跨域調(diào)度。它可以將其子Agent轄區(qū)內(nèi)沒(méi)有得到匹配的任務(wù)，提交到另一個(gè)子Agent進(jìn)行匹配。
基于Agent網(wǎng)格模型中，Agent節(jié)點(diǎn)包括5個(gè)功能模塊和2種數(shù)據(jù)節(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都有任務(wù)請(qǐng)求客戶(hù)端和任務(wù)應(yīng)答客戶(hù)端,圖2是基于Agent網(wǎng)格模型下的資源調(diào)度模型，它描述了底層Agent節(jié)點(diǎn)和資源節(jié)點(diǎn)的各個(gè)模塊和模塊的工作流程。
?
在Agent接受任務(wù)到建立任務(wù)連接過(guò)程中，如果任務(wù)池中為非空，第一步從任務(wù)池中提取第i項(xiàng)任務(wù)；第二步分析第i項(xiàng)任務(wù)的資源需求；第三步由動(dòng)態(tài)平衡負(fù)載模塊(全局資源剩余率，全局任務(wù)空閑率，全局負(fù)載變化率)生成網(wǎng)格資源調(diào)度的上限；第四步調(diào)用此模塊返回匹配節(jié)果；第五步如果有匹配節(jié)果，就創(chuàng)建資源節(jié)點(diǎn)和任務(wù)請(qǐng)求節(jié)點(diǎn)間的工作流，成功通訊后斷開(kāi)本連接；最后在第十步檢測(cè)到第i項(xiàng)任務(wù)完成后，在Agent中清楚所有任務(wù)。
任務(wù)處理模塊將收到的任務(wù)放入任務(wù)等待隊(duì)列，如果任務(wù)等待隊(duì)列為非空，在第八步任務(wù)管理器從任務(wù)隊(duì)列中選取第i項(xiàng)任務(wù)運(yùn)行并更新任務(wù)狀態(tài)表匯總的狀態(tài)，第九步中若任務(wù)完成，調(diào)用任務(wù)釋放模塊與任務(wù)請(qǐng)求節(jié)點(diǎn)通訊，第十一步中若任務(wù)已經(jīng)成功歸還任務(wù)請(qǐng)求節(jié)點(diǎn)，則更新任務(wù)狀態(tài)，收回所占資源。
1.3?基于多Agent的網(wǎng)格資源管理模型下的的緊鄰算法
代理對(duì)計(jì)算資源和Web用戶(hù)是透明的，它只與自己相連的節(jié)點(diǎn)(代理)打交道，接受這些代理或者計(jì)算資源的注冊(cè)和撤銷(xiāo)[7]。如圖3所示，計(jì)算資源可以選擇某個(gè)代理進(jìn)行注冊(cè)，每個(gè)代理最終管理一組資源，響應(yīng)用戶(hù)的任務(wù)請(qǐng)求。由于可用帶寬以及主機(jī)性能等原因，各個(gè)代理的資源利用率、負(fù)載等不盡相同，可能會(huì)出現(xiàn)某些代理服務(wù)器負(fù)載過(guò)重、有些代理服務(wù)器處于輕負(fù)載運(yùn)行狀態(tài)的情況。一個(gè)代理接收到一個(gè)新的計(jì)算任務(wù)以后，如果自身負(fù)載過(guò)重，或者自身的可用資源難以滿(mǎn)足新的計(jì)算任務(wù)的要求，就會(huì)根據(jù)負(fù)載平衡算法，通過(guò)ACP(Agent Communication Protocol)把計(jì)算任務(wù)交給其他代理完成。
?
?
假定并行處理系統(tǒng)是由多個(gè)節(jié)點(diǎn)按照一定的節(jié)構(gòu)相互連接構(gòu)成的并行處理網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)只能與其直接連接的節(jié)點(diǎn)通信，計(jì)算負(fù)載也只能通過(guò)這些連接移動(dòng)。在負(fù)載平衡過(guò)程中，每個(gè)節(jié)點(diǎn)只能與其周?chē)墓?jié)點(diǎn)進(jìn)行負(fù)載交換，通過(guò)多次循環(huán)迭代實(shí)現(xiàn)系統(tǒng)的負(fù)載平衡。?
2 基于多Agent的網(wǎng)格資源調(diào)度層次模型的負(fù)載均衡算法
2.1?負(fù)載平衡算法的思想
本文設(shè)計(jì)的負(fù)載平衡算法屬于動(dòng)態(tài)平衡算法，決策取決于系統(tǒng)當(dāng)前的狀態(tài)。也就是說(shuō)，系統(tǒng)可以根據(jù)當(dāng)前的負(fù)載分布情況，對(duì)各個(gè)節(jié)點(diǎn)上的負(fù)載進(jìn)行動(dòng)態(tài)調(diào)整，使已經(jīng)分配給重載節(jié)點(diǎn)上的任務(wù)，通過(guò)通信設(shè)備，遷移到輕載的節(jié)點(diǎn)上去，從而提高系統(tǒng)的資源利用率，減小任務(wù)的平均響應(yīng)時(shí)間。
算法思想是緊鄰上限機(jī)制(Neareast Neighbor-Upper Bound)，它假定并行處理系統(tǒng)是由多個(gè)節(jié)點(diǎn)按照一定的節(jié)構(gòu)相互連接構(gòu)成的并行處理網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)只能與其直接連接的節(jié)點(diǎn)通信，計(jì)算負(fù)載也只能通過(guò)這些連接移動(dòng)。每個(gè)節(jié)點(diǎn)對(duì)于任務(wù)提交的資源要求進(jìn)行分析，得出其任務(wù)可以完成的底限；再在底限的基礎(chǔ)上適當(dāng)上浮一定比例，得到一個(gè)資源要求的上限；這樣，就有一個(gè)資源要求區(qū)間，用這個(gè)區(qū)間值在資源中進(jìn)行匹配，在所得的資源節(jié)點(diǎn)中，使用一定的資源搜索算法，進(jìn)行具體的資源定位。在負(fù)載平衡過(guò)程中，通過(guò)節(jié)點(diǎn)上限機(jī)制和緊鄰的節(jié)點(diǎn)多次循環(huán)迭代實(shí)現(xiàn)系統(tǒng)的負(fù)載平衡。
2.2?負(fù)載平衡算法的設(shè)計(jì)
當(dāng)接受某項(xiàng)任務(wù)后，網(wǎng)格的負(fù)載和吞吐量必然發(fā)生變化；不同任務(wù)引起的變化不同，對(duì)上限的影響也是不同的。任務(wù)對(duì)整個(gè)網(wǎng)格負(fù)載影響，是以接受節(jié)點(diǎn)資源能力的變化表現(xiàn)出來(lái)的。先給出2個(gè)公式：
其中，節(jié)點(diǎn)負(fù)載率(NLR)描述節(jié)點(diǎn)的當(dāng)前已耗費(fèi)的資源能力；節(jié)點(diǎn)剩余資源率(NRRR)描述節(jié)點(diǎn)的未來(lái)資源能力。為了定義上面2個(gè)概念，再引入2個(gè)概念：?jiǎn)喂?jié)點(diǎn)已使用資源(NUR)和單節(jié)點(diǎn)全部資源(NAR)。NLR與單節(jié)點(diǎn)的上限(SUB)成正向關(guān)系。
單個(gè)任務(wù)對(duì)網(wǎng)格吞吐量的影響很小，可近似看作不變。此時(shí)，網(wǎng)格中部分資源的負(fù)載增大，剩余資源減少。為使負(fù)載不繼續(xù)變大，這部分資源通過(guò)緊鄰算法將更多能力較類(lèi)似的節(jié)點(diǎn)(能力較強(qiáng)的)考慮進(jìn)來(lái)確保上限度量UB<1。
相同負(fù)載的強(qiáng)節(jié)點(diǎn)和弱節(jié)點(diǎn)的剩余資源能力是不一樣的，剩余資源能力高的節(jié)點(diǎn)對(duì)SUB調(diào)高的愿望較低；剩余資源能力低的節(jié)點(diǎn)則相反。所以，NRRR與SUB成逆向關(guān)系。于是，有下面的表達(dá)式：
其中，SUB由節(jié)點(diǎn)的資源能力在整個(gè)網(wǎng)格中的地位決定。因此，它不僅與節(jié)點(diǎn)自己的能力有關(guān)，還與網(wǎng)格資源的節(jié)構(gòu)有關(guān)。
其中,SUBS=
Ci即網(wǎng)格所有節(jié)點(diǎn)的上限之和，被稱(chēng)為網(wǎng)格動(dòng)態(tài)節(jié)點(diǎn)。它應(yīng)當(dāng)只與整個(gè)網(wǎng)表初始權(quán)值設(shè)置格的資源能力節(jié)構(gòu)有關(guān)。而網(wǎng)格的資源能力節(jié)構(gòu)是動(dòng)態(tài)變化的，它取決于很多因素:全局任務(wù)空閑率(TTFR)反映了網(wǎng)格當(dāng)前的吞吐量，全局負(fù)載變化率(TLCR)反映了全局任務(wù)資源要求的波動(dòng)速率，全局剩余資源率(TRRR) 反映了網(wǎng)格今后的能力。
綜上所述，節(jié)點(diǎn)動(dòng)態(tài)上限機(jī)制最終可以下面的形式來(lái)描述：C={f(TTFR,TLCR,TRRR,UC)}，UC為其他因素。其中TTFR，GSRR與UB成正向關(guān)系，TLCR與UB成加速關(guān)系.則有：
其中k為調(diào)整常數(shù)，將求和項(xiàng)調(diào)整為網(wǎng)格可以感知的程度，并確保UB<1。
網(wǎng)格環(huán)境中存在著多個(gè)Agent，如圖4所示。
?
??? 每個(gè)Agent周?chē)挤植剂硕鄠€(gè)節(jié)點(diǎn)。在單個(gè)Agent周?chē)墓?jié)點(diǎn)和節(jié)點(diǎn)之間通過(guò)緊鄰算法，實(shí)現(xiàn)系統(tǒng)的協(xié)調(diào)，解決節(jié)點(diǎn)和節(jié)點(diǎn)之間的負(fù)載平衡問(wèn)題。在Agent和Agent之間也通過(guò)緊鄰算法和ACP，達(dá)到網(wǎng)格資源調(diào)度的協(xié)調(diào)。在多Agent網(wǎng)格資源環(huán)境中，利用緊鄰算法實(shí)現(xiàn)了節(jié)點(diǎn)與節(jié)點(diǎn)的協(xié)調(diào)、單個(gè)Agent與單個(gè)Agent的協(xié)調(diào)，使整個(gè)網(wǎng)格環(huán)境實(shí)現(xiàn)分布式的協(xié)同。再利用上限度量的設(shè)定，最終實(shí)現(xiàn)系統(tǒng)的網(wǎng)絡(luò)負(fù)載平衡。
3?基于多Agent的負(fù)載均衡算法的優(yōu)點(diǎn)
本負(fù)載均衡算法最大的特點(diǎn)在于：根據(jù)網(wǎng)格實(shí)時(shí)負(fù)載和吞吐量等信息進(jìn)行動(dòng)態(tài)調(diào)度，節(jié)點(diǎn)與節(jié)點(diǎn)之間運(yùn)用緊鄰算法，設(shè)定上限量度，恰如其分地選擇資源；能很好地解決小任務(wù)堆積強(qiáng)節(jié)點(diǎn)的問(wèn)題；能夠?qū)崿F(xiàn)資源預(yù)留功能；可擴(kuò)展性強(qiáng)，它利用了1種兩級(jí)調(diào)度：一級(jí)調(diào)度采用動(dòng)態(tài)上限機(jī)制，二級(jí)調(diào)度可以根據(jù)不同的網(wǎng)格系統(tǒng)來(lái)靈活、透明、有效率地選擇。
本文將Agent技術(shù)引入網(wǎng)格資源管理調(diào)度，提出了1個(gè)網(wǎng)格環(huán)境下基于Agent的上限機(jī)制負(fù)載均衡的設(shè)計(jì)思想，充分發(fā)揮了Agent的智能性、自主性，并提高了網(wǎng)格資源的利用效率。本算法較大地發(fā)揮了系統(tǒng)的負(fù)載平衡能力，提高了網(wǎng)格計(jì)算能力和資源利用率。
參考文獻(xiàn)
[1]?STOICA I, MORRIS R, KARGER D, et al. A scalable peer-to-peer lookup service for internet applications[A].Processing of ACM SIGCOMM[C]. New York: ACM Press, 2001．149-160．
[2] ?LI Chun Lin，LI La Yuan．Agent framework to support computational grid[J]．The Journal of Systems and Software，2004，70(1／2)：177-187．
[3] ?LI Chun Lin，LI La Yuan．Apply agent to build grid service management[J]．Computer Applications 2003(26)：323-240．
[4] ?CAO Jun Wei，SPOONER D P．Grid load balancing using intelligent agents[J]．Future Generation Compute Systems，2005(21)：135-149．
[5] ?FREY J，TANNENHAUM T，F(xiàn)OSTER I，et a1．A computation management agent for multi—institution all grids[J]．Cluster Computer，2002，5(3)：237-246．
[6]? CAO JunWei，JARVIS S A，SAINI S，et a1．An agent—based resource management system for grid computing[J]．Scientific Programming(Special Issue on Grid Computing)，2002，10(2)：135-148．
[7]? 趙姍,胡根,周興社.基于多Agent網(wǎng)格資源管理模型的負(fù)載均衡研究[J] .微電子學(xué)與計(jì)算機(jī), 2005，22(10)：51-53.
[8] ?邸爍,鄭緯民，王鼎興，等．并行WWW服務(wù)器集群請(qǐng)求分配算法的研究[J]．軟件學(xué)報(bào),1999,10(7):713-718．