云计算环境下独立任务调度算法研究

徐星辰

（中共怀宁县委党校，安徽 安庆 246121）

云计算系统拥有数量众多的处理器，庞大的使用群体，多样化的任务类型，其数据中心时刻面临海量数据和应用任务。云计算环境下任务调度问题的研究具有较高的学术和实际应用价值[1]。任务调度一般分为静态调度和动态调度[2]。静态调度能够事先获取更多任务信息（如任务之间的关联性，任务在各服务器上的运算时间等），具有易实现、效率高、成本小等特征，因而，许多科学计算如图像识别、网格任务、路径规划[3]等都采用静态调度的方法对任务进行处理。动态调度在程序运行过程中，根据服务器和网络运行负载情况来随时调整调度算法，具有优异的适应能力和灵活度，但也存在难以解决的实际问题，相较于静态调度，动态调度的实际应用与理论研究成果不多，一般用于并行计算。云计算任务由若干子任务组成，按照前后执行的任务之间是否存在关联性，将任务调度分为独立任务调度和关联任务调度[4]。本文关注的是云计算中静态独立任务调度，重点分析典型的云环境下静态独立任务调度算法的发展趋势，为相关领域的研究提供参考。

1 云计算静态独立任务调度

独立任务调度指将没有关联的任务集合以一种合理的策略分配至不同的服务器上，实现任务的规模化处理，调度过程中，前后两个任务的执行互相独立、并列执行，其模型如图1所示。

图1 独立任务调度模型

关于静态独立任务调度算法的研究主要分为两种。（1）传统独立任务调度算法。该算法大多以非智能化算法为主，侧重于某个指标的寻优，具有简单容易实现的特点，但是算法只注重某个指标的最优，为了实现它通常会放弃其他指标，导致调度的结果是：虽然该指标实现了最优，但是其他指标的效果往往不是很令人满意，甚至很差。典型的算法包括Min-Min、Max-Min、Sufferage和RR算法等；（2）启发式独立任务调度算法。该算法大多采用群体智能的方式进行调度，其核心思想是多目标优化问题，在可接受的计算代价内，给出满足各个实例的可行解，而对于某个实例来说这个解未必是最优解。启发式独立任务调度算法的调度性能优良，在独立任务调度中应用较多，但也存在算法因需预设置参数和多次迭代以获得最后的优化结果，导致实现过程复杂。由此可见，启发式独立任务调度算法下一步的研究方向主要是进一步降低算法的复杂度。目前应用较多的启发式独立任务调度算法主要有GA算法、PSO优化算法、Ant算法等。

2 常见的静态独立任务调度算法

2.1 Min-Min算法

Min-Min算法[4]是一种典型的独立任务调度算法，每次调度开始前，需计算出任务调度队列中全部任务在各资源节点上的最早完成时间，然后将其中最短的任务分配到相应的服务器上执行，同时从队列中将其删除，接着更新任务队列的期望时间，反复执行上述过程，直至任务队列为空时退出。

算法优点：实现简单，时间和计算复杂度低。

算法缺点：性能更优的处理器负载过重和大任务调度时间太长，导致系统负载不均衡。

Min-Min算法最主要的问题是负载不均衡，文献[5-8]针对这一问题进行了优化，如表1所示。

表1 Min-Min算法优化

2.2 Max-Min算法

Max-Min算法和Min-Min算法的基本思想类似，不一样的地方是，Max-Min算法在调度前须计算出任务调度队列中全部任务在各资源节点上的最早完成时间，并将最早完成时间中最长的任务优先分配给相应的处理器上执行[9]。

算法优点：简单实用，时间复杂度低。

算法缺点：可能造成小任务调度延后，引发处理器负载不均衡现象的发生。

Max-Min算法的最主要问题就是贪心策略容易造成负载不均衡，文献[9-11]主要针对这一问题进行了优化，如表2所示。

表2 Max-Min算法优化

2.3 Sufferage算法

Sufferage算法首先计算任务集合中的所有子任务在各处理器上的执行时间，然后将任务最短完成时间与次短完成时间差的绝对值定义为Sufferage值。在进行任务调度时，先将任务分配至完成时间最短的处理器，假如该处理器已经分配任务，则需计算两个任务的Sufferage值，数值较大的优先调度；否则，该处理器直接执行已分配的任务，反复执行上述流程，直至任务队列为空时退出[12]。当任务集合的子任务之间Sufferage值均较小时，适合使用Sufferage算法进行调度。

