虛擬環(huán)境下硬件事務(wù)內(nèi)存輔助的同步機(jī)制*

余倩倩，董明凱，陳海波

上海交通大學(xué) 并行與分布式系統(tǒng)研究所，上海 200240

虛擬環(huán)境下硬件事務(wù)內(nèi)存輔助的同步機(jī)制*

余倩倩+，董明凱，陳海波

上海交通大學(xué) 并行與分布式系統(tǒng)研究所，上海 200240

虛擬化；硬件事務(wù)內(nèi)存；同步機(jī)制

1 引言

隨著虛擬化潮流的興起，多臺獨立的虛擬機(jī)被整合在一臺物理機(jī)中，從而充分利用硬件的處理性能。流行的系統(tǒng)虛擬化工具有VMware[1]、Xen[2]、KVM（kernel-based virtual machine）[3]等。在現(xiàn)有的虛擬化架構(gòu)中，虛擬機(jī)監(jiān)視器（virtual machine manager，VMM）負(fù)責(zé)模擬和調(diào)度物理硬件資源，為虛擬機(jī)提供虛擬化資源。理想狀態(tài)下，虛擬化環(huán)境能夠提供近似于物理機(jī)器的性能，這需要虛擬機(jī)監(jiān)視器提供有效的資源模擬和調(diào)度，以此來滿足虛擬機(jī)對物理資源的需求。

對于處理器資源的模擬與調(diào)度，虛擬機(jī)監(jiān)視器將每一個虛擬處理器（virtual CPU，vCPU）視為一個進(jìn)程，并通過向虛擬處理器提供物理處理器的時間片的方式來實現(xiàn)對虛擬處理器的調(diào)度。一個虛擬處理器的調(diào)度過程為：虛擬機(jī)監(jiān)視器將該虛擬處理器進(jìn)程分配到某一物理處理器上，從而為虛擬機(jī)提供處理器資源。虛擬機(jī)監(jiān)視器負(fù)責(zé)初始化以及保存和恢復(fù)虛擬處理器的狀態(tài)，從而使得虛擬機(jī)能夠有效工作。一個虛擬處理器的搶占過程通常在硬件輔助下實現(xiàn)，方法為：中斷發(fā)生后，虛擬機(jī)退出并將控制權(quán)傳給虛擬機(jī)監(jiān)視器，后者在中斷處理函數(shù)中，負(fù)責(zé)保存虛擬處理器的狀態(tài)信息，包括寄存器信息、虛擬機(jī)退出原因等，然后切換運行其他的進(jìn)程。該方法能夠簡單地實現(xiàn)虛擬機(jī)監(jiān)視器對虛擬處理器的調(diào)度機(jī)制，同時提供較優(yōu)的性能，因此被廣泛應(yīng)用于各系統(tǒng)虛擬化工具中。

然而，上述方法也容易因為雙重調(diào)度問題而引發(fā)效率問題。雙重調(diào)度[4-5]指，在虛擬機(jī)監(jiān)視器調(diào)度虛擬處理器的同時，虛擬機(jī)內(nèi)部的內(nèi)核調(diào)度器也在調(diào)度虛擬機(jī)內(nèi)部的進(jìn)程。在雙重調(diào)度的情況下，一方面，虛擬機(jī)監(jiān)視器調(diào)度虛擬處理器，使后者運行于分散的時間片上，不能保證其連續(xù)運行[6]，與物理處理器產(chǎn)生了語義縫隙[4]；另一方面，虛擬機(jī)內(nèi)部的內(nèi)核調(diào)度器認(rèn)為虛擬處理器的運行是連續(xù)的，可能要求不同的虛擬處理器相互協(xié)作來完成同步機(jī)制。然而，當(dāng)一個虛擬處理器被搶占時，其將處于無法響應(yīng)狀態(tài)，也就無法完成同步機(jī)制的協(xié)作任務(wù)，導(dǎo)致其他虛擬處理器的運行被阻塞，產(chǎn)生較大的性能影響。

在Linux操作系統(tǒng)中，排隊自旋鎖（ticket spinlock）是同步機(jī)制的基礎(chǔ)構(gòu)成。操作系統(tǒng)一般通過排隊自旋鎖來實現(xiàn)互斥性，同時保證系統(tǒng)的公平性和可伸縮性。排隊自旋鎖多用于處理短暫的、不可搶占的任務(wù)。在虛擬化環(huán)境中，虛擬處理器的引入使得排隊自旋鎖的公平性和可伸縮性變得不確定，產(chǎn)生了自旋鎖持鎖者被搶占問題[7]和自旋鎖等候者被搶占問題[8]，即當(dāng)一個持有或等待排隊自旋鎖的虛擬處理器被搶占后，可能引起其他處理器的等待，阻塞整個系統(tǒng)，從而浪費了處理器資源。因此，優(yōu)化虛擬化環(huán)境下同步機(jī)制的性能對系統(tǒng)整體性能是至關(guān)重要的。

硬件事務(wù)內(nèi)存（hardware transactional memory）[9-10]的出現(xiàn)，允許一組指令原子性地執(zhí)行，且不需要多處理器之間的相互協(xié)作，擁有低開銷和易使用的優(yōu)點。更重要的是，事務(wù)區(qū)間內(nèi)的整體代碼段只可能原子性地提交或者整個被中斷及回退，使得硬件事務(wù)內(nèi)存擁有不被打斷的特性。即使在虛擬化環(huán)境下，若虛擬處理器被搶占，那么該處理器上的硬件事務(wù)內(nèi)存將會發(fā)生中斷，也同樣能夠保證硬件事務(wù)內(nèi)存擁有不被打斷的特性。近年來，硬件事務(wù)內(nèi)存在英特爾處理器中被廣泛使用，為優(yōu)化同步機(jī)制提供了新的方向。如何更好地利用硬件事務(wù)內(nèi)存緩解雙重調(diào)度問題，來提高虛擬化環(huán)境下同步機(jī)制的效率，同時最大程度地維護(hù)同步機(jī)制的公平性和可伸縮性，是一個非常重要的研究課題。

