双层虚拟化云架构下任务调度能耗优化算法

张 驰，王宇新，冯 振，郭 禾

1.大连理工大学 软件学院，辽宁 大连116024

2.大连理工大学 计算机科学与技术学院，辽宁 大连116024

3.浪潮电子信息产业股份有限公司 高效能服务器和存储技术国家重点实验室，济南250101

近年来，无论是在科学研究还是商业领域，为了节约时间和经济成本，越来越多的工作流任务被托管到云平台上运行[1]。随着云计算基础设施需求不断扩大，云数据中心的规模呈爆炸式增长，能耗过高已经成为制约云计算产业健康发展的关键性问题。在过去的几十年中，云数据中心中计算资源的能耗已经占到其总能耗的45%[2]。为此，研究人员提出了多种节能策略如动态电压和频率缩放（DVFS）技术，工作流任务能耗优化调度策略，以及动态虚拟机合并策略。

虚拟化技术是云计算服务的核心和基础，是提高云数据中心服务器资源利用率的关键[3]。虚拟机技术作为传统的虚拟化技术会消耗大量的启动时间和服务器资源。相对于虚拟机的笨重，容器作为一种轻量化的虚拟化技术应用越来越广泛[4]。但是，由于容器共享服务器操作系统造成的隔离性不够也会导致一些安全隐患[5]。两者是不同层次的虚拟化技术，根据其各自的特性，将它们融合使用，如在虚拟机上部署容器形成双层虚拟化架构，可以使它们优势互补，更好地发挥作用[5]。一方面既能提供虚拟机带来的隔离性和安全性，又可以提供容器所拥有的轻便性和灵活性。另一方面，通过在虚拟机上部署多个容器可以使系统中的虚拟机的数量大大减少，相应地减少部署虚拟机的资源浪费和等待时间。大型云服务提供商，如Amazon Web Services、Microsoft Azure 和Google Container Engine，都已经在虚拟机实例上部署了容器；VMware等虚拟化公司也提交了相关的专利申请[6]。

在传统的并行工作流任务能耗调度算法中，任务独占一个计算资源，调度时考虑的任务执行代价就是它占用计算资源的时长。在双层虚拟化架构的云数据中心中，任务由容器执行，任务的执行代价不仅体现在容器的运行时长，也包括其占用计算资源的大小。多个容器的部署也会受到虚拟机有限资源的限制，因此传统算法并不能适用于双层虚拟化架构。为此，本文提出了一种新的能耗优化调度算法。在满足用户给定工作流截止时间约束的条件下，给出合理的调度方案以降低云数据中心的能耗。算法通过两个阶段完成调度，首先，在满足用户截止时间约束的同时，给出使用最少的虚拟机和服务器完成工作流的调度方案；然后，最小化上一阶段调度方案中虚拟机和服务器的工作时间。

1 相关工作

关于云数据中心的工作流任务能耗优化调度问题，国内外学者进行了大量的研究。在不使用虚拟化技术的场景下，Thanavanich[7]提出用处理器上分配任务的效率比作为性能度量的EHEFT和ECPOP算法，即在经典的DAG启发式列表调度算法HEFT和CPOP[8]的一次调度基础上，关闭调度方案中效率比低的处理器，将其上的任务重新分配到其余处理器上。王国豪等[9]提出了一种工作流能效调度算法——CWEES，该算法通过重新分配轻载处理器上的任务至其他处理器，降低处理器的使用数量；然后使用DVFS 技术降低仍有空闲时槽的处理器电压和时钟频率，扩展任务执行时间，最终在不违背任务顺序和截止时间约束前提下降低工作流执行总能耗。但是这些算法将任务直接运行在服务器的处理器上，无法适用于目前云数据中心的虚拟环境。同时，算法中的处理器不能并行多个任务，也未考虑任务需求的计算资源量。

