一种基于能耗优化的云计算系统任务调度方法

2013， 49 （20）1引言云计算系统通常由异构的服务器组成， 由于不同服务器硬件配置和计算性能的不同， 使得任务映射到不同服务器上执行产生的能耗也可能不同。 在大规模的云计算系统中， 有效降低系统能耗是云计算系统面临的一个新挑战。 在大规模云计算系统中， 云计算系统的任务调度不仅要满足用户对服务质量的要求， 还要尽可能降低云计算系统任务执行的总能耗。 云计算系统任务执行的总能耗由各个服务器执行能耗的和。 服务器执行能耗是任务在服务器上运行时产生的能耗， 它随着服务器的执行功率和任务在服务器上执行时间的变化而变化。 目 前，云计算系统的能耗优化方法可分为两大类： 一类是基于 DVFS （DynamicVoltage/Frequency Scaling） 的能耗优化方法， 它通过降低数据中心服务器的运行频率， 延长任务执行周期来降低数据中心的能量消耗； 另一类是通过将任务集中到少数服务器上运行， 让闲置服务器关闭或处于睡眠状态来降低数据中心的总能耗。 能耗优化是实现绿色云计算系统的一个重要基础， 众多学者从不同的视角提出了针对云计算系统的能耗优化管理方法。 文献[1]提出了一种基于 CPU 使用率和频率来计算云计算系统的能耗； 文献[2]提出了基于数据中 心 服务转移的 能耗控制 框架； 文献[3] 提出 了 基于DVFS 的多目 标能耗优化模型， 它通过引入虚拟机的最小运行频率， 将云计算系统中的虚拟资源分配问题建模为一个多目 标优化模型并使用多目 标进化算法求解该模型； 文献[4]针对硬实时服务模型和软实时服务模型， 提出了基于DVFS 的能量感知的虚拟机分配算法； 文献[5]建立了基于基金项目 ： 天津市高等学校科技发展基金 （No.20120817）； 天津财经大学预研项目（No.Y1211）。

作者简介： 何丽 （1969—）， 女， 博士， 副教授， 主要研究方向： Web服务、分布式计算； 饶俊 （1979—）， 男， 博士， 讲师， 主要研究方向： 分布式计算； 赵富强 （1974—）， 男， 博士， 副教授， 主要研究方向： 社会网络、分布式计算。 E-mail： renke21@vip.sina.com收稿日 期： 2013-05-02修回日 期：2013-07-09文章编号：1002-8331 （2013）20-0019-04CNKI出版日 期： 2013-07-29一种基于能耗优化的云计算系统任务调度方法何HE Li, RAO Jun, ZHAO Fuqiang丽， 饶俊， 赵富强天津财经大学 信息科学与技术系， 天津 300222Department ofInformation Science and Technology, Tianjin University ofFinance and Economics, Tianjin 300222, ChinaHE Li, RAO Jun, ZHAO Fuqiang. Task scheduling method based on energy optimization in cloud computing system.Computer Engineering and Applications, 2013, 49 （20）：19-22.Abstract： The energy consumption of servers produced in tasks executing is an important part of system dynamic energy incloud computing system. In order to lower the total task execution energy consumption of system, this paper presents a taskscheduling method based on energy optimization with the earliest task completion time, builds the dynamic power computingmodel of server, energy model based on dynamic power of servers, and the energy optimization model of cloud computing sys-tem. The proposed method uses different scheduling algorithms to get less task execution energy according to the deadline oftask and the execution energy on each server. Experimental results show that this scheduling policy can better meet the deadlineoftask, and reduce the total energy ofcloud computing system considerably.Key words： cloud computing; energy optimization; task scheduling; task deadline摘要： 服务器执行任务产生的能耗是云计算系 统动态能耗的重要组成部分。

为 降低云计算系 统任务执行的总能耗， 提出 了 一种基于能耗优化的最早完成时间 任务调度方法， 建立了 服务器动态功率计算模型， 基于动态功率的服务器执行能耗模型， 以 及云计算系 统的能耗优化模型。 调度策略根据任务的截止时间 要求和在不同 服务器上的执行能耗， 选择不同的调度算法， 以 获得最小任务执行总能耗。 实验结果证明 ， 提出 的任务调度方法， 能够较好地满足任务截止时间 的要求，降低云计算系 统任务执行的总能耗。关键词：云计算； 能耗优化； 任务调度； 任务截止时间文献标志码：A中图分类号：TP316doi： 10.3778/j.issn.1002-8331.1304-0449Computer Engineering andApplications计算机工程与应用19Computer Engineering andApplications计算机工程与应用2013， 49 （20）多个数据中心的能耗计算模型， 该模型通过跨数据中心的服务转移来提高数据中心的能量消耗； 文献[6]提出了基于CPU利用率的服务器能量消耗模型； 文献[7]提出了基于成本驱动的虚拟机调度策略， 实现了系统利益最大化的虚拟机调度策略； 文献[8]提出了一种基于机器学习和能耗感知的任务调度算法， 通过建立基于决策树和线性回归的机器学习模型来预测数据中心服务器的能量消耗， 但这种调度算法需要依赖相关任务的历史行为； 文献[9]提出了基于任务类型调度概率的云计算平台能耗优化管理方法； 文献[10]提出了基于蚁群优化算法的云计算任务分配方法。

