張 瑩 李 華

（國家知識產(chǎn)權(quán)局專利局專利審查協(xié)作河南中心，河南 鄭州 450000）

虛擬化技術(shù)是企業(yè)創(chuàng)建綠色數(shù)據(jù)中心的核心技術(shù)之一，多處理器技術(shù)的快速發(fā)展使計(jì)算能力有了突破性的提高，同時也使虛擬化技術(shù)成為研究熱點(diǎn)。虛擬化技術(shù)通過在底層物理環(huán)境與虛擬機(jī)之間建立虛擬機(jī)監(jiān)視層，從而屏蔽了復(fù)雜的底層物理環(huán)境，使物理機(jī)硬件資源不僅能夠同時被多個虛擬機(jī)共享，處于運(yùn)行狀態(tài)的虛擬機(jī)還可以在兩臺不同的物理機(jī)之間進(jìn)行無間斷的遷移［1］。因此，為了合并服務(wù)器資源和應(yīng)用，虛擬化技術(shù)逐漸成為大型企業(yè)構(gòu)建安全穩(wěn)定的企業(yè)架構(gòu)的最佳解決方案。

目前，在商業(yè)發(fā)展和開源技術(shù)研究中有多種虛擬化架構(gòu)，其中包括劍橋大學(xué)的XEN。在Xen中，多個虛擬機(jī)同時運(yùn)行在相互隔離的虛擬環(huán)境中，共享底層物理硬件，包括處理器資源，且各個虛擬機(jī)能夠以接近物理計(jì)算系統(tǒng)的性能運(yùn)作［2］。Xen中常用的三種CPU調(diào)度算法包括:BVT（借用虛擬時間算法）、SEDF（最早截止時間優(yōu)先算法）和基于信任值算法（Credit），三種算法各有不同的性能瓶頸，因此，如何實(shí)現(xiàn)高效調(diào)度成為虛擬化技術(shù)中面臨的更大挑戰(zhàn)。

專利CN102053858A中提出了一種虛擬機(jī)調(diào)度算法，通過監(jiān)測虛擬機(jī)的CPU 調(diào)度以及狀態(tài)標(biāo)識信息，解決了鎖搶占問題，從而在多處理器架構(gòu)中實(shí)現(xiàn)更精確的可調(diào)度狀態(tài)監(jiān)測，提高底層物理CPU 資源的利用率［3］。華中科技大學(xué)的金海提出了一種Xen虛擬化環(huán)境中動態(tài)感知音頻應(yīng)用的CPU 調(diào)度算法，通過設(shè)置合適的時間片大小以及增加實(shí)時優(yōu)先級等策略，提高了Xen 中音頻應(yīng)用的播放性能［4］。

本文提出了一種SMP（對稱多處理器）系統(tǒng)中的動態(tài)負(fù)載均衡調(diào)度算法—動態(tài)最早截止時間優(yōu)先算法（DLB_DEF）來提高物理CPU 利用率，從而減少空閑CPU。為了實(shí)現(xiàn)該算法，我們設(shè)計(jì)了一種共享等待隊(duì)列，考慮到多處理器環(huán)境中cache和內(nèi)存的同步關(guān)系，使虛擬CPU在執(zhí)行完任務(wù)之前都在同一個物理CPU上執(zhí)行。仿真實(shí)驗(yàn)表明，改進(jìn)后的DLB_DEF 算法能夠優(yōu)化系統(tǒng)性能，并完全消除空閑物理CPU。

2 SEDF算法以及SMP架構(gòu)

2.1 SEDF算法

在虛擬化計(jì)算環(huán)境中，多個虛擬機(jī)通過分時調(diào)度策略共享物理處理器資源，每個虛擬機(jī)就是一個域，每個域?qū)?yīng)一個或多個虛擬CPU（VCPU）［5］。因此，如何公平高效地將物理CPU 資源分配給多個虛擬機(jī)，并使CPU 有效利用率達(dá)到合理范圍就是一個問題。

SEDF 算法是一種基于最早截止時間策略的實(shí)時算法，每個VCPU都會根據(jù)自身處理情況設(shè)置一個參數(shù)：最早截止期限（deadline），SEDF根據(jù)該時間參數(shù)決定VCPU的調(diào)度順序［6］，而且VCPU 的優(yōu)先級根據(jù)deadline 的改變而變化。SEDF 算法將調(diào)度具有最早截止時間的VCPU，從而保證虛擬機(jī)任務(wù)能及時完成。

