虚拟机调度

1.云平台中的虚拟机调度系统的设计与实现（2015）对提升效率的机制、保证公平性的机制以及负载均衡机制进行了设计。目前的虚拟化技术的调度方案更多的注重于提供公平的多VCPU(VirtualCPU,虡拟CPU)支持和SMP(SymmetricMulti-Processing,对称多处理)负载均衡,但是对于集群化的分布式计算平台,公平的多VCPU调度并不能保证集群之间的公平性,甚至往往会导致集群间的不公平性;此外,传统的调度方案也没有考虑到分布式计算中各个虚拟机的负载特点是类似的这个特点,由此可见,在使用现行的调度方案的laaS层上运行BI-PaaS,势必会导致运算效率的下降,同时不公平的调度方案则是PaaS平台的致命伤。负载有两个特点：整个任务的执行时间与其I/O时间是接近的,CPU时间并不是主要开销。对于XenHypervisor来说,虚拟机频繁的I/O请求会极大的影响系统整体性能,因为每次I/O请求都需要DomainO处理。混合了CPU密集型负载和I/O密集型负载的系统。对于这种类型的负载,早期版本的Xen中提供的SEDF调度器以及现在较为主流的Credit调度器都可以提供较为优秀的性能。调度的方案设计：由于Domain0是一个特权级的域,所有的I/O请求都要由它处理,因此Xen的现有调度器在运行高I/O负载时,会频繁调度Domain0,从而导致大量的上下文切换开支。因此,本文的调度器的总体思路就是,抓住高I/O负载的特点以及云平台中并行化运算较多这两个特点,尽量将行为相似的VCPU放在一起,再推迟对Domain0的调度,从而达到减少上下文切换次数的目的以提升系统效率。具体方案的实现：每个VM的虚拟CPU(VCPU)根据它的状态、优先级、以及PCPU的可用性在PCPU上被调度运行的。当一个VCPU的状态变为可运行状态,它被插入到PCPU的运行队列中。Xen的Credit调度器按照VCPU的优先级从高至低的顺序排序,对于具有相同优先级的VCPU,Credit调度器按照FIFO顺序调度。为了充分利用Bl-PaaS的工作负载的特性,本文建议将运行队列中属于同一集群的VCPU放到运行队列中相邻的位置上。在本调度算法中,在相同Cluster的虚拟机如果被分配了相同的优先级,那么它们会被分到同一个组里。数据密集型负载特点带来的多次domO与domu上下文切换的问题,本文提出以下解决方案。调度器可设定一个阈值I/O—watcher,如果一个VCPU在其被调度的周期内处于运行状态的总时间低于这个阈值,就可以认为它下次被调度是极有可能发生I/O请求,这种情况下,调度器就可以将对domO的调度推迟到与与该VCPU属于同一集群的所有VCPU调度之后,从而达到串行化1/0,降低上下文切换的频率以提高系统的整体效率。这个排序方案分为两个部分,其一是优先级相同的情况下属于相同Cluster的VCPU尽量相互Bit邻,其二就是若某个VCPU被判定为可能出现m阻塞的话将DomO的调度推迟到整组之后。在这个机制下,上下文切换次数与I/O响应时间都会有一定的降低,从而达到提升系统整体性能的目的。2.虚拟计算环境下虚拟机资源负载均衡方法（2010）针对虚拟机资源粒度大和迁移时传输数据量大的特点，提出一种基于虚拟机迁移的负载均衡方法。该方法利用负载阈值对宿主机后续时间节点的负载趋势进行预测，避免瞬时负载峰值触发的虚拟机迁移问题。在触发迁移后采用加权概率转发方式选择迁移目标节点，解决传统负载均衡技术中的群聚冲突问题。实验结果表明，在宿主机负载分布严重不平衡的情况下，该方法能有效改善系统性能。3.云环境下的虚拟机调度策略研究_殷小龙（2014）当前云计算数据中心在虚拟机调度方面存在以下缺陷[6]：（1）资源利用率不高。大量的物理机闲置或部署少量虚拟机都会造成物理资源的浪费，从而导致资源的利用率较低。（2）系统负载不均衡。由于不同的应用对应着不同的需求，会导致某一物理机上的CPU、内存和带宽等资源的利用不均衡。同时由于需求的大小不同，也会导致不同虚拟机间的资源利用率不均衡。（3）系统能耗过高。计算资源和存储资源集中在云端，需要大量的服务器来维持系统的正常运行，因此对电能的需求十分巨大。能耗过高不仅造成了电能的浪费，同时也会对环境造成污染。为了克服云计算数据中心在虚拟机调度方面存在的缺陷，保证云计算为用户提供更好的服务质量。本文对云计算环境下的虚拟机调度进行研究，为其建立了调度模型，并针对调度模型提出了基于混合优化的虚拟机调度算法和基于改进NSGAII的虚拟机部署算法。其中基于混合优化的虚拟机调度算法运行在虚拟机资源层，基于改进NSGAII的虚拟机部署算法运行在物理机资源层。这两个算法在一定程度上满足了用户QoS的同时对云计算系统也有不同的要求，前者为负载均衡，后者为系统能耗。因此本课题的研究对云计算的实际应用具有重要意义。云环境下的虚拟机调度按照其调度目标的不同可分为：以减少任务执行时间为目标的调度算法、以提高资源利用率为目标的调度算法、以系统负载均衡为目标的调度算法和以降低系统能耗为目标的调度算法。针对相应的目标，目前业内提出的调度算法主要有传统的调度算法、基于预测的调度算法、基于信任机制的调度算法和基于启发式智能调度算法。（1）传统的调度算法[12-14]。传统的虚拟机调度算法有Min-Min、轮转、先来先服务等。Min-Min算法的原理是将任务调度到预计执行时间最短的虚拟机上执行，轮转算法是把用户任务依次分配给云数据中心的虚拟机。先来先服务算法则是根据任务的到达顺序为其依次分配虚拟机。（2）基于预测的调度算法[15-16]。该类算法通常具有一个预测模型，用来根据历史任务的运行情况来预测下一个任务的需求，从而可以提前创建虚拟机或者进行资源预留，保证任务调度至合理的虚拟机。（3）基于信任机制的调度算法[17-18]。该类算法在云计算中引入信任的基本概念，确立虚拟机与物理机间的信任关系，采用信任效益函数量化不同信任关系下调度结果对安全性与可靠性影响，从而保证了调度算法的质量。（4）基于启发式智能的调度算法[19-27]。启发式算法包括遗传算法、蚁群算法、粒子群算法、模拟退火算法等。启发式算法具有较好全局优化搜索能力，将其应用于虚拟机调度，可以大幅度提高调度的质量。（5）基于混合优化的调度算法[28-31]。由于混合优化算法较单一的优化算法具有更好的寻优效果，部分学者将混合优化算法用于虚拟机调度当中。以上算法主要考虑的是单一的调度目标，缺少对各调度目标的综合考虑，因此有学者提出基于多个目标的虚拟机调度算法，同样取得了相应的成果。基于多目标的虚拟机调度算法可分为两种，一种是将多个目标经过处理变为一个目标后采用上述算法实现虚拟机调度，另一种是对虚拟机调度建立多目标优化模型并采用现有的多目标优化算法对其求解。在云计算中，判断一个虚拟机调度策略的优劣必须通过目标函数，同其它行业的资源调度目标一样，都是如何提高资源的利用率、如何保证尽快地完成用户提交的任务、如何降低系统的成本投入等。但是随着云数据中心的规模不断扩大，使得虚拟机调度的目标有所区别，同时近年来能源消耗成为人们日益关注的问题，节能必须在考虑的目标之内。云计算中的虚拟机调度，目标主要有以下几个方面：（1）服务质量（QualityofService，QoS）。对于云用户而言，如何能尽快地、无差错地完成任务是其关心的问题，所以用户QoS需求是所有目标的前提，引申到虚拟机资源调度上，即从第一个任务至最后一个任务完成的总时间最短。（2）负载均衡。在任何分布式计算模式下，衡量调度算法的一个最重要指标都是负载均衡。由于云计算环境下具有大量异构的虚拟机节点，因此负载均衡变得更加重要，虚拟机资源调度下的负载均衡是指保证所有虚拟节点和物理节点的平均资源利用率达到平衡。（3）资源利用率。云服务提供商通过提高资源的利用率来降低成本投入和增加利润收入。资源的利用率越大，云数据中心的虚拟机能够得到最大程度的利用，即使用最少的虚拟机来满足用户的请求。（4）能量消耗。供电和制冷等能耗费用是云数据中心的主要成本投入，同时大量的能源消耗也违反了当下的节能潮流，因此云计算环境下的虚拟机调度目标要考虑系统的能量消耗，在其他条件不变的情况下尽量使用较少的节点和降低设备的能耗。（5）可靠性。主要分为业务可靠性和系统可靠性，业务可靠性是保证用户提交的任务能够得到执行，系统可靠性是指任务执行的过程中系统发生故障后能够及时备份任务并移交其它服务器继续完成该任务。（6）经济原则。云计算平台按照用户的请求提供服务并收取费用，在市场经济的原则下，必须合理地为资源定价和设计合理的计费系统，保证云资源提供商和使用方能够共同获益，从而吸引更多的用户。以上优化目标对虚拟机一级和二级调度都适用，当优化目标确定后，虚拟机调度按照目标来判定调度的优劣，再通过调度算法产生优化的结果，最后调度中心按照最优的结果来执行调度。调度算法：虚拟机调度算法研究如何按一定规则将大量任务调度到各虚拟机上，可分为传统的调度算法和采用启发式方法来进行寻优的调度算法。传统的虚拟机调度算法有Min-Min、轮转、先来先服务和动态监控等。由于传统的调度算法考虑的过于简单，Min-Min算法会导致配置高的虚拟机上聚集大量任务，影响整体性能；轮转算法假设所有虚拟机处理性能均相同，忽略了异构性；先来先服务未考虑多任务同时执行的情况，忽略了并行性。因此不少学者采用启发式算法来进行全局优化搜索最佳虚拟机调度方案。基于启发式算法的虚拟机调度策略主要采用的是经典的优化算法，主要包括遗传算法、蚁群算法、粒子群算法、模拟退火算法等。综上所述，传统的调度算法过于简单，忽略了云计算的异构性和并行性等特点，因此很难满足日益增长的云计算规模；传统的单一启发式算法由于自身的局限性（例如遗传算法早熟收敛、后期搜索缓慢；蚁群算法参数过多、时间复杂度高；粒子群算法处理规模小、可靠性差），也不能很好地解决大型、复杂、动态的虚拟机调度问题；混合优化算法虽然能够解决原算法的缺陷，但是仍具有以下三个问题：1、目前已有的混合优化算法大多通过设定迭代次数或者时间来衔接两个算法，不能保证算法在最佳结合点处融合从而影响搜索效率；2、当两种算法的编码不一致时，通常采用数学方法进行强制转换，这样会带来不必要的误差；3、当混和算法中包含遗传算法时，通常采用的是最基本的轮盘赌选择方法，会导致算法前期早熟和后期进化缓慢的问题。[6]KhazaelH,MisicJ,MisicVB.AnalysisofaPoolManagementSchemeforCloudComputingCenters[J].IEEEtransactionsonparallelanddistributedsystems,2013,24(5):849-861.[12]夏沛.Hadoop平台下的作业调度算法研究与改进[D].广州:华南理工大学,2010.[13]HafizS,TanHX,IshfaqA,SanjayR.Energyandperformance-awareschedulingoftasksonparallelanddistributedsystems[J].ACMJournalonEmergingTechnologiesinComputingSystem,2013,4(8):1-37.[14]ZhengZN,WangR.Anapproachforcloudresourceschedulingbasedonparallelalgorithm[C].Proceedingsof3rdInternationalConferenceonComputerResearchandDevelopment,2011:444-447.[15]KangJ,RankaS.Dynamicslackallocationalgorithmsforenergyminimizationonparallelmachines[J].JournalofParallelandDistributedComputing,201