網格資源管理與定位

摘 要

提出了一種資源管理模型采用分布式的動態層次結構。網格中的資源之間根據通信性能進行結構組織，以樹型結構組織資源。采用社區的概念來進行網格資源的邏輯劃分，能夠反映網絡的實際拓撲，可以從資源上合理分配計算任務，有目的性的選擇資源，在全局意義上進行最佳調度。在本管理模型上的請求定位策略可以快速定位目標結點，提高效率。

【關鍵詞】網格計算 資源管理 社區 定位

1 引言

網格（Grid）在信息學中是一種用于集成或共享地理上分布的計算機系統、存儲系統、通信系統、文件、數據庫、程序等資源，使之成為有機的整體，共同完成各種所需任務的機制。網格計算是解決計算、數據或存儲資源的短缺的問題，實現高性能計算和共享異構，提高或拓展所有計算資源的效率和利用率。但是網格計算環境較復雜，必須提供高效的資源管理機制，能夠快速的定位資源，提高用戶與網格計算環境的交互。

本文采用的資源管理模型是分布、動態的結構模型，在該模型下引入了分類社區的概念進行管理和高效的查詢。該模型通過同傳統的網資源管理模型相比，在資源管理，資源的利用率上都優于傳統模型，并且該模型能夠在復雜的網格環境中共享資源，提高工作效率。采用了資源目錄樹來組織資源，定位算法能夠快速的定位，可以解決單個資源定位請求和多個資源定位請求問題。

2 資源管理模型

2.1 社區概念

本文在網格資源中引入了社區的概念，社區是網格用戶和管理策略的集合，可以快速實時聯系資源請求者和資源提供者。社區與社區之間聯通，可以進行資源的擴展，資源管理細粒度可以通過社區對資源策略管理。社區定義表示如下：

社區={資源集合，用戶集合，規則集合}

客體是資源集合中的成員，主體是用戶集合成員。規則集合中是規則的描述，規則描述主體和客體間的關系。每個社區都有自己的社區管理器，不同社區的管理器之間如果遵從相同的數據交換協議是可以連通的。

2.2 資源管理模型與實現

社區的資源管理模型是分布式的動態層次結構。在網格中可以劃分不同的社區，可以按類別、負載等進行劃分。每個社區的管理通過局部資源管理器進行，可以進行資源的定位和調度。社區中的局部資源管理系統之間采用路由器連接構造更大的資源管理系統，這樣并用戶減少通訊代價，達到負載平衡，實現任務調度，提高任務的處理時間和效率。社區之間的局部資源管理器中有統一的交互協議，局部資源管理器中鄰近結點的信息存儲在信息表內，把整個資源連接成整體是利用信息表之間。關聯資源管理的請求調度分成四層：用戶層、網格安全層、資源管理層、資源層。用戶層主要為用戶提供接口。網格安全層主要負責用戶身份認證。網格管理層負責用戶和資源的交互，資源定位、資源匹配、資源調度、資源監控等操作。它的主要任務是找到作業對資源的最佳映射。資源層是資源的提供者。較高層次的組件利用較低層次組件提供的服務實現自身的功能。

網格的四層具體的資源管理的流程如下：

（1）用戶在用戶層的網格入口處要進行安全身份確認及權限確認。

（2）用戶通過身份驗證后，向系統提交作業，作業管理器接受作業。

（3）作業管理器接受的作業要進行作業的資源狀態匹配，即同網格資源管理器中的網格信息表中的信息比較，成匹配成功后將搜集執行結果和資源信息返回給資源管理器。

（4）控制器接受來自網格監控器的作業執行狀態匯報。

（5）最后作業執行狀態由網格控制器報告給用戶。

通過同其它三類模型的對比，本模型的結構合理，分工明確，能夠支持網格環境下資源的定位，提高查詢的效率，便于資源的描述。

3 資源定位算法

網格資源的定位是在分層動態的管理模型下進行的定位，資源定位的原則是以優先定位原則，即本社區的匹配的資源可以最先定位，未匹配的請求資源才可以在就近的社區內進行擴散，這樣資源定位的時間就會縮短，效率就會提高。我們可以設定一個誤差值，在該誤差值內，社區內部可以把將少數較好的結果返回給用戶的資源定位機制，不需要用戶選擇比較。

