云计算是一种能将计算任务分布在大量计算机组成的资源池上的商业计算模型, 使用户能够获取计算力、信息服务和存储空间^[1].工作流系统在云计算环境中不仅能发挥更大的效用, 还能为云计算服务提供便利^[2].因云环境下的工作流系统的高效、灵活等特点, 云工作流技术成为研究热点.

如何针对各种目标进行调度是云工作流技术中的热点问题.以性能为中心的调度算法主要以调度性能作为最终目标, 如可靠性、任务最早完成时间、资源利用率等.Lee等^[3]提出最大有效减少(maximum effective reduction, MER)算法, 改善资源利用率, 减少资源配置, 节省能源消耗.黄婷婷等^[4]提出一种结合模拟退火算法和遗传算法的任务完成时间-可靠性的多目标优化算法.Casas等^[5]提出了一种平衡和文件重用-复制调度(balanced and filereuse-replication scheduling, BaRRS)算法以优化对云工作流的调度, 通过并行平衡系统利用率, 利用数据重用和复制技术来优化在运行时任务之间传输需要的数据量.Starlinger等^[6-7]基于科学工作流分层、分阶段研究, 提出了新方法以高效地进行工作流调度.Kianpisheh等^[8]提出了一种调度算法最大化工作流执行的可靠性, 同时尊重用户定义的最后期限和预算.以服务质量为中心的调度算法主要以保障用户的服务质量(quality of service, QoS)作为最终目标, 如经济性、时间性、安全性等.刘井响等^[9]提出一种考虑云环境中廉价资源的基于批量处理策略的云工作流调度方法, 在小范围取得趋近全局最优调度的结果.文一凭等^[10]提出了一种云工作流调度算法CP-PSO (cost-aware and privacy-aware scheduling algorithm based on particle swarm optimization)满足用户的隐私保护和成本需求.Poola等^[11]提出了一个调度算法安排任务在云资源使用2个不同的定价模型(现货和随需应变实例)来调度任务，降低执行成本的同时满足工作流的最后期限.杨玉丽等^[12-13]利用粒子群算法优化云工作流调度模型使该算法的时间性能较优.李智勇等^[14]提出了新的文化基因(Memetic)优化方法以解决异构云环境多目标调度优化问题.魏豪等^[15]提出了一种基于应用特征的平台即服务(platform as a service, PaaS)弹性资源管理机制(application feature based elastic resource management mechanism, AFERM), 能够在保证服务质量的前提下, 有效地减少服务器的使用. Zeng等^[16]介绍了一种自适应数据感知调度(ADAS)工作流应用程序的策略.Fatih等^[17]利用软件定义网络(software-defined networking, SDN)解决数据传输服务的控制问题和资源配置, 以满足从多个耦合工作流共享相同的服务中的不同QoS要求.

现在已有很多研究分别将用户成本或系统利用率作为目标进行调度, 本文提出一种基于新颖性排名和多QoS目标的云工作流调度算法，综合考虑用户成本和系统利用率, 将资源节点执行任务的频度、任务的等待时间和执行时间作为因子加入推荐模型, 并使用模拟退火算法(simulated annealing algorithm, SA)训练求出推荐模型中的未知量, 从而计算出每个任务在各个资源节点上的优先级因子, 调度器根据当前任务的优先级因子表进行调度, 同时将此次调度后资源节点执行任务的频度、任务的等待时间和执行时间更新到该任务的优先级因子表, 从而优化推荐模型.使用本文提出的算法, 用户成本和系统使用率的综合指标更好.

1 调度算法 1.1 调度流程

本文提出基于云环境的工作流调度算法, 考虑云环境内有多台异构的虚拟机执行任务, 由统一的调度器根据策略分发任务到各个虚拟机执行.本文任务调度考虑的目标是系统的利用率、任务的执行时间和等待时间这3种QoS属性.其中系统的利用率通过虚拟机的新颖性(给调度器推荐那些以前没有分发到或少分发的虚拟机)来体现.当用户提交任务组成任务集合后, 调度器会根据考虑了目标的该任务的优先级因子表进行调度, 分发任务到具体的虚拟机上执行并更新优先级因子表, 继续调度任务, 直到任务集合为空.本文提出的云工作流任务的调度过程如图 1所示.

