一種基于計算期望的網(wǎng)格資源管理模型

　　隨著技術(shù)的進步和人類需求的發(fā)展，越來越多的應(yīng)用領(lǐng)域離不開高性能計算。網(wǎng)格正在逐漸成為下一代高性能計算的基礎(chǔ)架構(gòu)。在分布式環(huán)境中，資源在對不同的用戶在不同的時間有著不同的可用性和代價，優(yōu)先權(quán)和目標也隨時間變化。在這樣一個分布的環(huán)境里，資源管理和應(yīng)用程序調(diào)度必須具有較強的自適應(yīng)性，才可以滿足資源的可用性和用戶要求的動態(tài)變化。同時它們還必須提供可擴展的、可控的、可量測的以及容易實施的管理調(diào)度策略。

　　網(wǎng)格資源管理模型根據(jù)用戶對計算資源的要求來進行資源調(diào)度，可以更好地利用資源。但是在一個龐大的計算環(huán)境中，所有的用戶都更傾向于更強的運算能力和更豐富的資源，而這將導(dǎo)致資源的不合理分配?；谑袌鼋?jīng)濟的網(wǎng)格資源管理模型通過經(jīng)濟學(xué)原理，設(shè)定適合的市場規(guī)則和價格策略能較好地解決這個問題。

　　本文在在市場經(jīng)濟模型的基礎(chǔ)上，設(shè)計了一種基于計算期望的網(wǎng)格資源管理模型。該模型通過計算期望來描述用戶的計算任務(wù)，并對其進行抽象和量化，為實現(xiàn)靈活高效的資源管理和調(diào)度提供了基礎(chǔ)；在網(wǎng)格市場的資源交易中采用可變價格策略，使網(wǎng)格資源價格根據(jù)網(wǎng)格內(nèi)資源的交易情況上下浮動，反映了網(wǎng)格內(nèi)的資源供求關(guān)系，并實現(xiàn)自適應(yīng)的負載均衡。

1 模型的結(jié)構(gòu)

　　基于計算期望的網(wǎng)格資源管理模型(簡稱計算期望模型)，主要由計算期望分析器、資源管理交易器、本地市場信息服務(wù)模塊、安全認證模塊、作業(yè)管理器、網(wǎng)格信息轉(zhuǎn)發(fā)器等部分組成。模型基本框架如圖1所示。

　　在本模型中，將網(wǎng)格計算資源描述為4種屬性的集合，記為：R=(RCPU，Rmem，Rstor，RBwidth)。4種屬性依次為：處理器計算能力、內(nèi)存的大小、存儲設(shè)備容量和網(wǎng)絡(luò)帶寬。計算期望分析器負責將用戶提出的“計算期望”轉(zhuǎn)換成對計算資源屬性相應(yīng)的描述。用戶在提交作業(yè)時，只需要對其作業(yè)運行的計算期望，以及保證作業(yè)正常運行所需要的最小資源需求進行描述。例如指定“最小作業(yè)計算費用”，“最短作業(yè)計算時間”等。記網(wǎng)格中資源的價格為P，計算期望分析器將用戶計算任務(wù)的計算期望轉(zhuǎn)換為對資源R和價格P的描述，并把任務(wù)對資源的需求描述提交到資源管理交易器。在保證作業(yè)運行所需最小資源的基礎(chǔ)上，盡量滿足用戶的計算期望。

　　資源管理交易器負責本地計算資源的管理與調(diào)度，處理本地資源在網(wǎng)格市場中相關(guān)的交易事宜，并周期性地更新本地市場信息服務(wù)模塊中關(guān)于本地計算資源與價格的信息，是本模型中的核心組件。

2 網(wǎng)格資源價格策略

　　根據(jù)市場經(jīng)濟原則，各自治域內(nèi)的資源管理交易器應(yīng)當能夠獨立地調(diào)整本自治域內(nèi)計算資源的價格。通過價格反映市場的供求關(guān)系，實現(xiàn)負載均衡。在本模型中，各計算資源根據(jù)自身被使用的狀況實現(xiàn)其價格的自主決策。

