0 引言

随着新基建建设的提速, 数据中心建设步伐明显加快. 普通数据中心一般由5~10万台服务器组成, 但国内外著名互联网公司的数据中心规模远不止如此, 谷歌全球数据中心的服务器总量已超百万台, 为用户提供搜索服务; 亚马逊公司仅弹性计算云(elastic compute cloud, EC2)就部署了约50万台服务器; 国内腾讯公司天津数据中心在2018年服务器总数突破10万台; 国内阿里巴巴将在南通建立云计算数据中心, 计划容纳30万台服务器.数据中心规模越来越大, 造成计算资源的异构化和规模化, 给大规模数据中心的作业调度带来一定的挑战. 云计算数据中心作为商业计算服务平台, 首先, 需要满足各种不同的用户需求. 例如, 有些用户需要快速的服务响应时间, 有些用户需要服务的稳定性和可靠性, 有些更倾向于低廉的计算成本, 与此同时还要保障用户的服务体验^[1]. 再者, 云计算的商业性决定了调度策略需保障服务供应商的利益, 减少能耗及相应开销. 传统的调度方法已不能适应其复杂多变的调度环境, 因此, 研究云计算异构环境下的多目标优化调度策略具有相当重要的意义.

针对异构云环境多目标优化调度问题, 本文定义了执行时间、服务延迟成本、平台运行能耗、成本等多个目标, 其中服务延迟成本用以描述用户对服务质量的满意程度; 设计AHP定权的多目标调度综合评价方法, 并将该方法引入强化学习Q-learning的奖励值计算, 有利于后续作业的经验学习; 利用MultiRECloudSim平台进行仿真实验, 实验结果表明所提出方法优于大部分对比方法, 能够较好地改善作业执行效率并保证用户及服务提供商的利益.

1 相关工作

云数据中心作业调度主要分为3类: 传统作业调度、多目标优化作业调度和基于机器学习的作业调度.

1.1 传统作业调度方法

传统作业调度方法一般优先考虑性能, 被广泛应用的算法有先来先服务调度算法、max-min调度算法、min-min调度算法、公平调度算法以及单目标启发式调度算法等. 这类算法一般不考虑资源需求及利用率, 只为查找满足计算需求的节点来执行作业. 但是, 实际的作业调度问题往往有多个目标, 例如最短执行时间、最佳服务质量、最少计算成本等, 因此这类方法实用性较为欠缺.

1.2 多目标优化作业调度方法

考虑到云环境下的多个优化目标, 并将作业映射至合适的云计算资源, 多目标优化作业调度方法较传统的作业调度方法更具实用性^[2-3]. 近年来, 随着云服务快速普及, 多目标优化作业调度方法受到广泛关注, 并已取得一定成果. Akbari等^[4]设计了基于布谷鸟搜索的多目标作业调度算法, 该算法不但减少了异构系统中的作业执行时间, 而且最大程度保障了作业并行化. 胡成玉等^[5]建立了以利润、碳排放以及QoS为目标的数据中心负载优化调度模型, 并设计出一种非支配排序遗传算法, 保证算法能快速收敛. Zhu等^[6]以作业完成时间和成本作为调度目标, 设计了基于演化算法的多目标调度算法以优化IaaS(infrastructure as a service)平台的工作流调度. 苏命峰等^[7]结合能耗、成本和系统可用性等指标构建了多维QoS云资源调度模型, 并提出结合多重贪心算法的云资源调度算法. 上述方法取得了比传统作业调度方法更好的解, 但同时也存在一些问题. 现有的调度策略研究较少兼顾用户和服务供应商双方的利益, 如何使资源供给与消费双方互利共赢是当前云作业调度需考虑的问题.

1.3 基于机器学习的作业调度方法

基于机器学习的作业调度方法学习数据中心资源消耗、性能变化与负载波动之间的关系, 探索高效执行作业时所需资源. 在实际执行调度算法时, 根据学习结果与实时监控状况调整作业分配方案^[8].Islam等^[9]利用神经网络和线性回归设计了资源预测和供应策略, 实现了云作业资源的按需分配. Chen等^[10]设计了基于动态加权随机森林的负载预测方法, 并根据预测结果进行自适应作业调度. 上述方法通过预测负载波动调节计算资源规模, 为减少处于活跃状态的服务器, 需频繁地进行虚拟机迁移, 这会对云作业调度造成一定程度的影响.

