對延遲敏感型應用的虛擬機調度算法

佘名高 張 顏

(武漢理工大學計算機科學與技術學院 湖北 武漢 430070)

對延遲敏感型應用的虛擬機調度算法

佘名高 張 顏*

(武漢理工大學計算機科學與技術學院 湖北 武漢 430070)

針對Credit調度算法不能保證實時性的不足提出兩點改進。首先，當有大量I/O任務時對BOOST態虛擬CPU進行負載均衡來縮短系統響應時間。其次，利用動態時間片代替原來的固定時間片去適應虛擬CPU的動態變化。通過檢測系統對任務的平均響應時間和周轉時間來評估改進前和改進后對I/O任務的響應的影響。實驗研究表明，改進之后的Credit調度算法平均響應時間與改進前相比降低了102.3%，可以顯著提高I/O延遲敏感型應用的性能。

Xen Credit調度算法 虛擬化 負載均衡

0 引 言

隨著近年來云計算的興起，虛擬化技術也成為企業和學者研究的熱門領域之一。大量企業利用Xen虛擬化技術管理自己的應用服務，通過虛擬化技術可以方便實現資源的充分利用，資源的快速重分配，以及增加系統的靈活性。這些都是影響應用服務成功交付的關鍵因素[1]。

當應用采用Xen虛擬化技術進行管理，Xen調度虛擬機會造成額外的開銷，對某些應用程序的整體性能會造成一定的影響。一個典型的例子，如基于流的音頻/視頻服務是對延遲敏感的I/O密集型應用。通常情況下，這些應用不需要消耗大量的CPU計算資源，但是對服務響應的實時性要求較高。然而，Xen虛擬化技術缺省的Credit 調度算法針對延遲敏感型應用的性能還不夠理想。改進Credit調度算法，使I/O延遲敏感型應用得到及時響應一直是虛擬化研究的熱點領域。當前，Govindan等提出了一種在計算密集型應用中，通過犧牲短期的公平，來優先調度面向通信域的通信感知調度算法[2]。同樣的，Ongaro等主張利用Boost/Tickle機制去提升I/O域的調度優先級[3]。

為了進一步探尋這些改進算法的性能。在本文中提出的改進算法可以看作是前人想法在多處理器平臺上的一個拓展。首先，在多核系統中，通過均衡I/O密集型任務的優先級(即BOOST態虛擬CPU的優先級)來盡量減少系統的響應時間。其次，通過利用動態時間片而不是固定時間片來優化CPU切換的頻率。

1 Xen虛擬機管理器以及Credit調度算法

Xen虛擬機管理器VMM是一個開放源代碼的虛擬化管理軟件，它工作在底層硬件資源之上，為上層虛擬機實例(又稱為域，Domain)提供服務[4]。Xen的默認調度算法是Credit調度算法。

1.1 Credit調度算法的基本原理

Credit調度算法是公平共享的非搶占式調度算法[5]。它可以為每一個域分配Credit值，Xen按照Credit值公平調度各個域。

Xen-4.1之前的版本，Credit調度算法在調度時，Domain有兩種優先級狀態：UNDER狀態和OVER狀態。每個物理CPU都管理一個可運行的隊列，根據VCPU的優先級將其進行排列入隊。調度器會優先調度處于UNDER狀態的VCPU，當發現虛擬CPU對應域的Credit值小于零時，就將VCPU的狀態轉化為OVER狀態。當處于UNDER狀態的虛擬機全部都調度完之后，處于OVER狀態的虛擬機才會得到調度的機會。此時，Credit調度算法將重新為每個域賦予Credit值，然后把相應的VCPU調整為UNDER狀態，如此周期循環。由于系統總是優先調度處于UNDER隊列頭的VCPU。此Credit調度算法僅適合于工作負載為計算密集型應用，卻不適合I/O延遲敏感型應用。為了盡量減小I/O敏感型事件的響應延遲，Ongaro等提出在Credit調度算法中引入BOOST機制[3]。通過在系統中添加一個新的BOOST優先級，允許一個為BOOST狀態的VCPU(即BOOST態VCPU)去搶占一個正在運行的UNDER態 VCPU。