1.2 相关定义 1.2.1 工作流模型

根据传统的工作流模型, 本文用有向无环图(directed acyclic graph, DAG)将工作流模型定义为G=(V, E). V代表任务节点集合：

$ \mathit{\boldsymbol{V}} = \left\{ {\left( {{t_1}, T_{{\rm{e\_avg}}}^{^1}} \right)} \right., \left( {{t_2}, T_{{\rm{e\_avg}}}^2} \right), \ldots, \left. {\left( {{t_n}, T_{{\rm{e\_avg}}}^n} \right)} \right\}. $

式中：T_{e_avg}ⁿ为任务t_n在所有虚拟机上的平均执行时间；E为任务节点间的依赖关系集合.

1.2.2 新颖性

考虑新颖性是指给任务推荐那些它以前没有分发到或少分发的虚拟机, 如果推荐结果中虚拟机的平均调度频度较低, 那么该推荐就可能有较高的新颖性.比如, 现有虚拟机1、2、3, 等待任务被调度.因为虚拟机1拥有更高的执行速度, 所以在前面的调度过程中任务t_i总是被调度到虚拟机1执行, 此时虚拟机2、3对于t_i来说是新颖的.新颖性也就是在推荐时, 乘以因子1/log(1+αN_j)对虚拟机的调度频度进行降权, 其中N_j为虚拟机上执行任务的频度, α为调度因子.

1.2.3 资源节点指标

采用计算资源节点j(j=1, 2, …, K；K为资源节点总数)上已经执行任务的个数来表示资源节点执行任务的频度, 用N_j表示.当调度器调度任务i到资源节点j上执行, 当资源节点j执行完任务i, 频度N_j加1.整个系统资源节点利用率为

$ r = \frac{{\sum\nolimits_{j = 1}^K {{N_j}} }}{{K \cdot \mathop {\max }\limits_{j \le K} \left( {{N_j}} \right)}} \times 100\% . $

(1)

1.2.4 时间指标

任务i从进入调度器的调度队列直到被调度器调度所经过的时间称为任务i的等待时间.任务i在调度器上所有等待时间的平均值称为任务i的平均等待时间.调度器将任务i分发到资源节点j上, 处理任务i所花费的时间称为任务i的执行时间.任务i在各个资源节点上所有执行时间的平均值称为任务i的平均执行时间.

1.2.5 优先级因子

表示任务i在资源节点j上执行的优先级, 用P_ji表示, 如式(2) 所示.优先级因子越大表明优先级越大, 即任务i应该优先被调度到资源节点j上更能满足算法目标.

$ {P_{ji}} = \frac{{\exp \left[{-\theta \left( {\overline {T_{\rm{w}}^i} + \overline {T_{\rm{e}}^i} } \right)} \right]}}{{\log \left( {1 + \alpha {N_j}} \right)}} $

(2)

1.2.6 优先级因子表

每个任务有一张优先级因子表, 记录各资源节点执行任务的频度N_j、任务i的平均等待时间、平均执行时间以及任务i在各资源节点的优先级因子.

1.3 问题描述及流程建模

本文要解决的是在云工作流调度问题中考虑系统利用率、任务的等待时间和执行时间, 提高系统利用率的同时, 降低任务的等待时间.现有最优化目标为系统利用率、任务的等待时间和执行时间的综合指标, 根据前述定义, 可建立优化模型如下：

$ F = \min \left( {-{f_1}, -{f_2}} \right) =-p*{f_1} - \left( {1 - p} \right)*{f_2}. $

(3)

