徐 琳,曲仕茹,鱼 滨

(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