第一章 绪论
1.1 研究背景与意义
云计算是互联网时代衍变的产物，它的到来为人们的生活带来极大便利的同时，也使互联网的发展面临了很多全新的挑战[1-3]。如今，一些大型互联网公司纷纷建立自己的云服务平台通过网络的形式为互联网使用者提供各种不同的云服务。这些服务的提供对人们的生活方式有着巨大的改变。
进入 21 世纪以后，信息技术的快速发展使得互联网的规模逐日扩大，网络用户数量也急剧增长。在这种背景下，如何储存和处理网络用户产生的海量的信息数据成为互联网发展过程中亟待解决的重大难题。为了解决这一难题，一些科研学者提出：在互联网中使用虚拟化技术、并行计算技术、网格技术等将各地异构的计算机资源（如存储资源、计算资源、网络资源等）通过网络技术连接起来用以高效的存储和处理互联网上的海量的数据[4-6]。这一理论提出以后引起了社会各界高度重视，很多顶尖的互联网公司纷纷投入了对云计算技术的研究和发展。这使得云计算在很短的时间内发展成为当前最火热的研究领域。
然而，随着云计算技术的迅速普及以及云服务领域的不断扩大，云数据中心的计算资源与任务也随之扩大，这给云计算的发展带来一个新的问题，即云计算中的任务调度问题。该问题的实质就是如何将用户提交的任务高效的分配到云环境中的各个资源上执行，使得在满足 QoS[7]需求的情况下实现系统资源的高效利用和负载均衡。因为任务调度算法结果的好坏直接影响云计算环境中资源的整体利用效率以及用户对云服务使用的认可度，所以云环境中任务调度问题已经被越来越多的人所重视。
.........................
1.2 国内外任务调度算法研究现状
目前，国内外研究云计算任务调度的学者数不胜数，他们提出的任务调度算法也各有不同。这些算法大致可分为传统的任务调度算、智能优化算法及其改进算法。
（一）Hadoop 中任务调度算法
Hadoop 是一种能够存储和处理海量数据的分布式软件框架，在云环境中扮演着非常重要的角色。在 Hadoop 生态系统中，HDFS（Hadoop Distributed File System）用于存储集群环境中的海量数据[20,21]。而 MapReduce 则用于 hdfs 上海量数据的处理和计算，这种计算模式通过 Map（映射）和 Reduce（规约）的方式对大规模数据集进行运算，并且在计算时采用并行运算的方式以提高运算速率。YARN 则是新版的 Hadoop 中新增的资源管理组件，它主要负责将云计算上的任务合理的分配到集群上的资源去执行[22,23]。
然而，在不同的应用场景需要的任务调度策略也有所不同，所以我们很难找到一个能符合所有应有场景的调度策略。为此，Hadoop 开发团队在 YARN 中封装了三种不同的任务调度算法以适应不同环境下的任务调度需求。我们可根据需要通过修改配置文件的方式选取不同的任务调度算法。
FIFO 算法，即先进先出算法。当 Hadoop 集群没有修改配置文件指定某一特点的调度策略时，集群默认采用调用这种算法。该算法原理很简单：调度器首先在系统中设置一个作业队列，然后根据被提交的作业的先后顺序，依次将任务插入到作业队列中去。当要执行一个作业时，就从作业队列的队首取出并执行。但是当某一个作业很大时且先进入作业队列中，那么它在执行的期间就会长时间占用系统中的资源，使得队列中的小作业得不到及时的处理。这种调度策不利于队列中小作业的运行也没有考虑任务的优先级。
Capacity Schedule 算法。该算法可以有效的管理集群中的内存资源，具有多用户弹性、安全可靠、资源感知等特点。
Fair Scheduler 算法[24]。该算法给用户提交的每个应用设置一个作业池用来组织由应用分割成的作业。并且所有应用共享集群中的资源，当集群中只有一个应用的时候，由该应用对应的作业可使用集群中全部的资源。当集群中有多个应用的时候，这些应用平分系统中的资源，然后每个应用中的作业可占用应用对应的全部资源。另外，这种调度策略还可以适用于优先级，优先级可作为权重的调节因素来决定每一应用得到的资源。默认情况下作业池中的作业也是按照FIFO 的调度策略分配到对应的资源上。
...............................
第二章 相关理论概述
2.1 云计算概述
2.1.1 云计算原理和特点
云计算是互联网时代发展的必然产物，同时也是互联网的一种新型的使用模式。这种应用模式主要通过虚拟化技术和计算机网络技术将大量的、分散的、异构的计算机资源组合成一个巨型的资源池。云用户可以通过租赁的方式使用资源中的各种计算机资源[36]。云计算系统有一下几个重要的特点。
超大规模。一般情况下，云计算系统是由第三方供应商研发和推进的。该系统是利用成熟的网络技术将分布在各地异构的、大量的计算资源连接起来，构成一个庞大的计算机资源池，用以处理用户海量的云服务请求。
安全可靠。由云供应商提供的服务，均会采取必要的保护措施，使得用户在使用这些服务时，不必担心因为数据的丢失和病毒的入侵带来的麻烦[37]。
价格低廉。用户只需支付少量的费用就能获取和使用云环境中的强大的计算能力和资源。云计算数据中心可根据用户的实际需求为其提供相应的服务，从而让互联网上的 IT 资源的得以充分的利用。
2.1.2 云计算体系结构
由于不同厂家提供的云服务类型可能也不同，其云计算的构建方案也各有差异，造成了各种厂家的云计算体系结构也有所不同，综合分析了当前的几个主流的云计算研发公司的方案。整理得到了图如 2-1 所示的云计算架构示意图。
..........................
2.2 云计算任务调度问题概述
2.2.1 任务调度模型
在云计算任务调度的过程中，每个用户向云计算数据中心提交了若干个相互独立的任务，这些任务首先云计算任务调度中心被分配到由各个主机的虚拟机群上去执行。最后，虚拟机将执行的结果通过网络传递给各个用户，其模型如图2-2 所示：
.........................
3.1 引言 .................................. 17
3.2 粒子编码与解码 ............................... 17
3.3 基于粒子群算法的改进算法 .......................... 18
第四章 实验验证及结果分析 ...................... 28
4.1 云计算仿真平台 CloudSim .............................. 28
4.1.1 CloudSim 的简介 .............................. 28
4.1.2 CloudSim 的体系结构 ........................... 28
第五章 总结与展望 ....................................... 38
5.1 总结 ............................ 38
5.2 展望 .............................. 38
第四章 实验验证及结果分析
4.1 云计算仿真平台 CloudSim
4.1.1 CloudSim 的简介
在 2009 年，
澳大利亚墨尔本大学的网格实验室发布了一款功能强大的云计算仿真软件 CloudSim[38][39] [40]。CloudSim 是一种跨平台软件软件，它能在 Linux、Windows 以及 macOS 等多种不同的操作系统上运行。在 CloudSim 上我们可以对云计算中的任务调度过程进行模拟实验，
研究云计算中任务调度原理。
4.1.2 CloudSim 的体系结构
云计算的仿真平台 CloudSim 的体系结构如图 4-1 所示
...........................
第五章 总结与展望
5.1 总结
在解决任务调度问题时，粒子群优化算法所求得的结果对初始种群质量具有较强的依赖性，并且算法在搜索最优解时极易陷入局部最优。针对这一些缺点本文 提 出 了 融 入 反 向 学 习 和 试 探 感 知 搜 索策 略 的 粒 子 群 算 法 的 改 进 算 法OBL-TP-PSO，并在 CloudSim 平台上进行了云环境下任务调度的模拟实验，实验结果表明：OBL-TP-PSO 算法得到的任务分配方案比 Min-Min 算法，Max-Min 算法以及 PSO 算法求得任务调度方案对应的任务总的执行时间要小；OBL-TP-PSO 算法比 PSO 算法求得的解更加精确且收敛速度更快。此外，在负载均衡度方面，本文提出的算法比 Min-Min 和 Max-Min 算法更好。
OBL-TP-PSO 算法得到了较好的结果，但是在解空间搜索任务最优解时，该算法只选择了任务总的执行时间最小，作为度量解空间种群中粒子位置（任务调度方案）是否优劣的标准。实际生产中，评价任务结果的优劣也有很多其他的因素，例如：用户使用云中资源时产生的花费，用户对云服务的满意程度，用户提交的任务对资源的特殊需求（如安全性、网络带宽、cpu 处理能力等）以及在云环境中任务调度需资源异同和系统能耗等。设计一个更合理的算法是以适应更复杂的应用环境是我们研究的重点。
参考文献（略）