混合云环境下考虑工作流的任务调度策略

翟青海, 谢晓兰

(桂林理工大学 a.信息科学与工程学院; b.广西嵌入式技术与智能系统重点实验室, 广西 桂林 541006)

0 引 言

云计算技术有低成本、 配置灵活和资源利用率高的特点, 正在以极快的速度兴起。云计算的计算中心由一系列的异构网络服务和计算资源组成[1]。在云计算领域中, 任务调度策略对用户的任务执行效率以及云环境下资源的使用效率有十分重要的作用。任务调度就是根据当前的目标要求, 将不同的任务调度到合适的资源上, 建立适当的任务执行顺序, 使得该调度策略尽可能满足当前目标要求。

混合云是一种将私有云资源和公有云资源结合起来使用的云计算环境[2]。但是由于安全性因素, 企业不希望将一些数据放至公有云上托管。而混合云模式则既可以提供私有云的安全性以达到对敏感数据的安全保证, 又可以利用公有云庞大的计算资源处理非关键任务和数据。因此， 研究混合云下的任务调度具有重要意义。

针对云计算环境下的工作流调度问题, 许多研究者将元启发式算法引入到云任务调度中, 元启发式优化算法可以降低搜索空间的复杂性并且算法运行的时间也可以接受。罗智勇等[3]提出了一种面向云计算的花朵差分授粉工作流算法, 该算法将工作流任务和虚拟机建模成花粉, 将完整的调度序列建模成花朵, 再利用任务的偏序关系进行离散花朵授粉过程。Singh等[4]提出了基于蚁群算法的混合云工作流调度模型, 在满足任务的最低期限的基础上, 降低任务的执行成本。徐俊等[5]提出了基于混合蛙跳算法的调度优化策略, 该算法利用时间贪心算法来优化初始种群以提高搜索效率, 同时增加对局部最优个体的重建策略跳出局部最优, 增加全局搜索能力， 由于使用贪心算法提高了初始化种群质量, 使得算法搜索耗时缩短。黄婷婷等[6]提出了基于模拟退火和遗传算法结合的多目标优化算法, 首先利用任务的影响程度生成合适的初始化种群; 再对交叉、 变异等遗传操作产生的个体分别进行模拟退火操作, 避免引起早熟收敛问题； 最后在变异阶段引入失败率, 提高调度结果的可靠性。针对混合云环境下的任务调度问题, Sanaj等[7]提出了在混合云环境下保证服务完成时间的基础上最大化私有云利润的鲸鱼优化算法, 该算法相对人工蜂群和遗传算法具有更高的效率。Zhou等[8]提出了两种有效的混合云工作流调度方法, 既考虑了完成时间又考虑了完成成本: 单目标工作流调度优化方法用于优化截止期约束下的完成成本, 多目标工作流调度优化方法用于同时优化完成时间和完成成本。

本文根据混合云环境下的工作流调度问题特点建立了相关问题模型, 借鉴黏菌算法(slime mould algorithm,SMA)和粒子群算法(particle swarm optimization,PSO)的思想对算法进行重新设计: 当黏菌个体解的质量较差时, 有较大概率保留全局最优解的特征, 加快较差解的收敛速度; 当解的质量较好时, 则进行局部变异, 避免陷入局部最优; 同时, 加入了交叉算子解决当任务调度问题中解空间较大时, 局部寻优粒度不够的问题。

1 混合云环境下工作流调度模型

1.1 混合云的相关定义

1)混合云模型: 目前, 越来越多的公有云厂商和私有云厂商向混合云转型。如果企业和用户最终需要同时访问本地和云服务提供商提供的资源, 则使用混合云模型, 即选择同时使用公共云和私有云。

