面向 QoS 与成本感知的云工作流调度优化研究 方伯芃 孙林夫 西南交通大学信息科学与技术学院 西南交通大学制造业产业链协同与信息化支撑技术四川省重点实验室 摘 要： 为有效提升云工作流服务质量、降低运营成本, 对云工作流调度优化问题展开研究。分析问题涉及的不同主体与调度环节, 建立面向 QoS 与成本感知的云工作流调度模型, 并针对问题模型不同阶段的调度策略展开剖析, 依据阶段策略特征设计调度方案的编码规则, 在此基础上提出一种基于任务序列划分的两段式编码遗传算法。该算法以租户流程租约和虚拟机实例负载为约束, 通过两段式交叉、变异算子进行种群的迭代进化, 以实现对云工作流服务费用与云资源使用成本的调度优化。通过对不同规模问题实例进行仿真实验, 结果表明, 所构造算法的解质量明显优于两类基于任务与虚拟机映射编码的遗传算法。关键词： 工作流; 云计算; 资源优化; 任务调度; 遗传算法; 作者简介：方伯芃 (1986-) , 男, 河南罗山人, 西南交通大学博士研究生, 研究方向:产业链协同技术、数据挖掘、最优化理论及应用等;E-mail:644892587qq.com;作者简介：孙林夫 (1963-) , 男, 浙江绍兴人, 博士, 西南交通大学首席教授, 博士生导师, 研究方向:网络化制造技术、产业链协同技术及公共服务平台技术等;E-mail:sunlfvip.sina.com;收稿日期：2017-03-27基金：国家科技支撑计划资助项目 (2015BAF32B05) Cloud workflow scheduling optimization oriented to QoS and cost-awarenessFANG Bopeng SUN Linfu School of Information Science and Technology, Southwest Jiaotong University; Manufacturing Industry Chains Collaboration And Information Support Technology Key Laboratory of Sichuan Province, Southwest Jiaotong University; Abstract： In order to improve QoS while reducing cost of cloud workflow effectively, this paper studies the cloud workflow scheduling optimization. Based on analyzing different involving subjects and scheduling links, a cloud workflow scheduling model oriented to QoS and cost-awareness was established. Meanwhile a coding rule dedicated to scheduling scheme was proposed as a result of analyzing characteristics of the scheduling strategy of the model at different stages. Then a Genetic Algorithm based on Two Segment Coding of Tasks Order Division was proposed. With tenant leases and virtual machine instance loads as constraints, this algorithm advances population evolution through genetic recombination and mutation processes of two segments to achieve both cloud service charge saving and cloud resources cost saving. Simulation experiments were conducted on instances of different sizes, and the results showed that the proposed algorithm can achieve much better solution quality than the two kinds of Genetic Algorithm based on Tasks and Virtual Machines Mapping Coding.Keyword： workflow; cloud computing; resources optimization; task scheduling; genetic algorithms; Received： 2017-03-270.引言随着云计算技术的迅速发展以及云服务模式的不断成熟, 当今 IT 领域正发生着重大变革。云计算作为一种新的服务提供模式, 其高效、灵活、可定制、可扩展的特点帮助用户大大降低软硬件的购买与维护成本。通过互联网, 云计算向用户提供各种计算、存储及应用资源服务, 诸如基础设施即服务 (Infrastructure as a Service, Iaa S) 、平台即服务 (Platform as a Servie, Paa S) 以及软件即服务 (Software as a Service, Saa S) 等1-2, 不同用户则可按各自需求租赁所需的云服务资源, 并依据服务类型和使用时间支付相应的服务费用。云工作流是云计算环境下工作流的一种新型应用模式, 它集成云计算及工作流的技术特征与模式特点, 依据不同租户需求, 将特定的业务流程部署在云平台中, 并允许多个租户能同时在云中设计、配置和操作各自的业务流程, 与此同时实现数据、性能和执行三个层次的隔离3。与传统工作流相比, 其应需服务、随需而变、按需支付的服务特征有效为租户节约成本开支、提高工作效率, 极适宜于那些因缺少资金及人力而无法购买与运维工作流系统的企业用户。云计算中的工作流不仅在应用模式上发挥了更大的优势, 还为租户提供了诸多的高效、便利与灵活, 与此同时, 云工作流的运行环境也与先前发生了巨大的改变, 这使得传统的工作流资源调度方法在新模式中将不再适用, 在云环境下, 相关的模型方法需被重新分析与设计。目前, 关于工作流的调度问题已有较多研究成果, 依据调度目标的不同, 现有研究主要从工作流的完成时间、服务质量以及云资源使用成本三个角度对问题展开分析。最为常见的工作流调度目标是如何更有效的缩减工作流响应完成时间, 这也是早期在网格计算环境下工作流调度通常需要考虑的问题。肖志娇等针对工作流资源配置优化问题展开研究, 提出一种基于分层嵌套遗传算法的资源优化方法, 在成本约束下针对资源专业化/一般化程度及资源数量进行配置优化, 从而最小化工作流实例的平均响应时间4;Amalarethinam 等针对网格工作流调度问题展开研究, 通过建立工作流任务调度模型, 并提出一种最小化完成时间网格工作流调度算法, 基于该算法实现网格工作流完成时间的最小化5;衣杨等针对工作流流水时间资源优化问题进行研究, 建立最小化流水时间的工作流资源优化数学模型, 在此基础上设计精英保存策略改进型遗传算法, 实现工作流最小流水时间的调度寻优6。上述研究能有效降低工作流的完成时间, 提升执行性能与效率。然而在云环境下, 仅考虑工作流的执行时间是不够的, 由于云环境中的工作流是通过服务的形式以满足不同租户业务流程需求, 故如何提升租户的服务质量 (Quality of Service, Qo S) 往往是云工作流调度所关注的重点, 现有的一些研究则致力于解决满足租户期限约束下最小化租户服务费用问题。李学俊等针对云工作流任务调度优化问题展开研究, 提出一种基于新型自适应惯性权重计算法则的改进粒子群算法, 在此基础上求解云工作流截止期限约束下服务费用最低的调度方案7;王岩等针对实例密集型云工作流资源调度问题进行研究, 提出一种基于Qo S 约束的云工作流调度算法, 以寻求截止期限约束下, 有效降低云工作流服务费用的调度策略8;Verma 等针对云工作流调度优化问题进行研究, 考虑云模式中不同类型的定价模型, 并提出一种基于截止时间约束的启发式遗传算法, 在此基础上实现满足期限约束下, 云工作流服务费用的最小化9;郑敏等则将云服务费用价格函数定义为常值型与周期分段型两类模型, 在此基础上研究云工作流任务调度开销问题, 并提出一种基于动态规划的云工作流调度算法, 求解出截止时间约束下租户服务开销最低的调度方案10。与此同时, 云工作流的执行需占用一定的云资源, 对于云服务提供商而言运营成本也是需要重点考虑的对象之一, 现有部分研究则侧重于探索云工作流成本感知与云资源调度优化问题。文一凭等对云工作流的隐私与成本感知技术进行研究, 针对云工作流执行过程中的计算成本、传输成本、存储成本进行云资源使用成本模型的建立, 在粒子群与模拟退火算法基础上引入任务优先级计算策略, 提出一种具有隐私与云资源使用成本感知能力的云工作流调度方法, 寻求隐私保护约束下云资源使用成本最低的调度方案11;沈虹等针对带准备时间和截止期约束的云工作流资源调度问题进行研究, 建立问题优化模型, 并提出一种混合分布估计优化方法, 在此基础上建立云工作流任务与云基础设施资源服务间选择对应关系, 求解出带准备时间和截止期约束下云资源租赁成本最低的调度方案12;Durillo 针对亚马逊弹性计算云工作流调度问题展开研究, 分析云工作流执行过程中的计算、传输与存储三类执行成本, 并提出一种基于Pareto 规则的表调度启发式算法, 以寻求云工作流完成时间最短及执行成本最低的多目标调度优化方案13;Mollajafari 等针对截止期限约束的云工作流资源调度问题展开研究, 提出一种从基因编码到调度方案的新型映射规则, 在此基础上使用遗传算法进行调度寻优, 求解出流程任务与服务资源间的最优映射关系, 以实现满足截止时间约束下云资源使用成本最低的调度方案14。现有文献面对不同调度目标展开了诸多研究, 但大多都从单个角度对问题进行分析与优化, 而忽略了调度中不同主体间利益的博弈与共赢, 事实上, 云工作流的资源调度无论是对于租户而言还是云服务提供商都有着十分重要的意义, 调度优化的目标需对租户服务质量及云服务提供商运营成本进行综合考虑。此外, 现有研究大多针对云工作流任务集与虚拟机类型集间部署关系进行调度优化, 在调度过程中未考虑或是简化了虚拟机的负载约束与实例数量问题, 如文献 15 在处理云工作流调度问题时作出假设“各种类型的虚拟机拥有足够的能力执行任务, 在执行过程中其计算能力不会变化, 且每类虚拟机拥有足够多的虚拟机实例15”。然而, 在实际中虚拟机实例存在着诸如 CPU、内存、存储等多种类型的资源负载约束, 它们中的任何一种资源出现超载都将对虚拟机的整体性能造成极大影响, 最终波及租户的服务质量;但若是为了均衡负载, 而又随意的增加虚拟机实例数量, 则会造成虚拟机资源的闲置浪费, 从而加大了云服务提供商的运营成本。因此, 云工作流的调度目标不仅需考虑云工作流任务集与虚拟机类型集间的部署关系, 更需要考虑任务集与虚拟机实例集间的部署关系以及各类虚拟机实例的数量大小。最后, 由于云工作流技术融合了工作流系统与云计算平台两者的技术特征, 故即具有工作流的流程配置特性, 又具备云计算平台的多租户特征,