在虚拟机云环境下，谢毅等[10]提出了基于负载的能耗计算方法及相应的工作流调度算法HMEC，算法在进行任务优先级计算和任务选择时同时考虑了任务间的优先约束关系和数据传输；在进行虚拟机选择时，采用了能耗消耗最小的任务分配规则。张奕等[11]提出了能源和时限可感知的非迁移调度算法EDA-NMS，通过利用任务时限的松弛度，延迟宽松时限任务的开始时间，减少使用的服务器数量，避免虚拟机迁移，达到降低能耗的目的。Zhu等[12]研究了具有用户指定截止时间的独立任务的能耗优化调度问题。提出了一种依据能源效率的任务排序方法和虚拟机搜索策略。上述研究将虚拟机作为计算资源的最小分配单位来接收和处理工作流任务，但是在虚拟机模型中没有考虑任务的并行处理能力，这种粗粒度的模型有很大的局限性。

在容器云环境下，Zhang 等[13]为了降低能耗以及容器镜像和工作负载的网络传输的成本，提出了一种基于整数线性规划的解决方案。李磊[14]使用任务排队模型对容器云建模，构建基于任务QoS约束的能耗最小化的目标函数，再利用李雅普诺夫优化算法求解，减少容器运行数量，获得高资源利用率。Canosa等[15]通过定义容器请求能力模型和完全能力模型来约束不同模型中任务执行的速度上限，并给出分配任务到容器的调度策略集。但是，这些研究中容器直接放置在物理机上，同时也没有考虑到任务之间的优先约束关系。

对于双层虚拟化架构的云数据中心能耗问题，目前还没有关于工作流任务调度的研究成果，已有工作主要集中在资源调度上。例如，Hussein等[16]提出了一个双层放置架构，使用基于最优拟合的蚁群优化算法（ACO-BF）完成容器到虚拟机以及虚拟机到服务器的放置，算法的适应度函数同时评估虚拟机和服务器剩余资源量。本课题组之前曾研究[17]针对虚拟机云环境下有截止时间约束的并行工作流任务的能耗优化调度，本文在此基础上进行了扩展和改进，提出了能够适应双层虚拟化架构云数据中心的工作流任务调度算法。

2 系统模型和相关定义

2.1 云数据中心模型

本文面向的云数据中心基于在虚拟机上部署容器的双层虚拟化云架构，如图1所示。

图1 双层虚拟化云架构

容器是工作流任务的处理单元，部署在虚拟机上，虚拟机部署在服务器上。具体的约束关系如下：

（1）任务和容器之间是一一对应的关系，即任务只能放在一个容器上执行，而且在执行过程中不能被打断。容器的大小等于任务要求的计算能力。任务执行完成后，容器销毁，释放占用的计算资源，容器的生命周期等于任务需要的计算时长。

（2）只要虚拟机上有足够的计算资源，多个容器可以并行在一个虚拟机上。

（3）一个工作流的容器可以根据需要放置在一个或者多个虚拟机上，但是为了工作流之间的隔离性和安全性，虚拟机上只能放置同一个工作流的容器。工作流的所有任务执行完成后，运行该工作流的所有虚拟机会被销毁，释放计算资源。

（4）虚拟机的创建以最大化利用服务器资源为原则，只有当已使用服务器上没有足够的计算能力时才会启动新的服务器。

（5）由于要考虑使用的服务器和虚拟机的数量，为了简化问题模型，假设所有的服务器和虚拟机同构，也就是所有的虚拟机的计算能力(vc)都是相同的，每个服务器上能放置的最大虚拟机数量(vn)也是相同的。那么，服务器的计算能力hc=vn×vc。

2.2 工作流模型

通常，云计算中应用的工作流包含很多具有依赖关系的并行任务，可以用有向无环图（Directed Acyclic Graph，DAG）来表示其中，V是DAG中所有节点的集合，工作流中有n个任务，每个任务分别与DAG 中的一个节点对应。节点的权值是任务的计算量，与传统工作流DAG的最大区别是，表示为任务要求的计算能力乘以计算时长。这里假设是由用户提前给出的，并且在任务的执行过程中不会改变。E是DAG 中所有边的集合，如果两节点之间存在一条边，则说明任务τi是τj的前驱任务，相应地，τj是τi的后继任务。一个任务只有在它所有的前驱任务都完成之后才能开始执行。考虑到可以忽略同部署在一个服务器的容器之间的通信代价，模型中没有给出边的权值，边只代表任务之间的优先约束。工作流有给定的释放时间TR和相对截止时间TD，绝对截止时间可以表示为TR+TD。