加入BOOST機制的Credit調度通過事件信道接收事件，當有I/O操作的任務時，系統會將處于阻塞狀態的UNDER態VCPU優先權提升到BOOST狀態并將其喚醒。喚醒的VCPU立即搶占CPU資源而不是進入運行隊列與其他域競爭。因此，I/O密集型任務響應時間減少。圖1顯示了Credit調度算法的結構圖，其中四個域位于同一臺機器上，以有效利用底層物理資源。

圖1 Credit調度算法的結構圖

1.2 Credit調度算法的性能分析

在這一部分，分析當前Credit調度算法中可能導致I/O延遲敏感型應用性能不足的兩個問題，并把他們稱為多BOOST態問題以及固定時間片問題。

1) 多BOOST態問題:是指多個域同時提升到BOOST狀態導致調度算法性能降低的現象，這種情況通常在處理I/O密集型任務中時有發生。由于處于UNDER狀態的虛擬CPU在隊列中等待被調用，可能導致的響應延遲，通過加入BOOST狀態，使得具有BOOST狀態的虛擬機能立即被調度，以減少調度的響應時間。但是，當大量I/O應用并發執行時，這些應用對應域的VCPU都會進入BOOST狀態，導致BOOST態的VCPU負載失衡，某些應用仍不能及時得到調度。如圖2所示，在四核平臺下的32個非特權域均勻分為四組，每組各8個域同時運行在Xen-4.4.2的虛擬機管理器上，測試兩個程序(Ping和Zip)在物理CPU上運行BOOST態VCPU的時間。從圖中數據可知BOOST 態VCPU分布不均。

圖2 BOOST態VCPU在物理CPU上的分布

2) 固定時間片問題：當PCPU調度處于UNDER狀態的VCPU時,允許相應的VCPU運行一個為30 ms的固定時間片，這個時間片的設置一方面獨立于VCPU數量，另一方面還得確保域間調度的公平。因此這可能導致兩個問題：當運行隊列的VCPU數量小，固定時間片將導致在運行隊列中的VCPU之間頻繁切換，增加系統開銷。當VCPU數量較多，固定時間片的設置將導致在隊列的尾部VCPU響應時間過長。理論上，在一個固定的時間間隔內，時間片越長，表示越少的VCPU切換和越短的調度平均周轉時間。對于一個延遲敏感型任務，響應時間與運行隊列中等待任務的數量是密切相關的。因此，根據等待隊列中VCPU的數量動態的調整調度時間片可能是更理想的方式。

2 改進調度算法的設計與實現

上文論述了Credit調度算法存在的不足，在這一節中，首先提出了Credit調度算法的改進算法，然后，描述算法的核心實現步驟。

2.1 對BOOST態的域進行負載均衡

在第1節中提到，Credit調度算法可能引起多BOOST態同時存在的問題，導致在PCPU之上的BOOST 域分布不均。雖然Credit調度算法可以實現全局負載均衡，但是當BOOST域較多時，會使得整個系統的響應速度降低。為了解決這個問題，實驗中將物理機上每個PCPU對應運行隊列的中BOOST態VCPU進行負載均衡，改進VCPU的響應速度。實驗使用的負載均衡算法如下所示：

在BOOST域被喚醒并插入運行隊列之后，VMM會給調度器一個與該PCPU調度相關隊列的反饋。在這個操作被執行之前，先執行一個簡單的負載平衡算法：

1) 檢查相應PCPU上正在運行的VCPU是否是BOOST狀態。

2) 如果是，基于下文提出的標準選擇目標PCPU，其中VCPU應該是可轉移的。如果目標PCPU和源PCPU是相同的，那么就退出。否則，將VCPU插到目標PCPU的運行隊列中。

3) 如果當前運行的VCPU不是BOOST態，那么就觸發缺省的PCPU調度策略，然后退出。

在多核系統中，目標PCPU是根據以下標準選擇：

1) 按照相同的內核，相同Socket的順序搜索閑置的PCPU。如果找到，則返回的PCPU的數量。

2) 找到運行隊列中包含BOOST 態VCPU最少的PCPU，然后返回PCPU數。

該標準背后的基本原理是計算的空間局部性。例如，如果兩PCPU共享相同的內核，那么，它們也可以共享相同的本地緩存。

2.2 動態時間片

