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

工第卷增刊系统程理论与实践，年月一文章编号：中图分类号：文献标志码：基于随机模型的动态调度算法研究红肖逸飞，彭舰，黎友四川大学计机学院都算，成一摘要针对多资源云环境中虚拟机放置问题，提出了种在随机模型下综合利用率较高的动态调心立一度算法首先，在调度中建个虚拟的中用用法用缓，最央队列存户任务然后利随机路由算对户任务进行服务器快速选择，后在服务器上建立队法拟法证虚拟等待列并利用算进行虚机配置仿真实验结果表明，该算在保的情一了均，可大高统综用率况下，实现定程度上的负载衡并较提系的合利云利用率随负均调度；算载关键词计；；机衡引言着云的迅速展以及虚拟机的广泛使用，有限的资需理地分随计算发（将源按合配给不同的应用变得至关重要然而，云计算环境下内在的动态性、复杂性和异构性使得合理利用各种资源一亚成为云服务提供商的个主要挑战虽然，几大云计算系统，包括马逊的谷歌的还有微软的都已经实现了云计算的商业化，但是其多维资源的综合利用率普遍较低导致浪费资源问，题严重，产生了较高的运营成本，因此多资源环境下的放置问题亟待解决以，以为了模拟真实的云环境本文着重研究随机模型下的动态调度算法，保证任务的随机到达及请求的以巳快速响应在进行任务调度时，本文服务质量和负载均衡为前提，通过改进有的调度算法，提高服务器的综合利用率，进而达到高效利用多维资源的效果本文的贡献总结如下：，模拟真实的云环境从实际的角度出发，在保证负载均衡和的前提下，考虑高效地利用多维资源问将多维资源的放置问题转化成可解决的线性题，并给出相应的算法通过实验证明了本文提出的算法不仅能够提供之间的负载均衡，保证任务的，而且能够达到较高的综合利用率收稿日期：项目：国基金川划基金家自然科学（，四省科技支撑计：：逸汉四硕士生研方云，作者简介肖飞（男川成都人研究，究向计算166系统工程理论与实践第卷工已，本文第节介绍相关作，并对有算法的不足作出总结第节描述云计算模型并进行问题陈述第节阐述算法并与算法进行分析比较第节进行仿真实验与分析第节一工总结全文，并提出下步作相关工作近来，许多研究关注于大规模数据中心的放置问题，和针对对一’进行放置，对单资源放置算法进行誠然而，没有考虑多维资源已，问，问为了响应各种资源需求，放置问题在文献中被研究频繁使用的技术包括装箱题多维背包阆问目企题等等研究了放置题，标是最大化满足需求的数量针对在大规模业数据中心中的动态资源配置提出了一个可扩展的应用放置算法然而以上研究只是分开考虑了种资源的调度，并没有联合起来考虑考虑负载均衡，利用多维资源的不平衡度进行放置，然而该文献并没有考虑选中的剩一余资源是否可容纳文献则考虑多维资源的共同调度，并利用内存转化技术消除单资源的瓶颈，一然而在真实的云环境下，将资源舍弃部分用于计算内存压缩，其可操作性和实时性不得而知文献计对放置问题提出了非抢占式的调度算法—该算法能够对任务目上现，负载变化进行相应的处理，以达到平衡各类任务负载的的并且在表良好能够长期将平均等待时延保持在较低水平但是，该算法考虑的是等待队列长度与任务可放入数量的乘积，而任务可放入数量越一高对资源的需求则越低因此利用率（放入数量对资源的需求资源总数）不定高国，而还由此可见，虽然内外研究成果特别是解决问题的方法有许多可供借鉴之处然是有很多不足本文在现有研究的基础上，以可操作性和实时性为前提’对算法进行优化放置’在保以目证和负载均衡的条件下，提高系统的综合利用率，达到高效利用多维资源的的模型资源模型一和一心本文的云系统包括个调度中心个数据中（由一…个联网的异构组成，单个用表示，，，个上资源维数为中资源…的数量用表示’’，絲模型“”一一与文献类似，本文设定云用户根据资源请求每个请求被称为个任务，任务均不可一抢占并可在定时间内完成，任务的类型决定了用户希望使用的类型和配置任务的大小决定了请求的时间每个任务都是分时间片执行，时间片用表示一一…，本文设定配置种类有种，则某种虚拟机个需要资源的数量为调度模型当任务由用户提交给之后，有个虚拟的中央队列，根据任务的类型采用一一一丨上，算法将任务随机分配给在每种任务（即都有个唯与之对应的虚拟等待队歹种任务组成了一个等待队列集任，务到达之后首先进入相应的，等待时间片到达之后根据本文算法完成创建并执行一一以，定义若给定个该可同时接受，，的数量为即用个一…维的向量表示个上的可行配置，，则有〉：，此，例如，在本文实验中，需要种资源类型和存储空间分另表示时一一例若个云系统中只有种，的配置为（若的种出一向，中类和配置如表所示，此时则利用公式⑴可计算所有可行配置集的每个增逸飞：基机型的态法研刊肖，等于随模动调度算究量从左到右依次为标准，密集，密集可放表中画实例的数量°标准占、，定义右向量满足密集密集则为中的一个最大配置在例中，（，，（，，，，均满足定义，而（，不满足，因为它