一种基于多阶段PSO的多目标工作流调度算法

申秋慧 牛玲

摘 要：基于启发式算法的工作流调度算法目标单一，无法保证用户满意度，且多目标调度算法少、性能差。为了改善现状，提出基于多阶段PSO的多目标工作流调度算法MSPSO，分析工作流任务的层次结构，按层次进行多阶段PSO调度，结合排队理论估算每阶段调度需要的虚拟机数量，控制PSO搜索空间，使算法能快速找到最优解。用4种真实科学工作流在CloudSim环境下进行仿真实验。结果表明，MSPSO算法资源利用率提高了1.81%，能耗降低了9.16%，任务违约率低至0.075%。MSPSO调度算法不仅能动态增减虚拟机，降低能耗，还能在保证截止时间的前提下降低任务违约率，提高资源利用率。

关键词：工作流调度;PSO;CPU能耗;云计算

DOI：10. 11907/rjdk. 191474 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2019）009-0081-04

A Multi-objective Workflow Scheduling Algorithm Based on Multi-Stage PSO

SHEN Qiu-hui，NIU Ling

（School of Computer Science and Technology， Zhoukou Normal University， Zhoukou 466000，China）

Abstract： In order to improve the current situation of workflow scheduling algorithm based on heuristic algorithm， which has single goal， can not guarantee user satisfaction， and has few multi-objective scheduling algorithms and poor performance， based on PSO algorithm， a multi-objective workflow scheduling algorithm MSPSO based on multi-stage PSO is proposed. Firstly， the hierarchical structure of workflow tasks is analyzed， and multi-stage PSO scheduling is carried out according to the hierarchical structure. At the same time， the number of virtual machines needed for each stage scheduling is estimated by queuing theory， and the search space of PSO is controlled， so that the algorithm can quickly find the optimal solution. Four kinds of real scientific workflow are used to simulate the experiment in CloudSim environment. The results show that the resource utilization of MSPSO algorithm is increased by 1.81%， the energy consumption is reduced by 9.16%， and the task default rate is reduced to 0.075%. MSPSO scheduling algorithm can not only dynamically increase and decrease the energy consumption of virtual machines， but also reduce the default rate of tasks and improve resource utilization on the premise of guaranteeing deadlines.

Key Words：workflow scheduling; PSO; CPU consumption; cloud computing

0 引言

工作流可以表示為一个有向无环图，任务表示节点，边表示任务间的依赖关系，所以工作流调度就属于一类NP（Non-deterministic Polynomial）完全问题。研究者提出了各种基于启发式和元启发式的算法解决工作流调度问题[1]。文献[2]开发了一个称为Dyna的调度系统，在用户指定的概率期限保证下，将预期货币成本最小化;文献[3]提出了一种基于任务序列划分的两段式编码遗传算法，考虑流式工作特点和地理分布式控制系统的价格差异，以租户流程租约和虚拟机实例负载为约束，通过两段式交叉、变异算子进行种群迭代进化，实现服务费用与使用成本优化;文献[4]对PSO（Particle Swarm Optimizat）算法进行了改进，优化目标是执行代价和通信代价最小;文献[5]考虑工作流中间数据存储，将竞价实例与按需实例相结合，提出了一种调度总费用最小化算法;文献[6]提出了一个复合迭代局部搜索算法，以成本最小为优化目标;文献[7]提出了一种离线容错弹性调度算法，能够有效地为云系统中资源利用率较高的工作流提供相应容错调度策略，任务违约率低;文献[8]基于定价模型提出了一种针对特定问题的编码种群初始化、适应度评估和遗传算子新方案，在大多数有INS的工作流程中具有更高可靠性;文献[9]针对数据密集型工作流，提出了一种面向负载均衡的数据约减策略，以较少调度时间为目标;文献[10]以截止时间为目标，提出了一种满足期限约束的工作流调度算法;文献[11]从云工作流任务分配、主机负载和主机功耗关系角度出发，提出了一种面向能耗的云工作流调度优化方法;文献[12]提出了一种两阶段调度算法，第一阶段进行预调度，第二阶段进行负载感知动态调度，两阶段结合实现高资源利用率目的;文献[13]提出的调度算法，分析了最小时间增加与最大化资源减少量之间的平衡点，通过合并任务和资源以提高资源利用率。

