摘要：云计算中任务调度算法的好坏直接影响云计算系统整体性能，也影响着云计算系统处理用户提交的任务的能力。本文归纳了云计算调度的特点和性能指标，总结了云计算中的任务调度算法，分析了云计算任务调度算法的研究现状及其进展。最后讨论了现有任务调度策略存在的问题，为云调度研究指明了方向和思路。
关键词：云计算；任务调度；遗传算法；蚁群算法
前言
云计算是一种基于互联网的新的服务模式，这种模式按使用量付费，提供可用的、便捷的、按需的网络访问，它将用户需求的计算任务分布在由大量计算机构成的数据中心，数据中心采用虚拟化技术，把各种软硬件资源抽象为虚拟化资源，再通过资源调度技术使各种应用能够根据需要获取计算能力、存储空间和信息服务。
在云计算环境中，一个大规模计算任务需要进行分布式并行处理，系统首先将逻辑上完整的一个大任务切分成多个子任务，然后根据任务的相应信息采取合适的调度算法，在不同的资源节点上运行这些子任务，所有的子任务处理完后进行汇总，最后将结果传给用户。云计算任务调度的目的是给需要的用户分配不同的资源，在某一特定的云环境下，依据某一种规则使用资源，在不同的用户之间平衡和调整资源，在满足用户需求的前提下，使得任务完成时间尽量小，且资源利用率尽量高。调度最终要实现时间跨度、服务质量、负载均衡、经济原则最优等目标。云计算任务调度是云计算研究中的重点和难点。任务调度算法的优劣会影响到云计算系统处理任务的能力。近几年，研究者针对云环境下的资源调度做了很多研究，主要体现在以提高云计算数据中资源利用率为宗旨的资源管理与调度、以降低云计算数据中心的能耗为目标的资源分配与调度、经济学的云资源管理模型研究等方面。
本文综述了云环境下的任务调度算法，分析了近几年来典型的云计算任务调度算法的发展趋势，为相关领域的研究人员提供参考。
1、网格任务调度与云计算任务调度的比较
在网格计算和云计算中，虽然系统资源都是以数据池的形式呈现给用户，但它们之间的区别是网格用户的任务是通过实际的物理资源来执行，而云计算环境下的用户任务是通过逻辑意义上的虚拟资源来执行。对于以上两种计算方式，都是由用户将任务提交给计算中心，系统通过对任务的需求进行分析，然后来寻找合适的资源节点执行，此时的用户并不关心执行任务的是哪个节点。网格系统通过用户预先设定的任务并行执行算法，并结合自己的调度系统使用户任务实现跨物理节点并行执行[1]，云计算任务调度通常情况不会跨虚拟机并行调度。尽管云计算是在网格计算、分布式计算及并行计算的基础上发展起来的，但是云环境比较复杂，任务呈现多样性，而且是以商业服务作为宗旨。云计算任务调度策略不能照搬传统调度策略来满足用户提出的各种任务要求，必须考虑怎样在高效任务调度与资源分配同时提高经济效益、资源利用率以及用户体验等各方面的因素。可靠的云服务和各层次的用户公平使用资源的机会是云计算调度策略必须考虑的问题，此外还需要有一个调度策略来提供系统可以使用的资源，以便满足多样化的用户需求。因此虚拟化技术在云计算中的广泛应用、中间层与资源节点以及用户与中间层之间的关系发生了很大变化，云计算应该研究新的任务调度策略来满足用户的要求。
2、云计算任务调度算法
2.1 传统任务调度算法
传统任务调度算法主要有Min-Min算法、Max-Min算法、Sufferage算法等。Min-Min算法是将任务分配给执行效率最高的资源，这种算法容易导致负载大多集中在能力较强的资源节点上，使得资源负载极度不均衡。Max-Min算法首先要计算每一个任务在任一个可用资源上的最早完成时间，然后将具有最早执行时间的计算资源分配给最大的任务，随后更新资源的最早可用时间和任务集，直到全部任务调度完成。Min-Min算法是将小的任务分配到执行效率高的资源上进行，有很好的负载均衡性。当可执行任务的资源发生变化时，Max-Min算法的优势就不存在。Sufferage算法是以任务最小完成时间为调度目标。Sufferage算法的缺点是负载的平衡性能不高。基于传统调度算法进行改进的研究已有很多。王文豪[2]为了解决Min-Min调度算法中存在的负载不平衡问题，改善系统负载的均衡性，提出基于Min-Min极限下压算法的负载模糊分类及局部重调度的算法。引入模糊分类的思想，根据各节点的负载大小，将节点分成三种类型：重负载、中负载和轻负载；对负载较重和较轻的节点进行重新调度，通过使用Min-Min极限下压算法来压缩资源节点完成任务的时间，改善算法的负载失衡问题。何丽[3] 提出将优化能耗的调度方法应用到min-min任务调度算法中，它通过系统对任务结束时间的要求，先选取任务队列中的最小任务，然后分配到所需能耗最小的服务器上执行，结果表明能够较好地满足任务结束时间的要求，同时降低了云计算系统的总能耗。周舟[4]提出一种Min-Max算法。该算法对时间贪心，将小任务和大任务“捆绑”在一起执行调度，从而有效地解决了负载不均衡的问题。
2.2 基于智能启发式任务调度算法
传统调度算法一般都把效率作为追求的首要目标，且由于调度算法普遍适应性不强，局限性较大，如：最小完成时间的任务调度方法，虽具有较好的完成效率，但是系统负载均衡达不到理想要求，计算效率高的虚拟机资源长期超负荷运行；最终还不一定能满足用户任务的服务质量要求。因此，基于智能启发式任务调度算法有了很快的发展，主要有遗传算法、蚁群优化算法、粒子群优化算法以及模拟退火算法等，现阶段这些智能启发式算法经过许多学者的改进已经广泛应用到云计算系统中，它们通过迭代对解进行了优化，最终得到近似解。
（1）遗传算法
遗传算法的原理是生物界中的自然选择学说和种群遗传学，它是一种利用繁衍、监测和评价来进行迭代、进化的搜索方法，具有求解问题的高度并行性及很强的全局性空间搜索能力。在搜索的过程中它能自动获取相关搜索空间的知识，并能自适应地控制搜索的过程从而得到满意解。但遗传算法也有不足之处：收敛速度慢、易于陷入局部最优的问题[5]。李韪韬等[5]提出用N进制的浮点数来表示每个基因值，然后将其分为两部分及整数部分和小数部分， 重新编码组成染色体的新的基因值，提高算法在早期的全局搜索能力，避免陷入局部极值。张爱科[6]结合遗传算法的优点，提出一种公平均衡遗传调度算法FBGSA。该算法充分考虑到任务调度过程中资源和任务的公平性问题，以及资源的负载均衡等因素。
（2）蚁群算法和粒子群优化算
蚁群算法是一种用来寻求最优化路径的群体智能算法。由于蚁群算法的并发性和可扩展性，所以其很适用于云计算环境下的资源调度。粒子群优化算法是根据交互粒子群之间的信息来寻找全局最优解的算法[7]。它的特点是原理简单、参数设置较少，所以与其他多数智能算法相比，粒子群优化算法已广泛应用于神经网络、函数优化、智能控制等领域。孟凡超[8]提出了一种基于蚁群优化算法的资源调度算法，主要针对云数据中心虚拟机分配物理机时，存在负载不均衡的问题。通过对问题场景进行分析，提出了数据中心负载不均衡度，以及物理机与虚拟机之间不匹配度的概念，并给出了问题的形式化描述。在蚁群算法选择概率规则中参考了用户对虚拟机资源的需求，尽量避免对相同类型虚拟机部署在一台物理机上，同时对信息素的初始化、信息素的更新进行了改进。文晓棠[9]通过对蚁群算法和粒子群算法的理论进行了研究，根据这两种算法本身存在的缺点，对算法进行了一些改进。通过取长补短对两种算法进行融合改进后的算法，比之前基于一种算法的调度策略有更好的执行时间和效率。
王登科[10]将粒子群优化算法中的快速收敛和蚁群算法的寻优能力相结合，提出了一种新的任务调度算法，该算法缩短了系统处理调度问题的时间，提高了云计算任务调度的效率。封良良[11]提出的任务调度算法在考虑总任务完成时间和任务平均完成时间的同时，也考虑了总任务完成成本，在传统粒子群优化算法的基础上，选取双适应度的原则实现最小执行时间的同时兼顾成本最小。
（3）模拟退火算法
模拟退火算法最早是在1953年由Metropolis等人在研究二维变相时发现的，1983年由kirkpatrick等成功地引入到组合优化领域中，从此模拟退火算法开始被大规模、广泛地应用于组合优化求解的问题中。模拟退火算法是一种可以广泛应用于实际工程中的全局最优算法，也是局部搜索算法的扩展。徐洁[12]针对现有的云计算任务调度算法提出一种双适应度遗传退火任务调度算法(DFG2A)，基于该任务调度算法的任务调度策略能够有效平衡用户对任务各项属性的需求，提高云计算平台的用户满意度。 张浩荣[13]提出一种融合蚁群算法和模拟退火算法的混合调度算法(ACOSA)，该算法以最小化调度时间为目标，引入了任务与资源的匹配因子和负载均衡度，先利用蚁群算法得到一组任务到资源的优化解，然后通过模拟退火算法对解进行路径的优化和信息素的更新。
3、存在的问题及展望
目前，许多学者对云计算资源调度的问题进行了大量的研究和改进，有了一定的研究成果，但在调度策略方面还存在许多问题，要想云计算能被更多的用户接受，有持续快速的发展，还需要对云计算的任务调度有更深入的研究。
1）既能满足用户的服务需求同时又能兼顾系统整体性能和经济成本方面还需深入研究。调度策略要注意到云计算面向服务的特点，满足用户的费用低廉的目的又能给用户提供实时性保证。
2）现阶段的云计算任务调度算法主要通过任务的响应时间、可靠性及成本等方面来考虑用户的QoS；而对于云计算服务提供商来说，主要是从如何降低能耗，减少花费，提高系统资源的利用效率等方面来考虑。如何才能让云服务提供商和用户双方达到互利共赢是一个有待解决的问题，在以后可以进行更加深入的研究。
3）加强云计算任务调度算法性能检测模型的研究，对于衡量云计算调度算法性能的模型很少，而且多是利用一些数学模型或是采用分布式系统中的任务调度模型的问题，迫切需要设计出合理的任务模型来检测云计算任务调度算法性能。
4、结束语
云计算任务调度问题是云计算系统的核心技术之一，是云计算应用的关键问题，好的任务调度策略，能够提高系统资源的利用率，平衡系统负载，提高云计算服务质量。本文介绍了云计算任务调度的概念以及其特点，并系统综述了云计算中几个比较常见的任务调度算法近年来的研究进展，最后对云计算任务调度中当前存在的问题进行了概括说明。
参考文献
[1] 罗红, 慕德俊,邓智群, 王晓东. 网格计算中任务调度研究综述. 计算机应用研究,2015,5:16-19.
[2] Zehua Zhang, Xuejie Zhang.A Load Balancing Mechanism Based on Ant Colow and Complex Network Theory in Open Cloud Computing Federation.2010 2nd Intern ational Conference on Industrial MechatroniCS and Automation.2010.
[3] 何丽, 饶俊, 赵富强. 一种基于能耗优化的云计算系统任务调度方法. 计算机工程与应 用，2013, 49(20):19-22,111.
[4] 周舟, 胡志刚. 云计算中融入贪心策略的调度算法研究. 小型微型计算机系统，2015, 36(5):1024-1027.
[5] 吴玫, 陆金桂. 遗传算法的研究进展综述. 机床与液压, 2008, 36:176-179.
[6] 张爱科, 谢翠兰. 基于公平性和负载均衡的云计算任务调度算法. 计算机应用与软件, 2015,32(2):268-271.
[7] 王洪涛. 粒子群优化算法的改进及应用：西安科技大学硕士学位论文，2011.
[8] 孟凡超, 张海洲, 初佃辉. 基于蚁群优化算法的云计算资源负载均衡研究. 华中科技大 学学报，2013,41:57-62.
[9] 文晓棠.云计算环境下基于蚁群粒子群优化算法的资源调度策略研究:江西师范大学硕 士学位论文，2013.
[10]王登科, 李忠. 基于粒子群优化与蚁群优化的云计算任务调度算法. 计算机应用与软件，2013,30(1):290-293.
[11]封良良, 张陶, 贾振红等.云计算环境下基于改进粒子群的任务调度算法.计算机工程，2013(5)：183-186.
[12]徐洁, 朱健琛, 鲁珂基于双适应度遗传退火的云任务调度算法. 电子科技大学学报, 2013,42(6):900-904.
[13]张浩荣, 陈平华, 熊建斌. 基于蚁群模拟退火算法的云环境任务调度. 广东工业大学学报, 2014,31(3):77-82.
作者简介：张艳敏，山西大学商务学院 讲师，硕士研究生，主要研究方向为云计算。