算法优点：简单可行；衡量子任务的时间损失度，减少任务调度跨度。

算法缺点：负载的平衡性能不高，缺乏对全局任务调度的考虑。

目前的主要研究方向是针对Sufferage算法的负载均衡性和全局调度进行优化，如表3所示。

表3 Sufferage算法优化

2.4 遗传算法

遗传算法是一种模拟自然界生物种群“优胜劣汰”自然选择过程的算法，随机初始化一个种群，种群中所有个体都由基因编码的染色体构成，每次迭代更新，都会经过一系列杂交、突变、繁殖等遗传操作过程，淘汰基因劣质的染色体，选择适应能力强的染色体形成新种群，重复上述迭代过程直至产生基因最优的个体，该个体即代表任务调度问题在当前环境下的最优解[17]。

算法优点：从群体出发，具备同时搜索能力，解决并行问题能力强；易与其他算法融合。

算法缺点：算法实现过程比较复杂，搜索时间耗费过长且效率不高；随着计算规模的不断扩大，易出现提前收敛。

应用于云计算任务调度时，遗传算法有很强的全局搜索能力，但是算法的搜索效率和解的多样性方面还需要提高，为解决上述问题，学者们做了一系列优化研究，如表4所示。

表4 遗传算法优化

2.5 粒子群优化算法

受鸟群和鱼群寻找食物的行为规律启发，Eberhart和Kennedy提出了粒子群（PSO）优化算法[23]。PSO算法的基本思想是通过集体协作和互通信息来寻找最优解。首先初始化粒子群体，群体中的每个粒子都包含两个属性，即位置和速度；然后计算每个粒子的适应度，将每个粒子的当前适应度与其历史最佳位置对应的适应度作比较，如果当前的适应度更高，则用当前位置替代历史最佳位置；接着将每个粒子当前适应度与整个粒子群的全局最佳位置对应的适应度作比较，如果当前适应度更高，则用当前位置替代全局最佳位置。反复迭代直到搜寻到与目标最近的解。

算法优点：具有参数设置少、搜索和收敛速度快等特点。

算法缺点：PSO算法初始种群随机性强，其好坏直接影响算法的搜索空间，如果初始种群选择不当会降低算法的寻优能力。

与蚁群算法类似，在应用于云计算任务调度时，粒子群优化算法搜索速度快，但局部最优收敛速度快很容易导致陷入局部最优解，目前主要针对算法多样性进行优化，如表5所示。

表5 粒子群算法优化

2.6 蚁群算法

受蚂蚁觅食行为的启发，Marco提出了蚁群算法（ACO）[29]。该算法的核心思想是蚂蚁在觅食路径上通过分泌的信息素来传递信息，信息素浓度越高，被后来的蚂蚁选择的概率越大，后来的每只蚂蚁都会在该路径上留下外激素，路径长度与外激素的浓度呈负相关关系，随着时间推移，路径越短其累计的信息素浓度就越高，蚂蚁更倾向选择这条路径。最后，所有的蚂蚁都会选择集中于最佳的路径上，此时对应的便是最优解。

算法优点：具有优异的扩展性、丰富的多样性，其正反馈性和并发性也比较突出，适用于多目标下最优解问题的搜寻。

算法缺点：因信息匮乏，算法前期需花费时间积累信息素，速度慢、搜索时间较长。

应用于云计算任务调度时，信息素积累起来之后，蚁群算法具有极高的搜索效率和解的精度，但是前期信息素积累需花费较长时间，易造成收敛速度过快和陷入局部最优解。目前的主要研究方向是针对算法多样性和前期搜索效率进行优化，如表6所示。

表6 蚁群算法优化

3 结束语

本文阐述了云计算环境下静态独立任务调度模型，对静态独立任务调度算法作了分类，选取了6个比较常见的静态独立任务调度算法：Min-min算法、Max-min算法、Sufferage算法、ACO算法、GA算法、PSO算法，分别对它们进行详细分析，从优化内容、对比算法、优化结果等方面归纳总结了以上算法的改进方式及效果，为相关领域的研究提供参考。目前绝大多数静态独立任务调度算法都是在理想的网络环境下进行的，但现实云服务环境下的网络带宽每时每刻都在变化，因此，对于任何一种调度算法，如果不考虑网络带宽对调度结果产生的影响是不合理的，设计一种考虑实际网络环境的任务调度算法成为目前云计算需要解决的一个关键性问题。