云工作流中基于分时虚拟机的任务层调度算法

王建　李龙澍

摘要：云计算是新的一种面向市场的商业计算模式，向用户按需提供服务，云计算的商业特性使其关注向用户提供服务的服务质量。任务调度和资源分配是云计算中两个关键的技术，所使用的虚拟化技术使得其资源分配和任务调度有别于以往的并行分布式计算。目前主要的调度算法是借鉴网格环境下的调度策略，研究基于 QoS 的调度算法，存在执行效率较低的问题。我们对云工作流任务层调度进行深入研究，分析由底层资源虚拟化形成的虚拟机的特性，结合工作流任务的各类QoS约束，提出了基于虚拟机分时特性的任务层ACS调度算法。经过试验，我们提出的算法相比于文献[1]中的算法在对于较多并行任务的执行上存在较大的优势，能够很好的利用虚拟的分时特性，优化任务到虚拟机的调度。

关键词：云计算；工作流系统；云工作流；工作流调度；蚁群算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）10-2431-05

Abstract：Cloud computing is a new market-oriented business model， providing the users the services they need， so that the commercial characteristics of cloud computing makes service providers pay more attention to the quality of service users need.Task scheduling and resource allocation are two key cloud technologies， and virtualization technology makes its resource allocation and task scheduling is different from the previous Parallel distributed computing.Currently，The scheduling algorithm in Cloud Workflow references to the scheduling strategy in grid environment.Based QoS scheduling algorithm in some papers are Inefficient in Cloud Environment.In this paper， they focus on Task-level scheduling in Cloud Workflow and analysis the features of virtual machines which is from the underlying resource by virtualization ，.considering all kinds of QoS constraints of workflow tasks， they propose ACS scheduling algorithm based on virtual machine sharing features .By the simulation experiment， the proposed algorithm，compared to the algorithm in the literature[1]，shows the better performance in the situation where there are many parallel tasks ， and can make good use of virtual resource and optimize the Task-to-VM assignment in the cloud data centers.

Key words： cloud computing；workflow system；cloud workflow；workflow scheduling；ant colony algorithm

云工作流系统区别于其他的工作流系统就是它的面向市场商业模型[2-3]，成本节约是它最大的特点，用户使用云端的资源就像是使用水电一样，用多少付多少钱，所以用户通常使用云工作流系统会对应用服务进行执行时间和成本上的约束。云服务供应商和用户通过协商签订服务级协议，云服务供应商根据服务级协议执行用户的云工作流实例，云中有很多满足各种条件的云服务，能够满足各种服务质量要求，所以要为工作流实例中的任务选择合适的云软件服务，符合服务级协议。同时作为一个服务供应商，也要尽可能为自身获得一定的利润，那么，对云工作流的资源管理提出了一个很高的要求，而云工作流调度是云工作流资源管理的核心问题，因此，研究云工作流调度是非常有意义的。云工作流调度就是将云工作流实例中的任务映射到合适的执行资源上并管理其运行。

国内外有较多的研究机构和研究团队在研究关于云工作流调度。Gurmeet Singh等[4]提出了在网格环境中通过任务聚类来优化工作流运行，使用提前预留和动态提供等资源配置方法，来降低科学工作流的完成时间。同时还研究了资源配置的成本问题，提出了基于资源利用率的评价矩阵，用于决策配置方式。Eun-Kyu Byuna[5]提出了平衡时间调度（BTS）近似算法，该算法通过计算出执行在用户指定结束时间内的工作流任务所需的计算资源的最小数量，来确保执行工作流执行所需的最优资源数量。Buyya 等[6]提出采用基于粒子群算法（PSO）的启发式算法调度云工作流任务，该算法不仅考虑计算成本，还考虑数据的传输成本，满足用户的最小化时间、最小化运行成本以及均衡资源负载的 QoS 约束。MohsenAmini Salehi等[7]提出了两个以市场为导向的调度策略，分别用来优化执行时间和执行成本。通过向服务提供者租用资源来扩展本地资源的计算能力，来满足用户截止时间的服务质量需求。该策略无需应用程序执行时间的相关历史数据，并以用户层代理的方式集成在 Gridbus 系统中。国内也有较多的团队在研究云工作流，在活动调度方面，谢海军等[8]为提出了一种新颖的基于Skyline点和局部选择的启发式服务组合方法SLOMIP。该方法首先从候选服务集合中选出 Skyline服务，再从Skyline服务集中选取最优的k个服务进行最终服务组合方案的优化求解。该方法求得的解必然是最优解。