规定一个DAG中只能有一个没有前驱的节点作为入口节点和一个没有后继的节点作为出口节点，它们分别对应工作流中的入口任务(τentry)和出口任务(τexit)。因此，当工作流中存在多个没有前驱的任务时，需要为这些任务增加一个计算量为0的虚拟任务作为前驱，同样，当存在多个没有后继的任务时，也会为这些任务增加一个计算量为0的虚拟任务作为后继。

图2 给出了一个用DAG 表示的工作流实例，图中给出了每个任务的计算量，τ0和τ11是虚拟的入口任务和出口任务，TR=0，TD=25。

图2 工作流DAG示例

2.3 能耗模型

Feller等[18]根据服务器功率和资源利用率之间的近似线性关系给出了服务器功率的计算公式：

其中，PRidle和PRmax分别是服务器在空闲和满载时的功率，u是服务器资源利用率。服务器资源利用率(u)根据服务器上使用的虚拟机数量(vnused)来计算：

最终，将执行工作流所使用的所有物理机的能耗加起来就是云数据中心完成这个工作流的总能耗。

2.4 相关定义

定义1 任务拓扑层级表示任务在DAG 中的层级，具体定义如下：

定义2 路径长度和关键路径，路径长度定义为路径上所有任务的计算时长的总和。关键路径是指从τentry到τexit有最长的路径长度的路径。一个DAG中可能存在多条关键路径，但是它们有相同的路径长度，称为关键路径长度(TC)。对于有严格截止时间的工作流，给定的相对截止时间必须不小于关键路径长度，即TD≥TC。根据定义，对于图1的DAG，TC=22。

定义3 任务最早开始时间和最迟完成时间，主要取决于工作流的TR和TD，以及DAG的结构，它们的计算公式如下：

定义4 任务松弛时间，指出在工作流的实际完成时间不超过截止时间的条件下，τi可以最长推迟的时间。它可以用来代表一个任务的紧急程度，越小意味着任务更加紧迫。如果，那么这个任务必须在开始执行，否则将导致违反截止时间。的计算公式如下：

定义5 任务开始时间和完成时间是指在调度算法给出的调度方案中τi实际的开始时间和完成时间，。而且根据和的定义，必然存在两个约束条件，

定义6 调度中任务最早开始时间和最迟完成时间是指在任务调度过程中，τi可以最早开始执行的时间和最迟完成的时间。调度开始时，和的值分别被初始化为和，在调度过程中，随着τi的前驱和后继任务被调度完成，和会不断变化。

定义7 虚拟机可用范围，如果在某一个时间段，虚拟机上的资源没有完全被容器占用，那么虚拟机在这个时间段内的空闲资源被称为是虚拟机可用范围。每个虚拟机的是一个集合，集合中的每个元素(ark)有三个属性，分别是可用时间段开始时间(stk)和结束时间(ftk)，以及可用资源量(vrk)。每当有一个容器被放置在VMj上，将更新。

定义8weightu和weightd，参照Topcuoglu等在文献[19]中提出的ranku和rankd，提出了weightu和weightd。weightu是从当前任务到τexit的最长路径上所有任务的计算量（包含当前任务），计算时从τexit递归向上到τentry；weightd是从τentry到当前任务的最长路径上所有任务的计算量（不包含当前任务），计算时从τentry递归向下到τexit。其中计算量等于要求的计算能力乘以计算时长，具体计算公式如下：

3 算法设计

