基于三支队列的实时云任务节能调度算法

姜春茂，王凯旋

(哈尔滨师范大学 计算机科学与信息工程学院 黑龙江 哈尔滨 150080)

0 引言

云计算是一种新型的信息服务模式，通常基于虚拟化和分布式计算技术.在云计算过程中，资源的虚拟化利用率较低，但同时又有着较高的能耗.文献[1]研究表明，闲置资源的能耗可以达到总能耗的60%或者更多，所以提高云环境中的资源使用率和降低云能耗变得非常重要.文献[2]研究表明，当云环境中的虚拟机在资源利用率超过70%时，能耗会急剧上升.为了更合理地节约能耗，采用了云计算中一项能够有效降低云能耗的技术——任务合并[3-5].任务合并是一个为了最大化资源利用率和最小化能耗，而将一个任务(服务请求)集合分配到一个云计算资源集合的过程，它能够按照设定好的调度策略将任务分配给最适合的虚拟机来执行.

借鉴三支决策的基本思想[6-8]，本文提出了基于三支队列的实时云任务节能调度算法(简记为TQS算法).当用户提交一个实时任务给云平台以后，首先会利用其截止时间进行松弛时间的计算，之后按照松弛时间将任务放入紧急调度队列、正常调度队列和松弛调度队列.结合虚拟机的实际负载情况，对三个队列提交任务进行调度.结果表明，在满足任务实时性需求的情况下，TQS算法能够有效降低云能耗.

1 相关工作

三支决策的基本思想是通过一对阈值(α,β)将全集U划分成三个独立的部分，然后针对各个区域开发相应的策略.三支决策的唯一特征是使用三支方法进行问题的解决和信息的处理.三支是基本的出发点，决策是应用之一.

三支决策[3]作为一种有效的粒度计算方法，内在地切合了云平台的诸多特点，如云任务可以按照任务的类型(计算密集型、存储密集型、通信密集型)、作业的长短(长、中、短)等进行分类；虚拟机则涉及合并、迁移、关闭.本文结合三支决策的基本思想对实时云任务的松弛时间进行“三分”，不同的队列采取不同的任务合并策略进行调度执行.

文献[2]提出了ETC (energy-aware task consolidation)算法：当虚拟机在资源利用率超过70%时，能耗会急剧上升.因此，ETC算法认为将每个虚拟机利用率的上限限制在70%为最优.在云计算中调度器调度任务时，会按照一定的调度顺序提交任务给虚拟机运行(例如先到先服务、最短作业时间优先等策略)，每次提交的虚拟机都不会超过70%的使用率，如果所有虚拟机的利用率都超过了70%，那么就寻找当前资源利用率最低的虚拟机来运行这个任务.文献[9]提出了ESTC (energy saving task consolidation)算法：调度器会优先将任务提交给空闲的虚拟机，这样就极大降低了云环境中虚拟机的空闲率，减少了能耗，如果最后没有空闲的虚拟机，就找一个利用率最低的虚拟机来运行提交的任务.文献[10]提出了MTC (multi-criteria based task consolidation)算法：给每个时刻同时到达的任务计算一个适应值，调度器按照适应值的升序来调度任务，适应值低的优先提交，越高的会越晚提交，适应值F的计算公式为

F=λ·NT+(1-λ)·NU，

(1)

式中：0<λ<1；NT表示规格化运行时间，即当前任务的运行时间除以同时到达任务中的最大运行时间；NU为规格化利用率.之后按照适应值从大到小进行排序，调度器依次提交任务给虚拟机执行.文献 [11]提出了MQS (multi queue scheduling)算法：MQS算法是一种多队列调度算法，在调度之前，调度器会按照任务的突发时间对任务进行升序排序，这里的突发时间是指任务从到达到任务开始所需要的时间，可以表示为

Ti(BT)=Ti(ST)-Ti(AT).

(2)

本文提出了TQS算法，其基本思想是按照突发时间排序，将任务分成三个队列，之后将三个队列通过一定的算法分为两个队列进行提交运行.TQS是一种基于实时任务的松弛时间进行任务的三支划分，然后合并调度的机制，即将提交的任务按照松弛时间进行三支队列排序，之后按照不同的队列顺序对任务进行调度执行.

2 TQS算法

2.1 问题描述

一个具有n个实时云任务的集合T={T1,T2,…,Tn}，Ti是一个六元组{AT,ST,UT,PT,FT,DL}，任务属性含义如表1所示，m个虚拟机的集合V={V1,V2,…,Vm}，其属性如表2所示.

表1 任务属性Tab.1 Task properties

表2 虚拟机属性Tab.2 Virtual machine properties

每一个任务都会被调度器分配到一台合适的虚拟机上运行，每一台虚拟机又都具有一定的属性，虚拟机的利用率与能耗呈线性增长关系.为了降低云计算中的能耗，需要设计一个调度算法来降低虚拟机在运行任务时的利用率，从而达到降低能耗的目的.在降低能耗的同时，也需要考虑任务的违约率，如果违约率过高，将会极大地影响到用户体验.

2.2 调度算法