　　對于自治域內(nèi)每個獨立的計算資源Ri，由其資源提供者設(shè)定各自的漲價影響因子ai與降價影響因子bi。資源評估參數(shù)的定義如式(1)所示：

　　資源根據(jù)其等待作業(yè)長度和資源空閑時間決定其價格上漲或下降的幅度。當資源由空閑狀態(tài)變?yōu)閳?zhí)行狀態(tài)后，提交給該資源的作業(yè)進入等待隊列。每當新作業(yè)jim進入等待隊列，資源價格上漲，資源價格上漲幅度如式(2)所示。

　　其中作業(yè)的預(yù)測執(zhí)行時間tim越長，說明其占用資源的時間越長，資源供不應(yīng)求的狀態(tài)就越嚴重，因此漲價幅度就越大。漲價影響引子ai決定了價格上漲速度的快慢。資源評估參數(shù)Ei用于對資源能力進行評價。資源能力越強，則相應(yīng)的價格就越高。當資源恢復(fù)空閑狀態(tài)后，若長時間閑置，得不到作業(yè)請求，說明資源供大于求。此時，根據(jù)市場經(jīng)濟原則，資源價格下跌。從資源變?yōu)榭臻e狀態(tài)開始，每隔一個固定時間段tint發(fā)布一次資源的最新價格。經(jīng)過第n個時間段發(fā)布的資源價格如式(3)所示：

　　其中Pi為資源Ri空閑時的價格。根據(jù)市場經(jīng)濟機制，作業(yè)總是被調(diào)度到價格較低的資源上。通過各個資源對其價格的自主調(diào)節(jié)，以價格為杠桿，使網(wǎng)格內(nèi)資源負載達到平衡。

3 網(wǎng)格資源調(diào)度算法

　　在本模型中，通過不同的計算期望來描述用戶不同類型的計算要求，不同的計算期望對應(yīng)著不同的資源調(diào)度算法。下面介紹本模型中的幾種資源調(diào)度策略。

3.1 期望為“最小作業(yè)計算費用”的資源調(diào)度算法

　　設(shè)執(zhí)行用戶計算任務(wù)所需要最低資源要求為：

　　計算期望分析器從本地市場信息服務(wù)模塊中查詢到的當前本地可用資源為：

　　n為本地市場信息服務(wù)模塊中記錄的可用資源數(shù)。

　　最小作業(yè)計算費用算法概述如下：

　　步驟1 根據(jù)計算期望描述，資源管理交易器查詢本地市場信息服務(wù)模塊，選擇滿足條件的價格P最低的計算資源。

　　步驟2 資源管理交易器將選擇出的計算資源分配給用戶作業(yè)。

　　步驟3 若本自治域內(nèi)的資源無法滿足用戶計算任務(wù)的最低資源要求，則資源管理交易器將資源請求發(fā)送至本區(qū)域的信息轉(zhuǎn)發(fā)器。信息轉(zhuǎn)發(fā)器查詢其數(shù)據(jù)庫中保存的本區(qū)域內(nèi)各自治域計算資源屬性的最大值。并選擇所有滿足式(4)的自治域j，將資源請求發(fā)送至這些自治域。

　　步驟4 收到資源請求的自治域執(zhí)行步驟1，并將滿足條件的計算資源信息發(fā)送至作業(yè)提交者的資源交易管理器。

　　步驟5 若作業(yè)提交者所在區(qū)域內(nèi)所有自治域的資源都無法滿足用戶計算任務(wù)的最低資源要求，則由本區(qū)域的信息轉(zhuǎn)發(fā)器將資源請求發(fā)送至相鄰的信息轉(zhuǎn)發(fā)器。收到資源請求的信息轉(zhuǎn)發(fā)器選擇滿足式(4)的自治域，將請求轉(zhuǎn)發(fā)至這些自治域，并執(zhí)行步驟4。同時，將請求發(fā)送到與其相鄰的信息轉(zhuǎn)發(fā)器(不包括將資源請求轉(zhuǎn)發(fā)至該轉(zhuǎn)發(fā)器的資源轉(zhuǎn)發(fā)器)。重復(fù)這一過程，使資源請求在網(wǎng)格全局內(nèi)轉(zhuǎn)發(fā)。

