多核平臺下XEN虛擬機動態調度算法研究

黃漾

收稿日期：2013-10-18

基金項目：國家自然科學基金重點項目（61133005）； 湖南省科技廳課題項目（2011FJ3067）

作者簡介：黃 漾（1974—），女，湖南株洲人，副教授，碩士，研究方向：分布式系統、并行計算。

通訊聯系人，E-mail：543179572@qq.com

文章編號：1003-6199（2014）03-0084-04

摘 要：虛擬機調度算法對并行任務的執行效率考慮不夠充分?，F代處理器平臺具備了多個可用的計算核心，使多個虛擬機并發執行成為了現實。針對多核平臺下的并行虛擬機調度優化問題，提出一種基于任務特征虛擬機CON-Credit調度算法。該算法在調度并行任務時，使用動態方式對計算機核心進行分配，采用傳統的虛擬機調度算法為執行普通任務的虛擬機進行分配；采用定制的同步算法給執行并行任務的虛擬機分進分配。相關實驗顯示，CON-Credit調度算法能顯著提高并行任務的執行效率。

關鍵詞：多核； 虛擬機； VMM； 調度；MapReduce

中圖分類號：TP311 文獻標識碼：A

Dynamic Scheduling Model of XEN Virtual Machine in Multi-core System

HUANG Yang

（Hunan Vocational College of Railway Technology， Zhuzhou，Hunan 412000，China）

Abstract：The virtual machine scheduling algorithm doesnt fully consider the execution efficiency of parallel application. Modern processors have multiple available computing core， so that concurrent execution of multiple virtual machines become a reality. In this paper， a parallel multicore platform virtual machine scheduling problems， Presents a task-based Virtual Machine CON-Credit scheduling algorithm. The algorithm in the scheduling of parallel tasks， Dynamically allocated using a computer core， using the traditional virtual machine scheduling algorithm to perform common tasks allocated virtual machines； Using custom synchronization algorithm to perform parallel tasks assigned virtual machine. Related experiments show， CON-Credit scheduling algorithm can significantly improve the efficiency of the parallel task execution.

Key words：multi-core； virtual machine； VMM； scheduling； MapReduce

1 引 言

目前系統級虛擬機技術已成為云計算平臺的重要基礎設施，KVM、XEN、VMware等大批虛擬機平臺已被廣泛部署和應用。虛擬機調度由虛擬機管理器（VMM）實施，VMM采用了不同的虛擬化方法，為每一個虛擬機分配虛擬CPU，其虛擬機調度算法負責將所有虛擬機所使用的VCPU分配到物理CPU上。由于PCPU數量通常遠小于VCPU，如何高效地在各虛擬機之間分配處理器是虛擬機調度的研究熱點之一.目前VMM的調度算法，直接借鑒了操作系統的調度思路，并不能反映虛擬機自身的特點；虛擬機是硬件加軟件的集合。根據不同的任務特征設計調度算法，滿足多種任務類型需要。多核平臺可同時運行多個虛擬機，調度算法已從純粹的時分復用向時分復用與空分復用相結合的混合調度模式過度。當請求任務中包含并行任務時，VMM默認的調度算法性能無法適應底層硬件特點，導致并行任務的執行效率下降。以XEN為例設計應用于并行環境的調度算法——CON-Credit。該算法根據當前資源狀態和任務特點動態調整資源，將CPU分配給不同類型任務，確保并行任務在空間上的分布執行和時間上的并發執行，提高多核平臺的整體性能。

2 算法與實現

2.1 問題提出及算法分析

XEN中默認調度算法——Credit算法沒有充分考慮虛擬機之間的協作關系及多核特點，單純基于時間來劃分和調度不同的處理器核，這不利于MapReduce型的并行編程框架。 MapReduce是由Google公司實現的分布式計算模型，該框架結構結合了早期的人工智能領域的Lisp語言的設計思想[1]。美國斯坦福大學設計了第一個面向共享內存系統的MapReduce計算框架[2]，而復旦大學則開發出原型系統Ostrich，采用一種分塊MapReduce編程模型，以適用于NUMA系統的特點[3]

使用MapReduce模型時，其用戶需要指定兩個函數；Map和Reduce。 Map把一組鍵值對映射成一組新的鍵值對，Reduce接受一個鍵和相關的一組值，將這組值進行合并最后生成一組規模更小的值。Map是高度并行的，Reduce則依賴于Map的結果。且Map操作的并行性和均衡性決定MapReduce程序的整體效率。

例舉MapReduce結構模型如圖1所示，其中表示計算任務節點集合，設在同一層的所有節點的計算時間相同，令第i層任務的處理時間T（Vi）：

T（Vi）=T（Vi1）=T（Vi2）=…=T（Vij），i=1，2，3…，l