上述算法大多只考虑了一个目标，比如执行成本最低、完成时间最短、能耗低、资源利用率高、系统可靠性高等。而对于一个以上的多目标调度则研究较少，只有文献[14]针对大数据环境下的科学工作流调度提出了一种考虑总完成时间和负载均衡的最大百分比调度算法，但调度算法是静态调度;文献[15]提出了一种双目标遗传算法（BOGA），以实现工作流调度的低能耗、高系统可靠性;文献[16]提出的多目标差分演化（MODE）算法基于重力搜索算法，以执行时间和成本最小化为目标;文献[17]提出的多目标异类最早完成时间（MOHEFT）算法同时考虑了完成时间和能耗两个目标。

因此，研究多目标工作流调度是一个挑战，本文基于粒子群算法结合排队理论提出了一种多阶段多目标的工作流调度算法，在保证完成时间的前提下，能达到低能耗、高资源利用率和高可靠性的多目标调度，改善了多目标工作流调度算法数量少、性能差的现状。

1 问题描述

云环境下一个工作流WF可以用两个集合表示，即WF=（T，E），其中T={t1，t2，t3，…，tn}是WF中所有任务的集合，任务个数为n，E是有向边的集合，其中元素为eij，表示任务ti与tj之间存在依赖关系，ti是tj的父任务，tj是ti的子任务，tj必须在ti完成后才能开始执行。工作流结构是可以被分析的，当工作流到达时，根据任务间的依赖关系将工作流分成x层，第i层任务个数用ni表示，任务的集合用Ti表示[18]。如图1所示，第一层任务个数n1=2，任务集合T1={t1，t2};第二层任务个数n2=8;第三层任务个数n3=9;第4层任务个数n4=1。

本文定义按层次对工作流任务进行调度。用V={v1，v2，v3，…，vm}表示云计算系统中m个活动虚拟机的集合，m的大小随着负载变化而动态变化。每台物理机hi上各虚拟机的CPU计算能力总和不超过物理机CPU峰值的70%，因为如果再配置新的虚拟机到hi，会导致能耗大幅度提升[19]。每台虚拟机vj一个时间只执行一个任务ti，对ni个任务在m个虚拟机上调度就可以转化为一个M/M/n排队模型。当系统处于平衡状态时，由排队理论可通过式（1）计算出任务的平均响应时间TRi[5]。

其中，[P0=（k=0mρk1k！+ρn1/1-ρm！）-1]，ρ1=λμ，ρ=λμ/n表示服务强度，λ表示系统中工作流任务到达的速率，μ表示各任务的平均执行时间，m表示虚拟机个数，对应于排队系统中服务窗口个数。

用stj表示虚拟机vj执行任务开始时间，用etj表示执行任务结束时间，用M表示任务到虚拟机的映射集合，由tij=（ti，vj，sti，eti）组成，表示任务ti在虚拟机vj上运行，运行开始时间是sti，结束时间是eti。工作流任务第i层的开始时间STi=Minimize sti，结束时间ETi= Maximize eti，用STWF表示工作流的到达时间，则工作流的完成时间ETWF可由式（2）计算得到。

综上所述，工作流调度问题可以表示成一个四元组S=（T，V，M，ETWF），约束条件为ETWF≤deadline。在满足截止时间的前提下，可以计算得到每一次调度最合适的TRi，虽然任务是动态变化的，但每一次调度时都可以統计出需要调度的任务个数，进而可以推算出每一次调度时满足任务要求的虚拟机个数，虚拟机个数m随负载动态变化，任务多时开启新的虚拟机，任务少时关闭空闲虚拟机，不仅提高了虚拟机资源利用率，还达到了动态节能目的。在可靠性方面，若上一层调度存在失败节点，在下一层调度时会实时增加虚拟机数量，保证任务顺利完成。每一次调度都采用种群规模相对较小的PSO算法，不仅能快速收敛，找到最优解，而且还能使调度策略的鲁棒性更好。

2 多阶段PSO调度算法

2.1 PSO模型

用PSO解决问题有两个关键步骤：一是设置问题的编码方式，二是定义适应度函数。为了定义问题的编码方式，需要先建立粒子的含义和尺寸。对于提出的调度策略，一个粒子代表工作流的一个层次和子任务，即第i阶段粒子的尺寸是ni。粒子的尺寸决定空间中粒子所在位置的坐标个数。比如，5个粒子的位置用5个坐标表示，6个粒子用6个坐标表示。系统中每阶段可用虚拟机个数m决定了粒子移动的范围。因此，坐标值范围是0-m。粒子位置坐标值向下取整，表示该虚拟机被分配给了粒子所表示的任务。这样，粒子的位置就能描述任务到虚拟机的映射。比如，系统中有6个虚拟机，每个粒子的坐标值都在0和6之间，坐标1表示t1值是1.3，意味着t1被分配给了v1，坐标2相当于t2值是3.1，表示t2被分配给了v3，以此类推。

