云计算中基于预先分类的调度优化算法

左利云，左利锋

（1.广东石油化工学院 实验教学部，广东 茂名525000；2.郑州宇通客车股份有限公司 新能源产品部，河南 郑州450016）

0 引 言

云计算是当前IT界的研究热点，其强大能力最终通过其任务的运行性能体现，而资源调度算法设计的好坏对系统效率的高低起着至关重要的作用［1－3］。如何充分利用云计算中的计算资源并高效合理的使用是云计算领域的一个研究重点和难点。云计算的使用是付费的，而其费用开销主要体现在云的使用时间上。因此研究重点还是放在缩短完成时间上。云计算中包含大量异构资源，且资源动态变化，并存在多个任务竞争资源等问题，这使得传统的资源调度算法备受限制［4－8］。现有的资源调度算法中以追求最短完成时间为目标的有经典的启发式算法如Min－Min算法、Max－Min算法和sufferage算法等，另外还有些相应的改进算法［9－12］，但是它们没有很好的兼顾调度执行时间最小与负载平衡问题，这对于以资源共享和追求最大可能利用资源的云计算是很不利的。本文提出一种新的调度资源算法，以期在实现最小执行时间的同时平衡负载，从而实现云计算中资源共享和最大可能的利用资源。

1 预先分类调度模型

1.1 云计算环境中的调度

之前提到云计算中资源异构且动态变化等特点会影响到调度策略问题，事实上云计算环境中的服务类型也会影响到云计算资源的调度［13］，因为不同的服务类型，在资源使用、负载类型和性能评价指标等方面也有很大差异。

云计算中的服务大致分为两大类：数据计算密集型服务 （下简称计算型）和交互密集型网络处理服务 （下简称交互型），在负载类型、资源使用和性能评价的差异如下：

（1）负载特征：计算型负载是并行批处理作业，交互型负载是一系列的单链接或多链接的请求序列组成；

（2）资源使用特征：计算型需要独占资源处理作业，交互型请求可以在共享资源上并发执行；

（3）服务性能指标：计算型服务的用户可以容忍作业的排队等等，直到获得运行的资源，而交互型服务的用户请求需要在线立即地响应。

本文的调度算法主要针对计算型云计算服务而进行研究的。因此批处理算法中的经典算法——Min－Min算法无论从其追求最小完成时间的目标，还是针对数据计算密集型服务调度的特点，都说明该算法比较适合云计算中计算型服务调度。该算法简单、快速，通过计算两次最小值来完成资源的调度，尽可能将大量的任务调度到执行它最快的资源，以使得总体完成时间最小。但它总优先调度小作业，造成对大任务不公平的问题，也使得部分资源繁忙，部分资源闲置。针对此问题也有一些对应的改进算法，如文献 ［14］为了平衡负载根据QoS需求对资源简单分成两大类：特殊资源和一般资源，对任务也分类标记，将指定高要求的任务调度至特定资源，但它对资源分类过于简单，没有提及分类依据。

在此也提出对Min－Min算法进行改进优化，首先对云计算中资源根据其属性信息进行预先分类，以确保负载平衡，再对分类后资源结合Min－Min算法思想进行调度，以实现调度时间最小，从而兼顾执行时间最小与负载均衡。

1.2 预先分类调度模型

由于Min－Min算法仅考虑作业在资源的执行时间，故尝试将资源本身的因素考虑在内，在调度前先对资源进行等级划分，在调度时结合资源等级及任务调度执行时间，从而确保时间最小并充分利用资源平衡负载。基于此思想，调度模型的调度器由两部分组成：预先分类窗口和调度窗口。首先在预先分类窗口对云计算系统中资源的属性信息进行分类，将分类后资源等级数据信息送入下一单元——调度窗口，再使用Min－Min改进优化算法进行调度输出，如图1所示。

2 预先分类方法

图1 预先分类模型框架

为了充分利用云计算中的资源，尤其是优势资源，在调度器中先对云计算系统中的资源进行分类，在此采用可标识资源自身属性的资源可见度η这一指标，该指标用来衡量资源的计算能力和通信能力，它是根据在资源加入云计算系统时提供的属性信息来计算的，主要包括CPU个数h及处理能力P、磁盘容量C（MB）和资源所在的网络带宽B（Mb／s）。其中，CPU个数h和处理能力P主要反映资源计算能力，带宽反映资源的通信能力。资源可见度具体计算公式如下

式中：a、b、c——资源计算能力、磁盘容量、带宽在资源可见度这一指标中所占的比重。由于现在调度的对象是云计算中数据计算密集型服务，故根据需要在此分别将a、b、c设定为40%、20%、40%。

