胡鹏

（南京邮电大学电子与光学工程学院微电子学院，江苏 南京 210023）

云计算是通过互联网提供的动态可扩展虚拟化资源，按需提供方便可用的网络访问[1]。由于云计算系统的动态性和多样性，任务调度成为一个挑战性的问题[2]。文献[3]首先制定任务执行时间目标函数，然后引入改进粒子群优化算法来调度任务并增强负载均衡。文献[4]通过基于混沌惯性权重的随机选择对群居蜘蛛群体进行智能建模，使得总体完工时间最小化。文献[5]先构建云计算资源负载平衡优化的约束条件， 其次通过改进萤火虫算法优化资源搜索路径， 优化云服务器中虚拟机之间的任务负载平衡来缩短用户任务完成总时间。文献[6]以完成时间、成本以及最后期限违反率为目标函数， 将布谷鸟算法和粒子群优化组合来智能优化任务调度问题。文献[7] 提出了一种引入min-min 和max-min 算法生成初始化种群，选择任务完成时间和负载均衡作为双重适应度函数，提高初始化种群质量、算法可搜索性和收敛速度的改进遗传算法进行任务调度。文献[8]在遗传算法的变异操作中引入了一种改进的随机因子和惯性权重的增强型粒子群优化算法，通过增强粒子群优化算法中的当前最优解和全局最优解重构变异算子，增强遗传和粒子群优化算法具有更快的收敛速度而且不会陷入局部最优解。文献[9]利用布谷鸟搜索和引力搜索算法的优点，根据不同的评价指标，提升了算法的性能。文献[10]依据空间案投影分析计算了集群的负载均衡度，给出调度决策变量，依据任务的执行代价完成时限赋予任务不同优先级进行任务调度。

云任务调度下执行任务聚类有助于降低系统开销[11]。现有调度大多是对云计算环境的资源和任务进行聚类[12-15]，再进行任务和资源的分配调度。本文提出了一种基于类簇匹配的策略，利用模糊聚类算法，通过对云任务进行分类，对云计算资源进行聚类分簇，将任务队列与资源簇进行匹配，通过贪心策略将任务分配到对应的资源簇上进行调度。

1 相关工作

1.1 模糊聚类分析

聚类分析是把一个没有类别标记的样本按照某种准则划分为若干子集，使相似的样本尽可能归于一类，把不相似的样本划分到不同的类中。传统的硬聚类把每个待识别的对象严格的划分某类中，具有非此即彼的性质，而模糊聚类建立了样本对类别的不确定描述，更能客观的反应客观世界，从而成为聚类分析的主流。

模糊C 均值（Fuzzy C-means）算法简称FCM 算法，是一种基于目标函数的模糊聚类算法，主要是用于数据的聚类分析。相较于k-means 的硬聚类，模糊c 提供了更加灵活的聚类结果。大部分情况下，数据集中的对象不能划分成为明显分离的簇，指派一个对象到一个特定的簇有些生硬，也可能会出错。因此对每个对象和每个簇赋予一个权值，指明对象属于该簇的程度。虽然基于概率的方法也可以给出这样的权值，但是有时候我们很难确定一个合适的统计模型，因此使用具有自然地、非概率特性的模糊c 均值就是一个比较好的选择。

FCM算法流程图如图1 所示。

图1 FCM 算法流程图

因此，给定一个数据样本集合为T={ T1，T2，T3，…Tn}，再通过FCM 聚类算法分析之后，得到了样本类划分为C={ C1，C2，C3，…Ck}，目标函数J 如式1 所示：

目标函数是由样本的隶属度uij与该样本到各个类中心的欧氏距离组成，m 是一个隶属度因子，实质是一个刻画模糊化程度的参数，最佳取值范围在[1.5，2.5]，大部分情况下取2。式（2）为约束条件，表示一个样本属于所有类的隶属度和要为1。因此本质上就是要求得最小的目标函数值，目标函数值越小，表示簇内相似度越高，因此FCM就是不断迭代求最优J 的过程。

1.2 贪心策略

贪心算法（又称贪婪算法）是在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体的最优解上加以考虑，它所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

2 基于模糊聚类的任务调度

2.1 问题建模

假定用户所提交的任务集T 中包含有n 个任务，这n 个任务相互独立大小不同，即T = {T1，T2，T3，…，Tn}，第j 个任务又可以详细描述为Tj= {tid，tlen，tPe，tcomp，tmem，tbw}，其中，tid是任务所属的编号，tlen是任务的长度，tPe是任务运行所需要的内核数，tcomp是任务执行时需要的计算能力，tmem是任务执行时所需要的内存量，tbw是任务运行时所需要的带宽，其中tcomp也可以根据以下公式计算得到：tcomp= tlen/ tPe。

云环境下的资源为虚拟机资源。因此假定一个资源集合中有m 个虚拟机资源，即VM = {VM1，VM2，VM3，…VMm}，且这些资源性能不同，而第i 个资源又可以详细描述为VMi= {Vmid，Vmcpu，Vmmips，Vmcomp，Vmmem，Vmbw}，这里的Vmid指的是虚拟机所属的编号，Vmcpu是该资源的CPU 数目，Vmmips是该虚拟机资源每秒的指令执行能力，Vmcomp是该资源的计算能力，Vmmem是该资源的存储能力，Vmbw是该资源的带宽能力。虚拟机资源的计算能力可由下式得到：Vmcomp=VmcpuVmmips。

ETC（i，j）矩阵所代表的是各个任务分别在各个虚拟机上的完成时间，ETCij指的是任务i 在虚拟机j 上执行需要的完成时间，它由任务的执行时间ECTij加上任务的等待时间wij得到：ETCij=ECTij+wij，最后用来计算任务执行总时间。

