兩種網(wǎng)格服務(wù)模型的對比研究

摘要：結(jié)合網(wǎng)格系統(tǒng)中虛擬組織內(nèi)部的集中調(diào)度機(jī)制，介紹了一種現(xiàn)有的多隊列服務(wù)模型，該模型將提交到虛擬組織上的作業(yè)請求分配到該虛擬組織內(nèi)部資源的服務(wù)隊列上；考慮到網(wǎng)格環(huán)境中服務(wù)的動態(tài)性，將服務(wù)隊列集中在調(diào)度中心的單隊列服務(wù)模型應(yīng)用于網(wǎng)格環(huán)境，通過對提供服務(wù)的資源發(fā)生故障的情況進(jìn)行仿真實驗，對這兩種服務(wù)模型進(jìn)行了對比研究，并進(jìn)一步提出了自適應(yīng)隊列模型的構(gòu)想。

關(guān)鍵詞：網(wǎng)格；服務(wù)模型；虛擬組織；調(diào)度中心

中圖分類號：TP393．1文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)11-0271-03

0引言

網(wǎng)格的思想是將網(wǎng)格定位于一種類似于電力設(shè)施，只要通過統(tǒng)一的接口接入網(wǎng)格，就可以獲得類似于電的持續(xù)計算力。該思想自20世紀(jì)末提出以來，得到了全球的廣泛關(guān)注。學(xué)術(shù)界在網(wǎng)格研究領(lǐng)域的諸多成果，引起了眾多IT企業(yè)的興趣。一些著名的IT廠商，如微軟、IBM、Sun、Oracle等均投入了大量的經(jīng)費(fèi)進(jìn)行網(wǎng)格研究。

網(wǎng)格思想的核心是資源的共享與協(xié)作。圍繞著這個核心，大量涉及安全、資源管理、網(wǎng)格體系結(jié)構(gòu)、數(shù)據(jù)管理、調(diào)度等方面的研究工作正在進(jìn)行。文獻(xiàn)[1]提出了基于協(xié)議的五層沙漏模型的網(wǎng)格體系結(jié)構(gòu)。基于此文獻(xiàn)思想，Globus項目組開發(fā)了相應(yīng)的工具包GT2。GT2中的MDS2實現(xiàn)了資源的監(jiān)測和發(fā)現(xiàn)。隨著網(wǎng)格研究進(jìn)入商業(yè)領(lǐng)域，一些商業(yè)標(biāo)準(zhǔn)如Web service被融入了網(wǎng)格中。文獻(xiàn)[2]提出了以服務(wù)為中心的網(wǎng)格體系結(jié)構(gòu)OGSA。在此體系結(jié)構(gòu)中，所有的資源都被建模成服務(wù)。基于OGSA，Globus項目組但又推出工具包GT4。GT4中的服務(wù)監(jiān)測與發(fā)現(xiàn)由MDS4實現(xiàn)。

雖然MDS2和MDS4實現(xiàn)了資源及服務(wù)的發(fā)現(xiàn)、監(jiān)測，但是關(guān)于這方面的性能評價與分析的研究工作還很少。在網(wǎng)格環(huán)境中，服務(wù)是動態(tài)分布在異構(gòu)的廣域網(wǎng)中，對服務(wù)的透明訪問與管理構(gòu)成了網(wǎng)格研究的一個重要方面，而網(wǎng)格服務(wù)的建模研究則可為評價與分析網(wǎng)格服務(wù)提供理論基礎(chǔ)。

目前，國內(nèi)外對網(wǎng)格建模方面的研究主要集中在對提交到網(wǎng)格的作業(yè)的調(diào)度上，對網(wǎng)格服務(wù)模型研究得不多。文獻(xiàn)[3~5]主要研究了網(wǎng)格環(huán)境下資源管理和調(diào)度模型，但是沒有考慮到資源的動態(tài)性；文獻(xiàn)[6]研究了資源狀態(tài)變化時（資源故障或主動退出服務(wù)）網(wǎng)格服務(wù)的建模。該模型存在一個調(diào)度中心，用于將提交到網(wǎng)格上的作業(yè)分配到各個資源的隊列上，每一個資源都對應(yīng)一個服務(wù)隊列。下面討論的多隊列模型就是這個模型。基于以上研究工作，本文擬討論一種網(wǎng)格環(huán)境中存在調(diào)度中心的情況下，提交到網(wǎng)格上的作業(yè)由調(diào)度中心統(tǒng)一調(diào)度的單隊列模型，并且將該模型與多隊列模型在資源動態(tài)變化的情況下進(jìn)行對比研究。

1兩種模型介紹

文獻(xiàn)[6]中提出了網(wǎng)格服務(wù)中的多隊列模型，如圖1(a)所示。該模型在多個資源組成的虛擬組織內(nèi)設(shè)立一個調(diào)度中心，所有提交到該虛擬組織的作業(yè)，都通過該調(diào)度中心分配到虛擬組織內(nèi)的服務(wù)提供者上去執(zhí)行。每個服務(wù)提供者都有一個服務(wù)隊列與其對應(yīng)。目前，Condor－G、Nimrod/G等系統(tǒng)就可以用該模型來近似。