設處理器核4個，該MapReduce任務模型在Credit調度算法下，一旦任務在所分配的某一Credit值下不能完成該任務時，正在執行的任務會被迫中斷，并調入另一任務運行，且處在同一層的其他任務可能不會在同一時間內得到處理器資源，已處理完畢的任務必須等待該層所有任務完成，才能進入下一層次的任務執行。等待時間往往不確定且不可忽視。如圖2可能出現的調度情況，總的完成時間：

T=41T（V1）+21（V2）+T（V3）+T（V4）

對于并行計算任務，依據各自的任務權重來動態分配PCPU；時間上統一決定處理器核的啟動時間和運行時間，對一個任務節點來說，下一層任務必須等待上一層任務全部完成后才開始執行。進一步考慮混合任務類型同時執行的情況，設該MapReduce模型和另外5個串行任務同時請求，物理處理器核數為6，預先分配3個為普通任務類型，分配3個為并行任務類型。運行時采用動態分配資源機制，對不同類型任務根據其任務量來動態調整資源分配。core3結束J3后一直處于空閑狀態，若動態分配給V17，此時調度情況如圖3所示：

分析可知，默認算法對并行任務存在缺陷，而針對多核的改進算法有更好的適應性。且對混合型任務的分析說明，動態調度更有利提高資源利用率和性能，減少總執行時間。

據上分析提出基于任務類型動態劃分多核處理器的調度模型CON-Credit。在原結構基礎上增加了任務狀態監控和調度決策模塊，前者通過讀取事件通道中的數據來收集設備訪問過程中的時間和任務狀態信息；后者對收集到的信息實時處理，動態分配資源到各個VCPU處理相應類型的任務，條件滿足時做出調度決策。整體結構如圖4所示，實現包括；將處理器核動態劃分為COM-Core和CON-Core， COM-Core對應串行任務，CON-Core對應并行任務；調度器根據應用類型在不同的集合內進行調度；任務狀態監測與動態劃分決策；實現虛擬機并行協作調度。

2.2 CON-Credit策略分析

考慮|P|個處理器核的系統，用P={P1，P2，…，Pp}；所有多核處理器，J={J1，J2，…，Jn} 為待處理的n個串行任務，代表任務i的處理時間。V={V11，V12，…，V21，V22，…，Vi1，…，Vij}共m個任務。令W=JV。設|D|個虛擬機CPU的集合為D={D1，D2，…，DD}。某一運行時刻，成立，其中分別表示該時刻正在運行的任務，VCPU及PCPU數。在多核VMM系統中，任務調度包括VCPU對任務的虛擬機分配，設Dk=λ（Wi），以及VMM對各個虛擬機的PCPU分配，設Pj=μ（Dk），于是Pj=μ（λ（Wi））表示將處理器核j分配給任務i。對|P|個核動態分配，令串行任務所需資源的比重為ω（Pj），并行任務所需資源的比重為ω（Pv），且ω（Pj）+ω（Pv）=1。

3 性能分析

3.1 實驗環境與基準

本文所使用的實驗平臺硬件配置為Intel八核Xeon 7550處理器，主頻為2。0MHz，18M緩存，Seagate 1TB IDE 硬盤，DDRII-800 8GB內存，RTL 8139D 200Mbps 以太網卡。實驗中使用的XEN版本號為4。1。2，Domain0和所有的Domain U的操作系統都為Fedora16 64位，Linux 版本號為3.10.17。實驗通過在XEN上搭建8個虛擬機來創建虛擬集群環境進行實驗。為全面的研究算法的性能，比較分析CON-Credit調度算法；高效性，CON-Credit相對于傳統Credit算法對并行任務調度性能的提升；適應性，混合任務模式下CON-Credit的算法性能。

為說明CON-Credit算法，構造四個MapReduce程序[4]；點乘；在MapReduce實現中，把乘法運算作為Map函數，把求和運算作為Reduce函數。π估算；采用蒙特卡羅概率算法，Map函數輸出的是一連串的二進制值0或1，Reduce函數負責求和，最后再計算π的值。RC4密鑰查找；標準的64bit無線加密協議。Map函數輸入是一個指針指明開始探尋的位置，Reduce函數則檢查返回值和輸出正確的密鑰。N-體問題[5]；是解一組已知初始值的常微分方程組。輸入的Map函數是n個粒子當前的信息和計算顆粒指數，Reduce則負責計算各粒子的新狀態。

3.2 實驗結果及分析

