萬成威，王 霞，王 猛

(北京航天飛行控制中心，北京 100094)

0 引 言

虛擬化云計(jì)算平臺可實(shí)現(xiàn)不同云租戶相對獨(dú)立地共享底層基礎(chǔ)資源，在有效滿足多樣化應(yīng)用需求的同時,實(shí)現(xiàn)了底層服務(wù)器的CPU、內(nèi)存、硬盤等資源的高效利用、靈活分配以及統(tǒng)一管理[1-2]。因此，虛擬化云平臺已日漸成為各類業(yè)務(wù)系統(tǒng)運(yùn)行的基礎(chǔ)支撐環(huán)境[3]。為實(shí)現(xiàn)物理資源被多個虛擬機(jī)調(diào)用，無論軟件模擬虛擬化，還是硬件輔助虛擬化，均需虛擬機(jī)監(jiān)控器的參與，實(shí)現(xiàn)物理設(shè)備與上層多個虛擬機(jī)之間的抽象與適配。虛擬機(jī)操作系統(tǒng)管理和訪問的系統(tǒng)資源，如虛擬CPU、虛擬內(nèi)存、虛擬IO等，只有在虛擬CPU被調(diào)度至物理CPU時，虛擬機(jī)操作系統(tǒng)中的各個進(jìn)程才可以運(yùn)行[4]。因此，虛擬CPU調(diào)度算法直接影響著虛擬機(jī)的性能。虛擬CPU調(diào)度包含虛擬機(jī)之間的CPU調(diào)度和虛擬機(jī)內(nèi)部CPU調(diào)度。這些虛擬CPU調(diào)度算法中，準(zhǔn)確的CPU資源預(yù)測是保證算法有效性的重要前提。從系統(tǒng)層面看，云服務(wù)器提供商需盡可能根據(jù)虛擬機(jī)承載的業(yè)務(wù)需求動態(tài)分配或遷移虛擬機(jī)，以避免分配過多的資源形成浪費(fèi)，或者因分配資源不足而影響業(yè)務(wù)運(yùn)行[5-8]；從虛擬機(jī)操作系統(tǒng)本身看，大量的虛擬機(jī)同時運(yùn)行著計(jì)算密集型業(yè)務(wù)和IO密集型業(yè)務(wù)，兩類業(yè)務(wù)的資源分配策略直接影響著虛擬機(jī)操作系統(tǒng)的綜合服務(wù)性能[4,9]。因此,準(zhǔn)確的資源需求預(yù)測是保證云平臺資源調(diào)度算法有效性的重要前提，其中CPU資源預(yù)測是云平臺各類資源中的核心指標(biāo)。已有研究表明，在大時間尺度上，大型分布式系統(tǒng)中的CPU負(fù)載具有明顯的自相關(guān)性、周期性等[9]，故通過長期的云平臺負(fù)載數(shù)據(jù)積累，使用各種數(shù)據(jù)挖掘算法，可以準(zhǔn)確地預(yù)測云平臺CPU資源的變化特性，對云平臺資源的整體規(guī)劃有著重要意義。然而，在小時間尺度上，各服務(wù)器或虛擬機(jī)的負(fù)載變化仍具有較強(qiáng)的隨機(jī)性，這也為云平臺虛擬機(jī)實(shí)時遷移或虛擬CPU資源實(shí)時分配帶來了挑戰(zhàn)。尤其在虛擬機(jī)操作系統(tǒng)環(huán)境下，可用CPU資源相對有限，且操作系統(tǒng)CPU調(diào)度具有很強(qiáng)的實(shí)時性，這就要求CPU預(yù)測及調(diào)度算法盡可能簡單，且占用較小的計(jì)算、存儲等資源。

考慮到虛擬機(jī)操作系統(tǒng)應(yīng)用場景多樣性所引入的隨機(jī)性，本文以適用虛擬機(jī)操作系統(tǒng)環(huán)境的CPU預(yù)測方法為研究對象，詳細(xì)評估了各種虛擬CPU資源預(yù)測算法的準(zhǔn)確性以及算法性能隨各關(guān)鍵參數(shù)的變化情況，為虛擬機(jī)操作系統(tǒng)的CPU資源調(diào)度策略設(shè)計(jì)與實(shí)現(xiàn)提供了研究基礎(chǔ)。

1 CPU負(fù)載預(yù)測算法性能評估