在網(wǎng)格環(huán)境下，服務(wù)模型還可以用如圖1(b)所示的單隊列模型來表示。該模型與圖1(a)的區(qū)別是，提交到虛擬組織上的作業(yè)進(jìn)入調(diào)度中心的隊列上，各個資源沒有服務(wù)隊列。這是因為考慮到在網(wǎng)格環(huán)境下，資源是動態(tài)地加入虛擬組織并且提供服務(wù)的，當(dāng)資源動態(tài)退出虛擬組織時，其服務(wù)隊列上的作業(yè)要么丟失，要么重新提交到其他資源的服務(wù)隊列上，這將增加作業(yè)的丟失率或延長作業(yè)的平均服務(wù)時間。圖1(b)就是基于這種考慮提出來的。

在圖1中，進(jìn)入虛擬系統(tǒng)的作業(yè)服從強(qiáng)度為λ的泊松分布。q1，q2，…，qN為將各新到達(dá)的作業(yè)分配到各個資源的概率。

從直觀上看，多隊列模型的優(yōu)點(diǎn)在于調(diào)度中心無須維護(hù)服務(wù)隊列，從而降低了調(diào)度中心的負(fù)擔(dān)；同時也避免了由于調(diào)度中心故障而導(dǎo)致整個虛擬組織不能正常工作的風(fēng)險。單隊列模型的優(yōu)點(diǎn)在于可以降低當(dāng)服務(wù)提供者動態(tài)退出網(wǎng)格時，可能會引起的作業(yè)損失或作業(yè)遷移對系統(tǒng)帶來的影響。

2關(guān)于兩種模型的一些結(jié)論

下面對多隊列模型和單隊列模型作簡單的理論分析。首先考慮資源不動態(tài)變化的情況，即各服務(wù)提供者既不中途退出服務(wù)，又不發(fā)生故障。

3仿真研究

以下通過仿真，對上述兩種模型進(jìn)行對比研究。仿真程序是采用Java編寫，每一個服務(wù)提供者對應(yīng)一個provider類的對象，每一個隊列對應(yīng)一個queue類的對象。圖2是在資源穩(wěn)定不變的情況下，對一個存在著100個服務(wù)提供者的虛擬組織進(jìn)行仿真得到的結(jié)果。這里每個服務(wù)提供者的服務(wù)速率服從參數(shù)為10的負(fù)指數(shù)分布，到達(dá)虛擬組織的作業(yè)服從參數(shù)為λ的泊松分布。λ在下面的仿真實驗中從500個/s增加到1 200個/s。在多隊列模型中，每個服務(wù)提供者的隊列容量為10，單隊列模型中的隊列容量為1 000。 

在圖2(a)中，當(dāng)提交到虛擬組織上的作業(yè)到達(dá)率小于虛擬組織內(nèi)所有服務(wù)提供者的總服務(wù)速率時，單隊列模型無論在作業(yè)的平均完成時間上，還是在作業(yè)的丟失率上，都具有優(yōu)勢。這與理論上的推導(dǎo)是吻合的。

圖3是在虛擬組織內(nèi)各個資源均存在較小的資源故障率(ξ=0.1)時，兩種服務(wù)模型分別在較長的故障修復(fù)時間(η=0.1)和較短的故障修復(fù)時間(η=1)的情況下，平均完成時間和平均丟失率的仿真。

從圖3(a)可以看出，當(dāng)提交到虛擬組織上作業(yè)的到達(dá)率小于虛擬組織內(nèi)有服務(wù)提供者的總服務(wù)速率時，單隊列模型的平均完成時間要少于多隊列模型的平均完成時間。隨著作業(yè)到達(dá)速率的增加，單隊列模型的平均完成時間也明顯增加。這是因為作業(yè)隨著到達(dá)速度的增加而在調(diào)度中心的隊列中等待的時間明顯增加。當(dāng)資源發(fā)生故障時，單隊列模型對調(diào)度中心的隊列沒有影響，而多隊列模型則因為故障發(fā)生時，將丟失其隊列上的所有作業(yè)，導(dǎo)致作業(yè)丟失率增加，而完成的作業(yè)平均時間相對于資源穩(wěn)定的情況，變化不大。同時，從圖3(a)還可以看出，隨著故障排除時間的減少，可以使作業(yè)的平均完成時間略有減少。

圖3(b)則是在資源低故障率時，兩種模型的作業(yè)丟失率的對比。從圖3(b)可以發(fā)現(xiàn)，單隊列模型的作業(yè)丟失率明顯少于多隊列模型，并且在作業(yè)到達(dá)率較高時，可以通過減少故障排除時間來降低作業(yè)的丟失率。

圖4是在較大的資源故障率(ξ=1)時，兩種服務(wù)模型在較長的故障修復(fù)時間(η=0.1)和較短的故障修復(fù)時間(η=1)的情況下，平均完成時間和平均丟失率的仿真。