$ {\rm{s}}.{\rm{t}}.\;\;\;\;{f_1} = r = \frac{1}{{K \cdot \mathop {\max }\limits_{j \le K} \left( {{N_j}} \right)}} \bullet \sum\limits_{j = 1}^K {{N_j}} . $

(4)

$ {f_2} = \frac{1}{M} \bullet \sum\limits_{i = 1}^M {\mathop {\max }\limits_{j \le K} } \left( {{P_{ji}}} \right). $

(5)

式(3) 描述了问题的目标函数；式(4) 描述了系统利用率；式(5) 描述了资源节点执行任务的频度、任务的等待时间和执行时间的优先级因子最大值之和的平均值.式中：f₁, f₂为约束目标, p为自变量, r为节点利用率, K为资源节点总数, N_j为虚拟机上执行任务的频度, P_ji为优先级因子, M为任务总数.

该优化模型有3个自变量p、α、θ, 采用模拟退火算法进行求解.由一定的仿真实验可知, 0 < p < 1, α > 1, 0 < θ < 1, 控制变量在(0, 1), 设定初始向量(p₀, 1/α₀, θ₀), 初始温度T₀, 控制降温快慢的d, 温度下限T_min, 初始解F(p₀, α₀, θ₀), 循环求解F(p, α, θ), 求得最优F(p, α, θ)时的自变量p、α、θ.采用梯度下降法, 根据偏导数公式(6)~(8), 由上一个解(p_i, α_i, θ_i)求得(p_i+1, α_i+1, θ_i+1):

$ {p_{i + 1}} \leftarrow {p_i}-{f_1} + {f_2}. $

(6)

$ \begin{array}{l} {\alpha _{i + 1}} \leftarrow {\alpha _i} + \\ \frac{1}{M} \bullet \sum\limits_{i = 1}^M {\mathop {\max }\limits_{j \le K} } \frac{{- \exp \left[{-{\theta _i}\left( {\overline {T_{\rm{w}}^i} + \overline {T_{\rm{e}}^i} } \right)} \right] \bullet {N_j}}}{{{{\log }^2}\left( {1 + {\alpha _i}{N_j}} \right)\left( {1 + {\alpha _i}{N_j}} \right)}}. \end{array} $

(7)

$ {\theta _{i + 1}} \leftarrow {\theta _i}- \sum\limits_{i = 1}^M {\mathop {\max }\limits_{j \le K} } \frac{{\left( {\overline {T_{\rm{w}}^i} + \overline {T_{\rm{e}}^i} } \right)\exp \left[{-{\theta _i}\left( {\overline {T_{\rm{w}}^i} + \overline {T_{\rm{e}}^i} } \right)} \right]}}{{M \bullet \log \left( {1 + {\alpha _i}{N_j}} \right)}} $

(8)

本文将工作流模型定义为有向无环图(DAG), 任务i(i=1, 2, …, M)准备执行时, 进入调度器的等待队列等待被调度.利用推荐系统^[18]建模, 将3个因素考虑成推荐物品时需要考虑的属性.利用新颖性排名及资源节点j执行任务的频度, 对热门资源节点进行降权, 推荐不常用的资源节点从而提高系统利用率.再考虑任务的平均等待时间$\overline {T_{\rm{w}}^i} $和平均执行时间$\overline {T_{\rm{e}}^i} $与优先级因子P_ji成反比, 得到优先级因子P_ji, 从而, 调度器根据优先级因子表将任务i调度到资源节点j执行.

1.4 调度算法

基于新颖性排名和多QoS目标的云工作流调度算法(cloud service workflow scheduling algorithm based on novelty ranking strategy and multi-QoS objective, RMO-CWS)如算法1所示.首先, 初始化各参数, 如资源节点的频度、任务的等待时间和执行时间以及优先级因子表.各个任务进入等待队列, 使用模拟退火算法求解α、θ, 通过控制降温快慢的d因子降温, 在当前温度大于最小温度时, 计算i+1和i时2个状态之间的温差, 若温差大于0, 取移动后更优路径, 否则, 一定概率接受移动.根据优先级因子表调度任务, 每执行完一个任务, 根据该任务的等待时间、执行时间, 用更新优先级因子表算法更新该任务的优先级因子表.