根据计算出的资源可见度η进行资源等级分类。具体做法是对资源按η从大到小进行排序，排名前35%的定为第1级，以下的30%、20%、15%分别定为第2、3、4等级。

3 基于预先分类的Min－Min优化调度算法

首先分析原始Min－Min算法的调度思想和执行过程，针对其负载不均衡问题进行改进优化，结合之前对资源划分的等级提出新的改进算法，即基于预先分类的Min－Min优化调度算法 （reservation category Min－Min，RCMM）。

3.1 原始的 Min－Min算法

原始的Min－Min算法尽可能将任务分配到执行时间最小的资源上，从而使得整体完成时间最小。Min－Min算法中 “Min－Min”的含义是通过计算两次最小值来完成资源的调度，两次最小值分别指的是首先计算每个任务在相应资源上的最小完成时间，再从这些最小完成时间中择其最小值，那么此时的资源－任务组合即为最佳资源－任务组合［15］。算法过程如下。

首先假设云计算环境中有n个任务Y＝ ｛y1，y2，…，yn｝和m个资源X＝ ｛x1，x2，…，xm｝。循环执行以下步骤直至集合为空：

（1）for each yiin Y；

求 mintime（yi至x1，x2，…，xm）；

Tmin（i）＝Min（mintime（yi至x1，x2，…，xm））；

得到有m个元素的数组Tmin（i）；

（2）if Tmin（i）最小；

yi调度至xj；

（3）delete yi；

Next yi

表1列出了每个作业任务在相应资源的预期执行时间矩阵的值，其中 “－”代指该作业无法在此资源运行，如作业y1只能在资源x1、x3、x4上执行，而作业y3则可以在任何一个资源执行。由算法执行过程可知，调度顺序为：y5（x1），y2（x1），y1（x1），y3（x1），y4（x1）。此时任务总体完成时间为：4＋3＋7＋10＋2＝26ms。但此时所有的作业都使用资源x1，而资源x2、x3、x4完全空闲，导致资源严重失衡，这就是Min－Min算法的最大缺点，它总是优先调度小任务而不能确保云计算资源负载平衡。这对于以资源共享和追求最大可能利用资源的云计算来说是非常严重的问题。因此必须改善这种状况，以适应云计算环境的需要。

表1 作业任务在资源上的预期执行时间

3.2 RCMM调度算法

针对以上对原始Min－Min调度算法的分析，提出基于预先分类的 Min－Min优化调度算法——RCMM调度算法，给出其执行过程，并与原始算法进行对比分析。

3.2.1 算法执行过程

由以上分析知原始的Min－Min调度算法存在的负载不均衡问题，改进的Min－Min调度算法就是要解决这个问题的，考虑资源差异，首先算出每个作业任务在所有资源上的执行组合值 （即作业在资源上的执行时间与资源等级的乘积）情况，然后从中选择执行组合值最小的任务－资源对进行调度，这样既能保证执行时间最小，又同时保证了调度过程的负载平衡。

仍然假设云计算环境中有n个任务Y＝ ｛y1，y2，…，yn｝和m个资源X＝ ｛x1，x2，…，xm｝。循环执行以下步骤至集合为空：

（1）for each yiin Y

求 mintime（yi至x1，x2，…，xm）；

yiTmin（i）＝Min（mintime（yi至x1，x2，…，xm））；

（2）Comxy（i，j）＝yiTmin（i）×资源等级；

得到二维数组Comxy［i，j］；

（3）对Comxy［i，j］排序；

（4）if Comxy［i，j］最小；

将yi调度至xj；

（5）delete yi；

Next yi

该算法相对于原始的Min－Min算法，除依然追求最小执行时间，还考虑到了平衡负载。

3.2.2 算法分析

对于资源x1、x2、x3、x4由预先分类方法计算出相应等级类别分别为3、2、1、1。通过RCMM调度算法，得出作业与资源相关数据信息如表2所示。

表2 作业任务在资源上的预期执行时间和资源等级属性

从表2可以看出：如果采用原始的Min－Min调度算法来执行的话，那么所有的任务都选择在资源x1上执行，调度的顺序依次为：y5（x1），y2（x1），y1（x1），y3（x1），y4（x1）。造成x1负载过重，单个资源利用率为100%，而x2、x3、x4却闲置，利用率为0。这是原始的Min－Min调度算法的最大问题。若采用本文改进的算法，先计算每个作业任务与各个资源的执行组合值分别为：y1（4＊4，－，4.5＊1，5＊2）；y2（3＊4，3.5＊3，12＊1，－）；y3（7＊4，8＊3，7.5＊1，9＊2）；y4（10＊4，11＊3，－，10.5＊2）；y5（2＊4，9.5＊3，9＊1，6＊2）。对每个作业取执行组合值最小的作业－资源对，调度顺序为：y1（x3），y5（x1），y2（x2），y3（x3），y4（x4）。这时作业整体完成时间为：4.5＋3.5＋7.5＋10.5＋2＝28ms。