在Credit調度算法中，30 ms固定時間片的設置獨立于VCPU狀態。BOOST態VCPU時間片的運行分為兩個階段。在第一階段，VCPU將在BOOST 狀態下運行10 ms，然后切換到UNDER狀態，進入第二階段。BOOST狀態下的時間長度是VCPU調度的關鍵。如果這個長度太長，其他相同優先級的VCPU可能被延遲，增加I/O響應時間。另一方面，如果太短，BOOST態 VCPU在被其他BOOST態VCPU搶占之前無法獲得充分的執行時間。為了均衡系統的平均周轉時間和I/O敏感型應用的平均響應時間，本文提出動態時間片，時間片的長度根據運行隊列中VCPU的數量進行動態調整。時間片的優化算法是在選定VCPU之后進行以下步驟：

改變的BOOST第一階段的運行時間片長度為2 ms，約為I/O程序運行在BOOST 態VCPU的時間長度，將它插入到運行隊列，然后改變其優先級為UNDER。因此，被選定的VCPU在隊列中將位于所有UNDER 態VCPU之前，所有BOOST 態VCPU之后。如果隊列中沒有其他的BOOST態 VCPU，那么剛插入的VCPU就可以繼續調度執行。

根據隊列中UNDER態VCPU的數量，計算UNDER態 VCPU 的時間片，通過以下公式得出：

(1)

式中，avg_length為運行隊列的缺省長度，在Credit調度算法中一般缺省設置為4。qlen指在計算時間片時隊列中UNDER態VCPU的數量。

這個改進基于兩點考慮。首先，在BOOST階段，I/O密集型程序經常進入阻塞狀態，基本不消耗VCPU。因此，該VCPU通常不需要分配很長的時間片。另一方面，如果除了阻塞I/O程序之外其他的程序同樣運行在BOOST態VCPU中，這些應用程序還將繼續運行在BOOST 態直到時間片結束。它將延遲其他BOOST態VCPU被調度的時間。因此需要先分配一小段時間片(2 ms)進行處理。其次，在UNDER階段，又分為兩種情況。其一，由于VCPU關聯關系項很小，在隊列中UNDER態VCPU的數量基本不變。如果有相當多的VCPU，可以增加時間片來減少調度開銷。正如前面所討論的，事實上，UNDER態 VCPU的數量與PCPU的數量關聯性通常很小，改進算法應該優化這種常見的情況。其二，增加的時間片不應該在很大范圍內變化，否則，它可能會損害Credit調度算法的目標公平性原則。因此，在本文提出的改進算法中，使用了兩個固定值(30 ms和60 ms)優化調度器的運行隊列，來實現調度算法公平的目標。

使用動態時間片來改進算法是比較容易實現的。首先，添加顏色屬性到VCPU的數據結構中，當VCPU插入運行隊列時設置為紅色，當它從隊列中出來重新計算時間片時設置為黑色。基于這個屬性，改進算法執行以下步驟：

1) 檢查選定的VCPU的狀態。如果是在BOOST狀態，那么時間片直接設置為30 ms。

2) 如果選定的VCPU不在BOOST狀態，那么檢查該VCPU的顏色。如果它是黑色的，時間片將設置為一個值，根據式(1)計算得出。否則，如果它是紅色的，表示之前計算的時間片已經過期，算法需要重新計算它。

3) 鎖定整個運行隊列，計算VCPU的數量并根據式(1)重新計算時間片，然后設置所有的VCPU為黑色，存儲時間片到每個PCPU的局部結構。

4) 計算下一個VCPU時間片的值。

3 實驗與評估

在這一部分中，通過大量的實驗來評估提出的改進算法。首先介紹實驗裝置，之后通過測量延遲敏感型應用的響應時間來評估提出的改進算法。實驗數據表明，所提出的改進算法可以顯著提高延遲敏感型任務的性能。

3.1 實驗裝置

實驗所使用的設備包括兩個物理機和32個虛擬機(不包括驅動域)。兩個物理機的通過100 Mbps以太網連接，它們的配置如表1所示，所有的虛擬機安裝在一臺物理機器之上是通過Xen-4.4.2管理的，另一臺物理機作為遠程主機與這些虛擬機通信。實驗中每個域的配置如表2所示，Domain0以CentOS-5.2作為客戶操作系統。本研究的主要目的是通過優化Credit算法減少延遲敏感型應用的響應時間。實驗選擇Ping和一個基本的搜索程序作為實驗測試的程序，這兩種程序在此類研究中被廣泛采用。具體地講，一個遠程系統發送Ping命令到客戶操作系統，客戶操作系統只確認收到Ping數據包不做任何其他的計算。通過網絡延遲的時間作為參照，來評估本文提出的算法的性能。