群集智能作为一种新兴的求解问题的方案，在工程优化领域具有不可替代的作用，它对提高大规模优化问题的求解速度及优化精度具有非常重要的实际意义。蚁群算法作为群集智能的一种，在工作流调度上也有很好的应用。Ruay-Shiung Chang[9]等就提出了在网格中的平衡工作流调度的蚁群算法。Wei-Neng Chen[10]等提出了网格中工作流调度算法——蚁群优化算法，文中提出两种启发式信息——成本和执行时间。之后，又提出基于多种服务质量的要求的蚁群优化算法优化网格工作流任务调度[11]，将蚁群优化算法应用于优化云工作流的任务调度，结合云工作流的特点设置改进蚁群算法的各个参数模型。Zhangjun Wu[1]等提出面向市场云工作流的两层调度算法。在任务层就提出采用蚁群优化算法来生成任务层的调度策略。在任务层中的调度，由于分配到数据中心局部调度器的任务可能有上千个，那么匹配局部调度器管理的虚拟机上采用蚁群算法进行调度，结合云工作流的特点，设置合适的蚁群算法的参数算子，提高算法解决问题的整体能力。

本文提出在数据中心内，采用虚拟机分时的特性，进行工作流实例的任务和非工作流任务的调度，优化数据中心内系统的执行效率。

1 问题分析

在任务层调度中，我们所要调度的工作流任务可能来自不同的工作流实例。对其进行逻辑处理，根据其任务间相互依赖关系，并添加一个虚拟的开始任务节点和结束任务节点，构成一个集成工作流实例。采用一个集成的DAG图表示一个工作流实例。一个集成的工作流实例为[G=N，E]。n表示集成工作流实例的任务个数。其中[N=T1，T2，…，Tn]表示流任务集合，集合[E=Ti，TjTi，Tj∈N]表示任务间的依赖关系，每个任务[Ti（1≤i≤n）]将调度到虚拟机集合[V=V1，V2，…，Vm]中的某个虚拟机上，因此，任意的工作流任务[Ti]可用两个元素[]表示，其中[timei=time1i，time2i，…timemi]表示[Ti]在虚拟机集合[V]中每个虚拟机上的执行时间，[co st]表示[Ti]的成本约束。

现有的任务层调度算法未考虑虚拟机的分时特性，并发任务串行执行，执行效率低。在公有云计算环境中，虚拟机是多用户共享的，任务在各个虚拟机上要形成一个队列任务。因此，任务层在虚拟机上执行有先后关系。如果两个任务是并行的， 要么分配到不同的虚拟机，或者形成串行化的任务。但是，一个虚拟机同时只做一个任务是不现实的，虚拟机应当是分时的。在考虑分时的情况下，并行任务可以并发执行，也就缩短了执行时间，减少了时序异常的出现。因此，对于虚拟机集合中的任意虚拟机[Vi]可以用两个元素[]表示，其中[price]表示虚拟机的价格，[ma xpra]表示保证任务执行效率时并行执行任务的最大个数。两者均为常数。

任务层调度形成一个调度方案表示为一个二元组集[Ki=Ti1，Vi1，Ti2，Vi2，…Tin，Vin]，二元组中的任务集[Ti1，Ti2，…Tin]任务具有一定的先后关系。则在调度方案[Kj]下的该数据中心内部局部调度的最大完工时间为：

[MakespanKj=m ax1≤i≤nTKji.makespan]

其中，[TKji.makespan]表示任务[Ti]在调度方案[Kj]下的完成时间，包含等待时间。

那么，调度的优化目标是局部调度器内所有任务的最大完工时间的最小即：

对于集成的工作流任务执行要满足用户定义的QoS约束，该文主要考虑以下两个约束：

