基于Cloud Sim云平台的任务调度与能耗分析研究∗

罗肖辉 徐美霞

（1.广州商学院网络中心 广州 511363）（2.广州商学院信息技术与工程学院 广州 511363）

1 引言

作为新兴的计算模式，云计算一直是目前最为热点的研究领域，它被视为以科学研究为主的网格计算的商业化实现［1］。目前，对于云计算的定义业界仍未达成共识，具有代表性的一种观点是：可以提供 IaaS［2］、SaaS［3］和 PaaS［4］等类型服务的资源池，资源池中的资源可以根据负载变化动态进行配置，同时，资源的使用方式是采取即付即用方式。该定义强调了云计算环境的超大规模、虚拟化、可扩展性、通用性及按需服务等特点。目前，各大厂商都相继推出了云平台，如谷歌的App Engine［5］、亚马逊的 Amazon EC2［6］、IBM 的蓝云［7］以及微软 件的Azure OS［8］等。基于模拟的方法允许用户反复测试用户的服务，而不需要大量的资金耗费，并能够在部署之前调节性能瓶颈。而作为新兴的互联网计算模式，目前的云仿真工具并不多，比较典型的有CloudSim［9］、SimCloud［10］及 云计 算平 台［11］三 种。CloudSim云平台［12］是墨尔本大学开发的开源仿真工具包，旨在量化针对不同应用类型和不同服务模型的调度性能。

SimCloud是面向企业级的云平台，它可以整合工程数值仿真软件等资源，并配置动态的资源调度策略，为企业用户提供统一、便捷、强大的云计算服务［13］。“云计算平台”是李伯虎院士等提出的一种新型网络化仿真平台［14］。该平台基于云计算理念，可以应用于工程与非工程领域，实现线上资源的多用户按需协同互操作与调度。“云仿真平台”旨在改善仿真网格对多用户在多粒度资源按需共享、协同、容错迁移等方面的能力，进而建立新的建模仿真模式“云仿真”。

鉴于CloudSim云平台的开源性和使用的广泛性，且提供虚拟引擎，有助于在一个数据中心节点上创建和管理多个独立和协同的虚拟机服务，本文在CloudSim云平台环境中研究了云计算的任务调度算法和基于节能的虚拟机部署算法，提出了五种任务调度算法和两种节能算法，并通过平台扩展在CloudSim中实现了这七种算法，并配置了具体的云计算场景进行了仿真实验与性能分析。

2 Cloud Sim体系结构

CloudSim云平台是一种开源模拟引擎，基于GridSim和离散事件驱动，可以模拟创建多种云计算环境中的实体，包括云数据中心、物理主机与虚拟机、各组件间的消息传输及时钟管理等。并且，CloudSim作为通用的可扩展的模拟框架，支持模拟新兴的云计算基础设施和管理服务。图1是Cloud⁃Sim体系结构。

2.1 用户代码层

用户代码层负责提供基本云实体，包括与主机（多台机器、多规格）、应用（任务及其需求）、虚拟机、大量用户及其应用类型和代理的调度策略的配置相关功能的用户代码。云应用开发人员可在本层开发各种用户需求分布、应用的配置请求和云可用场景，进行可靠性测试，从而实现自定义的云应用调度算法。

2.2 云资源层

该层负责物理资源建模。云中的硬件可以通过扩展数据中心实体实现，数据中心作为云系统的核心部分，负载管理物理主机，并对主机处理能力和存储进行分配，以及管理内核的调度。在Cloud⁃Sim云平台中，一个实体就是一个实例化组件，一个CloudSim组件可定义为一个类或者一个Cloud⁃Sim模型的类集。

图1 CloudSim体系结构

2.3 云服务层

尽管VM上下文是相互独立的（通常指主存和辅存空间），但仍会共享CPU内核和系统总线。因此，VM的可用资源仍受主机处理能力限制。为了实现不同环境下对不同调度策略的模拟，目前的CloudSim支持两层VM调度［15］：主机层和VM层。主机层中的VM调度直接指定VM可获取的处理能力，而VM层中，VM为在其内运行的独立任务单元分配固定的处理能力。

