基于混合式启发的云计算任务调度算法_李丹丹.pdf

安阳工学院学报Journal of Anyang Institute of Technology Vol.22 No.2（Gen.No.122）Mar.,2023第22卷第2期（总第122期）2023 年 3 月DOI:10.19329/ki.1673-2928.2023.02.014基于混合式启发的云计算任务调度算法李丹丹（三门峡职业技术学院，河南 三门峡 472000）摘 要：为了进一步降低云计算中的任务最大完成时间并提升负载均衡能力，提出了一种综合遗传算法、Max-Min 算法以及 Min-Min 算法的混合式启发任务调度算法。首先，遗传算法通过染色体编码针对云计算中的任务和计算资源进行表征；然后，将新的染色体信息与每个任务的最大执行时间和最小执行时间的平均值作比较，从而决定对应任务应使用 Max-Min算法或 Min-Min 算法加以调度。仿真结果表明，与经典的 Max-Min 算法以及 Min-Min 算法相比，本文算法在最大完成时间和资源利用率方面均具有显著优势。关键词：云计算；任务调度；启发式；最大完成时间；资源利用率中图分类号：TP391 文献标志码：A 文章编号：1673-2928（2023）02-0074-04 云计算能够提供包括互联网存储、互联网应用以及互联网服务器等一系列相关服务的访问途径，有效降低信息技术应用领域的成本和复杂度1-3，因而受到了学术界和业界的广泛关注。在云计算框架中，任务的合理调度以及计算资源的负载均衡始终是 2 个重要问题。当多个用户想要在云端运行多个任务时，云计算应当能够运用最佳调度算法确定不同任务的调度方案。总体上看，云计算的任务调度算法可以划分为传统的调度算法以及启发式任务调度算法 2类。其中，较典型的传统调度算法包括 Max-Min调度算法、Min-Min 调度算法、Suffrage 调度算法等，而遗传算法(Genetic Algorithm,GA)、蚁群算法(Colony Algorithm,CA)和粒子群优化(Particle Swarm Optimization,PSO)则被视为具有代表性的启发式算法。采用 Max-Min 调度算法、Min-Min 调度算法、CA 等优化算法进行任务调度的相关工作已被广泛应用于云计算或网格计算等一系列应用场景。Xiong 等针对云数据中心的任务调度问题展开了深入研究，将约翰逊法则与GA算法相结合，提出了一种双阶段任务调度算法；Fang 等提出可以通过使用优先级算法针对 Min-Min 调度算法和Max-Min 调度算法加以优化，并据此设计了一种算法，该算法可以用于决策在云计算框架中何时选择采用Min-Min调度算法或Max-Min调度算法；Patel 等将 Min-Min 调度算法应用于云计算中的静态元任务调度，然后再通过重新调度资源上的任务以实现最大完成时间的压缩并提升负载均衡能力。然而，该思路往往会导致云计算框架性能的下降；Kumar 等7提出了一种混合任务调度算法，其将 GA 与 PSO 相结合，从而有效降低了执行时间，但工作负载的增加以及巨量的计算资源开销成为该算法的瓶颈问题；Yao 等8提出了一种“三阶段选择”框架用于进行云计算框架的任务调度，该方法尝试降低找到最佳局部最优方案的可能性，但却忽略了计算资源的开销；Biswas 等构建了一种系统，该系统通过使用基准数据集用于增强 GA 的变异性能，虽然该系统可在变异阶段降低执行时间，但在新的变异步骤中，该系统需要消耗更多的时间用于跟踪过载处理器以及负载最小的处理器；Mala 等提出了一种算法用于增强 Max-Min 调度算法，该算法可以并行运行所有微任务并分配相应资源，尽管该算法具有较理想的资源利用率，但在执行时间较长的任务数量过多的情况下，该算法性能不佳；Shi 等11提出了 BSufferage任务调度算法，该算法提升了 Sufferage 调度算法的性能，但在每次迭代中均需要花费大量时间对完成时间进行排序，因此，BSufferage 算法在进行大量任务调度时往往性能不佳。在此背景下，本文针对包括 Max-Min 调度算法、Min-Min 调度算法等在内的传统任务调度算法以及 GA 等在内的启发式任务调度算法进行了深入研究，旨在提出一种能够降低最大完工时间收稿日期：2023-02-02基金项目：河南省高等学校重点科研项目（17A113010）；河南省高等职业学校青年骨干教师培养计划项目“云计算环 境智能化运维关键技术研究”（2020GZGG041）。作者简介：李丹丹（1989），女，河南三门峡人，助教，硕士，主要研究方向为计算机云计算技术。第二期75以及提升负载均衡的云计算任务调度算法。1 相关算法1.1 Max-Min 调度算法Max-Min 算法是一种应用于分布式系统的调度算法，采用该算法可以将调度前的任务进行分配，从而分别得到每个任务在各个处理器上的期望完成时间矩阵，以及每个任务的最小完成时间矩阵。然后，选择具有最大的最小完成时间的任务，并将其分配给具有最小执行时间的处理器加以执行。Max-Min 算法将重复执行上述选择和分配流程，直至所有任务得到映射且待分配任务集合为空。然而，当具有较大的最小完成时间的任务数量增多时，Max-Min 算法的性能将会下降，并导致所分配的任务对应的最大完成时间过长。反之，当最大完成时间较短的任务数量多于最大完成时间较长的任务数量时，Max-Min 算法性能较佳。1.2 Min-Min 调度算法与 Max-Min 算法类似，Min-Min 算法也是一种典型的调度算法，该算法可以根据最小完成时间对所有任务加以分配，并将其分配给相应的处理器。假设有一组待映射的任务集合 S，N 个相互独立的任务和 M 台处理器，对每个待分配的任务 ti分别计算出分配该任务到 M 台处理器的最小完成时间，构成最小完成时间矩阵(Minimum Completion Time,MCT)；从 MCT 矩阵中，分别找到能够最快完成该任务的处理器及最小完成时间，然后在所有的最小完成时间中找出具有最小完成时间的任务 ti，并将其分配给相应的处理器；最后，从 S 中将任务 ti删除，并更新 MCT 矩阵。当任务集合 S 为空集时，算法结束。显然，与Max-Min 算法不同，Min-Min 算法优先对较小的任务进行分配，从而增加大任务的等待时间。当小任务的数量大于大任务的数量时，Min-Min 算法性能较佳。1.3 遗传算法遗传算法是一种性能优越的搜索和优化技术，目前已被广泛应用于多模环境中的全局最优解搜索问题的解决。通常情况下，GA 首先通过随机方式针对染色体进行编码，生成若干确定长度编码的初始群体；然后，通过适应度函数对该种群中的每个个体进行评估，选择适应度数值较大的个体参与遗传操作，适应度数值较小的个体被淘汰；此外，GA 算法还将利用选择、交叉和突变等一系列遗传操作形成新一代种群，重复上述过程，直至最优解收敛为止，最后将性能最好的个体作为 GA 算法的执行结果。2 本文算法通过对 Max-Min 算法、Min-Min 算法以及经典 GA 算法进行分析与研究，本文提出了一种新的云计算任务调度算法，该算法将遗传算法、Max-Min算法以及Min-Min算法进行了有效结合。其中，GA 算法主要用于确定较合适的任务调度框架，即选择 Max-Min 算法或 Min-Min 算法。本文中 GA 算法的执行效率主要取决于染色体的编码和解码过程，从而生成一个初始群体，同时，采用适应度函数选择产生最佳的交叉和变异以产生新的群体，以便后续用于选择最佳的任务调度方法。2.1 染色体编码和解码GA 算法中针对染色体的编码主要可以分为二进制和浮点型 2 种类型，其中，二进制编码由于采用了连续函数离散化容易导致映射错误。不仅如此，二进制编码在单个字符串编码时也往往无法满足最佳时间内的精度要求。相比二进制编码，浮点型编码更容易对云计算中的任务进行表征并能较快地获得结果。因此，浮点型编码更适合对云计算中的任务和计算资源进行表征，故本文提出的云计算任务调度算法中涉及的染色体编码采用了浮点型编码方式。2.2 染色体选择本文利用任务表中的数值生成染色体，其中，任务表中的每一行数值表示任务 ti在所有可用资源 R1,R2,Rj,RM上的执行时间，通过选择资源 R1,R2,Rj,RM上任务 ti的最大执行时间和最小执行时间完成 GA 的选择流程，其中 M表示可用资源的数量。例如，若任务 t1在 4 个可用计算资源 R1,R2,R3,R4上的执行时间分别为 4,7,2,8，则第 1 条染色体为最小执行时间 2，第 2条染色体为最大执行时间8。因此，针对每个任务，可以为其选择 2 条染色体，以便后续用于交叉和突变。2.3 交叉与变异在GA算法中，交叉操作属于一种重组操作。通过交叉操作，下一代个体可以将父母染色体中的良好特征加以继承。本文算法的交叉操作是将前一代染色体的数值相乘，然后求出对应的平方根从而生成新的染色体，新的染色体数值将作为下一步选择 Max-Min 算法或 Min-Min算法的依据，该操作可以有效改进 GA 算法，并避免陷入局部最优解。为了获得问题的新解，可以采用变异算子随机选择不同染色体上的 2个位置进行交换。新的染色体数值 C1,C2,Ci,CN将与每个任务的最大执行时间和最小李丹丹：基于混合式启发的云计算任务调度算法2023 年安阳工学院学报76执行时间的平均值 Ave 进行比较，并分别计算大于 Ave 的新的染色体数量 R 以及小于 Ave 的新的染色体数量 L。若 RL，则选择 Max-Min算法；否则，选择 Min-Min 算法。上述过程直至所有任务完成分配为止。2.4 算法步骤本文算法的具体步骤如下。输入：待分配任务集合 S=t1,t2,ti,tN；计算资源集合 R=R1,R2,Rj,RM；任务表 Tab 负责记录每个任务在不同计算资源上的完成时间；GA 种群代数 Gen=0；GA 最大种群代数Genmax；染色体集合 C=c1,c2,cN；输出：任务调度序列；具体步骤：步骤 1：根据每个待分配任务 ti在不同计算资源上 Rj的执行时间生成任务表 Tab；步骤 2：当 S 时，若 GenL，则选择 Max-Min 算法对任务 ti进行调度；否则，选择 Min-Min 算法对任务ti进行调度；步骤 10：删除任务表 Tab 中任务 ti的相关信息且 S=S-ti；步骤 11：当 S=时，算法结束；否则，返回步骤 2。3 仿真实验为了验证本文算法在云计算资源调度方面的合理有效性，本节在 Windows 10 操作系统环境下选用 Matlab 2018 软件分别针对 Max-Min 算法、Min-Min 算法以及本文算法进行了仿真实验。仿真实验分别涉及在 14 个计算资源上的 10 个随机完成时间的任务调度。Max-Min 算法、Min-Min算法以及本文算法对应的最大完成时间结果如图1 所示。图 1 3 种算法的最大完成时间比较为了保证图 1 中实验结果的客观性，针对每种算法的仿真实验均进行了 10 次，并将 10 次实验结果的平均值作为最终结果。与 Max-Min 算法和 Min-Min 算法相比，本文算法在不同数量的计算资源上的任务最大完成时间均少于前两种算法，体现出良好的计算资源调度性能。此外，除了最大完成时间，负载均衡也是衡量云计算资源调度性能的一项重要指标。因此，本文借鉴文献 12 中的相关内容，提出了一种综合 3 种不同参数的资源利用率评价指标，对应的数学表达式为：1kiic Util Makespan*N=其中，ci为在第 i 个资源上运行的所有任务的总完成时间；makespan 为总的最大完成时间，N 为可用资源的数量。Max-Min 算法、Min-Min 算法以及本文算法在14 个计算资源上的资源利用率结果如图 2 所示。图 2 3 种算法的资源利用率比较从图 2 可以看出，随着资源数量的增加，Min-Min 算法的资源利用率逐渐增大，Max-Min算法在资源