每個域都設(shè)置一個三元組（s， p， x），時間片s 和周期時間p共同表示該域請求的CPU份額和時間，flag是一個boolean 類型的值，表示該域是否能夠占用額外的CPU 份額，三個參數(shù)時間粒度的設(shè)置對調(diào)度的公平性影響很大。VCPU 結(jié)構(gòu)體的屬性如圖1 所示，每個PCPU 包含2個雙鏈表隊(duì)列，如圖2所示。

圖1 VCPU結(jié)構(gòu)體

圖2 PCPU的雙鏈表隊(duì)列

runnableq 隊(duì)列中的VCPU 都是處于running 或runnable狀態(tài)，根據(jù)deadline參數(shù)排序，隊(duì)首的VCPU處于running 狀態(tài)，而其他VCPU 都處于runnable 狀態(tài)，必須在deadline規(guī)定時間內(nèi)執(zhí)行調(diào)度；waitq隊(duì)列中的VCPU處于runnable狀態(tài)，還未開始計(jì)時。

總之，SEDF 算法可以通過參數(shù)動態(tài)配置VCPU 的優(yōu)先級，因此在負(fù)載較大的實(shí)時系統(tǒng)中具有較高性能，當(dāng)系統(tǒng)負(fù)載較小時其CPU 使用率可以達(dá)到100%，然而，隨著負(fù)載逐漸增大，一些任務(wù)就會發(fā)生時間錯誤，錯過截止期來不及處理而夭折。另外，SEDF 算法不支持SMP 架構(gòu)，從而不能實(shí)現(xiàn)對多CPU間全局負(fù)載均衡的控制。

2.2 SMP架構(gòu)

在SMP架構(gòu)中，多個處理器共享內(nèi)存，但每個處理器都對應(yīng)一個私有cache，大多數(shù)調(diào)度算法都遵循就近原則執(zhí)行調(diào)度，也就是說首選本地CPU來執(zhí)行相應(yīng)的任務(wù)，從而提高cache 命中率。當(dāng)一個私有cache 被修改后，就要考慮內(nèi)存和cache之間的一致性問題，即不僅要確保修改后cache和相應(yīng)內(nèi)存之間的一致性，而且要確保內(nèi)存和其他cache 之間的一致性。在執(zhí)行過程中，VCPU 可能會處于掛起狀態(tài)，比如時間片到或被其他事件阻塞，此時VCPU 雖然停止執(zhí)行，但是其對應(yīng)的私有cache 中還保存著運(yùn)行時環(huán)境［7］，當(dāng)處于掛起狀態(tài)的VCPU 被再次喚醒時，使其在上次執(zhí)行過的物理CPU上繼續(xù)執(zhí)行，從而減少數(shù)據(jù)一致性產(chǎn)生，即就近調(diào)度原則。

為了提高CPU資源的利用率，就要重視cache和內(nèi)存一致性帶來的性能消耗問題。即VCPU 在PCPU 之間的頻繁調(diào)度會產(chǎn)生嚴(yán)重的cache抖動，進(jìn)而使數(shù)據(jù)一致性問題產(chǎn)生額外的性能損耗，嚴(yán)重降低CPU執(zhí)行速度［8］。

3 DLB_DEF算法的設(shè)計(jì)

通過上節(jié)中對SEDF 算法的分析可知：SEDF 在實(shí)時性環(huán)境中具有較好性能，但不支持SMP 架構(gòu)，如果一個CPU空閑，它只能等待新的VCPU任務(wù)到來，而此時其他CPU 的任務(wù)量可能已經(jīng)超載，此時SMP 架構(gòu)中的多處理器系統(tǒng)的物理性能遠(yuǎn)低于具有相同處理器個數(shù)的系統(tǒng)。基于此研究結(jié)論，本文提出一種基于SMP 架構(gòu)的虛擬機(jī)負(fù)載均衡調(diào)度算法——DLB_DEF算法。

在DLB_DEF 算法中，共享隊(duì)列shareWaitq 中的VCPU 按照deadline 參數(shù)進(jìn)行排序，且都處于runnable 狀態(tài)，如圖3所示為shareWaitq結(jié)構(gòu)體屬性：

圖3 shareWaitq結(jié)構(gòu)體

每個PCPU 具有不同的等待時間權(quán)值，即為對應(yīng)runnableq 隊(duì)列中存放的VCPU 的運(yùn)行時間總和。當(dāng)PCPU 空閑時就從共享等待隊(duì)列中調(diào)取VCPU 任務(wù)，同時，考慮到cache 就近原則，將該VCPU 任務(wù)上次執(zhí)行過的PCPU 記作pre_pcpu，改進(jìn)后CPU 和VCPU 的結(jié)構(gòu)體屬性分別如圖4和圖5所示：

