多核结构下的虚拟机vcpu调度策略和机制研究

多核结构下的虚拟机vcpu调度策略和机制研究

云平台可以通过公立网络为用户提供基本结构服务。根据需要动态扩展是云计算基层结构的主要优点之一。服务器虚拟化是云计算基层结构建设的重要途径。例如，pythonec2是一个典型的例子，它以虚拟机的形式为用户提供基础结构服务。系统虚拟化允许多个虚拟机同时安全地运行在同一个物理上，充分利用物理资源，有效防止数据处理服务器的服务器延迟和能源。此外，虚拟机转换技术是为数据处理资源的动态分配和负载平衡提供有效技术方法的优质途径。目前，流行的虚拟化系统包括vm、xen、虚拟server和linux用户模式。多核处理器的出现扩大了虚拟化技术的优势.在基于多核物理平台的虚拟机系统中,处于虚拟机与硬件层之间的虚拟机监视器能采用灵活的策略将物理处理单元分配给上面的虚拟机,从而有效地满足虚拟机的资源需求.随着工作负载的动态变化,它还能动态地重新分配物理处理单元.虚拟机中的CPU(简称为VCPU)可以分时复用所有的物理处理单元,也可以被限制访问仅仅部分指定的物理处理单元,这给虚拟机系统的资源分配带来更大的柔韧性.因此,以多处理器为物理平台的虚拟机系统显示出更大的优势.虚拟机VCPU调度器主要负责物理处理器资源在各个虚拟机之间的分配与调度,本质上即把各个虚拟机中的VCPU按照一定的策略和机制调度在物理处理单元上.由于虚拟机系统中的各个虚拟机所运行的负载呈现多样化的特性,如何满足各个虚拟机的性能要求,同时提高系统的整体性能,是虚拟机VCPU调度重点关注的问题.虚拟机VCPU调度是影响虚拟机系统性能的一个关键因素.在虚拟机系统中,由于增加了虚拟机监视器层,操作系统的部分功能下移,改变了传统的软件栈结构,使得虚拟机VCPU的调度面临许多新的问题.例如,虚拟机监视器由于缺乏对工作负载特征和客户操作系统内核行为的感知,会导致虚拟机系统无法满足特定应用程序的性能要求或影响系统的整体性能.因此,如果我们将传统操作系统的调度策略和机制不加修改地移植到虚拟机VCPU调度器中,虚拟机系统将会产生性能偏差甚至严重的性能下降.多核处理器应用于虚拟机系统中,更增加了虚拟机VCPU调度的复杂性和挑战性.多核处理器具有许多新的调度敏感的特征,如cache共享、多核的不对称性等等.如何充分发挥多核处理器的优势,是多核环境下虚拟机VCPU调度必须考虑的问题.目前,随着虚拟化技术和多核技术应用的日益普及,多核环境下虚拟机VCPU的调度引起了研究领域广泛地关注.本文围绕多核环境下虚拟机VCPU调度所面临的主要问题和挑战展开讨论,对目前已提出的解决机制进行了深入分析和讨论,指出了它们的局限性,提出了未来研究方向的建议.1在多核环境下，虚拟机系统框架和二级布局框架1.1主机的控制和管理权限典型的基于多核平台的虚拟机系统可分为3层(如图1所示):硬件层、虚拟机监视器层及虚拟机层.硬件层提供多个物理执行核、内存及I/O资源,虚拟机监视器层拥有对系统资源的完全控制能力和管理权限,包括资源的分配、监控和回收.每个虚拟机拥有自己的虚拟硬件(如CPU、内存和I/O设备),多个虚拟机复用下面的物理机,每个虚拟机中的VCPU的个数可以大于、等于或小于物理处理单元的个数.应用程序运行在各个虚拟机实例中,虚拟机中的操作系统被称为客户操作系统(guestOS),负责管理虚拟机中的虚拟资源.系统虚拟化提供了多个隔离的执行环境,这种以虚拟机为粒度的抽象提供了优秀的封装性,虚拟机之间具有很强的隔离性,虚拟机与硬件没有直接的关联.虚拟机监视器层作为特权层能够提供前所未有的功能.1.2两级调度框架通过虚拟机系统的结构与功能划分可以看出,客户操作系统与虚拟机监视器构成了虚拟机系统的两级调度框架.图2是一个多核环境下虚拟机系统的两级调度框架.虚拟机监视器负责第1级调度,即VCPU在物理处理单元上的调度;客户操作系统负责第2级调度,即线程或进程在VCPU上的调度.两级调度的调度策略和机制不存在依赖关系.两级调度框架增加了系统的灵活性,异构负载虚拟机可以同时安全地运行.VCPU可以调度在多个物理处理单元执行,也可以与物理处理单元建立一对一固定的映射关系.VCPU既能分时复用物理处理单元,也可以空间复用物理处理单元.VCPU调度器可以采用任意的策略来分配物理资源,满足虚拟机的不同需求.但是,两级调度框架可能带来很多负面的问题.如优先权失效,分配不公平等.假设有2个虚拟机A和B,A中运行的是CPU受限型负载,而B运行的负载既包括CPU受限型负载也包括对响应性要求很高的I/O受限型负载,在虚拟机B中,客户操作系统赋予I/O受限型负载较高的优先级.但是如果VCPU调度器不相应地赋予虚拟机B较高的优先权,那么B中的I/O受限型负载仍然不会获得较高的性能.在两级调度框架中,VCPU调度器难以直接建立线程与物理处理单元的映射关系,这种两级调度框架会使VCPU的调度在很多情况下难以实现期望的功能,导致了虚拟机VCPU调度面临的诸多问题,后面我们会详细讨论这些问题.2在多核环境下，虚拟机vmp交付的主要问题和挑战结合虚拟机系统结构、两级调度框架及多核处理器的发展,总结现有的研究,归纳起来多核环境下虚拟机VCPU的调度主要面临以下问题和挑战.2.1桥接语义目标多核平台虚拟机系统所采用的体系结构导致了两级调度框架中的2个主体——客户操作系统与虚拟机监视器——间存在着语义缝隙.这里所指的语义缝隙,是指客户操作系统与虚拟机监视器之间因为在整个系统中功能的划分而导致的对上层应用程序或底层硬件特征认知的差异.语义缝隙是不可避免的,因为不同的客户操作系统有其自己的一套复杂机制和策略,它们仅仅共享部分抽象,如虚拟地址空间、线程控制、网络协议和文件系统格式等.因此,为了保持可扩展性,虚拟机监视器只能拥有轻量级组件和有限的接口.语义缝隙的存在,妨碍了虚拟机监视器对每个虚拟机有效的硬件资源分配.具体表现在以下2个方面:1)由于虚拟机监视器无法感知运行在虚拟机中的工作负载的特性,因此虚拟机系统工作负载的多样化和不可预测性,会使CPU资源分配变得困难,对具有时间性要求的工作负载,会产生更大的影响.2)虚拟机监视器没有建立I/O事件与阻塞任务的关联,这会使响应性降低,尤其是在多种负载并存的情况下,影响更为严重.综上所述,语义缝隙会严重影响VCPU调度器合理地为每个虚拟机分配计算资源,从而难以保证应用程序的性能.这是所有虚拟机VCPU调度所面临的一个根本问题.对于多核环境下的虚拟机系统,由于多个物理核共享最后一级cache、任务或者线程间还存在着对共享cache的竞争,语义缝隙的影响会变得更大.如何桥接语义缝隙,是虚拟机VCPU调度研究者们必须面对的问题.2.2多处理机操作系统中的同步机制现代操作系统为支持多处理器而对内核进行了多方面的优化,增加了一些新的机制,如多处理器调度、同步机制等.其中同步机制会因为虚拟化技术的引入而产生较大性能开销.下面我们介绍在典型的多处理机操作系统中具有普遍性的自旋锁同步机制以及Solaris系统的cross-calls机制在虚拟化系统中所产生的问题.2.2.1不允许占用旋以锁的内核进程自旋锁是支持多处理器的操作系统内核中实现的一种主要的同步机制,它避免了阻塞型同步机制产生的上下文切换的开销,但它要求持有锁的时间很短.一个处理器拥有自旋锁的时间越长,其他处理器不得不自旋以等待释放该自旋锁的时间就越长,这样会导致优先级高的进程得不到及时调度.因此,在典型的支持多处理器的操作系统如Linux中,不允许抢占持有自旋锁的内核进程.在虚拟机系统中,虚拟机监视器在调度时,缺乏对客户操作系统内核自旋锁持有情况的感知,会抢占一个正持有自旋锁的VCPU,此时,同一个虚拟机中的其他VCPU可能运行在其他的物理核上,等待着自旋锁的释放,这样会浪费大量的处理器周期,多达几十毫秒,严重地影响了系统性能.自旋锁开销增大是采用自旋锁同步机制的多处理器操作系统应用在虚拟化系统中时面临的一个普遍问题,是虚拟机VCPU调度研究者应该关注的问题.2.2.2远端监控和cuSolaris操作系统采用cross-call(使用同步软件中断)机制来实现不同CPU之间的通信.当一个cross-call被调用时,在得到硬件通知软件中断已经被传送到远端CPU之前,系统处于忙等状态.对于SPARC处理器,如果有其他未完成的待处理中断,远端CPU会发出一个NACK信号,此时,发送者会不断重试直到接收到ACK信号.如果远端CPU被抢占,那么发送者会处于一直自旋等待状态.在虚拟机系统中,由于虚拟机监视器缺乏对客户操作系统内核机制的理解,往往会抢占如上所述的虚拟机中的远端VCPU,从而导致其他VCPU的忙等延长,降低系统的性能.cross-calls对虚拟机系统性能的影响,是Solaris应用到虚拟机系统应该解决的问题.2.3多核多槽系统性能表现多核处理器的各个核之间,通常共享最后一级cache.运行在操作系统上的任务或者线程希望有效、公平地共享cache这一珍贵资源.任务或线程对cache的共享分为2类:一类为干涉性共享;另一类为有益性共享.如果任务间互相独立,没有数据共享,那么这类任务对cache的共享为干涉性共享;如果任务间有数据共享,例如并行负载的线程之间,它们对cache的共享为有益性共享,因为具有同步关系的线程通过cache共享可以实现数据重用,减少了cache缺失.有益性共享会对系统性能带来很大的提高,尤其是在多核多槽系统中表现得更为明显.多核多槽服务器中,处在同一个核上的处理器单元(如超线程)典型地通过共享L1进行通信,延迟约为1～2个处理器周期;处在同一个槽但不同核的处理器单元典型地通过共享L2进行通信,延迟约为10～20个处理器周期;处在不同槽中的处理器单元通过cache一致性协议或者内存共享进行通信,延迟多达几百个处理器周期.图3是一个典型的多核多槽系统结构图.由上述可以看出,对于有数据共享的多个并行线程,将它们调度在共享最后一级cache的各个核上,会有效地提高系统性能.近年来,已经有大量研究关于线程间如何有效、公平地共享cache这一珍贵资源,但在虚拟机系统中,如1.2节所述,由于VCPU调度器不能直接建立线程与物理处理单元的映射关系,它所采用的调度策略可能是与客户操作系统的调度策略相背离的,因此会抵消客户操作系统所作的努力.VCPU调度器如何实现任务间或者线程间对cache有益的共享,充分发挥多核处理器的潜力,是一个大的挑战.另外,调度的cache亲和性也是多核环境下虚拟机VCPU调度应考虑的一个重要因素.2.4不对称调度算法不对称多核处理器典型的由多个指令集相同但大小、频率和能耗皆不同的核构成.通常,不对称多核处理器由2类核构成:快核和慢核,其中快核具有更大的体积、更高的频率以及更复杂的乱序执行流水线和更大的能耗,而慢核具有较小的体积、较低的频率和简单的流水线和较低的能耗.和对称多核处理器相比,不对称多核处理器更适合多样化的工作负载.例如,对于一个运行在多核处理器上的含有串行部分的并行程序,串行部分往往是限制其加速比的瓶颈,如果用快核运行串行部分,而慢核运行并行部分,能有效地减轻可扩展性瓶颈问题.目前,已有很多研究者致力于不对称核调度算法的研究,比较流行的不对称调度算法有3类:第1类是通过持续地监控性能或者通过基于应用的静态统计信息的分析模型来决定线程在不对称核上的调度策略,见文献;第2类是将并行程序的串行部分调度在快核上而把并行部分调度在慢核上,见文献;第3类是公平地共享快核或者给快核分配更重的负载,见文献.在虚拟机系统中,两级调度系统的任何一级如果缺乏对不对称核的支持,都无法发挥不对称多核处理器的潜力,甚至产生相反的影响.例如,如果虚拟机监视器不能感知核的不对称性,那么,它可能把客户操作系统认为“快”的VCPU一直映射到慢的核上,相反,如果客户操作系统不具备不对称感知能力,它可能会把运行在快核上的VCPU上的线程迁移到运行在慢核上的VCPU上,进行不必要的负载平衡,此外,还可能造成程序运行性能的不稳定.因此,如果虚拟机VCPU调度器不支持不对称核,会妨碍不对称多核处理器在虚拟机系统中的应用,导致虚拟机的应用受到限制.这是多核环境下虚拟机VCPU调度面临的另一个挑战.3研究解决机制针对上述的虚拟机VCPU调度所面临的问题和挑战,研究人员进行了大量研究,提出了一些解决相应问题的机制,下面我们从上一节所提的4个方面介绍和分析目前的研究已经提出的解决机制.3.1混合负载情况下的i/o受限型负载感知机制Xen的Credit调度器增加了所谓的“boosting”机制.“boosting”机制利用I/O受限型负载的基本特性识别I/O受限型负载并给予运行I/O受限型负载的VCPU以相对高的优先级,提高了响应性.Credit调度器为VCPU提供了3种优先级:boost,under和over,其中,boost优先级最高,而over优先级最低.一个VCPU的缺省优先级为under,当它耗尽分配给它的时间片时,优先级会变为over.一个处于over优先级的VCPU会被强迫释放物理CPU,进入等待队列.假如一个VCPU仅运行I/O受限型任务,它会频繁地被阻塞,消耗的CPU时间片很少.当一个与它对应的I/O事件发生时,虚拟机VCPU调度器会唤醒它,如果它此刻的优先级为under,那么它会立即被赋予最高优先级boost,进而抢占优先级为under的VCPU,因此提高了响应性和I/O吞吐率.这个机制的前提是一个VCPU仅运行I/O受限型任务,因此,对于混合负载的虚拟机,“boosting”机制就失效了.Kim等人提出了混合负载情况下I/O受限型负载感知的调度机制.这个机制主要包括2部分:1)I/O负载的感知.通过监测虚拟机中客户操作系统内核与硬件的低级交互行为,结合基于I/O负载特征的灰盒知识来推断和识别I/O负载.2)“partialboosting”机制.一旦有I/O事件发生,对应的VCPU马上被调度到物理CPU上进行I/O事件的处理,完成之后立即将CPU归还给运行计算型负载的VCPU(如果有的话),这样既保证了I/O受限型负载的高响应性,同时也不违背调度的公平性原则.I/O受限型负载要求高响应性,由于目前虚拟机I/O性能普遍较差,除了对虚拟机I/O模型进行优化,如何最优调度I/O负载虚拟机是研究者们所关注的重点.文献和文献提出的2种机制提供了克服语义缝隙、提高I/O受限型负载响应性的有效途径.Credit调度器的“boosting”没产生额外开销,但只适合纯I/O受限型负载虚拟机与其他负载(如计算型负载)虚拟机并存的情况,应用范围有限.Kim等人提出的“partialboosting”调度机制适用范围更广,但也存在较大的缺陷.首先,他们对I/O受限型负载的推断是基于一个前提,即I/O负载仅仅消耗少量的CPU时间而计算受限型负载消耗较多的CPU时间,而事实上,有很多情况是违背这个前提的.例如,当操作系统产生中断,处理内核数据而并不切换虚拟地址空间的时候,一个I/O受限型任务表现出消耗较长的CPU时间,另一方面,当一个计算受限型任务被抢占的时候,它表现出消耗较少的CPU时间.因此,他们的推断是不够精确的.尽管他们采用了静态统计方法来提高精确性,但静态统计方法是不够智能的.让虚拟机监视器采用机器学习的方法来动态修正推断误差,虽然能提高智能性,但该方法由于虚拟机监视器不能准确地判别客户操作系统的内核操作而难以实现且会产生较大的额外开销.其次,“partialboosting”机制包含一个附加机制,即I/O任务与I/O事件的关联机制,由于I/O设备的多样性,建立一个具有较大通用性的关联机制是较难的.第三,“partialboosting”机制是基于单核物理平台实现的,没有考虑VCPU的迁移及同步问题.因此,I/O受限型负载感知的虚拟机VCPU的调度存在很大的研究空间.未来的研究可从2方面努力:1)研究有效精确的I/O负载的感知机制;2)在混合负载的情况下,设计调度机制时应充分利用多核处理器的优势,以提高I/O负载的响应性.“boosting”和“partialboosting”这2种机制都是针对I/O受限型负载的推断机制.并行负载由于其线程间具有较大的同步和数据共享,同样也是虚拟机VCPU调度研究者所关注的一类负载.对并行负载的准确识别可以为设计有效的VCPU调度机制来降低因线程间同步产生开销和充分利用多核的共享cache提供依据.Tam等人利用现代处理器自带的硬件性能计数器监控微结构事件来判断线程是否跨芯片访问远程cache,从而推断并行负载线程的共享模式.由于该方法主要基于硬件计数器,因此开销很小.虚拟机监控器通过提取性能计数器统计信息来推断负载特征是未来的一个研究方向.分析上面几种机制,可以发现,它们在本质上都是通过监控客户操作系统对虚拟硬件的访问来构造客户操作系统抽象,进而判断负载类型的.3.2建立滑动占用窗口机制组调度算法是一种经典的应用于并行负载调度的调度算法,它可以有效地降低并行负载的同步开销.组调度的基本思想是:线程划分为组,称为gang,gang中的线程在不同的处理单元上同时运行,线程与处理单元之间保持着一对一映射关系,线程同时被抢占且同时被重新调度.将组调度思想引入到虚拟机VCPU调度中,即可巧妙解决自旋锁问题.具体地,同一个虚拟机中所有的VCPU构成一个gang,gang中的所有VCPU分别映射在对应的物理核上,它们保持同时被抢占且同时被调度.显然,在这种调度机制下,所有VCPU都是同步调度,不存在忙等的问题.Chuliang等人提出了一个虚拟机VCPU的混合调度框架,他们把虚拟机分为两类:并行负载虚拟机和高吞吐率虚拟机.对于并行负载虚拟机,采用同步调度机制,即让并行负载虚拟机中的所有VCPU同时被调度且同时被抢占.从本质上来说,这种同步调度机制即采用了组调度的思想;而对于高吞吐率虚拟机,由于没有较高的同步要求,则采用异步调度机制.Uhlig等人提出了2种锁持有者抢占避免调度机制.一种被称为入侵式锁持有者抢占避免调度机制,而另外一种被称为非入侵式锁持有者抢占避免调度机制.入侵式锁持有者抢占避免机制要求修改客户操作系统,在一个VCPU即将持有自旋锁之前,由客户操作系统通知虚拟机监视器,告知在未来的n秒内,不允许抢占该VCPU.同样,当一个VCPU释放自旋锁后,由客户操作系统通知虚拟机监视器该VCPU愿意被抢占.n值的选择依赖于操作系统所设定的自旋锁的持有时间.由于入侵式锁持有者抢占避免机制需要修改客户操作系统,因此不适用于全虚拟化系统.非入侵式锁持有者抢占避免机制不要求修改客户操作系统,它是通过划分“安全点”来判别安全的抢占时机.“安全点”指客户操作系统内核线程不持有自旋锁的时间点.基于安全点概念,Uhlig等人提出了一个滑动抢占窗口调度机制.滑动抢占窗口机制的基本思想是:对于一个VCPU,如果上一次的抢占点在给它正常分配的时间片结束点之后,意味着它多占用了物理CPU时间,那么本次的强制抢占点会提前;反之,如果上一次的抢占点在给它正常分配的时间片结束点之前,意味着它被占去了应有的时间份额,那么在本次调度中,会把强制抢占点推后.滑动抢占窗口调度机制,在保证调度公平性的情况下,避免了内核自旋锁带来的影响.Wells等人提出了一种带有硬件支持的自旋管理调度机制.他们提出了一个简单的被称为SDB(spindetectionbuffer)的硬件机制用来检测处于自旋状态的VCPU.一旦有这样的VCPU,调度器抢占它并调度不同的具有生产性的VCPU,从而提高了整个系统的吞吐率.抢占自旋VCPU的调度机制,在一定范围了减轻了VCPU调度时自旋锁带来的影响,提高了系统吞吐率.上述的3种机制,从不同的角度解决了自旋锁问题,但都有其局限性.组调度算法有效地避免了同步所带来的开销,但它受到VCPU的数目必须小于物理核数目的限制.而且,一个虚拟机中的VCPU不管是否将完成有用的工作,都会被统一调度,这会影响物理资源的有效利用,影响了系统的可扩展性,另外,组调度排斥其他的调度算法,影响了系统的柔韧性和灵活性.Uhlig等人提出的2种锁抢占避免机制有较大的额外开销.Wells提出的调度机制采用硬件来检测自旋的VCPU,虽然开销较小,但这种调度策略的目标是提高整个系统的吞吐率,不能保证特定的应用程序的QoS(qualityofservice),而且这种策略只适用于虚拟机系统中VCPU的个数大于物理核个数的环境.未来的工作可以从2方面努力:一是优化锁抢占避免调度机制;二是考虑修改自旋锁原语.前者可考虑如下3个方面:一是安全点的精确推断;二是建立有效机制保持调度的公平性;三是减小机制本身的开销.Solaris的cross-call机制问题,妨碍了Solaris系统在虚拟化系统的应用,至今尚没有相关文献提出有效的解决机制,是未来的一个研究点.3.3线程间的静态映射机制2.3节已经谈到,由于虚拟机系统采用的是两级调度框架,从虚拟机监视器级的调度来实现应用程序同步线程对cache的有益性共享,是研究者们关注的一个问题.Wells等人提出了逻辑划分的机制,即在多个虚拟机并存的情况下,如果VCPU的数量大于物理CPU的数量,可将同一个虚拟机中的VCPU划分为组,建立组与槽的映射关系.如图4所示,虚拟机1的3个VCPU只能运行在槽1的2个物理核上,同样,虚拟机2的3个VCPU也只能运行在槽2上.由于虚拟机1中运行的是并行负载,如果并行负载的各个线程间具有较多的数据同步,那么在这种情况下虚拟机1中的线程之间就能实现有益的cache共享,同时逻辑划分还满足了调度的cache亲和性.我们不难发现,这个机制有很大局限性.首先,这种逻辑划分实际上是一种静态划分,不能适应系统负载的变化.比如,假设物理处理器是双路4核的,初始情况下,有2个虚拟机:虚拟机A和虚拟机B,通过逻辑划分,2个虚拟机的VCPU分别运行在不同槽的4个核上,到了某一时刻,虚拟机B停止工作,但虚拟机A却依然只能运行在4个核上,没能充分利用物理资源.虽然虚拟机监视器提供了动态改变虚拟机VCPU数量的接口,但相应的软件机制会产生额外的开销.其次,这种静态逻辑划分不适合并行负载与其他负载混合运行在同一个虚拟机中的情况,应用范围极为有限.Tam等人提出了一个在多核平台上共享感知的调度机制.他们首先推断线程间的共享模式,然后动态地将具有数据共享的线程划分为组,调度在同一个槽的物理核上,实现具有数据共享关系的线程在cache上的有益性共享.但该机制难以扩展到虚拟机系统中,因为线程与VCPU之间的映射是由客户操作系统决定的,虚拟机监视器本身难以确定线程与物理核的映射关系.但如果线程与VCPU是绑定的,问题会变得相对简单,VCPU调度器可以简单地借鉴上述机制实现线程间cache有益性共享,但这只是一种特殊情况.综上所述,对于混合负载虚拟机,要实现线程间对多核处理器最后一级cache的有益性共享,必须有一个合适的机制来建立线程与物理核的映射关系,这是研究者们未来的一个重要研究方向.对于纯并行负载虚拟机,可通过空间划分,建立VCPU群组与物理核群组的映射关系,从而有效地支持多核共享cache的有益性共享,但目前已有的静态划分机制,有较大的应用局限性,如何实现动态的划分,也是虚拟机VCPU调度研究者未来研究的一个方向.3.4不对称感知调度虚拟机系统的两级调度框架决定了要在虚拟机系统中实现对不对称核的支持,虚拟机监视器和客户操作系统都应该进行相应的优化.优化包括2个方面:一是建立不对称感知的机制,二是对调度算法优化,