由于云环境中虚拟机和任务个数都是无限的，因此PSO搜索空间会很大，导致算法收敛慢并很难找到合适的解。为了减小搜索空间，提出了分阶段调度方案。第一阶段调度时搜索空间规模即虚拟机个数m设置为第一层任务的个数n1，之后每个阶段搜索空间规模在满足式（1），即满足该阶段任务响应时间的前提下，计算取最小的m值，也就是说之后每一个阶段调度都是在满足该阶段任务响应时间的前提下取最小虚拟机个数，这样不仅能使PSO收敛速度快，而且找到最优解相对容易。同时，系统中运行的虚拟机个数随负载动态变化，且被充分利用，相比不分阶段的PSO，需要的虚拟机个数明显减少且没有空闲虚拟机，不仅提高了资源利用率，也降低了系统能耗，实现了保证完成时间、高资源利用率、低能耗的多目标调度。

2.2 调度算法

多阶段PSO调度算法思想是当一个工作流任务到达时，首先分析它的结构，把它分为x层，每一层依次采用PSO进行调度。初始化粒子位置P[i]为一组0-mj的随机数。第一层比较特殊，没有父节点，所以初始化虚拟机个数就是第一层任务的个数n1，后面每一次调度粒子的规模根据式（1）计算得到，若下一阶段调度时粒子规模大于上一阶段粒子规模，就部署新的虚拟机，否则关闭虚拟机。调度时用执行时间最短作为适应度函数选择优秀粒子的位置，第j阶段调度输出的是第j层任务的调度表。当调度算法在执行第j+1层PSO时，第j层的调度表已经输出，调度中心就可以展开实际调度，调度算法执行和任务执行可以并行，这样可以减少工作流的完成时间。另外若已调度任务中有执行失败的，可以在下一阶段重新参与调度，这样可以有效降低任务违约率，提高系统对工作流任务执行的成功率。算法具体描述如下：

3 实验与性能分析

本文使用CloudSim框架运行在实验室的真实云环境中进行实验，选择来自不同科学领域具有不同结构、数据和计算特点的4个真实工作流Montage、LIGO、SIPHT和CyberShake作为实验输入。用本文多阶段PSO调度（MSPSO）算法与双目标遗传算法（BOGA）、多目标异类最早完成时间（MOHEFT）算法、多目标差分演化（MODE），在完成时间、资源利用率、系统能耗和任务违约率4个方面进行比较。

3.1 实验设置

实验运行在一台IBM高性能服务器上，假设采用同一类型虚拟机，参数是：CPU计算能力为4 400MIPS，存储容量50GB，带宽2G。虚拟机每次运行一个任务，每种算法执行20次，求平均值作为最终实验结果。初始虚拟机个数取工作流第一层任务个数。根据文献[20]研究成果PSO算法中的参数c1、c2和ω，取值为c1=c2=2，ω=0.5。

3.2 结果分析

仿真实验时，分别设置工作流规模为50、100、1 000个任务，结果表明，虽然任务规模与完成时间、能耗、资源利用率有直接关系，但是在证明算法性能上50、100和1 000个任务结果是相同的，因此结果分析以100个任务为代表。任务完成时间如图2所示，BOGA算法完成时间最小，表现最好，MSPSO算法次之，比其高了8.39%，原因在于BOGA算法以完成时间最短为目标，而MSPSO算法是多目标的，在保证截止时间的前提下首先优化的是系统能耗和资源利用率，然后才是完成时间。如图3、图4所示，在系统能耗和资源利用率方面，MSPSO算法表现最好，能耗降低了9.16%，资源利用率提高了1.81%，原因是MSPSO算法调度时虚拟机是随着每一阶段任务个数动态增减的，能及时关闭空闲虚拟机降低系统能耗，且系统中每一个活动虚拟机都被充分利用，而虚拟机部署时也是在保证物理机性能的情况下装载尽可能多虚拟机。另外，MSPSO还有一个好处就是上一阶段执行失败的任务将在下一阶段重新被调度，降低任务违约率。如图5所示，MSPSO算法任务违约率最低，为0.075%。

4 结语