本文的目标是给出在截止时间内完成且能耗最低的工作流调度方案，调度算法分两个阶段实现，分别是时间利用率最大化调度（TUMS）和运行时间压缩（RTC）。TUMS 阶段通过充分使用给定的时间范围来尽可能减少完成工作流所使用的虚拟机和服务器数量，给出初步的调度方案。RTC 阶段找出调度方案中可以提前运行的容器，在满足任务间优先约束的同时，通过压缩虚拟机上前面的空闲时间来提前它们的开始时间，以缩短虚拟机和服务器的工作时间，最终达到降低能耗的目标。

3.1 时间利用率最大化调度阶段

减少完成工作流所需的虚拟机和服务器数量的途径是延长它们的工作时间，在有严格截止时间约束的条件下，只能最大化时间利用率。TUMS是启发式列表调度策略，调度的第一步是确定每个任务的优先级。对于两个任务τi和τj，确定优先级的四条规则具体描述如下：

（3）如果相关任务数量也相同，根据任务要求的计算能力；如果，则τi有更高的优先级。

（4）对于前三个规则不能区分优先级的任务，根据任务的拓扑层级；如果，则τi有更高的优先级。

如果存在上述规则不能区分优先级的任务，则随机分配。最终，将所有任务按优先级降序排列存储在一个有序列表。

所有的任务根据其weightu和weightd的大小关系被分为前置任务和后置任务两类。如果，说明当前任务后面有比前面更多的计算量，为了留下更多的运行空间给其后继任务的容器，li应该尽早开始运行，属于前置任务；反之，如果＜，则li应该尽量推迟，属于后置任务。

TUMS从L中依次取出任务li，找到合适的虚拟机来部署它的容器，并确定其ST(li)。先创建个虚拟机，并依次编号。对于li，它的开始时间可以在区间中选择。使用li的开始时间范围以及它要求的计算能力和计算时长，去匹配每个虚拟机的可用范围，找到能够容纳li容器的所有虚拟机。如果已有的虚拟机中没有可用的，则要新创建一个。同时要根据li的类别确定它在这些虚拟机上的最优开始时间。最后，根据li的类别，前置任务在所有虚拟机中选择最优开始时间最小的，后置任务选择最优开始时间最大的，虚拟机放置它对应容器，同时，最终的ST(li)等于它在该虚拟机上的最优开始时间。

一个任务调度完成后，TUMS更新该任务所有前驱任务的SLFT和后继任务的SEST，同时更新接收容器的虚拟机的AR。重复执行上述步骤，直到工作流中的所有的任务都调度完成。TUMS 的时间复杂度为n为工作流中任务数量，m为虚拟机数量，为任务的平均计算时长。

3.2 运行时间压缩阶段

TUMS给出调度方案后，进入RTC阶段。RTC的任务是找到每个虚拟机上可以提前运行的容器，压缩虚拟机的空闲时间以减少虚拟机和服务器的工作时间。可以提前运行是指在容器的开始时间之前，虚拟机上有足够的可用范围，并且容器提前之后不会违背任务之间的优先关系。这个阶段通过四个步骤实现：

步骤1 建立一个有序列表L′，将所有的任务按照它们在TUMS 中的优先级递增的顺序存储在L′中，也就是说，L′是L的反向列表。

步骤2 找到L′中的第一个开始时间不等于最早开始时间的任务，也就是。

步骤3 记录的容器所在的虚拟机为VMj，如果中存在一个元素k，满足且vrk≥，而且不是VMj上最早开始运行的容器，那么更新，。

步骤4 更新所有后继任务的SEST，以及AR(VMj)。

重复步骤2 到4，直到检查完L′中的所有任务。在步骤3中，不考虑虚拟机上最早运行的容器是因为提前它的开始时间只会拉长它与后续容器之前的空闲时间，而不会缩短虚拟机的工作时间。RTC 的时间复杂度为，n为工作流中任务数量。

3.3 算例说明

