ITSGrid資源調度策略的研究

徐 琳,曲仕茹,魚 濱

(1.西北工業大學自動化學院,陜西西安 710129; 2.西安電子科技大學計算機學院,陜西西安 710071)

ITSGrid資源調度策略的研究

徐 琳1,曲仕茹1,魚 濱2

(1.西北工業大學自動化學院,陜西西安 710129; 2.西安電子科技大學計算機學院,陜西西安 710071)

定義了系統負載均衡評價值和資源節點滿意度評價模型,并在此基礎上設計了一種分布式資源自適應調度算法(GLBCQ),同時兼顧全局負載均衡和用戶自定義的服務質量,可根據智能交通系統計算任務的自定義服務質量需求,結合當前智能交通系統網格的系統負載狀況,為提交的任務自適應地選擇最優資源.仿真實驗結果表明,GLBCQ算法具有更高的效率和自適應性,能夠促進智能交通系統網格的系統負載均衡以及整體性能的提升.

智能交通系統網格;資源調度算法;自定義服務質量需求;系統負載

隨著社會的發展,交通需求也隨之快速增長,對現有的智能交通系統(ITS)應用提出更多更高的要求.為了更好地支持ITS的各類計算服務,高效管理ITS中海量具有分布性、異構型、自治性和動態性[1]等復雜特征的計算資源,智能交通系統網格(Intelligent Transportation System Grid,ITSGrid)應運而生,且被視為解決分布式異質性環境下ITS應用問題的一種理想方案.目前,ITSGrid平臺所支持的計算服務的規模越來越大,計算服務所涉及的資源越來越多,計算服務的種類越來越多元化,并且不同的ITS計算服務分屬不同的應用類型,具有各自的特征.即使是同屬于一個應用類型的不同計算服務,也可能有各自的服務質量(Quality of Service,QoS)需求.由此可見,智能交通系統網格應用中QoS的協商和保證是一項非常復雜和具有挑戰性的工作[2].因此,如何有效地進行分布式資源調度是ITSGrid應用所面臨的重要問題,也是保證ITS應用的QoS、高效利用分布式ITS資源和提高ITSGrid系統整體性能的關鍵.為此,筆者設計了一種分布式資源自適應調度算法GLBCQ,可根據ITS計算任務的自定義QoS的需求,結合ITSGrid系統實時負載狀況,為ITS計算任務自動選擇最優資源,從而實現既滿足計算服務的自定義QoS的需求、又兼顧ITSGrid整體性能的目標.

1 ITSGrid資源調度問題的特點

在ITSGrid中,資源調度的對象廣泛分布,經常需要跨越多個管理域.不同的ITS子系統或交通參與部門采用不同策略管理各自的資源,甚至存在資源用戶和資源提供者的目的分歧相互抵觸的現象.這些分布式資源所提供的QoS是多層次的,ITSGrid用戶在很大程度上需要依賴遠程資源提供最后的QoS,以實現計算任務的應用約束.

ITSGrid是一個多資源多任務的環境.在此類環境中,資源調度問題本質上是為計算任務的執行而選擇和確定ITS資源.ITS資源與計算任務之間可能存在一對一、一對多、多對一,甚至多對多的關系,兩者之間的映射關系是一個NP完全問題[3].因此,ITSGrid的資源調度系統在進行分布式資源選擇時可能存在多種問題,需要根據不同的問題制定相應的解決方案,應充分考慮計算任務自定義QoS要求和ITSGrid系統負載均衡,按照調度策略在計算任務和分布式資源之間找到一個理想的匹配.

2 ITSGrid資源調度策略

目前,國內外已出現了許多成熟的關于通用網格的分布式資源調度策略,其中較為經典的調度策略有隨機負載平衡(OLB)、最短完成時間(MCT)、最短執行時間(MET)、切換算法(SA)和百分比K最佳啟發式(KPB)等.雖然這些經典的調度策略在實際應用中已展現了各自的效果,但是這些模型和算法也存在一定的局限性,例如它們大多只部分地考慮了眾多系統級QoS要求,在調度中逐個匹配相關參數實現資源的選擇[4],與特定的應用系統或應用特征高度耦合.更關鍵的是,所有的算法均不考慮應用任務的個性化資源QoS需求.