表1 硬件配置

表2 虛擬機的配置

3.2 將BOOST 態負載平衡后的算法評估

在實驗中，為了評估在BOOST 態虛擬機的負載情況，首先創建20個客戶域平均分為兩組，各有10個虛擬機。然后，讓在第二組的虛擬機每隔一秒去Ping第一組的虛擬機，以產生大量BOOST 態VCPU。然后，通過計算每一個Ping的響應時間。算法改進前和改進后比較結果如圖3所示。很明顯優化之后數據包的響應時間不僅顯著降低而且也更穩定。這表明對BOOST態VCPU進行負載平衡能有效提高系統性能。這種現象不難理解，BOOST態VCPU在運行隊列中是有組織的等待，這將導致在隊列前面的VCPU能更快地獲得調度，從而縮短了Ping的響應時間，但在隊列后面的VCPU他們會較慢獲得調度，使Ping的響應時間較長，從而導致不穩定。與之相反，在改進負載平衡后，BOOST態 VCPU被均勻分布到每個PCPU的運行隊列中，在每個運行隊列中BOOST態VCPU平均增加的數量相應的降低。因此，即使BOOST態VCPU在運行隊列的后端也不會等待太久。因此，Ping的響應時間波動較小(約在0.08 ms)，平均響應時間與改進前相比降低了102.3%且更穩定。

圖3 Boost態負載均衡前和改進后運行Ping程序響應時間的比較

3.3 改進動態時間切片算法的評估

為了全面評估改進算法，在實驗中，我們集中評估了算法對延遲敏感型應用平均響應時間的影響和系統平均周轉時間的影響。研究結果表明，改用動態時間片的算法，可以明顯降低平均響應時間和平均周轉時間。

VCPU的平均響應時間：在這個實驗中，對基本搜索服務進行壓力測試來測量VCPU平均響應時間。為此，首先配置一臺作為搜索服務器的測試機，其中包括四個客戶操作系統，并觀察在不同強度搜索請求下客戶操作系統中的響應情況。然后，使用四個客戶操作系統的平均響應時間來度量評估改進動態時間片算法的性能。

如圖4所示，隨著請求數量增多，改進動態時間片后算法平均響應時間和改進之前相比要短。這是由于搜索服務器部署在虛擬機中，它可能發生多個進程在同一個VCPU中運行。算法改進前，當VCPU 進入BOOST狀態，除了I /O進程，其他的計算密集型進程也會使BOOST態VCPU長時間執行，在對延遲敏感型任務較多時此方案不合理。改進后，時間片調整為

2 ms，只允許I/O程序的VCPU有BOOST狀態而其他的VCPU只能處于UNDER狀態 。在圖4中，當請求強度較低時，改進前和改進后的平均響應時間幾乎相同。這是因為在這種情況下，只有很少BOOST態VCPU在隊列中等待。而隨著請求強度的增加，BOOST態VCPU的數量不斷增長，改進之后進行了BOOST態VCPU的負載均衡，結果顯然是比改進之前的平均響應時間要低。

圖4 優化動態時間片之前和之后的平均響應時間比較

平均周轉時間：在Credit調度中，UNDER態的VCPU時間片設置為30 ms。而在改進的算法中，當等待運行隊列長度小于缺省值時進行優化。表3顯示了算法改進前和改進后在運行隊列中VCPU數量從1到8時平均周轉時間的對比，Credit算法缺省設置隊列長度為4。隨著VCPU的數量增多，可以觀察到調度算法改進后的平均周轉時間比改進前要低。并且，他們之間的差值隨著執行時間的變化在逐漸增加，如圖5所示。原因是當UNDER態VCPU數量小于預設值，該算法為了減少調度開銷設置時間片為60 ms。然而，當UNDER態 VCPU隊列長度大于預設值，改進前和改進后的兩個算法具有相同的時間片30 ms。因此，它們表現出大致相同的周轉時間。這些結果表明，當UNDER VCPU在隊列中的數量較少時，增加時間片可以明顯提高系統的性能。

表3 使用Benchmark工具，測試運行隊列中VCPU數量和周轉時間的關系

圖5 隨著Benchmark運行時間的延長，改進前與改進后平均周轉時間的差值

