云计算任务调度算法综述

顾阳，李敏，李华

（广西师范学院计算机与信息工程学院，南宁 530023）

0 引言

云环境是一个异构的分布式计算平台，为用户提供方便的可用资源，包括网络、服务器、存储、软件等。由于成千上万的用户同时使用云环境，任务数量庞大，因此任务调度算法对云平台的性能稳定有着重要影响，具有理论研究意义。任务调度一般可分为动态调度和静态调度。动态调度算法会根据实时调度来调整结果，具有较强的适应性和灵活性，但存在诸多不确定因素。静态调度算法则通常需要获取实时任务信息，具有简单高效、成本低廉等特性。本文总结了当前部分任务调度算法，包括传统的任务调度算法、启发式任务调度算法和商业应用中的任务调度算法，并在此基础上对其进行评估总结。

1 问题定义

在云环境中，任务调度的任务通常可以被抽象为四元组（T,≺,C,D）[1],在这个四元组中，T=（t1，t2，...，tn）是可执行任务的集合；≺描述任务之间的部分顺序，例如，ti≺ tj表明任务 ti应该在任务 tj之前执行；C={c1，c2，...，cn}是任务集 T 中所有任务的计算，ci是任务 ti的计算；D是n×n矩阵，Dij是从任务ti到任务tj的数据量。根据任务之间是否存在依赖关系或优先约束条件，我们可以将任务划分为独立的组件任务和工作流任务，独立的组件任务可以用一个二元组（T，C）来描述，工作流任务因为依赖或优先约束可以用有向无环图（DAG）来表示。

2 任务调度算法分析

2.1 传统的任务调度算法

一般地，我们假设可以得到每个任务的执行时间和每个机器最早可用时间。机器最早的可用时间加上任务的执行时间等于机器上任务的最小完成时间。我们将从任务集T中的第一个任务开始到任务集T中的上一个任务结束的时间定义为完工周期。我们的目标是获得最小完工时间。

（1）OLB，MET，MCT，Duplex和 KPB

OLB算法主要考虑到机器最早的可用时间，所以无法保证任务将被分配到最小的机器执行时间。而MET算法是以最短的执行时间将任务分配给机器，而不是最早的可用时间，结果可能出现负载不平衡。MCT算法选择以最早的完成时间分配一个任务给机器，但是可能导致一些任务不能以最小的执行时间分配给机器，结果使得制造时间变长，MCT算法优于OLB算法和MET算法。Duplex算法和KPB算法都是基于MET和MCT的，它们的区别在于Duplex算法是根据系统负载均衡参数来选择MET或MCT算法。而KPB算法设置一个名为K（100/n≦K≦100）的参数，并选择n×（K/100）个机器按任务的执行时间分配任务。

（2）MinMin算法、MaxMin算法和Sufferage算法

不同于前面提到的算法，MinMin和MaxMin算法都考虑到了所有集中任务，而不仅仅是当前的任务。MinMin算法在任务长度变得不均匀时，性能会有所下降，因为它总是先分配小任务会导致大任务的长时间等待，并且这个完成时间会迅速增加，此外，系统的负载将会是不平衡的。而MaxMin算法在这种情况下会先分配大任务，同时执行大任务和小任务，从而减少执行时间。为了解决这一问题，Zhou[2]提出了一种基于MinMin和MaxMin算法的动态启发式H-MM算法。该算法将提高分配的质量，但该算法通过每个处理单元分配的状态值来判断是否将任务分配给机器，否则，算法将比较任务的超时和机器上任务的超时，选择更大的任务分配任务。另一个任务将回到未分配的任务集并等待下一个分配，所以可能会增加算法复杂度。

2.2 基于启发式思想的任务调度算法

（1）遗传算法（GA）

遗传算法于1975年由美国教授Holland J提出[3]。这是一个随机搜索算法，参考生物圈中自然规律和机制。一般情况下，我们用1×n向量来描述染色体，n是任务数量，向量的各个元素代表被分配的某个机器。例如，假设有六个任务D和三个机器M，名为R=[1,3,2,3,1,2]的染色体，指的是D1和D5分配给M1，D3和D6分配到M2，D2和D4分配到M3。当染色体被随机生成一定数量，再根据每个任务执行在所有机器上的最早可用时间，计算任务分配解决方案的完工时间，并将完工时间设置为染色体的适应度。然后，算法通过不断地选择、交叉和变异，以获得最优的调度方案。

（2）模拟退火算法（SA）

模拟退火算法是1953年Metropolis被固体材料的退火过程所启发而提出的[4]，并被Kirkpatrick于1983年应用于最优组合问题[5]。它是采取循环搜索的搜索策略来寻求最优解。首先是对空间经行进行编码，SA的编码风格与GA相同，不同之处在于SA在一个周期内只考虑一个解。SA通过变异得到新的解，同时由公式（1）得到基于概率的非最优解。经过一轮循环搜索后，如果新解决方案的完工时间少于原解决方案，SA将接受新解决方案作为当前的解决方案；否则SA将产生一个随机数z ϵ random[0,1]。如果z>y，SA将接受新的解为当前解；否则，将维持原始解决方案。

