关于数据中心资源调度算法的调研报告ppt课件.ppt

关于数据中心调度算法的调研报告 2013 12 21 目录 研究背景 1 Q A 4 1 1研究背景 什么是云计算 云计算并没有一个统一的定义 长定义是 概括的讲云计算是一种商业计算模型 它将计算任务分布在大量计算机构成的资源池上 使各种应用系统能够根据需要获取计算力 存储空间和信息服务 也是建立在计算机界长期的技术积累基础之上 包括软件和平台作为一种服务 虚拟化技术和大规模的数据中心技术等关键技术 短定义是 云计算是通过网络按需提供可动态伸缩的廉价计算服务 百度知道 1 2研究背景 云计算是并行计算 ParallelComputing 分布式计算 DistributedComputing 和网格计算 GridComputing 的发展 或者说是这些计算机科学概念的商业实现 云计算是虚拟化 Virtualization 公用计算 UtilityComputing IaaS 基础设施即服务 PaaS 平台即服务 SaaS 软件即服务 等概念混合演进并跃升的结果 总的来说 云计算可以算作是网格计算的一个商业演化版 1 3研究背景 通俗的理解 云计算就是指你电脑里所有的资料放在网络上 然后你什么都不用带 到任何一个地方任何一个角落 只要能上网 通过身份识别 你的资料或者你想要的资料都能找出来查询 修改 保存 例如网盘 还有就跟钱存到银行以后 到哪个城市的ATM机上都能取出来一样 1 4研究背景 关于数据中心的理解数据中心 可能是分布在不同地理位置的多个系统 是容纳计算设备资源的集中之地同时负责对计算设备的能源提供和空调维护等 数据中心可以是单独建设也可以置于其他建筑之内 动态分配管理虚拟和共享资源在新的应用环境 云计算数据中心里面临新的挑战 因为云计算应用平台的资源可能分布广泛而且种类多样 加之用户需求的实时动态变化很难准确预测 以及需要考虑系统性能和成本等因素使得问题非常复杂 需要设计高效的云计算数据中心调度算法以适应不同的业务需求和满足不同的商业目标 目前的数据中心调度算法依据具体的应用 计算资源 存储 搜索 海量信息处理等 不同采用不同策略和算法 提高系统的响应速度和服务质量是数据中心的关键技术指标 然而随着数据中心规模的不断扩大 能源消耗成为日益严重和备受关注的问题 因为能源消耗对成本和环境的影响都极大 总的发展趋势是从简单的粗旷的满足功能 性能需求的方式向精细的优化节能的方向发展 1 5研究背景 多数据中心调度算法的参考体系结构如图 1 6研究背景 云计算厂商都有自己资源分配与任务调度模式 但并没有统一的标准和规范 在云计算中 资源分配的效率非常重要 对云计算平台的系统综合性能影响很大 2 1数据中心资源调度方案分析 Google解决方案 Google也许是业界最早使用和发起云计算的厂家之一 因商业保密 其大部分技术实现内容并未被外界了解 从其公开发表的文献可及了解到其关于云数据中心 搜索引擎网络设计 分布式文件系统以及并行处理模式MapReduce的概要设计 Google云计算平台架构 其基础平台是建立在MapReduce结构之上 利用了类似Hadoop的资源调度管理方法 不过Google自己设计了文件系统 GFShunkserver 数据库系统 BigTable 以及其它相关系统 2 2数据中心资源调度方案分析 Amazon解决方案 Amazon目前被认为推广云计算应用最为成功的厂家之一 它成功地推出了EC2 弹性云计算 SQS 简单消息存储服务 S3 简单存储服务 SimpleDB 简单数据库 等近十种云服务 Amazon的云计算平台体系结构 其中 EBS ElasticBlockService ProvidingtheBlockInterface StoringVirtualMachineImages 2 3数据中心资源调度方案分析 IBM解决方案 IBM云计算调度是建立在虚拟计算资源之上 IBM云计算基础平台建立在开源Xen虚拟linux平台和Hadoop集群平台之上 采用了IBMTivoli网络资源监控和WebSphere网络服务 由此可见其核心的调度是建立在HadoopMapReduce框架之上 2 4数据中心资源调度方案分析 HP解决方案 HP很早就开始数据中心的研究工作 下式描述了其数据中心基于成本考虑的各要素 建筑空间占用成本 供电 制冷 维护成本等 Cotst total Cost space Cost power Cost cooling Cost operations 1 2 5数据中心资源调度方案分析 VMWARE解决方案 VMWare成为服务器虚拟化的主要提高商 虚拟化是提高资源利用效率的有效手段 被众多云计算提供商采用 其数据中心虚拟机的动态分配管理主要使用使用VMwareInfrastructure3实现 主要特点是体现在虚拟共享 容灾备份等 将虚拟化优势扩展到远程和分支机构 从而在单一控制点中即可实现以下目标 更加灵活地远程管理每个站点的虚拟机 在中央数据中心托管可远程访问的虚拟机 同时使用分布式虚拟机和集中式虚拟机 目前VMWare公司数据中心的工作还侧重在资源虚拟化 容灾备份等方面 对于资源的动态调度管理方面考虑较少 主要考虑通过虚拟化提高资源利用率 原则 和动态迁移虚拟机以及容灾备份等 Vmware通过建立远端服务器群 可实现双中心互备的虚拟化IT架构 在运营端和远端之间启vReplicator服务 可以实现运营端虚拟机应用实时复制到远端ESX主机存储 达到异地容灾的目的 vReplicator针对虚拟机操作 实时监控虚拟机磁盘文件的数据变化 在完整磁盘数据复制操作完成后 每隔5分钟 自动将两地磁盘数据间的差异数据复制到容灾端 当运营端服务器出现异常中断 服务中断vReplicator自动将容灾端处于待机状态的备份虚拟机进行Failover操作 备份机数据及设置与源虚拟机完全相同 因此启动后即刻可以接管应用 重新开始对最终用户提供服务 2 6数据中心资源调度方案分析 其它厂家解决方案 以上厂家提供的方案多是建立在私有云上 不开源 开源的适用于海量信息处理的HadoopMapReduce和小型云计算平台Eucalyptus是两类值得了解的解决方案 实际上很多前面介绍的厂家包括Google IBM等都在基础架构上采用了MapReduce设计思想 对于小型云计算平台Eucalyptus的资源调度分配管理目前业界是用监测负载平衡器日志和检测响应时间要求来进行的 资源调度管理算法读取实时的负载平衡器日志和计算在每个虚拟机每60秒在集群中的平均响应时间 当它检测到有任何虚拟机的平均响应时间超过需要的反应时间 它将开启一个新的虚拟机实例或更多新的虚拟机实例来满足需求 相应的也可在系统负载较低时减少虚拟机实例 2 7数据中心资源调度方案分析 云计算资源调度 云计算资源调度指的是在一个特定的云环境中 根据一定的资源使用规则 在不同的资源使用者之间进行的资源调整过程 目前的资源调度策略大多数是通过虚拟机级别上的调度技术结合一定的调度策略来为虚拟机内部应用做资源调度 并且调度算法过于简单 判断需要进行推测执行的任务的算法造成过多任务需要推测执行 降低了整个任务的性能 所以在虚拟机级别上采用什么算法实现资源调度是目前待解决的一个难题 3 1基于微粒群算法的云计算资源调度策略 3 1 1微粒群算法的起源 在自然界中 鸟群运动的主体是离散的 其排列看起来是随机的 但是在整体的运动中它们却保持着惊人的同步性 这些呈分布状体的群体所表现出的似乎是有意识的集中控制 一直是许多的研究者感兴趣的问题 有研究者对鸟群的运动进行了计算机仿真 它们通过对个体设定简单的运动规则 来模拟鸟群整体的复杂行为 例如 1986年CraigReynolds提出了Boid模型 用以模拟鸟类的聚集飞行的行为 通过对现实世界中这些群体运动的观察 在计算机中复制和重建这些运动的轨迹 并对这些运动进行抽象建模 以发现新的运动模式 该模型的关键在于对个体间距离的运算操作 即群体行为的同步性在于个体努力维持自身与邻居之间的距离为最优 为此每个个体必须知道自身位置和邻居的位置信息 受上述鸟群运动模式的影响 社会心理学博士JamesKennedy和电子工程学博士RussellEberhart于1995年提出了微粒群算法 PSO 该算法将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置 通过个体间的信息传递 导引整个群体向可能解的方向移动 在求解过程中逐步增加发现较好解的可能性 群体中的鸟被抽象为没有质量和体积的 微粒 通过这些 微粒 间的相互协作和信息共享 使其运动的速度受到自身和群体的历史运动状体信息的影响 以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响 较好的协调微粒本身和群体运动之间的关系 以利于群体在复杂的解空间中进行寻优操作 它既保持传统进化算法深刻的群体智慧背景 同时又有自己许多良好的优化性能 3 1 2微粒群算法的基本原理 微粒群算法与其它算法相似 也是通过适应度值判断群体中个体的移动方向 不同之处在于微粒群算法不像其它算法那样对单个个体使用演化算法 而是将每个个体看作是搜索空间中一个没有体积没有质量的微粒 微粒经初始化后 根据微粒与群体飞行经验 结合对环境的适应度对微粒飞行速度动态调整 使微粒向解空间飞行 最终停留在最优解处 3 1 3参数分析 3 1 4算法流程 微粒群算法的计算流程如下 1 初始化所有的微粒 群体规模为M 在允许的范围内随机设置微粒的初始位置和速度 每个微粒的pbest设为其初始位置 pbest中的最好值设为gbest 2 评价每个微粒的适应值 计算每个微粒的目标函数 3 对每个微粒 将其适应值与其经历过的最好位置pbest进行比较 如果优于pbest 则将其作为当期的最好位置pbest 4 对每个微粒 将其适应值与群体所经历过的最好位置gbest进行比较 如果优于gbest 则将其作为群体最优位置 并重新设置曲est的索引号 5 根据方程 3 2a 和 3 2c 调整当前微粒的位置和速度 6 检查终止条件 通常为达到最大迭代次数或者满足了足够好的适应值 或者最优解停滞不再变化 若上述条件满足 终止迭代 否则返回2 图3 2给出了微粒群算法的流程图 根据微粒群算法计算流程的说明可知其具有以下优点 1 鲁棒性好 由于无集中控制约束 不会因个别个体的故障影响整个问题的求解 2 原理简单 容易实现 3 具备分布式的特征 可方便应用分布式算法模型 及利用多处理器并行计算 4 群体搜索 并具有记忆能力 保留局部个体和全局种群的最优信息 5 算法通用 不依赖于问题的信息 6 协同搜索 同时利用个体局部信息和群体全局信息指导算法下一步的搜索 7 算法简单 同时将微粒的位置和速度模型化 给出显式进化公式 8 以非直接的信息交流方式确保了系统的可扩展性 3 1 5微粒群算法研究 微粒群算法自提出以来 得到了国内外相关领域众多学者的关注和研究 成为国际进化计算界研究的热点 目前 各种改进的PSO算法己广泛应用于科学和工程 生产调度等领域 1 位置和速度更新公式的研究和改进目前 关于微粒群优化算法的很多研究都是围绕着更新公式展开的 文献 18 提出了一种自适应调整惯性权重策略 即线性减少惯性权重的值 这使得算法在迭代初期具有较强的探索能力 可不断搜索新的区域 迭代后期开发能力逐渐增强 使算法能够在最优解周围进行精细搜索 文献 19 给出了一种使用模糊规则动态调整惯性权重方法 通过对当前最好性能评价对惯性权重制定相应的隶属度函数和模糊推理规则 确定惯性权重的增量 实验也表明了该算法比惯性权重线性减小的PSO相比更优 文献 20 给出了惯性权重随迭代次数余弦减少的方法 也取得了良好效果 2 基于遗传思想的改进PSO算法文献 21 提出了杂交微粒群算法 每个微粒赋予了一个与适应值无关的杂交概率 每次迭代 依据杂交概率选取指定数量的微粒放入杂交池中 池中的微粒随机地两两杂交 产生数目相同的子代作为新一代微粒群 文献 22刊哿粒子群算法用于可靠性冗余优化模型 结合遗传算法的思想 与模拟退火算法和遗传算法进行实验比较 得到了较好的仿真结果 3 混合PSO算法文献 23 提出模拟退火并行PSO 粒子群的追踪过程在各个相对独立的并行进程内完成 从而保证各个种群的多样性 而且在各个进程引入了模拟退火跳出粒子群局部极值 文献 241提出了自适应变异的PSO算法 即在进化过程中增加了随机变异算子 增强了PSO跳出局部最优解的能力 从而提高了全局搜索能力 并且能够有效避免早熟收敛的问题 4 离散PSO基本PSO算法最初是用来解决连续函数优化问题的 对于离散优化而言 解空间是离散点的集合 而非连续区域 因此使用PSO算法解决离散优化问题就必须修正速度和位置更新公式 或对问题进行变形 文献 25 中引入了新算子 针对TSP问题实现了一个具体的离散PSO算法 它把位置定义为N个城市的排列 而速度定义为交换的列表 每个交换表示交换排列中的两个城市 在此基础上 对其它量及运算法则进行了定义 算法表现出了很强的进化特征 为PSO的应用拓展了一个可行的新方向 文献 26 针对旅行商问题 提出了一种离散粒子群优化算法 对粒子位置 速度等量及其运算规则进行了重新定义 仿真表明 该算法具有很好的性能 由于微粒群算法提出的时间不长 算法尚缺乏深刻的 具有普遍意义的理论分析 其数学基础相对薄弱 且存在许多不完善和未涉及到的问题 如何利用有效的数学工具对算法的收敛性 收敛速度的估计 计算的复杂性 鲁棒性 以及预防陷入局部最优和参数设置影响等进行分析将是今后的研究热点之一 标准微粒群算法主要适用于连续空间函数的优化问题 如何将算法应用于离散空间的优化为问题 特别是非数值优化问题将是微粒群算法的主要研究方向 此外 充分利用其他进化算法以改善微粒群算法存在的不足 也是值得研究的问题 在进化优化领域 自1980年代以来 一些新颖的优化算法接踵而来 如遗传算法 模拟退火 混沌 人工神经网络 进化规划 禁忌搜索及其混合优化策略等 各种算法在不同的理论分析方面及应用领域中各有千秋 微粒群算法只有通过与其他优化算法的比较 才能更深的了解其性能 只有通过与其他技术相结合 才能达到扬长避短 以提高算法的计算性能 3 2基于预测及蚁群算法的云计算资源调度策略 3 2 1概述 随着计算机性能的不断提高和互联网技术的飞速发展 出现了云计算这种新兴的计算方式来满足人们日益增长的计算需求和海量数据处理需求 资源调度问题是云计算中一个核心问题 针对网格计算 已经有许多静态资源调度算法被提出和应用 但是 这些针对网格计算的静态资源调度算法并不适用于云计算的资源调度中 原因包含以下三方面 首先 网格计算中的资源调度问题大多只考虑如何将一批网格任务合理分配到网格资源上使得当前资源得到最优分配 然而 云计算中时刻存在着虚拟机的申请和释放 所以 静态资源调度算法不适用于云计算 其次 网格计算中的网格任务运行时间是由其所选择的静态资源调度策略所决定的 但是 云计算中虚拟机的使用时间是由用户所决定的 云计算资源调度策略不能决定虚拟机的使用时间 最后 网格计算中的资源调度的目的是为了减少任务运行时间 然而 云计算中虚拟机的使用时间是不能改变的 所以 云计算中资源调度的主要目的变成了如何降低数据中心的用电量 针对上述情况 提出一种结合预测算法与蚁群算法的云计算资源调度策略来降低数据中心的用电量 该资源调度策略有如下两个创新点 第一 通过动态趋势预测算法预测未来短时间内数据中心负载的变化情况 从而合理开关宿主机并且进行资源预留 预测数据中心负载的好处是提前判断下一时刻数据中心的负载情况 避免频繁开关宿主机 从而达到了资源预留的目的 第二 为了适应云计算的动态性和实时性 动态运行改进蚁群算法 在整个数据中心利用率较低时 利用改进蚁群算法将虚拟机集中到某些宿主机从而提高数据中心利用率 动态运行蚁群算法的好处是避免由频繁的虚拟机迁移导致数据中心产生额外用电量 3 2 2问题描述 3 2 3云计算资源调度算法模型 3 2 3 1云计算资源调度系统原理 本文提出的云计算资源调度策略系统原理如图1所示 数据中心资源调度系统由虚拟机管理模块 虚拟机调度模块 宿主机电源管理模块和数据中心负载预测模块组成 系统拥有一个虚拟机队列和两个宿主机队列 开启