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

《云计算中关于任务调度优化策略的研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

云计算中关于任务调度优化策略的研究全力傅明长沙理工大学计算机与通信工程学院基于蚁群算法的任务调度会遇到负载不均衡与收敛速度变慢的问题，针对蚁群算法应用于任务调度机制吋存在的缺陷，通过赋予权重的方法对该算法的信息素更新规则进行改进，加快求解速度，利用动态更新挥发系数优化算法的综合性能，并在局部信息素的更新过程中，引入虚拟机负载权重系数。实验结果表明，基于改进算法的任务调度策略在保证任务得到合理分配的同时，算法的收敛速度与总执行时间得到了优化。关键词：蚁群算法;信息素;虚拟机;权重系数;收敛速度;云计算屮需要处理的任务被调度分配到在各个计算资源屮，用户可以通过云计算按照需求获取计算与信息服务，以及高效的存储服务m。任务调度作为云计算的核心技术，在云计算处理任务的过程中，任务调度是不可避免的重要环节之一，因此，优化任务调度机制是强化云计算综合性能的重要方法。为了更有效的改善云计算的服务性能，不少学者针对云计算中的任务调度机制所遇到的问题展开丫研宄。文献［3］以提高云计算服务质量为棊础，通过对蜂群算法的改进，能够在一定程度提高算法的全局搜索能力，并且能够有效地满足QOS需求，文献［4］引入局部搜索算子对蜂群算法进行优化，能够有效的缩短任务的完成时间，文献［5］利用蚁群算法对云计算任务调度系统进行改善，能够较好的在多个方面提高系统性能，文献［6］针对任务调度过程中虚拟机负载的问题,利用蚁群算法较好的反馈机制提出蚁群优化算法，能够较好的改善资源利用率，文献［7］利用遗传算法较好的搜索能力能够有效地改善任务调度的性能，使虚拟机达到负载均衡，文献［8］利用遗传算法前期搜索能力强的优势与蚁群算法的信息反馈的特点，将两种算法相结合来弥补各自的问题，该算法在改善收敛速度的同时满足用户所要求的服务质量，文献［9］对遗传算法中的交叉和变异的概率公式进行优化，提高了全局搜索能力，文献［10］针对云计算屮任务调度需要多个目标优化的问题，提出了改进的Memetic算法，该算法能够较快的找到全局最优解，计算效率得到了提高。本文针对蚁群算法中收敛速度慢与任务分配不均的问题，结合调度机制的特点对蚁群算法的信息素更新方法进行优化，通过对信息素增量赋予权值，改进算 法的计算效率，并采用挥发系数动态调整的方法，提高算法的搜索能力，在进行局部信息素更新时，加入衡量虚拟机工作负载的权重系数，保证虚拟机的负载均衡，实验表明，本文设计的改进算法能更快的找到全局最优解，并且在任务得到合理分配的同时，缩短了总执行时间。2任务调度模型云计算在处理任务时，任务需要被合理地分配到各个计算资源中，其任务调度机制可以表示为:通过任务调度策略将需要处理的任务分配到异构的资源上，使全部任务在被执行完成之后所需时间最少并满足负载均衡，本文考虑的问题是将N个和互独立、不同大小的仔务根据仔务调度算法分配到M个性能不同的虚拟机进行并行计算，根据虚拟机处理任务吋的性能指标得出实验结果。2.1模型定义在云计算调度模型屮需要处理的作业为N个互不关联的任务，N个任务集合表示为:Task={tut2，t3，…，tn},MI表示任务的指令长度，其中ML表示任务t,的指令长度［11］。处理任务的异构资源为M个虚拟机，虚拟机集合表示为VM={v,,v2,v3,vj,MIPS表示虚拟机的执行速度，其中MIPS」表示虚拟Wv：的执行速度［12］。为丫计算每个任务在不同虚拟机上所需要的处理时间，定义执行时间矩阵T，矩阵表示为：其中1^~表示表示虚拟机Vj处理任务ti所需要的执行时间，并H根据虚拟机与任务的匹配关系建立矩阵x［i］［j］，表示任务it是否分配给虚拟机Vj，定义为：通过计算任务完成的总执行时间，对虚拟机的执行效率进行评估，为丫计算总执行时间，定义时间集合C={ci，C2,C3,•…，CE}，Cj表示虚拟机Vj完成分配 的任务所需要的执行时间，其中。由于虚拟机在处理任务时采用并行计算[13]，因此，任务完成的总执行时间表示为：，m表示虚拟机的1D号。负载均衡度作为衡量虚拟机工作效率的关键指标[14],定义为：，其中表示每台虚拟机完成任务的平均执行时间，负载均衡度表示为任务执行吋间标准差。3云计算任务调度策略3.1基于蚁群算法的调度模型蚁群算法作为一种全局优化算法，一般被用来解决路径优化的问题，该算法具有分布性、随机性、反馈性等特点，在云环境中利用蚁群算法的特点能够有效的处理任务调度机制所遇到的问题。在应用蚁群算法解决任务调度问题的过程屮，首先根据虚拟机对每个任务的处理能力，对信息素Tu(t)与启发函数Hu(t)进行初始化，并对任务集合E初始化，kE表示第k只蜗蚁可以选择的任务集合，Ek={tbt2,t3,•…，tn},根据信息素浓度与启发函数计算任务与虚拟机的配对概率P,」(t):allowedk表示第k只妈蚁可以选择的虚拟机集合，allowedk={v,,v2,v3,••vj,Pu(t)表示第t次迭代时，蚂蚁K将任务ti分配給虚拟机久的概率。启发函数表达式为：Hu(t)=1/Dij,Dfl/timeij表示为虚拟机Vj对任务ti的执行时间，执行吋间越小启发函数nu(t)越大。在完成一次迭代之后，根据虚拟机与任务的配对情况，对信息素T(t)进行更新，表达式为：Td(t)表示在t吋刻虚拟机Vj与任务^配对的信息量，信息素挥发系数P 表示为信息素的积累程度，目的是防止某些信息素在累加过程屮积累过多，提高搜索范围，丰富解的多样性［15］。AtN(t)表示在本次迭代之后虚拟机Vj与任务^配对的信息素增量式，为:其中。最优解Fbest的表达表示第t次迭代的全局最优解，其物理意义为任务完成的时间，n表示蚂蚁的数量。3.2任务调度算法的优化蚁群算法在解决任务分配的问题时，对任务的分配采用随机选择的方法，影响了算法的搜索能力，使算法需要更多的迭代才能得到最优分配方案，因此就会出现收敛速度变慢的问题，虽然通过正反馈机制可以强化较优的解，但会导致停滞现象。针对这些问题，本文通过对信息素增量△t(t)赋予权值的方法，改变全局信息素的更新规则，并依据迭代次数的增加更新挥发系数P的参数值，改善了算法的综合性能。3.2.1信息素的更新为了更好的利用最优解的信息，使算法得到较好的性能，在每次迭代完成之后，将每只蚂蚁所形成的解按照从小到大排序，表示为F:(t)