在公式中，Tk是系统的当前温度，一般是调度的完成时间；f（s1）是提出调度完成时间的新解决方案。我们可以发现，当f（s0）和f（s1）大小相同或者Tk的值大时，y接近于0.5，这意味着非最优解的接受概率为50%；否则，y接近于1，表示非最优解的接受概率为0。所以，SA具有较好的渐进收敛性和并行性，但它可能容易陷入局部最优解中。

（3）蚁群优化算法（ACO）

蚁群优化算法是1992年由Marco Dorigo提出的[6]，灵感来自蚂蚁在寻找食物时寻找路径的行为。ACO由于其并发性和可扩展性而在解决调度问题上有很好的效果。在文献[7]中，作者将ACO应用在调度任务中。我们利用信息素来随时描述可能影响资源状况的因素。当资源进入系统时，应该将其性能参数的值提交给系统，例如PE的个数等。资源监控器会根据公式（2）对这些信息素进行初始化，并分别验证其参数。当资源出现故障或者新的任务被分配或者某些任务已经完成时，算法将根据公式（3）更新从调度中心到相关资源的路径上的信息素。在任务完成之后，新任务分配给资源的概率将根据公式（4）重新计算。

在公式（2）中，Δτj(0)是资源j路径上的原始信息素；m代表PE的数量；c代表参数长度；p代表单个PE的处理速度；sj代表资源j的传输时间。公式（3）中，Δτj是资源监测中心到资源sj的路径上的信息素变化值，ρ（0≤ρ≤1）是信息素的保留因子，1-ρ是信息素的挥发因子。当任务分配给资源j时，Δτj=-K，K是任务的计算；当资源j上的任务执行成功并返回任务时，Δτj=Ce∘K，Ce是鼓励因子。当任务执行失败并返回任务时，Δτj=Cp∘K ，Cp为惩罚因子。在公式（4）中，R是可用资源集合；τj(t)是时刻t从调度中心到资源j的路径上的信息素；ηj是资源j的固有属性，τu(t)是时间u从调度中心执行到j的路径上所包含的信息素；α和β分别代表信息素和固有属性的权重。

（4）粒子群优化算法（PSO）

粒子群优化算法于1995年由Dr.Eberhart和Dr.Kennedy提出[8],是模拟鱼类和鸟类在饲养期间的迁移和聚集。粒子群优化算法是一种基于群体的多目标优化算法，它将搜索过程中基于目标函数的粒子群中的粒子移动到最优解的位置。该算法将每个个体视为在D维搜索空间中以给定速度移动的粒子。粒子的速度将根据个体和全局最优值进行动态调整。我们假设i={1,2，...，N}是粒子的个数，d={1,2，...，D}是每个粒子的 D维搜索空间，所以是第i个粒子的位置，然后算法根据预先设定的目标函数计算xi的当前适应度，从而说明粒子位置的优劣。是粒子i的速度，p是每个粒子从迭代开始找到的最优解的位置。是即刻所有粒子的最优解位置。所有粒子在每次的迭代过程中通过公式（5）（6）来不断更新自己的速度和位置：

在这些公式中，k是第k代。在公式（5）中，w是惯性权重，c1和c2是加速系数，也称为学习因子，用于维持种群多样性。r1和r2是[0,1]之间的随机数。此外，vij是三部分的线性组合。

3 结语

任务调度是一个非确定多项式（NP）问题，也是云环境下分布式平台资源管理的核心功能。虽有已有的很多算法和技术不断地成熟，但实际上还存在很多问题。例如，由于资源可以随时加入和离开系统，用户的需求也一直在变化，任务调度的失败是不可避免的。而且，由于云环境中的资源是异构的，因此可能会分配一些资源来执行不能完成的任务或不好的任务，从而降低系统的性能。因此，我们需要从不同方面量化资源评估，制定统一的绩效评估标准和模型。另外，我们需要对资源进行适当的分类，并根据用户的需求进行资源分配，一些人工智能算法也必将被应用于商业云系统中的任务调度。

[1]Li Jia.Research on DAG Task Scheduling Algorithm in Grid Environment[D].Central South University,2008.

[2]Yanhui Zhou,Kai Zhang.New Distributed Task Scheduling Algorithm[J].Computer Systems&Applications,2008,17（10）:40-42.

[3]Holland J H.Adaptation in Natural and Artificial Systems[J].University of Michigan Press Ann Arbor Mich,1975.

[4]Steinbrunn M,Moerkotte G,Kemper A.Heuristic and Ran2 Domized Optimization for the Join Ordering Problem[J].The VLDB Journal,1997,6（3）:8-17.

[5]Vecchi M P,Kirkpatrick S.Global Wiring by Simulated Annealing[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1983,2（4）:215-222.

[6]Dorigo M,Di C G,Gambardella L M.Ant Algorithms for Discrete Optimization[J].Artificial Life,1999,5（2）:137-172.

[7]Xue S,Li M,Xu X,et al.An ACO-LB Algorithm for Task Scheduling in the Cloud Environment[J].Journal of Software,2014,9（2）.

[8]Kennedy,James,Eberhart,et al.Particle Swarm Optimization[C],1995.