本文硬件事務(wù)內(nèi)存的輔助下，提出了一種優(yōu)化虛擬化環(huán)境下同步機(jī)制的方法，設(shè)計了一種新的同步機(jī)制，實現(xiàn)了對系統(tǒng)性能和公平性的提升。

本文組織結(jié)構(gòu)如下：第2章介紹了虛擬化環(huán)境下同步機(jī)制相關(guān)的背景和工作，包括排隊自旋鎖的工作原理和虛擬機(jī)監(jiān)視器的基本調(diào)度機(jī)制；第3、第4章介紹了SPINRTM的設(shè)計與實現(xiàn)，包括所涉及的硬件事務(wù)內(nèi)存的應(yīng)用，以及對虛擬機(jī)操作系統(tǒng)與虛擬機(jī)監(jiān)視器中各組件的修改；第5章是針對SPINRTM的測試結(jié)果，并且和未加修改的排隊自旋鎖進(jìn)行了對比和分析；第6章是本文工作的總結(jié)和展望。

2 背景

2.1 硬件事務(wù)內(nèi)存

事務(wù)內(nèi)存[11]允許一組指令原子性地執(zhí)行，并且完全與多處理器架構(gòu)中的其他處理器隔離開來，不需要多處理器的相互協(xié)作。它是一種并行控制機(jī)制，類似于數(shù)據(jù)庫中用來并行訪問共享數(shù)據(jù)的數(shù)據(jù)庫事務(wù)。與其他同步機(jī)制（比如自旋鎖）相比，事務(wù)內(nèi)存具有語義清晰和易于編程的特點。由于軟件事務(wù)內(nèi)存普遍開銷巨大，而硬件事務(wù)內(nèi)存不僅開銷小，而且在近年來廣泛內(nèi)置于處理器之中，故本文僅討論硬件事務(wù)內(nèi)存。本文以英特爾公司的硬件事務(wù)內(nèi)存——限制性事務(wù)內(nèi)存為例，進(jìn)行研究與設(shè)計。

英特爾事務(wù)同步擴(kuò)展[12]（Intel transactional synchronization extension）是英特爾公司針對限制性內(nèi)存的擴(kuò)展指令集。這一擴(kuò)展允許處理器使用硬件事務(wù)內(nèi)存，以一種樂觀的方式來實現(xiàn)同步機(jī)制。在事務(wù)區(qū)間內(nèi)的代碼運行時，由硬件負(fù)責(zé)監(jiān)控多個線程之間是否發(fā)生沖突，并在事務(wù)無法成功提交時，中斷和回滾事務(wù)，再交由軟件來處理失敗的事務(wù)。該技術(shù)通過硬件實現(xiàn)了同步機(jī)制，又隱藏了其實現(xiàn)細(xì)節(jié)，僅僅向軟件提供了同步機(jī)制的接口，簡化了編程的難度。不僅如此，該技術(shù)允許程序員將限制性事務(wù)內(nèi)存作為同步機(jī)制的一條快速路徑，將普通軟件鎖作為一條慢速路徑（回退機(jī)制），是軟件鎖的一種有效替代方式。

如果一個事務(wù)的執(zhí)行成功提交了，那么硬件將保證事務(wù)區(qū)間里的所有內(nèi)存修改都會同時生效。對于其他邏輯處理器而言，這些內(nèi)存修改會原子性地出現(xiàn)。上述事件被稱為原子性提交。任何事務(wù)區(qū)間內(nèi)的內(nèi)存修改都只有在原子性提交之后，才能對其他處理器可見。由于一個事務(wù)內(nèi)存的成功提交保證了事務(wù)區(qū)間內(nèi)代碼段的原子性，程序員可以將事務(wù)區(qū)間內(nèi)的代碼段指定為臨界區(qū)間代碼，從而使用事務(wù)內(nèi)存這種樂觀的同步機(jī)制實現(xiàn)方式來代替鎖這種悲觀的實現(xiàn)方式。即使當(dāng)同步機(jī)制對于該事務(wù)區(qū)間代碼段的執(zhí)行實際是多余的時，該事務(wù)內(nèi)存也能夠在不需要線程間進(jìn)行同步的情況下原子性提交，使得該代碼段生效。

如果一個事務(wù)的執(zhí)行中斷了，那么處理器就不能原子性地提交該事務(wù)。在這種情況下，處理器會回滾該事務(wù)。上述事件被稱為事務(wù)中斷。在一個事務(wù)中斷發(fā)生時，處理器會丟棄在事務(wù)區(qū)間內(nèi)做出的所有修改，恢復(fù)處理器架構(gòu)的狀態(tài)至事務(wù)開始之前，形成該事務(wù)從未發(fā)生的假象，并且非事務(wù)性地恢復(fù)執(zhí)行流。基于硬件事務(wù)內(nèi)存的設(shè)計特點，一個失敗的事務(wù)可能被重試多次，并且在多次失敗后顯式地獲取一把鎖，來保證執(zhí)行流向前發(fā)展。

2.2 內(nèi)核排隊自旋鎖

內(nèi)核排隊自旋鎖的設(shè)計通過模擬一條先進(jìn)先出的隊列來實現(xiàn)有序的同步機(jī)制。在具體實現(xiàn)中，每個自旋鎖維護(hù)一個2 Byte的整形變量，并將其劃分為兩個1 Byte的整形變量：Next和Owner。這兩個變量表示隊列中的兩個票號，分別對應(yīng)于入隊的票號和出隊的票號。Next表示這個隊列中管理者要分發(fā)的下一個票號；Owner表示這個隊列中當(dāng)前正在接受服務(wù)的票號。

在初始化時，自旋鎖維護(hù)的兩個整形變量被賦值為0。獲取鎖時，spin_lock函數(shù)體會原子性地獲取鎖變量的值，同時將next變量的值加1。next變量增加之前的值也就是該線程獲取的票號，會作為其取鎖順序的依據(jù)。當(dāng)這個票號與自旋鎖owner變量的值相等時，系統(tǒng)則判斷該線程成功獲取了該排隊自旋鎖；當(dāng)這個票號與owner變量的值不等時，系統(tǒng)則判斷該線程未能成功獲取鎖，此時該線程將會阻塞在這個變量上，直到自旋鎖owner變量增長到與該線程票號相等的數(shù)值。值得注意的是，在內(nèi)核排隊自旋鎖中，處理器在獲取鎖之前會關(guān)閉中斷，即不會發(fā)生進(jìn)程調(diào)度。因此，在等待鎖獲取成功的時間段中，該處理器會處于忙等狀態(tài)，而無法處理其他任務(wù)。