此外, 基于强化学习的作业调度方法也是研究热点. Yi等^[11]利用LSTM网络构建系统状态预测模型, 并使用该模型训练基于深度强化学习的作业分配器, 有效地为数据中心节省近10%的计算能力. Yang等^[12]提出了基于强化学习的资源分配方法, 并通过优化长期奖励以改善工作流调度效率.

本文介绍的方法充分考虑到节能增效、用户体验、执行成本等多个目标之间的平衡, 兼顾用户和服务供应商双方利益, 着眼于云计算资源的异构性及作业多样化, 利用强化算法对云数据中心作业进行智能自主管理.

2 多目标与约束定义

定义1(异构资源约束)  云数据中心由众多异构服务器构成, 这些服务器被虚拟化成虚拟机, 虚拟机$ V_i $有$ d $个维度资源, 可表示为$ V_i = \{V_i^1, V_i^2, \ldots, V_i^d\} $. 同理, 定义作业$ T_j $所需的资源为$ T_j = \{T_j^1, T_j^2, \ldots, T_j^k\} $. 虚拟机与作业之间的放置关系可用调度矩阵$ X = [x_{ij}] $表示, 当$ T_j $作业分配到虚拟机$ V_i $时, $ x_{ij} = 1 $, 否则$ x_{ij} = 0 $. 通过上述对异构资源的分配关系, 可以获得异构资源环境下作业调度的资源约束目标为

$ \sum\limits_{j = 1}^{m}T_j^k\cdot x_{ij}\leqslant V_i^k. $

(1)

式(1)反映了表示作业执行所消耗的全部资源量应小于等于平台的总资源量.

定义2(执行时间)  执行时间是作业调度中最为普遍的优化指标, 作业$ T_j $的执行时间$ t_e(T_j, V_i) $可计算为

$ t_e(T_j, V_i) = \frac{{\rm len}(T_j)}{V_i^{\rm CPU}}. $

(2)

其中: $ {\rm len}(T_j) $为作业$ T_j $的长度; $ V_i^{\rm CPU} $为虚拟机$ V_i $中的CPU执行能力. 假定每个任务只能在一台虚拟机上执行, 云平台的总执行时间$ t_{\rm all} $为

$ t_{\rm all} = {\rm max}\Big\{\sum\limits_{j = 1}^{m_1} t_e(T_j, V_1), \ldots , \sum\limits_{j = 1}^{m_n} t_e(T_j, V_n)\Big\}, $

(3)

其中$ m_i $为全部被虚拟机$ V_i $成功执行的作业数目, $ \sum\limits_{i = 1}^{n}m_i = m $. 对于云平台而言, 总执行时间越少, 用户的满意程度越高.

定义3(服务延迟成本)  对于云计算平台管理者而言, 更关注平台的整体性能, 如资源负载均衡、能耗等. 对于提交作业的用户而言, 更关心的是服务执行效果. 用户访问数据中心, 不仅需要考虑服务价格, 同时也要考虑服务质量. 本文利用服务延迟成本描述用户对服务质量的满意程度. 作业等待响应的时间越长, 延迟成本越大, 服务体验就相对较差. 服务延迟成本可表示为作业等待响应时间的函数. 作业$ T_j $的等待响应时间$ t_{w}(T_j) $可计算为

$ t_{w}(T_j) = t_{\rm est}(T_j)-t_{\rm ar}(T_j)+t_s(t_w). $

(4)

其中: $ t_{\rm est}(T_j) $为作业开始执行的时间; $ t_{\rm ar}(T_j) $为作业到达时间; $ t_s(t_w) $为调度算法$ t_w $执行时长. 作业$ T_j $的服务延迟成本$ {\rm cost}_{d}(T_j) $可计算为