私有云作为企业或个人所独有的专有云平台, 其规模相对公有云而言不会很大, 因此提供的各类资源一般比较有限。而公有云是由云服务提供商架设好大规模的IT基础设施, 通过互联网为企业提供服务器、 存储、 应用程序等租用服务。公有云通常是指可以同时提供大量的虚拟机实例供用户使用的云平台。因此, 本文假设公有云总有足够的资源处理任务, 并且每一个任务都在不同的虚拟机上执行。

2)计费模型: 公有云资源由公有云提供商提供, 云服务提供商会根据其向用户提供的资源收取一定的费用。2017年, 微软、 亚马逊和阿里云等服务商实现了按秒计费[9], 不需要将虚拟机的启动时间和销毁时间计算在内。 而私有云为企业个体所有, 数量有限, 但是基本不需要考虑使用费用的问题。因此, 本文混合云的计费方法仅考虑公有云的收费, 计算方法为

(1)

其中:pricej表示公有云资源j的单位价格；Start_Timei表示任务i的运行开始时间;End_Timei表示任务i的运行结束时间。Start_Timei和End_Timei的计算方式如式(4)和式(5)。

1.2 工作流的相关定义

1)虚拟机模型: 服务商一般采用虚拟机进行抽象表示其计算资源, 用户可以租用虚拟机执行工作流任务, 虚拟机可以用六元组M={id,ispublic,type,mip,costper,ram}表示。其中:id表示虚拟机的标识;ispublic表示该虚拟机是否属于公有云;type表示虚拟机的型号; 同一型号的参数mip、costper、ram值相同,mip为虚拟机的运算能力,costper为租用虚拟机的单位时间费用,ram为虚拟机的内存。

2)任务模型: 任务采用六元组表示N={id,task_length,size,depth,parent_task_list,child_task_list}。 其中,id表示任务的标识；task_length表示任务的操作指令数；size表示任务的存储大小；depth表示任务在工作流当中的深度层级, 如图1所示, 任务之间的执行顺序可以用有向无环图(DAG)表示, 图中共有6个任务, 并且任务1的深度为1, 任务2、 3、 4、 5的深度为2, 任务6的深度为3；parent_task_list表示当前任务的上一个深度的任务集合；child_task_list表示当前任务的下一个深度的任务集合。

图1 任务深度

3)执行时间Texe(ti,mj)表示工作流中任务ti在虚拟机mj上的执行时间

Texe(ti,mj)=task_lengthti/mipmj,

(2)

其中,mipmj表示虚拟机mj的处理能力。

4)传输时间Ttrans(ti,tk)表示任务ti和任务tk之间的数据传输时间, 可由式(3)计算得出。当任务ti和任务tk处于同一个虚拟机时, 则传输时间为0。

(3)

其中:sizeti表示任务ti的传出数据大小;Bwi和Bwk分别表示任务ti和任务tk所在虚拟机的带宽。

5)任务ti的实际开始时间Start_Timei的计算方式如式(4)所示。当该任务没有父节点时, 则为起始节点, 开始时间为0； 否则， 需要等待该任务的所有父节点任务执行完成并将数据传输至该任务所在的虚拟机上才能开始执行。

(4)

6)任务ti的完成时间End_Timei表示任务ti在对应虚拟机上的完成时间

End_Timei=Start_Timei+Texe(ti,mj)+Ttrans(ti,child)。

(5)

1.3 多目标模型

假设有n个任务Task={t1,t2, …,tn},m个虚拟机vm={vm1,vm2, …,vmm}, 则关于调度目标模型如下:

1)调度时间Tmakespan, 表示整个工作流的调度执行时间, 即为最后一个任务计算完成的时间和第一个任务开始的时间差

Tmakespan=End_Timelast-Start_Timefirst。

(6)

2)执行费用cost, 表示完成整个工作流任务所需要的执行花费

(7)

costperj表示租用虚拟机j的费用。

3)多目标优化, 适应度是评价智能算法解优劣程度的重要指标, 由于本模型的目标是使调度时间Tmakespan和执行费用cost尽可能小, 因此适应度函数可以由调度时间和完成成本计算