本节利用图2 的DAG，说明TUMS-RTC 算法的过程。在TUMS 阶段，通过计算所有任务的优先级，有序列表L={τ0,τ11,τ10,τ8,τ2,τ7,τ1,τ6,τ4,τ5,τ9,τ3}，除了τ9、τ10和τ11是后置任务之外，其余任务都是前置任务。TUMS阶段的调度结果如图3（a）所示。τ0和τ11是虚拟的入口任务和出口任务，权值为0，在图中用虚线表示。接着，RTC 阶段中找到τ10对应的容器C10可以提前运行，将由19提前到16，这样VM0的工作时间由25缩短到了24。图3（b）给出了经过RTC阶段后TUMSRTC算法的最终调度结果。

图3 算法调度结果

4 实验与结果分析

4.1 实验配置与性能指标

如前文所述，以往的工作流能耗优化调度算法无法直接应用于双层虚拟化云架构。为了评估TUMS-RTC算法的性能，使用HEFT和EHEFT算法的调度思想实现了能够适用于双层虚拟化云架构的HEFT*算法和EHEFT*算法，将它们作为对比的基准算法。在EHEFT*算法中，由于虚拟机在任务执行完之后就会销毁，无法使用EHEFT 算法中的效率比作为评价指标，这里选择关闭工作时间最短的虚拟机。另外，由于在双层虚拟化云架构下目前还没有公开的真实工作流数据，对比实验中使用大量参数可控的随机DAG作为测试工作流。

本文以能耗优化为工作流任务调度的目标，因此设计了以下三个性能指标量化算法间的性能对比：

（1）资源利用率，表示执行工作流使用的所有虚拟机的总使用资源与总占有资源的比例，占有资源为虚拟机计算能力乘以虚拟机工作时间。资源利用率的计算公式如下：

wt(VMj)为虚拟机VMj的工作时间，也就是虚拟机上第一个容器开始的时间到最后一个容器结束的时间。

（2）虚拟机数量减少率，表示使用的虚拟机数量在虚拟机上限数量上的减少率。

（3）能耗节省率，表示完成工作流的能耗在上限能耗上的减少率。

由于不同DAG 之间的差异，后两个指标使用相对于上限的减少率比直接使用虚拟机数量和能耗的效果更好。为了给出基准值，提出层次顺序调度策略，把DAG 的节点按层次顺序排序，调度时将其放在能使它最早完成的虚拟机上。将层次顺序调度中使用的虚拟机数量作为虚拟机基准数量，完成工作流的能耗作为基准能耗。

4.2 DAG随机生成程序

为了得到大量有可控特征的随机工作流DAG，设计了DAG 随机生成程序，通过设置多个输入参数来控制生成的DAG的特征。

（1）节点（任务）数量，n。

（2）宽度，fat。控制DAG 的形状，每层节点的个数最大值为因此fat的最大值为在n确定的情况下，fat越大，工作流的并行度越高，DAG层数越少。

（3）匀称度，regularity。控制各层间节点数的差异情况，最大值为1。每层节点的个数最小值为regularity，因此regularity越大表示每层节点数越相似，DAG更匀称。

（4）边密度，density。控制DAG 相邻两层的节点之间连接的紧密程度，density越大，它们之间的边越多。最大值为1，说明一个节点与它下一层的每个节点之间都有边。

参数的值从以下相应的集合中选择：

上述参数的组合可以生成大量不同的DAG 模型，对每种模型随机生成100个具体的DAG 作为实验测试工作流。另外，由于在云数据中心中资源的数量可以看作是无限的，这种情况下，HEFT*和EHEFT*算法都一定会按照DAG 的关键路径长度完成工作流。因此，为了对比的公平性，实验中将工作流的截止时间设置为关键路径长度，即TD=TC。

4.3 实验结果

任务要求的计算能力wc和计算时长wt对不同调度算法的性能对比没有影响。由于任务不能拆分，其对应的容器必须能够放置到一个虚拟机上，因此wc必须小于等于虚拟机的计算能力vc。实验中，vc取值为6，wc取值为区间[1，6]内的随机整数；wt取值为[1，20]内的随机整数。针对工作流DAG 的四种参数，分别进行了四组对比试验，详细实验结果分析如下。