${\rm cost}_{d}(T_j) = \left\{\begin{array}{l} 0, \, {t_{w}(T_j) < \psi t_{\rm rt}};\\ L(t_{w}(T_j)), \, {t_{w}(T_j) \geqslant \psi t_{\rm rt}}.\\ \end{array}\right. $

(5)

$ L(t_{w}(T_j)) = {\rm cost}_{d/u}\cdot(t_{w}(T_j)-\psi\cdot t_{\rm rt}). $

(6)

其中: $ t_{\rm rt} $为用户的可容忍等待时间; $ \psi $为自适应调节因子, 用户可容忍等待时间在不同时间段是不同的; $ {\rm cost}_{d/u} $为单位时间内服务延迟成本. $ {\rm cost}_{d}(T_j) $越小, 表明用户体验越好. 总服务延迟成本$ {\rm cost}_d^{\rm all} $可计算为

$ {\rm cost}_d^{\rm all} = \sum\limits_{j = 1}^{m}{\rm cost}_{d}(T_j). $

(7)

定义4(平台运行能耗)  利用CPU利用率-功率函数^[13]计算数据中心运行能耗$ \rm energy_{all} $. 服务供应商不仅需考虑服务器能耗, 还要考虑制冷、照明等能耗. 因此数据中心能耗利用能源效率指标(power usage effectiveness, PUE)进行估算^[14], 具体计算为

$ {\rm energy}_{\rm all} = t_{\rm all}\cdot \sum\limits_{i = 1}^{p}P_i(U_i). $

(8)

其中: $ p $为数据中心内活跃的服务器数量; $ P_i(\; ) $为第$ i $台服务器的CPU利用率-功率函数; $ U_i $为第$ i $台服务器的CPU利用率, 其计算公式为

$ U_i = \frac{1}{c}\cdot \sum\limits_{k = 1}^{c}{\rm VM}_{k}^{\rm CPU}. $

(9)

其中: $ c $为部署在第$ i $台服务器上的虚拟数量; $ {\rm VM}_{k}^{\rm CPU} $为该虚拟机CPU利用率.

定义5(成本)  总成本$ \rm cost_{all} $包括用户成本$ {\rm cost}_{u} $和服务供应商成本$ {\rm cost}_{p} $. 用户成本主要为作业执行成本, 服务供应商成本主要为能耗成本. 因此总成本的具体计算公式为

$ {\rm cost}_{\rm all} = {\rm cost}_{u}+{\rm cost}_{p} = \\ \sum\limits_{j = 1}^{m}{\rm cost}_v(V_i)\cdot t_e(T_j, V_i)+ {\rm energy_{all}}\cdot \rm cost_{ep}. $

(10)

其中: $ {\rm cost}_v(V_i) $为虚拟机$ V_i $的单位计算成本, $ \rm cost_{ep} $表示单位电力成本.

定义作业调度过程中的多个目标, 其调度目标如下:

$ {\rm min}\{t_{\rm all}, \; {\rm energy}_{\rm all}, \; {\rm cost}_{\rm all}, \; {\rm cost}_d^{\rm all} \}. $

(11)

需要满足的约束条件如下:

$ \sum\limits_{j = 1}^{m}T_j^k\cdot x_{ij}\leqslant V_i^k. $

(12)

3 AHP定权的多目标强化学习作业调度 3.1 马尔可夫决策过程

根据排队模型, 动态到达的作业调度过程可视为马尔可夫决策过程, 因此构建马尔可夫决策过程的四元组$ E = \langle X, A, P, R\rangle $. 作业调度的状态空间为$ X\! = \{{\rm schedule}(T_j), {\rm queue}(V_i), \rm excute\} $, 包括3类状态: 调度状态$ {\rm schedule}(T_j) $、在虚拟机前队列等待$ {\rm queue}(V_i) $和执行状态$ \rm excute $. $ A $为各个作业$ T_j $的动作; $ P(x, x', a) $为作业执行动作$ a $后到达状态$ x' $的概率; $ R $为奖励函数, 具体为

$ \begin{array}{lll} R_1:A\times X = {\rm schedule}(T_j)\to {\rm queue}(V_i), \\ R_2:A\times X = {\rm queue}(V_i)\to \rm excute.\\ \end{array} $

(13)

当作业从调度状态转换为等待状态, 获得奖励$ R_1 $; 当作业变成执行状态时, 则获得奖励$ R_2 $.

可以发现, 状态空间$ X $的规模为作业数量$ m $和虚拟机数量$ n $的乘积. 奖励$ R_2 $需要很长的反馈过程, 且计算较为复杂, 本文研究重点在调度过程, 因此在后续研究中, 奖励$ R $即因调度动作而产生的奖励$ R_1 $. 奖励$ R $是根据虚拟机前的作业等待队列长度确定的, 即根据作业被分配至虚拟机$ V_i $上的数量, 可计算为

$ R_{x\to x'}^{a} = k\cdot {\rm size}({\rm queue}(V_i)). $

(14)

其中: $ R_{x\to x'}^{a} $为执行动作$ a $后, 状态从$ x $转变成$ x' $所获得的奖励; $ k $为常数, 用于调节$ k $的奖励$ R $值大小. 但仅依据虚拟机前作业等待队列长度确定奖励值$ R $, 则忽略了作业调度的多个优化目标, 为此将面向异构资源的多目标调度综合评价引入奖励$ R $的计算策略.

3.2 AHP定权的多目标调度综合评价

首先需构建面向异构资源的多目标调度综合评价体系, 该体系是简化复杂调度问题的关键. 该评价体系分为3层: 最上层为目标层; 中间层为对象层, 包括用户与服务供应商; 最下层为指标层, 包括用户所关注的指标(作业执行时间、成本(作业执行成本)和服务延迟成本)以及服务供应商所关注的指标(成本(平台能耗成本)和平台运行能耗). 该评价体系的层次结构详见图 1.

在建立多目标调度综合评价体系之后, 还需确定评价体系中各指标的权重. 对此, 本文利用层次分析法设置其初始权重, 具体步骤如下:

1) 建立判断矩阵.

假设有$ n $个指标$ I_1, I_2, \ldots, I_n $对上一层要素有影响, 利用T. L. Sataty的9分位标度^[15], 两两比较同层指标, 获得相对于上层要素的判断矩阵$ A = (a_{ij})_{m\times n} $.其中: $ a_{ij} > 0 $, $ a_{ij} = 1/a_{ji} $, $ a_{ii} = 1 $.

利用9分位标度^[15]方法, 将本文所建立的多目标调度综合评价体系结构中的对象层和指标层内的各个指标进行两两比较, 比较结果如表 1所示.

根据表 1得到如下3个判断矩阵:

$ A_1 = \left[\begin{array}{cc} 1& 2\\1/2 &1 \end{array}\right], $

(15)

$ A_{21} = \left[\begin{array}{ccc} 1 &5 &2\\1/5 &1 &1/3\\1/2 &3 &1 \end{array}\right], $

(16)

$ A_{22} = \left[\begin{array}{cc} 1& 1\\1 &1 \end{array}\right]. $

(17)

其中: 矩阵$ A_1 $为对象层的判断矩阵, 矩阵$ A_{21} $、$ A_{22} $分别为指标层中针对用户和服务供应商的判断矩阵.

2) 一致性检验.

判断矩阵客观地反映出不同指标间的相对重要性, 但无法保证每个判断矩阵都是一致的. 例如, 判断指标$ I_1 $比$ I_2 $重要, $ I_2 $比$ I_3 $重要, 那么$ I_3 $比$ I_1 $重要就明显不合理. 本文利用一致性指标$ \rm CI $衡量判断矩阵是否拥有完全一致性, $ \rm CI $具体计算公式为

$ {\rm CI} = \frac{\lambda_{\rm max}-n}{n-1}. $

(18)

其中: $ n $为判断矩阵的阶数; $ \lambda_{\rm max} $为判断矩阵的最大特征值. 若$ {\rm CI} = 0 $, 则表示判断矩阵拥有完全一致性; 反之, 则需计算随机一致性比率$ \rm CR = CI/RI $, $ \rm RI $为平均随机一致性指标, 其取值见表 2. 当$ \rm CR\!<\!0.1 $时, 判断矩阵的一致性可以被接受, 否则判断矩阵需进行调整. 本文判断矩阵$ A_1 $、$ A_{21} $、$ A_{22} $一致性检测如下:

$ A_1 $的$ \lambda_{\rm max} = 2 $, $ {\rm CI} = (\lambda_{\rm max}-n)/(n-1) = (2-2)/(2-1) = 0 $, 所以$ A_1 $是完全一致的.

$ A_{21} $的$ \lambda_{\rm max} = 3.003\, 7 $, $ {\rm CI} = (\lambda_{\rm max}-n)/(n-1) = (3.003\, 7-3)/(3-1) = 0.001\, 85\!\neq\!0 $, 因此还需计算$ \rm CR $, $ \rm CR = CI/RI = 0.001\, 85/0.52 = 0.003\, 6\!<\!0.1 $, 所以$ A_{21} $的一致性可以被接受.

$ A_{22} $的$ \lambda_{\rm max} = 2 $, $ {\rm CI} = (\lambda_{\rm max}-n)/(n-1) = (2-2)/(2-1) = 0 $, 所以$ A_{22} $是完全一致的.

3) 计算相对权重.

计算各指标相对权重, 即求各判断矩阵的特征向量, 也就是计算符合$ A\cdot\, W = \lambda_{\rm max}\cdot\, W $的特征向量, 并将$ W_{\lambda_{\rm max}} $归一化, 即得到其相对权重. 文中判断矩阵$ A_1 $的相对权重为$ (0.67, 0.33) $, $ A_{21} $的相对权重为$ (0.58, 0.11, 0.31) $, $ A_{22} $的相对权重为$ (0.5, 0.5) $.

4) 计算综合权重.

