云计算中任务调度优化策略的研究

全 ,

(长沙理工大学 计算机与通信工程学院,长沙 410114)

0 概述

云计算是互联网计算发展的新革命,相比于分布式计算其具有更突出的优势,它是一种高效率的多功能计算系统[1],大规模的计算资源确保了云服务的高效性。云计算中需要处理的任务被调度分配到在各个计算资源中,用户可以通过云计算按照需求获取计算与信息服务,以及高效的存储服务[2]。任务调度作为云计算的核心技术,在云计算处理任务的过程中,任务调度是不可避免的重要环节之一,因此,优化任务调度机制是强化云计算综合性能的重要方法。

为了更有效地改善云计算的服务性能,有学者针对云计算中的任务调度机制所遇到的问题展开了研究。文献[3]以提高云计算服务质量为基础,通过对蜂群算法的改进,能够在一定程度上提高算法的全局搜索能力,并且能够有效地满足QoS需求;文献[4]引入局部搜索算子对蜂群算法进行优化,能够有效地缩短任务的完成时间;文献[5]利用蚁群算法对云计算任务调度系统进行改善,能够较好地在多个方面提高系统性能;文献[6]针对任务调度过程中虚拟机负载的问题,利用蚁群算法较好的反馈机制提出蚁群优化算法,能够较好地改善资源利用率;文献[7]利用遗传算法较好的搜索能力能够有效地改善任务调度的性能,使虚拟机达到负载均衡;文献[8]利用遗传算法前期搜索能力强的优势与蚁群算法的信息反馈的特点,将2种算法相结合来弥补各自的问题,该算法在改善收敛速度的同时满足用户所要求的服务质量;文献[9]对遗传算法中的交叉和变异的概率公式进行优化,提高了全局搜索能力;文献[10]针对云计算中任务调度需要多个目标优化的问题,提出了改进的Memetic算法,该算法能够较快地找到全局最优解,提高了计算效率。

本文针对蚁群算法收敛速度慢与任务分配不均的问题,结合调度机制的特点对算法中信息素更新方法进行优化,通过对信息素增量赋予权值,改进算法的计算效率,并采用挥发系数动态调整的方法,提高算法的搜索能力,在进行局部信息素更新时,加入衡量虚拟机工作负载的权重系数,保证虚拟机的负载均衡。

1 任务调度模型

云计算在处理任务时,任务需要被合理地分配到各个计算资源中,其任务调度机制可以表示为:通过任务调度策略将需要处理的任务分配到异构的资源上,使全部任务在被执行完成之后所需时间最少并满足负载均衡。本文考虑的问题是将N个相互独立、不同大小的任务根据任务调度算法分配到M个性能不同的虚拟机进行并行计算,根据虚拟机处理任务时的性能指标得出实验结果。

在云计算调度模型中需要处理的作业为N个互不关联的任务,N个任务集合表示为:Task={t1,t2,…,tn},MI表示任务的指令长度,其中MIi表示任务ti的指令长度[11]。处理任务的异构资源为M个虚拟机,虚拟机集合表示为VM={v1,v2,…,vm},MIPS表示虚拟机的执行速度,其中MIPSj表示虚拟机vj的执行速度[12]。

为计算每个任务在不同虚拟机上所需要的处理时间,定义执行时间矩阵为:

其中,timeij表示表示虚拟机vj处理任务ti所需要的执行时间,并且timeij=MIi/MIPSj。

根据虚拟机与任务的匹配关系建立矩阵x[i][j],表示任务ti是否分配给虚拟机vj,定义为:

2 云计算任务调度策略

2.1 基于蚁群算法的调度模型

蚁群算法作为一种全局优化算法,一般被用来解决路径优化的问题,该算法具有分布性、随机性、反馈性等特点,在云环境中利用蚁群算法的特点能够有效地处理任务调度机制所遇到的问题。

(3)

在完成一次迭代之后,根据虚拟机与任务的配对情况,对信息素τij(t)进行更新,表达式为:

τij(t+1)=ρ·τij(t)+Δτij(t)

(4)

2.2 任务调度算法的优化

蚁群算法在解决任务分配的问题时,对任务的分配采用随机选择的方法,影响了算法的搜索能力,使算法需要更多的迭代才能得到最优分配方案,因此,会出现收敛速度变慢的问题,虽然通过正反馈机制可以强化较优的解,但会导致停滞现象。针对这些问题,本文通过对信息素增量Δτij(t)赋予权值的方法,改变全局信息素的更新规则,并依据迭代次数的增加更新挥发系数ρ的参数值,改善了算法的综合性能。

2.2.1 信息素的更新

为了更好地利用最优解的信息,使算法得到较好的性能,在每次迭代完成之后,将每只蚂蚁所形成的解按照从小到大排序,表示为F1(t)≤F2(t)≤…≤Fm(t),利用解的大小对信息素增量赋予不同的权值,最优解的权值最大。最优解的权值大小为a,当全部的蚂蚁进行完一次迭代之后,利用赋予信息素增量权值的方法对信息素做全局更新:

(6)

负载均衡是衡量任务调度算法的重要指标,针对负载均衡的问题,在信息素的更新规则中,通过加入局部信息素的更新方法来保障任务调度的负载均衡。局部信息素的更新方法定义为:每完成一次任务与虚拟机的配对之后,将引入局部信息素,并依据虚拟机的运行时间对其进行更新,更新规则为:

2.2.2 自适应调整策略