1）集成的工作流实例必须满足一定的成本上限。即所有任务在调度方案[Kj]下的成本：

[CostKj=i=1nVKiji.c ost≤Budget]

其中，[Budget]表示为用户的容忍成本上，其上限为所有任务成本约束之和。

2）对于每一个虚拟机都有自己相应的最大并行上限，在调度方案[Kj]下满足

[ViKj.prataskNum≤Vi.ma xpra ?i∈1，2，3，…，m]

其中，[Vi.ma xpra]表示虚拟机[i]的允许最大并行数。

由于在任务层的调度中针对的是来自至少一个工作流实例的任务，是一个集成的工作流。那么对于集成DAG，并行任务的开始执行时间不仅受到集成的DAG中的相互依赖关系，还要满足该任务所在的工作流实例中的依赖关系。如图1所示，工作流调度分为两层，即服务层调度和任务层调度。在服务层调度中，用户通过web端口的建模工具，构建一定规格的工作流实例，并将其提交给全局调度器，进行工作流的管理和评估，将工作流的任务分配给相应的服务。任务层调度的任务数量并不多，但是由于虚拟机是共享的，在分配任务的时刻虚拟机上正运行着其他任务，所以涉及到的任务数量会很大.

在服务层调度之后，全局调度器将工作流实例中的任务段分配给相应的局部调度器，为了优化任务所在数据中心的系统运行时间，局部调度器将分配的任务形成集成的DAG图，进行优化分配任务到虚拟机。图1中，工作流实例2中的[T1，T5，T7]分配给了同一个服务，在集成的DAG图中，[T5，T7]都是[T1]的后继任务，一般，在任务[T1]执行完后，就可执行[T5，T7]，但是，[T5，T7]在其原本的工作流实例不是并行执行的，它们的开始执行时间分别是由[T3，T6]任务的结束时间决定的。另外，在一个数据中心中，虚拟机都是建立在不同的规格的商业机或者是高性能的超级计算机上的，虚拟机的执行速度和价格是不一样的。

针对上述问题，如何构建基于虚拟机分时特性的任务层调度模型，使得在满足成本约束的情况下，优化数据中心局部调度器内的执行时间是关键所在。该文就针对这一问题进行详细的研究提出合理的算法。

2 基于分时虚拟机的任务层ACS调度算法

针对上述的问题分析，该文对于不同的虚拟机设置在不影响其他任务运行的情况下，允许最大并行任务数。该文根据任务所在的工作流实例的时间约束，结合集成工作流的时间约束，设置任务预计开始时间，然后根据任务的预计开始时间，对蚁群算法进行改进设置新的启发式信息并将其用于任务层调度。

2.1 信息素设置

在算法中，所有的信息素值都设置为[τ0]，该文中对于[τ0]初始化为：

其中，[Min_makespan]表示为在资源不受限制的情况下，集成工作流实例的最小执行时间。[Max_makespan]表示在资源不受限制的情况下，集成工作流实例的最大执行时间。

2.2 启发式设置

在任务层调度中存在成本约束，以及对执行时间的优化，因此，在蚁群算法中对应不同的启发式信息。

1）执行时间启发式：该启发式信息引导蚂蚁为未分配的任务选择执行时间短的虚拟机。

2）成本启发式：该启发式信息引导蚂蚁为未分配的任务选择成本最少的虚拟机。

3）成本预算的启发式：由于有多个QoS约束，各个约束之间会产生矛盾，执行时间短的虚拟机的成本高，执行成本低的虚拟机执行时间长。所以，为了权衡各个约束条件之间的关系，在设置启发式信息时会有一定的倾向性，该启发式信息引导蚂蚁为未分配的任务选择满足成本约束的虚拟机。

2.3 解的构建

在蚂蚁选择某个具体的启发式信息后，蚂蚁开始构造调度方案。每只蚂蚁为未调度的任务选择合适的虚拟机时，要考虑启发式信息和信息素。其概率选择方程为：

[Vji=arg max1≤j≤miτi，jβηi，j q≤q0 轮盘赌方式选择 q>q0] [6]