在非排隊自旋鎖（即普通自旋鎖）的實現(xiàn)中，所有處理器可能會同時競爭同一把鎖，“爭搶”誰能夠第一個獲取鎖。該機(jī)制既沒有一個明確的鎖獲取順序，也不能保證獲取鎖的最長等待時間。而在排隊自旋鎖的實現(xiàn)中，各線程能夠依據(jù)其最初的到達(dá)時間來有序地獲取鎖；多線程的運行時間能夠得到均衡；最長等待時間也會有所下降（更重要的是，這成為了確定性事件，有一個確定的順序）。雖然排隊自旋鎖的實現(xiàn)引入了額外的處理器開銷，但是相對于普通自旋鎖中頻繁引發(fā)的高速緩存未命中的開銷，尤其對于時下流行的多處理器架構(gòu)而言，這樣的額外開銷是十分小的，幾乎可以忽略。從系統(tǒng)內(nèi)核的角度考慮，維護(hù)各處理器之間的公平性比節(jié)省這樣的開銷要重要得多。

2.3 鎖持有者搶占和鎖等待者問題

在虛擬機(jī)監(jiān)視器和虛擬機(jī)內(nèi)核調(diào)度器的雙重調(diào)度下，虛擬機(jī)內(nèi)核中的同步機(jī)制可能會引發(fā)嚴(yán)重的性能問題。相關(guān)的常見場景有鎖持有者被搶占問題和鎖等待者被搶占問題。

鎖持有者被搶占問題指，一個虛擬處理器在成功獲取排隊自旋鎖之后，釋放該鎖之前，被搶占。該問題將導(dǎo)致其他虛擬處理器在獲取鎖時，只能忙等，無法進(jìn)展，余下的時間片就會被浪費。如圖1，vCPU0和vCPU1先后獲取了排隊自旋鎖，vCPU0在臨界區(qū)間中被搶占，導(dǎo)致vCPU1只能忙等，后續(xù)時間片整個被浪費。由于虛擬處理器的時間片調(diào)度粒度一般為毫秒級別，而排隊自旋鎖的等待粒度一般為微秒級別，當(dāng)上述問題發(fā)生時，該鎖的獲取時間將被延長千倍級別，這一影響就變得不可忽視。

Fig.1 Lock holder example圖1 鎖持有者問題例圖

鎖等待者被搶占問題指，一個虛擬處理器在獲取排隊自旋鎖票號，進(jìn)入等待后，被搶占。該問題將導(dǎo)致票號在此虛擬處理器之后的線程只能忙等，無法進(jìn)展。如圖2，vCPU0、vCPU1、vCPU2先后獲取了排隊自旋鎖，vCPU0釋放排隊自旋鎖后，由于vCPU1被搶占，使得vCPU2只能忙等，剩余時間片被浪費。與鎖搶占者問題一樣，上述問題也會帶來不可忽視的負(fù)面影響。

Fig.2 Lock waiter example圖2 鎖等待者問題例圖

3 設(shè)計與實現(xiàn)

3.1 限制性事務(wù)內(nèi)存的特性利用

鎖持有者搶占問題和鎖等待者搶占問題有一個共性：在問題發(fā)生時，持有鎖或者等待鎖的虛擬處理器被虛擬機(jī)監(jiān)視器所搶占。由于在搶占機(jī)制實現(xiàn)中，虛擬處理器會首先收到一個來自物理處理器的中斷，若這個虛擬處理器此時已經(jīng)開啟了硬件事務(wù)內(nèi)存，則硬件事務(wù)內(nèi)存能夠通過物理處理器引發(fā)的事務(wù)中斷來感知搶占事件，從而做出回退措施，并對鎖持有者搶占問題和鎖等待者搶占問題做出相應(yīng)的處理。

詳細(xì)地來說，在一個虛擬機(jī)運行時，一個虛擬處理器占用物理處理器的一個時間片。當(dāng)一個虛擬處理器被搶占時，這個虛擬處理器會接收到來自物理處理器的一個中斷，如果該虛擬處理器的限制性事務(wù)內(nèi)存已經(jīng)開啟，那么此時硬件事務(wù)內(nèi)存就會被中斷。作為結(jié)果，這個虛擬處理器的執(zhí)行流就會跳轉(zhuǎn)到限制性事務(wù)內(nèi)存的回退路徑上，同時虛擬機(jī)監(jiān)視器的執(zhí)行流也會跳轉(zhuǎn)到搶占處理函數(shù)上，并且限制性事務(wù)內(nèi)存中所做的所有內(nèi)存修改都會被回退，恢復(fù)到限制性事務(wù)內(nèi)存開啟前的狀態(tài)。這一硬件特性是本文設(shè)計中利用的最核心的特性。通過限制性事務(wù)內(nèi)存的這一特性，來對虛擬處理器的搶占做出額外的判斷與操作，從而提高同步機(jī)制在虛擬環(huán)境下的效率。

在實際測試中發(fā)現(xiàn)，虛擬機(jī)監(jiān)視器的控制流優(yōu)先級高于限制性事務(wù)內(nèi)存回退路徑的控制流。因此，在搶占中斷發(fā)生時，物理處理器的控制流會跳轉(zhuǎn)至虛擬機(jī)監(jiān)視器的搶占回調(diào)函數(shù)中。

3.2 硬件事務(wù)內(nèi)存輔助排隊自旋鎖的設(shè)計

3.2.1SPINRTM的設(shè)計