计算各判断矩阵的相对权重之后, 还需计算确定指标层各指标相对于总目标的权重, 计算方法为

$ w_i = \sum\limits_{j = 1}^{m}w_{ij}^{(3)}\cdot w_j^{(2)}. $

(19)

其中: $ w_{ij}^{(3)} $表示指标层第$ i $个指标相对于对象层中第$ j $个指标的相对权重; $ w_j^{(2)} $表示对象层第$ j $个指标相对于总目标的权重. 根据式(19)可得指标层各指标相对于总目标的综合权重为$ (0.39, 0.07, 0.375, 0.165) $. 图 2为综合权重计算过程.

最后, 结合综合权重可得异构资源的多目标调度综合评价值计算公式, 即

$ T_{\rm value} = 0.39\cdot t_{\rm all}+0.07\cdot {\rm cost}_d^{\rm all}+0.375\cdot\rm cost_{all}+\\ \;\quad\qquad 0.165\cdot\rm energy_{all}. $

(20)

需要注意的是, 在实际应用中各指标需进行归一化处理. 将异构资源的多目标调度综合评价值$ T_{\rm value} $引入多目标调度奖励值$ R $的计算策略, 得出奖励值计算公式, 即

$ R_{x\to x'}^{a} = k\cdot {\rm size}({\rm queue}(V_i))\cdot T_{\rm value}. $

(21)

利用式(21)计算出的多目标调度奖励值$ R $能够反映出异构云环境下作业的执行时间、成本、能耗等情况, 对后续待分配作业起到良好的经验学习作用.

3.3 基于强化学习的调度方案

强化学习Q-learning算法的基本思想是根据状态和动作构造一张$ Q $值表保存$ Q $值, 然后从$ Q $值表找出使得作业调度收益最大的动作. 本文Q-learning算法在对下一步状态$ x' $进行探索时采用了$ \varepsilon $贪心策略, 即有$ \varepsilon $的概率随机挑选一个动作, 余下$ 1-\varepsilon $的概率挑选效用值$ Q $最大的动作. $ \varepsilon $一般取$ 0.01\, \sim\, 0.1 $.具体的$ Q $值更新公式如下:

$ Q_{t+1}(x, a) = Q_{t}(x, a)+\alpha\cdot (R_{x\to x'}^a+\\ \qquad \qquad \qquad \gamma\cdot Q_t(x', a')-Q_t(x, a)). $

(22)

其中: $ a $为更新步长, $ a $越大表明越靠后的累计奖励越重要; $ \gamma $为折扣奖赏权重, $ \gamma $值越大表明之前的经验越重要. AHP定权的Q-learning多目标作业调度的具体步骤详见算法1.

算法1  AHP定权的Q-learning多目标作业调度.

输入：第$ w $批次队列$ {\rm List}\, T $, 虚拟机队列$ {\rm List}\, V $, $ Q $值表;

输出：第$ w $批的调度方案$ \rm assingedList $.

1. $ \rm begin $

2. 构建状态空间$ X $;

3. 选择第一个作业$ T_{\rm 1} $作为开始

4. $ \rm for $ $ T_j $ $ \rm in $ $ {\rm List}T $ $ \rm do $

5.    if(random $ \!<\!1-\varepsilon $)then

6.        在$ Q $值表中选择最大$ Q $值所对应的动作$ a $;

7.    else

8.        为作业$ T_j $随机选择一个动作$ a $;

9.     end if

10.    执行动作$ a $, 并获取下阶段状态$ x' $和奖励$ R $;

11.    根据下阶段状态, 选择最大$ Q $值所对应的动作$ a $;

12.    根据式(22)更新当前状态-动作的$ Q $值;

13.     将作业与虚拟机的映射关系放入assignedList;

14.     令下一个状态$ x' $变为$ x $;

15. end for

16. 输出assignedList;

17. end

算法1在初始化$ Q $值表过程中, 时间复杂度和状态数量、动作空间密切相关, 该步骤的时间复杂度为$ O(n\cdot m) $; 在利用$ \varepsilon $贪心策略进行动作选择时, 时间复杂度与动作空间大小有关, 单次复杂度为$ O(n) $; 最后在更新$ Q $值表时, 时间复杂度为$ O(n\cdot {\rm log}n) $.

3.4 AHP定权的多目标强化学习作业调度框架

图 3是AHP定权的多目标强化学习作业调度总体框架图, 反映出多目标调度的总体运行状况及控制机制, 其主要由4个部分组成: 1) 用户层; 2) 计算资源层; 3) 监控层; 4) 决策层.