圖4 改進(jìn)后的PCPU結(jié)構(gòu)體

圖5 改進(jìn)后的VCPU結(jié)構(gòu)體

假設(shè)物理機(jī)有M個可運(yùn)行的PCPU，如式（1）所示；式（2）為runnableq隊(duì)列中的所有VCPU；式（3）為所有PCPU的weight集合；式（4）為weight集合中的最小時間權(quán)值。

改進(jìn)后的動態(tài)負(fù)載均衡算法DLB_DEF與SEDF算法相同，PCPU都是優(yōu)先調(diào)用具有最早截止期限的VCPU，通過增加并實(shí)時更新共享等待隊(duì)列shareWaitq，從而實(shí)現(xiàn)動態(tài)負(fù)載均衡。DLB_DEF算法如圖6所示：

圖6 DLB_DEF算法

4 仿真實(shí)驗(yàn)與結(jié)果

4.1 仿真平臺及環(huán)境配置

Schedsim 是一種CPU 調(diào)度模擬器，提供了良好的接口，能夠?qū)崿F(xiàn)先來先服務(wù)算法、短作業(yè)優(yōu)先算法等多種常見的調(diào)度算法［9］。基于Schedsim，本文設(shè)計(jì)并實(shí)現(xiàn)了SEDF 算法和改進(jìn)后的DLB_EDF 算法，并模擬了兩種算法在不同數(shù)量處理器上的調(diào)度情況，最后對兩種算法調(diào)度的系統(tǒng)性能進(jìn)行了分析和比較。

將SEDF 和DLB_EDF 中的一個VCPU 任務(wù)記作一個進(jìn)程，由5個參數(shù)表示：進(jìn)程ID 號、優(yōu)先級、就緒時間、執(zhí)行時間和最早截止期限。為了滿足仿真實(shí)驗(yàn)的需要，假設(shè)PCPU個數(shù)最大為6，配置5個進(jìn)程池，分別包含10、20、40、60、80個進(jìn)程，仿真實(shí)驗(yàn)步驟如下：

步驟1：創(chuàng)建的進(jìn)程池至少符合以下要求：①2個就緒時間相同而最早截止期限不同的進(jìn)程，②2個就緒時間和最早截止期限都相同的進(jìn)程，③2個執(zhí)行時間不同而就緒時間和最早截止期限相同的進(jìn)程，④2個分別具有不同的就緒時間、執(zhí)行時間和最早截止期限的進(jìn)程，⑤就緒時間與執(zhí)行時間之和大于最早截止期限的2個進(jìn)程，⑥將所有進(jìn)程的最早截止期限設(shè)置為與優(yōu)先級成反比。

步驟2：進(jìn)程池中的所有進(jìn)程入隊(duì)。

步驟3：配置PCPU個數(shù)，選擇調(diào)度算法和調(diào)度模式。

步驟4：運(yùn)行模擬器。

以下實(shí)驗(yàn)結(jié)果是以包含40個VCPU的進(jìn)程池作為參考，對每個進(jìn)程池分別做10 組測試，并取10 組數(shù)據(jù)的平均值。

4.2 仿真結(jié)果分析

當(dāng)兩個算法的進(jìn)程都完成時，如圖7、圖8、圖9 分別為系統(tǒng)吞吐量、平均周轉(zhuǎn)時間和平均應(yīng)答時間的比較結(jié)果。

通過圖7-9我們可以看到，當(dāng)PCPU個數(shù)為1時，由于需要考慮cache 就近原則，因此DLB_DEF 的系統(tǒng)吞吐量和任務(wù)完成率比SEDF算法略小，但是平均周轉(zhuǎn)時間以及平均響應(yīng)時間比SEDF略大；當(dāng)PCPU個數(shù)增多，即在支持SMP 架構(gòu)的多處理系統(tǒng)中，具有負(fù)載均衡策略的DLB_DEF 算法的各個性能指標(biāo)都略超過SEDF，系統(tǒng)吞吐量和任務(wù)完成率逐漸增大，平均周轉(zhuǎn)時間以及平均響應(yīng)時間卻逐漸減小。特別地，當(dāng)DLB_DEF 和SEDF 的系統(tǒng)吞吐量具有最大差值時，PCPU個數(shù)等于4，即在PCPU為4時DLB_DEF算法具有最優(yōu)性能。當(dāng)PCPU個數(shù)繼續(xù)增大為6 時，SEDF 算法由于空閑PCPU 的出現(xiàn)而導(dǎo)致多種系統(tǒng)指標(biāo)性能降低，而此時，在DLB_DEF算法中，雖然PCPU個數(shù)增多，但由于共享等待隊(duì)列的互斥性，PCPU調(diào)用任務(wù)時等待互斥鎖的解鎖時間逐漸增大，同時，共享等待隊(duì)列的更新也要占用更多時間，因此，DLB_DEF 算法的系統(tǒng)吞吐量、任務(wù)完成率、平均周轉(zhuǎn)時間以及平均響應(yīng)時間也逐漸達(dá)到平穩(wěn)狀態(tài)。