　　步驟6 作業(yè)提交者所在的資源管理交易器在收到滿足作業(yè)最小要求的資源返回的資源信息后，對其按照價格進行排序，并按照作業(yè)的要求，選擇價格最小的一個或多個資源分配給用戶作業(yè)。并將交易契約發(fā)送至被選擇的資源。資源得知自己被選擇后，根據(jù)價格策略提升其資源價格。為了防止等待時間過長，用戶的本地資源管理交易器從將資源請求發(fā)送至本區(qū)域信息轉(zhuǎn)發(fā)器時開始計時，經(jīng)過一段規(guī)定的時間，停止查詢，若此時無滿足條件的資源信息返回，則本次查詢失敗。

3.2 期望為“最小作業(yè)計算時間”的資源調(diào)度算法

　　期望為“最小作業(yè)計算時間”的資源調(diào)度算法只需將“最小作業(yè)計算費用”資源調(diào)度算法步驟6中按照價格進行排序改為按照作業(yè)等待隊列時間丁Twait進行排序，并按照作業(yè)的要求，選擇價格最小的一個或多個資源分配給用戶作業(yè)。

3.3 期望為“自定義價格／執(zhí)行時間”的資源調(diào)度算法

　　用戶指定的完成時間為Tuser，用戶作業(yè)在資源i上的預(yù)測執(zhí)行時間為TiPRDCT，資源i上作業(yè)等待隊列時間為Tiwait，用戶指定的作業(yè)計算費用為Puser，資源i的價格為Pi。

　　當計算期望為“自定義價格／執(zhí)行時間”時，用戶作業(yè)除了要滿足作業(yè)執(zhí)行的最小資源要求以外，還需要花費小于指定金額的計算費用，或作業(yè)在規(guī)定時間內(nèi)完成。這2種算法的前5步與“最小作業(yè)計算費用”資源調(diào)度算法相同，它們的第6步簡述如下：

　　“自定義執(zhí)行時間”調(diào)度算法步驟6：作業(yè)提交者所在的資源管理交易器在收到滿足作業(yè)最小要求的資源返回的資源信息后，對其按照作業(yè)等待隊列時間Twait進行排序，選擇所有滿足式(5)的資源i，并將其結(jié)果返回給用戶，由用戶從1個或多個滿足時間約束的資源中選擇合適自己作業(yè)的資源。

　　“自定義價格”調(diào)度算法步驟6：作業(yè)提交者所在的資源管理交易器在收到滿足作業(yè)最小要求的資源返回的資源信息后，對其按照預(yù)測執(zhí)行時間為TPRDCT排序，選擇所有滿足式(6)的資源i，并將其結(jié)果返回給用戶，由用戶從1個或多個滿足時間約束的資源中選擇合適自己作業(yè)的資源。

4 實驗數(shù)據(jù)及分析

　　實驗的仿真環(huán)境為：Intel(R)Pentium(R)4 CPU2.66 GHz，512 MB DDR 400 SDRAM，Windows XP professional SP2，Java 2 SDK 1.4.2。所用的仿真軟件為Gridsim。

　　圖1給出了本文設(shè)計的基于計算期望的網(wǎng)格資源管理模型的仿真數(shù)據(jù)。固定時間為30 000個時問單位，從domain01～domain08每個自治域中各隨機抽取1個計算資源，記錄其在網(wǎng)格內(nèi)不同作業(yè)數(shù)的情況下資源的利用率。其中資源利用率為該資源在某一時間段內(nèi)處于被占用狀態(tài)的時間與總時間的比值。