其中，[τi，j]为活动[i]选择资源[j]的信息素，[ηi，j]为活动[i]选择资源[j]的启发式信息。[β]为常系数。

2.4 解的优化

在ACS算法中，蚂蚁在为集成工作流任务分配到合适的虚拟机上，对于选择的路径进行信息素更新，包括局部更新和全局更新。

1）在蚂蚁为未分配的任务选择合适的虚拟机后，进行局部信息素更新，从而能够减少其他蚂蚁为相同任务选择相同虚拟机的概率保证调度方案的多样性。局部更新信息素规则如下：

2）在本算法中有多个启发式信息，每只蚂蚁只选择某一种启发式信息，进行启发式选择信息素局部更新，保证其他蚂蚁能够尽可能选择其他的启发式信息，从而使调度方案多样。启发式选择信息素局部更新规则如下：

其中，[τA]为当前最优调度的选择信息素，[ρlocal∈（0，1）]为挥发系数，[τ0]为信息素最小值。

在所有的蚂蚁都构造了调度方案之后，算法将评价各个蚂蚁所构造的调度方案。具体评价函数为：

其中，[K]为当前最优调度方案。

2.5 算法流程

基于分时虚拟机的任务层ACS调度算法的具体过程如下：

步骤1. 初始化蚁群系统的各类参数：信息素，蚂蚁个数，选择参数[q]，局部信息素挥发因子[ρlocal]，全局信息素挥发因子[ρglobal]，最大迭代次数，当前迭代次数为1；

步骤2. 初始化所有蚂蚁：为每只蚂蚁构建任务序列，选择合适的启发式方式（选择采用轮盘赌的方式进行，同时进行类似信息素的更新的方式进行对每个启发式方式的选择概率进行调整。）

步骤3. 对每个任务，每只蚂蚁根据其启发式信息和信息素选择相应的资源。

步骤4. 对每只蚂蚁构建的调度方案进行评价，并进行全局更新。

步骤5. 计算迭代次数，如果小于最大迭代次数，转step2，否则结束，输出最优方案。

3 实验仿真

3.1 实验数据描述

本文中的实验数据均是随机产生，根据应用层的DAG图随机产生50到250个集成任务DAG图。任务的平均执行时间是随机正态分布30到3000 之间的时间单位，为了能体现底层资源的高动态性，标准差定义为平均值的33%。

每个资源包含三个属性，包括资源的ID，执行速度，执行成本和最大任务并行数。执行速度被定义为一个在1到5之间随机整数，任务的执行时间等于任务的平均执行时间除以各自虚拟机的执行速度。每组有一半虚拟机的速度为1。为了实验设置方便，实验中每个资源价格定义为执行速度加上一个1到3之间的随机整数。随机的云工作流总任务数量从50个变化到 300 个，包含工作流任务和非工作流任务。子工作流的数量相应地由5个增加至50个。由于是集成的工作流应用，在DAG图中表现的并行任务不一定是真正的并行。因此，每个任务都有一个绝对的开始时间，它是由它所在的工作流实例的时间约束推导得到的。在实验中任务的预计开始时间也是随机产生的，且每个任务的 QoS 约束定义为时间约束和成本约束：时间约束为平均执行时间加上 1.28倍的标准差，成本约束为时间约束的三倍。云工作流的完工时间定义为所有虚拟机上的最后结束时间，工作流的总成本定义为任务执行时间之和乘以分配给它们的虚拟机价格。

3.2 实验分析

3.2.1 收敛性分析

每组实验的蚂蚁个数为10个，集成工作流任务约束取集成DAG中所有任务成本约束之和。设置概率选择方程中的[β]为1.2和[q0]为0.9，，全局信息素更新和局部信息素更新的挥发系数[ρglobal]和[ρloacal]均为0.1。我们设计了5组实验，集成工作流应用的任务个数分别从50到250，对于每个工作流实例得到调度方案每次迭代的统计得出本算法的收敛情况。

从图中，可以看出本算法收敛速度较快。由于在算法设计过程中考虑集成的工作流实例中，任务是来自各个实际工作流实例，都有各自的时间约束，任务的开始时间不仅是受集成的DAG中任务的影响，也受到各自的工作流实例的任务间的依赖关系的影响，基于上述的考虑，设置了任务的预计开始时间，从而造成算法的收敛速度较快。