當(dāng)PCPU個數(shù)逐漸增多時，即具有更多處理器來執(zhí)行系統(tǒng)任務(wù)時，SEDF 和改進(jìn)后的DLB_DEF 算法的任務(wù)完成數(shù)和任務(wù)完成率都逐漸增大，但是兩者的完成率都達(dá)不到100%，即有些VCPU 由于錯過截止時間而錯過執(zhí)行的機(jī)會，但是DLB_DEF 在總體上完成量比SEDF多。

圖7 系統(tǒng)吞吐量對比

圖8 平均周轉(zhuǎn)時間對比

圖9 平均應(yīng)答時間對比

圖10 完成進(jìn)程數(shù)對比

5 總結(jié)

本文主要對SEDF算法進(jìn)行分析，針對其不支持SMP架構(gòu)的不足，提出一種動態(tài)負(fù)載均衡算法DLB_DEF。該算法設(shè)計(jì)了一個共享等待隊(duì)列存儲VCPU 任務(wù)，并根據(jù)cache就近原則和PCPU的等待時間權(quán)值，VCPU可選擇最優(yōu)PCPU 執(zhí)行其任務(wù)。DLB_DEF 算法不僅可以降低cache 抖動帶來的性能損耗，還可以通過獲取PCPU 的最小等待權(quán)值來增大PCPU使用率。最后，在Schedsim仿真環(huán)境中模擬SEDF和DLB_DEF，仿真結(jié)果表明，DLB_DEF在系統(tǒng)吞吐量、平均周轉(zhuǎn)時間和應(yīng)答時間、進(jìn)程完成率等性能指標(biāo)上都略優(yōu)于SEDF 算法。目前僅在模擬環(huán)境中執(zhí)行DLB_DEF 算法，下一步任務(wù)要將DLB_DEF 嵌入到XEN源代碼中并運(yùn)行在真實(shí)虛擬環(huán)境中。

［1］懷進(jìn)鵬，李沁，胡春明. 基于虛擬機(jī)的虛擬計(jì)算環(huán)境的研究與發(fā)展［J］. 軟件學(xué)報(bào)，2007，18（8）：1016-1026.

［2］ Paul Barham，Ian Pratt，Keir Fraser，et al，“Xen and the art of virtualization，”In SOSP’03:Proc of the nineteenth ACM symposium on Operating systems principles，New York，ACM，2003，15：164-177.

［3］金海，吳松，石宣化，等. 一種虛擬CPU 調(diào)度方法［P］.中國專利，102053858，2011-05-11.

［4］ Huacai Chen，Hai Jin，Kan Hu，et al.“Adaptive audio-aware scheduling in Xen virtual environment，”In AICCSA’10: Proc of the ACS/IEEE International Conference on Computer Systems and Applications. USA， IEEE Computer Society Washington，2010：1-8.

［5］Hyunsik Choi，Saeyoung Han，Sungyong Park and Eunji Yang，“A CPU Provision Scheme Considering Virtual Machine Scheduling Delays in Xen Virtualized Environment，”TENCON’09:2009 IEEE Region 10 Conference.2009：1-6.

［6］Xinjie Zhang，Dongsheng Yin，“Real-time Improvement of VCPU Scheduling Algorithm on Xen，”In CSSS’11: Computer Science and Service System.2011：1506-1509.

［7］常建忠，劉曉建.虛擬機(jī)協(xié)同調(diào)度問題研究. 計(jì)算機(jī)工程與應(yīng)用，2011，47（6）：38-41.

［8］ Min Lee， A.S.Krishnakumar， P.Krishnan et al.“Supporting Soft Real-Time Tasks in the Xen Hypervisor，”In VEE '10: Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments［J］.New York，ACM，2010，45：97-108.

［9］姚文斌，鄭興杰.一種改進(jìn)的SEDF 算法［J］.小型微型計(jì)算機(jī)系統(tǒng).2010，31（3）：446-450.