两层VM调度均实现了时间共享和空间共享。以下分析两者在应用任务调度性能上的区别。如图2，某主机可运行两个VM，该主机拥有两个CPU内核，每个VM请求两个内核并执行四个任务，T1、T2、T3、T4占用VM1，而T5、T6、T7、T8占用VM2。

图2（a）中，VM主机层和任务单元均采用空间共享。空间共享中，VM请求两个CPU内核，对应时间内只能运行一个VM。同样的原因，对于VM1，其任务单元分配模式也是一样的，由于一个任务单元只需一个CPU内核，因此可以同时运行任务单元T1和T2。此时，T3和T4在队列中等候。则VM完成任务集T的完成时间是：

图2 四种VM调度场景

其中，StartTime(T)表示云任务集的开始时间，MI(T)表示任务集T执行的总指令数。这种策略下，一个有N个CPU内核的主机总容量可表示为

其中，Cap(i)为内核处理能力。

图2（b）中，VM采用空间共享，任务单元采用时间共享。通过使用时间共享策略，VM完成任务集T的估计完成时间是：

其中，FinishTime(T)表示任务完成时间，NowTime(T)表示仿真时间，Cores(T)表示任务集的内核需求量。时间共享下，单个VM可同时运行多个任务。此时，主机总能力为

图2（c）中，VM采用时间共享，任务单元采用空间共享。此时，内核通过时间片原理将其处理能力在VM中进行分配，而时间片本身以空间共享方式分配至任务。由于内核共享，VM的可用处理能力是变化的。而任务单元是空间共享，表明内核只执行一个任务单元。

图2（d）中，VM和任务单元均采用时间共享。此时，VM共享处理能力，并且同时将共享内核分配至所有任务单元。

2.4 网络层

实现云计算实体的复杂网络拓扑结构等仿真实体进行建模。CloudSim云平台中的云实体（数据中心，主机，SaaS提供商及终端用户）的内部网络是抽象的网络概念。CloudSim实体间的网络通信延时是通过延时矩阵模拟的，延时单位以毫秒表示。由延时矩阵的含义可知，通过事件管理引擎实现实体i到实体 j的消息传递的总时间为t+d，t是仿真开始时间，d是传输延时。

2.5 虚拟机服务层

虚拟机服务层主要用来管理任务单元的操作和虚拟机的生命周期。

2.6 用户接口结构层

该层实现任务单元和虚拟机间的接口创建。根据以上的层次结构，将CloudSim的类划分为如图3所示的基础类设计图和如图4所示的内核模拟引擎类。

3 任务调度算法

对 CloudSim的 DatacenterBroker类的 bind⁃cloudlet ToVm（）进行扩展，实现任务与VM的绑定，图5是任务调度流程及实现类。通过重载bind⁃cloudlet ToVm（int cloudletId，int VmId），设计五种任务调度算法。

图3 CloudSim的基础类设计图

图4 CloudSim内核模拟引擎类图

图5 CloudSim云平台下的任务调度方式

1）SSA（Sequenced Scheduling Algorithm，顺序调度算法）：顺序将任务分配至所有VM，然后，重新分配新到来的任务时以第一个VM作为目标，直至完成所有任务。SSA算法可以保证每个VM执行的任务数量大致相同，实现负载均衡。

2）FCFSA（First Come First Service Algorithm，先来先服务调度算法）：按照先来先分配的方式，将任务分配至VM后，新到任务直接分配至最先完成任务的VM上，直至完成所有任务。FCFSA算法可以降低VM空闲时间，但处理能力较强的VM可能会负载过重，无法实现负载的均衡分配。

3）STFA（Shortest Task First Algorithm，短任务先调度算法）：将任务按大小（Million Instructor）升序排列之后，顺序调度至VM。