3.2.2 算法比较

将本文提出的基于分时虚拟机的任务层ACS调度算法和在文献[1]提出的蚁群算法进行比较。设置概率选择方程中的[β]为1.2和[q0]为0.9，，全局信息素更新和局部信息素更新的挥发系数[ρglobal]和[ρloacal]均为0.1。我们设计了5组实验，集成工作流应用的任务个数分别从50到250，对于每个工作流实例运行10次，求平均值后得到实验结果。

通过算法运行得到的结果显示，采用基于分时虚拟机的任务层蚁群调度算法的优化的整体执行时间比采用队列形式的算法得到的执行时间要短。这是由于工作流实例中某些任务是可以并行的，采用队列的形式只能将并行任务串行化，这增加了执行的时间。在100和150的任务数的点上，由于任务是随机生成的，预计开始时间也是随机生成的，造成实际并行的任务数不多，造成两个算法得出的实际的全局完工时间较为接近，但是总局也是由于对比的算法，由此得出，该文提出的算法在对于较多并行任务的执行上存在较大的优势，能够很好的利用虚拟的分时特性，优化系统的执行时间。

4 总结

云工作流调度是云工作流资源管理的核心问题。该文提出的于分时虚拟机的任务层ACS调度算法在满足用户定义的QoS约束，优化系统执行时间，让相同时间内在相同资源尽可能多的任务允许。通过实验证明，该文提出的算法相比于其他算法在对于较多并行任务的执行上存在较大的优势，能够很好的利用虚拟的分时特性，优化系统的执行时间。

参考文献：

[1] Wu Z， Liu X， Ni Z， et al. A market-oriented hierarchical scheduling strategy in cloud workflow systems[J]. The Journal of Supercomputing， 2013， 63（1）： 256-293.

[2] Foster I， Zhao Y， Raicu I， et al. Cloud computing and grid computing 360-degree compared[C]//Grid Computing Environments Workshop， 2008. GCE'08. IEEE， 2008： 1-10.

[3] Zhang X D， Li X P， Wang Q， et al. Hybrid particle swarm optimization algorithm for cost minimization in service-workflows with due dates[J]. Tongxin Xuebao/Commun， 2008， 29（8）.

[4] Buyya R， Yeo C S， Venugopal S， et al. Cloud computing and emerging IT platforms： Vision， hype， and reality for delivering computing as the 5th utility[J]. Future Generation computer systems， 2009， 25（6）： 599-616.

[5] Han J， Kamber M， Pei J. Data mining： concepts and techniques[M]. Morgan kaufmann， 2006.

[6] Pandey S， Wu L， Guru S M， et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//Advanced Information Networking and Applications （AINA）， 2010 24th IEEE International Conference on. IEEE， 2010： 400-407.

[7] Salehi M A， Buyya R. Adapting market-oriented scheduling policies for cloud computing[M]//Algorithms and Architectures for Parallel Processing. Springer Berlin Heidelberg， 2010： 351-362.

[8] 谢海军， 齐连永， 窦万春. 基于 Skyline 和局部选择的启发式服务组合方法[J]. 东南大学学报： 自然科学版， 2011， 41（3）： 449.

[9] Chang R S， Chang J S， Lin P S. An ant algorithm for balanced job scheduling in grids[J]. Future Generation Computer Systems， 2009， 25（1）： 20-27.

[10] Chen W N， Zhang J， Yu Y. Workflow scheduling in grids： an ant colony optimization approach[C]//Evolutionary Computation， 2007. CEC 2007. IEEE Congress on. IEEE， 2007： 3308-3315.

[11] Chen W N， Zhang J. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements[J]. Systems， Man， and Cybernetics， Part C： Applications and Reviews， IEEE Transactions on， 2009， 39（1）： 29-43.

[12] Yang Y， Liu K， Chen J， et al. Peer-to-peer based grid workflow runtime environment of SwinDeW-G[C]//e-Science and Grid Computing， IEEE International Conference on. IEEE， 2007： 51-58.