　　圖2為傳統(tǒng)基于固定價格的網(wǎng)格市場經(jīng)濟模型的仿真數(shù)據(jù)。固定時間也為30 000個時間單位。從domain01～domain08每個自治域中各隨機抽取1個計算資源，對其按照價格從低到高編號。資源1價格最低，資源8價格最高。記錄其在網(wǎng)格內(nèi)不同作業(yè)數(shù)的情況下資源的利用率。其中資源利用率為該資源在某一時間段內(nèi)處于被占用狀態(tài)的時間與總時間的比值。

　　由圖2可看出在計算期望模型中，相同作業(yè)數(shù)的情況下，資源基本處于負載均衡狀態(tài)，沒有出現(xiàn)忙閑不均的情況。隨著作業(yè)數(shù)的增加，資源利用率迅速上升，在作業(yè)數(shù)為200時，各資源已處于飽和狀態(tài)。此外，資源1，2，3的利用率比較接近，資源4，5，以及資源6，7，8也有相同的情況。這是由于資源調(diào)度算法優(yōu)先選擇位于作業(yè)提交者所在網(wǎng)格區(qū)域內(nèi)資源造成的。相比之下，圖3顯示系統(tǒng)處于負載不均的狀態(tài)。這是由于模型基于固定價格策略，調(diào)度器總是將作業(yè)調(diào)度到價格低的資源上，直至該資源飽和。

　　圖4為基于固定價格的市場經(jīng)濟模型中作業(yè)執(zhí)行時間與計算期望模型中作業(yè)執(zhí)行時間的比較。設(shè)定10個作業(yè)，作業(yè)長度從10 000到50 000，調(diào)度策略為最小資源價格策略。將這10個作業(yè)分別運行于上述2種模型的模擬程序中，統(tǒng)計在系統(tǒng)內(nèi)總共運行著50，100，150，200個作業(yè)的狀態(tài)下這10個作業(yè)各自的運行時間，并去掉1個最大值和1個最小值后對剩余運行結(jié)果求平均值，得到圖中數(shù)據(jù)。

　　由圖4可知，在系統(tǒng)內(nèi)作業(yè)總數(shù)為50個的情況下，系統(tǒng)負載較輕，幾乎每個作業(yè)不用經(jīng)過長時間等待就可被執(zhí)行，因此二者的執(zhí)行時間比較接近。當系統(tǒng)內(nèi)作業(yè)總數(shù)為100個和150個時，系統(tǒng)內(nèi)負載開始加重，資源等待隊列中處于等待狀態(tài)的資源開始增多。由于固定價格的市場經(jīng)濟模型將作業(yè)優(yōu)先調(diào)度到價格低的資源上，導(dǎo)致大量作業(yè)在低價資源的作業(yè)等待隊列中堆積，增加了作業(yè)執(zhí)行前的等待時間。而計算期望模型中通過價格浮動，確保作業(yè)被相對均衡地分配到資源上，減少了資源等待隊列的長度，因此計算期望模型下作業(yè)執(zhí)行時間較短。當系統(tǒng)內(nèi)總作業(yè)數(shù)為200個時，系統(tǒng)處于飽和狀態(tài)，各資源的等待隊列都被作業(yè)占滿，因此兩個模型中作業(yè)執(zhí)行時間相差不多。

　　圖5，反映了相同的作業(yè)在網(wǎng)格內(nèi)作業(yè)數(shù)不同的情況下運行時間的差異。用來測試的作業(yè)分別為：作業(yè)1，長度為10 000；作業(yè)2，長度為25 000；作業(yè)3，長度為50 000。3個作業(yè)的調(diào)度策略都為“最小作業(yè)執(zhí)行時間”。為了不受偶然情況的影響，對每個作業(yè)運行10次，去掉其中1個最大的執(zhí)行時間和1個最小的執(zhí)行時間，對剩余的時間求平均值。