此外，学者们还提出了基于虚拟机动态分配的云计算系统能耗[11-15]。 以上研究成果主要通过虚拟资源优化管理管理方法来降低云计算系统的运行能耗， 没有根据不同的任务要求来调整任务调度策略。 本文根据用户对任务截止时间的要求， 提出了一种基于能耗优化的最早完成时间调度方法。 该调度方法首先选择在所有服务器上具有最早完成时间的任务， 然后根据任务截止时间的紧迫程度， 将其映射到相应的服务器上执行， 在尽可能满足任务截止时间要求的情况下， 将任务分配到执行能耗最小的服务器上执行， 以获得更好的能耗优化效果。2问题描述在由异构服务器组成的云计算系统中， 由于同一任务在不同服务器上的运行时间和服务器执行功率的不同， 使得同一任务在不同服务器上执行的计算性能和产生的能耗也会有所差别。 服务器的执行能耗与服务器执行任务时的动态功率和任务在服务器上的执行时间密切相关[1]。为了建立云计算系统的能耗优化模型， 首先需要建立云计算系统中任务和服务器的描述模型。 假设云计算系统中配置了 M 台异构服务器， 则将服务器集合描述为 S={s1? s2? ?? sM} 。 对集合S中的任意一个服务器 sj(1 ? j? M) ，令 sj=< sid? SNumCpu? Ppeak? Pidle> 。

其中 sid 是服务器 sj的编号， SNumCpu表示服务器 sj拥有的 CPU个数， PPidle分别表示 sj的峰值功率和空闲功率。peak和云计算系统中的任务集合用 T表示， 将由 N个任务组成 的 任 务 集 描 述 为 T={t1? t2? ?? tN} 。 对 T 中 的 任 务ti(1 ? i? N) ， 令 ti=< tid? RCpu? Runtime? deadtime > 。 其中，tid是任务 ti的编号， RCpu 表示 ti请求的 CPU数量， Runtime表示 ti在单处理器上的估计运行时间， deadline 表示用户对 ti的截止时间要求。为记录任务在不同服务器上的执行时间， 建立矩阵AN? M， A 的每一行表示一个任务， A 的每一列表示一个服务器， 对任一元素 Aij(1 ? i? N? 1 ? j? M) ， 其值是任务 ti在服务器 sj上的执行时间。 理论上每增加一个 CPU， 服务器每个时钟周期内执行的指令数可以增加一倍。 因此， 本文将 Aij的值定义为：Aij=ìí?? ?? ?ti.Runtimesj.SNumCpu0， 其他? ti.RCpu ? sj.SNumCpu3服务器执行能耗和任务调度服务器能耗计算模型服务器在运行状态的功率称为服务器的执行功率， 服3.1务器的执行功率与该服务器的峰值功率和 CPU 的利用率成正比。

服务器的执行功率一般在 Pidle和 Ppeak之间。 对任意一个服务器 sj(1 ? j? M) ， 用 uij表示表示 sj执行任务ti(1 ? i? N) 时的 CPU 利用率， 将 sj的执行功率计算公式描述为：Pij= sj.Pidle+(1 - α).Ppeak.uij（1）在式 （1） 中， uij= ti.RCpu/sj.SNumCPu ， α 为服务器空闲功率与峰值功率的比值。 当服务器处于执行状态时， 其执行功率与 CPU的利用率成正比。 服务器处于空闲状态时， 其执行功率等于 Pidle。服务器执行任务时产生的能耗称为服务器的执行能耗。 服务器的执行能耗与服务器的执行功率和分配到该服务器上的任务总数和每个任务的运行时间相关。 假设用 eij表示服务器 sj在执行任务 ti时产生的执行能耗， 则根据公式 （1）， 可以将 eij的计算模型描述为：eij= Pij? Aij（2）云计算系统执行任务集合中所有任务产生的总能耗等于各个服务器执行能耗的和。 云计算系统能耗优化的目 标是使系统在该任务集上产生的总能耗最小。 根据式（2）可以将云计算系统的能耗优化模型描述为：N?j= 1min?i= 1Meijti.RCpu ? sj.SNumCpu（3）3.2任务调度算法在一个拥有 M台服务器和 N个任务的云计算机系统中， 任务调度的目 标是把 N个任务映射到 M台处理器上，在尽可能满足任务截止时间要求的前提下， 使系统在任务集上产生的总能耗最小。