多核處理器程序通常需要使用同步機(jī)制保護(hù)共享數(shù)據(jù)的訪問。其中，鎖是一種悲觀的同步機(jī)制實現(xiàn)方式，通常適用于競爭較高的場景；事務(wù)內(nèi)存是一種樂觀的實現(xiàn)方式，通常適用于競爭較低的場景。在樸素的設(shè)計方式中，使用硬件事務(wù)內(nèi)存直接代替排隊自旋鎖會產(chǎn)生大量的事務(wù)中斷。這是由于在競爭較高的情況下，共享數(shù)據(jù)的訪問在事務(wù)區(qū)間中產(chǎn)生大量的數(shù)據(jù)沖突，這些沖突導(dǎo)致了限制性事務(wù)內(nèi)存的頻繁中斷，進(jìn)而產(chǎn)生巨大的開銷。頻繁的事務(wù)中斷不僅會回滾事務(wù)開啟后提交前在臨界區(qū)間的所有修改，浪費處理器資源，而且會引發(fā)大量的事務(wù)重試，重復(fù)事務(wù)內(nèi)存的開啟與臨界區(qū)間內(nèi)的指令，極大地加劇了硬件事務(wù)內(nèi)存的同步開銷。為了避免這種情況對系統(tǒng)整體性能的影響，本文提出了一種新的設(shè)計方式：使用限制性事務(wù)內(nèi)存來輔助內(nèi)核排隊自旋鎖的同步機(jī)制。這一設(shè)計利用排隊自旋鎖來避免大量的數(shù)據(jù)沖突，同時利用限制性事務(wù)內(nèi)存來避免雙重調(diào)度產(chǎn)生的效率問題。偽代碼見圖3。

Fig.3 Pseudo code圖3 偽代碼

3.2.2 鎖持有者問題的解決

為了解決鎖持有者問題，必須保證臨界區(qū)間代碼段的不被打斷性，即一個虛擬處理器不能在持有鎖的時候被搶占。

在實現(xiàn)中，有兩種方式：一是延長鎖持有者的時間片長度，使該虛擬處理器能夠在被搶占前完成臨界區(qū)間的代碼段，并釋放該鎖；二是延遲臨界區(qū)間的執(zhí)行時間，使它完全在下一個時間片中被執(zhí)行。由于延長虛擬處理器時間片的方法會進(jìn)一步影響虛擬機(jī)監(jiān)視器中調(diào)度機(jī)制的公平性，本文采用了后一種方式，即延遲臨界區(qū)間的執(zhí)行時間。在傳統(tǒng)的排隊自旋鎖中，這種方式是難以實現(xiàn)的，因為在虛擬處理器獲取鎖時，處理器無法預(yù)知其是否會在臨界區(qū)間內(nèi)被打斷，所以也無法決定這個獲取鎖的操作是否需要被延遲。而在硬件事務(wù)內(nèi)存的輔助下，可以使用事務(wù)內(nèi)存的中斷和回滾功能，來模擬達(dá)到延遲的效果。在事務(wù)內(nèi)存發(fā)生中斷時，這個事務(wù)中做的所有內(nèi)存修改都將被回滾，恢復(fù)到事務(wù)發(fā)生之前的狀態(tài)。事務(wù)中斷后的狀態(tài)與事務(wù)未開始時的狀態(tài)是一致的，因此這個效果就可以等效為事務(wù)被延遲執(zhí)行。

通過延遲整個臨界區(qū)間的執(zhí)行，當(dāng)一個虛擬處理器被搶占時，其他虛擬處理器依然能夠進(jìn)入臨界區(qū)間而不被其阻塞，這一方法能夠有效地緩解鎖持有者問題帶來的性能影響。

3.2.3 鎖等待者問題的解決

首先，SPINRTM能夠有效緩解鎖持有者問題。SPINRTM減短了虛擬處理器獲取一個鎖時的等待時間，因而降低了鎖等待者搶占問題的發(fā)生概率。而通過降低發(fā)生的概率，SPINRTM能夠緩解鎖等待者問題帶來的性能影響。

此外，文獻(xiàn)[13]通過半虛擬化技術(shù)主動喚醒被搶占的虛擬處理器（鎖等待者）；文獻(xiàn)[8]通過放寬鎖獲取的順序，來允許其他虛擬處理器率先獲取鎖。這兩種方法都能夠有效緩解鎖等待者問題。SPINRTM與以上兩種方法是完全兼容的。

3.3 虛擬機(jī)監(jiān)視器與虛擬機(jī)內(nèi)核的協(xié)同實現(xiàn)

3.3.1 虛擬機(jī)內(nèi)核的預(yù)先處理

每個虛擬機(jī)內(nèi)核會在啟動時，向虛擬機(jī)監(jiān)視器申請注冊一塊共享內(nèi)存。在這塊共享內(nèi)存中，會保存虛擬機(jī)監(jiān)視器中被搶占排隊自旋鎖的信息，用以幫助虛擬機(jī)監(jiān)視器來協(xié)助虛擬處理器釋放鎖。這些信息包括排隊自旋鎖的地址和票號。

3.3.2 虛擬機(jī)監(jiān)視器解鎖

在虛擬處理器被搶占后，控制流會進(jìn)入虛擬機(jī)監(jiān)視器的搶占回調(diào)函數(shù)中。在這個回調(diào)函數(shù)中，虛擬機(jī)監(jiān)視器會檢查該虛擬處理器是否是一個鎖持有者，并且在檢測出是鎖持有者時，協(xié)助該虛擬處理器釋放鎖。此時，雖然該虛擬處理器仍然持有鎖，但是它在持鎖后做的所有內(nèi)存修改都已經(jīng)被硬件事務(wù)內(nèi)存恢復(fù)，因此可以釋放鎖而不引起正確性問題。

虛擬機(jī)監(jiān)視器的解鎖分為兩個步驟：一是判斷虛擬處理器是否為一個鎖搶占者；二是釋放該鎖。

在本文的實現(xiàn)中，對鎖搶占者的判斷基于PC寄存器（program counter）的地址。一個鎖持有者在被搶占時，它開啟的限制性事務(wù)內(nèi)存就會被中斷，使得控制流（即PC）指向限制性事務(wù)內(nèi)存的回退路徑地址上。在限制性事務(wù)內(nèi)存沒有中斷時，PC是不會指向此地址的。因此，通過PC地址的判斷，能夠分辨出一個虛擬處理器是否為一個鎖持有者。在Linux內(nèi)核3.18.24的具體實現(xiàn)中，由于內(nèi)聯(lián)函數(shù)的原因，這樣的PC地址可能有3個，需要分別進(jìn)行判斷。另外，需要在虛擬機(jī)啟動前，事先獲取這些地址。