由以上分析可知，改进后的算法使得作业整体完成时间增加了2ms，但是平衡了负载，原始的Min－Min调度算法使得所有的任务都在x1上执行，而x2、x3、x4空闲，导致x1负载过重，资源严重失衡，资源x1的利用率为100%，而x2、x3、x4的利用率均为0。而改进后的算法使得资源x1、x2、x3、x4的利用率分别为20%、20%、40%、20%，提高了资源的整体利用率，避免了资源调度中部分资源拥塞而部分资源闲置的现象。因此虽使得作业整体完成时间略有增加，但解决了原有算法最大的问题——负载不均衡，使得资源——尤其是优势资源得到充分利用，这对于以资源共享和最大利用为主要目的的云计算是非常重要的。

4 实验验证

为了评估提出的调度算法的性能，使用云计算仿真软件CloudSim采用离散事件模拟了云计算实验环境，主要来验证：①所提算法适用于云计算环境；②实现原始 Min－Min调度算法和改进算法的性能比较。

通过以下4个指标评估算法性能：①任务响应时间RT（response time），指从任务进入云计算系统起到该任务完成这段时间，定义为任务的等待时间与完成时间的和；②任务总体完成时间，即所有任务总的完成时间，是从第一个任务进入云计算系统到最后一个任务完成这段时间；③速度下降比S（slowdown），表示任务在云计算环境中执行与在单一站点中执行时的速度下降率，定义为任务响应时间与实际完成时间的比值；④系统资源利用率 （Ui），表示资源的忙闲程度，它也是云计算环境下任务调度比较好的一个指标，因为云计算的目的主要在于资源的有效共享和最大利用。

在仿真的云计算数据计算密集型实验系统中，实现了本文算法和原始的Min－Min算法，该系统中有500个计算节点和300个数据源，其中每个计算节点的处理能力不同，数据源与不同计算节点间的传输速率随机产生，范围是100－250kbps。实验中共采用3组任务，任务数分别为1000、2000和3000。任务的进入时间和执行时间也随机产生，范围是1－205s。任务也是随机进入仿真实验系统的，任务在数据源中的存储量随机产生，范围是200－10000KB。另外计算节点只能接收处理能力范围内的任务。实验仿真结果如图2所示。

图2 两种算法的仿真实验结果

从图2可以看出，改进算法在任务平均响应时间方面比原始Min－Min算法有了明显的提高，如在任务数量为3000时，平均任务响应时间为3.5s，比 Min－Min算法减少了约1.5s；在不同任务数量的情况下改进算法得到的总任务完成时间与原始Min－Min算法相差无几，特别是在任务数量比较多的情况下，这种差距更小；改进算法的任务平均速度下降比比原始的 Min－Min算法提高了15%左右；4个指标中改进算法的整个系统的利用率方面的表现最好，比Min－Min算法提高了56%左右。从实验结果可以看出，改进算法更适合在本地执行的任务，从而得到更小的平均任务响应时间、平均速度下降比和更高的系统利用率。当任务数量增加时，改进算法仍然得到较小的任务总体完成时间，这表明该方法非常适用于云计算这种数据计算密集型服务环境。

5 结束语

原始Min－Min算法中的负载不均衡现象会严重影响以资源共享和追求资源最大利用为目的的云计算系统的性能。同时考虑云的使用付费问题，故本文算法将缩短云计算的使用时间 （包括响应时间和完成时间）、平衡负载和充分利用优势资源作为主要目的。根据资源CPU个数h及处理能力P、磁盘容量C和资源所在的网络带宽B等3个参数计算资源的可见度，并据此对资源进行分类，计算出分类等级，通过计算资源等级与作业在资源上的预期执行时间的乘积，该乘积值最小的即为最适合的资源－任务对。为验证RCMM调度算法和原始Min－Min算法是否适合云计算环境，利用云仿真软件模拟了云计算环境，采用RT、任务总体完成时间、S和Ui等指标比较两算法的优劣。实验结果表明，RCMM算法除在任务总体完成时间方面表现稍逊于原始算法外，在RT、S和Ui的表现均优于原始的 Min－Min算法，特别是在系统利用率方面的表现尤为出色，这对于云计算这种以追求资源共享和最大限度利用资源的系统来说是十分重要的。虽然任务总体完成时间方面稍逊于原始算法，但这种差距随着任务量的增多而缩小，说明该算法非常适合云计算中数据密集型服务调度的。