min-min算法是一种经典的分布式任务调度算法，它每次从任务队列中选择一个当前最小任务云计算调度系统， 并将其映射到具有最早完成时间的服务器上执行，该算法能够获得较好的计算性能。 云计算系统一般由 多个异构服务器组成， 不同服务器对任务的执行功率和响应时间可能会不同， 任务执行产生的系统能耗也可能不同。鉴于此， 本文提出了一种基于能耗优化的最早完成时间任务调度方法。 该调度算法将能耗优化方法应用到 min-min任务调度算法中， 它根据系统对任务截止时间要求的满足程度， 优先选择任务队列中的最短任务， 并将其分配执行能耗最小的服务器上执行。 当任务集合不为空时， 每次从任务集中选择一个完成时间最小的任务执行， 然后计算该任务在每个服务器上的执行能耗， 首先考虑将任务分配到执行能耗最小的服务器上执行， 并计算任务在该服务器上的完成时间， 如果完成时间能满足该任务的截止时间要求， 本次任务调度结束， 否则， 使用 min-min调度策略， 将当前任务映射到完成时间最小的服务器上执行。202013， 49 （20）为方便模型实现， 在算法实现过程中， 建立两个临时矩阵 bN? M和 mctN? M， bN? M和 mctN? M的每一行表示一个任务， 每一列表示一台服务器。

bN? M描述任务与服务器之间的映射结果， 以及任务在相应服务器上的执行时间。当任务 ti(1 ? i? N) 被调度到服务器 sj(1 ? j? M) 上执行时，令 bij= Aij， 其他情况令 bij= 0 。 矩阵 mctN? M描述服务器按照调度结果执行任务后的就绪时间。 若任务 ti被映射到服务器 sj上执行， 则 mctij等于 ti在 sj上的完成时间。 同时， 为避免服务器出现过载现象， 设置一个服务器负载上限 Wh， 当服务器负载大于 Wh时， 暂不接收新任务。 服务器 sj的负载用 wj表示， 将 wj的计算模型描述为：wj=?i= 1N?k= 1Nbij?i= 1Mbik（4）云计算系统提供的服务是一种有偿服务， 需要满足用户对任务服务质量的要求。 本文以任务的完成截止时间来描述用户对任务服务质量的要求， 并用 SLAs来统计调度算法对任务集合中任务服务质量的违反情况。 当一个任务的完成时间大于该任务的完成截止时间时， 则认为违反了当前任务的服务质量要求， 令 SLAs 加 1。根据上述描述， 将基于能耗优化的最早完成时间任务调度算法描述如下：输 入 ： 服 务 器 集 合 S={s1? s2? ?? sM} ， 任 务 集 合T={t1? t2? ?? tN} ， 任务在各个服务上执行时间矩阵 AN? M，服务器负载上限 Wh。

输出：系统总能耗TE和违背截止时间的任务比例SLAs。步骤：1.初始化（1） TE= 0; SLAs = 0;（2）FOR ( j= 1 to M) {① Ej= 0 ； // Ej表示 sj的执行能耗②FOR (i= 1 to N) {mctij= Aij；bij= 0; }}2.WHILE （T不为空）{（1） t= Min_t(mct)//函数Min_t返回 T中完成时间最小的任务t（2） tempE= ?; s = - 1 ；（3）FOR ( j= 1 to M) {①根据式 （2）计算 etj；②根据公式 （4）计算 wj；③IF (etj< tempE && wj? Wh) {tempE= etj； s = j ； }}（4）IF (mctts+ Ats> t.deadline)s = Min_s(mct[t]) ；//函数Min_s返回完成时间最小的服务器s（5）完成任务t到服务器s的映射① t? s ； //将t映射到 s上执行② bts= Ats； mctts= mctts+ Ats；③IF (mctts> t.deadline) SLAs + + ；④ Es= Es+ ets；⑤ T= T-{t} ；}//ENDWHILE3. TE=?i= 1MEi； SLAs =SLAs||T；4实验实验设置为验证本文提出的基于能耗优化的最早完成时间任务调度算法的有效性， 本文使用 VC++ 6.0 进行仿真， 在仿真4.1实验中， 数据中心中设置两种异构服务器模型， 参数设置见表 1。

实验随机生成 5 个服务器和 5 000 个任务， 随机抽取其中的 100、300、500、1 000、2 000、3 000、4 000 和 5 000个任务建立8个任务集合。 实验中，两种服务器模型的峰值功率分别设为 250 W 和 150 W， 空闲功率分别设为 150 W和 75 W， 服务器空闲功率和峰值功率的比值 α 设为 0.7。4.2实验分析性能分析4.2.1为验证基于能耗优化云计算系统任务调度算法在响应时间上的有效性， 分别在上述 8 个任务集合上对本文算法、min_min算法、文献[9]算法的计算性能进行比较了， 具体包括三种调度算法在各个任务集上的平均响应时间和违背任务截止时间的百分比。 一个任务的响应时间...

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!