表3.6  DAG类主要变量定义表 16

表3.7  DAG类主要函数定义表 16

表3.8  WORKFLOW类主要变量定义表 18

表3.9  WORKFLOW类主要函数定义表 19

表4.1  基准测试应用程序生成的DAG结构表 21

表4.2  qsort应用程序调度结果 25

表4.3  表4.1中其他应用程序调度结果 26

表4.4  调节迭代次数IterNum的调度结果 27

表4.5  调节种群规模N的调度结果 28

1  引言

本章阐述了本课题的基本状况，如背景和相关现状等。同时，对本文工作的技术方案及其社会、经济影响做出介绍。

1.1  研究背景与意义

随着互联网技术的迅速发展，云计算已引起大量学术界和工业界学者的共同关注。云计算是能够将基础设施、平台和软件作为服务提供给用户的分布式计算模型[1]。云计算能够帮助用户应用程序在需要时在指定位置动态提供尽可能多的计算资源。为了实现规模化服务、有效提高系统效能，任务调度成为了云计算研究的热点之一。

云计算任务调度指的是在云环境中，将特定的资源依据一定的调度策略分配给不同的计算单元（Processing Element, PE）的过程[2]。高效的任务调度策略能够有效提升云计算系统的任务执行效率和系统整体效能。但是，由于传统的任务调度策略通常只是简单地依据某一评判准则决定任务的执行顺序，在当前日益增加的云计算规模和日益复杂的云计算环境下，已无法满足任务调度的性能需求。因此，本文旨在设计一种高效、可靠且符合云环境特点的任务调度算法以应对上述问题。

1.2  研究现状

针对于云计算的任务调度问题，长期以来学术界进行了大量的深入研究与探讨，并提出了基于不同策略的众多任务调度算法，总结如图1.1所示。

图1.1  云计算任务调度算法

如图中所示，最小完成时间(Minimum Completion Time, MCT)[3]、轮循调度算法(Round Robin, RR) [4]等属于传统算法。在当前的复杂云计算环境下，传统算法已经无法应对复杂工作流和各种先进的云计算架构。相应地，任务调度算法越来越多的采用启发式搜索的策略。常用的基于启发式思想的方法包括遗传算法(Genetic Algorithm, GA)[5]、粒子群算法(Particle Swarm Optimization, PSO) [6]、模拟退火算法(Simulated Annealing, SA)[7]、蛙跳算法(Shuffled Frogleaping Algorithm, SFLA) [8]、蚁群优化算法(Ant Colony Optimization, ACO) [9]等。这些算法在任务调度过程中搜寻最佳调度的效率较高，但也存在易于早熟的缺陷，导致搜寻到的调度结果陷入局部最优。

相关研究表明，大部分任务调度问题可以归结为多约束的NP难问题[10]。此类问题通常会导致较高的计算时间复杂度[11]。国内外的大量学者通过研究表明将PSO算法应用于云计算任务调度问题上，能够取得相对较好的效果。Pandey等将PSO算法应用于云环境中的启发式工作流调度，并且获得了比较理想的调度结果[12]。在此基础上，赵莉提出基于改进量子粒子群算法（Quantum-behaved Particle Swarm Optimization, QPSO）的云计算任务调度算法，在采用QPSO求解最佳调度的同时，对平均最佳位置进行随机变化，使得搜寻粒子尽可能避免陷入局部最优解[13]。此外，邬开俊等在任务调度过程中引入了粒子离散化思想，增强了粒子群优化算法的离散程度，从而获得了较高的云计算任务调度性能[14]。

1.3  总体技术方案及其社会影响

本课题的技术方案围绕任务调度算法展开。首先，通过调研对比常用的任务调度策略建立任务调度模型。然后，根据调度模型设计并实现一种快速有效的任务调度算法。所设计的算法能够应用于所建立的调度模型中以求解最佳调度方案。搜寻最佳调度的过程根据粒子群优化的思想实现。本课题的研究工作，为解决云计算任务调度问题提供了一种可行的解决方案，对今后的研究起到一定的指导意义。