随着多核硬件技术的迅速发展和应用对计算能力需求的不断增强,多核虚拟机应用也越来越广泛。但多核虚拟机会引发锁占用的可扩展性问题,锁占用严重影响系统的整体性能。本文基于Linux的完全公平调度器(CFS)设计并实现了一个高效的瞬态协同调度算法,能够高效地解决锁占用问题并获得更好的系统性能。实验结果表明,相比Linux 2.6.38内核,该算法可以显著地提高系统性能,在SysBench.OLTP的测试用例中系统整体性能最多提高到3.41倍,并且对调度公平性几乎没有影响。
Multiprocessor (MP) virtual machines (VMs) are widely used in cloud environments with the development of MP hardware and the demands for greater computing power. However, MP VMs suffer from the lock holder preemption (LHP) issue, which causes significant system performance degradation. This paper describes an efficient transitory co-scheduling algorithm based on the Linux CFS scheduler that effectively bypasses the guest spin lock loop to achieve better system performance. Tests show that this method significantly improves system performance (up to 3.41 fold performance advantage over the original Linux kernel 2.6.38 with SysBench.OLTP 4-VM case), while at the same time improving system latency with little to no effect on scheduling fairness.
狭义上说,虚拟化是一种在物理机器上虚拟出多个虚拟机实例的技术,这些虚拟机可以透明地共享物理资源。虚拟化技术不仅可以提高服务器的可靠性,增加服务器资源的利用效率,还能极大简化系统的管理复杂度。基于虚拟化技术,云计算(如亚马逊云服务)能为人们提供灵活和丰富的计算资源服务。
随着应用对计算能力需求的不断增长,多核虚拟机的应用也越来越广泛。但多核虚拟机却可能引发诸如锁占用等新问题。在多核环境中操作系统内核多用自旋锁来保护共享资源。相比另一种机制的锁——互斥量(也称为信号量), 自旋锁在等待获取锁的持有权时会一直自旋,直到锁被释放为止,因此自旋锁响应速度更快。但使用自旋锁必须遵守一个基本原则: 持有锁的任务应该在获取锁后要尽快地完成对共享资源的访问,然后立即释放锁,并且在持有锁的期间任务不可以被调度出去而中断执行。但在虚拟机应用中,这个应用准则被破坏了。这是因为虚拟机中的虚拟CPU在宿主机中只是一个普通任务进程,而普通进程在宿主机中运行时随时都有可能被调度出去进入休眠状态。由于客户机虚拟CPU是否正在持有锁对于宿主操作系统是不可见的,如果一个正在持有自旋锁的虚拟CPU因为某些原因被宿主机调度出去,而这时有其他虚拟CPU正在等待这个自旋锁,则会因为锁被长期占用而需要等待额外更长的时间。这个时间通常是几毫秒,而正常情况下一个自旋锁一般只会被持有几百微秒左右。锁占用会导致CPU资源的巨大浪费,严重降低系统的性能。
锁占用现象的提出最初见于并行计算领域[1,2], 为了解决锁占用问题,相关学者[3,4,5,6]提出了协同调度算法的解决方法,其主要思路是协同调度所有任务来避免锁占用的发生。在虚拟化环境中,协同调度同组(同一个虚拟机)所有的虚拟CPU使得每一个虚拟CPU都获得执行机会,锁的持有者因此可以释放掉锁,也就消除了锁占用现象。但协同调度算法存在一些固有的缺陷,如CPU使用碎片化和系统响应不确定等[7]。Uhlig[8]提出了2种解决方案: 修改客户机操作系统(即类虚拟化)和增加一个无锁机制的驱动模块。类虚拟化的解决方案的最大缺陷是不够通用,因为并不是所有的操作系统都是开源的,而添加设备驱动程序因其实现复杂也不够通用。Johnson[9]提出了负荷控制管理机制的解决方法,但无法避免频繁的系统调用和上下文切换等弊端,系统开销过大。Sukwong[10]提出了平衡协同调度算法,通过将虚拟CPU与物理CPU进行简单的一一绑定来尽量避免锁占用发生,但不适用于虚拟CPU数量大于物理CPU的系统过载场景。Intel[11]和AMD[12]提供了硬件支持检测锁占用的功能,基于此Dong[13]提出了一个锁持有任务简单让出的解决方法,在发生锁占用现象时将等待锁的虚拟CPU任务暂时让出CPU, 从而避免CPU资源无谓的浪费。但因为其策略过于简单,对虚拟CPU的控制不够精准,会引入不必要的上下文切换,对系统性能的提升相对有限。
本文提出了一个高效的瞬态协同调度算法——Lockvisor。该算法在发生锁占用时,借助CPU硬件完成等待锁虚拟CPU的识别,并瞬态协同调度持有锁和等待锁的虚拟CPU来消除锁占用。瞬态协同调度算法对调度的公平性几乎没有任何影响。为面向不同的应用场景,算法包括了基本瞬态协同调度、选择性瞬态协同调度、延迟瞬态协同调度3种调度策略。从性能、可扩展性、系统延迟和调度公平性等4个方面来测试Lockvisor的性能。结果表明: 选择性瞬态协同调度算法能够满足绝大多数应用关于性能和系统响应实时性的需求。Lockvisor在SysBench性能测试环节中,基本瞬态协同调度和选择性瞬态协同调度策略的系统性能分别提高到Linux原生内核的3.41和2.78倍。
在操作系统中往往通过锁来实现保护共享资源。锁主要分为2种: 自旋锁和互斥量。自旋锁避免了上下文切换,具备更好的性能和更快的系统响应速度,但在自旋过程中会浪费CPU资源; 互斥量会引入上下文切换,但能够避免因自旋等待而导致的CPU资源浪费。因此自旋锁的设计前提是假定锁持有者只持有锁很短的时间(通常是几十或几百微秒), 并且在持有锁期间任务不可以被调度出去。因为自旋锁性能更好,操作系统内核中大量应用了自旋锁。内核开发者严格遵守自旋锁的使用准则,因此锁占用几乎不会发生。但在虚拟化应用场景中,虚拟机对于虚拟CPU调度的特点导致了锁占用频繁发生。
任务的调度行程包括调入时间和调出时间。当持有自旋锁任务被调度出去时,如果这时等待该锁的其他任务正在运行,等待锁任务因为无法获得锁而不得不进入长时间自旋状态,导致CPU资源的巨大浪费。图1中 T0和 T1代表了重叠时间窗口,锁占用的开销同时间窗口大小成正比。持有锁任务vCPU0和包括vCPU1、 vCPU2及vCPU3在内的等待锁任务分别在不同的物理CPU上运行。重叠时间窗口有可能完全重叠(见vCPU2运行队列)或部分重叠(见vCPU1和vCPU3运行队列), T0可能等于
在进入自旋状态时,自旋锁通过重复执行PAUSE指令来降低CPU功耗,因此这条指令可以用来感知处理器是否处于自旋状态。CPU硬件也集成了PLE (pause loop exit) 功能用来检测锁占用,具体是通过设定PLE_GAP和PLE_WIN来实现的,其中PLE_GAP是PAUSE指令连续两次执行的时间差, PLE_WIN是正常执行流程中自旋循环中执行PAUSE指令的最大上限值。当一个等待锁任务在自旋时执行PAUSE的次数超过PLE_WIN值,则可以简单认定此时锁占用现象正在发生(并不严格保证识别的绝对准确性), CPU硬件通过一个中断来提示锁占用发生了。这两个值的取值与锁的具体应用场景有密切关系。PLE技术提供了一个从硬件层面来识别锁占用的手段,可以用来检测虚拟机客户端的锁占用现象。
本文提出一种适用于多核虚拟机的高效瞬态协同调度算法——Lockvisor。Lockvisor当且仅当在锁占用发生时,通过协同调度的策略使占有自旋锁的虚拟CPU释放锁来消除锁占用,在消除锁占用后停止协同调度并继续遵循之前的调度策略,最大程度保证调度的公平性和效率。
图2中,标注为vCPU的任务进程为虚拟CPU, 灰度相同表示为同组的虚拟CPU(即属于同一个虚拟机); pCPU为物理CPU。基本瞬态协同调度(instant transitory co-scheduling, ITCS)策略在发生锁占用时,会立即调度运行所有不在运行中的同组虚拟CPU。当检测到pCPU上的vCPU1发生锁占用现象时, ITCS迅速调度运行同组的虚拟CPU(包括vCPU0和vCPU2)来消除锁占用。与经典协同调度算法的周期执行的策略不同, ITCS仅仅在发生锁占用时临时将物理CPU分配给非活动的虚拟CPU来实现协同调度。
设计Lockvisor的难点之一是何时终结协同调度状态。协同调度持续时间越长,对调度公平性和效率的影响越大。本文采用了如下策略: 即只发起协同调度,但不主动显示停止虚拟CPU的运行,而是由宿主的本地调度器来决定停止的时机。这样做的优点是避免过多的上下文切换,尽量减少对本地调度器调度策略的影响。另一方面CFS(completely fair scheduler)会自行修正被Lockvisor激活运行的虚拟CPU在下个调度周期的CPU资源分配,最大程度地保证整体调度的公平性。测试表明Lockvisor对调度公平性的影响可以控制到一个非常小的范围。
ITCS能最大限度地提高虚拟机的性能,在发生锁占用时它会立即调度同组的所有非在线虚拟CPU, 但这种策略会对影响其他程序的正常运行状态。消除锁占用的本质问题是让持有锁的虚拟CPU得到执行机会来释放锁,因此仅需调度不在运行状态的持有锁的虚拟CPU就能消除锁占用,并可以尽量减少对调度公平性的负面影响。自旋锁主要用于在内核空间(类似数据库的应用程序也会在用户空间使用自旋锁来提高效率,不在本文论述范围内), 这意味着应用程序在返回到用户空间时一定会释放掉持有的锁。基于这样的事实可以得出: 在用户空间中任务不会持有自旋锁。这意味着可以根据虚拟CPU的运行状态来判断其是否正在持有一个锁。Uhlig[8]率先提出的安全态和不安全态的定义: 安全状态是指虚拟CPU目前正运行在用户空间,因为用户空间中没有内核锁,所以将正在用户空间运行的虚拟CPU调度出去是一种安全行为; 而如果虚拟CPU正运行在内核空间就可能持有锁,则是不安全状态,此时将虚拟CPU调度出去就可能导致锁占用现象。
本文借鉴了类似的思想提出了选择性瞬态协同调度 (selective instant transitory co-scheduling, SITCS), SITCS能够兼顾系统性能和响应速度。图3 中,当出现锁占用时仅仅调度运行在内核空间中的vCPU0, 而运行在用户态的vCPU2不会被立即调度运行。这种策略能够节约更多的CPU资源分配给其他任务,尽量减少对其他任务的干扰。
虚拟机调度策略除了系统性能还应考虑包括服务质量(QoS)、 公平性等很多其他因素。例如, Web服务虚拟机需要尽快响应外部客户的请求,对系统响应的实时性要求很高。在发生锁占用时, ITCS会立即运行同组的非活动虚拟CPU来消除锁占用。但这种激进策略会影响其他正在运行的虚拟CPU的运行状态,可能会中断正在运行中的服务程序的正常执行,虽然这只会在发生锁占用时瞬态发生,但如果系统中锁竞争非常激烈且持续较长时间时,由此带来的影响也不容忽视。
延迟瞬态协同调度算法(deferred transitory co-scheduling, DTCS)采用另一种方法避免了上述缺陷。在发生锁占用时, DTCS不像ITCS那样立即调度运行该虚拟CPU, 而是选择让出该虚拟CPU停止运行。图4中,当检测到pCPU上的vCPU1的发生锁占用现象时, DTCS则立即停止运行vCPU1, 并将其放置在运行队列中合适的位置,以保证vCPU1能够与同组中第一个可能持有锁的虚拟CPU(vCPU2)同时运行或稍微滞后一点运行,避免了因为锁占用导致的资源浪费。DTCS并不同于简单让出策略,简单让出策略只是将等待锁任务推迟放置在运行队列的头部或尾部,运行时机可能过早(虚拟CPU被放置在运行队列头部)或者过晚(虚拟CPU被放置在队列尾部), 很可能会再次产生锁占用现象。而DTCS将等待锁任务推迟到大约能与锁持有任务同时或稍晚于锁持者任务运行来避免CPU资源浪费和消除锁占用,达到协同调度相同的效果。DTCS可以被视作一个有效但不是纯粹的协同调度策略,因为它对虚拟CPU的调度更侧重的是系统整体的QoS。
Lockvisor一共包括了3种调度策略,用于面向不同的应用场景。ITCS通常具备最佳的整体性能,但其稍显激进的调度策略可能会影响其他正在同时运行的任务,对系统的整体响应也会有一些影响。相比之下,DTCS采用了更温和的调度方法,虽然与ITCS相比性能会稍差,但能最大限度保证系统响应速度。SITCS在识别锁持有任务的基础上,只瞬态协同调度持有锁的虚拟CPU, 兼顾了系统性能和响应速度,集成了前2种调度策略的优点,应用性更加广泛。
本文基于Linux 2.6.38内核的CFS实现了Lockvisor。当CPU检测到锁占用现象发生时则立即触发Lockvisor执行相应调度策略。PLE_GAP与PLE_WIN参数的取值决定了识别自旋等待锁任务的准确度。基于以往的经验知识[14], 本文将PLE_WIN和PLE_GAP分别取值2 048和128, 对识别精度和系统开销进行折中。
本文将在公平性、性能、延迟和可扩展性等4个方面来评估Lockvisor。为了更好地分析测试结果还实现了简单让出算法的2种变型: 让出至前端(yielding-to-head, YTH)和让出至尾端 (yielding-to-tail, YTT), 在检测到系统发生锁占用现象时停止运行等待锁任务并分别将其推迟到运行队列头端和尾端。
测试环境配置如下: 双英特尔至强E5606CPU(四核)、 24GB内存和1 Gbps网卡,宿主机运行Linux 2.6.38内核,客户机的操作系统是未经修改的Linux内核2.6.38。每个虚拟机均配置8个虚拟CPU, 与物理CPU的核数相等。测试使用的测试集包括Pi、 HackBench[15]、 SysBench[16]。因为在实验中需要同时运行多个虚拟机,因此用原生内核宿主机上单个虚拟机的性能作为归一化性能基准,并且用所有虚拟机性能的几何平均值来表示系统的整体性能。
本章节通过每个虚拟机的CPU利用率的方差来衡量Lockvisor对调度公平性的影响。CPU利用率的方差越小,就意味着算法对调度公平性的影响越小。虚拟机分为2组,一组运行1个虚拟机,运行HackBench; 另一组则运行4个虚拟机,运行程序Pi, 用来模拟系统中同时运行的其他程序。运行Pi的虚拟机不产生任何锁竞争,因此该组虚拟机的CPU利用率可以衡量Lockvisor对系统调度公平性的影响。HackBench运行了150个对话(6 000个任务), 使用完成时间作为性能指标。
实验结果显示Linux原生内核性能十分低下。就HackBench来说, ITCS性能约为Linux原生内核性能的130倍, SITCS取得了近似的性能提升,其性能约为原生内核100倍; 相比之下, DTCS性能提升要少得多,其性能约为原生内核15.31倍。就系统整体性能来说, ITCS, SITCS和DTCS的系统性能分别是Linux原生内核的2.64、 2.60和1.71倍。与Lockvisor相比, YTH对HackBench的性能提升没有那么显著,但仍然优于Linux原生内核,约为 10.69 倍。YTT比YTH要小一些,约为2.7倍,但Pi测试程序取得了最好的性能,因为它延迟策略使得运行Pi的虚拟CPU获得更多的执行机会。YTH和YTT对应的系统性能分别是Linux原生内核的1.59和1.51倍。ITCS和SITCS对系统整体性能提升最大,而YTT提升的幅度最小。
从调度公平性来看, SITCS和DTCS对于系统调度公平性的影响最少,相对来说ITCS影响稍大一些。但因为采用瞬态系统调度的策略, Lockvisor能够将对调度公平性的影响减到最小; 而且Linux的CFS调度算法会部分抵消瞬态协同调度所引入的调度不公平性。从实际测试的结果来看, Lockvisor对于调度公平性的影响几乎额可以忽略不计。
在性能测试环节中,通过运行4台相同虚拟机(每台虚拟机都运行SysBench.OLTP测试程序)来评估Lockvisor对于数据库类应用程序的性能提升。数据库是云计算环境中最流行的应用之一。本文选择每秒完成事务的数量作为评价系统性能的标准。
测试结果表明, Linux原生内核性能最差。ITCS有最佳的系统性能, SITCS和DTCS提升的幅度要稍小一些,对应系统性能分别是Linux原生内核的3.41、 2.78和2.69倍。相比Lockvisor, YTH和YTT对系统性能提升的幅度差不多,分别是原生内核的2.56和3.30倍。这是因为发生锁占用时,每一个虚拟机都试图获得CPU执行机会来消除锁占用现象,频繁的上下文切换反而会抵消协同调度带来的性能提升。因为同样的原因,延迟调度策略反而可以获得较好的性能。图6中可以看到,虽然YTT对系统整体性能改善仅次于ITCS, 但对调度公平性的影响也最大,具体表现为虚拟机的性能方差最大。
SysBench可以精准地统计每一个请求得到响应的时间,因此本节通过SysBench来评估Lockvisor对于系统延迟的影响状况。测试中一共运行了8个虚拟机,其中7个虚拟机上运行的SysBench同时启动8个线程来模拟系统中的实际应用负载,并使用单位时间执行的事务数量作为系统性能指标。另外1个虚拟机运行的SysBench启动1个线程,这样可以避免锁占用现象的发生,从而使该SysBench的请求执行时间能反映出系统对于外部操作的响应速度。图7中,相比Linux 2.6.38内核, ITCS改善系统整体性能最多,提高了75.55%,但系统的响应时间增加了14.47%。SITCS使系统整体性能只提高了约41.59%,但是具备更快的系统响应,约提高了5.37%。正如预期的那样, DTCS表现最好,系统响应时间减少了约17%。
为了测试Lockvisor的可扩展性,测试中逐渐增加同时运行的虚拟机的数量并用虚拟机的算术平均性能来评估Lockvisor的可扩展性,其中每个虚拟机都运行SysBench.OLTP测试程序,虚拟机的
配置保持不变(虚拟CPU数量为8)。测试最初只运行1台虚拟机,所有策略的性能基本一样。为了更好的量化可扩展性,将系统只运行1台虚拟机时的性能均一化为1。图8中,随着虚拟机数量的增加, Linux 2.6.38内核性能下降最多。而ITCS有着最好的可扩展性,表现为系统性能最好。相比之下, SITCS的可扩展性要稍差一些,这与SysBench.OLTP采用了大量的用户态的自旋锁有一定关系,导致了SITCS对持有锁任务的识别不够精准。DTCS有一个相对平缓的性能曲线, YTH和YTT算法也取得了比较接近的性能。因为随着虚拟机数量的增加,虚拟CPU的数量成比例增加,发生锁占用的几率越来越高,调度器会反复激活瞬态协同调度来消除锁占用。但频繁的上下文切换抵消了协同调度带来的收益,表现为各种策略的性能差距在逐渐缩小。
本文基于协同调度算法提出了一种高效的瞬态协同调度算法Lockvisor, 通过硬件来识别等待锁任务,并在软件层面来识别持有锁任务,实现了更加精准的调度,能有效地消除锁占用。Lockvisor设计了不同的调度策略来满足各种应用场景的需求。通过一系列实验测试表明: 相比Linux内核的CFS,尤其是对于锁密集型的应用, Lockvisor能够取得显著的性能提升。
实验中硬件检测锁占用现象是通过预设参数来具体实现的,而PLE_WIN的取值和具体的应用程序的执行是密切相关的,当前静态设定的方法无法反应不同程序执行状态的差异,不够灵活。下一步将根据目前锁占用发生的频率来动态修改PLE_GAP与PLE_WIN来实现更准确的锁占用检测识别。
| [1] |
|
| [2] |
|
| [3] |
|
| [4] |
|
| [5] |
|
| [6] |
|
| [7] |
|
| [8] |
|
| [9] |
|
| [10] |
|
| [11] |
|
| [12] |
|
| [13] |
|
| [14] |
|
| [15] |
|
| [16] |
|