服務網格中資源可用性評估方法研究
2008-12-31 00:00:00丁長松胡周君
計算機應用研究 2008年12期
(1.吉首大學 物理科學與信息工程學院，湖南 吉首 416000; 2.中南大學 信息科學與工程學院，長沙 410083)
摘 要：
資源可用性的預測與評估是動態網格環境下合理資源選擇和保證服務質量的前提和基礎。基于相關資源和任務的歷史信息，利用概率論方法對資源可用性進行了預測與評估，提出了資源離線時間、本地任務執行時間、等待隊列長度、等待時間等可用性尺度，證明并給出這些尺度的分布函數。實驗表明，基于相關歷史信息對資源可用性進行預測方法有效，并且根據資源可用性評估及提取的相關可用性尺度來確定任務調度的候選資源，可大大減少候選資源數目，從而降低調度的時間復雜度。
關鍵詞：可用性； 可用性尺度； 預測； 評估
中圖分類號：TP316文獻標志碼：A
文章編號：10013695(2008)12379004
Research on methodology of resource availability evaluation in service grid environment
DING Changsong1，2， HU Zhoujun2
(1. School of Physics Electron， Jishou University， Jishou Hunan 416000， China; 2. School of Physics Science Information Engineering， Central South University， Changsha 410083， China）
Abstract:In dynamic grid environment， prediction and evaluation of resource availability are the prerequisite for reasonable resource selection and good QoS guarantee. Based on some related resource and task historical traces， applied probability theory to resource availability prediction and evaluation.Presented the availability metrics including resource offline time， local task execution time， waiting queue length and waiting time and gave and proved the distribution functions of these metrics. The experiment results show that the prediction is effective， and the amount of candidate resources determined by resource availability evaluation is decreased significantly， therefore lowering time complexity of task scheduling.
Key words：availability;availability metric; prediction; evaluation
0 引言
面向服務的網格計算是將地理上異構的大量閑置資源利用起來實現資源共享，為大規模科學應用提供解決手段的一種技術。網格中的資源為通過高速網絡互連的自治管理域，本文將這樣的管理域稱為網格節點。服務網格環境下，資源管理和任務調度需要知道服務的狀態、能力等可用信息，然而由于本地任務到達、資源本身、資源提供者的自主行為等原因使得將網格資源封裝抽象成網格服務時，其服務可用性具有較強的動態性。如何對產生服務可用性動態變化的網格資源進行預測與評估對資源管理和任務調度具有重要意義。
服務網格環境下，資源可用性包含以下內容：a)資源的在線服務時間，可通過由于資源本身原因如軟/硬件故障，或資源提供者的自主行為如重啟、撤銷網格服務等資源離線造成的服務不可用(offline unavailability， OLU)時間進行度量。b)資源為網格任務服務的時間，資源作為網格服務提供者，其服務能力受到執行動態到達的本地任務的影響，并且在通常情況下本地任務具有更大的優先權[1，2]，可通過在一定時間內本地任務執行時間的大小來體現一個資源的閑置狀況。c)資源提供給網格服務時，但由于本地接納任務數量已達到上限造成資源對后續任務不可用，可通過等待隊列長度進行度量。
1 相關工作
目前，對資源可用性的特性如利用率、統計特征(分布函數、均值等)、自相似性等已有相關研究。文獻[3]對資源利用率進行了統計，指出大多數桌面主機沒有被充分利用，平均利用率低于5%，而服務器平均利用率為14%，并且在低利用率時，負載有著幾乎靜態的行為。文獻[4]對桌面主機網格中的資源易變性進行了分析，指出桌面主機空閑時間最小為10 min，平均空閑時間為2.6 h。文獻[5]對若干個工作站進行了數月的監控，對獲得的歷史數據進行統計分析，得出了工作站本地任務執行時間的概率分布。文獻[6]統計分析得出集群、服務器、工作站的主機負載存在高度的自相似性。文獻[7]認為網絡流量具有很強的自相似性。
在資源可用性的預測與評估方面，文獻[8]利用時間序列模型(AR、 MA、ARMA、ARIMA)對未來1~30 s內主機負載進行了預測，基于預測的負載值設計并實現了RPS(resource prediction system)[9]，網格環境中的網絡性能預測系統(network weather system， NWS)則是利用時間序列模型對網絡帶寬作短期內預測。文獻[10]基于對實際網絡數據包的歷史數據分析，利用人工神經網絡對網絡可用帶寬進行預測，并通過實驗得出了神經網絡的學習速率、學習樣本數量、隱含層數目、每層神經元數目等相關參數。這些研究主要集中在資源某個方面能力(如CPU負載、內存利用率、網絡帶寬等)的預測與評估。文獻[1]基于排隊理論預測任務完成時間，從而對資源的服務能力進行評估，該方法需要事先知道任務在資源無負載時的執行時間，不是單獨從資源端進行評估。文獻[2]基于資源及任務的相關統計特性評估得出了資源可用性的一些度量尺度如平均隊列長度、平均使用CPU數量等，但評估得出的尺度主要是平均值并且不夠全面。文獻[11]根據導致資源可用與否的原因將其分為若干種狀態，利用馬爾可夫模型預測資源的未來狀態，但其對資源的評估僅僅停留在可用或不可用狀態上，缺乏對資源可用性相關尺度的提取。
與上述對資源可用性評估研究不同的是，本文研究服務網格環境下的資源可用性，其包含的內容更加全面、深入，基于對資源和任務相關信息觀察、統計、分析得出的歷史信息，利用概率論的方法對資源可用性進行預測，研究并提出了網格資源可用性的四個評估尺度及其分布函數，即資源離線時間、本地任務執行時間、等待隊列長度、等待時間等。通過對資源可用性的預測與評估，可以提高資源預留及SLA協商成功率，并為資源匹配或任務調度等提供更可靠更直觀的依據。
2 研究基礎
本文基于對網格節點相關可用性特性統計的歷史信息，利用概率論的方法預測資源未來狀態，并對其進行評估，提取若干可用性尺度。相關研究基礎簡述如下：
假設本地任務比網格任務具有更大優先權[1，2]，一個網格節點在執行一個網格任務時，由于本地任務的到達使得網格節點中斷執行網格任務轉去處理本地任務。假設當網格任務達到時，節點處于空閑狀態，則一個網格任務的完成時間可表示為
T=Y1+X1+Y2+X2+…+YN+XN+Z
(1)
其中：Yi、Xi(i=1，…，N)分別表示網格任務執行時間和本地任務執行時間;Z表示最后一部分網格任務執行時間;N表示時間段T內到達的本地任務數量。
文獻[5]指出本地任務執行時間Xi(1≤i≤N)服從參數為γ的指數分布。其概率分布函數為
F(x)=1-e-γ#8226;x
(2)
其中:參數γ由各網格節點根據本地任務執行時間的歷史數據統計可得，并且可以動態更新。
文獻[1]將網格節點處理本地任務視為一個排隊系統。根據排隊理論可知，在時間段Δt內，本地任務達到數目N為一隨機變量，服從參數為λ的泊松分布，則在時間段T內本地任務到達的數目為n的概率分布為
P{N=n}=λΔt/T#8226;n#8226;e-λ/(Δt/T#8226;n)!
(3)
其中：參數λ、Δt由各網格節點根據一段時間內本地任務到達數目的歷史數據統計可得，并且可以動態更新。
文獻[11]對普渡大學計算機實驗室大量主機觀察了三個月，基于其統計得出的歷史數據，本文分析發現其24 h內資源離線造成的服務不可用時間從曲線上看可以用指數或超指數分布曲線對其進行擬合，不失一般性，本文簡單假設某段時間內資源由于重啟、關機或故障等因素造成的資源離線的時間服從參數為δ的指數分布。其概率分布函數為
F(x)=1-e-δ#8226;x
(4)
其中：參數δ由各網格節點根據本地資源離線時間的歷史數據統計可得，并且可以動態更新。
3 可用性尺度
首先，利用概率論方法得到若干個相同隨機變量之和服從一定概率分布的定理。該定理描述及證明如下：
定理1 假設隨機變量X1，X2，…，XN相互獨立，且均服從參數為γ的指數分布，則隨機變量U=∑Ni=1Xi的概率分布函數為
F(u)=-1/γ{e-γ#8226;u#8226;un-1+（n-1）/γ[e-γ#8226;u#8226;un-2+（n-2）/γ(…+（3/γ(e-γ#8226;u#8226;u2+2/γ(e-γ#8226;u#8226;u+
1/γ（e-γ#8226;u-1)))）…)]}#8226;γn/(n-1)!;u≥0
0；u＜0
(5)
證明 當u＜0時，F(u)=0。
當u≥0時，X服從參數為γ的指數分布并且X1，X2，…，XN相互獨立，則(X1，X2，…，XN)的聯合分布密度為
f(x1，x2，…，xN)=γN#8226;e-γ#8226;∑Ni=1xi(6)
故∫∑Ni=1Xi≤u+h…F(u)=P(∑Ni=1Xi≤u)=
∫∑Ni=1Xi≤u…∫γN#8226;e-γ#8226;∑Ni=1xidx1dx2…dxN
(7)
可得F(u+h)-F(u)=∫∑Ni=1Xi≤u+h…∫γN#8226;e-γ#8226;∑Ni=1Xidx1dx2…dxN(h＞0)。
于是有
F(u+h)-F(u)≤∫u＜∑Ni=1Xi≤u+h…∫γN#8226;e-γ#8226;udx1dx2…dxN=
γN#8226;e-γ#8226;u#8226;∫u＜∑Ni=1Xi≤u+h…∫dx1dx2…dxN
(8)
F(u+h)-F(u)≥∫u＜∑Ni=1Xi≤u+h…∫γN#8226;e-γ#8226;(u+h)dx1dx2…dxN=
γN#8226;e-γ#8226;(u+h)#8226;∫u＜∑Ni=1Xi≤u+h…∫dx1dx2…dxN
(9)
令S(u)=∫∑Ni=1Xi≤u…∫dx1dx2…dxN(10)
則 S(u+h)-S(u)=∫u＜∑Ni=1xi≤u+h…∫dx1dx2…dxN
由式(8)(9)得
γN#8226;e-γ#8226;(u+h)#8226;[S(u+h)-S(u)]/h≤[F(u+h)-F(u)]/h≤
γN#8226;e-γ#8226;u#8226;[S(u+h)-S(u)]/h
(11)
再令xi=wi#8226;u，則dxi=udwi(i=1，2，…，N)
所以，由式(10)得S(u)=∫∑Ni=1Wi≤1…∫uNdw1dw2…dwN=uN#8226;CN
其中:CN=∫∑Ni=1wi≤1…∫dw1dw2…dwN是僅與N有關的常數。
所以，S′(u)=N#8226;CN#8226;uN-1
可求
limn→0γN#8226;e-γ#8226;(u+h)#8226;[S(u+h)-S(u)]/h=γN#8226;e-γ#8226;u#8226;N#8226;CN#8226;uN-1
(12)
limh→0γN#8226;e-γ#8226;u#8226;[S(u+h)-S(u)]/h=γN#8226;e-γ#8226;u#8226;N#8226;CN#8226;uN-1
(13)
由式(11)~(13)，根據夾逼定理得
limh→0[F(u+h)-F(u)]/h=γN#8226;e-γ#8226;u#8226;N#8226;CN#8226;uN-1
(14)
由式(14)，根據導數定義得f(u)=F′(u)=BN#8226;e-γ#8226;u#8226;uN-1。
其中:BN=γN#8226;N#8226;CN。
又因為∫+∞0f(u)du=1
即∫+∞0BN#8226;e-γ#8226;u#8226;uN-1du=1
所以
BN=1/∫+∞0e-γ#8226;u#8226;uN-1du=γN/(N-1)!(15)
故
f(u)=γN/(N-1)!#8226;uN-1#8226;e-γ#8226;u(16)
故
F(u)=∫u0f(u)du=∫u0BN#8226;e-γ#8226;u#8226;uN-1du=
-1/γ{e-γ#8226;u#8226;uN-1+（N-1）/γ[e-γ#8226;u#8226;uN-2+（N-2）/γ(…+
(3/γ(e-γ#8226;u#8226;u2+2/γ(e-γ#8226;u#8226;u+
1/γ（e-γ#8226;u-1))))…)]}#8226;BN
(17)
故定理得證。
基于定理1及相關歷史統計信息，再得出資源離線時間、本地任務執行時間、等待隊列長度、等待時間等可用性尺度的分布函數。
3. 1 資源離線時間
離線時間服從參數為δ的指數分布，通過在實際環境中觀察得到在某段時間內由于軟/硬件更新或故障、人為因素等造成的資源離線次數相對比較穩定，假設為常數C。根據定理1可得，在某段時間內，資源離線時間分布函數為
F(u)=-1/δ{e-δ#8226;u#8226;uC-1+（C-1）/δ[e-δ#8226;u#8226;uC-2+
（C-2）/δ(…+（3/δ(e-δ#8226;u#8226;u2+2/δ(e-γ#8226;u#8226;u+
1/δ(e-δ#8226;u-1))))…)]}#8226;δC/(C-1)!； u≥0
0;u＜0
(18)
3. 2 本地任務執行時間
在某段時間內，本地任務到達數目N也為一隨機變量，服從參數為λ的泊松分布，并且與本地任務執行時間x相互獨立，則根據定理1可得，該時間段內，本地任務執行時間是一個二維隨機變量。其分布函數為
F(u，n)=-λΔt/T#8226;n#8226;e-λ/(Δt/T#8226;n)!#8226;1/γ{e-γ#8226;u#8226;un-1+
（n-1）/γ[e-γ#8226;u#8226;un-2+（n-2）/γ(…+(3/γ
(e-γ#8226;u#8226;u2+2/γ(e-γ#8226;u#8226;u+1/γ(e-γ#8226;u-
1))))…)]}#8226;γn/(n-1)!；u≥0
0; u＜0
(19)
根據式(19)，對于給定時間段T內到達的本地任務數量n以及一定的概率p，可得到該段時間內本地任務執行時間大小Tl=u，定義資源閑置率為
r=1-Tl/T
(20)
資源閑置率表示在本地任務具有較大優先權情況下，一段時間內網格任務能使用該資源的時間比例大小，其值越大，表明該節點有更多的時間為網格任務服務。
3. 3 等待隊列長度
假設一個網格節點內包含的機器數目為c，當前等待隊列中等待執行的任務數目為w，一段時間t內到達任務數目為N，該段時間t內執行完畢或正在執行的任務總數為F(即離開等待隊列的任務數目)，則經過時間t后的等待隊列長度L=w+N-F。
其中：w為常量;N為服從參數為λ的泊松分布的隨機變量，任務執行時間以及正在執行任務的已執行時間服從參數為γ的指數分布;F為離散型隨機變量。
在時間段t內，F個任務在c臺機器上執行完畢或正在執行，則X1+X2+…+XF=ct，即定理1中的U=ct，N=F，可得隨機變量F的分布函數為
P{F=f}=-1/γ{e-γct#8226;(ct)f-1+(f-1)/γ[e-γct#8226;(ct)f-2+(f-2)/γ(…+(3/γ(e-γct#8226;(ct)2+2/γ(e-γct#8226;c#8226;t+1/γ(e-γct-1))))…)]}#8226;γf/(f-1)!； f≤w+N
當w+N-F＞0時，等待隊列長度的分布函數為
P{L=l，F=f}=-（λΔt/t#8226;(l+f)#8226;e-λ）/[Δt/t#8226;(l+f)]!#8226;1/γ{e-γct#8226;(ct)f-1+（f-1）/γ[e-γct#8226;
(ct)f-2+（f-2）/γ(…+(3/γ(e-γct#8226;(ct)2+2/γ(e-γct#8226;
c#8226;t+1/γ(e-γct-1))))…)}#8226;γf/(f-1)!
(21)
當F=w+N-1時，等待隊列為空，則距離等待隊列為空的時間的分布函數為
P{L=0， N=n}=-（λΔt/t#8226;n#8226;e-λ）/(Δt/t#8226;n)!#8226;1/γ{e-γct#8226;
(ct)w+n-2+(w+n-2)/γ[e-γct#8226;(ct)w+n-3+（w+n-3）/
γ(…+(e/γ(e-γct#8226;(ct)2+2/γ(e-γct#8226;c#8226;t+1/γ(e-γct-
1))))…)]}#8226;γw+n-1/(w+n-2)!
(22)
3. 4 等待時間
假設一個網格節點內包含的機器數目為c，當一個任務到達時，隊列中已有w個任務，新到達的任務在隊列中等待直到隊列中w個任務全部分配到處理機上，并當有一臺機器空閑時，該任務即可運行，則其等待時間Tw為w個任務在c臺機器上執行花費的時間。即
c#8226;Tw=X1+X2+…+Xw，即定理1中N=w，求U的概率分布。則等待時間Tw概率分布函數為
F(u)=-1/γ{e-γ#8226;c#8226;u#8226;(cu)w-1+（w-1）/
γ[e-γ#8226;c#8226;u#8226;(cu)w-2+（w-2）/γ(…+
(3/γ(e-γ#8226;c#8226;u#8226;(cu)2+2/γ(e-γ#8226;c#8226;u#8226;c#8226;u+
1/γ(e-γ#8226;c#8226;u-1))))…)]}#8226;γw/(w-1)!
(23)
4 性能評估
本章通過仿真實驗來驗證預測及資源可用性評估的有效性。
本文在GridSim網格模擬器上進行仿真。實驗數據采用真實數據與假設數據相結合的方式，總共產生15個網格節點。其中一個網格節點的各種參數為真實數據(見表1第2行)，其他產生14個網格節點的相關參數為假設數據，在表1第3行指定的范圍內隨機產生。真實數據來源如下：文獻[5]對運行在UNIX系統下的11個DEC VAXstationⅡ工作站使用情況進行了5個月的監控，通過對歷史數據的統計與分析，得出本地任務執行時間服從指數分布的參數γ=1/7；文獻[1]假設在1 h內，本地任務到達數量服從泊松分布的參數λ=1；對文獻[11]中的歷史數據進行分析得出資源離線時間服從指數分布的參數δ=0.18；同時，對中南大學的并行處理與網絡計算實驗室若干臺服務器由于軟/硬件更新或人為因素造成資源離線次數進行了2個月的觀察，得出24 h內平均資源離線次數C=2；網格節點內包含的機器數目為c=1;時間段T=24 h。
表1 不同網格節點參數信息表
type γλδCc
real1/710.1821
hypothetic[0.02，0.2][1，12][0.15，0.25][1，5]30
對預測的驗證采取理論分析與模擬兩種方式進行理論分析時，求得概率大于0.9的資源離線時間、本地任務執行時間、等待隊列長度、等待時間等尺度；模擬時，根據各網格節點服從各種參數分布的特性產生一系列相應的隨機數，為使假設數據符合實際情況，對產生的隨機數加入一定的高斯白噪聲(服從N(0，1)分布)，并得到資源離線時間、本地任務執行時間、等待隊列長度、等待時間等尺度。兩種方式下的四個尺度對比如圖1~4所示(其中，第一個網格節點的相關參數為真實數據)。從圖中可以看出，理論分析的預測值與模擬得到的實際值均比較接近。各個節點的各種尺度預測精度為78%~97%，平均預測精度為85%。預測精度并不是很高的主要原因是，統計學方法只是對實際網格資源情況的一種近似刻畫，即預測精度取決于資源可用性的各種分布模型與實際情況的擬合程度。對網格資源可用性的相關歷史信息進行統計分析，并利用最貼近的模型對其進行描述不在本文討論范圍內。
從圖1~4中還可以看出，不同網格節點的資源可用性均有所不同。如節點1的本地任務執行時間總共不到1/3，有更多時間為網格任務服務，并且由于到達任務比較少使得任務無須等待即可執行。由于單個本地任務執行時間較長，導致節點3、7、11花費高達一半甚至超過2/3的時間處理本地任務，不利于為網格任務服務，但由于本地任務到達時間間隔較長，無須長時間等待即可執行。有些節點雖然本地任務總共執行時間不大(如節點9)，但由于任務頻繁到達使得在該節點上執行的任務等待時間較長。所有節點作為網格服務提供者均比較穩定，其資源離線時間在24 h內僅為10~60 min，主要可能是由于資源提供者升級系統補丁后重啟或斷開網絡進行有關備份造成的。
同時，與基于資源靜態能力來確定調度選擇的候選資源進行比較，來驗證基于動態資源評估對候選資源數目的影響，模擬產生資源共600個，每個資源的相關參數在表1第二行指定的范圍內隨機產生，產生一個任務并設定四個不同的截止時間分別為10~13 h，資源靜態能力均能滿足用戶截止時間要求，在此主要利用本地任務執行時間對資源進行篩選。
動態資源評估對候選資源數目影響如圖5所示。在截止時間較小情況下，篩掉了負載較重的大多數資源；隨著截止時間的不斷寬松，候選資源數目也逐漸上升，部分負載重的資源有足夠的時間來處理網格任務。因此，在一定截止時間特別是截止時間較嚴格的條件下，通過對動態資源的評估，篩掉由于本地負載過重或由于等待隊列過長而無法接納新任務等因素不能滿足任務要求的資源，可大大減少任務調度的候選資源數目，從而降低調度的時間復雜度。
5 結束語
面向服務的高性能計算網格環境下的動態資源可用性評估是資源管理中的一個關鍵問題。本文基于相關歷史信息，利用概率論方法，研究并給出了網格資源可用性的以下四個評估尺度及其分布函數，即資源離線時間、本地任務執行時間、等待隊列長度、等待時間。實驗表明，預測方法有效，并且與只考慮資源靜態能力相比，基于動態資源評估來確定任務調度的候選資源，可大大減少候選資源數目，降低了調度的時間復雜度。下一步工作是基于本文的可用性尺度設計相應的調度算法。
參考文獻：
[1]GONG Linguo， SUN Xianhe， WATSON E F. Performance modeling and prediction of nondedicated network computing[J]. IEEE Trans on Computers， 2002，51(9):10411055.
[2]BERTEN V， GOOSSENS J， JEANNOT E. On the distribution of sequential jobs in random brokering for heterogeneous computational grids[J]. IEEE Trans on Parallel and Distributed System， 2006，17(2):113124.
[3]SOLDATOS J， VAYIAS E， POLYMENAKOS L. Grid donors resources utilization analysis towards optimal job scheduling[C]//Proc of DPSN ’04 Workshop.Athens: IEEE Computer Society， 2004.
[4]KONDO D， FEDAK G， CAPPELLO F， et al. Resource availability in enterprise desktop grids [EB/OL]. [20060111]. http://hal.inria.fr/inria00000994/en/.
[5]MUTKA M W. Sharing in a privately owned workstation environment[D]. [S.l.]: University of WisconsinMadison， 1988.
[6]DINDA P A. The statistical properties of host load[J]. Scientific Programming， 1999，7(3~4):211229.
[7]CROVELLA M E， BUSTAVROS A. Selfsimilarity in World Wide Web traffic: evidence and possible causes[J]. IEEE/ACM Trans on Networking， 1997，6(5): 835846.
[8]DINDA P A， O’ H ALLARON D R O. An evaluation of linear models for host load prediction[C]//Proc of the 8th IEEE International Symposium on High Performance Distributed Computing (HPDC’99). Redondo Beach: IEEE Computer Society， 1999:8796.
[9]DINDA P A. Design， implementation， and performance of an extensible toolkit for resource prediction in distributed systems[J]. IEEE Trans on Parallel and Distributed System， 2006，17(2):160173.
[10]ESWARADASS A， SUN Xianhe，WU Ming. A neural network based predictive mechanism for available bandwidth[C]//Proc of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05). Denver: IEEE Computer Society， 2005:33a.
[11]REN Xiaojuan， LEE Seyong， EIGENMANN R， et al. Prediction of resource availability in finegrained cycle sharing systems empirical evaluation[J].Journal of Grid Computing， 2007，5(2):173195.
