首页资源分类嵌入式开发DSP > 基于人工蜂群算法的云计算

基于人工蜂群算法的云计算

已有 460221个资源

下载专区


TI最新应用解决方案

工业电子 汽车电子 个人消费电子

文档信息举报收藏

标    签: 云计算

分    享:

文档简介

人工蜂群算法的云计算

文档预览

江苏科技大学 硕士学位论文 大摘要 论 文 题 目 基于人工蜂群算法的云计算 资源优化管理的研究 研 究 方 向 云计算资源优化管理 学科、专业 计算机技术 研究生姓名 卢荣锐 导师姓名 彭志平 填表时间 2013 年 3 月 22 日 摘要 摘要 云计算作为一种新兴的计算模式,是并行计算、分布式计算和网格计算、效用计 算、网络存储、虚拟化、负载均衡等传统计算机技术和网络技术发展融合的产物。云 计算的主要思想是把互联网上的各种计算资源整合在一起,向用户提供以租用计算资 源为形式的服务。资源调度作为云计算中一个关键性的问题,它是按照一定的资源使 用规则,在不同的资源使用者之间进行的资源调整过程。目前的资源调度策略大多数 是通过虚拟机级别上的调度技术结合一定的调度策略来为虚拟机内部应用做资源调 度,并且调度算法过于简单,判断需要进行推测执行的任务的算法造成过多任务需要 推测执行,降低了整个任务的性能。所以能在云环境中引入一些群体智能算法进行任 务的分配和资源调度来实现资源的优化管理有着非常重要的研究意义。 本文首先从业界中不同角色给出的云计算定义出发,详细介绍了云计算的原理、 一般体系架构、服务模式、和资源调度的实现机制以及行业领先者 VMware 的等云计 算的相关技术。给出了云计算资源管理的系统模型,提出了任务分割模型和资源划分 模型,并对分割后的任务进行优先级编码、划分后的资源进行功能等级编码,给出了 资源调度策略,实现任务和资源的有效匹配。 其次,本文还研究了当前几种比较热门的群体仿生智能算法(遗传算法、蚁群算法、 粒子群算法、人工蜂群算法),通过比较它们之间的优缺点、适用范围,并结合云环境 的特性最终选取人工蜂群算法进行深入的研究和实验。人工蜂群算法是一种基于群体 智能的自适应搜索算法,是蜂群通过分工协作,蜜源信息的交换来寻找最优蜜源这一 群体行为的模拟。具有控制参数少、进化速度快、易于实现、并行扩展性好等优点, 并且在动态环境中也具有较高的灵活性和健壮性,特别适合解决组合优化问题。从解 决问题角度出发,人工蜂群算法能够很好地解决云境中的资源调度问题。但是它仍然 存在不完善的地方,在算法后期时搜索速度变慢、过早收敛、种群多样性减少等。本 文结合 ABC 算法的特性,通过引入一个控制因子,能够自适应地调整搜索空间寻找最 优蜜源位置,提出了一种改进的人工蜂群算法(MABC)—带控制因子的自适应人工 蜂群算法。通过控制因子来动态调节地蜂群个体之间信息共享程度的强弱,使算法避 免陷入局部最优解,更快速地找到全局最优解。 最后本文研究云计算资源 MapReduce 模式调度的运行模式,按照 QoS 参数要求 先将任务进行分类处理,可以准确及时地将任务分配到最合适的资源上。最后通过在 CloudSim 仿真环境中对现有的轮循算法,基本的人工蜂群算法和改进后的人工蜂群算 法进行仿真实验,通过资源调度性能测试,对比三种算法在执行相同任务的平均运行 I 江苏科技大学工学硕士学位论文 时间,结果表明改进后的算法执行时间大大缩短了,有效地提高了资源利用率,一定 程度上达到了对云计算资源的优化效果。 关键词:云计算;资源调度;人工蜂群算法;cloudSim II Abstract Abstract As an emerging computing model, cloud computing is a mode which have the ability of parallel computing, distributed computing and grid computing, utility computing, network storage, virtualization, load balance. The main idea of cloud computing is to integrate various computing resources on the Internet and provide the services of computing resources to users in the form of renting. These computing resources very large amount of data and are heterogeneous. Resource scheduling as a key problems in cloud computing, it is a resource adjustment process between different users of the resource according to certain regulations. Currently , most resource scheduling strategy is through the virtual machine level scheduling technology combined with certain scheduling strategy for applying , but dispatching algorithm is too simple, judge need to speculate the algorithm of task too cause need to speculate the task execution, and reduce the performance of the whole task. So if we can introduce some swarm intelligence algorithm into cloud environment, through task allocation and resource scheduling to make the optimization of resources management , it will be a very important research significance. Firstly ,the paper gives the definition of cloud computing from the different roles in the industry, and then introduced detailly the principle of cloud computing , general architecture, service model, and the realization of resource scheduling mechanism and industry leaders such as VMware's cloud computing technology. The paper also present cloud computing resource management system model , through investigating task division, resource division and resource scheduling strategy deeply, the task division model and resource division model are proposed respectively, then priority coding after task division, function level coding after resource division, and the resource scheduling strategy is proposed to achieve suitable match of tasks and resources. Secondly, this paper studies several popular group the current bionic intelligent algorithm (genetic algorithm, ant colony algorithm, particle swarm optimization, artificial bee colony algorithm), by comparing the advantages and disadvantages, the scope of application between them, and combination with the characteristics of the cloud . Finally we do deep research and experiments on artificial bee colony algorithm. Artificial colony algorithm is based on swarm intelligence, it is the simulation of this group behavior III 江苏科技大学工学硕士学位论文 through the division of labour cooperation and exchange for bee information in order to find optimal bee. The algorithm has less control parameters, its evolution speed is fast, the algorithm is easy to be realized, especially for the good parallel scalability. Besides, in dynamic environment the algorithm also has high agility and robustness, it is especially suitable for solving combinatorial optimization problem. From the Angle to solve the problem, the artificial colony algorithm also can well solve the cloud of the land resource scheduling problem. But there still exists no perfect place, in the late period of algorithm evolution the search speed gets slow, and premature convergence, population diversity is reduce and. Based on the characteristics of the ABC algorithm, and by introducing a control factor, the algorithm is adaptive to adjust the search space to find the optimal bee position, an modified artificial colony algorithm(MABC)is proposed - take control factor of the adaptive artificial colony algorithm. Its main idea is: in the search process, through the control factor to dynamically adjust information strength sharing between colony individual, avoid the algorithm falling into local optimal solution. According to the effective design of the algorithm parameters, the performance of the algorithm is improved. Finally in this paper, we study the cloud computing resource scheduling operation on the mode of the MapReduce model. According to the requirements of QoS parameters process categorizing task ,we can assign tasks accurately to the most appropriate resources in a timely manner. And in the cloudSim simulation environment for the round robin algorithm, basic artificial bee colony algorithm and the improved artificial bee colony algorithm simulation, through resource scheduling performance test, the comparison of three kinds of algorithm to perform the same task average running time, the results show that the improved algorithm execution time is greatly shortened, and effectively improve the the utilization rate of resources, at a certain extent on cloud computing resources optimization effect. Keywords: Cloud computing; Resource schedule; Artificial bee colony algorithm; CloudSim IV 目录 目录 摘 要 ........................................................................................................................................ I Abstract ................................................................................................................................. III 第 1 章 绪 论 ...................................................................................................................- 1 - 1.1 研究背景、目的以及意义 ................................................................................- 1 1.2 研究现状 ............................................................................................................- 2 1.3 本文研究内容 ....................................................................................................- 3 1.4 本文结构 ............................................................................................................- 4 第 2 章 云计算相关技术概述 .........................................................................................- 5 2.1 云计算概述 ........................................................................................................- 5 - 2.1.1 云计算概念 .............................................................................................- 5 2.1.2 云计算的原理 .........................................................................................- 6 2.1.3 云计算的研究与应用现状 .....................................................................- 6 2.1.4 云计算的特点 .........................................................................................- 9 2.2 云计算一般的体系架构 ..................................................................................- 10 2.2.1 SOA .......................................................................................................- 10 2.2.2 管理中间件 ...........................................................................................- 10 2.2.3 资源池 ...................................................................................................- 10 2.2.4 物理资源 ...............................................................................................- 11 2.3 云计算服务 ......................................................................................................- 11 2.4 云计算实现机制 ..............................................................................................- 12 2.5 云计算应用中的资源管理 ..............................................................................- 13 2.5.1 云计算应用中的任务分割 ...................................................................- 13 2.5.2 云计算应用中的资源调度 ...................................................................- 13 2.6 典型的云计算平台—VMware ..........................................................................- 15 2.6.1 VMware 虚拟化技术............................................................................- 15 2.6.2 VMware 云计算架构............................................................................- 16 2.7 本章小结 ..........................................................................................................- 17 - V 江苏科技大学工学硕士学位论文 第 3 章 云计算环境下资源调度及优化算法的研究 ...................................................- 19 3.1 云计算环境下资源调度的研究 ........................................................................- 19 3.1.1 云计算资源调度模型 ...........................................................................- 19 3.1.2 任务分割 ...............................................................................................- 20 3.1.3 资源划分 ...............................................................................................- 21 3.1.4 资源管理的调度策略 ...........................................................................- 23 3.2 资源管理系统的详细设计 ..............................................................................- 24 3.3 资源调度优化算法 ..........................................................................................- 27 3.4 基于 QoS 的任务分类 ...................................................................................- 29 3.5 MapReduce 模式下的调度.............................................................................- 30 3.6 本章小结 ............................................................................................................- 32 - 第 4 章 基于 MABC 算法的云计算资源调度策略 .....................................................- 33 4.1 人工蜂群算法的基本原理 ..............................................................................- 33 4.2 人工蜂群算法(ABC algorithm)的数学模型...................................................- 33 4.3 改进的人工蜂群算法与云环境下的资源调度 ..............................................- 34 4.4 参数设置及计算资源优劣度评判条件 ............................................................- 36 4.5 本章小结 ..........................................................................................................- 38 - 第 5 章 实验仿真与性能分析 .......................................................................................- 39 5.1 测试环境配置 ..................................................................................................- 39 5.1.1 CloudSim 简介......................................................................................- 39 5.1.2 CloudSim 体系结构..............................................................................- 39 5.1.3 环境配置 ...............................................................................................- 40 5.2 仿真流程 ..........................................................................................................- 41 5.3 实验结果及性能分析 ......................................................................................- 42 - 结论与展望 .......................................................................................................................- 45 参考文献 ...........................................................................................................................- 47 攻读学位期间所发表的学术论文专利目录 ...................................................................- 49 致 谢 .............................................................................................................................. - 51 - VI contents CONTENTS Abstract(Chinese) ...................................................................................错误!未定义书签。 Abstract(English)................. 错误!未定义书签。错误!未定义书签。错误!未定义书签。 Chapter1 Exordium ...............................................................................错误!未定义书签。 1.1 Background and significance of research................................错误!未定义书签。 1.2 Research status ........................................................................错误!未定义书签。 1.3 The structure of the thesis .......................................................错误!未定义书签。 1.4 Chapters summary...................................................................错误!未定义书签。 Chapter2 Cloud computing technology overview .............................................................. 5 2.1 Cloud computing summary ................................................................................. 5 2.1.1 The concept of cloud computing ................................................................. 5 2.1.2 The principle of cloud computing ............................................................... 6 2.1.3 The study and Application status of cloud computing ................................ 6 2.1.4 The characteristics of cloud computing ..................................................... 9 2.2 The general architecture of cloud computing ....................................................... 10 2.2.1 SOA ........................................................................................................... 10 2.2.2 Management Middleware.............................................错误!未定义书签。 2.2.3 Resource pool ...............................................................错误!未定义书签。 2.2.4 Physical resources ........................................................错误!未定义书签。 2.3 Cloud computing services .......................................................错误!未定义书签。 2.4 Cloud computing implementation mechanism........................错误!未定义书签。 2.5 The resource management of cloud computing application....错误!未定义书签。 2.5.1 The task segment of cloud computing application .......错误!未定义书签。 2.5.2 The resource scheduling of cloud computing application错 误 ! 未 定 义 书 签。 2.6 The typical cloud computing platform - VMWARE ..................错误!未定义书签。 2.6.1 VMware virtualization technology...............................错误!未定义书签。 2.6.2 VMware cloud computing architecture ........................错误!未定义书签。 2.7 Chapter summary ....................................................................错误!未定义书签。 Chapter3 Cloud computing resource scheduling and optimization algorithm错误!未 定 VII 江苏科技大学工学硕士学位论文 义书签。 3.1 The research of cloud computing resource scheduling ..............错误!未定义书签。 3.1.1 Cloud computing resource scheduling model ..............错误!未定义书签。 3.1.2 Task division.................................................................错误!未定义书签。 3.1.3 Resource partition.........................................................错误!未定义书签。 3.1.4 Resource scheduling strategy .......................................错误!未定义书签。 3.2 The detailed design of resource management system .............错误!未定义书签。 3.3 Resource scheduling algorithm ...............................................错误!未定义书签。 3.4 Classification task base on QoS............................................................................. 29 3.5 The Map-Reduce mode operation ...........................................错误!未定义书签。 3.6 Chapter summary ....................................................................错误!未定义书签。 Chapter4 Scheduling strategy based on MABC algorithm ................错误!未定义书签。 4.1 The basic principle of artificial bee colony algorithm.............错误!未定义书签。 4.2 Artificial bee colony algorithm mathematical model..............错误!未定义书签。 4.3 Improved bee-colony algorithm and cloud environment resource scheduling错误! 未定义书签。 4.4 Parameter setting and computing resources quality evaluation conditions错 误 ! 未 定义书签。 4.5 Chapter summary ....................................................................错误!未定义书签。 Chapter5 The simulation results and performance testing ................错误!未定义书签。 5.1 Test environment configuration...............................................错误!未定义书签。 5.1.1 CloudSim introduction .................................................错误!未定义书签。 5.1.2 CloudSim System structure ..........................................错误!未定义书签。 5.1.3 Environment configuration...........................................错误!未定义书签。 5.2 Process simulation ................................................................................................ 41 5.3 The experimental results and performance analysis................错误!未定义书签。 Conclusion and outlook..........................................................................错误!未定义书签。 References ...............................................................................................错误!未定义书签。 The academic and scientific research published during graduate school错误!未定义书 签。 Acknowledgement ............................................................................................................... 51 VIII contents 摘 要 ........................................................................................................................................ I Abstract ................................................................................................................................. III 目 录 .................................................................................................................................... V 第 1 章 绪 论 .................................................................................................................- 1 - 1.1 研究背景、目的以及意义 ................................................................................- 1 1.2 研究现状 ............................................................................................................- 2 1.3 本文研究内容 ....................................................................................................- 3 1.4 本文结构 ............................................................................................................- 4 第 2 章 云计算相关技术概述 .........................................................................................- 5 2.1 云计算概述 ........................................................................................................- 5 - 2.1.1 云计算概念 .............................................................................................- 5 2.1.2 云计算的原理 .........................................................................................- 6 2.1.3 云计算的研究与应用现状 .....................................................................- 6 2.1.4 云计算的特点 .........................................................................................- 9 2.2 云计算一般的体系架构 ..................................................................................- 10 2.2.1 SOA .......................................................................................................- 10 2.2.2 管理中间件 ...........................................................................................- 10 2.2.3 资源池 ...................................................................................................- 10 2.2.4 物理资源 ...............................................................................................- 11 2.3 云计算服务 ......................................................................................................- 11 2.4 云计算实现机制 ..............................................................................................- 12 2.5 云计算应用中的资源管理 ..............................................................................- 13 2.5.1 云计算应用中的任务分割 ...................................................................- 13 2.5.2 云计算应用中的资源调度 ...................................................................- 13 2.6 典型的云计算平台—VMware ..........................................................................- 15 2.6.1 VMware 虚拟化技术............................................................................- 15 2.6.2 VMware 云计算架构............................................................................- 16 2.7 本章小结 ..........................................................................................................- 17 第 3 章 云计算环境下资源调度及优化算法的研究 ...................................................- 19 - IX 江苏科技大学工学硕士学位论文 3.1 云计算环境下资源调度的研究 ........................................................................- 19 3.1.1 云计算资源调度模型 ...........................................................................- 19 3.1.2 任务分割 ...............................................................................................- 20 3.1.3 资源划分 ...............................................................................................- 21 3.1.4 资源管理的调度策略 ...........................................................................- 23 - 3.2 资源管理系统的详细设计 ..............................................................................- 24 3.3 资源调度优化算法 ..........................................................................................- 27 3.4 基于 QoS 的任务分类 ...................................................................................- 29 3.5 MapReduce 模式下的调度.............................................................................- 30 3.6 本章小结 ............................................................................................................- 32 第 4 章 基于 MABC 算法的云计算资源调度策略 .....................................................- 33 4.1 人工蜂群算法的基本原理 ..............................................................................- 33 4.2 人工蜂群算法(ABC algorithm)的数学模型...................................................- 33 4.3 改进的人工蜂群算法与云环境下的资源调度 ..............................................- 34 4.4 参数设置及计算资源优劣度评判条件 ............................................................- 36 4.5 本章小结 ..........................................................................................................- 38 第 5 章 实验仿真与性能分析 .......................................................................................- 39 5.1 测试环境配置 ..................................................................................................- 39 - 5.1.1 CloudSim 简介......................................................................................- 39 5.1.2 CloudSim 体系结构..............................................................................- 39 5.1.3 环境配置 ...............................................................................................- 40 5.2 仿真流程 ..........................................................................................................- 41 5.3 实验结果及性能分析 ......................................................................................- 42 结论与展望 .......................................................................................................................- 45 工作总结 ...................................................................................................................- 45 工作展望 ...................................................................................................................- 46 参考文献 ...........................................................................................................................- 47 攻读学位期间所发表的学术论文专利目录 ...................................................................- 49 致 谢 ...............................................................................................................................- 51 - X 第 1 章 绪论 第1章 绪 论 1.1 研究背景、目的以及意义 近年来,人们的工作、学习和生活等发生了翻天覆地的变化,而这一切都依赖着 通讯技术、信息技术、计算机科学技术等的发展。随后,网格计算、普适计算的大力 发展,也给人们带来了极大的方便,它将更多的资源和服务整合在一起,于是用户可 以更便捷地获取互联网的服务。同时,企业规模的不断壮大,对用来存取数据并构建 数据中心的基础设施的建设要求也日益提高;数据中心的构建和维护会消耗相当大的 成本,于是也给企业的管理工作带来了全新的挑战[4]。企业若能建立自己的数据中心, 或者与其他企业一起共享数据中心,就不必投入资金用来进行基础设施的建设,企业 既能获取所需的服务而也不必花费高额的运营成本,从而能够更加灵活地管理自己的 资源。在这种背景下,云计算应运而生。作为一个新兴的商业计算模型,云计算利用 高速互联网的传输能力,将数据的处理过程从个人计算机或服务器转移到互联网上的 大型计算机集群中。集群中的节点都是很普通的 PC 服务器,由一个大型的数据处理 中心管理统一管理,数据中心根据用户的需求分配计算资源,实现与超级计算机一样 的作用。云计算是并行计算、分布式计算和网格计算的综合发展,或者说是这些计算 科学概念的商业实现[1] 云计算利用网络将不同的资源和信息整合,使其成为一个整体,用户能实现将这 些计算和存储资源进行资源分享与协作的要求,它将软件、平台、网格计算、普适计 算、虚拟化技术等概念融合,云计算将计算任务分布在由网络中的计算机和存储设备 等构成的资源池上。云用户根据自身的需要来获取存储空间、计算能力和各种软件服 务,即通过网络将各种资源整合在一起,并将资源以服务的形式向外提供。 云端能完成如文字处理、数据计算、数据存储等用户所需完成的各种任务,云用 户付费后,只需要通过一个终端,即可以利用网络来获取自己所需的服务,于是云用 户无需购买价值不菲的软件和硬件设施,而且软件的升级和维护等都可以由云端提供 商来完成,这种全新的商业计算模式极大地方便了用户。另外,对企业也不必为了构 建自己的数据中心而购买昂贵的基础设施,大大地节约了成本。除此之外,所有的云 提供商都是由很多庞大的数据中心构建而成,因此云计算服务商可以提供近乎无限的 数据计算和存储能力,能满足系统对软硬件设备的要求,从而更好地应对业务的突发 性需求。目前现有的云计算提供的服务形式存在单一性和定价不灵活的局限性,这样 用户只限于使用单一的云服务,用户通过连接某个云来获得其所需服务,若此云提供 商出故障,则即使其他云可以提供相同的服务,用户也无法得到所需的服务,这种服 -1- 江苏科技大学工学硕士学位论文 务是面向连接的,而不是面向服务的[4]。能在用户中实现大范围的资源共享是研究云 计算的根本目的,云计算系统的核心部分就是对资源实现合理的管理。在某个特定的 云环境中,由用户发出资源请求来管理云计算资源,云计算服务器根据的资源使用规 则,在合理地调度相应的资源的基础上,将对应的资源分配给资源请求者,以保证请 求资源的作业能够在不同的用户之间调整及运行,云计算资源管理系统为了实现上述 功能,提供了资源发现、资源分发、资源存储和资源的调度等四种基本服务[5]。其中, 资源发现和资源分发的功能互补;资源分发、资源发现和资源存储是资源调度的前提 条件,将用户请求的资源分配到相应的用户中去即为资源调度的具体任务,资源调度 的实现还需依赖不同结点资源的协作分配[5]。目前的资源管理策略主要利用虚拟机级 别上的调度技术,并结合一定的调度策略来调度虚拟机内部应用资源,调度算法过于 简单且精确性不高,算法的执行能力较差, 故如何引入一些改进的调度算法来实现资 源的合理调度是急需解决的问题。 人工蜂群算法是一种基于群体智能的自适应搜索算法,它是对蜂群通过分工协作 和交换蜜源信息来寻找最优蜜源这一群体行为的模拟。人工蜂群算法具有控制参数少、 进化速度快、易于实现、并行扩展性好等优点,并且在动态环境中也具有较高的灵活 性和健壮性,特别适合解决组合优化问题。资源调度的本质是从资源分配给任务的多 种组合中选出性能比较好的一种动态组合方式,也是属于组合优化的问题。从解决问 题角度出发,人工蜂群算法能够很好地解决云境中的资源调度问题。建立在 CloudSim 环境下的仿真实验,实验结果表明了这种算法能满足云计算服务模式,并且在执行同 等任务时,响应时间与其他的分配算法相比变得更短的,工作质量也增强了,从而更 加适合在云环境中使用,此算法能够缩短云环境下的任务平均运行时间。提高了资源 利用率.因此在对云计算资源管理具有很重要的意义与实用价值。 近几年,云计算(Cloud Computing) 是商业机构、科研机构研究的热点问题,云计 算主要对数据中心的资源进行虚拟化处理,并以根据用户所提交的任务需求和资源自 身的最大利用率来为服务用户,同时对数据中心所提供的服务类型和服务方式等问题 进行研究[3]。如何高效地进行用户任务调度、合理分配系统资源并实现资源的均衡负 载,这些是商业界关心的问题,也是提高云计算平台性能和服务质量的关键要求。 1.2 研究现状 云计算是一种商业计算模型。在业界大规模的推动下,各类云计算应用应运而生, 极大的推动了云计算技术的快速向前发展[28],全球各 IT 巨头争相进入云计算领域,从 不同领域和角度开始在云计算领域布局[29],Microsoft、Google、IBM、VMware、Oracle、 HP 等纷纷发布云计算战略,试图在激烈的云计算市场竞争中抢占先机。每个公司根据 -2- 第 1 章 绪论 自身的基础设施和技术来构建云平台:Google 公司拥有独立的云计算平台,可以提供 如搜索服务等在内的多种应用服务,针对搜索应用程序的特点开发了 MapReduce 并行 编程模式,另外,分布式锁机制 Chubby、Google Fife System 分布式文件系统、大规 模分布式数据库 BigTabte 构成了 Google 的云基础模式[6]。 目前,国内外的云计算厂商仍对云计算的资源作业调度、负载均衡及资源优化问 题尤为关注,目前云计算应用还没有形成统一的标准和规范,云厂商架构自己的基础 设施并在此基础上开发发展云计算应用,云计算的作业调度模式和资源管理模式呈现 多样化发展趋势[6]。面对云计算中如此庞大的计算资源,考虑到资源利用、经济效益 等各个方面的原因,如何对其进行优化管理在国内外也有一些研究。 目前,学术界也正加大了对云计算的应用研究,国内外的专家学者对云计算都提 出了不同的架构思想,基本都体现了云计算的特征及相关的技术手段,如资源池和虚 拟化的概念等。 国内张尧学院士领导的研究小组对透明计算理论进行了深入的研究,使透明计算 的概念不断发展而被重视;透明计算可以将存储与计算分离,即将操作系统、应用程 序和具体程序的执行在不同的媒介实现;服务器端能完成操作系统和应用程序,而执 行具体程序却是通过用户端的机器完成;系统自动完成具体的调度过程和环境部署, 而这一切对用户来说完全是透明的,用户则可以根据需要来通过网络获取多种服务[9]。 在国外,云计算的研究正在不断地前进中。IBM 早前基于云计算融合了虚拟技术、 SOA 技术,提出 7 个架构的准则,开发了可重用的开放架构(CCOA);后来克莱姆森 学院在网格结构的基础上构建计算云,实现了在自适应的调度覆盖网络,其中网格取 代节点管理策略的域,而且可实现在网格架构下搭建云计算环境;代尔夫特大学针对 云计算的安全威胁,设计了 C-Mcte 结构可分析出云计算的性能;为了实现云服务的动 态变化,有人又设计出虚拟化的网络结构,使得虚拟机可以进行迁移,大大提高了云 服务质量;美国国家实验室提出高性能并行计算的思想,在提高性能的同时节省云计 算中大量的计算资源[8]。 如何有效的利用云计算技术,建设一个具有交互能力强、资源利用率高、规范化 的云计算资源管理系统仍然是一项艰巨的任务,有待进行长期的研究和探索。 1.3 本文研究内容 基于上述研究内容和方向,本文主要包括以下几个方面的内容: (1) 从多角度解析云计算的概念,总结云计算的几大主要特征,分析总结主流商业 云提供商的云计算方案特点,为用户选择合适自己的云计算平台提供参考。 (2) 阐述云计算资源管理系统的功能。针对用户资源需求任务和云计算资源管理的 -3- 江苏科技大学工学硕士学位论文 特点,提出任务分割模型和资源划分模型,并对分割后的任务和划分后的资源进行优 化,提出一种基于人工蜂群算法的云计算资源调度策略,以实现实验任务和虚拟机资 源的有效匹配。 (3) 主要阐述遗传算法、粒子群算法、蚁群算法以及人工蜂群算法等群体仿生智能 算法的概念以及它们的优缺点。重点研究人工蜂群算法的原理及其性能分析,同时建 立实现算法的数学模型。针对算法后期搜索速度变慢、过早收敛、种群多样性减少等 缺点,提出了一种改进的人工蜂群算法—-带控制因子的自适应人工蜂群算法。其主要 思想是:在搜索过程中,通过控制因子来动态调节地蜂群个体之间信息共享程度的强 弱,使算法避免陷入局部最优解。基于这种改进的人工蜂群优化算法,云计算服务集 群可以快速实现资源匹配、资源发现、产生调度、执行任务,对资源管理起到了很好 的优化效果。 (4) 研究 Google 公司提出的 MapReduce 调度模型,了解 MapReduce 在典型云计 算应用的使用情。在此模式下设置相关的试验参数。在 cloudSim 仿真平台下,将现有 的随机算法,基本人工蜂群算法和改进后的人工蜂群引入到云计算环境中,计资源调 度性能测试实验,通过对比三种算法执行任务的时间,验证改进后算法对资源调度的 优化效果。 1.4 本文结构 第一章,绪论。阐述课题背景和现实意义,总结国内外研究状况,最后说明本课 题要研究的主要内容。 第二章,云计算的相关技术。详细介绍了云计算的原理、一般体系架构、实现机 制、任务分割和资源调度以及行业领先者 VMware 的等云计算的相关技术。 第三章,云计算中的资源调度策略。给出了云计算资源管理的系统模型,深入研 究任务分割、资源划分、资源调度等关键技术,并列举出常用的优化算法,比较个算 法的优缺点,详细介绍 MapReduce 模式下调度设置。 第四章,基于 MABC 算法的云计算资源调度策略。详细介绍了人工蜂群算法的基 本原理以及它的数学模型,提出改进的人工蜂群算法并将此算法引入到云环境进行资 源调度,给出算法调度的工作流程。 第五章,实验仿真与性能分析。介绍 cloudsim 平台的原理以及它的体系架构,配 置实验环境及试验参数进行仿真实验。通过资源调度性能测试实验,验证了资源调度 策略的有效性。 第六章,总结与展望。总结本文的主要工作,展望今后的工作方向。 -4- 第 2 章 云计算相关技术概述 第 2 章 云计算相关技术概述 本章首先描述云计算的概念、特点以及发展应用的现状,总结对当前商用云平台 的架构,结合云计算分布式、面向服务特征提出四层云架构,总结了各层功能、关键 技术和问题,包括分布式调度问题、虚拟化技术问题和监控容错问题。 2.1 云计算概述 下面主要介绍云计算的概念、原理、研究现状以及特点等相关内容。 2.1.1 云计算概念 2006 年,Google 首先推出“Google 101 计划”,提出了“云”的概念和理论,随 后,Amazon、Microsoft、HP、Yahoo、Intel、IBM 纷纷宣布“云计划”,云存储、云安 全、医疗、教育云、交通云、旅游云、公共云、私有云、混合云等与云计算相关的名 词不断的涌现,云计算迅速被业界所接受。然而,云计算究竟是什么呢? 在维基百科(Wikipedia.org)中,定义云计算为一种基于互联网的计算,共享硬 件、软件和信息等资源,以按需的方式提供服务,如同生活中的电网一样。专业 IT 名 词百科(Whatis.com)将云计算定义为一切能够通过互联网提供的服务,并将服务划 分为三个层次:基础设施即服务(Infrastructure as a Service, IaaS)、平台即服务(Platform as a Service, Paas)和软件即服务(Software as a Service, SaaS)[7]。《商业周刊》 (BussinessWeek.com)中,Google 云计算视为由网络连接起来的几十万甚至上百万台 的廉价计算机,这些超大规模集群每天都处理着来自互联网的海量检索数据和搜索业 务;Amazon 云计算视为一个大规模的系统环境中,不同的系统之间能够相互提供服 务,当整个系统相互协作并通过互联网向外界提供服务时,系统的集合体就称为云[8]。 IBM 认为云计算是对信息技术和商业服务的消费与交付模式革新,在该模式下,用户 可以实现的按需请求服务,通过网络就可以获得来自从地理无关的资源池中快速分配 到的资源,根据实际使用情况计费。 云计算的出现,彻底的改变了企业及个人用户的应用观念,从传统的购买软硬件 产品到购买一种“服务”。在云计算中,数据保存在云端,一般不会丢失,安全性好不 必备份,并且可任意点的恢复;软件也放在云端,不必每次都下载,并且支持自动升 级;计算无所不在,任何时间、任意地点、任何设备均可接入,进行计算;计算能力 无限强大,无限的空间,无限的速度。总之,云计算是一个基于互联网的虚拟化资源 平台,是在新的 IT 架构模式下形成的一个动态的数据中心;以互联网为载体聚集大量 -5- 江苏科技大学工学硕士学位论文 的资源,通过动态分配、协同处理、负载均衡等技术手段,将计算任务分布在大量计 算机构成的资源池上,使用户能够获取超强的计算能力、大规模的存储空间和便捷的 信息服务[6]。 2.1.2 云计算的原理 云计算是分布式计算(Distributed Computing)、并行计算(Parallel Computing)、网格 计算(Grid Computing)、网络存储(Network Storage)和大型数据中心(Large-scale Data Center)的融合发展,可以说是在互联网宽带技术和虚拟化技术高速发展的背景下,网 络计算和公用计算的商业实现[9]。 概括的说,云计算的基本原理是:利用广域分布的分布式计算机资源为互联网用 户提供各种服务服务(包括计算、存储、软件),用户可以根据实际需求随时、随地的 获取服务资源。云计算利用互联网技术和虚拟化技术,将大量的 PC 机或服务器连接 在一起形成庞大的集群,虚拟化成的资源池,按需向用户分配资源,以较低的成本获 得较高的资源利用率。云计算作为一种全新的理念,打破传统模式下的资源束缚,用 户只要能够接入网络,便可以获取超级的计算能力、存储能力以及软件资源。 2.1.3 云计算的研究与应用现状 云计算其实是一种商业计算模型,最终都是要运用在商业中。在业界大规模的推动 下,各类云计算应用应运而生,极大的推动了云计算技术的快速向前发展,全球各 IT 巨 头 争 相 进 入 云 计 算 领 域 , 从 不 同 领 域 和 角 度 开 始 在 云 计 算 领 域 布 局 , Microsoft 、 Google、IBM、VMware、Oracle、HP 等纷纷发布云计算战略,试图在激烈的云计算市 场竞争中抢占先机。 (1)IBM“蓝云(Blue Cloud)” 2007 年 11 月,IBM 宣布“Blue Cloud”计划,将云计算作为一项重要的战略。目前, IBM 在全球已建立了 13 个云计算中心,拥有多个成功案例,不仅能够帮助企业建立内 部私有云,而且可以构建对外服务的公共云。当前 IBM 已经部署了世界上最大的商业 智能私有云,并着力于智慧医疗云、“UK Smart Energy Cloud(英国智能能源云)”等云 计算相关应用的发展。图 2.1 为 IBM 的“Blue Cloud”系统架构。 -6- 第 2 章 云计算相关技术概述 图 2.1 IBM 的“Blue Cloud”系统架构 Fig2.1 Architecture of IBM “Blue Cloud” (2)Google 云计算 Google 的云计算应用有:由 100 万台以上的服务器组成、分散在全球 200 多个站点 上的 Google Engine,Google Earth、Google Map、Google Gmail、Google Docs 等。Google 建立了 世界最大的公有云平台,提供搜索引擎和网络应用引擎(Google App Engine) 服务,同时在云计算教育市场中推广 Google Gmail、Google Calendar、Google Docs 等云 应用。图 2.2 为 Google 云平台架构。 图 2.2 Google 云平台架构 Fig2.2 Architecture of Google cloud platform (3)Amazon 云计算 Amazon 侧重于云计算领域中云服务方面的发展,有弹性计算云服务 EC2、简单存 储服务 S3、简单数据库服务 SimpleDB、弹性 MapReduce 服务、简单队列服务 SQS、内 容推送服务 CloudFront、电子商务服务 DevPay 等。目前,Amazon 推出了电子商务云服 -7- 江苏科技大学工学硕士学位论文 务、在线存储服务 Amazon Cloud Drive 以及基于云计算的音乐服务等方面的云计算应 用。图 2.3 为 Amazon 云平台架构。 图 2.3 Amazon 云平台架构 Fig2.3 Architecture of Amazon cloud platform (4)Microsoft 云计算 Microsoft 云计算涉及了云计算的不同层次,提供全面的 SaaS(软件即服务)服务, 如 Microsoft 的 Live 服务和 Online 服务;也提供基于 Microsoft Windows Azure Platform 的 PaaS(平台即服务)服务;还提供数据存储、计算、数据中心优化等 IaaS(基础设 施即服务)服务[16]。在云计算应用方面,微软推出 OA Cloud 云端办公室服务、HealthVaul 系统以及教育行业云等。图 2.4 为 Microsoft 的云平台架构。 图 2.4 Microsoft 云平台架构 Fig2.4 Architecture of Microsoft cloud platform -8- 第 2 章 云计算相关技术概述 目前,云计算以较快的速度向前发展,越来越多的应用开始转向云计算,依托云计 算技术,开拓了新的发展模式。SAP 推出基于面向服务的 SaaS 产品(包括 CRM、SCM 等);阿里云提供云聊、云存储、云手机、云搜索等应用;美国 LifeSize 推出 LifeSize Passport ConnectTM——云视频会议系统;乐视网推出统一的云视频平台;爱国者推出 云播放器 MP6;讯飞率先推出云语音识别;大量的云输入法有搜狗云输入法、QQ 云输 入法、百度在线输入法、Google 云输入法等。另外,大量行业云如医疗云、电网云、交 通云、教育云、旅游云、政务云等不断涌现。 2.1.4 云计算的特点 云计算是将并行计算、分布式计算、普适计算和网格计算等计算技术综合运用的 结果,是利用虚拟化等技术将资源和服务整合在一起,向用户提供平台、软件、基础 设施的一种新的商业计算模式,它利用虚拟化技术将所有资源以资源池的形式提供给 上层,并由相应的中间件或其它方式来进行资源池的管理,它可以提供高可用性和高 可靠性的计算平台[4]。云计算的特征可概况为分布式计算、大规模、虚拟化、按需服 务等,总结如下: (1) 超大规模。大部分云中心都具备极其大的规模,靠成千上万台服务器组成,像 著名公司 IBM、Yahoo 等公司的“云端”服务器有几十万台甚至百万。 (2) 虚拟化技术。云计算能为用户提供任意位置和所有终端设备的服务,所请求的 资源来自“云”,而不是固定的有形的实体,也就是说用户不知道“云”上的应用运行 的具体物理资源位置[4]。 (3) 高可伸缩性。为了能满足不断增长的用户和应用的需求,“云”可以动态的进 行伸缩。 (4) 易用性。云计算使用起来很容易,IT 资源如同水和电等公共设备一样,用户 可以方便、快捷地享受到各种服务。用户只需要登录对应的系统就能直接使用云计算。 (5) 成本适中。从服务提供商的角度出发,云计算可以让提供商无需关心细节问题, 只专注业务问题,对创新和降低成本很有效;从用户的角度出发,云计算是一款软件, 只需定期的更新,没有购买成本,不需要任何投资,所以云计算的适用是经济、实用 的。 (6) 通用性。云计算具有普遍性,它不针对某个具体应用,在同一片“云”能支持 各式各样的应用。 (7) 高可靠性。云的资源管理应该满足用户应用的可靠性需求,通过数据多副本容 错和计算节点同构可互换等有效措施来保障服务的高可靠性,使用云计算比使用本地 计算机更加可靠。 (8) 按使用计费。云的服务可以按实际用情况进行计量收费。比如 Amazon 的简单 -9- 江苏科技大学工学硕士学位论文 存储服务 S3(Simple Storage Services)。 2.2 云计算一般的体系架构 云计算一般的体系结构分为四层:物理资源层、资源虚拟化层、管理中间件层、 SOA(Service-Oriented Architecture,面向服务的体系结构)层[10],如图 2.5 所示。该 体系架构下,管理中间件负责建立用户应用与虚拟资源之间的联系。 图 2.5 云计算的体系架构 Fig 2.5 Architecture of cloud computing 2.2.1 SOA SOA 层将云计算的服务能力封装成为标准化的 Web Services 服务,以接口的模式进 行管理和使用,包括了服务接口、服务注册、服务查找、服务访问、服务工作流等内容。 在 SOA 组件模型下,云计算可以实现服务的平台无关性,使各种服务能够统一的使用 和交互,同时 SOA 具有低耦合、分模块实施以及发布方便等方面的优势。 2.2.2 管理中间件 管理中间件抽象为四部分:用户管理、映像管理、安全管理和资源管理[6],如图 2.5 所示。云计算的结构是松耦合模式,具有特点是应用独立、灵活性强,同时也增加了资 源管理和安全管理的复杂性。 2.2.3 资源池 云计算通过虚拟化技术,将互联网上的分布式计算机和设备虚拟化为计算资源池、 存储资源池、网络资源池、数据资源池,以按需的模式向用户提供服务,当用户提出资 - 10 - 第 2 章 云计算相关技术概述 源请求后,管理中间件就会分配相关的虚拟化资源[10]。云计算支持用户在任何时候,任 意位置上、使用任何终端设备通过网络来按照自己的需求来获取云服务。 2.2.4 物理资源 物理资源是由分布在互联网上的计算机、存储器、网络设备、数据库等基础设施组 成,包含了计算机运行时的硬件设备及其软件[6]。云计算采用松耦合的形式,通过网络 技术、并行技术、分布式技术等进行资源整合并虚拟化,大大的提高了云计算的灵活性。 2.3 云计算服务 云计算以服务的模式向用户提供服务,云计算的服务方式分为 IaaS、PaaS、SaaS 三 类。图 2.6 为云计算服务方式。 软件即服务 SaaS(Software as a Service) 平台即服务 PaaS(Platform as a Service) 基础设施即服务 IaaS(Infrastructure as a Service) 图 2.6 云计算服务 Fig 2.6 The services of cloud computing 1.IaaS 基础架构即服务 IaaS,相当于一个按需提供基础设施服务的数据中心,通过多台服 务器组成的“云端”基础设施,它是由内存、网络、I/O 设备、计算能力和存储组成的 一个虚拟资源池,利用网络向所有用户提供用户所需的资源存储、虚拟化等各种服务, 本质上使用方式是一个托管型的硬件。如 Amazon Web 服务(AWS),IBM 的 Blue Cloud 等均属于 IaaS 服务方式。 目前,各大 IaaS 云计算提供商均是通过虚拟化技术,对大规模的底层硬件资源进行 虚拟化,屏蔽底层硬件资源的物理差异,提供统一资源管理接口。IaaS 能够提供给客户 的是出租处理能力、存储、网络和其它基本的计算资源,用户能够部署和运行任意软件, 包括操作系统和应用程序[11]。 2.PaaS 平台也称作服务 PaaS,就是为用户提供一种类似开发环境的服务,属于分布式的一 种平台服务,为企业和个人提供的研发平台是一个中间件,提供各种各样的服务,例如: - 11 - 江苏科技大学工学硕士学位论文 开发应用程序、服务器、数据库、试验及一些应用服务,用户可以在提供商的平台上开 发自己的应用程序并发布使用。Google App Engine、Salesforce 的 force.com、八百客的 800APP 都属于 PaaS 服务方式。 PaaS 提供商为开发者提供了有利条件,为企业研发所提供的中间件平台服务,涵盖 了数据库和 WEB 应用发布服务器等内容,同时用户还可以根据自己研发软件的需要对 平台进行定制,大大减低了开发的成本和风险。PaaS 为用户提供多种开发语言和工具 (如 Java,python,.Net 等),用户可以根据实际需求开发自己的应用程序并部署到 PaaS 平台上。 3.SaaS 软件即服务模式 SaaS,是一种基于互联网提出的软件服务应用模式,服务提供商 将应用软件统一部署在自己的数据中心,用户通过网络订购相应的软件服务,按照使 用软件的数量、时间的长短等因素进行计费[9]。Salesforce.com、Google Doc、Google Apps 和 Zoho Office 均属于 SaaS 服务方式。 在该服务模式下,SaaS 提供商对软件及其对应的硬件设施进行统一的管理和维护, 用户只需要接入网络就可以随时随地通过浏览器访问所需资源。 2.4 云计算实现机制 为了有效地管理云计算资源,则需要深入了解云计算平台的实现机制,下面以云 计算的 IaaS 为例,说明云计算的实现机制。图 2.7 为云计算 IaaS 层的实现机制。 用户端 管理系统 部署工具 服务器集群 服务目录 资源监控 图 2.7 云计算 IaaS 层的实现机制 Fig2.7 The implementation mechanism of IaaS layer in cloud computing (1)用户端:用于实现用户请求服务的交互。用户可以通过浏览器进行注册、登 录、请求服务、配置和管理。 (2)服务目录:装载用户请求的服务、权限、配置以及管理等信息。用户可以随 时对自己的服务进行重新定制或更新。 (3)管理系统和部署工具:实现用户和资源的管理,对用户进行授权、认证等操 - 12 - 第 2 章 云计算相关技术概述 作,对计算资源和服务进行分配和调度。接收到用户的请求后,管理系统会根据请求 任务内容,智能地调度资源、部署应用,实现资源的动态部署、配置以及回收[10]。 (4)监控:实现云平台资源的使用情况监控。通过节点同步、负载均衡、资源监 控等技术确保资源和用户请求任务间的快速响应。 (5)服务器集群:由大量的服务器虚拟化组成,通过管理系统进行统一的管理, 负责对大量的云计算应用提供满足服务需求的资源。 用户可在用户端通过服务目录选择对应的服务,发送请求后由管理系统调度服务 器集群中的资源,并通过部署工具部署应用来响应用户服务。 2.5 云计算应用中的资源管理 云计算应用中的资源管理主要包括任务分割和资源调度两大块。 2.5.1 云计算应用中的任务分割 在云计算环境下,任务具有数量大、比较分散、需求不一等特点,针对大规模的 计算任务一般通过分割策略,以并行的模式执行,以达到高执行速率。 不同的应用类型有不同的任务分割策略。在云渲染应用中,渲染任务的分割以帧 为单位,根据图片的信息量,分割成若干个能够并行实现的原子任务,由集群中各个 节点同时渲染,从而达到快速渲染、缩短动画片和电影的制作过程及提高制作效果的 目的。在 Google 的 MapReduce 编程模型机制下,将用户输入的数据分割为若干个小 的数据片段,然后与 Map 任务相对应,通过中间文件和 Reduce 过程实现海量数据的 并行处理。 鉴于不同的应用背景下,任务的功能和属性有很大的差异。因此,云计算环境下 的任务分割方法需要和实际的应用任务相结合。 2.5.2 云计算应用中的资源调度 通常情况下,云计算资源管理应实现 4 个服务过程:即资源发现、资源分发、资 源存储以及资源调度。前三个过程是资源调度的前提条件,资源调度是通过一系列算 法和访问模型把所需资源分配到相应的云任务上。资源发现是由网络应用启动并在云 计算中发现适合本任务的资源;资源分发是由资源启动且提供有关资源的信息并寻找 能够利用该资源的云任务;资源发现和资源分发相互补充。在不同应用背景下,不同 的 IT 厂商和科研机构提出不同的云计算资源调度策略,下面以 IBM 的监控代理调度 机制和 Google 的 MapReduce 编程模型的调度机制描述云计算中的资源调度模型。 1.监控代理调度机制 IBM 采用专用的资源监控代理和作业调度器来实现云计算中资源的管理与调度, - 13 - 江苏科技大学工学硕士学位论文 其资源分配与任务调度由 IBM Tivoli Provisioning Manager、Tivoli Monitoring 以及一些 虚拟化组件共同组成。Websphere Application Server 负责检测可用资源、资源调度、供 应及预订;资源供应后,根据操作系统和平台用 Xen 管理程序创建虚拟机;Tivoli Monitoring Server 监控 Tivoli Provisioning Manager 所提供服务器的运行状况(如 CPU、 内存以及磁盘),该方式为云计算通用的管理模式,以虚拟化技术为支撑,简化了作业 调度过程,将云计算的技术核心转移到资源的虚拟化技术上[6]。 2.MapReduce 编程模型调度机制 MapReduce 是一种海量数据成的并行计算模式,是云计算的编程模型和任务调度 模型。MapReduce 把对数据集的大规模操作,分发给一个主节点管理下的各分界点共 同完成,通过这种方式实现任务的可靠执行与容错机制,在每个时间周期,主节点都 会对分节点的工作状态进行标记,一旦分节点的状态标记为死亡状态,则这个节点的 所有任务都将分配给其他分节点重新执行。图 2.8 为 MapReduce 调度模型。 图 2.8 MapReduce 编程模型的调度机制 Fig2.8 The scheduling mechanism of MapReduce programming model MapReduce 在程序的执行过程中有输入文件、Map、写入中间文件、Reduce 以及 文件输出五个阶段[38]。中间文件和 Reduce 过程相结合大大的减少数据在传输过程中 的网络带宽需求,同时数据分割开来以并行的模式执行,从某种程度来说提 MapReduce 模型高了程序的执行效率。 目前,不同的云计算厂商采用不同的资源调度模式,仍没有形成统一的标准和规 范;云计算资源调度的相关研究不多,仍是国内外商业和科研机构研究的关键问题。 - 14 - 第 2 章 云计算相关技术概述 不同的云平台,采用不同的调度算法得到的资源调度策略也不同[39]。因此,如何驾驭 云计算,如何实现资源的有效调度具有重要的研究意义。 2.6 典型的云计算平台—VMware 虚拟化是云计算关键技术,是云计算平台的支撑技术,当前比较成熟的虚拟化技 术供应商主要有:VMware、Citrix 和 Microsoft 等。表 2.1 比较了 VMware、Citrix、 Microsoft 的虚拟化产品。 表 2.1 VMware、Citrix、Microsoft 虚拟化产品比较 Table 2.1 Comparison of virtual product of VMware, Microsoft and Citrix VMware Microsoft Citrix 虚拟化产品 ESXi/ESX HyperV Server Xen Server 支持操作系统 管理工具 优势 Windows, Linux, Mac, DOS 等 vCenter Server, vSphere, vCenter Lab Manager, vCenter, Converter, View 预制应用选择广泛; 支持操作系统选择广泛 Windows, Linux System Center VM Manager HyperV 包含于 64 位 Windows Server 2008 操作系统;根据虚拟客 户机认证数付费 Windows, Linux Citrix Essentials, Lab Manager 开源解决方案; 支持 32 个 CPU; P2V 包含于整个解决方 案 缺点 价格和认证 CPU 支持个数有限 预制应用有限 从表 2.1 可以看出,在虚拟化技术方面,VMware 相对比较成熟,具有广泛的应 用支持和操作系统支持。因此,DEP2C 选择 VMware 的云计算技术来实现原型系统。 下面对 VMware 的虚拟化技术和云计算架构进行详细的研究。 2.6.1 VMware 虚拟化技术 VMware 云计算平台主要依托虚拟化技术。通过虚拟化,我们可以实现物理主机 划分,形成多个独立的虚拟机,以实现资源按需分配;也可以实现物理主机的聚合, 形成庞大的虚拟资源整体,满足大型应用的需求;同时,可以实现应用与物理资源的 隔离,有利于物理资源的复用、管理复杂度的降低、资源的共享以及设备利用率的提 高。借助于虚拟化,有利于实现云计算平台的资源统一管理,使平台部署变得更加灵 - 15 - 江苏科技大学工学硕士学位论文 活、方便,同时,应用与平台无关,可靠性更好,有利于负载均衡的实现和资源节约。 VMware 的虚拟化技术是以资源共享为目标,屏蔽物理资源间的异构性,将服务 器、存储、网络整合为统一的资源池,以更灵活的方式为用户提供所需的物理资源[40]。 VMware 的虚拟化架构如图 2.9 所示。 图 2.9 VMware 虚拟化架构 Fig2.9 The virtualization architecture of VMware 2.6.2 VMware 云计算架构 VMware 认为,云计算是一种能够降低 IT 基础架构复杂性的新方法,它将按需提 供自助管理虚拟基础架构汇集成的高效池,以服务的形式提供计算[41]。 下面以 VMware 的 vSphere 为例说明 VMware 的云计算平台架构。VMware 的 vSphere 虚拟化整个 IT 基础架构(包括服务器、存储器和网络等),聚合所有资源, 提供统一资源管理平台 vCenter,由虚拟化层、管理层和接口层组成,如图 2.10 所示。 图 2.10 VMware 的云计算架构 Fig2.10 Cloud computing architecture of VMware - 16 - 第 2 章 云计算相关技术概述 1.虚拟化层 vSphere 的虚拟化层包括基础架构和应用程序服务两部分。基础架构服务为计算、 存储和网络等可以虚拟化的基础设施资源,基础架构服务包括计算服务、存储服务以 及网络服务;应用程序服务指用于保障上层应用可用性、安全性以及可扩展性的相关 服务[42]。 2.管理层 vSphere 的管理层是由 vCenter 实现。vCenter 为配置和管理虚拟化资源的中央控 制点,整合所有服务器的资源,以共享的模式实现数据中心所有组件的集中管理。 vCenter 作为数据中心单一控制点,提供访问控制、性能监控和配置功能等基本的数 据中心服务。vCenter 的主要功能有:部署新的 ESX 主机,配置各种基础架构组件的 存储、网络以及虚拟硬件特性,管理每个主机的存储要求和资源要求,创建或导入新 的虚拟机,对客户操作系统、虚拟机和底层主机的性能特征进行监视、报告和预警, 以及管理虚拟基础架构不同级别的权限和角色等。 VMware DRS 是 vCenter 的关键组件,可将物理主机的群集作为单个计算资源进 行管理,以确保群集中的负载保持平衡,并强制执行群集范围内的资源分配策略(如 预留、优先级和限制等)。 3.接口层 用户可以通过 GUI 客户端(如 vSphere Client 或 vSphere Web Client)访问 VMware vSphere 数据中心。此外,用户可以通过使用命令行界面和 SDK 进行自动管理的客户 机访问数据中心。 2.7 本章小结 本章主要介绍了云计算的概念和它的几大主要特征、云计算的关键技术、云计算 不同的分类情况等。并且分析了谷歌、微软、亚马逊和 IBM 等主流商业云计算提供 商的云计算平台方案和服务,总结出了部分主流云计算平台的全方位比较,有助于云 用户选择最合适的平台方案。接着扼要地介绍了云计算在中国的发展状况,探讨云计 算的商业价值。最后阐述云计算资源管理的基本服务过程,和 IBM、Google 两家不 同的资源管理策略。本章是全文研究的理论基础。 - 17 - 江苏科技大学工学硕士学位论文 - 18 - 第 3 章 云计算环境下资源调度及优化算法的研究 第 3 章 云计算环境下资源调度及优化算法的研究 3.1 云计算环境下资源调度的研究 目前,云计算资源管理调度可以采用集中式、分布式、层次式和计算经济等方法。 云计算的资源管理涉及很多方面,比如云计算的内部架构、云存储策略、调度组织、 调度策略等等,还应该满足用户的 QoS 要求等。 3.1.1 云计算资源调度模型 在云计算环境下,资源调度模型是指根据一定的资源使用策略将云计算任务分配 给不同的资源,完成资源在资源使用者之间的调度过程,图 3.1 为资源调度模型。 用户 任务 任务分割 任务编码 调度策略 资源编码 资源划分 资源 提供方 任务分配和资源调度 任务完成 资源释放 图 3.1 云计算资源调度模型 Fig3.1 Resource scheduling model of cloud computing 资源调度模型通过任务分割和任务编码形成具有一定优先级的 M 个任务的队列, 通过资源划分和资源编码形成具有一定功能等级的 N 个资源的队列。资源调度的最 终目标是将 M 个任务合理分配到 N 个资源,而任务分割、优先级编码和资源划分、 功能等级编码的目标是实现任务和资源的高效匹配,达到优化平均资源利用率的目 的。 用户在进行科研、学习实践活动时,需要占用一定量的计算资源、存储资源、应 用程序资源。要实现不同学科之间的交叉融合,首先需求对资源进行规范化的整合, 按照不同的功能进行等级划分,进行统一的调度和管理;同时,要满足不同的用户对 特定实验资源的需求,要求资源能够快速分配,高效的完成用户提交的任务。云计算 环境下,需要对实验任务进行分割,以提高任务的执行速度和资源利用率;合理的资 源调度策略有利于实现资源的动态均衡,通过均衡不同实现任务访问的时间也能够从 很大程度上解决平台的负载问题。所以,对任务进行分割、资源进行划分和提出合理 - 19 - 江苏科技大学工学硕士学位论文 的资源调度策略是非常重要的。 3.1.2 任务分割 1.任务定义 任务为用户在特定时间段内所要完成的一系列实验的集合。 2.任务的特点 任务具有以下特点: 1)在特点时间段有效; 2)有一系列实验组成,每个实验对资源的需求不同; 3)任务可以划分为不可分割的原子任务; 4)分割后的各个任务之间在执行时间上存在并行或顺序关系。 按照任务执行的特点,可以将任务之间的依赖关系分为:并行执行任务和顺序执 行任务。 根据不同实验任务功能特点、执行特点、执行时间段以及所需求的资源数进行任 务的分割,将其分割成一系列原子任务,具体分割过程如下: (1)对于一个实验任务来说,分割方法如下,首先,按照实验任务的功能需要实 现的不同功能将实验任务分割为多个子任务,并结合子任务在执行过程中执行顺序是 否可以调整分为有序任务集和无序任务集,其中,无序任务集存放着若干任务可以调 整的子任务,有序任务集存放着若干个按照时间执行的先后顺序进行排列的子任务, 两者同属于该实验任务的任务集;接着,按照任务执行的特点,对于同一类功能任务 中能够并行执行的实验任务继续进行分割,将其分割为多个可以并行执行的原子任务, 以并行任务集的形式存在实验任务队列中。 (2)将所有的实验任务按照用户提交的先后顺序进行(1)的分割过程。 图 3.2 为任务分割的流程图。 - 20 - 第 3 章 云计算环境下资源调度及优化算法的研究 实验任务 按照功能划分为不同的子任务 根据任务执行是否有时间先后序分类分为有序集和无序集 对有序集中任务按照时间排序 将所有任务按照是否可以并行执行分割为若干个 可以执行的原子任务 形成任务集 图 3.2 任务分割流程图 Fig 3.2 Flow chart of task division 在任务分割过程中,应遵循下面规则: (1)对于大量的分割后的原子实验任务来说,在同一时刻,资源需求不同的任 务也是并行存在的。 (2)在整个分割过程中要保证所有原子任务中最大的资源需求的最大配置小于 或等于所有资源池中资源节点的最大的资源配置。 (3)在实验任务最小化分割过程中要略小于或相当于当前资源池中最小的资源 节点拥有配置,否则会造成大量资源的浪费和不必要的资源迁移。 (4)所有实验任务应满足所需要的应用程序需求数和所有资源节点应用程序需 求种类。 3.1.3 资源划分 1.资源的定义 资源主要分为两部分:物理资源和虚拟资源。虚拟资源为物理服务器、存储等经 过虚拟化,形成资源池,建立满足不同应用需求的虚拟机来满足用户实验的实际需求, 虚拟机的属性特点为 CPU、内存、存储容量、应用程序等;物理资源为物理主机,承 载对应的实验运行环境,属性内容包括 CPU、内存、存储容量、应用程序等。将物理 主机或者虚拟机均视为一个资源的节点。 2.资源的特点 资源具有以下特点: (1)将物理资源和虚拟资源分别作为一个大的资源池物理资源池和虚拟资源池,可 - 21 - 江苏科技大学工学硕士学位论文 以划分为若干个满足不同实验功能需求的功能资源池; (2)功能资源池由一组虚拟机或者物理主机组成,资源池内的物理主机或虚拟机具 有相当的功能; (3)不同资源池的容量不同,虚拟机或主机的配置也不一定相同; (4)每个虚拟机或者物理主机拥有 CPU、内存、存储容量、应用程序等资源。 特定资源池内的虚拟机或物理主机的 CPU、内存、存储容量可以实现动态的负载 均衡。 根据实验任务对资源的需求和实验任务的分割模式,以及资源集群所拥有的资源 总数、资源池以及资源节点在划分过程所需要额外的资源开销,将资源集群划分为若 干功能资源池,每个功能资源池包含若干虚拟机或物理主机资源,具体划分过程如下: (1)根据不同的操作系统将虚拟资源池或物理资源池分为两组,并设定操作系 统配置决定因子 OSQ ,对于第 i 个资源池来说,如果 i  OSQ ,该资源池内所有资源 节点配置的操作系统均为 Windows;再则 i  OSQ ,该资源池内所有资源节点的操作 系统均为 Linux; (2)按照资源所能完成的任务将资源集群划分为若干功能资源池,每一个资源 节点能够完成实验任务中某一类功能; (3)将能够并行执行实验任务的资源节点形成形成特定功能资源池; (4)按照资源池的规模和资源节点配置需求将功能资源池划分为子资源池。 图 3.3 为资源划分的流程图。 服务器集群 按照操作系统进行分组 设定操作系统配置因子OSQ 按照功能进行划分资源池 按照并行程度形成特定资源池 按照资源池规模和资源节点配置需 求继续划分 形成功能子资源池 图 3.3 资源划分流程图 Figure 3.3 Flow chart of the resource division 在资源划分的过程中,遵循下面规则: - 22 - 第 3 章 云计算环境下资源调度及优化算法的研究 (1)资源池中的资源节点配置至少能够承担一种任务; (2)能够并行执行实验任务的资源池拥有较高的功能等级,并行程度越高,功 能等级就越高; (3)同一个资源池内资源节点的处理器的个数相同; (4)资源节点的配置中 CPU、内存、存储及其应用程序的个数配置成同比增长 关系,CPU 配置份额越大对应内存、存储的配置也越大、对应承载应用程序的个数也 越多; (5)资源池中的所有资源节点之间能够实现动态的负载功能,当某资源节点资 源不足时,将其它资源节点所有拥有资源中预留的份额均衡至该资源节点中。 3.1.4 资源管理的调度策略 1.调度策略 调度策略主要功能是实现任务的调度和资源的分配。任务调度和资源的分配主要 是完成特定状态下资源队列和任务队列最佳匹配映射。 对特定任务进行资源预分配时,遵循下述策略: (1)根据任务的资源需求,同一个资源任务优先选择能够满足其任务完成需求 的资源池,该资源池具有以下属性:实验任务的原子任务序列中原子任务最大的并行 程度小于等于选定资源池中资源节点的个数;原子任务最大并行程度任务需求的资源 配置小于等于功能相同能够执行并行任务的资源节点配置。 (2)当一个资源池无法满足任务需求的资源节点配置,以最邻近的模式依次搜 索相邻的资源池中是否有满足功能需求的资源节点。 (3)分配过程中,首先判断该任务所需要的操作系统运行环境,若仅需 Windows 操作系统运行环境,则从第 1 个资源池开始配置;若仅需 Linux 操作系统运行环境, 则从(最后一个资源池)第 N 个资源池开始配置;对于混合性需求的操作系统环境 来说,从操作系统配置决定因子 OSQ 依次配置。 (4)任务的配置需求满足的过程中以应用程序的需求为首选因素,若资源节点 中配置有满足该任务需求的应用程序,再比较 CPU 的值是否满足任务资源需求,若 匹配则该资源节点便被选中,执行该原子任务。 (5)对于并行程度大于 1 的原子任务来说,在执行过程中需要有满足其并行程 度值的资源节点,开始执行前,满足需求的资源节点便处于等待任务执行状态,以并 行的模式完成原子任务。 (6)对于优先级为 0 的实验任务来说,当资源节点空闲时,便分配其资源,并 且资源一旦分配,只有当任务执行完成才能释放;对于优先级为 0 的原子任务来说, 在整个任务的执行过程中,所在最邻近资源池的资源有空闲时,便分配其资源,并且 - 23 - 江苏科技大学工学硕士学位论文 资源一旦分配,只有当任务执行完成才能释放。 2.调度策略过程 下面以具有 m 个子任务的实验任务Ti 为例,描述任务执行的过程中的资源调度: 1)该实验任务处于资源预分配状态, Ti  {Ti,1,Ti,2,Ti,3,...,Ti,m} ; 2)根据上述资源调度策略中(1)和(3)选择最邻近满足功能需求的资源池 RPj , RPj  {VM j,1,VM j,2,VM j,3,...,VM j,k }; 3)选中任务编码中优先级中整数部分为 1 的子任务Ti,x , 将该子任务放入资源调度器,该子任务处于资源预分配状态,根据优先级的小数 部分和该子任务的应用程序需求选中资源池 RPj 或 RPj 最邻近资源池中的处于空闲状 态的一个资源节点或资源节点组合,用来执行该优先级的子任务,该资源节点的运行 状态由空闲转化为忙碌,直到任务完成,该资源节点被释放,运行状态返回为空闲; 同时,资源调度器记录该子任务执行的开始时间TSi,x 和结束时间TEi,x ;当该子任务执 行完成时,将该子任务的生命周期状态置为终止状态; 4)将任务编码中优先级中整数部分为 2 的子任务Ti,y 放入资源调度器,进行资源 预分配,继续过程; 5)当对任务编码中优先级中整数部分为 1 的子任务进行资源预分配后,该资源 池仍然有资源节点空闲,对优先级小于 1 的无序任务集中的无序子任务进行搜索,直 到空闲的资源节点能够满足其配置需求,然后将该子任务继续过程 3); 6)对于优先级整数部分为 0 的原子任务来说,若优先级大于 1 的原子任务均执 行完成,其按照最邻近功能资源池中资源满足情况,依次分配; 7)直到中所有的原子任务处终止状态,该任务执行完成,处于终止态。 整个任务Ti 执行过程,花费的总时间为 COSTi : m  COSTi  (TEi,x  TSi,x ) x1 (3.1) 第 i 个资源池中第 k 个虚拟机的 CPU 的预留值 RCPUi,k 设定为: RCPUi,k  CPUi,k TCPU j,m (3.2) 3.2 资源管理系统的详细设计 云计算资源管理系统详细结构如图 3.4 所示。引入任务分割、资源划分策略以及 资源调度策略来实现实验资源的规范化统一管理调度,同时,引入任务池和资源池的 概念,将任务和资源分别聚合在一起,以资源池的模型来执行任务或提供资源,对用 户来说,不需要了解享用资源所处的位置,对资源来说,不需要知道所完成任务的对 应具体用户,只需要执行任务池的一个个任务,直到所有的任务执行完成。 - 24 - 第 3 章 云计算环境下资源调度及优化算法的研究 图 3.4 资源管理系统详细结构图 Figure 3.4The detailed composition of resources management system 资源管理系统主要有三个关键部分:任务管理器、资源管理器和资源调度器,三 者协同起来实现实验平台的运行管理。具体说明如下: 任务管理器主要负责用户提交的实验任务的处理,具有任务分析、任务分割、优 先级编码三个部分组成。任务管理器接收到用户的请求后,首先对任务进行分析,按 照任务执行的时间需求和用户的优先级插入原有的任务队列,然后按照任务的功能特 点和执行特点对任务进行分割,得到一个个原子实验任务,最后将原子任务进行编码, 最终形成有一系列用户所提高的任务组成的任务池。 资源管理器主要负责实验设备资源的接入管理,并向用户提供资源服务,具有资 源分析、资源划分、功能等级编码三个部分组成。资源管理器将接入的物理设备分为 两类:物理资源和虚拟资源。当接入物理设备时,首先根据该资源是否虚拟化进行分 组,然后按照功能属性组成不同能够执行不同任务的功能资源池,每个功能资源池有 若干个功能相近的物理资源节点或者若干个功能相近的虚拟机资源节点组成,最后对 这些资源节点进行功能等级编码,形成能够满足用户需求的资源池。 资源调度器主要负责任务池中任务的分配和资源池中资源的调度,实现任务和资 源的最佳匹配映射。同时,资源调度器具有任务检测功能和资源检测功能,对任务的 执行和资源调用进行全生命周期的管理。当任务执行完成时,反馈信息给用户,同时 释放该任务所分配的资源。 对用户来说,可以通过各种各样的客户端接入开放性的资源管理平台,可以是个 人电脑、智能手机、PDA 等终端设备,只要拥有一定的权限,就可以访问实验资源, 完成相应的科研实验活动。 - 25 - 江苏科技大学工学硕士学位论文 对资源来说,可以是具有专有性能的计算设备,也可以是服务集群,或是高性能 的服务器,通过直接接入或者虚拟化后,统一配置成若干个虚拟机来执行用户所提交 的任务,而当系统升级或实验室设备更新时,可以根据需求作为新的资源节点接入管 理平台。 对管理员来说,将任务和资源进行统一的组织管理,以实现平台的资源共享。管 理员可以管理所有接入平台的用户并设定用户权限,并制定调度策略对资源进行管 理。 资源调度根据资源调度策略实现任务和资源的合理匹配,实现资源的有效利用和 用户提交任务的响应速率,由任务管理和资源管理两部分协同完成。在任务执行和资 源分配的过程中,资源调度相关的交互模块有任务管理器、资源调度器等。资源调度 服务类图具体如图 3.5 所示。 ResourceAllocation <> RequestService +GetResource() 1 1 * TaskQueue -TaskProxy 1 * ResourcePool -FunctionProxy 1 * * SubTask +ExecuteOnCode() FunctionResourcePool +ExecuteTask() 图 3.5 资源调度类图 Fig 3.5 Class diagram of resource scheduling 而图 3.6 说明了具体任务执行的时序流程图。用户请求递交给 ReguestService 接 口处理,ReguestService 通过资源调度(ResourceAllocation)来完成用户的请求。 - 26 - 第 3 章 云计算环境下资源调度及优化算法的研究 DEP2C 任务队列 任务管理器 资源调度器 资源管理器 用户 1:提交任务 2:提交成功 3:提交失败 4:任务分析和编码 5:申请资源 6:分配资源 7:资源申请失败 10:返回用户 9:返回 8:任务执行成功 图 3.6 任务执行时序图 Figure 3.6 Sequence diagram of task execution 3.3 资源调度优化算法 在计算机领域,资源调度一直以来都是专家学者们很热衷研究的问题,在调度这 个问题上,目前已有很多的研究成果,现在我们所要研究的就是对资源的调度进行更 优效率的优化,已满足用户的越来越广泛的请求。 在云计算的服务中资源调度作为分布和集群计算中的一个关键问题,它对任务执 行效率的高低、系统资源数的多少和整体性能的优劣等都有着重要的影响。因此,已 有很多云计算厂商和科研机构已经加大力度开始研究如何优化资源调度,一般采用一 些仿生群智能的算法,在一定程度上是资源管理得到优化,特别是在动态负载平衡方 面和基于 Agent 的分布计算方面都取得很好研究成果[3]。从优化调度策略角度来讲, 群智能调度算法是网格资源调度中应用最广泛的,目前常用的算法有: (1)遗传算法。遗传算法是基于自然界遗传和基因进化规律的搜索算法,它以 物进化为原型,具有很好的收敛性,并能结合已有的结果在搜索空间产生新的结果。 具有收敛速度快,通用性强,处理数据是并行发生的不会轻易陷入局部最优等优点[3]。 但是,遗传算法也存在一些比较明显的缺点:搜索效率低,理论还不成熟,收敛定理 证明不成熟等。 (2) 蚁群算法。是一种用来在图中寻找优化路径的机率型算法,它由 Marco - 27 - 江苏科技大学工学硕士学位论文 Dorigo 于 1992 年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现 路径的行为,初步的研究表明该算法具有许多优良性质;针对 PID 控制器参数优化设 计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表 明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值[12]。其主要特点就 是:通过正反馈、分布式协作来寻找最优路径。 (3)粒子群算法:粒子群(Particle Swarm Optimization,PSO)算法是模拟鸟群在 觅食中的行为,演化成算法。粒子群算法模拟动物集群行为,模仿群体中个体共享信 息的特点,让所有群体在求解空间内由无序变为有序的过程,最终获得最优解。由于 它较少的参数、简单的结构,成为研究热点同时广泛应用到很多自然、工程领域。PSO 的优点是:实现起来简单容易,无需调整很多参数。当前,已成功运用在神经网络、 函数优化、遗传算法、模糊系统等领域。但粒子群算法也存在很明显的缺陷,由于搜 索空间内有局部极值,它就很容易陷入局部最优,在进化后期也会导致收敛速度变慢、 鲁棒性变差等。 (4)人工蜂群算法:人工蜂群算法(artificial bee colony algorithm,ABC)是一种模 拟蜜蜂群体觅食行为的智能算法[15],它的参数简单易设置,过程易于实现,并受到各 个领域学者的关注和研究。Karaboga 把蜂群算法与函数的优化相结合,同时和微粒群 算法、遗传算法及差分算法进行区别和比较,试验表明蜂群算法在效率和时间上具有 更好效果。 在自然界中,蜜蜂的生存形式是群体,它们间食物源信息的传递是通过舞蹈传递 的。在蜂群中,蜜蜂的角色是不同的,这是根据寻找食物与采蜜的任务不同而不同的, 一般把发现食物的蜜蜂称作被雇用的蜜蜂,也称作引领蜂。它的作用是发现食物源所 在位置,并把食物源的信息按照特定的概率发送给其它蜜蜂,与它们共享。未被雇用 的蜜蜂又可以分成侦查蜂与跟随蜂两种。跟随蜂的智能是按照引领蜂传递的信息确定 出食物源具有的收益率,收益率高低决定了是否该选择这个食物源去采蜜,而侦查蜂 则是完成寻找新食物源的任务。 作为一种新兴的群体智能算法,蜂群算法也存在后期时搜索速度变慢、过早收敛、 种群多样性减少等难题。本文结合 ABC 算法的特性,并通过引入一个控制因子,自 适应地调整搜索空间寻找最优蜜源位置,提出了一种改进的人工蜂群算法—带控制因 子的自适应人工蜂群算法。其主要思想是:在搜索过程中,通过控制因子来动态调节 地蜂群个体之间信息共享程度的强弱,使算法避免陷入局部最优解。 3.1: - 28 - 第 3 章 云计算环境下资源调度及优化算法的研究 表 3.1 四种算法的优缺点 Table3.1 The advantages and disadvantages of four kinds of algorithm 算法 优点 缺点 适用范围 GA ACO PSO ABC 收敛速度快,通用性强 通过个体间信息的共享 形成正反馈机制,有效 提高全局寻优效率 收敛速度快,设置参数 少 蜜蜂按照劳动分工采用 不同的搜索策略,相互 协作完成寻优工作;全 局寻优能力强;基于繁 殖行为的蜂群算法总保 留每一代最优个体。利 用蜜蜂之间寻优的正反 馈机制加快了全局寻优 过程 易早熟收敛、在迭代后 求解组合优化问题和 期收敛速度慢 连续优化问题 在迭代初期信息缺乏, 蚂蚁寻优较盲目,收敛 速度慢;由于更新能力 主要求解组合优化问 有限,易陷入局部最优 题,并能求解一些连续 解,出现停滞情况;当 优化问题 问题规模增大时,算法 效率下降明显 在迭代后期难以保证 种群多样性,易陷入局 部最优解,且搜索精度 不高 主要求解连续化问题, 并能求解一些组合优 化问题 在接近全局最优解时, 搜索速度变慢,种群多 求解组合优化问题和 样性减少,甚至陷入局 连续化问题 部最优解 虽然 GA、ACO 和 PSO 三者都比蜂群算法的发展历史悠久,前三者的研究及应用 也比较成熟。但由上表可知,蜂群算法因有劳动分工和协作机制,算法更灵活,易与 其他技术结合以改进原算法,同时,既能解决连续优化问题,又能求解组合优化问题, 可见该算法其具有广泛的适用性。 3.4 基于 QoS 的任务分类 服务质量 QoS(Quality of Service)是互联网络性能的一种安全机制,在云计算环境 中,QoS 是衡量用户使用云计算服务的满意程度的重要因素,云计算服务的功能与性 能评价将不再是采用传统服务的评价标准(如速度、性价比等),而是以用户满意度为 目标,用服务质量来衡量。云计算为各类用户提供服务,满足不同用户的不同需求, 而用户对资源需求有着不同的偏好,例如,有些用户需要实时性保证,有些用户需要 - 29 - 江苏科技大学工学硕士学位论文 低廉的费用,而有些用户需要较强的系统稳定性或安全性等。云计算的商业性特性, 使其需要为不同用户提供不同满意度的服务质量,由于用户的多样性,对云计算的作 业调度和资源分配提出了更高的要求,按照 QoS 参数要求先将任务进行分类处理, 可以更准确及时地将任务分配到最合适的资源上,一般考虑的 QoS 参数有以下几点: (1)网络带宽:当客户对通信带宽要求较高时,例如多媒体数据传输,就需要优先考 虑带宽要求,提供较高带宽。 (2)服务完成时间:对于实时性要求较高的用户,需要在尽可能短的时间内完成任务, 以及时响应用户提交的作业。 (3)系统可靠性:对于运行大量复杂任务的用户,需要云计算中心提供稳定可靠的性 能支持,例如海量数据存储服务。 (4)所需费用:云计算按需付费,使用费用是用户关注的一个因素,对于希望廉价的 服务的用户来说,费用是一个衡量标准。 因此针对不同用户需求,设定不同的 QoS 参数,按照这些参数来衡量用户的满 意程度,从而建立不同的量化评价标准。 云计算系统中资源具有高度动态性和异构性,资源环境所固有的不可靠状态,使得 云计算系统出现大规模资源失败的可能性大大增加。而高可靠性是云计算系统的内在 要求和至关重要的特点。要保证容错和可靠性更高,容错调度是云计算系统实现它们 的重要方法。同时 QoS 表示为获得应用的要求功能所必需的一组定量和定性的特征。 在云计算系统中,QoS 不能仅被限制在云计算中处理机的处理能力和存储能力还应扩 展到通信效率和可靠性上。 3.5 MapReduce 模式下的调度 MapReduce 模式中把容错处理、负载均衡和并发处理等问题存入函数库(lib)里, 用户通过 MapReduce 接口就能自动并发执行大规模的计算。在 MapReduce 编程模式 中,可将计算执行的过程抽象成三个角色,分别是:Master、worker 和 user:Master 负责负载均衡、任务分配、容错处理,它是系统的中央控制器,它为每一个 Map 和 Reduce 任务存储它们的状态、Worker 机器的标识、Map Worker 的 Key/Value,并进 行 Map 操作,存储 Key/Value 结果,最终把地址返回至 Master;Reduce Worker 的任 务是将 Key 到 Value 的地址按照 Key 化简,最终把结果返回给用户程序;Worker 的 - 30 - 第 3 章 云计算环境下资源调度及优化算法的研究 任务是将 Master 中接收到的任务进处理,同时负责数据的传输通信;User 定义为用 户端,用来控制整个计算过程,实现 Map 与 Reduce 函数[3]。 MapReduce 的运行模型如图 3.7 所示。图中有 M 个 Map 操作和 R 个 Reduce 操作。 简单说来,一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素 进行指定的操作。事实上,每个元素都是被独立操作的,而原始列表没有被更改,因 为这里创建了一个新的列表来保存新的答案。这就是说,Map 操作是可以高度并行的, 这对高性能要求的应用以及并行计算领域的需求非常有用。而化简操作指的是对一个 列表的元素进行适当的合并。虽然它不如映射函数那么并行,但是因为化简总是有一 个简单的答案,大规模的运算相对独立,所以化简函数在高度并行环境下也很有用[30]。 在编程的时候,开发者需要编写两个主要函数: 原始数据 1 原 始 数 据 原始数据 M 2 Map Map … Map Reduc … Reduc e e 结果 1 结果 R 图 3.8 MapReduce 的运行模型 Fig.3.8 Processing model of MapReduce Map 和 Reduce 的输入参数和输出结果根据应用的不同而有所不同。Map 的输入 参数是 in_key 和 in_value,它指明了 Map 需要处理的原始数据是哪些。Map 的输出 结果是一组对,这是经过 Map 操作后产生的中间结果。在进行 Reduce 操 作之前,系统已经将所有的 Map 产生的中间结果进行了归类处理,使得相同 key 对 应的一系列 value 能够集结在一起提供给一个 Reduce 进行归并处理,也就是说 Reduce 的输入参数是(key, [value1,…, valuem] )。Reduce 的工作是需要对这些对应相同 key 的 value 值进行归并处理,最终形成(key,final_value)的结果。这样,一个 Reduce 处理一 个 key,所有 Reduce 的结果归并在一起就是最终的结果。 当用户程序调用 MapReduce 函数,MapReduce 操作的执行流程为: (1) 用户程序首先调用的 MapReduce 库将输入文件分割成 M 个数据片段,每个数 据片段的大小一般从 16MB 到 64MB(可以通过可选的参数来控制每个数据片段的大 小)。然后用户程序在机群中创建大量的程序副本。 - 31 - 江苏科技大学工学硕士学位论文 (2) 这些程序副本中的有一个特殊的程序 Master。副本中其它的程序都是 worker 程序,由 Master 分配任务。有 M 个 Map 任务和 R 个 Reduce 任务将被分配,Master 将一个 Map 任务或 Reduce 任务分配给一个空闲的 worker。 (3) 被分配了 Map 任务的 worker 程序读取相关的输入数据片段,从输入的数据片 段中解析出对,然后把对传递给用户自定义的 Map 函数,由 Map 函数生成并输出的中间 对,并缓存在内存中。 (4) 缓存中的 对通过分区函数分成 R 个区域,之后周期性的写入到本 地磁盘上。缓存的对在本地磁盘上的存储位置将被回传给 Master,由 Master 负责把这些存储位置再传送给 Reduce worker。 (5) 当 Reduce worker 程序接收到 Master 程序发来的数据存储位置信息后,使用 RPC 从 Map worker 所在主机的磁盘上读取这些缓存数据。当 Reduce worker 读取了所 有的中间数据后,通过对 key 进行排序使得具有相同 key 值的数据聚合在一起。由于 许多不同的 key 值会映射到相同的 Reduce 任务上,因此必须进行排序。如果中间数据 太大无法在内存中完成排序,那么就要在外部进行排序。 (6) Reduce worker 程序遍历排序后的中间数据,对于每个唯一的中间 key 值, Reduce worker 程序将这个 key 值和它相关的中间 value 值的集合传递给用户自定义的 Reduce 函数。Reduce 函数的输出被追加到所属分区的输出文件。 (7) 当所有的 Map 和 Reduce 任务都完成之后,Master 唤醒用户程序。在这个时候, 在用户程序中对 MapReduce 调用才结束。 由于 MapReduce 在成百上千台机器上处理海量数据,所以容错机制是不可或缺 的。Master 会周期性地给 Worker 发送 ping 命令,如果 Worker 没有应答,则 Master 认为该 Worker 失效,终止对这个 Worker 的任务调度,把失效 Worker 的任务调度到 其他 Worker 上重新执行。 3.6 本章小结 本章主要介绍资源调度中的任务分割、资源划分、资源调度等关键技术和常见优 化算法的比较,以及 MapReduce 模式下调度的运行机制。 - 32 - 第 4 章 基于 MABC 算法的云计算资源调度策略 第 4 章 基于 MABC 算法的云计算资源调度策略 4.1 人工蜂群算法的基本原理 在自然界中,经过长期的自然进化后,蜜蜂形成了群体的生存方式,而它们对生 存的根本(蜜源)的寻找已经形成了本能,这是蜜蜂群体智慧的体现。Von Frisch 研究 揭示蜜蜂通过跳舞摆尾等形式来传达与共享蜜源的信息。采集到蜜源的蜜蜂,返回到 蜂巢后翩然起舞,其他蜜蜂就会沿直线爬行,然后再转向另一种舞蹈,其轨迹呈“8” 字形。蜜蜂寻食分三步走:发现食物来源、发现食物来源的蜜蜂及查看蜜源是否属实 的蜜蜂。蜜蜂采蜜过程有三种行为体现:寻找食物源(即蜂蜜)、采蜜及采蜜结束离开 蜜源。 蜂群采蜜工作图见图 4.1。 图 4.1 蜜蜂采蜜工作图 Fig4.1 Figure of bees gather honey 4.2 人工蜂群算法(ABC algorithm)的数学模型 ABC 算法中,人工蜂群主要由以下 3 部分组成:引领蜂(employed bees)、跟随蜂 (onlookers)和侦察蜂(scouts) [14]。此设计的算法在求其解以及综合优化算法的时候,将 - 33 - 江苏科技大学工学硕士学位论文 食物源位置建立成三维空间的坐标点,蜜蜂寻找蜜源的过程就是从解空间中搜寻最优 解的过程。在算法中,蜜源的位置对应优化问题中一个可能的解,蜜源的花蜜量对应 解的质量[12](即适应度)。蜂群会首先生成 m 个初始解(m 个蜜源),第 i 个解的位置 为 xi=(xi1 , xi2 , xi3 ,… xim),它是一个 d 维空间。引领蜂对蜜源进行搜索并记忆蜜源的 花蜜量;通过比较蜜源花粉量的优劣来对蜜源的质量进行排名,并会把这一信息传递 给跟随蜂。跟随蜂根据蜜源的收益率来选择是否对该蜜源进行采蜜,收益率越高的蜜 源被选择的概率也就越大。在确定了蜜源之后,跟随蜂也会在附近产生一个新的蜜源, 在比较两个蜜源适应度的大小,保留质量好的蜜源。蜂群就是通过循环寻找蜜源来求 得最优解的。当某个蜜蜂在若干代循环后依然没有更新蜜源时,它就会放弃该蜜源成 为侦察蜂,到别的地方寻找新的蜜源。 在算法中,引领蜂和跟随蜂对于每个蜜源 xi 的位置更新: vij  xij  rij (xij  xkj ) (4.1) 产生新解 vi 即对 xi 进行一次邻域搜索,若新解 vi 的适应度值优于原解 xi 的适应度 值,则用 vi 替换 xi 否则保持 xi 不变。式中 vi j 为新的蜜源位置, xi j 为蜜源 xi 的第 j 维, xkj 为随机位置为 k 的蜜源第 j 维位置。k 1, 2,...., m , j 1, 2,...., d ,k,j 为 2 个随 机数, k  i (k 为 i 的领域解);其中, rij 1,1 是一个随机数,它控制 xi j 领域的生 成范围。 跟随蜂根据蜜源的花蜜量大小来确定每个蜜源的选择概率。选择概率 Pi 则按照下 式确定: Pi  fi m  fi i 1 (4.2) 式中 fi 为第 i 个解的适应度值;m 是蜜源的个数。 此设计的算法包含一个用来反应解被改变次数的临界值:“limit”,若是某蜜源 xi 经 过“limit”次循环搜索后依然不能够被更新,那么该位置将被放弃,对应该位置的引 领蜂就会转变成为侦察蜂。侦察蜂通过(4.3)式随机产生一个新的蜜源来替换当前 的蜜源: xi j  xj min  rand (0,1)( xj max  xj min ) (4.3) 式中 j∈{1, 2, …, d}, rand(0,1)为随机数,xmax 、xmin 分别为最大、最小值。 4.3 改进的人工蜂群算法与云环境下的资源调度 ABC 算法有很多优点,但是它作为一种新的随机优化算法,仍然存在不完善的地 方,主要表现为在算法后期存在搜索速度变慢、过早收敛、种群多样性减少等难题。 - 34 - 第 4 章 基于 MABC 算法的云计算资源调度策略 本文结合 ABC 算法的特性,并通过引入一个控制因子,自适应地调整搜索空间寻找 最优蜜源位置,提出一种改进的人工蜂群算法——带控制因子的自适应人工蜂群算 法。其主要思想是:在搜索过程中,通过控制因子来动态调节蜂群个体之间信息共享 程度,使算法避免陷入局部最优解。基于这种改进的人工蜂群优化算法,云计算服务 集群可以快速实现资源发现、资源匹配、产生调度、执行任务。 ABC 算法寻找收益率高的蜜源(最优解)通常是由个体搜索以及个体与邻域之间的 信息共享提供的。随着算法的进行,搜索空间会缩小,个体之间的信息交流也相应地 变小,此时就会陷于局部搜索区域。因此,在搜索过程中,我们对蜜源位置更新式(4.1) 中引入一个控制因子,可以动态调节邻域个体之间信息共享的强弱,此时蜜蜂蜜源位 置更新公式为: vij  xij    r  (xij  xkj ) (4.4) 其中,  称作控制因子。 刚开始搜索时,蜂群广泛分布在整个搜索空间中,并通过  适当减弱个体之间的 信息共享程度,避免蜜蜂飞过最优蜜源所在空间。随着搜索进行,应该通过增大控制 因子  值来增强蜜蜂与邻域个体之间的信息共享程度,从而跳出局部最优,继续搜索 实现全局收敛。随着进化代数的增加,控制因子  应该由小到大地增大,同时搜索初 期个体之间信息共享较弱的时间不能过长,故  由较小的初值迅速增大到一定值,然 后根据不同情况对蜜蜂和邻域个体的信息共享程度进行动态调节。因此,随着进化代 数的增加因子  呈现非线性的动态变化,其表达式为:   (1 )  max (4.5) 其中:   1 (0 / max )1/n (4.6) 4.6 式中,n 为进化代数, 0 , max 为常数。当 n=1 时,  = 0 ;当 n→∞时,  → max 。进化的不断进行  也会呈由小到大渐变式的变化,因此,为了保证蜂群一开 始就有较好的探索能力,0 取值不能太小。在进化后期,max 取值不能太大。通过因 子理论和实验分析,  的取值范围在[0.1,1.2]之间比较合适。 MABC 算法求解过程如下描述: Step1 根据初始化蜂群的规模大小、进化代数,随机生成解(蜜源)xi ( i = 1… n),计算每个解 xi 的适应值。 Step2 引领蜂进行搜索蜜源位置,根据式(4.1)产生新的解 vi,通过与当前解 xi 进行对比,选择适应度更优的解。 Step3 计算与 xi 相关的概率值 pi,计算其适应度值。跟随蜂根据 pi 选择蜜源 (解) 并根据式(4.4)产生新的蜜源(解),与当前的蜜源进行对比,若质量优于当前蜜源则保 留,否则放弃此蜜源。 - 35 - 江苏科技大学工学硕士学位论文 Step4 蜂群记录蜜蜂觅食同一蜜源的次数,当某个蜜源被觅食的次数超过临界值 limit 而没有得到改善时,表明此解可能已经陷入了局部最优。蜜蜂就会放弃此蜜源成 为侦查蜂,重新回到解空间中产生新的蜜源将其换掉。 Step5 将最接近蜜蜂采蜜行为的解录入在案。 Step6 看算法是不是已经触发停止,若触发,并输出最接近蜜蜂采蜜行为的解, 否则转 Step2。 4.4 参数设置及计算资源优劣度评判条件 以 Google 的 Map/Reduce 云计算模型为参照例子,算法架构的各单元分成两个方面, 分别为:一方面是独立的资源分配节点(Master Job Tracker),另一方面为此模块所包括 的三维空间各集群点的一个附属作业任务点(Slave Task Tracker),主节点主要实现蜜蜂 从寻找蜜源到呼唤附近同伴来采蜜,最后忙完回蜂巢的整个过程的所有作业,所以这 些作业的信息源来源于各个相异作业的镜像分片,而且其镜像分片是把信息存储在三 维空间点上[3]。Map 端的输出数据首先被写入本地磁盘,当本机任务完成后通知 JobTracker,然后 Reduce 端在得到 JobTracker 的通知后会发出 HTTP 请求,利用复 制的方式从相应的 Map 端拉回其输出。这样的方式只能等该 Map 任务完成后才能开 始执行 Reduce 任务,并且 Map 任务和 Reduce 任务的执行是分离的。 一种改进思想是使 Map 任务和 Reduce 任务能够以管道的方式执行,即 Map 任务开始产生输出后直接发送给相应的 Reduce 任务,这需要在用户提交作业后 JobTracker 就分配相应的 Map 任务和 Reduce 任务,并将每个 Map 任务的位置发 送给 Reduce 任务。每个 Reduce 任务启动后就联系每个任务并打开一个 Socket。当 每个 Map 输出一产生后 Mapper 便决定发送的分区(Reduce 任务)并通过适合的 Socket 直接发送。 Reduce 任务接收从每个 Map 任务收到的管道数据并将其存储在内存缓冲区中, 在需要时将已排好序的缓冲区内容写到磁盘。一旦 Reduce 任务得知每个 Map 任务 均已完成,它执行已排序内容的最终合并,然后调用用户自定义的 Reduce 函数,将 输出写入 HDFS。 在寻找合适的计算节点时,首先,该从节点开始计算自身的资源,如果其剩余资 源足以满足用户提交作业的用量,则优先分配自身资源,如果资源已不足以分配给用 - 36 - 第 4 章 基于 MABC 算法的云计算资源调度策略 户的最小计算资源量,则根据搜索算法开始搜寻云环境中其他合适的计算资源,本文 介绍的蚁群优化分配算法就是在这一环节中实现,为了避免搜索停滞,搜索将在一定 范围内进行,目的是为了减小算法本身所带来的网络开销,如果在所有子节点中仍然 没有合适资源,则从节点报请主作业调度节点移走该节点集群中的用户数据镜像分片。 将 slave 节点域作为一个无向图 G (V , E ),其中 V 是区域 Area 中所有 slave 节点的集合,E 是连接各 slave 节点的网络集合。在云计算网络中均匀地划分成若干 个子区域,然后给每个区域分配相同个数的蜜蜂,每个组的蜜蜂在各自的区域进行搜 索,寻找合适的计算节点,也就是在 E 中寻找一条最优的路径,其度量标准要考虑的 有如下参数: ① 预计执行时间: time _cos t ( e) ,指路径 e 尽头的的计算资源处理这样作业要 消耗的时间。 ② 网络延迟:delay (e ) ,指路径 e 产生的最大网络延迟。 ③ 网络带宽:bandwidth( e) ,指路径 e 所提供的网络最大带宽。 将预计执行时间和网络延时综合后用变量 td m(t , e) 表示在 t 时间段内该 e 尽头 i 计算资源的所用量。 假设某虚拟机资源 VM i 的特征集合: Ri = {ri1 , ri2, rim}, m∈ [1 ,3] 其中, rim 表示一个 K 维对角矩阵,分别表示 CPU、内存和带宽。 用户对云计算资源需求的多样性与偏好性,如何作 Qos 保证。任务的 QoS 描述 通常可以采用任务完成时间、内存、网络带宽等参数指标来量化 QoS,如以任务完成 时间 QoS 作为评判标准,则可包括任务开始时间、全部完成时间、结束时间等,可选 取任务全部完成时间作为评判指标。 通常第 i 类任务的一般期待向量可以描述为: Ei = {ei1 , ei2, eim},m ∈[1 ,3] 其中 eim 分别表示 CPU、内存、带宽等的一般期待,且满足: 最终确定目标资源和路径的过程就是寻找路径最短且 res(e) 尽量小的路径和资 源的过程,其中 A,B,C 为三个约束条件的权重,TL,EL 和 DL 为其边界限制条 件,即在云计算环境满足 QoS 的限制条件。 - 37 - 江苏科技大学工学硕士学位论文 4.5 本章小结 本章仔细叙述了关于蜂群算法的原理,还有建立的算法的模型,针对人工蜂群算 法的优缺点提出了一种改进的人工蜂群算法,此算法对云计算资源管理具有更好的优 化效果。其次参照云运算的数值设定的需求,设计了蜂群算法来提高搜寻信息的过程 及算法使用效果好坏的情况,最终分析了本算法的信息搜寻流程。 - 38 - 第 5 章 实验仿真与性能分析 第 5 章 实验仿真与性能分析 5.1 测试环境配置 5.1.1 CloudSim 简介 云计算的仿真软件 CloudSim 是由澳大利亚的墨尔本大学与 Gridbus 项目共同推 出的,它是通过离散事件的模拟包 SimJava 而开发而成的函数库,它继承了 GridSim 的编程模型,可跨平台在 Windows 和 Linux 系统上运行,支持云计算的研究和开发。 CloudSim 提供了以下新的特点:(1)支持大规模云计算基础设施,包括数据中心在 单一物理计算节点上的仿真和建模;(2)一项独立的用于数据中心,服务代理,调度 策略的建模平台。 CloudSim 的独特功能有:(1)提供的虚拟化引擎,帮助在数据中心节点建立和 管理的多元、自主和协作的虚拟化服务;(2)为虚拟化服务的空间和时间共享切换灵 活性分配处理内核。CloudSim 的这些显著的特点将加快云计算改进算法的开发。 CloudSim 是在 GridSim 模型基础上发展而来,提供了云计算的特性,支持云计 算的资源管理和调度模拟。云计算与网格计算的一个显著区别是云计算采用了成熟的 虚拟化技术,将数据中心的资源虚拟化为资源池,打包向用户提供服务,CloudSim 体现了此特点,扩展部分实现了一系列接口,提供基于数据中心的虚拟化技术、虚拟 化云的建模和仿真功能。通常,数据中心的一台主机的资源可以根据用户的需求映射 到多台虚拟机上,因此,虚拟机之间存在对主机资源的竞争关系。CloudSim 提供了 资源的监测、主机到虚拟机的映射功能。CloudSim 的 CIS(Cloud Information Service) 和 DataCenterBroker 实现资源发现和信息交互,是模拟调度的核心。用户自行开发的 调度算法可在 DataCenterBroker 的方法中实现,从而实现调度算法的模拟。 5.1.2 CloudSim 体系结构 CloudSim 体系结构是 CloudSim 软件框架和体系结构组件的分层实现。在最底层 是 SimJava 离散事件仿真引擎,而实现核心功能需要更高级仿真的框架,如排队和 事件处理、建立系统组件之间的通信。下一步是 GridSim 工具包库函数实现,它支持 高层次软件组件,并用于多重网格的基础设施,包括话务状况和一些如网格的资源、 数据集、工作量跟踪和信息服务等组件的建模。CloudSim 在下一层通过编程扩展 GridSim 层的核心功能,并提供以虚拟云为基础的数据中心环境,如 VMs 的专门管理 接口、内存、存储和带宽的建模与仿真以实现在模拟时期管理实例和执行核心实体。 - 39 - 江苏科技大学工学硕士学位论文 这一层能够同时初始化和透明管理由数以千计的系统组件组成的大型云基础设施。另 外,对于最根本的问题如根据用户要求为 VMs 提供主机、管理应用程序的执行和实 施动态监测都在这一层实现。云供应商想要研究其主机分配不同策略的效果,就需要 在此层通过编程扩展核心 VMs 的配置功能实现他的策略。有一个明显的区别就在这 一层如何为不同的竞争云 VMs 分配主机。云主机能够大量根据用户定义的 QoS 规范 执行应用程序的 VMs 并行分享。 5.1.3 环境配置 本实验的开发环境是基于 Windows XP 操作系统,内存在 2G 左右,CloudSim 版 本为 2.1.1,采用 MyEclipse 下开发。 实验中需要建立资源池 cloudlab1,配置 Windows 操作系统的实验环境虚拟机模 板,安装 VMware Tool 以及 View Agent,并生成 5 个虚拟机资源; 图 5.1 为 vCenter 配置图。 图 5.1 vCenter 配置图 Fig5.1 Configuration of vCenter 图 5.2 为 View Manager 资源池配置图。 图 5.2 View Manager 资源池配置图 Figure 5.2 Configuration of the resource pool of View Manager 图 5.3 为资源池 cloudlab1 虚拟机配置图。 - 40 - 第 5 章 实验仿真与性能分析 图 5.3 资源池 cloudlab1 虚拟机图 Figure 5.3 Virtual machines of resource pool cloudlab1 5.2 仿真流程 CloudSim 仿真步骤为: 1.创建一个数据中心 A; 2.通过 A 建立内存、CPU 和带宽等资源参数; 3.注册。对 CIS 发送注册信号,注册成功后即刻登陆; 4. Data center Broker 将进行信息交互过程的管理。 实验过程中实现任务调度策略的一般步骤和代码为[15]: 步骤 对应代码 (1)初始化 CloudSim CloudSim.init(num_user, calendar, trace_flag); (2)创建数据中心,该中心由多个 Machine Datacenter datacenter0 = 组成,一个 Machine 由多个 Pes 组成 。 createDatacenter("Datacenter_0") (3)创建数据中心代理,并设定它的 brokerId; DatacenterBroker broker = createBroker(); (4)创建虚拟机,每个虚拟机包含 vmid, Vm vm=new Vm(vmid, brokerId, mips, vmname,mips,ram memory,bandwidth pesNumber, ram, bw, size, vmm, new 等参数,并把每个虚拟机加到列表(vmList) CloudletSchedulerTimeShared()); 中,最后把虚拟机列表提交给代理 broker ; broker.submitVmList(vmlist); - 41 - (续上表) 江苏科技大学工学硕士学位论文 步骤 (5)创建任务,每个任务包含任务 id,任 务长度,输入输出文件大小等参数,并把任 务加到,最后把任务列表提交给代理; 对应代码 Cloudlet cloudlet=new Cloudlet(id, length, pesNumber, fileSize, outputSize, utilizationModel, utilizationModel, utilizationModel); cloudletList.add(cloudlet); broker.submitCloudletList(cloudletList); (6)开始仿真 (7)仿真结束,打印统计结果,结果一般包 含有任务 ID,执行状态,数据中心 ID,分 配在哪个虚拟机(VM ID)上执行,开始时 间和结束时间等数据。 CloudSim.startSimulation(); CloudSim.stopSimulation(); List newList = broker.getCloudletReceivedList(); printCloudletList(newList); Cloudlet cloudlet=new Cloudlet(id, length, pesNumber, fileSize, outputSize, utilizationModel, utilizationModel, utilizationModel); cloudletList.add(cloudlet); broker.submitCloudletList(cloudletList); datacenter0.printDebts(); 5.3 实验结果及性能分析 按照上一章提到的人工蜂群的原理和执行流程,我们在本次测试实验中考虑设定 的参数如下:任务数量为 100 至 1000;节点个数为 5 个。为了测试结果能明显的起 到比较作用,所以我们放大 CPU、带宽和内存这些 QoS 中的属性差距。通过对 ABC 算法、改进后的 MABC 算法及随机轮循算法进行 10 次等量任务的测试和比较,得出 各自算法的执行时间,见图 5.4。 - 42 - 第 5 章 实验仿真与性能分析 任 务 平 均 执 行 时 间 ( /s) 1400 1200 1000 RR ABC MABC 800 600 400 200 0 200 400 600 800 任务数量(个) 1000 图 5.4 任务平均执行时间比较 Fig5.4 Comparison of average task execution time 从图中可以看出 RR 算法随着任务数量的增加,执行所耗费的时间也随之线性递 增;而 ABC 算法刚开始时能表现出较好的优化效果,但随着时间的推移,任务数量 加大后容易陷于局部解,后期的花费时间比较长。改进后的 MABC 算法无论从哪方 面都要优于 ABC 算法,此算法比前面两种算法执行时间要短,效率要高。 图 5.5 现有模式资源池 CPU 利用率 Figure 5.5 The utilization of CPU of traditional model - 43 - 江苏科技大学工学硕士学位论文 图 5.6 引入蜂群调度策略模式资源池 CPU 利用率 Figure 5.6 The utilization of CPU of scheduling policy model 通过现有模式和引入蜂群算法调度策略模式的任务执行时间和 CPU 利用率对比, 验证了本文所提出的资源调度策略的有效性。 - 44 - 结论与展望 结论与展望 云计算是当今技术领域中一项炙手可热的技术,很多专家认为,云计算会改变互 联网的技术基础,甚至会影响整个产业的格局。正因为如此,很多大型企业都在研究 云计算技术和基于云计算的服务,亚马逊、谷歌、微软、IBM、SUN 等 IT 巨头都在 其中。它主要通过大量资源的虚拟化实现的,这样企业能够将资源切换到需要的应用 上,根据需求访问计算机和存储系统,并通过计算分布在大量的分布式计算机上,而 非本地计算机或远程服务器中。这种模式与之前的互联网使用模式不同,也给企业管 理方式带来新的契机,但与此同时,也存在一些弊端,当云计算的结果不能满足客户 的需求时,它会按照实际情况动态地扩充添加一些子节点来弥补资源的不足。云计算 要解决的核心问题是如何优化资源管理和分配问题。本文结合 ABC 算法的特性,在改 进算法中引入的控制因子策略能够自适应地调整搜索空间。通过仿真测试结果证明, 改进后的 ABC 算法再计算精度和收敛速度上明显优于 ABC 算法并且兼具局部搜索和 全局搜索的能力,因为它依赖于个体之间动态调节的信息,使得搜索空间得以缩小并 加快了算法收敛速度,保证种群多样性的同时大幅度地提高了搜索效率。从仿真结果 可以看出,针对云环境的大规模性、共享性和动态性等特点,本文提出的资源调度策 略能够有效地在云计算环境中完成计算资源搜索与分配的工作,对云计算的资源管理 达到了很好的优化效果。 工作总结 本文中,详细阐述了云计算的定义、特点,同时和网格计算进行了比较发现,云 计算中的资源调度思想是其体系结构和实现模式的关键技术,所以我采用了人工蜂群 原型,实现云计算的资源调度。再利用仿真工具 CloudSim 对该算法进行仿真,通过结 果说明改进后的算法在节点分配和负载均衡方面都有着很好的效果,所以我们得出结 论如下: (1)在本文中研究的任务调度是众多云计算关键技术中的一个分支,它具有很多 其它的技术,涉及虚拟硬件资源及软件资源,计算动态的节点,备份数据文件等等, 所以这就要求研究者要充分熟悉云计算的体系架构,才能具备对云计算的一个宏观认 识。 (2) 本文中的资源调度根本思想是将任务分配给某个特定节点,这个节点必须 从大量节点中搜索到满足具体要求的某些节点,这是基于最优化搜索的思想。 (3) 本文中提到的 MapReduce 技术是完成任务的分割和开源实现。 - 45 - 江苏科技大学工学硕士学位论文 (4)之所以采用人工蜂群的模型,主要因为它对于未知环境能够搜索到最优的目 标节点,可是由于它的复杂化,自身也会带来过早收敛的缺陷,容易引起局部最优, 不能实现全局最优,所以我们利用控制因子的概念,对蜜蜂个体信息共享进行实时监 测,可以达到有效调节的目的,克服这个问题。 工作展望 云计算是一种新兴的计算模型,对其研究也还处于基础阶段,资源的调度和对资 源管理的优化问题是云计算中心必须解决的一个问题,人工蜂群算法可以对未知环境 搜索到最优的目标节点,可是由于它的复杂化,自身也会带来过早收敛的缺陷,容易 引起局部最优,不能实现全局的目标。所以其中有一些弊端: 1. 只有当搜索规模比较大时,蜂群算法的优势才会被明显的体现出来。 2. 改进算法对参数β有一定的依赖性,在测试中,我们选取的β是一种经验值, 但是在复杂的实际情况下,这个值的确定将和经验值有一些偏差,并且影响最后的收 敛效果。所以,正确合理的挑选β值非常关键,它取决于搜索目标节点的最佳路径和 这个路径中选择的最佳目标节点这两个方面。 3. 最佳目标节点数的选取。当适当的节点很多时,可以根据用户设定的最大参数 则来限制算法的迭代次数;当适当的节点过少时,将导致收敛速度变慢,所以作为以 后的研究方向,可以在这方面找到一个平衡点的方法,更好地实现算法优化。 - 46 - 参考文献 参考文献 [1] 刘鹏.云计算(第二版)[M].北京:电子工业出版社,2010:1-24. [2] 刘万军;张孟华;郭文越. 基于 MPSO 算法的云计算资源调度策略[J]. 计算机工程 .2010 [3] 宋坤芳. 基于蚁群算法的云计算资源调度策略研究[D].武汉纺织大学,2011. [4] 闫英辉. 云计算架构及调度机制的研究[D]. 大连理工大学,2010. [5] 李婷,李晓龙. 云计算的资源管理方法研究[J]. 电脑与电信,2010. [6] 赵春燕. 云环境下作业调度算法研究与实现[D], 北京交通大学,2009.6. [7] 蒋胜利;智西湖. 高校云计算教学初探[J]. 洛阳理工学院学报(自然科学版),2011. [8] 陈滢,王庆波,金涬等. 虚拟化与云计算[M].北京:电子工业出版社,2009. [9] 杨新月. 云计算环境下关联规则算法的研究[D]. 电子科技大学,2011. [10] 吴江丽. 云计算自动化软件安装系统的设计与实现[D]. 河北工业大学,2010. [11] 姜伟. 电信运营商云计算发展策略分析[J]. 电信技术,2011.1. [12] 王强,葛艳. 复杂生产调度与蚁群算法[J]. 中国教育技术装备, 2010. [13] 罗振山. 云计算中资源管理容错调度优化策略研究[D]. 浙江工商大学,2011. [14] 暴励,曾建潮. 一种双种群差分蜂群算法[J]. 控制理论与应用,2010,4. [15]暴励,曾建潮. 自适应搜索空间的混沌蜂群算法[J]. 计算机应用研究,2010,4. [16]lzakian H,Ladani B Zamanifar K,et a1.A Continuous Double Auction Method for Resource Allocation in Computational Grids[C]//Proc.of IEEE Symposium on Computational Intelligence in Scheduling.1S.1.]:IEEE Press,2009:295—299. [17] Wikipedia.Cloud computing[EB/OL].[2011-09-16]. http://en.wikipedia.org/wiki/Cloud computing. [18] IBM cloud computing:Rethink IT. Reinvent business.[EB/OL].[2011-12-06]. http://www.ibm.com/cloud-computing/us/en/. [19] M. Armbrust,A. Fox.A view of cloud computing.Communications of the ACM 53(4),2010. [20] Robert L.Grossman.The Case for Cloud Computing.IEEE Computer Society.2009,4:23-27. [21] L.Vaquero,L.Rodero-Merino,J.Caceres,M.Lindner.A break in the clouds: towards a cloud definition[J]. ACM SIGCOMM Computer Communication Review,2009,39(1):50-55. [22] Qi Zhang,Lu Cheng,Raouf Boutaba.Cloud computing:state-of-the-art and research challenges[J]. Journal of Internet Services and Applications,2010,1:7-18. [23] Wikipedia.Cloud computing[EB/OL].[2011-09-16]. http://en.wikipedia.org/wiki/Cloud computing. [24] cloud computing.[EB/OL].[2011-11-16]. http://searchcloudcomputing.techtarget.com/definition/cloud-computing. [25] IBM Blue Cloud project[EB/OL].[2011-12-2]. http://www-03.ibm.com/press/us/en/pressrelease/22613.wss/. - 47 - 江苏科技大学工学硕士学位论文 [26] Tianle Zhang,Zhihui Du,Yinong Chen,Xiang Ji,Xiaoying Wang.Typical Virtual Appliances:An optimized mechanism for virtual appliances provisioning and management[C].Journal of Systems and Software.2011,84(3):377-387. [27] VMware virtualization technology[EB/OL].[2011-11-15].http://www.vmware.corn [28] Sanjay Ghemawat,Howard Gobioff,Shun-Tak Leung.The Google File System[C].Proceedings of 19th ACM Symposium on Operating Systems Principles,2003,20-43. [29] Amazon elastic compute cloud(Amazon EC2)[EB/OL].[2011-10-22]. http://aws.amazon.com/ec2. [30] James Murty. Programming Amazon Web Services[M].O'Reilly. March 15, 2008. [31] Giuseppe DeCandia,Deniz Hastorun,Madan Jampani,Gunavardhan Kakulapati,Avinash Lakshman, Alex Pilchin,Swaminathan Sivasubramanian,Peter Vosshall,Werner Vogels.Dynamo:Amazon’s Highly Available Key-value Store[J].SOSP.2007,10:1-16. [32] Microsoft Azure[EB/OL].[2011-12-5].http://www.microsoft.corn/azure. [33] David Chiu,Apeksha Shetty,Gagan Agrawal.Elastic Cloud Caches for Accelerating Service-Oriented Computations[C].International Conference for High Performance Computing, Networking,Storage and Analysis,2010,1-11. [34] Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06.Erciyes University,Engineering Faculty,Computer Engineering Department,2005. [35]Kento Aida, Effect of job size characteristics on job scheduling performance[J], Computer Science, vol. 1911, 2000, doi:10.-1007/3-540-39997-6_1. pp.1–17. [36]Capacity Scheduler for Hadoop[EB/OL]. http://hadoop.apache.org/common/docs/current/capacity_scheduler.html. [37]李丽英.面向一种云计算平台的任务调度技术研究[D]:湖南大学,2011. [38]邓自立.云计算中的网络拓扑设计和 Hadoop 平台研究[D]中国科学技术大学,2009. [39]刘鹏.实战 Hadoop:开启通向云计算的捷径[M]. 北京:电子工业出版社,2011:4-33. [40]怀特. Hadoop 权威指南[M]. 曾大聃,周傲英译.北京:清华大学出版社,2010:166-169. [41]陈全,邓倩妮.云计算及其关键技术[J].计算机应用,2009,29(9):2562-2567. [42] 王 静 宇 , 谭 跃 生 . 云 计 算 环 境 下 资 源 分 配 与 任 务 调 度 研 究 [J]. 中 南 大 学 学 报 : 自 然 科 学 版,2010,41(1):46-49. - 48 - 攻读学位期间所发表的学术论文专利目录 攻读学位期间所发表的学术论文专利目录 发表论文: [1] 第一作者.基于 MABC 算法的云计算资源调度策略[J].信息技术,2012,12.(已录用) - 49 - 江苏科技大学工学硕士学位论文 - 50 - 致谢 致谢 光阴似箭,两年半的江苏科技大学研究生的学习和生活渐渐接近尾声,值此完成 论文之际,首先衷心感谢我的导师彭志平教授,在我攻读硕士研究生的期间,得到了 导师的精心指导和培养,使我能够顺利完成研究生学业。从论文立题、调研、深入研 究、参与实际开发到最后的论文撰写、审稿、完稿,导师花费了大量的时间和精力, 彭老师还多方为我查找最新文献,提出了很多建设性意见和建议。导师严谨的治学态 度、科学的学习方法、认真的工作态度和渊博的知识都给我留下了深刻的印象,使我 终身收益。 其次,感谢江苏科技大学计算机科学与工程学院的各位老师,兢兢业业,不辞辛 苦地为我们传授知识。感谢研究生学习生活互帮互助的同学们,感谢我的师兄马言春 和黄烨、周冬、安新亮,高苗粉等同学在共同学习和生活中给予我的帮助,从他们身上 感受到了友谊的伟大。 最后,特别感谢我的父母亲的养育之恩,感谢你们无私伟大的爱默默支持我,给了我 温馨舒适的学习环境,让我在求学路上充满信心和勇气,还要感谢我的家人们在身后 默默支持我、关心我。 - 51 - 江苏科技大学工学硕士学位论文 - 52 - 基于人工蜂群算法的云计算 作者: 学位授予单位: 卢荣锐 江苏科技大学 引用本文格式:卢荣锐 基于人工蜂群算法的云计算[学位论文]硕士 2013

Top_arrow
回到顶部
EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。