實驗中以MapReduce程序和串行程序（如排序算法及 .gcc）為例，驗證并比較改進前后算法的性能。在8個Domains上混合調度虛擬集群測試，測試該環境下運行MapReduce應用與串行應用的性能。設置4個于并行MapReduce程序，4個于串行程序，取MapReduce迭代次數為109。兩種算法下各任務的執行時間如圖5（a）所示。得出CON-Credit算法性能相對于傳統算法，點乘，π估算，RC4運算，N-體所需執行時間分別減少24.98%，24.06%，28.50%，25.31%。而排序算法，176.gcc所需執行時間分別增加5.43%，9.28%。

設置8個Domains中6個用于MapReduce程序，2個用于串行應用程序，取MapReduce應用迭代次數為109。兩種算法下各程序的執行時間如圖5（b）所示。并得出CON-Credit算法性能相對于傳統算法，點乘，π估算，RC4運算所需執行時間分別減少25.33%，26.14%，28.91%。排序算法，176.gcc所需執行時間分別增加5.43%，6.19%。這由于改進后的VMM中，增加了決策模塊，導致對于串行任務所需時間有少許增加，在大環境下是可接受的。綜合分析，相較于實驗二中兩組數據，通過實驗數據圖5（a）和（b）驗證了當串行任務比例較高時，改進后的算法效率降低。經實驗驗證，改進后的算法對于混合任務請求特別是對于并行任務具有極大意義。

4 相關工作

本小節對XEN VMM調度算法目前相關工作做簡要介紹。Kim等人在2009年VEE上發表的文獻[6]為了提高I/O任務的性能提出了任務特性感知的虛擬機調度算法，優先調度I/O-bounds的任務，在提高I/O任務性能的基礎上不降低CPU-bounds任務的性能。Weng等人針對目前運行在VM中的負載可以分為高吞吐量和并發任務兩種類型，在虛擬機系統中設計了一個混合調度框架，根據任務類型選擇不同的調度策略[7]。Diego Ongaro等人分析了不同調度特性支持的情況下，XEN調度在面向I/O密集型應用時的性能表現，其研究工作主要針對Credit調度進行[8]。Hwanju Kim等人測試了XEN系統Credit調度算法中的boost機制，提出了一種Partial-Boost方法[9]，該方法通過檢查I/O事件目標VCPU的CR3寄存器來判斷當前是否處于I/O密集進行應用的上下文中，以決定是否執行boost操作。L Shi等人[10]提出了一個vCUDA框架，GPGPU的虛擬機的高性能計算解決方案。vCUDA允許應用程序在虛擬機上的執行，以充分利用硬件加速功能，對HPC應用程序的性能具有意義。

5 總結及展望

本文針對傳統虛擬機調度算法不適應并行任務調度的缺陷，充分利用多核體系結構的內在特點，設計和實現了CON-Credit調度算法。該算法實現了物理CPU的動態分類和匹配，通過在普通任務和并行任務之間的協同調度提高了MapReduce等并行虛擬任務的執行效率。經實驗驗證，該算法在并行任務調度和混合任務調度中表現出良好的性能，具有較強的適應性和擴展性。CON-Credit目前僅部署于XEN虛擬機平臺，未來將向KVM、Hyper-V等虛擬機體系移植以進一步證實其有效性。此外，云計算平臺可能涉及大量異構處理器，如何將并行計算任務與異構虛擬計算環境相結合，設計具有更強適應性的虛擬機調度算法，是值得進一步深入研究的課題。

參考文獻

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.

4 相關工作

本小節對XEN VMM調度算法目前相關工作做簡要介紹。Kim等人在2009年VEE上發表的文獻[6]為了提高I/O任務的性能提出了任務特性感知的虛擬機調度算法，優先調度I/O-bounds的任務，在提高I/O任務性能的基礎上不降低CPU-bounds任務的性能。Weng等人針對目前運行在VM中的負載可以分為高吞吐量和并發任務兩種類型，在虛擬機系統中設計了一個混合調度框架，根據任務類型選擇不同的調度策略[7]。Diego Ongaro等人分析了不同調度特性支持的情況下，XEN調度在面向I/O密集型應用時的性能表現，其研究工作主要針對Credit調度進行[8]。Hwanju Kim等人測試了XEN系統Credit調度算法中的boost機制，提出了一種Partial-Boost方法[9]，該方法通過檢查I/O事件目標VCPU的CR3寄存器來判斷當前是否處于I/O密集進行應用的上下文中，以決定是否執行boost操作。L Shi等人[10]提出了一個vCUDA框架，GPGPU的虛擬機的高性能計算解決方案。vCUDA允許應用程序在虛擬機上的執行，以充分利用硬件加速功能，對HPC應用程序的性能具有意義。

5 總結及展望