本文研究主要针对云计算中数据密集型服务调度，至于云计算中交互密集型网络处理服务调度，还有待进一步研究。

［1］WANG Jiajun，LU Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion［J］.Computer Engineering ＆ Design，2010，31 （20）：4404－4409（in Chinese）.［王佳隽，吕智慧，吴杰，等.云计算技术发展分析及其应用探讨 ［J］.计算机工程与设计，2010，31（20）：4404－4409.］

［2］FANG Bingyi，ZHANG Yunyong，CHENG Ying.Analysis in the present and developing status of cloud computing ［J］.Telecommunication Science，2010，55 （S1）：1－6 （in Chinese）.［房秉毅，张云勇，程莹.云计算国内外发展现状分析［J］.电信科学，2010，55 （S1）：1－6.］

［3］Francesco Maria Aymerich，Gianni Fenu，Simone Surcis.An approach to a cloud computing network ［C］.First International Conference on the Applications of Digital Information and Web Technologies，2008：113－118.

［4］Ahson S，Ilyas M.Cloud computing and software services［M］.Florida，USA：CRC Press，2009.

［5］TANG Xiaochun，LIU Jian.Better allocation of meta－zone in cloud computing environment ［J］.Computer Engineering and Applications，2010，46 （34）：237－241 （in Chinese）. ［汤小春，刘健.基于元区间的云计算基础设施服务的资源分配算法研究 ［J］.计算机工程与应用，2010，46 （34）：237－241.］

［6］Foster I，Zhao Yong，Raicu I，et al.Cloud computing and grid computing 360degree compared ［C］.Proceedings of the Grid Computing Environments Workshop.Washington，DC：IEEE Computer Society，2008：1－10.

［7］Caron E，Desprez F，Loureiro D，et al.Cloud computing resource management through a grid middleware：A case study with DIET and eucalyptus［C］.Bangalore，India：IEEE International Conference on Cloud Computing，2009.

［8］LI Jianfeng，PENG Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing environment ［J］.Journal of Computer Applications，2011，31 （1）：184－186 （in Chinese）.［李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法 ［J］.计算机应用，2011，31 （1）：184－186.］

［9］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing ［J］.Computer Journal，2010，33 （10）：1859－1871 （in Chinese）. ［田冠华，孟丹，詹剑锋.云计算环境下基于失效规则的资源动态提供策略 ［J］.计算机学报，2010，33 （10）：1859－1871.］

［10］GAO Hongqing，XING Ying.Research on cloud resource management model based on economics ［J］.Computer Engineering ＆ Design，2010，31 （19）：4139－4142 （in Chinese）.［高宏卿，邢颖.基于经济学的云资源管理模型研究［J］.计算机工程与设计，2010，31 （19）：4139－4142.］

［11］Kimj S，Nam B，Marsh M，et al.Creating a robust desktop

grid using peer to peer services ［EB／OL］. ［2009－10－16］.

ftp：／／ftp.cs.umd.edu／pub／hpsl／papers／papers－pdf／ngs07.pdf.［12］Blythe J，Jain S，Declman E，et al.Task scheduling strategies for workflow－based applications in grids ［EB／OL］.http：／／grid.cs.tsinghua.edu.cn，2005.

［13］SUN Ruifeng，ZHAO Zhengwen.Resource scheduling strategy based on cloud computing ［J］.Aeronautical Computing Technique，2010，40 （3）：103－105 （in Chinese）. ［孙瑞锋，赵政文.基于云计算的资源调度策略 ［J］.航空计算技术，2010，40 （3）：103－105.］

［14］WU Gaofeng，CAI Yuming，YANG Lin，et al.Scheduling algorithm of modified Min－Min based on QoS in grid ［J］.Micro Computer Information，2009，26 （9）：110－112 （in Chinese）.［吴高峰，蒋玉明，杨林，等.基于QoS改进的网格调度算法［J］.微计算机信息，2009，26 （9）：110－112.］

［15］DU Yuxia，LIU Fangai，GUO Lei.Research and improvement of Min－Min scheduling algorithm ［J］.Computer Engineering and Applications，2010，46 （24）：107－109 （in Chinese）. ［杜玉霞，刘方爱，郭磊.Min－Min调度算法的研究与改进 ［J］.计算机工程与应用，2010，46 （24）：107－109.］