4）BSA（Balance Scheduling Algorithm，均衡调度算法）：将任务按大小（Million Instructor）对其进行降序排列，然后将VM按处理能力（MIPS）对其进行降序排列，任务集和VM集重新排序后，再调用SSA算法对任务进行调度。BSA算法的主要目标是将长任务尽量调度到处理能力更强的VM上，而处理能力较弱的VM则执行短任务，以便实现任务与VM之间的均衡调度，但这样会降低部分VM的资源利用率。

5）GSA（reed Scheduling Algorithm，贪婪调度算法）：首先，将任务按大小（Million Instructor）对其进行降序排列，将VM按MIPS进行升序排列。定义矩阵E(i，j)，计算任务大小与VM处理能力的比值，并将值存入矩阵，然后在矩阵中作贪婪选择：从E(0，j)中的任务开始，将其分配至最后一列VM，如果该调度结果最优，完成分配；否则，将该任务调度至使当前结果最优的VM。

4 云节能技术

虚拟化技术（Virtulization Technology）可以通过在一个物理主机上实例化多个虚拟机的方式来解决数据中心的高能耗问题，从而改善资源利用率，增加投资回报率。在云计算环境中，向用户提供确保以服务等级协议SLA定义的可靠QoS服务也是必不可少的，因此，对于云资源供应商而言，高能效与高性能间必须达到平衡，以解决能耗问题的同时提供高可靠QoS保障。

4.1 能耗模型

通常情况下，CPU是云系统能耗中能耗最高的部件，作者将主要关注CPU在能耗管理方面的问题。而且，对于计算机密集型应用，CPU的利用率与云系统负载是成正比的。本文实验部分，笔者将使用基于DVFS技术的线性额定关系功耗模型计算CPU的功能。

通常，对于CPU而言，空闲时服务器的功耗仍然是满载时的70%，表明设置空闲服务器成休眠模式可以降低系统的总体能耗，本文的功耗模型为

其中，Pmax为系统满载时的最大功耗，k为空闲时系统功耗比例，u为CPU的利用率。

通常，云系统中的负载执行是动态变化的，因此，u通常表示为u(t)，那么，总能耗E可定义为

4.2 SAL违例

云环境中的服务质量QoS是以服务等级协议SLA进行表示，基于些特征属性时行定义（最大化吞吐量，最小化响应时间或延迟）。

SLA违例表示为：所有VM请求的MIPS（Uj，r(t)）与实际分配的 MIPS（Uj，a(t)）之差与虚拟机在其生命周期内请求的MIPS总数之比：

其中，M表示VM数量。

4.3 节能算法

在CloudSim云平台中实现三种节能算法：DVFS、NPA以及STH算法。

1）DVFS（动态电压频率调整），算法思想是：考虑到执行任务时CPU利用率的不充分，降低CPU供电电压和时钟频率的方式达到降低CPU性能的目的，该方法不仅可以极大降低CPU的功耗，还可以保证服务性能。

2）STH算法。通过设置一个CPU利用率的阈值，在调度过程中始终保持其利用率不高于该阈值。其目的是为CPU预留部分处理能力，以满足对资源的动态增加需求，避免VM合并带来的SLA违例。若调度过程中CPU利用率高于阈值，则调用VM迁移算法降低利用率至阈值以内。

3）主机满载算法MPA：保持主机的最大功耗状态进行任务执行。MPA算法作为性能分析的比较算法。

4.4 任务调度的实体间通信

图6显示了CloudSim进行任务调度时实体间的通信流程。仿真初始化时，DataCenter实体通过CIS实体进行注册，DataCenterBroker在CIS中查询信息以获取云提供商列表，DataCenterBroker会选择CIS建议的云来部署应用。任务被分配到各自的VM之后，会持续更新任务处理过程。此时，DataCenter会调用 updateVMsProcessing（）管理主机。主机层上，updateVMsProcessing（）会触发up⁃dateCloulets-Processing（），以指示VM更新任务单元状态。该方法与updateVMsProcessing（）有类似的作用，不同之处在于updateClouletsProcessing（）方法在VM层上。调用updateClouletsProcessing（）方法后，VMs将返回任务单元的下一个期望完成时间，并传送所有完成时间中的最小值至DateCenter实体。