信息素挥发系数ρ的数值设定是否合理将会影响算法选找最优分配方案的搜索能力与计算效率[16],通过动态地改变ρ的值,从而能自适应地调整信息素的大小,因此,可以有效地加强算法前期的搜索能力,丰富解的多样性,并随着迭代次数的增加,最优分配方案的概率得到提高,保证了算法的综合性能,挥发系数ρ的调整策略为:

ρa(t)=1-ln(t)/ln(t+c)

(9)

其中,C为常数,挥发系数ρ的大小限制在[ρmin,ρmax],使ρ的值不会因为过大或过小,而导致求解效率变慢或者搜索能力变弱,保证了算法的综合性能。

2.3 算法的实现过程

算法实现过程如下:

1)初始化启发函数ηij(t)、信息素τij(t)、最大迭代次数tmax、蚂蚁数量n。

3)更新蚂蚁k的任务禁忌表tabuk,如果蚂蚁k将任务ti分配给虚拟机vj,则将任务ti加入禁忌表tabuk,更新任务集合Ek,如果任务集合Ek为空,则执行下一步,否则将跳转到第2步。

5)全局信息素的更新,根据式(5)对全局最优解进行更新,判断是否为最大迭代次数,如果t≥tmax,则结束算法,否则t++、k=1并跳转到第2步。

算法伪代码如下:

1.initialize ηij(t),τij(t),tmax,n,t←1;

2.while t≤tmax

3.initialize k←1,tabuk,Ek;

5.if k≤n

6.while Ek≠φ

8.update tabuk,Ek;

9.end while

10.update τij(t) by式(7);

11.calculate Fk(t);

13.k++;

14.end if

15.update τij(t) by式(6);

17.update Fbestby式(5);

18.t++;

19.end while

3 实验结果与分析

实验选择云计算仿真器CloudSim对任务调度实验进行仿真,CloudSim是一种可扩展、通用的仿真框架,能够对云计算任务调度实验进行模型建立和仿真模拟。实验对本文设计的改进蚁群算法与Min-Min算法、基本蚁群算法进行仿真,并比较3种不同算法的实验结果。

1)Min-Min算法

采用Min-Min算法处理任务调度的过程为:通过计算每个虚拟机处理不同任务时所需要的完成时间,选出每个任务所需完成时间的最小值,根据最小值的大小将任务进行排序,按照由小到大的顺序依次分配任务,因为Min-Min算法只考虑任务被完成的时间为优化目标,所以会导致任务分配不合理的问题。

2)蚁群算法

在应用蚁群算法解决任务调度问题的过程中,首先根据虚拟机对每个任务的处理能力,计算任务与虚拟机的配对概率,由蚂蚁根据配对概率对任务进行分配,完成一次迭代之后,更新目标解与信息素,在算法完成收敛时得到目标解。由于随机选择的方法与反馈机制的原因,因此会导致收敛速度变慢与早熟现象。

参数设置:需要处理的任务个数分别设为40、60、80、100和120,任务的指令长度为5 000 MI～50 000 MI,虚拟机数量为8,执行速度为1 000 MIPS～2 000 MIPS。根据文献[6,17],并通过多次实验进行测试仿真,对算法参数进行设置,算法参数如表1所示。

表1 任务调度算法参数

为了验证改进蚁群算法应用于云任务调度时的收敛速度,实验方案设置为:对于不相同的任务个数,分别计算改进蚁群算法与基本蚁群算法2种方案,找到最优解时的迭代次数,虚拟机的个数为8。每组数据为10次实验的平均值,实验结果如图1所示。

图1 算法的迭代次数

图1的仿真结果表明:改进蚁群算法完成收敛所需的迭代次数低于基本蚁群算法,因为本文通过结合调度机制的特点对信息素的更新规则进行优化,通过对信息素增量Δτij(t)赋予权值的方法,加快算法的求解速度,并对挥发系数的值进行动态更新,随着迭代次数的增加,提高最优目标解的概率,进一步加快算法的计算效率,收敛速度得到提高,因此改进蚁群算法相比于基本蚁群算法能够更快地找到最优解,算法性能得到较好地改善。

图2为在任务个数不相同的情况下,基于3种不同调度算法虚拟机完成任务所需要的总执行时间的对比。

图2 不同算法的任务完成时间

通过对3种算法的对比,改进蚁群算法根据解的大小作为信息素更新时的权值,并依据迭代次数的大小计算挥发系数,使算法的全局搜索能力得到加强,丰富解的多样性,最终解的大小更优,因此,总执行时间更快,与Min-Min算法、基本蚁群算法相比分别减少了16%～29%、10%～17%。

图3 不同算法的负载均衡情况

由于Min-Min算法只把总执行时间作为优化目标,因此负载均衡度最差,本文设计的改进蚁群算法根据虚拟机的运行情况对局部信息素进行更新,优化了虚拟机处理任务时的负载均衡,对比基本蚁群算法,虚拟机工作的负载均衡效果更好。

4 结束语

通过蚁群算法处理云计算中的任务时,会遇到求解速度慢和负载不均衡的问题,本文通过添加权值的方法对信息素更新规则进行改进,利用每只蚂蚁所生成的解作为信息素增量的权重,加快算法在选择匹配方案时的求解效率,并采用动态更新挥发系数的方法,根据迭代次数自适应地对权值进行更新调整,提高算法的全局搜索能力,丰富解的多样性,改善了算法的收敛性,保证算法的综合性能。在对局部信息素更新时,加入衡量虚拟机负载的权重系数,使任务得到合理分配。实验结果表明,本文设计的改进算法能够较快地得到最优解,与Min-Min算法和基本蚁群算法相比,任务的总执行时间与负载问题得到了改善。为了更好地提高调度机制的综合性能,下一步将研究具有关联性的云任务调度与能耗优化问题。