1) 用户层: 用户在不同时刻提交所需处理的作业, 然后这些作业进入作业队列等待处理. 这些作业种类不同, 而且对各类资源的需求也各异.

2) 计算资源层: 将异构服务器的实体资源抽象成虚拟资源, 便于对计算资源进行高效管理, 最大程度地利用数据中心内的可用计算资源.

3) 监控层: 作业的执行使得虚拟机以及物理服务器的资源利用率、耗电功率等发生变化. 因此不仅需要采集与作业执行相关的参数, 还需要采集计算资源的变化参数. 最后, 这部分采集的监控数据将作为反馈信息传送至决策层, 以供决策之需.

4) 决策层: 计算资源层和用户层的信息被实时更新至决策层. 而决策层利用AHP定权的强化学习算法对异构环境进行实时学习, 并确定当前状态下最优作业调度方案. 最后将该方案交给作业调度器执行. 随着作业部署到虚拟机, 计算资源层和用户层的变化信息被监控层传递给决策层. 这4个部分通力合作, 周而复始, 最终实现作业和异构资源的合理分配.

4 实验设计与结果分析 4.1 实验平台介绍

MultiRECloudSim^[16]是基于CloudSim3.0.3拓展开发的云计算仿真平台, 在原有的CloudSim平台增加了作业的多种资源需求模拟、预取资源管理模块以及多资源运行的能耗计算等功能.