图6 CloudSim实体通信流程

5 Cloud Sim扩展与任务调度

通过扩展CloudSim，实现所提算法，并对扩展后的仿真工具包进行了重编译，并对算法性能进行了分析。

5.1 任务调度实验分析

创建一个云数据中心，主机数量、虚拟机和云任务的数量分别为1、4和8。具体参数如表1～表4所示，表1为用户任务单元参数，表2为虚拟机VM相关参数，表3为数据中心相关参数，表4为主机相关参数。

表1 云用户任务单元（Cloudlet）参数列表

表2 虚拟机（VM）列表

表3 数据中心（Datacenter）列表

表4 主机（Host）列表

5.2 实验结果与分析

图7和图8分别是单个任务的完成时间和任务完成总时间。综合两个图可以看出，GSA算法的完成时间是最短的，主要原因是由于GSA在所有VM上对任务做贪心选择策略，而STFA没有考虑VM处理能力间的差异，其任务完成时间最长。同时，SSA与FCFSA的完成时间是大致相等的，这主要是由于两种算法在开始阶段的任务分配方式是顺序的，但随着任务量的增加，尤其任务量远大于VM数量时，FCFSA将具有更大的优势。总体看来，BSA算法是次优算法。

图7 单个任务的完成时间

图8 任务完成总时间

5.3 节能算法实验分析

创建以下云场景，包括一个数据中心，主机数量变化范围为［10，50］，部署虚拟机变化范围为［20，60］，云任务的变化范围为［20，60］。虚拟机请求的MIPS分别为｛250，500，750，1000｝，虚拟机其他 参 数 如 下 ：pesNumber=1，ram=128，bw=2500，size=2500。主机处理能MIPS=｛1000，2000，3000｝，主机其他参数如下：raw=10000，storage=10000，bw=10000，云任务大小为150000MI。

图9 算法性能比较

图9从能耗、虚拟机迁移次数及SLA违例三个方面比较了STH算法、DVFS算法及MPA算法的性能。可以看出，STH算法的能耗是最少的，因为STH算法通过虚拟机的动态迁移与合并，基于当前的动态资源需求减少物理节点的使用数量，从而达到节省能耗的目的。MPA算法中主机功耗一直维持最大，因此能耗也最大，DVFS算法可以根据任务需求自适应调整CPU的频率，这极大降低了CPU能耗。DVFS算法和MPA算法均属于静态算法，不存在虚拟机的迁移操作，且均得到了任务请求的资源，故不存在SLA违例。

图10 STH固定阈值对于算法性能

图10考察了阈值算法STH中固定阈值对于算法性能的影响。总体看来，当增加固定阈值时，能耗会降低，但会增加SLA的违例次数，原因在于随着阈值的增大，虚拟机合并的机会也会增多，这样虚拟机迁移也会更加频繁。可以看出，阈值的选择需要折衷，并非越大越好，因为能耗与性能是需要均衡考虑的。

6 结语

本文详细分析与研究了CloudSim云平台的工作原理，主要剖析了CloudSim在仿真机制中提供的层次模型，在以上工作的基础上，研究了云环境中的任务调度问题，提出了五种任务调度算法，算法均只考虑了任务的执行时间，忽略了主机能耗。进一步针对这一问题，在CloudSim云平台中实现了两种节能算法。通过扩展CloudSim的相关类，对以上七种算法进行了仿真实验分析，仿真结果证明了算法的有效性。而进一步的研究在于：1）改进文中的固定阈值算法，利用负载预测机制，根据任务属性，动态地进行任务及虚拟机的部署，以便最大限度地实现能耗与性能的均衡；2）资源分配的负载均衡问题。负载均衡机制可以通过虚拟机迁移尽量减轻物理节点的负载，避免产生热点问题，提高云资源利用效率，满足用户对资源的需求，为云环境下高效的资源利用提供良好的基础。