釋放鎖的實質(zhì)非常簡單，就是對鎖的票號進(jìn)行原子性增加。此處有一個需要注意的地方就是，鎖的增加量可能為1，也可能為2。在默認(rèn)配置的虛擬機(jī)內(nèi)核中（半虛擬化鎖不開啟），這個增加量為1。而在開啟了半虛擬化鎖的內(nèi)核中，由于半虛擬化鎖的實現(xiàn)需要，票號的最后一個比特被用作額外標(biāo)示，因此鎖的增加量調(diào)整為2。虛擬機(jī)監(jiān)視器也需要對這項配置事先了解，以正確解鎖。本文的實現(xiàn)中，虛擬機(jī)監(jiān)視器在啟動前已獲取具體的增加量。

3.3.3 虛擬機(jī)內(nèi)核的回退路徑

限制性事務(wù)內(nèi)存中斷后，虛擬處理器的控制流會跳轉(zhuǎn)到回退路徑上。此時，中斷處理函數(shù)需要對兩種可能的情況進(jìn)行處理：一是中斷原因來自虛擬機(jī)內(nèi)部；二是中斷原因來自虛擬機(jī)外部，比如搶占和其他中斷。當(dāng)中斷原因來自虛擬機(jī)內(nèi)部時，虛擬機(jī)內(nèi)核可以繼續(xù)重試事務(wù)內(nèi)存，或者放棄事務(wù)內(nèi)存回退至原始的排隊自旋鎖。當(dāng)中斷原因來自虛擬機(jī)外部時，中斷處理函數(shù)需要判斷該虛擬處理器是否被搶占，如果被搶占，是否被協(xié)助釋放了鎖。在鎖沒有被協(xié)助釋放的情況下，中斷函數(shù)的處理機(jī)制與第一種情況類似。而在鎖被協(xié)助釋放的情況下，中斷處理函數(shù)就需要重新獲取鎖，以保證臨界區(qū)間的互斥性。

中斷處理函數(shù)對鎖是否被協(xié)助釋放的判斷方法如下。在限制性事務(wù)內(nèi)存開啟之前保存票號，并在回退路徑上將再次讀取的票號與之比對，若不相等，則鎖已被協(xié)助釋放。原因有兩點：首先，協(xié)助釋放鎖必然導(dǎo)致兩個票號不相等。搶占與協(xié)助釋放鎖必然發(fā)生在限制性事務(wù)內(nèi)存開啟之后，回退路徑開始之前。如果協(xié)助釋放鎖的操作發(fā)生了，那么虛擬處理器記錄下的票號就對應(yīng)釋放鎖之前的票號，再讀的票號就對應(yīng)釋放鎖之后的票號，兩個票號必然是不等的。其次，兩個票號不相等必然是因為虛擬監(jiān)視器協(xié)助釋放了鎖。在事務(wù)開啟之前，該虛擬處理器已經(jīng)獲取了排隊自旋鎖，因此其他虛擬處理器無法進(jìn)行獲取鎖和釋放鎖的操作。此時，僅有該虛擬處理器自身和虛擬機(jī)監(jiān)視器能夠執(zhí)行釋放鎖的操作。因此，這個鎖的釋放只能來自于虛擬機(jī)監(jiān)視器。

4 測試與分析

本文通過測試對SPINRTM的性能和公平性進(jìn)行評估。測試在Intel Xeon?E5-2650 V3@2.3 GHz的處理器上進(jìn)行，共20個CPU并配有128 GB內(nèi)存。為了測試的準(zhǔn)確性，關(guān)閉了超線程支持和Turbo Boost功能。

測試給每臺虛擬機(jī)配置了20個虛擬處理器和8GB內(nèi)存。本地和虛擬機(jī)都搭載了Linux內(nèi)核3.18.24。測試選擇了3個基準(zhǔn)程序來檢測系統(tǒng)性能，Kernbench、Apache[14]和Pbzip2[15]，分別屬于處理器密集型、內(nèi)存密集型和輸入輸出密集型工作。基準(zhǔn)配置（Baseline）采用未修改的虛擬機(jī)內(nèi)核與虛擬機(jī)監(jiān)視器。

4.1 處理器密集型測試

圖4顯示了運行Kernbench基準(zhǔn)程序的性能結(jié)果。本測試中，Kernbench會重復(fù)編譯系統(tǒng)內(nèi)核，取5次運行時間平均值作為結(jié)果。本測試中配置的虛擬機(jī)內(nèi)存為8 GB，大于一個系統(tǒng)內(nèi)核的大小，因此Kernbench主要體現(xiàn)為一個處理器密集型基準(zhǔn)程序。在基準(zhǔn)配置的1臺和4臺虛擬機(jī)的結(jié)果比對中，4臺虛擬機(jī)的運行時間要小于1臺機(jī)器的4倍?？梢园l(fā)現(xiàn)，雖然配備了更多的虛擬機(jī)，使得虛擬資源超載了物理資源，實際上系統(tǒng)的整體效率卻得到了提升。這是因為在Kernbench中，虛擬處理器的資源成為瓶頸，而鎖競爭對整體性能的影響很小。在超載情況加劇時，并不引發(fā)鎖的效率問題，反而能進(jìn)一步提高處理器的利用率。SPINRTM比基準(zhǔn)配置提供了更低的性能，其原因在于限制性事務(wù)內(nèi)存的使用增加了同步機(jī)制的開銷，限制性事務(wù)內(nèi)存的中斷和處理更加劇了這一問題。

Fig.4 Execution time of Kernbench圖4 Kernbench運行時間示意圖

4.2 內(nèi)存密集型測試

