一種基于計算期望的網格資源管理模型

　　隨著技術的進步和人類需求的發展，越來越多的應用領域離不開高性能計算。網格正在逐漸成為下一代高性能計算的基礎架構。在分布式環境中，資源在對不同的用戶在不同的時間有著不同的可用性和代價，優先權和目標也隨時間變化。在這樣一個分布的環境里，資源管理和應用程序調度必須具有較強的自適應性，才可以滿足資源的可用性和用戶要求的動態變化。同時它們還必須提供可擴展的、可控的、可量測的以及容易實施的管理調度策略。

　　網格資源管理模型根據用戶對計算資源的要求來進行資源調度，可以更好地利用資源。但是在一個龐大的計算環境中，所有的用戶都更傾向于更強的運算能力和更豐富的資源，而這將導致資源的不合理分配。基于市場經濟的網格資源管理模型通過經濟學原理，設定適合的市場規則和價格策略能較好地解決這個問題。

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

1 模型的結構

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

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

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

2 網格資源價格策略

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

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

　　資源根據其等待作業長度和資源空閑時間決定其價格上漲或下降的幅度。當資源由空閑狀態變為執行狀態后，提交給該資源的作業進入等待隊列。每當新作業jim進入等待隊列，資源價格上漲，資源價格上漲幅度如式(2)所示。

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

　　其中Pi為資源Ri空閑時的價格。根據市場經濟機制，作業總是被調度到價格較低的資源上。通過各個資源對其價格的自主調節，以價格為杠桿，使網格內資源負載達到平衡。

3 網格資源調度算法

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

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

　　設執行用戶計算任務所需要最低資源要求為：

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

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

　　最小作業計算費用算法概述如下：

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

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

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

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

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

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

3.2 期望為“最小作業計算時間”的資源調度算法

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

3.3 期望為“自定義價格／執行時間”的資源調度算法

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

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

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

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

4 實驗數據及分析

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

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

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

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

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

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

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

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

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

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

5 結 語

　　本文設計的一種基于計算期望的網格資源管理模型，通過計算期望來描述用戶作業的執行要求，由系統自動將計算期望映射成對網格計算資源屬性的描述，簡化了用戶在提交作業時的工作量；根據不同的計算期望，設計了不同的資源調度算法，以實現靈活的資源調度。

　　在本模型中，通過資源價格在市場內根據其供需情況的變化自主浮動，實現網格資源的負載均衡。模型的資源發現策略采用基于數據庫查詢的層次式結構，以實現查詢效率與系統開銷的折衷。采用網格模擬器Gridsim對本文所設計的模型進行仿真。實驗結果表明本模型能夠有效實現資源的負載均衡，在常規條件下的資源調度具有較高的效率。

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