TQS算法是一种任务合并调度算法，算法除了考虑到节约云环境能耗，还考虑了任务的SLA违约问题.SLA违约问题是指用户提交任务后，任务完成的时间超过了任务的截止时间.在云环境中虚拟机利用率越高，单位时间内能耗就越多.TQS算法的主要思想就是减少虚拟机运行在高利用率的时间，让不紧急的任务尽可能得晚，但是又在不违约的情况下提交给虚拟机运行，从而减少能耗.紧急任务(UrgentTask)提交如图1所示，其中LocalTask为已经运行在虚拟机上的任务，如果此时将UrgentTask立即提交，重叠时间为4.2 s，在此期间，虚拟机运行的利用率为20%.

正常任务(NormalTask)提交如图2所示，如果到达的任务按照松弛时间判断为NormalTask，那么可以等候一段时间再提交，此时的重叠时间为3.2 s，这就证明在任务延后提交后，虚拟机在利用率为20%时运行了3.2 s，比UrgentTask提交时减少了1 s.

图1 紧急任务提交Fig.1 Emergency tasks submitted

图2 正常任务提交Fig.2 Normal tasks submitted

图3 松弛任务提交Fig.3 Relax tasks submitted

松弛任务(RelaxTask)提交如图3所示，此任务可以等待整个云环境中最先完成任务而空闲下来的虚拟机再进行提交运行.从图中可以看到，两个任务没有重叠时间，所以虚拟机没有达到过20%的利用率，这样就使虚拟机一直运行在较低的利用率水平，从而达到节省能耗的目的.

松弛时间(RelaxTime)代表了一个任务需要处理的紧急程度.通过对松弛时间的判定，将任务分为紧急任务、正常任务和松弛任务，分别将其放入三个相对应的调度队列，即紧急队列(UrgentQuene)、正常队列(NormalQuene)和松弛队列(RelaxQuene).

当调度器开始调度时，具体步骤如下：

1) 首先提交紧急队列中的任务.

2) 处在正常队列中的任务会一直等待，直到正常队列中排序最前的任务的松弛时间小于5 s，将此任务移动到紧急队列中，再立即提交此任务.

3) 对松弛队列中的任务，可以一直等到云环境中最早完成任务的虚拟机完成正在运行的任务后，再将松弛队列中的第一个任务提交给虚拟机运行，之后每1 s刷新一次队列状态.

当一个任务到达时，任务的松弛时间可以表示为

Ti(RT)=Ti(DL)-(CT+Ti(PT))，

(3)

式中：RT(RelaxTime)为松弛时间；DL(DeadLine)为任务的截止时间；CT(CurrentTime)为当前系统的运行时间；PT(PeriodTime)为任务的运行时间.

如果任务Ti的RT小于5 s并且大于0，则Ti为紧急任务，将其加入紧急队列；如果任务Ti的RT大于5 s,但是小于云环境中所有虚拟机的最小任务完成时间(意味着此任务无法等到有空闲虚拟机出现)，那么Ti为正常任务，将其添加到正常队列；如果任务Ti的RT大于云环境中所有虚拟机的最小任务完成时间(意味着此任务可以等到一台空闲虚拟机的出现)，那么将其添加到松弛队列.

假定一个虚拟机集合V={V1,V2,V3}，其中Vi={TUi，UUi，RUi，TLi，MTi}，虚拟机属性如表2所示.设置一个任务集合T={T1,T2,T3}，其中Ti={ATi，STi，UTi，PTi，FTi，DLi}，任务属性如表1所示.云计算中空闲虚拟机与处在工作状态中的虚拟机的能耗计算方法是不同的.

空闲虚拟机的能耗计算公式为

E(IVMi)=P20·Δv，

(4)

式中：E(IVMi)为VMi在空闲时的能耗；P20为虚拟机在利用率为20%时的能耗；Δv=vmax-vmin，为虚拟机开机时间减去虚拟机关机时间，即虚拟机持续运行的时间.

处在运行状态下的虚拟机的能耗计算公式为

(5)

式中：E(NVM2(X))为VM2在利用率为X时的能耗；%为取余运算符.

算法具体步骤如下.

输入：n个任务与m个虚拟机；输出： 云计算总能耗.

Step1计算每个任务的松弛时间.

Step2按照松弛时间判断任务，将任务分为三个队列,Ti∈UQ,Ti∈NQ,Ti∈RQ.

Step3首先提交紧急队列中的任务，如果有空闲虚拟机，优先使用空闲虚拟机，如果虚拟机全为运行状态，就挑选当前利用率最低的虚拟机进行提交.

Step4更新时间，检查正常队列中是否有任务的松弛时间小于5 s，如果有，就将任务移动到紧急队列,Ti∈UQ，再提交给虚拟机.

Step5检查是否有虚拟机K完成任务，如果完成，就将在松弛队列中的第一个任务提交给虚拟机K运行.

Step6所有任务提交完成后，按照能耗计算公式计算总能耗.

2.3 算法复杂度分析