從圖4(a)可以發(fā)現(xiàn)，當(dāng)資源高故障率并且故障排除時間較長時，單隊列模型的作業(yè)平均完成時間較長。這是由于資源發(fā)生故障不能提供服務(wù)時，在調(diào)度中心隊列的作業(yè)只能長時間進(jìn)行等待，直到故障恢復(fù)過來繼續(xù)提供服務(wù)；而當(dāng)故障排除時間較短時，對作業(yè)的平均完成時間基本沒有影響。對于多隊列模型，故障排除時間可以略微提高作業(yè)完成時間。

圖4(b)則是作業(yè)丟失率的對比。可以看出，無論是單隊列還是多隊列模型，減少故障修復(fù)時間，可以非常明顯地減少作業(yè)丟失率。當(dāng)某資源退出虛擬組織不再繼續(xù)提供服務(wù)時，可以將其看成是故障修復(fù)時間無窮大。

4結(jié)束語

對于以上兩種網(wǎng)格環(huán)境下的服務(wù)模型，還有一些因素沒有考慮，也是下一步需要研究的目標(biāo)：

a）以上模型都是假設(shè)虛擬組織內(nèi)的服務(wù)提供者可以滿足提交到虛擬組織上作業(yè)的要求。現(xiàn)實中這一點(diǎn)是不能得到保證的。實際系統(tǒng)中應(yīng)該是多虛擬組織協(xié)同工作，因此應(yīng)該存在遷移到其他虛擬組織的作業(yè)或由其他虛擬組織遷移進(jìn)來的作業(yè)，這一點(diǎn)在模型中還未涉及。

b）模型中假設(shè)各服務(wù)提供者提供的是能滿足作業(yè)的要求，這對于一些平凡服務(wù)或是某些需要計算資源的服務(wù)來說是合理的。例如SETI@HOME項目。但對于更加廣義的服務(wù)或者服務(wù)之間存在依賴關(guān)系時，該模型還有待擴(kuò)展和補(bǔ)充。

c）以上模型基本沒有考慮通信消耗問題，如對帶寬的影響以及通信延時等。目前的一些科研網(wǎng)格項目，都是構(gòu)建在高速的光纖網(wǎng)上，帶寬是足夠的，但是要將網(wǎng)格應(yīng)用到實際生活中，帶寬問題還是需要考慮的。

從以上的實驗結(jié)果來看，單隊列和多隊列模型各有其特點(diǎn)。單隊列模型在作業(yè)丟失率和作業(yè)平均完成時間這兩個指標(biāo)上，具有較好的結(jié)果；多隊列模型則在安全性以及通信開銷上較有優(yōu)勢。單隊列模型適合于資源動態(tài)變化較頻繁的場合；而多隊列模型比較適合穩(wěn)定的虛擬組織的建模。

為了能夠同時利用兩者的優(yōu)點(diǎn)，這里嘗試提出自適應(yīng)隊列模型的思想，即到達(dá)虛擬組織的作業(yè)，由調(diào)度中心分配到其內(nèi)部各個資源上，每個資源的隊列容量根據(jù)資源與虛擬組織的當(dāng)前狀態(tài)以及該資源的歷史故障數(shù)據(jù)進(jìn)行動態(tài)調(diào)整，以滿足特定目標(biāo)，如作業(yè)丟失率指標(biāo)、平均作業(yè)完成時間指標(biāo)等。自適應(yīng)隊列模型也是本文進(jìn)一步研究的方向。

以上介紹了網(wǎng)格環(huán)境下，兩種網(wǎng)格服務(wù)模型的對比研究，希望能為將來定量分析網(wǎng)格服務(wù)以及評價網(wǎng)格質(zhì)量提供一些思路。

參考文獻(xiàn)：

［1］FOSTER I，KESSELMAN C，TUECKE S.The anatomy of the grid:enabling scalable virtual organizations[J].International J Supercomputer Applications，2001，15(3): 200-222.

[2]FOSTER I，KESSLMAN C，NICK J，et al.The physiology of the grid:an open grid services architecture for distributed systems integration[EB/OL].(2002).http://www.globus.org/－research/papers/ogsa.pdf.

[3]CAO J，JARVIS S A，SAINI S.ARMS:an agent－based resource mana－gement system for grid computing[J].Sci Program，2002，10(2): 135－148.

[4]NITZBERG B，SCHOPF J M.Current activities in the scheduling and resource management area of the global grid forum[M].Heidelberg:Springer，2002:25-37.

[5]SPOONER D P，JARVIS S A，CAO J，et al.Local grid scheduling techniques using performance prediction[J].IEE Proc Comput Di－git Tech，2003，150(2): 87-96.

[6]THOMAS N，BRADLEY J T，KNOTTENBELT W J.Stochastic analysis of scheduling strategies in a grid－based resource model[J].IEE Proc Software，2004，151(5): 232-239.

[7]陸傳賚.排隊論[M].北京：北京郵電大學(xué)出版社，1994.

[8]THOMAS N.The effect of information latency on performance[C]//Proc of the 19th Performance Engineering Workshop.2003.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”