大型云平臺可以部署專用的云平臺管理系統(tǒng)，采用負(fù)載的CPU負(fù)載預(yù)測算法，并根據(jù)定義的效益最大化原則，調(diào)整云平臺資源的分配策略[10]。然而，對虛擬機(jī)操作系統(tǒng)而言，CPU負(fù)載預(yù)測算法需盡可能簡單、高效，占用盡可能少的計(jì)算、存儲等資源，不會引入較大的性能損耗和預(yù)測時延，便于實(shí)現(xiàn)CPU資源的快速、準(zhǔn)確調(diào)整。本文選取了五種常見的時間序列預(yù)測算法，以CPU負(fù)載數(shù)據(jù)為研究對象，詳細(xì)比較其在CPU負(fù)載預(yù)測方面的應(yīng)用性能。

1.1 CPU負(fù)載數(shù)據(jù)

本文采用CloudSim[11]平臺中resource/workload/20110420目錄下的CPU負(fù)載數(shù)據(jù)作為研究對象，該CPU負(fù)載為PlanetLab平臺上虛擬機(jī)真實(shí)的CPU負(fù)載測試數(shù)據(jù)集，可作為不同研究場景下的基準(zhǔn)測試數(shù)據(jù)集。該目錄下共包含1 054個CPU負(fù)載樣本序列。本文采取無監(jiān)督機(jī)器學(xué)習(xí)算法支持向量機(jī)(Support Vector Machine，SVM)將上述樣本分為三類(高CPU負(fù)載序列78個，低CPU負(fù)載序列639個，混合型負(fù)載序列337個)，以考察不同時間序列預(yù)測算法性能與不同CPU負(fù)載類型之間的關(guān)系。

1.2 時間序列預(yù)測算法

本文主要研究適用于虛擬機(jī)操作系統(tǒng)CPU調(diào)度的負(fù)載預(yù)測算法，算法需計(jì)算量小、占用存儲空間小。為此，本文主要考察簡單時間序列預(yù)測算法的性能，包括移動平均法[12]、加權(quán)平均法[13]、一次指數(shù)平滑法[14]、二次指數(shù)平滑法[14]、差分指數(shù)平滑法[15]等。

令各CPU負(fù)載樣本為時間序列X1，X2，…，XT，對于下列各算法進(jìn)行時間序列預(yù)測。

(1)平均移動法

給定移動項(xiàng)數(shù)N，時間序列預(yù)測值為

(1)

(2)加權(quán)平均移動法

給定移動項(xiàng)數(shù)N及權(quán)重系數(shù)w1，w2，…，wN，時間序列預(yù)測值為

(2)

w1+w2+…+wN=1。

(3)

(3)一次指數(shù)平滑法

給定加權(quán)系數(shù)α(0<α<1)，時間序列預(yù)測值

(4)

(4)二次指數(shù)平滑法

針對一次指數(shù)平滑法的預(yù)測結(jié)果進(jìn)一步指數(shù)平滑，得到的結(jié)果作為時間序列預(yù)測值，具體如下：

(5)

(6)

(7)

(8)

(9)

(5)差分指數(shù)平滑法

對一階差分值進(jìn)行指數(shù)平滑，將得到的結(jié)果作為時間序列預(yù)測值，具體如下：

ΔXt=Xt-Xt-1，

(10)

(11)

(12)

為準(zhǔn)確評估上述各算法的預(yù)測性能，定義預(yù)測標(biāo)準(zhǔn)誤差如下:

(13)

標(biāo)準(zhǔn)誤差值越小,算法預(yù)測性能越優(yōu)。

1.3 虛擬CPU負(fù)載預(yù)測算法性能評估

將上述各時間序列預(yù)測算法應(yīng)用于1.1節(jié)所述各CPU負(fù)載序列，完成CPU負(fù)載預(yù)測性能評估。因CPU負(fù)載變化復(fù)雜，具有較大的隨機(jī)性，且不同時間序列預(yù)測算法的參數(shù)差異，均會導(dǎo)致標(biāo)準(zhǔn)誤差的計(jì)算結(jié)果發(fā)生變化，為此，定義各時間序列預(yù)測誤差均值如下：

(14)

式中：Si為相同參數(shù)設(shè)置時N個不同CPU時間序列的預(yù)測標(biāo)準(zhǔn)誤差。

