引言
云计算具有海量计算资源、可弹性扩展、运维成本低等优势，这些巨大优势使得云计算被广泛应用于越来越多的大数据应用当中。
大数据应用需要快速地处理海量数据，而MapReduce可以并行地处理TB级别以上的大规模海量数据，是云计算大规模数据处理技术发展历史上的奠基石。
而选择合适的资源调度算法进行合理有效的资源分配是MapReduce实现并行计算的关键，因此，以MapReduce为核心研究云计算资源调度的相关工作显得尤为重要。
然而，与传统的集群和网格计算不同，云计算不仅在硬件上呈现多样性，而且用户执行不同任务对CPU (Central Processing Unit)、内存(Memory)及输入/输出等计算资源的需求方面也呈现高度的异构性和动态性。
在这样多资源的异构云计算环境下，全球数据量暴增，伴随着能耗也随之暴增，如何公平有效地分配资源并降低能源的浪费已成为云计算资源调度研究的关键问题。
本文主要围绕如何准确地描述资源的特性，捕捉用户的资源偏好、同时兼顾提高资源利用率、设计合理的资源调度策略展开研究。
本章首先介绍了本论文的研究背景及意义，重点叙述了云计算核心技术的经典调度算法的特点；然后对资源调度的国内外研究现状进行了分析，总结归纳了云计算环境下主流的几种不同的资源调度方法，最后给出了本文的贡献和结构安排。
1.2课题研究背景及意义
2003年MapReduce由一篇名为《MapReduce: Simplified Data Processing on Large Clusters》的论文首次提出，它是大数据时代的一次标志性革命。MapReduce作为Google核心技术之一，它采用分散处理-集中汇总的思想，是可以快速地处理海量数据的一种通用并行编程模型。
MapReduce将待处理的海量数据分成很多个map任务和reduce任务。其中，map任务被分布在整个集群网络的各个节点上来运行，负责处理一部分数据；reduce任务则负责汇总所有节点提交的中间结果，并经过归纳处理，输出最终结果。
MapReduce采用主/从结构，以Hadoop系统为例作业跟踪器Job Tracker与任务调度器Job Tracker的通信是双向的：Job Tracker接收到用户的作业请求后会命令Task Scheduler对提交的作业先进行初始化，然后再将待执行作业加入到资源分配的等待队列。
负责接收客户端用户（Client）提交的作业请求。TaskTracker定期地以Heartbeat方式向JobTracker汇报作业信息，并同时输出本节点空闲资源的使用情况和作业的执行状态。
当Task Tracker有空闲资源时，Job Tracker则在作业队列中选择合适的调度策略分配资源给Task Tracker。
基本思想是作业按照提交的先后顺序，遵循先进先出的原则，然后根据优先级（如系统可以根据作业提交的资源需求情况确定静态优先级或根据就绪作业等待高低按时间先后来选择被执行的作业。
如若先提交的作业需要占用大量的资源，处理占用的时间较多，那么占用资源少、处理时间较短的其他作业就可能需要等待很长时间。
正是因为实际应用中用户作业对资源需求差异性的存在，用户的体验和任务的执行效率会因此受到影响。
FIFO调度算法的弊端是忽略了不同作业存在需求差异，易造成云计算系统资源利用率不高，导致系统性能下降。
Capacity Scheduling：是一种多队列资源调度算法(由雅虎公司提出)，Capacity Scheduling调度算法为每个队列单独分配一定比例的资源，每个队列内部采用FIFO进行资源调度。
Capacity Scheduling 算法具有灵活性，一旦系统中有剩余资源出现，系统会暂时回收剩余资源，并把它实时地分配给有需要的队列使用。
而当原剩余资源所在队列有新的任务请求时，“借用”的资源会在它任务全部执行完后马上把“借用”的资源但随着分布式系统集群规模的不断扩大和用户任务对资源需求的差异性。
譬如，有的任务是CPU-密集型需要大量的CPU，而有的任务是Memory-密集型的，则需要大量的内存资源。
这些问题导致传统的MapRecuce并行编程模式无法提供良好的解决方案，这是因为传统的MapReduce提供的资源调度方案中，CPU、内存、网络带宽等资源是被切分成等量的若干份。
对应的每一份资源是采用固定的slot，即槽位来表示的。其主要存在的问题有：1）当MapReduce任务非常多时，所有资源管理和任务调度工作集中在Job Tracker作业跟踪器完成，存在单点故障。
- 资源被划分成若干份固定等量的slot槽位，无法真实准确地反映CPU或内存的占用情况，任务得不到有效的平衡，容易导致集群资源利用率不高、造成资源的浪费。
新管理架构改进了资源调度管理架构，将JobTracker的资源管理和作业调度这两个主要模块。隔离成了两个相互独立的模块。
通过将JobTracker拆分，与传统MapReduce相比，Hadoop Yarn降低了任务增加时对主节点的压力，能够运行更多的作业。
由于数据量、能耗暴增，公平有效分配资源成为资源调度的关键问题，本论文围绕MapReduce的Fair Scheduling算法中的DRF策略展开研究基于公平与效率的多资源调度优化问题。
1.3.1 传统资源调度优化分类
近年来，物联网、云计算、大数据、深度学习及量子通信等新技术已成为科研学者们研究的热点MapReduce是云计算实现并行计算的核心技术支撑，MapReduce资源调度优化的研究具有非常重要的价值和意义。
资源调度优化的主要目标是采用合适的资源调度策略实现资源的最优分配，并尽量使得分配结果满足用户的服务质量同时提高云计算系统资源使用效率及降低能耗等要求。
1.3.2基于能耗优化的资源调度
由于云计算大量的计算资源都集中在“云端”，导致云计算的资源利用率不高且造成巨大的能耗浪费，因此，数据中心的能耗管理面临着非常严峻的挑战。
云计算的巨大能耗已经成为阻碍其快速发展的制约因素之一。在这种情形下，学术界通常研究以下两类方法：
基于DVFS的方法：目前，降低云计算数据中心能耗的方法主要有基于DVFS技术的能耗优化，是大多数低功耗优化资源调度研究普遍采用的一种方法。
DVFS技术全称是动态电压频率调整技术（Dynamic Voltage and Frequency Scaling，DVFS），其核心思想是当CPU没有被完全利用时，通过降低CPU的供电电压和时钟频率，减小系统动态功耗的目的。
基于DVFS技术的能耗优化调度算法是云计算节能技术研究的重要基础。任务临界区的运行速度由静态算法来控制，以求出任务处于离线状态的执行速度。
即非临界区的静态速度，从而使得任务获得更多的空闲时间；而临界区的运行速度则由动态算法进行调节，保证了调度的实时性，并降低了能耗。
基于DVFS技术在计算节点闲置或低速运行（CPU的速率低）的情形下可以有效降低系统的空闲能耗。但是，这一类方法的弊端是同时减少了资源的供给，导致CPU的性能会随之降低。
以虚拟化为中心的方法：除DVFS技术外，近年来越来越多的研究者关注于基于虚拟机的资源调度算法以降低云计算数据中心的能耗。
虚拟化技术应用于节点硬件的同质化、隔离用户及高效地处理不同的工作负载
研究了低代价虚拟机迁移方法，提出了一种再调度的能耗优化算法。
解决了网络感知的周期性资源重置问题，算法有效提升了虚拟机的整体运行效率。
针对应用层的资源调度和资源使用效率问题，提出了一种基于阈值的动态资源分配算法。
算法以单个虚拟资源为动态分配资源的基本单位，通过负载的变化情况来动态地调度虚拟资源，实验证明了提出的方法能够提高资源利用率并降低用户使用成本。
将CPU和GPU耦合到一个单一的芯片上，针对这种CPU-GPU体系结构，文献[25]提出了一种弹性多资源公平分配策略来捕捉公平与效率之间的权衡。
而迁移的次数、迁移的规模及迁移的影响等因素不得不考虑。如上所述，基于能耗优化的资源调度算法思想固然有许多优势的决策基础。
但同时也应该注意到，这类算法思想仍存在诸多需要深入解决和研究的问题。
1.3.3基于智能优化的资源调度
云计算资源调度不可能在多项式时间复杂度内获得全局最优解因此，针对资源调度的NP-Hard 问题求近似解已成为国内外科学研究者们非常关注的热点问题。这些算法的特点是通过模拟自然过程或自然现象，具有自学习、自组织、自适应及高并行性等特点。
这一类智能优化算法主要分为单目标优化和多目标优化两种：单目标优化方法：提出了一个改进的粒子群优化算法，提高了粒子群算法收敛速度，避免了算法易陷入局部极小值的问题。
与传统算法不同，改进的算法在合作框架的基础上通过语义角色和概念来更新关键参数。
属于一典型的NP-hard 问题，提出了一个JSP的蚁群优化算法，通过使虚拟机闲置时间最小化来实现负载的平衡。
以上大多基于智能优化资源调度算法都是基于经典的启发式算法，经过适当地改进可应用于解决资源调度与分配问题，从而在较短的时间内把海量任务映射到合适的计算资源
多目标优化方法：现实应用中的很多问题都存在着多个目标，但往往有些目标是互相竞争互相排斥的。
多目标智能优化调度主要关注经济成本、能耗问题、服务质量及系统性能等目标。由于多目标优化调度问题有多个帕累托最优解，并且帕累托最优解集在解空间往往会形成一个边界线或者边界面。
因此，对于这一类问题很难找到使几个优化目标或各个目标函数同时实现最优解的结果，只能对其进行折中处理。
以多目标为约束条件的多目标优化的相关研究工作有很多。针对云计算任务调度问题，通过详细地定义任务对资源的需求特性提出了一个资源成本模型。
并根据提出的模型提出了一个多目标优化调度算法，算法以完工时间和用户预算成本为优化的。
因此，DRBF分配策略保障资源公平性不受用户欺骗行为影响，不仅满足真实性在资源利用率、用户所得总任务数及资源分配量等方面，表现优于其他三种算法；不仅保证了资源分配的公平性，而且提高了系统资源利用率。