圖5顯示了運行Apache的性能結(jié)果。在本測試中，Apache會向本機(jī)發(fā)送10 000個包，取平均吞吐量作為結(jié)果。當(dāng)運行4臺虛擬機(jī)時，取所有虛擬機(jī)的吞吐量之和。頻繁的發(fā)包與收包包含了大量的內(nèi)存操作，因此Apache是一個內(nèi)存密集的基準(zhǔn)測試程序。在測試結(jié)果中可以發(fā)現(xiàn)，當(dāng)運行4臺虛擬機(jī)時，系統(tǒng)的整體總吞吐量小于運行1臺虛擬機(jī)時的整體吞吐量，這是因為受到了雙重調(diào)度的嚴(yán)重影響。相比基準(zhǔn)配置的性能，在運行1臺虛擬機(jī)時，由于限制性事務(wù)內(nèi)存的處理開銷，SPINRTM給系統(tǒng)帶來了額外的開銷。然而，在4臺虛擬機(jī)的運行結(jié)果中，由于Apache程序頻繁的內(nèi)存操作，使得內(nèi)核需要通過排隊自旋鎖來進(jìn)行內(nèi)存管理，在這一過程中，引入了嚴(yán)重的雙重調(diào)度問題。SPINRTM通過對雙重調(diào)度問題的緩解，提升了Apache程序的性能。

Fig.5 Throughput ofApache圖5 Apache吞吐量示意圖

4.3 輸入輸出密集型測試

圖6顯示了運行Pbzip2的性能結(jié)果。在本測試中，Pbzip2會解壓縮一個大小為4 GB的文件，取5次運行時間的平均值作為結(jié)果。由于Pbzip2的解壓過程需要系統(tǒng)頻繁地從磁盤讀出寫入數(shù)據(jù)，使得Pbzip2成為一個輸入輸出密集型基準(zhǔn)程序。與Apache相似，當(dāng)運行4臺虛擬機(jī)時，系統(tǒng)的運行時間大于運行1臺虛擬機(jī)時的4倍，同樣受到了雙重調(diào)度的影響。相比基準(zhǔn)配置的性能，在運行1臺虛擬機(jī)時，SPINRTM就能小幅度地提高系統(tǒng)性能，縮短運行時間；在運行4臺虛擬機(jī)時，SPINRTM的性能提升就變得更加明顯。原因在于，Pbzip2不僅對系統(tǒng)資源的分配效率有很大的要求，涉及大量的排隊自旋鎖操作，而且頻繁、昂貴的磁盤操作增加了雙重調(diào)度問題的發(fā)生頻率，延長了等待時間。因此，SPINRTM有效地緩解了這一問題。

Fig.6 Runtime of Pbzip2圖6 Pbzip2運行時間示意圖

4.4 公平性測試

為了比較各虛擬機(jī)之間的公平性問題，本文計算了各基準(zhǔn)程序在多虛擬機(jī)運行時測試結(jié)果的標(biāo)準(zhǔn)差，將SPINRTM與基準(zhǔn)配置的結(jié)果相比較，結(jié)果如表1所示。

Table 1 Performance standard deviation表1 性能標(biāo)準(zhǔn)差

可以發(fā)現(xiàn)基準(zhǔn)配置本身就有一定偏移量，這是由于虛擬機(jī)監(jiān)視器的調(diào)度本身就不能完全保證虛擬機(jī)之間的公平性，虛擬機(jī)內(nèi)核的一些通信機(jī)制，如鎖，更加劇了這一問題。比對兩種配置的標(biāo)準(zhǔn)差結(jié)果，雖然SPINRTM沒有提升Kernbench的性能，卻降低了它的不公平性。Apache的結(jié)果恰恰相反，SPINRTM提升了性能，卻小幅度加劇了不公平問題，但是影響較小，可以忽略。Pbzip2在性能和公平性上都得到了提升。

總體來看，SPINRTM能夠保護(hù)虛擬機(jī)之間的公平性，并且與其總體性能無關(guān)。

5 相關(guān)工作

最初，虛擬機(jī)監(jiān)視器通過要求每個虛擬機(jī)同時調(diào)度[16]的方式來解決虛擬機(jī)內(nèi)核中同步機(jī)制的問題，即要求同一個虛擬機(jī)的所有虛擬處理器同時被調(diào)度，或者同時被搶占。上述方法被VMware ESX[17]的虛擬機(jī)調(diào)度器采用。然而，該方法對虛擬處理器的最大支持?jǐn)?shù)量以及虛擬機(jī)監(jiān)視器的調(diào)度器算法施加了很多限制。其后，協(xié)同調(diào)度[18]是一種新的解決方法，即由虛擬機(jī)監(jiān)視器動態(tài)地為一個虛擬機(jī)指定其協(xié)同調(diào)度和異步調(diào)度的虛擬處理器。該調(diào)度對虛擬處理器的選擇方法是基于虛擬機(jī)內(nèi)核對于長期阻塞的排隊自旋鎖的檢測。文獻(xiàn)[19]提出了一種自適應(yīng)的虛擬機(jī)放置框架和算法，根據(jù)資源的需求，動態(tài)調(diào)整虛擬機(jī)資源。最后，在虛擬機(jī)動態(tài)自適應(yīng)調(diào)度法[20]中，提出了一種平衡調(diào)度機(jī)制，將一個虛擬機(jī)的單個虛擬處理器與物理處理器聯(lián)系起來，而不要求這些虛擬處理器被協(xié)同調(diào)度。這一方法同樣增加了主機(jī)端（host）的負(fù)擔(dān)。

半虛擬化自旋鎖是一種通過半虛擬化技術(shù)來優(yōu)化排隊自旋鎖效率的機(jī)制。它首次在文獻(xiàn)[7]中被提出，采用了一種避免搶占的策略，通過虛擬機(jī)內(nèi)核向虛擬機(jī)監(jiān)視器發(fā)送提示，來防止排隊自旋鎖持有者被搶占。這一提示向虛擬機(jī)監(jiān)視器表明，當(dāng)前虛擬處理器是一個排隊自旋鎖的持有者，正進(jìn)入一個不可被搶占的臨界區(qū)間。半虛擬化技術(shù)在半虛擬化排隊自旋鎖[13]中又一次被采用，并被整合入虛擬機(jī)監(jiān)視器Xen和內(nèi)核虛擬機(jī)KVM的代碼中。該文用一個計數(shù)器來檢測一個虛擬處理器等待排隊自旋鎖的時間。當(dāng)?shù)却龝r間異乎尋常得長，也就是當(dāng)虛擬處理器用在等待上的自旋次數(shù)超過一定閾值時，該虛擬處理器就會向當(dāng)前虛擬機(jī)監(jiān)視器發(fā)送一個超調(diào)用（hypercall），表示當(dāng)前虛擬處理器被一個其他虛擬處理器持有的排隊自旋鎖阻塞了。隨之，虛擬機(jī)監(jiān)視器就會停止調(diào)度（搶占）當(dāng)前被阻塞的虛擬處理器，直到該排隊自旋鎖被釋放。這兩種方法都能夠提供較好的性能。然而，半虛擬化技術(shù)要求對虛擬機(jī)內(nèi)核進(jìn)行修改，從而會產(chǎn)生兼容問題和標(biāo)準(zhǔn)化問題。并且，這些方法只能解決排隊自旋鎖持有者被搶占的問題，而忽略了排隊自旋鎖等待者被搶占的問題。

