一種基于計(jì)算期望的網(wǎng)格資源管理模型
隨著技術(shù)的進(jìn)步和人類(lèi)需求的發(fā)展,越來(lái)越多的應(yīng)用領(lǐng)域離不開(kāi)高性能計(jì)算。網(wǎng)格正在逐漸成為下一代高性能計(jì)算的基礎(chǔ)架構(gòu)。在分布式環(huán)境中,資源在對(duì)不同的用戶(hù)在不同的時(shí)間有著不同的可用性和代價(jià),優(yōu)先權(quán)和目標(biāo)也隨時(shí)間變化。在這樣一個(gè)分布的環(huán)境里,資源管理和應(yīng)用程序調(diào)度必須具有較強(qiáng)的自適應(yīng)性,才可以滿(mǎn)足資源的可用性和用戶(hù)要求的動(dòng)態(tài)變化。同時(shí)它們還必須提供可擴(kuò)展的、可控的、可量測(cè)的以及容易實(shí)施的管理調(diào)度策略。
本文引用地址:http://m.butianyuan.cn/article/89102.htm網(wǎng)格資源管理模型根據(jù)用戶(hù)對(duì)計(jì)算資源的要求來(lái)進(jìn)行資源調(diào)度,可以更好地利用資源。但是在一個(gè)龐大的計(jì)算環(huán)境中,所有的用戶(hù)都更傾向于更強(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)描述用戶(hù)的計(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)稱(chēng)計(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é)將用戶(hù)提出的“計(jì)算期望”轉(zhuǎn)換成對(duì)計(jì)算資源屬性相應(yīng)的描述。用戶(hù)在提交作業(yè)時(shí),只需要對(duì)其作業(yè)運(yùn)行的計(jì)算期望,以及保證作業(yè)正常運(yùn)行所需要的最小資源需求進(jìn)行描述。例如指定“最小作業(yè)計(jì)算費(fèi)用”,“最短作業(yè)計(jì)算時(shí)間”等。記網(wǎng)格中資源的價(jià)格為P,計(jì)算期望分析器將用戶(hù)計(jì)算任務(wù)的計(jì)算期望轉(zhuǎn)換為對(duì)資源R和價(jià)格P的描述,并把任務(wù)對(duì)資源的需求描述提交到資源管理交易器。在保證作業(yè)運(yùn)行所需最小資源的基礎(chǔ)上,盡量滿(mǎn)足用戶(hù)的計(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é),以?xún)r(jià)格為杠桿,使網(wǎng)格內(nèi)資源負(fù)載達(dá)到平衡。
3 網(wǎng)格資源調(diào)度算法
在本模型中,通過(guò)不同的計(jì)算期望來(lái)描述用戶(hù)不同類(lèi)型的計(jì)算要求,不同的計(jì)算期望對(duì)應(yīng)著不同的資源調(diào)度算法。下面介紹本模型中的幾種資源調(diào)度策略。
3.1 期望為“最小作業(yè)計(jì)算費(fèi)用”的資源調(diào)度算法
設(shè)執(zhí)行用戶(hù)計(jì)算任務(wù)所需要最低資源要求為:
計(jì)算期望分析器從本地市場(chǎng)信息服務(wù)模塊中查詢(xún)到的當(dāng)前本地可用資源為:
n為本地市場(chǎng)信息服務(wù)模塊中記錄的可用資源數(shù)。
最小作業(yè)計(jì)算費(fèi)用算法概述如下:
步驟1 根據(jù)計(jì)算期望描述,資源管理交易器查詢(xún)本地市場(chǎng)信息服務(wù)模塊,選擇滿(mǎn)足條件的價(jià)格P最低的計(jì)算資源。
步驟2 資源管理交易器將選擇出的計(jì)算資源分配給用戶(hù)作業(yè)。
步驟3 若本自治域內(nèi)的資源無(wú)法滿(mǎn)足用戶(hù)計(jì)算任務(wù)的最低資源要求,則資源管理交易器將資源請(qǐng)求發(fā)送至本區(qū)域的信息轉(zhuǎn)發(fā)器。信息轉(zhuǎn)發(fā)器查詢(xún)其數(shù)據(jù)庫(kù)中保存的本區(qū)域內(nèi)各自治域計(jì)算資源屬性的最大值。并選擇所有滿(mǎn)足式(4)的自治域j,將資源請(qǐng)求發(fā)送至這些自治域。
步驟4 收到資源請(qǐng)求的自治域執(zhí)行步驟1,并將滿(mǎn)足條件的計(jì)算資源信息發(fā)送至作業(yè)提交者的資源交易管理器。
步驟5 若作業(yè)提交者所在區(qū)域內(nèi)所有自治域的資源都無(wú)法滿(mǎn)足用戶(hù)計(jì)算任務(wù)的最低資源要求,則由本區(qū)域的信息轉(zhuǎn)發(fā)器將資源請(qǐng)求發(fā)送至相鄰的信息轉(zhuǎn)發(fā)器。收到資源請(qǐng)求的信息轉(zhuǎn)發(fā)器選擇滿(mǎn)足式(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è)提交者所在的資源管理交易器在收到滿(mǎn)足作業(yè)最小要求的資源返回的資源信息后,對(duì)其按照價(jià)格進(jìn)行排序,并按照作業(yè)的要求,選擇價(jià)格最小的一個(gè)或多個(gè)資源分配給用戶(hù)作業(yè)。并將交易契約發(fā)送至被選擇的資源。資源得知自己被選擇后,根據(jù)價(jià)格策略提升其資源價(jià)格。為了防止等待時(shí)間過(guò)長(zhǎng),用戶(hù)的本地資源管理交易器從將資源請(qǐng)求發(fā)送至本區(qū)域信息轉(zhuǎn)發(fā)器時(shí)開(kāi)始計(jì)時(shí),經(jīng)過(guò)一段規(guī)定的時(shí)間,停止查詢(xún),若此時(shí)無(wú)滿(mǎn)足條件的資源信息返回,則本次查詢(xún)失敗。
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è)資源分配給用戶(hù)作業(yè)。
3.3 期望為“自定義價(jià)格/執(zhí)行時(shí)間”的資源調(diào)度算法
用戶(hù)指定的完成時(shí)間為T(mén)user,用戶(hù)作業(yè)在資源i上的預(yù)測(cè)執(zhí)行時(shí)間為T(mén)iPRDCT,資源i上作業(yè)等待隊(duì)列時(shí)間為T(mén)iwait,用戶(hù)指定的作業(yè)計(jì)算費(fèi)用為Puser,資源i的價(jià)格為Pi。
當(dāng)計(jì)算期望為“自定義價(jià)格/執(zhí)行時(shí)間”時(shí),用戶(hù)作業(yè)除了要滿(mǎn)足作業(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è)提交者所在的資源管理交易器在收到滿(mǎn)足作業(yè)最小要求的資源返回的資源信息后,對(duì)其按照作業(yè)等待隊(duì)列時(shí)間Twait進(jìn)行排序,選擇所有滿(mǎn)足式(5)的資源i,并將其結(jié)果返回給用戶(hù),由用戶(hù)從1個(gè)或多個(gè)滿(mǎn)足時(shí)間約束的資源中選擇合適自己作業(yè)的資源。
“自定義價(jià)格”調(diào)度算法步驟6:作業(yè)提交者所在的資源管理交易器在收到滿(mǎn)足作業(yè)最小要求的資源返回的資源信息后,對(duì)其按照預(yù)測(cè)執(zhí)行時(shí)間為T(mén)PRDCT排序,選擇所有滿(mǎn)足式(6)的資源i,并將其結(jié)果返回給用戶(hù),由用戶(hù)從1個(gè)或多個(gè)滿(mǎn)足時(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è)占滿(mǎn),因此兩個(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í)間增加,所以滿(mǎn)足一定的價(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)確的資源描述與分配,滿(mǎn)足了用戶(hù)個(gè)性化的計(jì)算需求,簡(jiǎn)化了用戶(hù)的工作量,在系統(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)描述用戶(hù)作業(yè)的執(zhí)行要求,由系統(tǒng)自動(dòng)將計(jì)算期望映射成對(duì)網(wǎng)格計(jì)算資源屬性的描述,簡(jiǎn)化了用戶(hù)在提交作業(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ù)查詢(xún)的層次式結(jié)構(gòu),以實(shí)現(xiàn)查詢(xún)效率與系統(tǒng)開(kāi)銷(xiāo)的折衷。采用網(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)一步的研究。
評(píng)論