網(wǎng)格資源管理與定位

摘 要

提出了一種資源管理模型采用分布式的動(dòng)態(tài)層次結(jié)構(gòu)。網(wǎng)格中的資源之間根據(jù)通信性能進(jìn)行結(jié)構(gòu)組織，以樹(shù)型結(jié)構(gòu)組織資源。采用社區(qū)的概念來(lái)進(jìn)行網(wǎng)格資源的邏輯劃分，能夠反映網(wǎng)絡(luò)的實(shí)際拓?fù)洌梢詮馁Y源上合理分配計(jì)算任務(wù)，有目的性的選擇資源，在全局意義上進(jìn)行最佳調(diào)度。在本管理模型上的請(qǐng)求定位策略可以快速定位目標(biāo)結(jié)點(diǎn)，提高效率。

【關(guān)鍵詞】網(wǎng)格計(jì)算 資源管理 社區(qū) 定位

1 引言

網(wǎng)格（Grid）在信息學(xué)中是一種用于集成或共享地理上分布的計(jì)算機(jī)系統(tǒng)、存儲(chǔ)系統(tǒng)、通信系統(tǒng)、文件、數(shù)據(jù)庫(kù)、程序等資源，使之成為有機(jī)的整體，共同完成各種所需任務(wù)的機(jī)制。網(wǎng)格計(jì)算是解決計(jì)算、數(shù)據(jù)或存儲(chǔ)資源的短缺的問(wèn)題，實(shí)現(xiàn)高性能計(jì)算和共享異構(gòu)，提高或拓展所有計(jì)算資源的效率和利用率。但是網(wǎng)格計(jì)算環(huán)境較復(fù)雜，必須提供高效的資源管理機(jī)制，能夠快速的定位資源，提高用戶與網(wǎng)格計(jì)算環(huán)境的交互。

本文采用的資源管理模型是分布、動(dòng)態(tài)的結(jié)構(gòu)模型，在該模型下引入了分類社區(qū)的概念進(jìn)行管理和高效的查詢。該模型通過(guò)同傳統(tǒng)的網(wǎng)資源管理模型相比，在資源管理，資源的利用率上都優(yōu)于傳統(tǒng)模型，并且該模型能夠在復(fù)雜的網(wǎng)格環(huán)境中共享資源，提高工作效率。采用了資源目錄樹(shù)來(lái)組織資源，定位算法能夠快速的定位，可以解決單個(gè)資源定位請(qǐng)求和多個(gè)資源定位請(qǐng)求問(wèn)題。

2 資源管理模型

2.1 社區(qū)概念

本文在網(wǎng)格資源中引入了社區(qū)的概念，社區(qū)是網(wǎng)格用戶和管理策略的集合，可以快速實(shí)時(shí)聯(lián)系資源請(qǐng)求者和資源提供者。社區(qū)與社區(qū)之間聯(lián)通，可以進(jìn)行資源的擴(kuò)展，資源管理細(xì)粒度可以通過(guò)社區(qū)對(duì)資源策略管理。社區(qū)定義表示如下：

社區(qū)={資源集合，用戶集合，規(guī)則集合}

客體是資源集合中的成員，主體是用戶集合成員。規(guī)則集合中是規(guī)則的描述，規(guī)則描述主體和客體間的關(guān)系。每個(gè)社區(qū)都有自己的社區(qū)管理器，不同社區(qū)的管理器之間如果遵從相同的數(shù)據(jù)交換協(xié)議是可以連通的。

2.2 資源管理模型與實(shí)現(xiàn)