硬件輔助的方式也能夠被用來緩解虛擬環(huán)境下同步機(jī)制的效率問題。例如，處理器的暫停-循環(huán)-退出機(jī)制，現(xiàn)在的處理器一般均支持這一機(jī)制。首先，虛擬機(jī)內(nèi)核中的自旋鎖在每一次自旋時，都會執(zhí)行一句暫停語句。然后，當(dāng)一個物理處理器檢測到過多的暫停時，即在一個短時間內(nèi)暫停指令的執(zhí)行次數(shù)超過一個預(yù)先設(shè)定的閾值時，虛擬機(jī)監(jiān)視器就會產(chǎn)生一個虛擬機(jī)退出指令。此時，虛擬機(jī)監(jiān)視器將會搶占當(dāng)前虛擬處理器，同時尋找并調(diào)度另一個等待被執(zhí)行的虛擬處理器。這樣做的目的在于，期望新的虛擬處理器能夠執(zhí)行有用的指令，而不是忙等，從而將更多的處理器時間用在處理有效的指令上。這種方式也有缺點：雖然提高了物理處理器的有效利用率，卻也影響了虛擬處理器之間的公平性。

6 結(jié)束語

雙重調(diào)度是虛擬環(huán)境下不容忽視的問題。本文研究了內(nèi)核的同步機(jī)制和虛擬機(jī)監(jiān)視器的調(diào)度機(jī)制，結(jié)合硬件事務(wù)內(nèi)存的特點，提出了一種虛擬環(huán)境下由硬件事務(wù)內(nèi)存輔助的同步機(jī)制SPINRTM。SPINRTM在內(nèi)核排隊自旋鎖的基礎(chǔ)上，由硬件事務(wù)內(nèi)存輔助，使虛擬機(jī)監(jiān)視器與虛擬處理器相互協(xié)助，有效地幫助系統(tǒng)緩解了虛擬環(huán)境下雙重調(diào)度產(chǎn)生的問題，提升性能，保護(hù)公平性。未來的工作中，還將考慮該設(shè)計在其他平臺上的進(jìn)一步優(yōu)化。

[1]Rosenblum M.Virtual platformTM—a virtual machine monitor for a commodity PC[C]//Proceedings of the Symposium of High-Performance Chips,Stanford,Aug 15-17,1999.

[2]Barham P,Dragovic B,Fraser K,et al.Xen and the art of virtualization[J].ACM SIGOPS Operating Systems Review,2003,37(5):164-177.

[3]Kivity A,Kamay Y,Laor D,et al.KVM:the Linux virtual machine monitor[J].Proceedings of the Linux Symposium,2007,1:225-230.

[4]Jin Hai,Zhong Alin,Wu Song,et al.Virtual machine VCPU scheduling in the multi-core environment:issues and challenges[J].Journal of Computer Research and Development,2011,48(7):1216-1224.

[5]Song Xiang,Shi Jicheng,Chen Haibo,et al.Schedule processes,not VCPUs[C]//Proceedings of the 4th Asia-Pacific Workshop on Systems,Singapore,Jul 29-30,2013.New York:ACM,2013:1.

[6]Ahn J,Chang H P,Huh J.Micro-sliced virtual processors to hide the effect of discontinuous CPU availability for consolidated systems[C]//Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture,Cambridge,UK,Dec 13-17,2014.Washington:IEEE Computer Society,2014:394-405.

[7]Uhlig V,LeVasseur J,Skoglund E,et al.Towards scalable multiprocessor virtual machines[C]//Proceedings of the 3rd Virtual Machine Research and Technology Symposium,San Jose,USA,May 6-7,2004.Berkeley,USA:USENIX Association,2004:43-56.

[8]Ouyang Jiannan,Lange J R.Preemptable ticket spinlocks:improving consolidated performance in the cloud[C]//Proceedings of the 9th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments,Houston,USA,Mar 16-17,2013.New York:ACM,2013:191-200.

[9]Dice D,Lev Y,Moir M,et al.Early experience with a commercial hardware transactional memory implementation[J].ACM SIGPLAN Notices,2009,44(3):157-168.

[10]Hammarlund P,Kumar R,Osborne R B,et al.Haswell:the fourth-generation Intel core processor[J].IEEE Micro,2014,34(2):6-20.

[11]Herlihy M,Eliot J,Moss B.Transactional memory:architectural support for lock-free data structures[J].ACM SIGARCH ComputerArchitecture News,1993,21(2):289-300.

[12]Rajwar R,Dixon M.Intel transactional synchronization extensions[R].Intel Developer Forum,San Francisco,2012.

[13]Raghavendra K T,Vaddagiri S,Dadhania N,et al.Paravirtualization for scalable kernel-based virtual machine(KVM)[C]//Proceedings of the 2012 International Conference on Cloud Computing in Emerging Markets,Bangalore,India,Oct 11-12,2012.Piscataway,USA:IEEE,2012:1-5.

[14]Knaus W A,Draper E A,Wagner D P,et al.APACHE II:a severity of disease classification system[J].Critical Care Medicine,1985,13(10):818-829.

[15]Gilchrist J.Parallel data compression with Bzip2[C]//Pro-ceedings of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems,2004,16:559-564.

[16]Feitelson D G,Rudolph L.Gang scheduling performance benefits for fine-grain synchronization[J].Journal of Parallel and Distributed Computing,1992,16(4):306-318.

