一種虛擬機(jī)負(fù)載均衡調(diào)度算法

張 瑩 李 華

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

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

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

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

本文提出了一種SMP（對(duì)稱(chēng)多處理器）系統(tǒng)中的動(dòng)態(tài)負(fù)載均衡調(diào)度算法—?jiǎng)討B(tài)最早截止時(shí)間優(yōu)先算法（DLB_DEF）來(lái)提高物理CPU 利用率，從而減少空閑CPU。為了實(shí)現(xiàn)該算法，我們?cè)O(shè)計(jì)了一種共享等待隊(duì)列，考慮到多處理器環(huán)境中cache和內(nèi)存的同步關(guān)系，使虛擬CPU在執(zhí)行完任務(wù)之前都在同一個(gè)物理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)境中，多個(gè)虛擬機(jī)通過(guò)分時(shí)調(diào)度策略共享物理處理器資源，每個(gè)虛擬機(jī)就是一個(gè)域，每個(gè)域?qū)?yīng)一個(gè)或多個(gè)虛擬CPU（VCPU）［5］。因此，如何公平高效地將物理CPU 資源分配給多個(gè)虛擬機(jī)，并使CPU 有效利用率達(dá)到合理范圍就是一個(gè)問(wèn)題。

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

每個(gè)域都設(shè)置一個(gè)三元組（s， p， x），時(shí)間片s 和周期時(shí)間p共同表示該域請(qǐng)求的CPU份額和時(shí)間，flag是一個(gè)boolean 類(lèi)型的值，表示該域是否能夠占用額外的CPU 份額，三個(gè)參數(shù)時(shí)間粒度的設(shè)置對(duì)調(diào)度的公平性影響很大。VCPU 結(jié)構(gòu)體的屬性如圖1 所示，每個(gè)PCPU 包含2個(gè)雙鏈表隊(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ī)定時(shí)間內(nèi)執(zhí)行調(diào)度；waitq隊(duì)列中的VCPU處于runnable狀態(tài)，還未開(kāi)始計(jì)時(shí)。

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

2.2 SMP架構(gòu)

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

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

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

通過(guò)上節(jié)中對(duì)SEDF 算法的分析可知：SEDF 在實(shí)時(shí)性環(huán)境中具有較好性能，但不支持SMP 架構(gòu)，如果一個(gè)CPU空閑，它只能等待新的VCPU任務(wù)到來(lái)，而此時(shí)其他CPU 的任務(wù)量可能已經(jīng)超載，此時(shí)SMP 架構(gòu)中的多處理器系統(tǒng)的物理性能遠(yuǎn)低于具有相同處理器個(gè)數(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)體

每個(gè)PCPU 具有不同的等待時(shí)間權(quán)值，即為對(duì)應(yīng)runnableq 隊(duì)列中存放的VCPU 的運(yùn)行時(shí)間總和。當(dāng)PCPU 空閑時(shí)就從共享等待隊(duì)列中調(diào)取VCPU 任務(wù)，同時(shí)，考慮到cache 就近原則，將該VCPU 任務(wù)上次執(zhí)行過(guò)的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個(gè)可運(yùn)行的PCPU，如式（1）所示；式（2）為runnableq隊(duì)列中的所有VCPU；式（3）為所有PCPU的weight集合；式（4）為weight集合中的最小時(shí)間權(quán)值。

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

圖6 DLB_DEF算法

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

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

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

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

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

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

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

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

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

4.2 仿真結(jié)果分析

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

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

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

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

圖8 平均周轉(zhuǎn)時(shí)間對(duì)比

圖9 平均應(yīng)答時(shí)間對(duì)比

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

5 總結(jié)

本文主要對(duì)SEDF算法進(jìn)行分析，針對(duì)其不支持SMP架構(gòu)的不足，提出一種動(dòng)態(tài)負(fù)載均衡算法DLB_DEF。該算法設(shè)計(jì)了一個(gè)共享等待隊(duì)列存儲(chǔ)VCPU 任務(wù)，并根據(jù)cache就近原則和PCPU的等待時(shí)間權(quán)值，VCPU可選擇最優(yōu)PCPU 執(zhí)行其任務(wù)。DLB_DEF 算法不僅可以降低cache 抖動(dòng)帶來(lái)的性能損耗，還可以通過(guò)獲取PCPU 的最小等待權(quán)值來(lái)增大PCPU使用率。最后，在Schedsim仿真環(huán)境中模擬SEDF和DLB_DEF，仿真結(jié)果表明，DLB_DEF在系統(tǒng)吞吐量、平均周轉(zhuǎn)時(shí)間和應(yīng)答時(shí)間、進(jìn)程完成率等性能指標(biāo)上都略?xún)?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］.中國(guó)專(zhuān)利，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)度問(wèn)題研究. 計(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.