不同算法條件下，三類CPU負(fù)載序列預(yù)測性能結(jié)果如圖1所示。

(a)平均移動法

由圖1可見，三類CPU負(fù)載序列的平均誤差具有明顯的差異，隨CPU負(fù)載升高而依次增大。受CPU負(fù)載的隨機(jī)性變化影響，在高CPU負(fù)載條件下，各算法預(yù)測的絕對誤差也相對較大，從而產(chǎn)生更大的平均預(yù)測誤差。

平均移動法、加權(quán)平均移動法等主要受移動項(xiàng)數(shù)影響，本文分別考察了兩者平均預(yù)測誤差隨移動項(xiàng)數(shù)的變化情況，分別如圖1(a)、(b)、(c)所示，其中加權(quán)平均移動法還受權(quán)重系數(shù)影響，一般而言，距當(dāng)前時刻越近，與當(dāng)前CPU負(fù)載的相關(guān)性越強(qiáng)，應(yīng)賦予更高的權(quán)重。為簡化處理，本文分別采用指數(shù)遞減和線性遞減方式確定權(quán)重系數(shù)。指數(shù)遞減方式下，當(dāng)前時刻前的N個時刻，負(fù)載權(quán)重依次為2N-1/(2N-1)，2N-2/(2N-1)，…，1/(2N-1)；線性遞減方式下，當(dāng)前時刻前的N個時刻，負(fù)載權(quán)重依次為[1+2(N-1)]/N2，[1+2(N-2)]/N2，…，1?？梢钥吹剑S移動項(xiàng)數(shù)逐漸增大，平均移動算法和加權(quán)平均移動算法的平均預(yù)測誤差均顯著下降；隨后，除低CPU負(fù)載序列外，其他序列的預(yù)測性能均存在不同程度的性能下降。另外，對于加權(quán)平均移動法而言，權(quán)重系數(shù)線性遞減方式整體性能明顯優(yōu)于指數(shù)遞減方式，僅在移動項(xiàng)數(shù)小于4時指數(shù)遞減方式性能更優(yōu)，但在移動項(xiàng)數(shù)為12時上述各種CPU負(fù)載類型及權(quán)重模式下，平均預(yù)測誤差均可到達(dá)最小值。

一次指數(shù)平滑法、二次指數(shù)平滑法、差分指數(shù)平滑法等預(yù)測性能主要受加權(quán)系數(shù)α及預(yù)測序列初值影響。本文采用實(shí)際CPU負(fù)載作為各指數(shù)平滑法的預(yù)測序列初值，在此條件下詳細(xì)考察其平均預(yù)測誤差隨加權(quán)系數(shù)的變化關(guān)系，如圖1(d)、(e)、(f)所示。一次指數(shù)平滑法中，三類CPU負(fù)載序列的平均預(yù)測誤差均隨加權(quán)系數(shù)先遞減，在加權(quán)系數(shù)為0.1時，平均預(yù)測誤差達(dá)到最小，隨后平均預(yù)測誤差逐漸升高，甚至高于前期誤差高值；而二次指數(shù)平滑法和差分指數(shù)平滑法中，三類CPU負(fù)載的平均預(yù)測誤差均隨加權(quán)系數(shù)增加而逐漸增大，且增大的速率明顯大于一次指數(shù)平滑法。這是因?yàn)槎沃笖?shù)平滑法和差分指數(shù)平滑法主要為適應(yīng)線性時間序列而進(jìn)行了修正處理，但實(shí)際CPU負(fù)載序列仍具有較大的隨機(jī)動態(tài)變化，從而產(chǎn)生較大的預(yù)測誤差。

綜上各CPU負(fù)載預(yù)測算法性能評估結(jié)果可以看到，平均移動法、線性遞減加權(quán)平均移動法、一次指數(shù)平滑法具有較好的CPU負(fù)載預(yù)測性能。為此，本文進(jìn)一步采用最優(yōu)的參數(shù)設(shè)置，詳細(xì)比較了這三種算法的預(yù)測誤差，結(jié)果如圖2所示。

圖2 最優(yōu)設(shè)置下的預(yù)測誤差