因此,在設計ITSGrid資源調度的策略時,需要重點考慮以下兩個方面:

(1)來自計算任務的應用級QoS需求.在ITSGrid中,不同的大規模應用計算任務往往具有不同的QoS需求,如CPU速度最快、可用內存最大、網絡延遲最小、使用費用最少等.

(2)來自ITSGrid系統的全局級QoS需求,通常反映為全局級的吞吐量和效率等指標.一般情況下, ITSGrid系統的全局級QoS需求可通過引入全局負載共享的機制來實現.

因此,在為ITSGrid設計資源調度算法時,需同時考慮以上兩個方面的需求,做到既尊重ITSGrid中各類計算任務的自定義QoS需求,又充分考慮ITSGrid系統本身的全局級QoS需求,根據ITSGrid資源負載情況,自適應地調整全局級QoS需求在分布式資源調度過程中的權重.

2.1 ITSGrid負載均衡評價模型

對于ITSGrid這種高復雜性、超大規模的綜合性網格,一個理想的資源調度系統應能在分布式資源調度過程中,將計算任務盡可能均衡地分配到ITSGrid中各個資源節點上,從而實現ITSGrid全局級的負載共享與均衡,保證系統整體性能的高效.由此可見,ITSGrid系統全局級負載的均衡程度是分布式資源調度效果的直接體現[5].在ITSGrid的資源調度系統中引入系統負載均衡評價技術,將有助于資源調度系統的自適應性,以實現ITSGrid全局級的負載共享與均衡.因此,系統負載均衡評價對ITSGrid的應用具有十分重要的意義.根據ITSGrid系統負載均衡評價的目的和要求,文中以ITSGrid中各個資源節點的負載情況為基礎,對ITSGrid系統負載均衡的評價進行建模.

定義1假設ITSGrid中的資源節點個數為n,每個資源節點在某一時刻的負載為li(0≤li≤1),分布式資源節點的負載指標可以根據需求自主選擇和組合,如資源節點的CPU利用率、內存利用率、數據庫連接池利用率和網絡帶寬利用率等.對應的ITSGrid資源節點負載集合可表示為L={l1,l2,…,ln},且ITSGrid的當前平均負載lavg可定義為

在式(1)中,0≤lavg≤1.系統負載均衡評價值可表示為

在式(2)中,0≤B≤0.5.當B=0時,表示系統當前的負載均衡程度處于最優狀態;當B=0.5時,則表示系統當前的負載均衡程度處于最差狀態.由此可見,系統負載均衡評價值B與系統負載均衡程度成反比.

由于B具有線性變化的特點,可以采用最小最大規格化方法[6]對B進行規范化處理.在經過規格化處理后,ITSGrid系統負載均衡評價值B就轉換成B′∈[0,1]區間.

2.2 ITSGrid資源節點滿意度評價模型

用下面3個定義構建資源節點滿意度評價模型.

定義2分布式資源的QoS參數q是從分布式資源的屬性中抽象而來的,可用一個二元組表示為q= {attr,v},其中,attr表示分布式資源的屬性名稱,v表示該資源屬性的當前值.理論上,分布式資源所有的屬性均可作為資源調度的QoS參數,然而在應用和實踐中,為了便于數學建模,一般要求選定的資源屬性是可測量的.

定義3QoS類別s為QoS參數的一個概念集合,可用一個三元組表示,即s={qcn,attr-set,w}.其中,qcn為QoS類別名稱;attr-set表示屬性集合,attr-set={attr1,attr2,…,attrm},其中,attrk為QoS參數中某一個具體的屬性,1≤k≤m;w表示QoS類別在分布式資源調度過程中所占的權重,即該QoS類別在資源調度過程中的重要程度,w∈[0,1].

定義4計算任務對分布式資源調度結果的滿意度評價模型M可用一個四元組表示,即M={Ri,Di, Ei,P}.其中,Ri表示被選中的資源節點實例;Di表示ri的資源屬性的數據,它可以包含多個數據項,每個數據項代表數據實例Di在滿意度評價過程中某一個QoS參數的取值;Ei為評價模型的輸出,用以保存Ri的滿意度評價結果;P為評價模型中組件間約束關系的集合.