本文針對傳統虛擬機調度算法不適應并行任務調度的缺陷，充分利用多核體系結構的內在特點，設計和實現了CON-Credit調度算法。該算法實現了物理CPU的動態分類和匹配，通過在普通任務和并行任務之間的協同調度提高了MapReduce等并行虛擬任務的執行效率。經實驗驗證，該算法在并行任務調度和混合任務調度中表現出良好的性能，具有較強的適應性和擴展性。CON-Credit目前僅部署于XEN虛擬機平臺，未來將向KVM、Hyper-V等虛擬機體系移植以進一步證實其有效性。此外，云計算平臺可能涉及大量異構處理器，如何將并行計算任務與異構虛擬計算環境相結合，設計具有更強適應性的虛擬機調度算法，是值得進一步深入研究的課題。

參考文獻

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.

4 相關工作

本小節對XEN VMM調度算法目前相關工作做簡要介紹。Kim等人在2009年VEE上發表的文獻[6]為了提高I/O任務的性能提出了任務特性感知的虛擬機調度算法，優先調度I/O-bounds的任務，在提高I/O任務性能的基礎上不降低CPU-bounds任務的性能。Weng等人針對目前運行在VM中的負載可以分為高吞吐量和并發任務兩種類型，在虛擬機系統中設計了一個混合調度框架，根據任務類型選擇不同的調度策略[7]。Diego Ongaro等人分析了不同調度特性支持的情況下，XEN調度在面向I/O密集型應用時的性能表現，其研究工作主要針對Credit調度進行[8]。Hwanju Kim等人測試了XEN系統Credit調度算法中的boost機制，提出了一種Partial-Boost方法[9]，該方法通過檢查I/O事件目標VCPU的CR3寄存器來判斷當前是否處于I/O密集進行應用的上下文中，以決定是否執行boost操作。L Shi等人[10]提出了一個vCUDA框架，GPGPU的虛擬機的高性能計算解決方案。vCUDA允許應用程序在虛擬機上的執行，以充分利用硬件加速功能，對HPC應用程序的性能具有意義。

5 總結及展望

本文針對傳統虛擬機調度算法不適應并行任務調度的缺陷，充分利用多核體系結構的內在特點，設計和實現了CON-Credit調度算法。該算法實現了物理CPU的動態分類和匹配，通過在普通任務和并行任務之間的協同調度提高了MapReduce等并行虛擬任務的執行效率。經實驗驗證，該算法在并行任務調度和混合任務調度中表現出良好的性能，具有較強的適應性和擴展性。CON-Credit目前僅部署于XEN虛擬機平臺，未來將向KVM、Hyper-V等虛擬機體系移植以進一步證實其有效性。此外，云計算平臺可能涉及大量異構處理器，如何將并行計算任務與異構虛擬計算環境相結合，設計具有更強適應性的虛擬機調度算法，是值得進一步深入研究的課題。

參考文獻

[1] The Lisp Programming Language[EB/OL].http：//groups.engin.umd.umich.edu/CIS/coursedes/cis400/1isp/1isp. html.

[2] Colb Ranger. Ramanan Raghuraman. Arun Penmetsa. Gan Bradski. Christos Kozyrakis[M].Evaluating MapReducc for Multi-core and Multiprocessor Systems. In the processing of the HPCA. 2007.

[3] Rong Chen. Haibo Chen， and Binvu Zang.. iled-MapReduce： Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling[M].In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. 2010.

[4] JACKSON H C，YEUNG C C，TSANG K.H.Tsoi， et al. Map-reduce as a Programming Model for Custom Computing Machines[M].16th International Symposium on Field-Programmable Custom Computing Machines，2008：149-159.

[5] K.H.TSOI， C.H.HO， H.C.YEUNG，P.H.W.LEONG. An arithmetic library and its application to the n-body problem[J].in Proc.IEEE Symposium on Field-Programmable Custom Computing Machines （FCCM）， 2004：68-78.

[6] H.KIM， H.LIM， J.JEONG， H.JO， et al. Task-aware Virtual Machine Scheduling for I/O Performance[J].In Proceedings of the 4th international conference on Virtual Execution Environments （VEE）， 2009：101-111

[7] Chulianq Wenq， Zhiqang Wanq， Minqlu Li et al. The Hybrid Scheduling Framework for Virtual Machine Systems[J]. In Proceedings of 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environment Washington ，DC， USA， 2009：156-168.

[8] Ludmila Cherkasova and Rob Gardner. Measuring CPU overhead for I/O processing in the xen virtual machine monitor[J]. In USENIX Annual Technical Conference， General Track， 2005：387-390

[9] H.KIM，H.LIM and et al. Task-aware Virtual Machine Scheduling for I/O Performance[C]. VEE， 2009； 101-110

[10]L SHI， H CHEN， J.H SUN， K.L.Li.VCUDA； GPU-Accelerated High-Performance Computing in Virtual Machines[J].IEEE Transaction on Computers doi/10.1109/TC.2011.112.