基于随机模型的动态调度算法研究_肖逸飞.pdf

《基于随机模型的动态调度算法研究_肖逸飞.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第卷增刊系统工程理论与实践，年月一文章编号：中图分类号：文献标志码：基于随机模型的动态调度算法研究肖逸飞，彭舰，黎红友四川大学计算机学院都，成一摘要针对多资源云环境中虚拟机放置问题，提出了种在随机模型下综合利用率较高的动态调一个虚拟的中度算法首先，在调度中心建立央队列缓存用户任务，然后利用随机路由算法对用户任务进行服务器快速选择，最后在服务器上建立虚拟等待队列并利用算法进行虚拟机配置仿真实验结果表明法在保证的情，该算况下现了一，并可，实定程度上的负载均衡较大提高系统的综合利用率关键词调度云计算利用率随机负载均衡；；；引言随着云计算的迅速发展以及虚拟机（的广泛使用，将有限的资源按需合理地分配给不

2、同的应用变得至关重要然而，云计算环境下内在的动态性、复杂性和异构性使得合理利用各种资源成为云服务提供商的一个主要挑战虽然，几大云计算系统，包括亚马逊的谷歌的还有微软的都已经实现了云计算的商业化，但是其多维资源的综合利用率普遍较低导致浪费资源问题严重运营成本此环境下的放置问题亟待解决，产生了较高的，因，多资源为了模拟真实的云环境，本文着重研究随机模型下的动态调度算法，以保证任务的随机到达以及请求的快速响应在进行任务调度时，本文以服务质量和负载均衡为前提，通过改进巳有的调度算法，提高服务器的综合利用率，进而达到高效利用多维资源的效果本文的贡献总结如下：，模拟真实的云环境从实际的角度出发，在保证负载

3、均衡和的前提下，考虑高效地利用多维资源将多维资源的放置问题转化成可解决的线性问题，并给出相应的算法通过实验证明了本文提出的算法不仅能够提供之间的负载均衡，保证任务的，而且能够达到较高的综合利用率收稿日期：基金项目：国家自然科学基金川省科技支撑计划（，四：云计算：肖逸飞，作者简介（男汉四川成都人硕士研究生，研究方向166系统工程理论与实践第卷本文第节介绍相关工作，并，并对已有算法的不足作出总结第节描述云计算模型进行问题陈述第节阐述算法并与算法进行分析比较第节进行仿真实验与分析第节总结全文一，并提出下步工作相关工作近来于大规模数据中心的放置问题针对对，许多研究关注，和进行放置一’，对单资源放置算法

4、进行誠然而，没有考虑多维资源为了响应各种资源需求，，多维背，放置问题已在文献中被研究频繁使用的技术包括装箱问题包问题阆等等研究了放置问题，目标是最大化满足需求的数量针对在大规模企业数据中心中的动态资源配置提出了一个可扩展的应用放置算法然而以上研究只是分开考虑了种资源的调度，并没有联合起来考虑考虑负载均衡，利用多维资源的不平衡度进行放置，然而该文献并没有考虑选中的剩余资源是否可容纳文献则考虑多维资源的共同调度一，并利用内存转化技术消除单资源的瓶颈，一部分用于计算内存压缩然而在真实的云环境下，将资源舍弃，其可操作性和实时性不得而知文献计对放置问题提出了非抢占式的调度算法—该算法能够对任务负载变化进

5、行相应的处理，能够长期将平均等待，以达到平衡各类任务负载的目的并且在上表现良好积而任务可放入数量越时延保持在较低水平但是，该算法考虑的是等待队列长度与任务可放入数量的乘，高对资源的需求则越低因此利用率一（放入数量对资源的需求资源总数）不定高而还是有很多不足本由此可见，然，虽然国内外研究成果特别是解决问题的方法有许多可供借鉴之处置文在现有研究的基础上，以可操作性和实时性为前提’对算法进行优化放’在保证和负载均衡的条件下，提高系统的综合利用率，以达到高效利用多维资源的目的模型资源模型一一个数据中心本文的云系统包括个调度中心和（由一…个联网的异构组成，单个用表示，，，个上资源维数为中资源…的数量用表

6、示’’，絲模型“”与文献类似一一个，本文设定云用户根据资源请求每个请求被称为任务，任务均不可一定时间内完成抢占并可在，任务的类型决定了用户希望使用的类型和配置任务的大小决定了请求的时间每个任务都是分时间片执行，时间片用表示一一种虚拟机…个需要本文设定配置种类有种，，则某资源的数量为调度模型当任务由用户提交给之后，有个虚拟的中央队列，根据任务的类型采用一一一丨算法将任务随机分配给在上，每种任务（即都有个唯与之对应的虚拟等待队歹种任务组成了一个等待队列集任务到达之后首先进入相应的，根据本文算法完成创建并执行，等待时间片到达之后一一定义若给定个该可以同时接受，个，，的数量为即用一…维的向量表示个上的

7、可行配置，，则有〉：此时例如，分，，在本文实验中，需要种资源类型和存储空间另表示一一例若个云系统中只有种，的配置为（若的种类和配置如表所示一个向，此时，则利用公式⑴可计算出所有可行配置集中的每增刊肖逸飞：基于随机模型的动态调度算法研究，等量从左到右依次为标准，密集，密集可放表中画实例的数量°标准占、，定义右向量满足密集密集则为中的一个最大配置在例中，，，，，，，均满，而，，因为它被，所包含由（（足