第一组实验观察工作流中任务数量n对算法性能的影响，fat、regularity和density的值分别设置为5、0.6和0.6，实验结果如图4 所示。图4（a）是资源利用率的情况。随着n的增加，HEFT*算法的资源利用率持续降低，由将近75%降低到不到55%；TUMS-RTC 算法的资源利用率稳定维持在75%到85%之间，且始终高于EHEFT*算法。图4（b）是虚拟机数量减少率的情况。三个算法的虚拟机数量减少率随着工作流规模的增大没有明显的变化趋势，TUMS-RTC 算法与HEFT*和EHEFT*算法的平均差值为38.8%和16.9%。图4（c）是能耗节省率的情况。随着n的增加，HEFT*算法的能耗节省率持续下降，HEFT*算法的能耗节省率维持在15%左右，TUMS-RTC 算法的能耗节省率持续增加。当n=500 时，TUMS-RTC算法的能耗节省率达到38.75%，是HEFT*算法的近6 倍。原因分析如下，HEFT*算法在调度时将容器放在它能最早完成的虚拟机上，当n增加时，DAG中同层次的任务数量会增加，因此它会使用过多的虚拟机，资源利用率也会下降，同时，由于作为基准的层次顺序调度同样会将容器放在它能最早完成的虚拟机上，这样HEFT*算法的虚拟机数量减少率不会增加，这样能耗节省率就会下降；EHEFT*算法在第二次调度时会对虚拟机数量有一定的缩减，因此能够保持比较高的资源利用率，虚拟机数量减少率和能耗节省率；TUMS-RTC 算法在调度任务时会尽量为其后续的任务留出空间，充分利用已有的虚拟机，因此当n增加时，依旧能够使用较少的虚拟机，保持很高的资源利用率和虚拟机数量减少率，这样相较于基准算法，TUMS-RTC 算法的能耗节省率会上升。根据第一组实验的结果，TUMS-RTC 算法相较于层次顺序调度算法最高减少了将近45%的虚拟机使用量和40%的能耗，资源利用率维持在80%左右，在调度任何规模的工作流时的性能都明显优于两个对比算法，而且随着任务数量的增加，算法的性能不受影响。

图4 任务数量对算法性能的影响

第二组实验观察工作流的宽度fat对算法性能的影响，n、regularity和density的值分别设置为100、0.6和0.6，fat的最大值为，即10，实验结果如图5 所示。图5（a）是资源利用率的情况。三个算法的资源利用率都随着fat的增大而上升，TUMS-RTC与HEFT*和EHEFT*算法的平均差值分别接近15%和3%。虚拟机上的空闲时间是由于虚拟机上顺序执行的容器之间的时间间隔造成的，当n不变时，fat越大，处于同一层级的节点越多，调度时会使用更多的虚拟机，每个虚拟机上顺序执行的容器会变少，导致虚拟机的空闲时间变少，因此资源利用率就会上升。图5（b）和图5（c）分别是虚拟机数量减少率和能耗节省率的情况。三个算法的虚拟机数量减少率和能耗节省率都随fat增大而增加，因为工作流并行的变高之后，在层次顺序调度中，同一层次的所有任务依次调度，为了保证它们的容器都能在最早开始时间开始执行，就会用到过多的虚拟机。另外，当fat由1增大时TUMS-RTC算法的虚拟机数量减少率和能耗节省率都明显提升，然后分别稳定在43%和30%左右。因为当fat为1 时，工作流中的任务趋近于顺序执行，调度算法的效果有限，当fat增加时，TUMSRTC算法由于同时考虑了任务的计算能力和计算时长，可以达到很好的性能。根据第二组实验的结果，TUMSRTC 算法在调度任何宽度的工作流时的性能都明显优于两个对比算法，而且当fat很大，也就是工作流中任务并行度很高时，算法依然有很好的性能。

图5 工作流宽度对算法性能的影响