本文分析了现有工作流调度算法，发现多目标工作流调度算法较少，因此提出一种结合排队理论、基于多阶段PSO的多目标调度算法MSPSO，该算法在保证截止时间的前提下，对工作流进行多阶段PSO调度，不仅能够动态增减虚拟机以降低能耗，还能提高资源利用率并降低任务违约率。实验验证了MSPSO算法的优越性，虽然完成时间略高于以最小完成时间为目标的BOGA算法，但在系统能耗、资源利用率、任务违约率方面表现最好。

MSPSO算法虽然能动态增减虚拟机，但是没有考虑虚拟机关闭和开启的能耗代价，因此未来会考虑把开关虚拟机能耗开销引入MSPSO，对MSPSO作进一步优化和验证。

参考文献：

[1] 马俊涛，陈业恩，胡国杰，等. 云计算环境下基于遗传算法的任务调度技术研究[J]. 软件导刊， 2016， 15（1）：51-53.

[2] ZHOU A C，HE B，LIU C. Monetary cost optimizations for hosting workflow-as-a-service in IaaS clouds[J]. IEEE Transactions on Cloud Computing， 2013， 4（1）：34-48.

[3] 方伯芃，孫林夫. 面向QoS与成本感知的云工作流调度优化[J]. 计算机集成制造系统，2018，24（2）：331-348.

[4] 郭文涛，卢少武. 基于代价优化的云工作流调度改进PSO算法[J]. 计算机测量与控制，2017，25（6）：162-166.

[5] 马子泰，曹健，姚艳. 云环境下使用竞价实例并考虑中间数据存储策略的工作流调度方法[J]. 计算机集成制造系统， 2017， 23（5）：983-992.

[6] 王宏欣，张跃. 带截止期约束的多模态云服务工作流调度[J]. 小型微型计算机系统， 2016， 37（11）：2437-2442.

[7] DING Y，YAO G，HAO K. Fault-tolerant elastic scheduling algorithm for workflow in Cloud systems[M]. Elsevier Science Inc，2017， 393：47-65.

[8] ZHU Z，ZHANG G，MEMBER S，et al. Evolutionary multi-objective workflow scheduling in cloud[J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（5）：1344-1357.

[9] 胡志刚，李佳，郑美光. 云环境下面向负载均衡的数据密集型工作流的数据约简策略[J/OL]. 计算机应用研究：2018-05-24 21：09：29. http：//kns.cnki.net/KCMS/detail/51.1196.TP.20180524.2109.020.html.

[10] 张秋霞，张来顺. 云环境中满足期限约束的工作流任务调度[J].  计算机工程与设计， 2019， 40（2）：425-432.

[11] 谢毅，贺田塔，倪倩芸，等. 面向能耗的云工作流调度优化[J].  系统工程理论与实践， 2017，37（4）：1056-1071.

[12] 王岩，汪晋宽，韩英华. 面向云工作流的两阶段资源调度方法[J]. 华南理工大学学报：自然科学版， 2017， 45（1）：80-87.

[13] 刘晓天，朱耀琴，顾大明. 有效资源减少量最大化的云计算工作流调度[J]. 计算机工程与设计， 2017， 38（11）：82-88.

[14] LI X， SONG J，HUANG B. A scientific workflow management system architecture and its scheduling based on cloud service platform for manufacturing big data analytics[J].  The International Journal of Advanced Manufacturing Technology， 2016， 84（1-4）：119-131.

[15] ZHANG L，LI K，LI C，et al. Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems[J].  Information Sciences， 2017， 379：241-256.

[16] ARSUAGA-RíOS，MARíA，VEGA-RODRíGUEZ，et al.Meta-schedulers for grid computing based on multi-objective swarm algorithms[J].  Applied Soft Computing， 2013， 13（4）：1567-1582.

[17] DURILLO J J，NAE V，PRODAN R.  Multi-objective energy-efficient workflow scheduling using list-based heuristics[J].  Future Generation Computer Systems， 2014， 36：221-236.

[18] RODRIGUEZ M A，BUYYA R.  Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].  IEEE Transactions on Cloud Computing， 2014， 2（2）：222-235.

[19] HSU C H，SLAGTER K D，CHEN S C，et al. Optimizing energy consumption with task consolidation in clouds[J]. Information Sciences， 2014， 258：452-462.

[20] 冀云，高世澤. 输入率和服务率可变且窗口能力不等的M/M/n排队模型研究[J]. 重庆师范大学学报：自然科学版，2014，31（3）：65-67.

（责任编辑：何 丽）