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

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

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

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

1 模型的結構

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

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

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

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

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

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

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

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

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

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

　　在本模型中，通過(guò)不同的計算期望來(lái)描述用戶(hù)不同類(lèi)型的計算要求，不同的計算期望對應著(zhù)不同的資源調度算法。下面介紹本模型中的幾種資源調度策略。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　用戶(hù)指定的完成時(shí)間為T(mén)user，用戶(hù)作業(yè)在資源i上的預測執行時(shí)間為T(mén)iPRDCT，資源i上作業(yè)等待隊列時(shí)間為T(mén)iwait，用戶(hù)指定的作業(yè)計算費用為Puser，資源i的價(jià)格為Pi。

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

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

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

4 實(shí)驗數據及分析

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

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

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

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

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

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

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

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

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

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

5 結 語(yǔ)

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

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

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