算法1：基于新颖性排名和多QoS目标的云工作流调度

算法

输入：任务等待队列TQ, 优先级因子表PFT

输出：各个任务将会调度到的资源节点序列S

BEGIN

01:WHILE TQ不为空DO

02:  WHILE T > T_minDO

03:    计算ΔE=F(α_i+1, θ_i+1)-F(α_i, θ_i)

04:    IF ΔE≥0 THEN

05:    F(α_i+1, θ_i+1)=F(α_i, θ_i), 移动后获得更优路径, 总是接受移动

06:    ELSE

07:       IF exp(ΔE/T) < random(0, 1) THEN

08:         F(α_i+1, θ_i+1)=F(α_i, θ_i),

        接受从F(i)到F(i+1) 的移动

09:    END IF

10:  END IF

11:  T^*=d, 退火冷却, 0 < d < 1. d更大时, 冷却更慢; d更小时, 冷却更快

12:  i++

13:  END WHILE

14:  取得TQ中的t_i

15:  找到PFT中将运行t_i的资源节点j

16:  S←j, 将j添加到序列S

17:  UpdatePFT(j, T_wⁱ, T_eⁱ)

18: END WHILE

END

更新优先级因子表算法UpdatePFT(j, T_wⁱ, T_eⁱ), 该算法运用机器学习中增强学习的思想, 对每个相同任务的执行情况进行学习, 更新每个任务的优先级因子表PFT, 如算法2所示.根据输入任务i的等待时间T_wⁱ、执行时间T_eⁱ和优先级因子表PFT中的平均等待时间$\overline {T_{\rm{w}}^i} $、平均执行时间$\overline {T_{\rm{e}}^i} $计算出新的$\overline {T_{\rm{w}}^i} {\rm{、}}\overline {T_{\rm{e}}^i} $；根据资源节点编号j, 更新N_j；再根据N_j、$\overline {T_{\rm{w}}^i} {\rm{、}}\overline {T_{\rm{e}}^i} $, 计算P_ji, 更新PFT.

算法2：更新优先级因子表UpdatePFT(j, T_wⁱ, T_eⁱ)

输入：资源节点编号j, 任务i的等待时间T_wⁱ、执行时间T_eⁱ, 优先级因子表PFT

输出：更新后的优先级因子表PFT

BEGIN

01:根据PFT.$\overline {T_{\rm{w}}^i} $和$T_{\rm{w}}^i$, 计算$\overline {T_{\rm{w}}^i} $

02:根据PFT.$\overline {T_{\rm{e}}^i} $和$T_{\rm{e}}^i$, 计算$\overline {T_{\rm{e}}^i} $

03:更新N_j

04:计算${P_{ji}} = \frac{{\exp \left[{-\theta \left( {\overline {T_{\rm{w}}^i} + \overline {T_{\rm{e}}^i} } \right)} \right]}}{{\log \left( {1 + \alpha {N_j}} \right)}}$

05:更新PFT

END

2 仿真实验

为分析和评估RMO-CWS算法的性能, 本文在CloudSim^[19]平台上进行仿真调度实验.由于本文不考虑数据问题, 实验采用1个数据中心、10个不同类型的虚拟机实例.所采用的工作流模型如图 2所示, 由2种节点组成：灰色阴影节点表示需要从资源数据中读取数据, 白色节点不需要；节点中的字母标号为任务的标识, 如t₁；节点中的数字代表该节点的任务在所有虚拟机上的平均执行时间, 由该节点的任务长度与3台虚拟机的平均执行速度求商得到；流程数据走向由实线箭头标明, 当执行完t₁后, 会根据实线箭头执行t₂；资源数据读取由虚线箭头标明, 当执行任务t₁时, 会根据虚线箭头读取资源数据保证任务能够执行.工作流中各任务参数(通过随机产生12个任务、每个任务大小不同)设置如表 1所示.不同的类型虚拟机实例参数设置如表 2所示.表中, f为虚拟机的执行频率, 通过虚拟机的每秒百万条指令(million instructions per second, MIPS)表示. RMO-CWS算法在进行模拟退火算法求解α、θ时, 初始值α₀=1、θ₀=1、T=100、T_min=e^-8.