資源樹是根據網格中收集的資源信息建立起來。資源樹中的每一個結點不論結點本身還是子結點、父結點的相應信息都需要被存儲起來；該資源樹的子樹的狀態、歷史信息、安全策略等也需要進行保存。當前的某一個結點的信息也存儲在父親結點和孩子結點中進行備份，這樣可以提高了系統在受到沖擊時具有盡可能強的恢復能力，在遇到非常情況時的應變能力。信息存儲、向監控子系統提供系統數據并接受監控子系統發出的命令和并處理資源的動態變更。向調度子系統提供資源處理能力都是資源管理器需要處理的問題。

結點基本信息的存儲是存在資源樹上，我們就可以進行了資源的定位、快速的查找資源，進行分配任務。源結點是發起資源查找請求的結點，目標結點是符合條件的資源結點。從任意的資源結點出發，在資源樹上定位符合條件的源結點。我們將樹轉換成有序樹，給定目標資源參數與參考值的大小關系，社區要把相應資源按結構或操作系統分類，為了更好的匹配資源，提高效率，每個社區建立一棵子樹，各個社區的實體之間是一個對等的。例如將網格上樹是以linux操作系統為主機建立的，在該樹下根據每一棵子樹中的結點的CPU使用率、作業個數、計算能力劃分多棵子樹，為了提高查找效率，子樹根據CPU使用率、作業個數、計算能力等進行排序。可以定位三種不同的如下解：滿意解、局部最優解和全局最優解。

下面以計算機能力建立子樹，并排好序來說明如何進行查找的。資源樹形態如圖1所示，樹中的結點數字來表示資源的計算能力。查找條件是“計算能力不小于30的參考值”。任意選定源結點，假設P為源節點，從P出發尋找目標結點，其K=40滿意解，R=31為局部最優解，Q=30為全局最優解。endprint

下面我們根據目標結點的查找過程來分析其查找過程時間復雜度。

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

最好的情況：查找步數目為0，是源結點本身的參數就滿足條件。

最壞的情況：查找過程要從資源樹最底層結點進行到根結點，查找步數為資源樹的深度log（N），因此其時間復雜度為O（log（N）），平均情況下的時間復雜度也為O（log（N））。

（2）局部最優解的求解過程為：先找到滿意解，在滿意解所在結點上的資源子樹中的最優解。任何一個結點的計算能力參數不小于其所有子結點的計算能力，因為資源樹的計算能力有向上聚集原則。孩子結點的信息都記錄在子樹的根結點上，可以通過查找根結點查找它另一個孩子，看是否滿足匹配條件。不滿足匹配條件，則子樹的根就是局部最優解。滿足匹配條件，把該孩子結點當作下一層子樹的根。在依次執行過程（1），用（2）來判斷。圖1中求解時，在找到滿意解S后，在K上維護的資源子樹中查找與30最近的且不小于30的結點，在（29，31，25，26）中查找到31，返回結點R，查找過程結束。

最壞的情況：時間復雜度為2×O（Log（N））。

（3）局最優解的求解過程：先查找需求沿資源樹向上發送到根結點，再在根結點上的資源樹中尋找最優解。圖1中，從p結點開始查找需求，沒有滿足條件的向上發送直到根結點，再在資源樹的根結點中查找與30最近而且不小于30的結點，在（70，40，50，29，31，30，40，25，26，15，15）中查找到30，返回結點Q，查找過程結束。

平均時間復雜度：2×O（Log（N））。

參考文獻

[1]王良，劉瀟，賈宇潔.基于收益率門檻限制考慮的網格資源拍賣問題[J].計算機系統應用，2017（07）.

[2]張相斌，李硯硯.基于無標度網絡的制造網格資源配置仿真研究[J].系統仿真學報，2015（02）.

[3]肖迎春，王漢武，李夢雄.基于混合組合雙向拍賣的網格資源分配方案[J].計算機科學，2014（05）.

[4]于帆，秦龍.多Agent在政府采購系統中的應用研究[J].計算機與數字工程，2011（04）.

作者簡介

劉磊（1975-），女，碩士學位。副教授。主要研究領域為網格計算。

作者單位

吉林建筑大學城建學院 吉林省長春市 130111endprint