基于云计算的调度算法

周捷 汪烊

摘要    文章从云计算的优势分析入手，论述了基于云计算的调度算法。期望通过本文的研究能够对高新能算法在云计算系统任务调度中的合理运用有所帮助。

【关键词】云计算 任务 调度算法

1 云计算的优势

云计算是由全球最大的搜索引擎公司-谷歌（Google），于2006年全球搜索引擎会议上提出的一种计算方法，其以效率高、成本低等特点，在各个领域中得到越来越广泛的应用，它的出现使计算科学领域发生了巨大改变。云计算的优势具体体现在如下几个方面：

1.1 低廉的成本

目前，大部分企事业单位在IT方面的主要支出包括以下费用：设备成本、能耗及管理费用等。云计算不需要在设备上投入较多的资金，运维费用相对较少，由此可以为企业节省大量的资金。同时，云计算的成本优势与规模成正比，即企业应用的云计算规模越大，成本优势就明显，资金缺乏的企业可以利用云计算进行项目开发和研究。

1.2 对设备的要求不高

云计算用户的应用全部都是在云数据中心运行，只要用户设备能够接入网络，便可对云计算进行使用。因此，只要基本的设备配置即可满足使用需要。

1.3 数据可靠性高

在云计算下，用户的数据全都存储在云端，当用户设备发生故障时，这些数据并不会丢失或是损坏，数据的安全性和可靠性得到有效保证。正是因为云计算所具备的上述优势，使其成为大多数用户的首选计算方式。

2 基于云计算的调度算法

云计算系统具有异常强大的功能，可以为用户提供与数据挖掘、数据处理等方面有关的服务。通常情况下，云计算系统会借助分布式处理技术，对任务进行分割，随后利用调度算法将各个子任务映射到虚拟资源节点上，调度策略是这一过程实现的前提和基础，调度算法则是获得调度策略的关键。采用最优的调度算法，可以得到最佳的调度策略，从而使云计算系统保持高效运行，满足不同用户的使用需求。

在云计算系统中，可将任务分为两种情况，一种是独立任务，另一种是关联任务。不同的任务类型，需要采用相应的调度算法。下面对此进行具体分析。

2.1 独立任务调度算法

对于云计算系统中的独立任务调度而言，可将其归入到NP-完全问题的范畴，此类问题可以运用传统的调度算法和启发式算法。

2.1.1 传统算法

在传统调度算法中，比较常用的有以下几种：

（1）Max-Min算法。这种算法的基本原理是将小任务优先映射到速度最快的虚拟机上。在该算法下，调度器会对每个任务在不同虚拟机上运行的执行时间进行计算，根据计算结果，找出执行时间最少的任务，并将该任务调度至速度最快的虚拟机上。按照这样的顺序，直至全部任务调度完毕为止。这种算法最为突出的优点是可以确保任务处理时间最短，但需要指出的是，部分虚拟机在该算法下可能会一直处于空闲状态，不利于资源的有效利用。

（2）回填算法。这是一种能够大幅度提升虚拟机利用效率的算法，在该算法下，系统会为等待隊列当中相对较小的任务预留出一定的资源，并对预约任务队列的空隙加以合理利用，从而将这部分任务回填至前面，可以使任务的平均等待时间有所减少。回填算法最为突出的特点在于复杂程度相对较低，整个过程易于实现，并且具有较为明显的调度优势。

2.1.2 启发式算法

在启发式算法中，比较常用的有以下几种：

（1）蚁群算法。这种算法归属于概率型算法的范畴，可以借助该算法寻找优化路径，其最为基本的特征是分布计算和启发式搜索。蚁群算法是以蚂蚁的行走路径，对待优化问题的可行解进行表示，整个蚁群的所有路径构成了优化问题的解空间。可将该算法在任务分配到虚拟机的场景中进行应用，虽然通过蚁群算法可以获得最优解，但若是系统的规模过大，则会导致算法的效率降低。所以在大规模的系统中进行任务调度时，不推荐使用这种算法。

（2）遗传算法。该算法简称GA，其理论基础是达尔文的生物进化论，通过对自然进化过程的模拟，来搜索最优解。GA在对多个个体的价值进行评估的过程中，主要是借助适应度函数，通过对初始种群的交叉以及变异操作，使最终结果满足终止条件的要求。该算法的优势体现在并行处理能力强，可对解空间中的多个解进行同时搜索等方面。

（3）粒子群算法。该算法简称PSO，归属于进化算法的范畴，其原理与模拟退火算法极为相似。PSO以随机解作为起点，通过不断地迭代寻找最优解，实践证明，PSO比遗传算法的规则更加简单，省去了交叉与变异过程，由此使其更容易实现，并且精度更高。

根据独立任务的特点，结合对上述调度算法的分析，可以采用传统算法中的回填算法或是启发式算法中的粒子群算法，实现云计算系统独立任务最优调度的目标。

2.2 关联任务调度算法

在云计算系统中，关联任务可以分为静态和动态两种类型，前者的执行与通信成本均为已知，而后者的这些条件则全部都是未知数，所以必须在系统运行时，才能进行调度决策。由于动态调度必须在运行的过程中完成，所以调度算法大多都是针对静态调度任务。常用的有以下几种：

2.2.1 基于表调度的算法

该算法包括两个阶段，在第一个阶段时，会对任务进行调度优先级划分，进而形成调度列表;在第二阶段时，会按照优先级将表中的任务分配到虚拟机上执行，直至全部任务调度完毕为止。

2.2.2 基于聚类的算法

该算法会以映射的方式，将任务映射到集群中，由于集群不会受到数量的限制，所以可承载海量的任务。然后集群中的任务进行聚类，迭代前先合并类似的集群，当两个任务被分配到同一个集群内时，可由一台虚拟机完成任务执行。

在这两种算法中，表调度的计算过程较为简单，并且其各方面性能都较为优异，所以可将之作为关联任务的主要调度算法。

3 结论

综上所述，随着云计算应用领域的不断拓宽，用户的使用需求随之发生了一定的变化。为对各种不同的任务进行高效调度，应当加大对云计算调度算法的研究力度，除对现有的算法进行逐步改进和完善之外，还应结合云计算的特点，开发一些新的调度算法，以此来推动云计算的持续发展。

参考文献

[1] 滕云.云计算下资源调度算法的节能研究[J].电脑知识与技术，2018（30）.

[2] 柳兴.移动云计算中的资源调度与节能问题研究[D].2015.

[3] 汪敏，汪正舟.实时服务框架设计于实现[J].指挥信息系统与技术，2017，8（02）：36-40.

[4] 苏淑霞.面向云计算的任务调度算法研究[J].安徽大学学报（自然科学版），2014，38（05）：24-30.