虚拟机调度
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调度器都可以提供较为优秀的性能。
调度的方案设计：
由于Domain 0是一个特权级的域,所有的I/O请求都要由它处理,因此Xen的现有调度器在运行高I/O负载时,会频繁调度Domain0,从而导致大量的上下文切换开支。因此,本文的调度器的总体思路就是,抓住高I/O负载的特点以及云平台中并行化运算较多这两个特点,尽量将行为相似的VCPU放在一起,再推迟对Domain 0的调度,从而达到减少上下文切换次数的目的以提升系统效率。
具体方案的实现：
每个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）系统能耗过高。计算资源和存储资源集中在云端，需要大量的服务器来维持系统的正常运行，因此对电能的需求十分巨大。能耗过高不仅造成了电能的浪费，同时也会对环境造成污染。
为了克服云计算数据中心在虚拟机调度方面存在的缺陷，保证云计算为用户提供更好的服务质量。本文对云计算环境下的虚拟机调度进行研究，为其建立了调度模型，并针对调度模型提出了基于混合优化的虚拟机调度算法和基于改进
NSGA II 的虚拟机部署算法。其中基于混合优化的虚拟机调度算法运行在虚拟机资源层，基于改进NSGA II 的虚拟机部署算法运行在物理机资源层。这两个算法在一定程度上满足了用户QoS 的同时对云计算系统也有不同的要求，前者为负载均衡，后者为系统能耗。因此本课题的研究对云计算的实际应用具有重要意义。
云环境下的虚拟机调度按照其调度目标的不同可分为：以减少任务执行时间为目标的调度算法、以提高资源利用率为目标的调度算法、以系统负载均衡为目标的调度算法和以降低系统能耗为目标的调度算法。针对相应的目标，目前业内提出的调度算法主要有传统的调度算法、基于预测的调度算法、基于信任机制的调度算法和基于启发式智能调度算法。
（1）传统的调度算法[12-14]。传统的虚拟机调度算法有Min-Min、轮转、先来先服务等。Min-Min 算法的原理是将任务调度到预计执行时间最短的虚拟机上执行，轮转算法是把用户任务依次分配给云数据中心的虚拟机。先来先服务算法则是根据任务的到达顺序为其依次分配虚拟机。
（2）基于预测的调度算法[15-16]。该类算法通常具有一个预测模型，用来根据历史任务的运行情况来预测下一个任务的需求，从而可以提前创建虚拟机或者进行资源预留，保证任务调度至合理的虚拟机。
（3）基于信任机制的调度算法[17-18]。该类算法在云计算中引入信任的基本概念，确立虚拟机与物理机间的信任关系，采用信任效益函数量化不同信任关系下调度结果对安全性与可靠性影响，从而保证了调度算法的质量。
（4）基于启发式智能的调度算法[19-27]。启发式算法包括遗传算法、蚁群算法、粒子群算法、模拟退火算法等。启发式算法具有较好全局优化搜索能力，将其应用于虚拟机调度，可以大幅度提高调度的质量。
（5）基于混合优化的调度算法[28-31]。由于混合优化算法较单一的优化算法具有更好的寻优效果，部分学者将混合优化算法用于虚拟机调度当中。
以上算法主要考虑的是单一的调度目标，缺少对各调度目标的综合考虑，因此有学者提出基于多个目标的虚拟机调度算法，同样取得了相应的成果。基于多目标的虚拟机调度算法可分为两种，一种是将多个目标经过处理变为一个目标后采用上述算法实现虚拟机调度，另一种是对虚拟机调度建立多目标优化模型并采用现有的多目标优化算法对其求解。
在云计算中，判断一个虚拟机调度策略的优劣必须通过目标函数，同其它行业的资源调度目标一样，都是如何提高资源的利用率、如何保证尽快地完成用户提交的任务、如何降低系统的成本投入等。但是随着云数据中心的规模不断扩大，使得虚拟机调度的目标有所区别，同时近年来能源消耗成为人们日益关注的问题，节能必须在考虑的目标之内。云计算中的虚拟机调度，目标主要有以下几个方面：（1）服务质量（Quality of Service，QoS）。对于云用户而言，如何能尽快地、无差错地完成任务是其关心的问题，所以用户QoS 需求是所有目标的前提，引申到虚拟机资源调度上，即从第一个任务至最后一个任务完成的总时间最短。
（2）负载均衡。在任何分布式计算模式下，衡量调度算法的一个最重要指标都是负载均衡。由于云计算环境下具有大量异构的虚拟机节点，因此负载均衡变得更加重要，虚拟机资源调度下的负载均衡是指保证所有虚拟节点和物理节点的平均资源利用率达到平衡。
（3）资源利用率。云服务提供商通过提高资源的利用率来降低成本投入和增加利润收入。资源的利用率越大，云数据中心的虚拟机能够得到最大程度的利用，即使用最少的虚拟机来满足用户的请求。
（4）能量消耗。供电和制冷等能耗费用是云数据中心的主要成本投入，同时大量的能源消耗也违反了当下的节能潮流，因此云计算环境下的虚拟机调度目标要考虑系统的能量消耗，在其他条件不变的情况下尽量使用较少的节点和降低设备的能耗。
（5）可靠性。主要分为业务可靠性和系统可靠性，业务可靠性是保证用户提交的任务能够得到执行，系统可靠性是指任务执行的过程中系统发生故障后能够及时备份任务并移交其它服务器继续完成该任务。
（6）经济原则。云计算平台按照用户的请求提供服务并收取费用，在市场经济的原则下，必须合理地为资源定价和设计合理的计费系统，保证云资源提供商和使用方能够共同获益，从而吸引更多的用户。
以上优化目标对虚拟机一级和二级调度都适用，当优化目标确定后，虚拟机调度按照目标来判定调度的优劣，再通过调度算法产生优化的结果，最后调度中心按照最优的结果来执行调度。
调度算法：
虚拟机调度算法研究如何按一定规则将大量任务调度到各虚拟机上，可分为传统的调度算法和采用启发式方法来进行寻优的调度算法。传统的虚拟机调度算法有Min-Min、轮转、先来先服务和动态监控等。由于传统的调度算法考虑的过于简单，Min-Min算法会导致配置高的虚拟机上聚集大量任务，影响整体性能；轮转算法假设所有虚拟机处理性能均相同，忽略了异构性；先来先服务未考虑多任务同时执行的情况，忽略了并行性。因此不少学者采用启发式算法来进行全局优化搜索最佳虚拟机调度方案。基于启发式算法的虚拟机调度策略主要采用的是经典的优化算法，主要包括遗传算法、蚁群算法、粒子群算法、模拟退火算法等。
综上所述，传统的调度算法过于简单，忽略了云计算的异构性和并行性等特点，因此很难满足日益增长的云计算规模；传统的单一启发式算法由于自身的局限性（例如遗传算法早熟收敛、后期搜索缓慢；蚁群算法参数过多、时间复杂度高；粒子群算法处理规模小、可靠性差），也不能很好地解决大型、复杂、动态的虚拟机调度问题；混合优化算法虽然能够解决原算法的缺陷，但是仍具有以下三个问题：1、目前已有的混合优化算法大多通过设定迭代次数或者时间来衔接两个算法，不能保证算法在最佳结合点处融合从而影响搜索效率；2、当两种算法的编码不一致时，通常采用数学方法进行强制转换，这样会带来不必要的误差；
3、当混和算法中包含遗传算法时，通常采用的是最基本的轮盘赌选择方法，会导致算法前期早熟和后期进化缓慢的问题。
[6] Khazael H, Misic J, Misic VB. Analysis of a Pool Management Scheme for Cloud Computing Centers[J]. IEEE transactions on parallel and distributed systems, 2013,24(5):849-861.
[12] 夏沛.Hadoop平台下的作业调度算法研究与改进[D].广州:华南理工大学,2010.
[13] Hafiz S, Tan H X, Ishfaq A, Sanjay R. Energy and performance-aware scheduling of tasks on parallel and distributed systems[J]. ACM Journal on Emerging Technologies in Computing System,2013,4(8):1-37.
[14] Zheng Z N, Wang R.An approach for cloud resource scheduling based on parallel algorithm[C]. Proceedings of 3rd International Conference on Computer Research and Development, 2011:444-447.
[15] Kang J, Ranka S. Dynamic slack allocation algorithms for
energy minimization on parallel machines[J]. Journal of Parallel and Distributed Computing, 2012, 70(5): 417-430.
[16] Ruan X J, Qin X, Zong Z L. A prediction scheduling algorithm using dynamic voltage scaling for parallel applications on clusters[C]. Proceedings of 16th Conference on Computer Communications and Networks, 2010:535-541.
[17] Wang W, Zeng G S, Tang D Z. Cloud-DLS:Dynamic trusted scheduling for Cloud computing[J]. Expert Systems with Applications,2013,39(3):2321-2329.
[18] Hu Z, Wu K J, Huang J S. An utility-based job scheduling algorithm for current computing Cloud considering reliability factor[C]. Proceedings of 3rd International Conference on Software Engineering and Service Science, 2012:296-299.
[19] 金嘉晖,罗军舟,宋爱波等.基于数据中心负载分析的自适应延迟调度算法[J].通信学报,2011,32(7):47-56.
[20] Zheng Z N, Wang R. An approach for cloud resource scheduling based on parallel genetic algorithm[C]. Proceedings of 3rd International Conference on Computer Research and Development, 2011:444-447.
[21] 朱宗斌,杜中军.基于改进GA的云计算资源调度算法[J].计算机工程与应用,2012,l(5):25-29.
[22] Kusic D, Kephart J O, Hanson J E, et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing, 2013,12(1):1-15.
[23] 谭一鸣,曾国荪,王伟.随机任务在云计算平台中能耗的优化管理方法[J].软件学报,2012,23(2):266 278.
[24] 熊聪聪,冯龙,陈丽仙等.云计算中基于蚁群算法的任务调度算法研究[J].华中科技大学学报(自然科学版),2012,1(1): 1-6.
[25] Beloglazov A, Buyya R. Energy efficient allocation of virtual machines in cloud data centers[C].Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2012:577- 578.
[26] 王永贵,韩瑞莲.基于改进蚁群算法的云环境任务调度研究[J].计算机工程,2011,19(5):1203-1211.
[27] Owezarski P, Lobo J, Medhi, D. Network and service management for cloud computing and data centers[J]. Journal of network and systems management, 2013,21(4):707-712.
[28] 王刚,钟志水,黄永青.基于蚁群遗传算法的网格资源调度研宄[J].计算机仿真,2011,9(4):240-243.
[29] Mezmaz M, Melab N, Kessaci Y, et al. A parallel bi-objective hybrid for energy-aware scheduling for cloud computing systems[J]. Journal of Parallel and Distributed Computing, 2013,71(11):1479-1508.
[30] 陈晨.基于遗传和蚁群混合优化算法的云计算资源调度算法研究[D].北京:北京邮电大学,2012.
[31] Wei G Y, Vasilakos A, Yao Z, et al. A game-theoretic method of fair resource allocation for computing services [J]. The Journal of Supercomputing, 2010,54(2):252-269.
4.云计算环境下虚拟机调度策略研究_姜永（2014）
提出了一种基于资源状态实时感知的虚拟机调度方法。该方法通过对虚拟机的实时监控来感知虚拟机资源的使用状态,以此为基础釆用贪心算法作出虚拟机调度策略,并最终利用虚拟机在线迁移技术实现云平台资源的动态负载均衡和节能优化。
5.Scheduling para-virtualized virtual machines based on events（2012）
①当处理cpu密集型任务时接收事件的虚拟CPUs有很少的block(virtual
CPUs that receive events while processing CPU-intensive tasks seldom
block)，因此，该机制不利于这些虚拟CPU，虚拟CPU可以处理混合工
作负载。
②经常发送事件请求的虚拟CPUs没有恰当的优先级。
以上两个问题可能会导致客户Domain中应用程序性能低下。所以提出了一个新的方法来提高Credit调度，使其具有更好的优先级例如domain。我们的解决方案有两部分：1)调度虚拟CPU, 虚拟CPU可以尽可能的接收I / O事件；2）
经常的切换事件发送者，让他们不时地开始更多的I/O请求。
试验评估表明，我们的方法不仅提高了domain做混合工作负载的响应，同时也最大限度地减少了调度引起的不公平。这篇文章提出了一个全职事件感知调度(full-time event aware scheduling(FEAS))机制，对Xen的Credit调度进行了补充，通过Xen的分片模型和事件通道提高了忙碌虚拟机时的I/O性能。它是credit的增强版本，使虚拟CPU的I/O工作优先级化，通过监控domain间的事件发送和domains与物理设备之间的物理中断请求的事件发送，FEAS使虚拟机监视器full-time event aware并立即尽最大努力调度可运行的VCPUs，VCPUs可以接收或优先考虑（期望）发送与I/O相关的事件。
未来的方向：虽然实验没有负面影响，但有可能在Xen的未来发行上会出现其他的问题，一些参数，如时间间隔大小，调度频率界限等都是被强制定义的，使它们动态的选择是我们未来研究的一个方向。
备注：
To complement creditscheduler, the proposed scheduler prioritises not onlyblocked VCPUs but also runnable ones, and is calledfull-time event aware scheduler (FEAS). A VM processingmixed workloads can greatly benefits from promptscheduling upon receiving an incoming event, particularlyif it is an I/O related event.
6.Batch scheduling of consolidated virtual machines based on their
workloadinterference model（2013）
因为虚拟机之间的工作负载的互扰（interference），所以当前的虚拟化技术的实现没有在运行在物理机的虚拟机之间提供有效的性能的隔离。一般情况下，这种互扰是由于争夺物理机的资源，不同的工作负载有不同的资源配置导致的。为了研究这种干扰的影响，我们为一个整合的多租户虚拟环境制定了一个干扰概念。根据此概念我们提出了一个新的批处理调度程序，这个调度程序减少了运行在物理机上的虚拟机之间的互扰，通过暂停那些对虚拟机有较高的干扰度的虚拟机。调度利用0-1背包求解问题选择出具有较少干扰的一些虚拟机。被选择的虚拟机允许运行而其他虚拟机被暂停。用户不会因为虚拟机短时间的暂停和恢复而困扰。因为调度器被设计为批处理类型。
其他研究者也提出了一些干扰原因：①多个资源调度器共同存在试图管理共
享的资源，然而每个调度器并不知道其他调度器的存在；②资源的竞争；③新的资源抽象层的存在。
我们利用数学模型根据这些虚拟机的进程，网络负载，虚拟机的数量来估计运行在一个物理机上的虚拟机之间的干扰度。被停掉的虚拟机可以被恢复，只要调度器发现他们对干扰不再有强大的干扰。该算法的复杂度为O（N），N为运行中被整合的虚拟机的数量。
将硬盘和内存的工作负载考虑进我们的模型中，在分布式虚拟数据中心部署改进的算法是我们未来工作的一部分。除此之外，根据在不同工作负载中测到的一些干扰数据的基础上找到一个最佳的干扰模型是一个值得追求的有趣的问题。
7.Energy-efficiency enhanced virtual machine scheduling policyfor mixed
workloads in cloud environment（2014）
本文提出了一个提高能源利用率的虚拟机调度策略，命名为Share-Reclaiming with Collective I/O (SRC-I/O)，目的是减少由I/O虚拟化导致的能效损失。所提出的SRC-I / O调度程序允许虚拟机在一定的条件下回收额外的CPU 资源，以提高CPU的利用率。同时，为了减少调度混合型工作负载时上下文切换的代价，它将I/O密集型和CPU密集型的虚拟机分隔开来，并且用集中式的方法调度他们。
以前的工作主要集中在提高性能相关的指标。提高了I/O性能但忽略了由I/O 虚拟化导致的能耗的损失。影响因素有：1）传统的调度只观察了多处理机的CPU 的公平分配，然而忽略了I/O资源的调度；2）当存在I/O密集型的工作负载时，在虚拟化系统中的上下文切换的频率也会急剧的增长，这会导致CPU和I/O设备性能的降低。3）在虚拟化系统中当执行I/O操作时，数据在客户层和主机层的复制和缓冲会降低整个系统的性能。所以调度策略应该考虑到工作负载的特点，特别是当CPU密集型应用和I/O密集型应用同时存在时。
Share-Reclaiming机制的目的是提高CPU的利用率，Collective I/O机制的主要目的是减少由IO密集型工作负载导致的上下文切换的代价。
未来的工作：将SRC-I/O调度器部署在其他的虚拟机监视器上，，而且，在SRC-I/O调度器中为实时工作负载合并一些策略。
8.申倩，等: 云计算环境下任务调度研究综述（2014）
云环境下，任务调度的目标就是对用户提交的所有任务实现最优调度，并尽量提高云计算系统的总体吞吐率。具体的目标包括: 服务质量(QoS) 、负载均衡、经济原则和节能减排等。
( 1)QoS。云环境下的任务调度系统必须满足用户的QoS，一方面，要根据应用的特征提高资源的发现率和准确性系数，保证用户服务的性能QoS; 另一方面，则需针对用户的状态变迁，动态进行资源选择以及重定向，满足用户的经济QoS，有效地提高用户满意度。
( 2) 负载均衡.由于云环境下计算资源是由大量计算机节点组成，复杂且异构，这就使得负载均衡的实现具有相当难度。
( 3) 经济效益.由于云计算是一种新型的商业模式，其中的经济效益必然成为着重关注的调度指标。该指标的切实完善的真正实现将直接关系着云计算这一面向普适商业应用计算模式的有效运营周期。
(4) 节能减排。云计算是超大规模的计算，每个数据中心的电力消耗均堪称巨大，在提倡绿色计算的背景环境下，云计算也必须将节能减排作为一个重要的追求目标。
云环境下任务调度技术研究现状：
1）侧重性能的调度
作为任务调度研究的核心热点，侧重性能的任务调度的最终目标就是性能，例如最优跨度，任务最早完成时间等。目前使用比较广泛的算法包括Min-Min 算法、Max-Min 算法、遗传算法、贪心算法、蚁群算法和模拟退火算法等。
具体来说，IBM 公司的云计算平台采用的就是以性能为中心的调度策略。而且，李建峰等人［李建锋，彭舰. 云计算环境下基于改进遗传算法的任务调度算法［J］. 计算机应用，2011，31（1）：184-186］基于MapReduce 模型，提出了一种具有双适应度的遗传算法(DFGA) ，该算法不仅能够使总任务的完成时间最短，还能使任务的平均完成时间较短; 汤小春等人［汤小春，刘健. 基于元区间的云计算基础设施服务的资源分配算法研究［J］. 计算机工程与应用，2010(9):239-242,246］则提出了一种基于元区间的最佳分配决策算法，并取得了良好效果; 还有，华夏渝等人［华夏渝，郑俊，胡文心.基于云计算环境的蚁群优
化计算资源分配算法［J］. 华东师范大学学报: 自然科学版，2010,1(1)：127-134.］提出了一种基于蚁群优化的资源分配算法，该算法适应于具有最小响应时间和最好服务质量为其指标要求的任务调度。另外，周文俊等人［周文俊，曹键. 基于预测及蚁群算法的云计算资源调度策略. 计算机仿真［J］. 计算机仿真，2012(9)：239-242,246.］针对静态资源调度中只考虑任务完成时间最小化问题，提出了一种基于预测的蚁群算法来满足云环境下资源的动态分配。
2）侧重服务质量的调度
云计算是一种商业模型，其中的用户QoS 不仅关系到用户的实际体验，而且将实际影响着云计算的良性发展。因此，基于QoS 的任务调度算法研究也获得蓬勃发展。一般情况下，算法研发框架除了要考虑最小完成时间或是最优跨度，还需涉及服务质量等问题。基于QoS 的研究，目前已推出丰硕成果。文献［李文娟，张启飞，平玲娣，等。基于模糊聚类的云任务调度算法［J］。通信学报，2012，33(3) : 146-154］提出了一种基于模糊聚类的云任务调度算法，该算法对资源进行模糊聚类，更好地反映了任务的需求。He 等人［7］对Min-Min 算法进行了改进，即根据用户是否还有QoS 需求而对系统的吞吐率实现了优化。Chanhan 等人［8］又根据加权平均执行时间进行资源选择，通过将网络带宽作为QoS属性，而将任务分为高QoS 与低QoS需求两类，并且对于高QoS的任务将进行优先调度。再有阿尔卡特朗讯贝尔实验室的Hao 等人［9］提出了一个网络虚拟化架构，用来实现云服务的动态需求和迁移，而不影响服务性能，由此提高了云服务质量。另外，孙大为等人［10］则提出一种基于免疫克隆的偏好多维QoS云计算调度优化算法，结合免疫克隆算法，对客户应用的偏好和多维QoS 中的客户效用进行量化，同时给出了多维QoS优化的目标函数，以此满足客户的经济QoS和性能QoS。
3）侧重经济原则的调度
除服务质量外，云计算的商业运行模式则使得经济因素也成为任务调度的重要指标之一。惠普的云数据中心采用的就是成本优先调度策略。邓见光等人［11］，在满足QoS 的前提条件下，从云服务提供商的角度出发，给出了一种基于成本的云任务调度策略。Buyya等人［12］进而提出了面向市场的云计算以及面向市场的云计算构架。葛新等人［13］再次提出了一种基于计算强度的调度策略，并
且具有低成本的特点。该策略的主要思想是将计算量大的任务分配给计算能力强的集群调度，而将计算量小的任务则分配给计算能力弱的集群调度。另外，对于那些经济效益要求高而时间需求相对宽松的应用，即可选择计算能力弱的集群调度; 但针对有严格时间要求的应用将可申请计算能力强的集群调度，如此即能达到降低成本的目的。
4）侧重能耗优化的调度
在提倡绿色计算的浪潮下，已有更多的学者正致力研究侧重于能耗优化的调度算法，并取得了可观的成就。文献［14］中设计了基于动态定价策略的数据中心能耗成本优化方案，为研究基于能耗优化的任务调度提供了基础。该调度算法可以根据动态的服务价格进行调度，达到优化能耗的目的。文献［15］中则提出了两种具有能量感知的任务调度算法，分别利用能耗时间归一及能耗时间来定义适应度函数，实验结果表明，与单独考虑能耗或是时间相比，这两种算法能够有效降低能耗并缩短任务执行时间。曹洁等人［16］也提出了两种满足并行任务截止时间要求和并行任务执行能耗要求的调度方法Ssef 和Egsa。实验结果表明，该算法在保证并行任务截止完成时间要求的前提下能够有效降低并行任务的能源消耗，从而降低了云计算系统的能耗开销。
9.云计算环境下基于遗传蚁群算法的任务调度_周彬（2014）
提出了一种混合调度算法。该算法是蚁群算法与遗传算法的有机融合。其中的遗传算法采用间接编码方式。结合由遗传算法衍生出的优化解。对蚁群信息素的分布进行初始化处理。使遗传算法的快速搜索能力得到充分利用。并通过克服蚁群算法的起始信息素不足问题。加快了求解速度。
蚁群算法是一种对全局进行优化的方法，通过模拟真实的蚁群寻径行为，对
种群的原始仿生进化进行计算，能够对相关信息进行正反馈，并能模拟负载情况【周文丽，张正青，刘小青。网络环境下任务调度算法的应用与研究[D].大连：大连海事大学，2013】。然而其缺乏初期信息素，导致需要花费大量时间搜索初期积累的信息素。有研究已得出结论:蚁群算法搜索初期信息素的时间占总时间的70%以上。
遗传算法在求解效率上过于偏低，导致求解过程中容易造成大量多余迭代，使蚁群算法与遗传算法之间的衔接受到影响。以往通过固定遗传算法的迭代次数实现衔接，但无法得到最好效果。本文通过动态融合策略,将遗传算法与蚁群算法有机融合，以确保迭代次数既不冗余又能达到最好的计算效果【李建峰，彭雨舰，冯玉如，云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2012,6(2)：40】。具体步骤如下:将最小以及最大遗传迭代次数预先设定好，在进行遗传迭代时及时记录子代群体的进化率,将此进化率作为子代群体的最小进化率。
10.一种基于贪心策略的启发式云计算任务调度算法_孙凌宇(2015)
提出了一种基于贪心策略的启发式任务调度算法，用于优化云计算环境下任务调度中执行时间。
任务调度作为云计算平台的重要组成部分，是将用户提交的任务进行合理高效地分配和调度，其实质就是将n个相互独立的任务分配到m个闲散异构的物理资源上，使得总任务完成时间最小并且可用资源得到充分利用[叶枫,王志坚,徐新坤,等. 一种基于QoS 的云负载均衡机制的研究[J]. 小型微型计算机系统, 2012, 33(10): 2147-2152.]。任务调度的效率直接影响到云计算平台的整体性能和服务质量。
国内外研究者提出了大量的云计算任务调度算法来计算任务调度的近似最优解，既有传统网格计算中的Min-Min[4]、Max-Min[5]、动态规划[6]等启发式调度算法，也有基于遗传算法[7]、粒子群算法[8]、蚁群算法[3]、免疫算法[9]、差分进化算法[10]和禁忌搜索算法[11]等智能调度算法。其中，传统启发式调度算法以最早完成时间为目标进行调度，有着较好的负载均衡性能，但总任务的实际执行时间并非最少[6]；智能调度算法在进行海量任务调度过程中，易陷入局部最优解，在收敛速度和负载均衡方面的效果有待提高[10]。
传统的顺序调度策略的启发式云计算任务调度算法把一组任务顺序分配给一组虚拟机，尽量保证每个虚拟机运行相同数量的任务以平衡负载，但没有考虑任务的需求和虚拟机之间的差别[1]。
参考文献：
[1] 白延敏,薛进,马维华. 云环境下弹性负载均衡方法的研究[J]. 小型微型计算机系统, 2014, 35(4): 814-816.
[2] 叶枫,王志坚,徐新坤,等. 一种基于QoS 的云负载均衡机制的研究[J]. 小型微型计算机系统, 2012, 33(10): 2147-2152.
[3] 查英华,杨静丽. 改进蚁群算法在云计算任务调度中的应用[J]. 计算机工程与设计, 2013, 34(5): 1716-1816.
[4] 史少锋,刘宴兵. 基于动态规划的云计算任务调度研究[J]. 重庆邮电大学学报:自然科学版, 2012, 24(6): 687-692.
[5] 李建锋,彭舰. 云计算环境下基于改进遗传算法的任务调度算法[J]. 计算机应用, 2011, 31(1): 184-187.
[6] 封良良,张陶,贾振红, 等. 云计算环境下基于改进粒子群的任务调度算法[J]. 计算机工程, 2013, 39(5): 183-188.
[7] 叶菁,陈国龙,阮一文. 异构环境下相关任务调度免疫遗传算法的研究[J].小型微型计算机系统,2011,32(10): 2124-2129.
[8] 董丽丽, 黄贲, 介军. 云计算中基于差分进化算法的任务调度研究[J]. 计算机工程与应用, 2014, 50(5): 90-95.
[9] 孙凌宇,冷明,朱平, 等. 云计算环境下基于禁忌搜索的负载均衡任务调度优化算法[J]. 小型微型计算机系统, 2015, 36 (8): 2409-2414.
[10] Reuters T. CloudSim: a framework for modeling and simulation of cloud computing infrastructures and services introduction[EB/OL]. https://www.wendangku.net/doc/3c10397043.html,/ gridbus/ cloudsim/.
11.Task-aware Virtual Machine Scheduling for I/O Performance(2009)
因为虚拟机缺少对每个虚拟机的认识，工作负载的不可预测性使得资源的分配变得很困难。特别的，在虚拟机监视器对虚拟机内部的工作负载是不预知的情况下虚拟机调度对I / O性能有重要的影响。
本文提出了一个基于用灰盒知识的推理技术的任务感知的虚拟机调度机制。该机制预测I/ O密集型的客户级任务并且将到来的事件和I/ O密集型任务相联系，我们提出了一个局部优化，它是一个根据任务粒度来制定优先促进机制，使得I/ O密集型任务可以被选择性的调度及时处理到来的事件。我们的技术主要提高在异构工作负载下的I/ O密集型任务的性能，通过轻量级机制完成虚拟机之间CPU 的负载均衡。
工作负载的不可预测性使CPU的分配变得困难，特别是考虑到时效性的时候。由于VMM缺乏有关各个客户机操作系统的现有任务的认识，就难以考虑虚拟机上的混合工作负载。此外，VMM不跟踪哪些I / O事件注定是个阻塞的任务。当大量的虚拟机同时有I/ O密集型和CPU密集型工作负载时，它们对I/ O的响应是很差的，因为VMM不能及时将收到的任务和I/ O密集型的任务相关联。如果虚拟机监视器调度虚拟机，而没有考虑虚拟机的内部工作负载，在虚拟机中不相关的CPU密集型任务就会尽可能的被分配CPU。因此，这样的调度导致了虚拟机之间的不公平，因此，VMM需要对客户级任务的感知以及将到来的事件和
I/ O密集型任务相联系。
本文提出了一种任务感知VM调度机制来提高VM中I /O密集型任务的性能。通过观察每个任务调度序列和CPU的消耗，VMM会优先调度I/ O密集型任务。I/ O密集型任务时需要I/ O响应的事件和消耗较短的CPU时间。
目前的方法只考虑一种情形：一个客户域在一个物理CPU上只有一个虚拟CPU。因此，我们不能解决客户级任务和VCPU的迁移问题。当前的credit调度倾向于在物理机之间重新放置VCPU，主要为了平衡CPU的负载。在未来的工作，我们计划去扩展我们的方法，以支持多核处理器来提高基于任务感知的I/ O性能。
12.A Comparative Analysis of Task Scheduling Algorithms ofVirtual Machines in
Cloud Environment(2015)
对比研究进行了三种任务调度算法：随机的资源选择。循环、绿色调度。结果发现这些算法在均提高了能源和VM的性能。均有优缺点。绿色调度算法在能源消耗方面有最佳的性能。随机调度在VM和数据中心的负载方面有较好的性能。循环调度在VM和数据中心负载方面比绿色调度要好，但和随机算法和绿色调度相比需要更多的能源消耗。循环算法调度器公平的分配任务，网络流量是平衡的，
所以不会出现服务器和网络结点的拥塞和超载。
随机资源选择算法具有用随机的方式分配优先任务到可用的虚拟机上。虚拟机的状态是未知的，即使虚拟机承载的负载或重或轻。这种行为可以导致虚拟机的重负载，而且在执行之前可能会有长时间的等待。在某些情况下，任务可能执行失败，因为期限已经过期，这种算法不是真的复杂，因为它并不需要架空或预处理【N., Z. Dong and R. Rojas-Cessa, 2013. Taskscheduling and server provisioning for energy-efficientcloud-computing data centers. Proceedings of the IEEE33rd International Conference on DistributedComputing Systems Workshops, Jul. 8-11, IEEEXplore Press, Philadelphia, PA., pp: 226-231.】。
RR任务调度算法使用循环顺序的方式将选择的任务分配到可利用的虚拟机上。每个任务被平均管理。由于RR调度算法可以平均的分配任务到所有的虚拟机上，所以，达到了负载均衡；很好的避免了拥塞和延迟。因此，任务失败的可能性变得最小。【Mathew, T., K.C. Sekaran and J. Jose, 2014. Study andanalysis of various task scheduling algorithms in thecloud computing environment. Proceedings of theInternational Conference on Advances inComputing, Communications and Informatics, Sept.24-27, IEEE Xplore Press, New Delhi, pp: 658-664.DOI: 10.1109/ICACCI.2014.6968517】
到达数据中心的工作负载通过能量感知的“绿色”调度机制被调度执行。这种“绿色”调度收集在最小的计算服务器的工作负荷。为了解释高性能计算工作量，调度器以连续方式的跟踪在路径上的网络交换机的缓冲器。当拥塞发生时，调度器远离拥塞的路由即使服务器可以满足工作负荷的计算要求。闲置的服务器被设置成睡眠模式使需求的电压最小化【Kliazovich, D., P. Bouvry and S.U. Khan, 2012.GreenCloud: A packet-level simulator of energyawarecloud computing data centers. J.Supercomput., 62: 1263-1283.DOI: 10.1007/s11227-010-0504-1】【Lin, X., Y. Wang, Q. Xie and M. Pedram, 2015. Taskscheduling with dynamic voltage and frequencyscaling for energy minimization in the mobile cloudcomputing environment. IEEE Trans. ServicesComput., 8: 175-186.DOI: 10.1109/TSC.2014.2381227】。
13.A Multi-Objective Task Scheduling Algorithm forHeterogeneous Multi-Cloud
Environment
大多数的算法的目标是减少整体的完成时间，而没有考虑使服务器的整体代价最小化，而且大多数的算法只适用于单一的云环境。本文提出了一种在异构云环境这的多目标任务调度算法。平衡总体完成时间和整个代价。
14.A Scheduling Strategy on Load Balancing of Virtual Machine Resources in
CloudComputing Environment(2010)
在云计算环境中的当前虚拟机（VM）的资源的调度主要考虑系统的当前状态，但很少考虑系统变化和历史数据，这总是导致系统负载的不平衡。鉴于虚拟机资源调度负载均衡的问题，本文提出了对基于遗传算法的虚拟机资源负载均衡调度策略。根据历史数据和系统的当前状态，和遗传算法；这种策略提前计算所需的虚拟机资源部署之后将对系统造成的影响，然后选择最少影响的算法。通过这种算法达到了最好的负载平衡并减少了或避免了动态迁移。这种算法经过部署之后解决了传统算法带来的负载不平衡问题和高迁移代价。
由于在云计算平台的资源的高度动态异构性，虚拟机必须适应云计算环境的动态，以便充分利用其服务和资源，以实现其最佳性能。但是，为了提高资源利用率，资源必须被合理的分配，并且也必须保障负载平衡。因此，如何调度VM 资源以实现在在云计算中的负载平衡，并提高资源利用率成为一个重要的研究点。
目前在云计算中，主要是考虑了在虚拟机的资源调度时系统的当前状态，但很少考虑调度前的状态，和调度之后对系统负载的影响，通常会导致负载不平衡问题。大部分的负载平衡的存在VM迁移[5]。然而，当整个VM资源被迁移，由于VM资源的大粒度的和在迁移过程中大量数据的传送，以及虚拟机服务的悬挂，使迁移成本成为问题。本文提出了一种调度策略，以实现负载均衡。根据历史数据和目前的状态，并通过遗传算法，提前计算当前的需要部署的虚拟机设备资源被安排到每个物理结点上将会带来的影响，然后选择对系统有最少影响的调度方案。该方法实现了最佳负载平衡，并减少或避免了动态迁移。解决了由传统调度算法带来的负载不均衡和高迁移代价问题。
VMware分布式资源调度器【VMWare, “VMware DRS - Dynamic Scheduling of SystemResources,” https://www.wendangku.net/doc/3c10397043.html,/cn/products/vi/vc/drs.htm l,2009.】是一种工具通过利用在虚拟环境中可用的资源来分发和平衡计算量。VMware分布式资源调度器持续监控在资源池中的资源利用率，然后根据预先定义的规则例如业
务需求的和改变优先级指导在虚拟机可用的资源的智能分配。如果一个或者多个虚拟机上工作负载发生了戏剧性的改变，VMware分布式资源调度器会重新分配物理服务器上的虚拟机，并通过VMware VMotion迁移虚拟机到不同的物理机服务器上。通过动态迁移达到了系统负载的平衡，但是频繁的动态迁移会占用大量的资源，最终导致整个系统性能的下降。
15.A Workload-aware Resources Scheduling Method for Virtual Machine(2015)
本文提出了一种负载感知的CPU资源调度方法（WARS）。WARS使用分配的credits和消耗的credits判断虚拟机的CPU资源需求，并根据虚拟机的需求，动态的调整CPU资源。CPU资源的调整转换成虚拟机权重的增加或减少。
当前的虚拟化技术使用静态的资源配置机制。底层物理资源，例如CPU，不能得到充分利用。1）虚拟机的工作负载通常是变化的。为了满足VM的资源要求，VM的资源必须按照其峰值需求来分配。虚拟机的资源会被浪费除了在峰值状态下。2）一些虚拟机的工作负载很轻，但他们占据物理机的资源。空闲的资源不能被工作负载较重的虚拟机利用；3）某些应用已完成，但用户可能释放该虚拟机，使得VM的资源被浪费。
为了提高CPU资源利用率，一些动态的CPU资源分配方式已经被提出[1-3]。这些方法利用平均CPU利用率或两个连续的的虚拟时钟周期，来推断虚拟机的资源需求。VMM根据虚拟机的资源需求分配CPU资源。为了提高的预测能力，[[4] W. Lixi, X. Jing, Z. Ming, T. Yicheng and J. A. B. Fortes, “Fuzzy Modeling Based Resource Management for Virtualized Database Systems”, Proceedings of the IEEE 19th International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems, (2011).
[5] R. Jia, W. Yudi, G. Jiayu and X. C. Zhong, “DynaQoS: Model-free Self-tuning Fuzzy Control of Virtualized Resources for QoS Provisioning”, IEEE Nineteenth IEEE International Workshop on Quality of Service, (2011).]作者用模糊建模来学习和预测虚拟机的CPU资源需求。然而CPU资源度量例如CPU利用率，响应时间和吞吐量在预测工作负荷时不是特别有用。
本文提出了一种负载感知的CPU资源调度方法（WARS）。WARS使用分配的credits和消credits判断虚拟机的CPU资源需求，如果在调度期间，虚拟机没有
使用分配给他的credit，也就意味着虚拟机需要较少的CPU资源，相反，如果在调度之前虚拟机使用了所有分配给它的credit，也就意味着虚拟机需要使用较多的CPU资源，分配的credit和消耗分配的credit的比率可以更加精确判断出CPU 真正的资源需求。基于虚拟机的CPU资源需求，在接下来的调度WARS会调整虚拟机的CPU资源。WARS的CPU资源的调整转化为虚拟机权重的增加或减少。
结果表明：1）根据判断CPU的需求，基于此对预测工作负载更有用；2）部署在了VMM层，而不依赖VM。
WARS Architecture
我们提出了工作负载感知的CPU资源调度方法（WARS），提高了CPU的整体利用率。WARS是一个周期性的分配算法。，每一个周期循环判断CPU资源，对权重进行调整，WARS S使用分配的和消耗的credit来判断VM的CPU资源需求，从而可以进一步提高预测能力。基于该预测信息，WARS将动态调整CPU资源。WARS的CPU资源的调整转化为虚拟机权重的增加或减少。
实验结果表明，WARS可提高CPU资源的整体利用率。我们还表明，WARS 的性能是受调度周期的影响。今后，我们将研究调度周期的时间。
VM的CPU利用率不高，但在VM中的一个或多个的VCPU都非常高。也就是说，不同VCPU的CPU利用率是不平衡的。例如，如果一个单线程应用运行在多VCPU的虚拟机上，那么只有一个VCPU处于忙碌状态，接下来，我们将研究：在虚拟机的一些VCPU的利用率是高的，但是处于同一个虚拟机的其他VCPU的利用率是低的条件下。研究在同一个虚拟机中VCPU的CPU资源的调整机制。
16.A New HybridVirtual Machine Scheduling Scheme for Public Cloud(2015)
先来先服务的主要缺点是响应时间和周期时间都很慢。虚拟机的重分配增加