社區(qū)的資源管理模型是分布式的動(dòng)態(tài)層次結(jié)構(gòu)。在網(wǎng)格中可以劃分不同的社區(qū)，可以按類別、負(fù)載等進(jìn)行劃分。每個(gè)社區(qū)的管理通過(guò)局部資源管理器進(jìn)行，可以進(jìn)行資源的定位和調(diào)度。社區(qū)中的局部資源管理系統(tǒng)之間采用路由器連接構(gòu)造更大的資源管理系統(tǒng)，這樣并用戶減少通訊代價(jià)，達(dá)到負(fù)載平衡，實(shí)現(xiàn)任務(wù)調(diào)度，提高任務(wù)的處理時(shí)間和效率。社區(qū)之間的局部資源管理器中有統(tǒng)一的交互協(xié)議，局部資源管理器中鄰近結(jié)點(diǎn)的信息存儲(chǔ)在信息表內(nèi)，把整個(gè)資源連接成整體是利用信息表之間。關(guān)聯(lián)資源管理的請(qǐng)求調(diào)度分成四層：用戶層、網(wǎng)格安全層、資源管理層、資源層。用戶層主要為用戶提供接口。網(wǎng)格安全層主要負(fù)責(zé)用戶身份認(rèn)證。網(wǎng)格管理層負(fù)責(zé)用戶和資源的交互，資源定位、資源匹配、資源調(diào)度、資源監(jiān)控等操作。它的主要任務(wù)是找到作業(yè)對(duì)資源的最佳映射。資源層是資源的提供者。較高層次的組件利用較低層次組件提供的服務(wù)實(shí)現(xiàn)自身的功能。

網(wǎng)格的四層具體的資源管理的流程如下：

（1）用戶在用戶層的網(wǎng)格入口處要進(jìn)行安全身份確認(rèn)及權(quán)限確認(rèn)。

（2）用戶通過(guò)身份驗(yàn)證后，向系統(tǒng)提交作業(yè)，作業(yè)管理器接受作業(yè)。

（3）作業(yè)管理器接受的作業(yè)要進(jìn)行作業(yè)的資源狀態(tài)匹配，即同網(wǎng)格資源管理器中的網(wǎng)格信息表中的信息比較，成匹配成功后將搜集執(zhí)行結(jié)果和資源信息返回給資源管理器。

（4）控制器接受來(lái)自網(wǎng)格監(jiān)控器的作業(yè)執(zhí)行狀態(tài)匯報(bào)。

（5）最后作業(yè)執(zhí)行狀態(tài)由網(wǎng)格控制器報(bào)告給用戶。

通過(guò)同其它三類模型的對(duì)比，本模型的結(jié)構(gòu)合理，分工明確，能夠支持網(wǎng)格環(huán)境下資源的定位，提高查詢的效率，便于資源的描述。

3 資源定位算法

網(wǎng)格資源的定位是在分層動(dòng)態(tài)的管理模型下進(jìn)行的定位，資源定位的原則是以優(yōu)先定位原則，即本社區(qū)的匹配的資源可以最先定位，未匹配的請(qǐng)求資源才可以在就近的社區(qū)內(nèi)進(jìn)行擴(kuò)散，這樣資源定位的時(shí)間就會(huì)縮短，效率就會(huì)提高。我們可以設(shè)定一個(gè)誤差值，在該誤差值內(nèi)，社區(qū)內(nèi)部可以把將少數(shù)較好的結(jié)果返回給用戶的資源定位機(jī)制，不需要用戶選擇比較。

資源樹(shù)是根據(jù)網(wǎng)格中收集的資源信息建立起來(lái)。資源樹(shù)中的每一個(gè)結(jié)點(diǎn)不論結(jié)點(diǎn)本身還是子結(jié)點(diǎn)、父結(jié)點(diǎn)的相應(yīng)信息都需要被存儲(chǔ)起來(lái)；該資源樹(shù)的子樹(shù)的狀態(tài)、歷史信息、安全策略等也需要進(jìn)行保存。當(dāng)前的某一個(gè)結(jié)點(diǎn)的信息也存儲(chǔ)在父親結(jié)點(diǎn)和孩子結(jié)點(diǎn)中進(jìn)行備份，這樣可以提高了系統(tǒng)在受到?jīng)_擊時(shí)具有盡可能強(qiáng)的恢復(fù)能力，在遇到非常情況時(shí)的應(yīng)變能力。信息存儲(chǔ)、向監(jiān)控子系統(tǒng)提供系統(tǒng)數(shù)據(jù)并接受監(jiān)控子系統(tǒng)發(fā)出的命令和并處理資源的動(dòng)態(tài)變更。向調(diào)度子系統(tǒng)提供資源處理能力都是資源管理器需要處理的問(wèn)題。