4 結 語

本文分析了Xen缺省調度算法Credit算法的基本原理。研究了Credit調度算法對延遲敏感型應用存在的兩個性能不足之處：多BOOST態導致CPU調度的負載不均衡以及固定時間片導致調度算法性能未能達到最優的情況。針對這兩個不足給出改進算法的基本思想。實驗結果表明，本文提出的改進算法與默認的Credit調度算法相比，在延遲敏感型應用中VCPU的平均響應時間更小且響應時間更加穩定，調度算法的性能相較于改進前有顯著提升。

[1] Wu S,Zhou L,Sun H,et al.Poris:A Scheduler for Parallel Soft Real-Time Applications in Virtualized Environments[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(3):841-854.

[2] Govindan S,Nath A R,Das A,et al.Xen and co.:communication-aware CPU scheduling for consolidated xen-based hosting platforms[C]//International Conference on Virtual Execution Environments,VEE 2007,San Diego,California,Usa,June.2007:1111-1125.

[3] Ongaro D,Cox A L,Rixner S.Scheduling I/O in virtual machine monitors[C]//International Conference on Virtual Execution Environments,VEE 2008,Seattle,Wa,Usa,March,2008:1-10.

[4] Wu J,Wang C Y,Li J F.LA-Credit:A Load-Awareness Scheduling Algorithm for Xen Virtualized Platforms[C]//Big Data Security on Cloud (BigDataSecurity),IEEE International Conference on High Performance and Smart Computing (HPSC),and IEEE International Conference on Intelligent Data and Security (IDS),2016 IEEE 2nd International Conference on.IEEE,2016:234-239.

[5] Zhou L,Wu S,Sun H,et al.Virtual Machine Scheduling for Parallel Soft Real-Time Applications[C]//2013 IEEE 21st International Symposium on Modelling,Analysis and Simulation of Computer and Telecommunication Systems.IEEE Computer Society,2013:525-534.

[6] Wang K,Hou Z.A relaxed co-scheduling method of virtual CPUs on Xen virtual machines[J].Journal of Computer Research & Development,2012,49(1):118-127.

[7] Xu C,Gamage S,Rao P N,et al.vSlicer:latency-aware virtual machine scheduling via differentiated-frequency CPU slicing[C]//International Symposium on High-Performance Parallel and Distributed Computing.ACM,2012:3-14.

[8] Xi S,Wilson J,Lu C,et al.RT-Xen:Towards Real-time Hypervisor Scheduling in Xen[C]//International Conference on Embedded Software,EMSOFT,2011:39-48.

[9] Seo J,Kim K H.A Prototype of Online Dynamic Scaling Scheduler for Real-Time Task based on Virtual Machine[J].International Journal of Electrical and Computer Engineering,2016,6(1):205-211.

[10] Cheng K,Bai Y,Wang R,et al.Optimizing Soft real-time scheduling performance for virtual machines with SRT-Xen[C]//Cluster,Cloud and Grid Computing (CCGrid),2015 15th IEEE/ACM International Symposium on.IEEE,2015:169-178.

[11] Venkatesh V,Nayak A.Optimizing I/O Intensive Domain Handling in Xen Hypervisor for Consolidated Server Environments[M].Green,Pervasive,and Cloud Computing. Springer International Publishing,2016:180-195.

VIRTUALMACHINESCHEDULINGALGORITHMFORLATENCY-SENSITIVEAPPLICATIONS

She Minggao Zhang Yan*

(SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430070,Hubei,China)

This paper proposes two improvements to the problem that the Credit scheduling algorithm can not guarantee the real-time. First, we can shorten the system respond time by loading balancing about the virtual CPU in BOOST state when it has a lot of I/O tasks. Second, we can use dynamic time slice instead of the former fixed time slice to adapt to the dynamic change of the virtual CPU. The impact of the improvement on the I/O task is evaluated by detecting the average response time and turnaround time of the task. The experimental results show that the average response time of the improved Credit scheduling algorithm is 102.3% lower than that before improvement, which can significantly enhance the performance of I/O latency-sensitive applications.

Xen Credit scheduling algorithm Virtualization Load balancing

TP3

A

10.3969/j.issn.1000-386x.2017.09.006

2016-11-28。佘名高，副教授，主研領域：計算機體系架構。張顏，碩士生。