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

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

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

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

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

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

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

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

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

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

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

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

　　其中作業(yè)的預(yù)測(cè)執(zhí)行時(shí)間tim越長(zhǎng)，說(shuō)明其占用資源的時(shí)間越長(zhǎng)，資源供不應(yīng)求的狀態(tài)就越嚴(yán)重，因此漲價(jià)幅度就越大。漲價(jià)影響引子ai決定了價(jià)格上漲速度的快慢。資源評(píng)估參數(shù)Ei用于對(duì)資源能力進(jìn)行評(píng)價(jià)。資源能力越強(qiáng)，則相應(yīng)的價(jià)格就越高。當(dāng)資源恢復(fù)空閑狀態(tài)后，若長(zhǎng)時(shí)間閑置，得不到作業(yè)請(qǐng)求，說(shuō)明資源供大于求。此時(shí)，根據(jù)市場(chǎng)經(jīng)濟(jì)原則，資源價(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à)格。根據(jù)市場(chǎng)經(jīng)濟(jì)機(jī)制，作業(yè)總是被調(diào)度到價(jià)格較低的資源上。通過(guò)各個(gè)資源對(duì)其價(jià)格的自主調(diào)節(jié)，以價(jià)格為杠桿，使網(wǎng)格內(nèi)資源負(fù)載達(dá)到平衡。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)數(shù)據(jù)及分析

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

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

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