結(jié)點(diǎn)基本信息的存儲(chǔ)是存在資源樹(shù)上，我們就可以進(jìn)行了資源的定位、快速的查找資源，進(jìn)行分配任務(wù)。源結(jié)點(diǎn)是發(fā)起資源查找請(qǐng)求的結(jié)點(diǎn)，目標(biāo)結(jié)點(diǎn)是符合條件的資源結(jié)點(diǎn)。從任意的資源結(jié)點(diǎn)出發(fā)，在資源樹(shù)上定位符合條件的源結(jié)點(diǎn)。我們將樹(shù)轉(zhuǎn)換成有序樹(shù)，給定目標(biāo)資源參數(shù)與參考值的大小關(guān)系，社區(qū)要把相應(yīng)資源按結(jié)構(gòu)或操作系統(tǒng)分類，為了更好的匹配資源，提高效率，每個(gè)社區(qū)建立一棵子樹(shù)，各個(gè)社區(qū)的實(shí)體之間是一個(gè)對(duì)等的。例如將網(wǎng)格上樹(shù)是以linux操作系統(tǒng)為主機(jī)建立的，在該樹(shù)下根據(jù)每一棵子樹(shù)中的結(jié)點(diǎn)的CPU使用率、作業(yè)個(gè)數(shù)、計(jì)算能力劃分多棵子樹(shù)，為了提高查找效率，子樹(shù)根據(jù)CPU使用率、作業(yè)個(gè)數(shù)、計(jì)算能力等進(jìn)行排序。可以定位三種不同的如下解：滿意解、局部最優(yōu)解和全局最優(yōu)解。

下面以計(jì)算機(jī)能力建立子樹(shù)，并排好序來(lái)說(shuō)明如何進(jìn)行查找的。資源樹(shù)形態(tài)如圖1所示，樹(shù)中的結(jié)點(diǎn)數(shù)字來(lái)表示資源的計(jì)算能力。查找條件是“計(jì)算能力不小于30的參考值”。任意選定源結(jié)點(diǎn)，假設(shè)P為源節(jié)點(diǎn)，從P出發(fā)尋找目標(biāo)結(jié)點(diǎn)，其K=40滿意解，R=31為局部最優(yōu)解，Q=30為全局最優(yōu)解。endprint

下面我們根據(jù)目標(biāo)結(jié)點(diǎn)的查找過(guò)程來(lái)分析其查找過(guò)程時(shí)間復(fù)雜度。

（1）滿意解的求解過(guò)程為：滿意解只需定位到滿足資源條件的第1個(gè)資源即可。因資源樹(shù)按計(jì)算機(jī)能力排序，根據(jù)計(jì)算能力向上聚集的原則，如果當(dāng)前結(jié)點(diǎn)的計(jì)算能力不滿足要求，根據(jù)向上匯聚原則，把查找請(qǐng)求上發(fā)給父親結(jié)點(diǎn)。設(shè)定1個(gè)查找步為查找請(qǐng)求被從一個(gè)結(jié)點(diǎn)發(fā)送到其父結(jié)點(diǎn)，若存在解，則一定在從源結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上。圖1中求解滿意解時(shí)，先在資源樹(shù)上選擇任意結(jié)點(diǎn)P，先判斷P（計(jì)算機(jī)能力為29）結(jié)點(diǎn)的參數(shù)不滿足條件，立即將查找請(qǐng)求發(fā)給父親結(jié)點(diǎn)K，父親結(jié)點(diǎn)K（40）的參數(shù)40滿足條件，返回滿意解K，滿意解的查找過(guò)程結(jié)束。這種方法的優(yōu)點(diǎn)是簡(jiǎn)單，可以快速找到匹配結(jié)果，缺點(diǎn)是有可能不是最佳的結(jié)果