4.2 异构资源平台设置

本文在MultiRECloudSim^[16]构建了6款异构服务器, 具体型号及功率映射函数如表 3所示. 其中: 功率映射函数根据SPEC官网提供的数据计算得到, $ x $为CPU利用率, $ y $为耗电功率^[17].

为便于计算, 在每台服务器上部署一台虚拟机(VM), 虚拟机的计算能力在600 ~ 1 000 MIPS之间, 依据阿里云的收费标准, 计算出1核CPU计费为0.067 5 ￥/ h, 1 GB内存计费为0.037 5 ￥/ h, 即虚拟机$ V_i $单位时间内的计费$ {\rm cost}_v(V_i) $为

$ {\rm cost}_v(V_i) = 0.067\, 5n+0.037\, 5m. $

(23)

其中: $ n $为$ V_i $的CPU核数; $ m $为内存容量. 本文模拟的作业不考虑硬盘需求, 因此设定虚拟机计费标准时不考虑硬盘.

4.3 实验作业流

本文共设置5个作业流, 作业分不同批次到达, 各批次作业的到达时间按泊松分布设定. 各作业流的到达时间和数量如图 4所示, 具体参数设置如表 4所示.

4.4 仿真实验

在仿真调度实验中, 设置如下基准作业调度算法:

1) 先来先服务调度算法(FCFS): 根据作业到达数据中心的先后顺序, 依次分配至空闲虚拟机.

2) 基于蚁群算法的调度算法(ACO): 以执行时间和平台能耗作为优化目标进行作业调度.

3) 基于遗传算法的主资源负载均衡调度算法(LVS): 通过对各指标加权设计适应度函数, 利用遗传操作挑选染色体, 当满足阈值时输出调度方案.

4) 贪心调度算法(GA): 将每个作业分配至当前最优虚拟机.

FCFS和GA属于传统作业调度算法, ACO和LVS属于多目标作业调度算法. 这些算法与本文算法(下文中用AHP-MQ表示)在执行时间、服务延迟成本、能耗、成本几个方面进行对比.

图 5为作业总执行时间. 由图 5可见, GA和AHP-MQ在作业总执行时间上表现较好. AHP-MQ比FCFS、ACO、LVS分别平均减少42.13

图 6为服务延迟成本. 由图 6可见, FCFS和LVS的服务延迟成本较大, 主要原因是FCFS按到达顺序分配作业, 并未考虑优化策略, 而LVS在调度时关注负载均衡, 不让过多作业集中到性能高的虚拟机上, 因此有较多作业处于等待状态. AHP-MQ算法在服务延迟成本这个调度目标上仅次于GA.

图 7为平台运行能耗. 由图 7可见, 在平台运行能耗方面, AHP-MQ算法和GA表现相当, 虽然AHP-MQ和GA在高性能虚拟机上部署较多作业导致单位时间内功率偏高, 但是AHP-MQ和GA的总执行时间远低于FCFS、ACO和LVS, 所以总体而言能耗更低.

图 8为总成本. 由图 8可见, GA和AHP-MQ的总成本比较低, 这与能耗较低的原因相似, 均为这些调度算法总执行时间少, 此外AHP-MQ在计算多目标调度综合评价值时, 成本的权重占较大比例.

在仿真平台内的实验结果表明, 所提出的AHP定权多目标强化学习作业调度算法在作业总执行时间、平台运行能耗方面表现较好, 但在服务延迟成本方面比GA表现劣势. 此外, AHP-MQ在总成本控制方面也表现得较好. 所提出的AHP-MQ算法能够发挥强化学习的能力, 较好地优化调度方案.

5 结论

随着云计算的快速发展, 越来越多的作业提交至云数据中心. 在海量的异构资源的云数据中心进行作业调度是一个NP难问题. 本文针对云环境下多目标优化调度问题, 定义执行时间、服务延迟成本、平台运行能耗、成本等调度目标, 其中服务延迟成本描述用户对服务质量的满意程度; 然后设计AHP定权的多目标强化学习作业调度算法并将面向异构资源的多目标调度综合评价方法引入Q-learning奖励值的计算, 有利于后续作业的学习; 最后利用MultiRECloudSim仿真平台进行仿真实验, 结果表明所提出方法优于大部分对比方法, 能够较好地保障用户及服务提供商的利益. 在今后的研究中, 将考虑负载均衡, 优化奖励值的计算, 使该算法更加全面合理.