2.3 GLBCQ分布式資源自適應調度算法

在進行資源調度的過程中,GLBCQ將在ITSGrid系統負載均衡QoS需求和計算任務自定義QoS需求之間進行適當的平衡,盡可能做到兩者兼顧,從而保證ITS應用計算的服務質量和ITSGrid的整體性能.

2.3.1 源數據的獲取

假設對計算任務T的QoS需求進行抽象,得到需求向量R=(r1,r2,…,rn),R∈attr-set,R中的每個rk(1≤k≤n)為所需資源的QoS參數取值.由此假設,ITSGrid中能滿足任務T的QoS需求的候選資源節點的集合N=(n1,n2,…,nm);針對N中的ni(1≤i≤m),假設需求向量R中的n個資源屬性值的資源屬性集向量yi=(yi1,yi2,…,yin);根據向量R和yi,計算出計算任務T對N中每一個候選資源節點的滿意度向量si=(si1,si2,…,sin)=

在計算滿意度向量過程中,為了降低調度算法的復雜度,采用絕對值把候選資源節點QoS滿意程度參數轉化為單調遞增的線性屬性.于是,k個si構成的矩陣mS=(s1,s2,…,Sk)T與候選資源節點的當前系統負載li共同組成GLBCQ算法的原始數據集,作為分布式資源調度器尋求最佳分布式資源節點的基礎.

2.3.2 源數據的預處理

在計算任務T的個性化QoS需求過程中,各個QoS參數分屬不同的數值類型,且取值范圍也各不相同.為了使得QoS參數在調度算法中的權重具有可比性,采用式(4)所定義的向量規范化方法對調度算法的源數據矩陣mS進行規范化,Sij被轉換為zij∈[0,1],矩陣mS={Sij},則被規范化為Z={Zij}.

經過規范化后,QoS滿意度參數的取值范圍被轉換到[0,1]區間.而候選資源節點的負載li的取值范圍原本就處于[0,1]區間,因此不需進行規范化操作.

2.3.3 權重調整

為了實現ITSGrid的系統負載共享與均衡,在GLBCQ算法中以候選資源節點的實時負載作為主要考慮的因素.然而,ITSGrid的系統負載均衡程度是動態變化的,這就要求資源調度算法必須適應這種動態性,同樣具有相應的靈活性.一般可以分為以下兩種情況:

(1)當ITSGrid的系統負載均衡程度較好時,調度算法就不需要過多地考慮系統負載共享與均衡因素,只需把如何滿足計算任務的個性化QoS需求放在首位.在GLBCQ算法中的處理方法為:降低分布式資源節點實時負載在調度算法中的權重.

(2)當ITSGrid的系統負載均衡程度較差時,調度算法在保證滿足計算服務個性化QoS需求的同時,還需重點考慮ITSGrid的系統負載的均衡因素.在GLBCQ算法中的處理方法為:提升分布式資源節點實時負載在調度算法中的權重.

由此可見,以ITSGrid的系統負載均衡評價值作為候選資源節點實時負載在GLBCQ算法中的權重,能夠較好滿足分布式資源調度算法的靈活性要求.由于系統負載均衡評價值B與系統負載均衡程度成反比,系統負載均衡評價值B越接近0,ITSGrid的系統負載均衡程度越好,而此時的候選資源節點的實時負載在調度算法中所占權重比例也越小.

2.3.4 候選資源節點滿意度評價模型

根據規范化的候選分布式資源節點的用戶滿意度矩陣Z,按照

計算出運行在候選資源節點ni上的計算任務T的QoS需求滿意度值.再利用vi、候選資源節點的實時負載li和負載均衡評價值B′,計算出候選資源節點ni的滿意度評價值為