Fitness=w1Tmakespan+w2cost,

(8)

w1、w2分别为调度时间和执行费用的权重, 且满足w1+w2=1。在本文中, 适应度值Fitness越小, 表示解的质量越好。

1.4 编码模型

参考文献[2]的编码方法解决混合云环境下的工作流调度编码问题。一个可行解的调度方案如式(9)所示, 由3条染色体编码组成

scheduler=(task_order,vm_order,vm_type),

(9)

3条染色体都由一个一维数组表示, 由于一个任务最多可放置在一个虚拟机上, 且本文定义公有云资源数量为无限多, 因此3个数组长度都相同, 长度为参与该次调度过程的任务数量。task_order表示任务的调度顺序, 数组中每个值表示任务的id, 该数组表示具有依赖关系的调度顺序；vm_order表示每个任务到虚拟机的映射关系, 数组中每个值表示虚拟机的id；vm_type表示每个虚拟机对应的虚拟机型号。

2 算法流程

2.1 黏菌算法

黏菌算法是根据黏菌在寻找食物过程中的变化建立的智能搜索算法。主要模拟黏菌在觅食过程中的行为和形态变化, 通过权值指标模拟黏菌静脉状管的形态和收缩模式之间的3种相关性[10]。在黏菌觅食过程中, 根据空气中的食物浓度接近食物, 食物浓度越高, 生物振荡波越强, 细胞质流动越快, 黏菌静脉状管越粗, 该区域会聚集更多黏菌; 当该区域的食物浓度较低时, 黏菌会有较大概率探索其他区域。黏菌接近食物的表达式

(10)

p=tanh|S(i)-DF|;

(11)

a=arctanh(-t/tmax)+1)。

(12)

(13)

式中:r为[0, 1]间的随机数;bF表示在当前迭代过程中最佳的适应度;S(i)表示当前个体适应度值;wF表示在当前迭代过程中最差的适应度值;i=C表示种群中适应度值最好的前一半个体;i=O表示其余个体;Sort(i)按照适应度值排序的气味指数。

当黏菌找到了更好的食物, 仍然会分离出部分个体探索其他区域进行全局寻优, 黏菌种群更新位置的计算方法为

(14)

rand是[0, 1]间的随机数,LB与UB表示解空间的上下边界,z是进行全局寻优的阈值。

2.2 本文算法设计

由于传统的黏菌算法和粒子群算法都是用于连续的数值优化, 进行迭代计算的都是实数, 但是工作流调度问题都是组合优化问题, 解由3组整数序列组成, 因此， 本文对算法进行重新设计。本文工作流调度算法的基本思想如下: 首先随机初始化符合工作流执行序列的初始种群, 计算种群中个体的适应度值, 并确定最佳的适应度值, 之后采用交叉算子对每个个体进行计算, 计算个体的适应度值判断是否进行粒子群优化全局寻优或局部变异， 最后标识出当前种群中的最优个体Gbest。算法的主要符号说明如表1, 具体步骤如下。

表1 主要符号说明

步骤1:按照算法1初始化种群, 并计算每个个体的适应度值和当前最优个体Gbest。

算法1 种群初始化算法INPUT: 工作流任务集合G, 种群规模NPOUTPUT: 相应规模的个体种群pop1.init i=02.while i

步骤2:按照文献[2]的做法更新任务调度顺序task_order。

步骤3:每个个体的vm_type根据算法2进行交叉计算, 其中v和b的计算方法为

v=|-b+(2·b)·r|;

(15)

b=0.25-iter/(max_iter·4)。

(16)

其中:r表示区间[0, 1]内的随机值;iter表示当前迭代次数;max_iter表示最大迭代次数；v表示交叉的位点个数, 随着迭代次数的增加而逐渐变小, 细化局部寻优的粒度进而增加算法的局部寻优能力。