如图 3所示为Max-Min算法、Min-Min算法、Q-learning算法^[20]和RMO-CWS算法分别在4台和8台虚拟机上随着任务数x的改变时, 任务总执行时间T_{e_total}的变化情况.由图可知, Max-Min算法、Min-Min算法在不同虚拟机数量上任务总执行时间有一定的变化, Q-learning算法和RMO-CWS算法变化不大.RMO-CWS算法的任务总执行时间始终低于其他3种算法.并且随着任务数增多, RMO-CWS算法相较于其他3种算法的优势更明显.当任务数为1 000~2 000, 虚拟机为4台时, RMO-CWS算法的任务总执行时间较Max-Min算法和Min-Min算法提升了15.2%~17.1%, 较Q-learning算法提升了9.1%~10.7%.当任务数为1 000~2 000, 虚拟机为8台时, RMO-CWS算法的任务总执行时间较Max-Min算法和Min-Min算法提升了10.9%~13.4%, 较Q-learning算法提升了7.4%~9.6%.

如图 4所示为不同任务数x, Max-Min算法、Min-Min算法、Q-learning算法和RMO-CWS算法在4台虚拟机上任务平均执行时间T_{e_avg}的变化.可以看出, RMO-CWS算法的柱形始终低于其他3种算法, 任务的平均执行时间更短.随着任务数增多, Max-Min算法、Min-Min算法、Q-learning算法3种算法的任务平均执行时间变化平稳, RMO-CWS算法任务平均执行时间呈下降趋势, 说明RMO-CWS算法在任务数多的情况下, 表现更优.当任务数为1 000~2 000, 虚拟机为4台时, RMO-CWS算法的任务平均执行时间较Max-Min算法和Min-Min算法提升了15.3%~17.1%, 较Q-learning算法提升了9.1%~10.7%.

如图 5(a)所示为RMO-CWS算法在不同任务数x, 不同虚拟机数下的任务总执行时间T_{e_total}.虚拟机数从3台递增到10台, 虚拟机参数如表 2所示.图中8条折线都呈递增趋势, 形态相似.随着任务数的增加, 任务的总执行时间也随之增加, 且接近线性增长, 由此可见该算法的执行时间增长较稳定.

如图 5(b)所示为RMO-CWS算法在不同任务数x, 不同虚拟机数下的任务平均执行时间T_{e_avg}.虚拟机数同样从3台递增到10台, 虚拟机参数如表 2所示.整体来看, 8条折线的形态相似, 都是呈递减趋势, 且随着任务数增多, 折线变化趋势变缓, 尤其是任务数大于2 000时, 折线趋于水平.由图形可以看出，随着任务数的增多, 任务平均执行时间减少, 这说明RMO-CWS算法在任务数较多的情况下表现更好.

3 结语

本文提出基于新颖性排名和多QoS目标的RMO-CWS算法, 在云工作流调度问题上加入了推荐系统方面的新颖性排名对各个资源节点进行负载均衡, 为云工作流调度的优化问题提供了新思路.在CloudSim平台上进行的模拟调度仿真实验结果表明：RMO-CWS算法在任务执行时间方面优于Q-learning算法, 并且随着任务数增加, RMO-CWS算法的优势越明显.

现阶段RMO-CWS算法只考虑了利用任务的新颖性来达到优化目标.在未来的工作中, 将会考虑如何更好的求未知量, 得到更优的推荐模型, 并考虑对云工作流调度进行重新建模, 增加任务的属性, 利用推荐系统的其他知识对调度进行优化, 研究除了利用率、时间之外的多目标云工作流调度.