第三组实验观察工作流的匀称度regularity对算法性能的影响，n、fat和density的值分别设置为100、5和0.6，实验结果如图6 所示。图6（a）是资源利用率的情况。三个算法的资源利用率都随着regularity的增大而上升。因为随着regularity的增大，工作流各层的任务数量相差更小，调度时容器在虚拟机上的分布也会更加均匀，所以资源利用率会上升。图6（b）和图6（c）分别是虚拟机数量减少率和能耗节省率的情况。三个算法的虚拟机数量减少率和能耗节省率随regularity的变化没有明显变化趋势。因为工作流中每个层次的任务数量越平均时，工作流中从入口任务到出口任务的各条路径长度也就越平均，越接近于关键路径长度，在截止时间等于关键路径的情况下，算法很难将同一条路径上的任务对应的容器集中放置在一个虚拟机上，因此虽然资源利用率增加，但是使用了较多虚拟机导致降低的能耗有限。尽管如此，TUMS-RTC 算法相较于HEFT*和EHEFT*算法，在虚拟机数量减少率上的优势分别有40%和16.5%，在资源利用率上分别提升了将近20%和9%。

图6 工作流匀称度对算法性能的影响

第四组实验观察工作流的边密度density对算法性能的影响。n、fat和regularity的值分别设置为100、5和0.6，实验结果如图7所示。三个算法的性能基本不受density变化的影响。因为如前文模型定义中所述，本文的工作流中，不计任务之间数据传输等通信开销，因此DAG中的边只代表任务之间的优先关系，没有权值，因此对调度几乎没有影响。在资源利用率、虚拟机数量减少率和能耗节省率上，TUMS-RTC算法与HEFT*算法的差值平均值分别接近17%、37%和20%；与EHEFT*的差值平均值分别接近5%、14%和9%。

图7 工作流边密度对算法性能的影响

在实验中，三种算法的资源利用率都很高，因为资源利用率的计算以虚拟机为单位，虚拟机在它上面所有的容器销毁之后也会被关闭。服务器上的空余资源可以被其余用户的虚拟机使用，这也是虚拟化技术的优势，因此不以服务器为单位计算资源利用率。根据上述实验结果分析，TUMS-RTC算法的性能在各项对比指标上都明显优于HEFT*算法和EHEFT*算法。通过统计所有工作流模型的调度结果数据，TUMS-RTC算法有80%左右的资源利用率，相较于层次顺序调度有40%左右的虚拟机数量减少率和30%左右的能耗节省率，达到了优化能耗的调度目标。另外，在工作流中任务数量和并行度增加时，该算法依旧可以保持很好的性能，说明它能够很好地应用于云数据中心中大型高并行度工作流的任务调度。

4.4 算法分析

云数据中心计算设备的能耗主要由启动的服务器数量和它们的工作时间两个因素决定，TUMS-RTC算法在两个阶段中分别针对两个因素给出优化策略，根据实验结果可以看出取得了预期的效果。算法在初始调度之后增加RTC阶段会在一定程度上增加实现成本，但这部分增加的成本是可接受的。首先，RTC阶段对初始调度结果的调整需要完整的虚拟机的可用范围数据，会使用额外的存储空间，但算法的整体空间复杂度依旧是，而且对当前计算机的内存容量不会构成瓶颈。另外，TUMS阶段的时间复杂度与任务的平均计算时长相关，当任务的计算时间过长时会对算法的性能有一定的影响，但相较于任务计算的时间，调度时长可基本忽略不计。

5 结语

云数据中心中，在虚拟机上部署容器的成为一种趋势，为了解决该架构下云数据中心的能耗问题，本文提出了一种针对有截止时间约束的工作流的能效优化调度算法TUMS-RTC。算法通过时间利用率最大化调度和运行时间压缩两个阶段，在保证截止时间约束的条件下，提高了资源利用率，最小化了完成工作流所需的虚拟机和服务器数量，从而达到了降低云数据中心能耗的目标。使用大规模随机工作流进行对比实验，结果证明算法对云数据中心中大型工作流的能耗优化调度是有效的。在下一步的研究中，将考虑工作流任务间的通信开销和云数据中心服务器和虚拟机的异构，使问题模型更加贴近真实场景，并设法使用真实的云数据中心数据和环境进行实验。