最好的情況：查找步數(shù)目為0，是源結(jié)點(diǎn)本身的參數(shù)就滿足條件。

最壞的情況：查找過(guò)程要從資源樹(shù)最底層結(jié)點(diǎn)進(jìn)行到根結(jié)點(diǎn)，查找步數(shù)為資源樹(shù)的深度log（N），因此其時(shí)間復(fù)雜度為O（log（N）），平均情況下的時(shí)間復(fù)雜度也為O（log（N））。

（2）局部最優(yōu)解的求解過(guò)程為：先找到滿意解，在滿意解所在結(jié)點(diǎn)上的資源子樹(shù)中的最優(yōu)解。任何一個(gè)結(jié)點(diǎn)的計(jì)算能力參數(shù)不小于其所有子結(jié)點(diǎn)的計(jì)算能力，因?yàn)橘Y源樹(shù)的計(jì)算能力有向上聚集原則。孩子結(jié)點(diǎn)的信息都記錄在子樹(shù)的根結(jié)點(diǎn)上，可以通過(guò)查找根結(jié)點(diǎn)查找它另一個(gè)孩子，看是否滿足匹配條件。不滿足匹配條件，則子樹(shù)的根就是局部最優(yōu)解。滿足匹配條件，把該孩子結(jié)點(diǎn)當(dāng)作下一層子樹(shù)的根。在依次執(zhí)行過(guò)程（1），用（2）來(lái)判斷。圖1中求解時(shí)，在找到滿意解S后，在K上維護(hù)的資源子樹(shù)中查找與30最近的且不小于30的結(jié)點(diǎn)，在（29，31，25，26）中查找到31，返回結(jié)點(diǎn)R，查找過(guò)程結(jié)束。

最壞的情況：時(shí)間復(fù)雜度為2×O（Log（N））。

（3）局最優(yōu)解的求解過(guò)程：先查找需求沿資源樹(shù)向上發(fā)送到根結(jié)點(diǎn)，再在根結(jié)點(diǎn)上的資源樹(shù)中尋找最優(yōu)解。圖1中，從p結(jié)點(diǎn)開(kāi)始查找需求，沒(méi)有滿足條件的向上發(fā)送直到根結(jié)點(diǎn)，再在資源樹(shù)的根結(jié)點(diǎn)中查找與30最近而且不小于30的結(jié)點(diǎn)，在（70，40，50，29，31，30，40，25，26，15，15）中查找到30，返回結(jié)點(diǎn)Q，查找過(guò)程結(jié)束。

平均時(shí)間復(fù)雜度：2×O（Log（N））。

參考文獻(xiàn)

[1]王良，劉瀟，賈宇潔.基于收益率門檻限制考慮的網(wǎng)格資源拍賣問(wèn)題[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2017（07）.

[2]張相斌，李硯硯.基于無(wú)標(biāo)度網(wǎng)絡(luò)的制造網(wǎng)格資源配置仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2015（02）.

[3]肖迎春，王漢武，李夢(mèng)雄.基于混合組合雙向拍賣的網(wǎng)格資源分配方案[J].計(jì)算機(jī)科學(xué)，2014（05）.

[4]于帆，秦龍.多Agent在政府采購(gòu)系統(tǒng)中的應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2011（04）.

作者簡(jiǎn)介

劉磊（1975-），女，碩士學(xué)位。副教授。主要研究領(lǐng)域?yàn)榫W(wǎng)格計(jì)算。

作者單位

吉林建筑大學(xué)城建學(xué)院 吉林省長(zhǎng)春市 130111endprint