算法2 交叉算法INPUT: 交叉个体X, 较优个体XbOUTPUT: 交叉个体X’1.按照式(15)计算交叉位点个数num2.init start=random(0, T_length-num)3.init end=start+num4.while start

步骤4:按照式(17)判断个体的vm_type迭代方式, 其中r表示区间[0, 1]内的随机值, 当解的质量较差时, 则有较大概率按照算法3进行迭代, 这样可以在前期加快全局寻优的速度。p值的计算方法为式(18), 在算法3中个体的速度值Vel按照式(19)和式(20)进行计算。由于个体位置vm_type的值为离散型变量, 采用相减的计算方法意义不大, 因此， 本文采用与运算处理离散型变量加快解的收敛速度。

(17)

p=tanh|best_fitness-fitness(X(j))|;

(18)

(19)

(20)

其中：c1和c2分别表示全局最优解和个体最优解的权重;best_fitness表示全局最优解的适应度值;fitness(X(j))表示当前个体j的适应度值;xg和xb分别表示全局最优解的vm_type和个体中最优解的vm_type。

算法3 全局寻优算法INPUT: 全局寻优个体X, 全局最优个体Xg, 个体最优XbOUTPUT: 全局寻优个体X’1. init j=02. while j

在算法4变异算法中,v和b的计算方式如式(15)和式(16)。由于解空间很大, 因此算法4并没有对所有位点进行变异,而是基于较优的个体选择局部位点进行变异。

算法4 局部变异算法INPUT: 局部变异个体XOUTPUT: 局部变异个体X’1.按照式(15)计算交叉个数num2.init j=0, x=[num]3.while j

步骤5:按照式(8)计算每个个体的适应度。

步骤6:更新当前迭代全局最优解和个体在迭代中的最优解,并判断是否达到最大迭代次数,若未达到,则继续从步骤2开始执行；若达到最大迭代次数,则停止搜索, 当前的全局最优解即为最终结果。

3 实验与结果分析

为验证本文设计算法在处理混合云环境下考虑工作流任务调度问题的有效性和可行性, 使用WorkflowSim作为仿真平台, 在同样的条件和环境下实验, 并和经典的粒子群算法、 遗传算法以及文献[11]的算法进行对比。设置10种虚拟机类型,虚拟机配置参考亚马逊的类型[12](表2),带宽速度设置为0.02 GB/s,存储费用为0.000 1 ＄/(GB·h)。实验设置迭代次数为1 000次,w1、w2为0.5, 种群个体数为60, 私有云虚拟机数占总虚拟机数的1/5。实验采用4种科学工作流模型, 即模型Epigenomic、

表2 虚拟机配置

Inspiral、 Montage和 Sipht。将这4种工作流的数据集进行优化调度, 各类算法在不同数据集和不同任务数量的完成时间和完成成本如图2—4所示。随着任务数量的增加, 由于遗传算法的全局寻优能力较低, 因此性能普遍较低, 而文献[11]的改进算法相对于遗传算法和粒子群算法这两种算法效果都要好。但是在任务数量较多时, 由于本文的算法有更细粒度的局部寻优能力, 因此在4种数据集上的整体表现都优于其他3种算法。

图2 50个任务完成时间(a)和完成成本(b)

图3 100个任务完成时间(a)和完成成本(b)

图4 1 000个任务完成时间(a)和完成成本(b)

4 结束语

本文以黏菌算法为基本的研究思路, 在算法前期借鉴了粒子群算法的思想, 加快全局寻优速度, 同时增加了交叉算子提高局部寻优的粒度, 在算法迭代后期通过变异算子, 避免陷入局部最优。从实验仿真结果看, 随着任务数量的增加, 本文算法的寻优能力比其他算法更优。但是, 本文算法依然存在有待改进的地方, 如当某一个任务的属性值和其他任务有明显差异时, 该任务的分配结果会显著影响算法寻优, 后续将针对该问题进行研究。