TQS算法的时间复杂度主要集中在调度步骤，设提交的任务总数为n，执行任务的虚拟机总数为m，虚拟机最早完成任务的时间为k.在调度过程中，遍历两次任务总数n，遍历搜索一次虚拟机总数m，迭代次数为O(n2×m)，所以TQS算法的时间复杂度为O(n3).

TQS算法中建有任务链表、虚拟机链表，建有紧急队列、正常队列、松弛队列，每个队列内部对象均为可数，即TQS算法的空间复杂度为O(n).

表3 生成任务属性Tab.3 Generate task properties s

2.4 算例说明

给出一个算例，提交5个实时任务，生成任务属性如表3所示.云环境中有两台虚拟机VM1和VM2，初始状态如下：TU为100%，UU为0，RU为100%，TL为Null，MT为0.

1) 从表3中可以看出，最先到达的为T5，根据式(3)计算其松弛时间为：T5(RT)=35 s，但是因为此时虚拟机没有运行任务，所以将T5提交给VM1直接运行，此时VM1的MT为T5的开始时间(ST)加上运行时间(PT)，为55 s.

2) 表3中第二个到达的任务为T1，根据式(3)计算其松弛时间为：T1(RT)=0 s，此时VM2上并没有运行任务，所以将T1提交给VM2运行，此时VM2的MT为T1的开始时间(ST)加上运行时间(PT)，为168 s.

3) 在13 s时任务T4到达，T4(RT)=1 s，所以将T4放入紧急队列，并且同时立即提交，此时两个虚拟机都被占用，选择利用率为12%的VM1来执行T4，此时VM1的最大任务完成时间为T4的完成时间，为58 s.

4) 在21 s时任务T3到达，T3(RT)=49 s，因为5 s

5) 在28 s时任务T2到达，T2(RT)=58 s，因为5 s

3 实验数据分析

测试的主机CPU均为四核，主RAM为16 GB，硬盘容量为1 TB，带宽1 Gbit/s，实验所需虚拟机在利用率为1%～20%、21%～30%、31%～40%、41%～50%、51%～60%、61%～70%、71%～80%、81%～90%、91%～100%时的能耗分别为78.5、83、85、88、93、102、109、122、136 W[3].

3.1 在少量任务情况下的实验数据分析

在模拟环境中随机生成了三个任务，属性见表3中的T1、T2、T3，其中任务到达时间(AT)服从泊松分布，运行时间(PT)服从指数分布.主机上运行三台虚拟机用作云任务处理机，实验共运行10次.三个任务在三台虚拟机上分别使用ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法，在少量任务情况下不同时间的能耗如表4所示.

通过实验数据可以计算得出ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法的总能耗分别为46 937、34 547、43 910、48 624、34 547、31 721 W.可以看出，在较少任务数量的实验中，ETC、MTC和ETC&MQS算法的能耗较高，ESTC和ESTC&MQS算法的能耗相对较低，TQS算法的能耗为最优.

表4 在少量任务情况下不同时间的能耗Tab.4 Energy consumptions under a small amount of tasks at different time W

3.2 在较多任务情况下的实验数据分析

在较多任务测试的情况下，实验自动生成了500个任务，其中任务到达时间(AT)服从泊松分布，运行时间(PT)服从指数分布，经过10次实验，取平均值得出6种算法在较多任务情况下不同时间的能耗，结果如表5所示.

表5 在较多任务情况下不同时间的能耗Tab.5 Energy consumptions under more tasks at different time 103 W

从实验数据可以得出ETC、ESTC、MTC、ETC&MQS、ESTC&MQS和TQS算法的总能耗分别为2.3×107、4.39×106、2.29×107、2.44×107、4.39×106、4.08×106W.从500个任务的实验结果可以看出，在较多任务情况下，ETC、MTC和ETC&MQS算法的能耗非常高，ESTC和ESTC&MQS算法的能耗相对较低， TQS算法的能耗为最优.

3.3 算法的能耗增长趋势测试

系统分别随机生成5、10、15、20、25、30、35、40、45个任务，其中任务到达时间(AT)服从泊松分布，运行时间(PT)服从指数分布，系统相应地自动生成5、10、15、20、25、30、35、40、45个虚拟机，共进行了10次实验.结果表明，在少量任务时，6种算法的能耗都较低，但在任务数超过25个时，ETC、ETC&MQS和MTC算法的能耗开始急剧增长，而在较多任务情况下，TQS算法仍然保持着较低的能耗水平.实验结果验证了TQS算法能够在保证违约率的同时减少在云计算中的能耗.

4 小结

本文提出了基于三支队列的实时云任务节能调度算法，在不违约的情况下能更加合理地调度任务，将每个任务的截止时间利用得更好，尽可能地减少云环境中虚拟机运行在高利用率的时间.实验结果表明，无论TQS算法在少量任务或者较多任务的情况下，能耗都优于其他5种算法，尤其是ETC算法.基于实时任务的松弛时间进行任务的合并调度算法，确实能够有效降低在云环境中的能耗.下一步将在算法的优化和面向容器的能耗优化中，更多地使用多粒度三支决策的思想进行任务的调度、容器的合并等.