為了實現ITSGrid系統負載動態的共享與均衡,GLBCQ算法需要從候選資源節點中優先選擇系統負載最輕的節點進行資源調度,在式(6)中,選擇用1-li和1-B′作為計算因子.另外,由于B′∈[0,1],為了避免B′以1-B′為0,因此增加經驗參數σ∈(0,1),σ通常為一個極小的常數.Ei可視為計算任務T將獲得資源服務QoS的預測[7].

2.3.5 GLBCQ算法框架

分布式資源自適應按需調度算法GLBCQ框架可用偽代碼描述如下:

Max_value=0;/*設定初始節點滿意度最大評價值為零*/

Satisfy_value=0;/*設定初始節點滿意度評價值為零*/

Selected_node=NULL;/*設定初始選中節點為空*/

Customed_QoS=task Analysis(ITS_task);/*解析ITS應用計算任務XML說明書,獲取自定義QoS需求*/

For(i=0;i＜Resource_number;i++){ /*Resource_number為ITSGrid中資源節點的總數*/

if(checkSatisfied(Resource_node[i],Customed_QoS)){/*檢查資源節點是否滿足計算任務的自定義QoS需求*/

dataPreprocess(Resource_node[i],Customed_QoS);/*按照式(4)預處理源數據*/

Satisfy_value=getSatisfaction(Resource_node[i]);/*按照式(5)和式(6)計算候選資源節點的滿意度評價值*/

if(Satisfy_value＞Max_value){

Max_value=Satisfy_value;

Selected_node=Resource_node[i];/*在已計算出的候選資源節點的滿意度評價值中,查找值最大的節點*/}

}

}

if(Selected_node!=NULL)

schedule Task2node(ITS_task,Selected_node)/*調度計算任務至滿意度評價值最大的資源節點*/

3 實驗與分析

為了測試文中構建的面向ITSGrid中計算服務的分布式資源調度管理模型的適用性和有效性,借助某校園的計算網格系統(Campus Grid,CG)、某公路勘察設計院的遙感計算中心(Remote Sensing Computing Center,RSCC)以及西安市交通警察支隊的道路交通監控系統(UTCS)中的交通管理(TMS)、交通信息服務(ISP)和交通規劃(PS)子系統,組成ITSGrid實驗仿真環境,其配置如表1所示.

表1 模擬ITSGrid計算節點的資源配置

每個模擬節點都安裝了支持實時應用集群(Real Application Clusters,RAC)的Oracle 10g數據庫,設置每個連接池的連接數量的最小值為5,最大值為100.用連接池的利用率來反映節點資源的利用情況.根據ITS資源需求頻度的歷史統計,從仿真ITSGrid環境選擇需求頻度最多的R1、R3、R4和R6,作為實驗所用的分布式資源節點.

從模擬ITSGrid的計算作業庫中,隨機挑選出資源需求及其QoS要求各異的50個ITS計算任務構成實驗所需的測試集.測試集在性能最好的節點R6上的執行時間少于50 h.通過ITSGrid的計算作業批處理模式,作業管理模塊在10 h內,隨機提交測試集中的全部計算作業.

作業調度策略庫內預置了3種資源調度算法:經典的OLB算法、MCT算法以及文中提出的GLBCQ算法.觀察在以上3種調度策略下,每個ITS節點的數據庫連接池的利用率、系統負載均衡評價值以及所有作業的調度運行信息(平均等待時間、成功率和按時完成率)的情況.觀察周期為50 h,取樣頻率為1次/h.

圖1中,在MCT算法主導的調度策略下,50個系統負載均衡評價值中的4個在0.10～0.20之間,表示系統負載均衡程度良好;44個在0.20～0.45之間,表示系統負載均衡程度一般;剩下的2個分布在0.45以上的區間里,表示系統負載均衡程度很差.在OLB算法主導的調度策略下,系統負載均衡評價值波動較大,在0.05～0.40之間隨機分布,其中分布在0.05～0.20區間的有18個,表示系統負載均衡程度良好;剩下32個都處于0.20～0.40之間,表示系統負載均衡程度一般.在GLBCQ算法主導的調度策略下,系統負載均衡評價值都分布在0.00～0.20之間,表示系統負載均衡程度良好.

圖1 模擬ITSGrid系統負載均衡評價

圖2 數據庫連接池的利用率