[17]Oglesby R,Herold S.VMware ESX server:advanced technical design guide(advanced technical design guide series)[M].[S.l.]:The Brian Madden Company,2005.

[18]Ousterhout J K.Scheduling techniques for concurrent systems[C]//Proceedings of the 3rd IEEE International Conference on Distributed Computing Systems,Miami,USA,1982:22-30.

[19]Shi Xuelin,Xu Ke.Utilization maximization model of virtual machine scheduling in cloud environment[J].Chinese Journal of Computers,2013,36(2):252-262.

[20]Weng Chuliang,Liu Qian,Yu Lei,el al.Dynamic adaptive scheduling for virtual machines[C]//Proceedings of the 20th International Symposium on High Performance Distributed Computing,San Jose,USA,Jun 8-11,2011.New York:ACM,2011:239-250.

附中文參考文獻(xiàn)：

[4]金海,鐘阿林,吳松,等.多核環(huán)境下虛擬機(jī)VCPU調(diào)度研究:問題與挑戰(zhàn)[J].計算機(jī)研究與發(fā)展,2011,48(7):1216-1224.

[19]師雪霖,徐恪.云虛擬機(jī)資源分配的效用最大化模型[J].計算機(jī)學(xué)報,2013,36(2):252-262.

YU Qianqian was born in 1993.She is an M.S.candidate at Institute of Parallel and Distributed Systems,Shanghai Jiao Tong University.Her research interests include synchronizations,non-volatile memory and file systems,etc.

余倩倩（1993—），女，浙江永嘉人，上海交通大學(xué)并行與分布式系統(tǒng)研究所碩士研究生，主要研究領(lǐng)域為同步，非易失性內(nèi)存，文件系統(tǒng)等。

DONG Mingkai was born in 1992.He is an M.S.candidate at Institute of Parallel and Distributed Systems,Shanghai Jiao Tong University.His research interests include synchronizations,non-volatile memory and file systems,etc.

董明凱（1992—），男，河北唐山人，上海交通大學(xué)并行與分布式系統(tǒng)研究所碩士研究生，主要研究領(lǐng)域為同步，非易失性內(nèi)存，文件系統(tǒng)等。

Hardware Transactional Memory Assisted Synchronization Mechanism in Virtualized Environment*

YU Qianqian+,DONG Mingkai,CHEN Haibo
Institute of Parallel and Distributed Systems,Shanghai Jiao Tong University,Shanghai 200240,China

In a virtualized environment,there is a common existence of double scheduling problem.Moreover,overcommitment exacerbates the problem,and causes a significant performance downgrade.As a result,how to alleviate this problem while protecting the system’s fairness and improve its overall performance has become a critical issue.This paper studies the performance issue of synchronization mechanism caused by double scheduling problem,and proposes a new synchronization mechanism SPINRTM with the help of hardware transactional memory.On the one hand,SPINRTM takes advantage of hardware transactional memory to protect critical sections from being preempted,which effectively alleviates double scheduling problem.On the other hand,it is combined with ticket spinlock to protect the efficiency of hardware transactional memory and guarantee the fairness of the system.Evaluation results show that SPINRTM can protect the system's fairness and improve its performance at the same time when resources are overcommitted.

virtualization;hardware transactional memory;synchronization mechanism

the Ph.D.degree in computer systems architecture from Fudan University in 2009.Now he is a professor at School of Electronic Information and Electrical Engineering,Shanghai Jiao Tong University.His research interests include systems software and systems architecture,etc.

2016-09, Accepted 2016-11.

A

TP316.1

+Corresponding author:E-mail:kiki_yu@sjtu.edu.cn

YU Qianqian,DONG Mingkai,CHEN Haibo.Hardware transactional memory assisted synchronization mechanism in virtualized environment.Journal of Frontiers of Computer Science and Technology,2017,11(9)：1429-1438.

10.3778/j.issn.1673-9418.1609034

*The National Natural Science Foundation of China under Grant No.61572314(國家自然科學(xué)基金面上項目);the National Key Research&Development Program of China under Grant No.2016YFB1000104(國家重點研發(fā)計劃);the Zhangjiang High TechnologyAchievement Transformation Program under Grant No.201501-YP-B108-012(張江高科技園區(qū)高新技術(shù)成果轉(zhuǎn)化項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2016-11-11, http://www.cnki.net/kcms/detail/11.5602.TP.20161111.1627.008.html

摘 要：在虛擬化系統(tǒng)中，雙重調(diào)度問題普遍存在。過度負(fù)載的現(xiàn)象進(jìn)一步加劇了雙重調(diào)度問題，造成了不可忽視的性能下降。如何在保護(hù)系統(tǒng)公平性的同時，緩解雙重調(diào)度問題帶來的負(fù)面影響，提高系統(tǒng)的整體性能，成為一個重要的課題。通過研究雙重調(diào)度引發(fā)的同步機(jī)制效率問題，結(jié)合硬件事務(wù)內(nèi)存的特點，為虛擬機(jī)內(nèi)核設(shè)計了新的同步機(jī)制SPINRTM。一方面，SPINRTM基于硬件事務(wù)內(nèi)存不可被打斷的特性，保護(hù)了虛擬機(jī)內(nèi)的臨界區(qū)間，使其不被打斷，有效緩解了雙重調(diào)度問題；另一方面，SPINRTM結(jié)合了傳統(tǒng)的排隊自旋鎖，保護(hù)了硬件事務(wù)內(nèi)存的運行效率，也維護(hù)了系統(tǒng)的公平性。測試證明，在超負(fù)載的情況下，SPINRTM能夠在保護(hù)系統(tǒng)公平性的同時，提高系統(tǒng)的整體性能。

陳海波（1982—），男，2009年于復(fù)旦大學(xué)計算機(jī)系統(tǒng)結(jié)構(gòu)專業(yè)獲得博士學(xué)位，現(xiàn)為上海交通大學(xué)電子信息與電氣工程學(xué)院教授、博士生導(dǎo)師，主要研究領(lǐng)域為系統(tǒng)軟件，系統(tǒng)結(jié)構(gòu)等。