徐 琳,曲仕茹,魚 濱

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

ITSGrid資源調(diào)度策略的研究

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

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

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

智能交通系統(tǒng)網(wǎng)格;資源調(diào)度算法;自定義服務質(zhì)量需求;系統(tǒng)負載

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

1 ITSGrid資源調(diào)度問題的特點

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

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

2 ITSGrid資源調(diào)度策略

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

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

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

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

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

2.1 ITSGrid負載均衡評價模型

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

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

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

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

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

2.2 ITSGrid資源節(jié)點滿意度評價模型

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

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

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

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

2.3 GLBCQ分布式資源自適應調(diào)度算法

在進行資源調(diào)度的過程中,GLBCQ將在ITSGrid系統(tǒng)負載均衡QoS需求和計算任務自定義QoS需求之間進行適當?shù)钠胶?盡可能做到兩者兼顧,從而保證ITS應用計算的服務質(zhì)量和ITSGrid的整體性能.

2.3.1 源數(shù)據(jù)的獲取

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

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

2.3.2 源數(shù)據(jù)的預處理

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

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

2.3.3 權重調(diào)整

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

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

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

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

2.3.4 候選資源節(jié)點滿意度評價模型

根據(jù)規(guī)范化的候選分布式資源節(jié)點的用戶滿意度矩陣Z,按照

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

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

2.3.5 GLBCQ算法框架

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

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

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

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

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

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

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

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

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

if(Satisfy_value＞Max_value){

Max_value=Satisfy_value;

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

}

}

if(Selected_node!=NULL)

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

3 實驗與分析

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

表1 模擬ITSGrid計算節(jié)點的資源配置

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

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

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

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

圖1 模擬ITSGrid系統(tǒng)負載均衡評價

圖2 數(shù)據(jù)庫連接池的利用率

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

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

表2 測試作業(yè)集的作業(yè)調(diào)度信息

4 結束語

為了適應ITSGrid的發(fā)展,需要根據(jù)ITS分布式資源的不同應用場景選擇相應的資源調(diào)度策略.文中提出了一種自適應的資源調(diào)度算法GLBCQ,能夠根據(jù)ITS計算任務的自定義資源的需求、ITSGrid資源節(jié)點的負載情況以及ITSGrid系統(tǒng)負載均衡評價值,為應用任務從資源節(jié)點中選擇合適的節(jié)點.最后,仿真實驗結果表明,GLBCQ算法的有效性和實用性良好,能夠促進ITSGrid整體系統(tǒng)性能的提升.目前,該算法已經(jīng)在文中所述的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] 劉宴兵,尚明生,肖云鵬.網(wǎng)格高性能調(diào)度及資源管理技術[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] 段富海,馬滿福.一種網(wǎng)格資源調(diào)度中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動態(tài)預測模型[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">網(wǎng)絡出版時間:

時間:2013-11-22

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

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

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