從圖2可見,與MCT和OLB資源調度算法比較,在GLBCQ算法主導的調度策略下,ITSGrid中各節點的資源利用率始終維持在75%以上,處于一個較高的水平,而且波動范圍較小.

從表2中的各項數據可見,構建的模型在3種調度算法的主導下,在作業的平均等待時間和作業成功率方面,GLBCQ算法優于MCT算法和OLB算法;在作業按時成功完成率方面,GLBCQ算法與MCT算法非常接近.

表2 測試作業集的作業調度信息

4 結束語

為了適應ITSGrid的發展,需要根據ITS分布式資源的不同應用場景選擇相應的資源調度策略.文中提出了一種自適應的資源調度算法GLBCQ,能夠根據ITS計算任務的自定義資源的需求、ITSGrid資源節點的負載情況以及ITSGrid系統負載均衡評價值,為應用任務從資源節點中選擇合適的節點.最后,仿真實驗結果表明,GLBCQ算法的有效性和實用性良好,能夠促進ITSGrid整體系統性能的提升.目前,該算法已經在文中所述的ITSGrid中得到具體部署和應用,取得的應用效果符合預期,證明了算法和策略的有效性.

[1] Xu Lin,Qu Shiru.A Resource Information Description Reference Model for ITSGrid[C]//Proceedings of the IEEE International Conference on Transportation,Mechanical&Electrical Engineering.Piscaaway:IEEE,2011:303-306.

[2] 劉宴兵,尚明生,肖云鵬.網格高性能調度及資源管理技術[M].北京:科學出版社,2010:94-95.

[3] Berman F,Casanova H,Chien A,et al.New Grid Scheduling and Rescheduling Methods in the Gr ADS Project[J]. International Journal of Parallel Programming,2005,33(2-3):209-229.

[4] 段富海,馬滿福.一種網格資源調度中QoS的最大化匹配算法[J].計算機應用,2010,30(1):108-110. Duan Fuhai,Ma Manfu.Maximum Matching Algorithm with QoSin Grid Resource Scheduling[J].Journal of Computer Applications,2010,30(1):108-110.

[5] Krzhizhanovskaya V V,Korkhov V V.Dynamic Load Balancing of Black-Box Applications with a Resource Selection Mechanism on Heterogeneous Resources of the Grid[C]//Parallel Computing Technologies.Heidelberg:Springer Press, 2007:245-260.

[6] Han J W,Kamber M.Data Mining:Concepts and Techniques[M].California:Morgan Kaufmann,2000:23-24.

[7] 彭飛,鄧浩江,劉磊.面向個性化服務推薦的QoS動態預測模型[J].西安電子科技大學學報,2013,40(4):174-180. Peng Fei,Deng Haojiang,Liu Lei.QoS-aware Temporal Prediction Model for Personalized Service Recommendation[J]. Journal of Xidian University,2013,40(4):174-180.

(編輯:齊淑娟)

Research on distributed resources scheduling strategy in the ITSGrid

XU Lin1,QU Shiru1,YU Bin2
(1.School of Automatic Control,Northwestern Polytechnical Univ.,Xi’an 710129,China; 2.School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

A distributed resource adaptive scheduling algorithm GLBCQ(Global Load Balance and Customed QoS)is proposed,which could take the customed QoS requirement of ITS computing tasks and current system load status of ITSGrid into account and select the optimal resources for the submitted tasks adaptively.Experimental result showed that compared to classical algorithms,GLBCQ has a higher efficiency and adaptability which could promote load balance and overall performance of the ITSGrid.

intelligent transportation system grid;resource scheduling algorithm;customed QoS requirement;system load

TP393

A

1001-2400(2014)03-0203-06

10.3969/j.issn.1001-2400.2014.03.031

2013-07-03< class="emphasis_bold">網絡出版時間:

時間:2013-11-22

國家自然科學基金資助項目(61172147);教育部博士點基金項目資助項目(20096102110027);航天科學創新基金資助項目(CASC201104)

徐 琳(1978-),男,西北工業大學博士研究生,E-mail:true-xulin@tom.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20131122.1628.201403.223_031.html