　　圖5顯示隨著作業(yè)數(shù)量的增加，相同的作業(yè)其執(zhí)行時間也隨之增加。特別是當系統(tǒng)內(nèi)的作業(yè)數(shù)在100個以上時，系統(tǒng)性能下降加快。表明此時系統(tǒng)內(nèi)處于等待隊列的作業(yè)開始增多。

　　圖6顯示在“自定義價格／執(zhí)行時間”策略下系統(tǒng)內(nèi)的作業(yè)總數(shù)和成功配到資源的作業(yè)數(shù)之間的關(guān)系。分別在系統(tǒng)內(nèi)總共有50，100，150，200個作業(yè)的情況下，隨機生成50個作業(yè)，統(tǒng)計其成功分配到資源數(shù)與總作業(yè)數(shù)的百分比。

　　從圖6可見，當系統(tǒng)內(nèi)作業(yè)數(shù)大于100時，自定義價格策略和自定義執(zhí)行時間策略的作業(yè)成功分配比率都下降的很快。這說明當系統(tǒng)內(nèi)作業(yè)數(shù)大于100時，各資源的等待作業(yè)隊列長度開始快速增加，導(dǎo)致系統(tǒng)內(nèi)資源價格上漲，作業(yè)等待時間增加，所以滿足一定的價格／最大執(zhí)行時間約束的資源數(shù)減少，導(dǎo)致資源成功分配數(shù)減少。

　　以上實驗數(shù)據(jù)說明本模型所設(shè)計的價格浮動機制，相比傳統(tǒng)基于固定價格的網(wǎng)格市場經(jīng)濟模型，能夠更加準確的反映網(wǎng)格市場內(nèi)的供求關(guān)系，實現(xiàn)網(wǎng)格內(nèi)的資源負載均衡，有著更高的調(diào)度效率。模型設(shè)計的不同的資源調(diào)度算法的調(diào)度結(jié)果，與其“計算期望”所要求的結(jié)果相吻合。“計算期望”結(jié)合相應(yīng)的調(diào)度算法，實現(xiàn)了靈活、準確的資源描述與分配，滿足了用戶個性化的計算需求，簡化了用戶的工作量，在系統(tǒng)負載不飽和的情況下，有著較高的調(diào)度效率。但是不足之處在于隨著系統(tǒng)內(nèi)作業(yè)數(shù)趨向飽和，調(diào)度效率下降較快。在系統(tǒng)飽和狀態(tài)下的調(diào)度效率還有待加強。

5 結(jié) 語

　　本文設(shè)計的一種基于計算期望的網(wǎng)格資源管理模型，通過計算期望來描述用戶作業(yè)的執(zhí)行要求，由系統(tǒng)自動將計算期望映射成對網(wǎng)格計算資源屬性的描述，簡化了用戶在提交作業(yè)時的工作量；根據(jù)不同的計算期望，設(shè)計了不同的資源調(diào)度算法，以實現(xiàn)靈活的資源調(diào)度。

　　在本模型中，通過資源價格在市場內(nèi)根據(jù)其供需情況的變化自主浮動，實現(xiàn)網(wǎng)格資源的負載均衡。模型的資源發(fā)現(xiàn)策略采用基于數(shù)據(jù)庫查詢的層次式結(jié)構(gòu)，以實現(xiàn)查詢效率與系統(tǒng)開銷的折衷。采用網(wǎng)格模擬器Gridsim對本文所設(shè)計的模型進行仿真。實驗結(jié)果表明本模型能夠有效實現(xiàn)資源的負載均衡，在常規(guī)條件下的資源調(diào)度具有較高的效率。

　　雖然本模型實現(xiàn)了資源的負載均衡，且在負載不重的情況下有較高的調(diào)度效率，但是在網(wǎng)格內(nèi)作業(yè)處于飽和狀況下資源調(diào)度性能下降較快。應(yīng)當在資源發(fā)現(xiàn)策略與資源調(diào)度策略方面做進一步的研究。