可以看到，最優(yōu)參數(shù)設(shè)置條件下，三類算法的預(yù)測誤差基本相同，整體上，一次指數(shù)平滑算法性能最優(yōu)，平均移動法次之，加權(quán)平均移動法誤差最大。平均移動法是一種特殊的加權(quán)平均移動法，相當(dāng)于所有權(quán)重系數(shù)完全相同，形成了類似最佳接收機(jī)的效果，但仍存在某些特殊情況，如圖2低CPU負(fù)載中的第11個序列(見圖3)、高CPU負(fù)載中的第49個序列(見圖4)。圖3中整個序列中基本保持低負(fù)載，僅存在幾個連續(xù)的高CPU樣本；圖4中高CPU負(fù)載序列垂直變化為低CPU負(fù)載序列。在上述情況下，加權(quán)平均移動法性能反而最優(yōu)，而平均移動法、一次指數(shù)平滑法等由于滯后作用影響，并不能較好地適應(yīng)這種迅速變化，導(dǎo)致預(yù)測性能較差。

圖3 低CPU負(fù)載序列樣本

圖4 高CPU負(fù)載序列樣本

1.4 一次指數(shù)平滑法的改進(jìn)

一次指數(shù)平滑法計(jì)算簡單，需要存儲的狀態(tài)參數(shù)及歷史負(fù)載信息較少，且預(yù)測效果好，被廣泛應(yīng)用于時間序列預(yù)測領(lǐng)域。實(shí)際上，一次指數(shù)平滑法是對全部歷史信息的加權(quán)平均，加權(quán)系數(shù)分別為α、α(1-α)、α(1-α)2……為適應(yīng)CPU負(fù)載快速變化的情況，本文基于反饋控制思想對一次指數(shù)平滑法進(jìn)行了改進(jìn)，即當(dāng)t時刻的CPU負(fù)載預(yù)測值與實(shí)際值Xt之間的差值滿足

(15)

時對一次平滑法參數(shù)進(jìn)行調(diào)整?？紤]正常業(yè)務(wù)運(yùn)行時，均會引起CPU負(fù)載升高，而一次指數(shù)平滑法得到的預(yù)測序列為CPU負(fù)載的加權(quán)平均，故當(dāng)CPU負(fù)載預(yù)測值與實(shí)際值滿足上述條件時，進(jìn)一步降低加權(quán)系數(shù)α，以避免預(yù)測序列劇烈波動，且與實(shí)際負(fù)載序列滯后，形成更大的預(yù)測誤差。本文進(jìn)行上述改進(jìn)后，采用三類CPU負(fù)載序列進(jìn)行了驗(yàn)證，結(jié)果如圖5所示。可以看到，在CPU負(fù)載預(yù)測值與實(shí)際值p大于0.5時，調(diào)整權(quán)重系數(shù)α至0.05，可明顯降低CPU負(fù)載、混合CPU負(fù)載的預(yù)測誤差，而且改進(jìn)后的一次指數(shù)平滑法的預(yù)測誤差隨權(quán)重系數(shù)增加上升得更為緩慢。

圖5 改進(jìn)的一次指數(shù)平滑法效果

2 結(jié)束語

準(zhǔn)確的虛擬機(jī)操作系統(tǒng)CPU負(fù)載預(yù)測是實(shí)現(xiàn)虛擬化平臺資源高效利用的基礎(chǔ)。虛擬機(jī)操作系統(tǒng)環(huán)境下，可用的計(jì)算資源、存儲空間等較為有限，CPU負(fù)載預(yù)測算法應(yīng)盡可能簡單、高效。本文基于實(shí)際的CPU負(fù)載數(shù)據(jù)，以常用的時間序列分析方法作為研究對象，詳細(xì)評估了各方法在虛擬CPU負(fù)載預(yù)測領(lǐng)域的應(yīng)用性能，結(jié)果表明，平均移動法、線性遞減加權(quán)平均移動法、一次指數(shù)平滑法計(jì)算方法簡單，所用存儲空間極小，且具有較好的CPU負(fù)載預(yù)測性能。在此基礎(chǔ)上，結(jié)合反饋控制思想，對一次指數(shù)平滑法進(jìn)行了改進(jìn)，進(jìn)一步提高了其CPU負(fù)載預(yù)測性能。

后續(xù)工作主要包含以下兩個方面：一是針對改進(jìn)的一次指數(shù)平滑法，進(jìn)一步詳細(xì)評估不同條件下參數(shù)p對算法性能的影響；二是將上述方法在各虛擬化平臺中實(shí)現(xiàn)，并在實(shí)際過程中檢驗(yàn)其應(yīng)用性能。