2.2 聚类分析

本文采用模糊FCM 聚类算法对任务集和资源集进行聚类划分，根据公式（1）目标函数可以简单按照如下步骤进行划分：

步骤1 对于n 个任务，以它们的需求属性tcomp，tmem，tbw建立一个初始的样本矩阵Tn×3，tij为矩阵中的一个元素，代表任务i的第j 维需求。

步骤2 对步骤1 中的矩阵Tn×3根据式（3）进行标准化，再利用式（4）压缩数据到[0，1]之间。

tj代表的是任务在第j 维需求的均值，Sj代表的是各任务在第j 维需求的标准差，t′jmin和t′jmax分别是t′1j，t′2j， …t′nj中的最小值和最大值。

步骤3 设定参数包括类别为3 类、迭代最大次数、目标函数阈值以及隶属度因子m=2，初始化隶属度矩阵U。

步骤4 根据式（5）分别计算3 个聚类中心ci。

步骤5 根据式（1）计算类内各节点与聚类中心的目标函数值，若小于所给阈值或者相较于上次的目标函数值的变化量小于所给阈值，或者达到迭代次数，则算法停止，否则继续执行下一步。

步骤6 根据式（6）重新计算隶属度U，再返回到步骤4 重复执行。

经过此类模糊聚类分析，可将所提交任务集划分为三个任务类，分别为计算需求型（CompClass）、内存需求型（MemClass）以及带宽需求型（BwClass）。

对主机资源集群来说，也采用聚类分析的方法来对虚拟机资源进行分类，在步骤1 中，以m 个资源的属性值Vmcomp，Vmmem以及Vmbw来建立初始样本矩阵Rm×3，rij代表了第i 个资源的第j 维属性性能，其他的步骤原理同对任务聚类分析一样，最终得到了三个资源簇分别为计算型资源簇（CompCluster）、内存型资源簇（MemCluster）以及带宽型资源簇（BwCluster）。

2.3 贪心调度分配

根据贪心策略将三个任务类分别分配到对应的资源簇上执行，以计算需求型任务匹配计算型资源簇为例，具体的执行步骤如下：

步骤1 判断任务集合是否为空，是则跳至步骤5，否则进行步骤2。

步骤2 按照式（7）和式（8）对任务队列的计算需求度以及簇内资源的综合能力进行排序。

步骤3 将需求最大的任务分配到综合能力最好的虚拟机资源上运行。

步骤4 返回至步骤2，更新虚拟机资源的综合性能排序队列，并且不断更新任务和虚拟机之间的映射关系。

步骤5 调度分配结束。

按照以上步骤，对内存需求型任务和带宽需求型任务也采用同样的贪心策略进行任务调度分配，直到所有的任务均执行结束，将结果反馈给用户。

3 实验仿真与分析

3.1 实验环境

本文的实验环境采用win10 操作系统，开发工具为IDEA，利用云仿真平台CloudSim[16]进行验证仿真，与Min-min 和Max-min 算法的执行结果从任务的总体完成时间、平均资源利用率进行了对比。具体环境如下：

任务参数配置：任务长度设置为[500，3000]，任务内存需求范围[512，2048]，任务带宽需求范围[1000，3000]，任务计算能力需求范围[500，3000]。

虚拟机资源参数配置：CPU 的个数取值{1，2，4}，虚拟机的处理速度[500，1000]，内存范围[512，2048]，带宽范围[500，3000]。

3.2 评价指标

任务完成总时间Makespan 是从第一个任务开始执行到最后一个任务执行结束所需要的时间，可以通过公式（9）虚拟机资源的工作时间来得到：

上述式中，l 为虚拟机j 上所分配的任务总数，m 为虚拟机资源总数，主要的评价指标由这两个组成。

3.3 仿真结果分析

在云平台上，随机生成了50，100，200，500，1000，2000 个任务，分别将本文的算法与Min-min 算法和Max-min 算法对比，比较三种算法情况下的任务总完成时间以及虚拟机资源的平均利用率。

从图2 和图3 的结果来看，本文算法相较Min-min 和Max-min 两种算法有着较快的任务执行速度，这是因为Min-min 和Max-min 算法都是基于任务最早的完成时间的大小来进行分配的，没有考虑到虚拟机的资源情况和负载均衡能力，而本文算法针对虚拟机的资源综合能力进行贪心策略的分配，可以让每个任务都能得到最合适的资源去运行，因此在执行速度上有着很大程度的提高。其次当任务量较多时，本文算法资源利用率一直在50%的水平以上，最高达到了70%，而Min-min 算法和Max-min 算法的资源利用率相比于本文算法一直处于较低水平。

图2 任务Makespan 比较结果

图3 算法AU 比较结果

综上分析可知本文算法在云计算环境下，不仅可以提高任务的完成效率，还可以在一定程度上提高云计算的资源利用率，提高云计算系统的整体性能。

4 结论

本文针对云计算环境下的任务调度问题进行分析，提出了一种基于模糊聚类和贪心策略分配的任务调度算法，通过对任务集和虚拟机资源进行聚类分析和类簇匹配，缩小了任务选择运行资源的范围，提高算法运行效率，再通过贪心策略调度机制，将任务具体分配到虚拟机资源上进行调度执行。最后通过CloudSim 平台仿真结果可知，一方面可以大大的提高云环境下任务的执行效率，缩短执行时间，另一方面也提高了虚拟机资源的利用率，下一步将对虚拟机集群的负载均衡度作进一步优化的研究，以适应高速发展的云计算体系。