基于OpenStack云計(jì)算的資源調(diào)度算法研究

朱建宇

1 引言

隨著計(jì)算機(jī)的快速發(fā)展和廣泛使用，計(jì)算機(jī)數(shù)據(jù)變得越來越復(fù)雜，規(guī)模越來越龐大。

為了處理大規(guī)模的數(shù)據(jù)和應(yīng)用，計(jì)算機(jī)數(shù)據(jù)做出各種正確的行為指導(dǎo)，云計(jì)算應(yīng)運(yùn)而生。云計(jì)算是一種在分布式計(jì)算，并行計(jì)算，網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展形成的一種計(jì)算模式。目前，從國內(nèi)國外的研究現(xiàn)狀來看，谷歌、微軟、亞馬遜、IBM等巨型IT公司紛紛在全球建立數(shù)據(jù)中心，研發(fā)和應(yīng)用云計(jì)算，并形成了相對成熟穩(wěn)定的云計(jì)算平臺(tái)。同時(shí)，均將云計(jì)算作為發(fā)展的重要戰(zhàn)略之一[1]。同樣，諸如Facebook，蘋果等其他大型公司及部分中小型企業(yè)也開始加大對云計(jì)算的投資力度，實(shí)現(xiàn)云計(jì)算的各領(lǐng)域的落地服務(wù)。在國內(nèi)，以阿里云為首，騰訊云，華為云，百度云等幾十家互聯(lián)網(wǎng)企業(yè)。都對云計(jì)算進(jìn)行了巨額投資和研發(fā)，并實(shí)現(xiàn)了初步的商用目的。國內(nèi)的大型央企，國企，政府機(jī)構(gòu)，都已經(jīng)建立了各自的云計(jì)算平臺(tái)，為自己的單位建立了相對完善的私有云平臺(tái)。

云計(jì)算利用了虛擬化技術(shù)將物理資源虛擬成為軟件資源，形成了多種資源池，這樣可以提供按需交付、靈活彈性、集中規(guī)模、自由調(diào)度、安全管理等多種功能。適應(yīng)了當(dāng)代企業(yè)和用戶對大規(guī)模數(shù)據(jù)計(jì)算，復(fù)雜邏輯處理的迫切要求。由于很多科學(xué)研究、項(xiàng)目需求對云計(jì)算的資源有各種各樣的要求，包括計(jì)算資源，網(wǎng)絡(luò)資源，存儲(chǔ)資源。研究高效靈活的云計(jì)算相關(guān)技術(shù)任重道遠(yuǎn)，滿足各種使用需求具有非常重要的價(jià)值和意義。

OpenStack是IaaS的重要組件，OpenStack的作用是創(chuàng)建虛擬機(jī)需要各種服務(wù)的交互和配合工作。OpenStack支持幾乎所有類型的云環(huán)境，項(xiàng)目目標(biāo)是提供實(shí)施簡單、可大規(guī)模擴(kuò)展、豐富、標(biāo)準(zhǔn)統(tǒng)一的云計(jì)算管理平臺(tái)。OpenStack通過各種互補(bǔ)的服務(wù)提供了基礎(chǔ)設(shè)施即服務(wù)的解決方案，每個(gè)服務(wù)提供API以進(jìn)行集成。目前OpenStack開發(fā)速度非?？?，社區(qū)也很活躍，國內(nèi)外的很多企業(yè)、研究機(jī)構(gòu)、學(xué)校、組織都踴躍參與和貢獻(xiàn)OpenStack的開發(fā)和修復(fù)工作，發(fā)展非常順利。

用戶在使用云計(jì)算服務(wù)的過程中，更為關(guān)注可靠性、效率、成本?；谏鲜鲋笜?biāo)提出QoS(quality of service)服務(wù)質(zhì)量。為了最大程度滿足QoS的需求，提高用戶滿意度，云計(jì)算需要在資源分配環(huán)節(jié)從用戶角度考慮，實(shí)現(xiàn)資源調(diào)度的合理化、自由化、準(zhǔn)確化。因此，資源調(diào)度和資源方向是云計(jì)算的重要研究方向。

為了保障QoS，提高資源利用率，必須解決好云計(jì)算中的資源調(diào)度問題，隨著仿生學(xué)的發(fā)展，人們開始關(guān)注遺傳算法，并將遺傳算法應(yīng)用到云計(jì)算當(dāng)中，提高了資源調(diào)度的智能性。

但是，傳統(tǒng)的遺傳算法具有局部收斂的問題。只能得到局部最優(yōu)解，因此，針對上述問題，本文提出基于OpenStack云計(jì)算的資源調(diào)度改進(jìn)遺傳算法，提高了可靠性，滿足了資源利用最大化，更好的發(fā)揮了遺傳算法的智能性作用。

2 OpenStack云計(jì)算理論基礎(chǔ)及傳統(tǒng)調(diào)度算法

2.1 云計(jì)算

云計(jì)算是一種可以提供按需收費(fèi)，能夠彈性伸縮的一種新型的計(jì)算模式。正所謂彈性可伸縮，即資源分配和部署可以根據(jù)用戶的需求時(shí)時(shí)的改動(dòng)。云計(jì)算的這種資源使用模式，為用戶通過網(wǎng)絡(luò)提供訪問計(jì)算資源的可能。比如存儲(chǔ)，應(yīng)用服務(wù)，軟件程序等。從用戶角度來講，云計(jì)算有以下特征：（1）按需服務(wù)，云計(jì)算可以為用戶快速提供可用資源可用服務(wù)，并且能夠根據(jù)用戶的需求對資源進(jìn)行使用，釋放，這樣，云服務(wù)商可以根據(jù)用戶需求調(diào)度各種云資源；（2）資源池，云計(jì)算通過虛擬化技術(shù)將存入資源進(jìn)行虛擬并組成資源池，讓多個(gè)用戶根據(jù)需求共同利用資源池中的資源[2]；（3）彈性伸縮，云服務(wù)商可以根據(jù)用戶的需求,快速的，彈性的分配，釋放，回收資源，這對于用戶而言，代表資源是無限的，任何需求都能夠及時(shí)得到滿足；（4）按需付費(fèi)，按需服務(wù)的基本眼球要求按需付費(fèi)，云計(jì)算商按照用戶是使用的資源進(jìn)行按量計(jì)費(fèi)，滿足了用戶的需求，當(dāng)然，這些資源也是虛擬抽象出來的資源，比如CPU，內(nèi)存，硬盤，帶寬等。

2.2 虛擬化技術(shù)

虛擬化技術(shù)是云計(jì)算IaaS層核心組成部分，虛擬化也可以理解為對物理資源的抽象化。其本質(zhì)是隔離了軟件和硬件的一種中間件技術(shù)，將物理底層進(jìn)行屏蔽，并為上層提供統(tǒng)一的接口服務(wù)。虛擬化的對象可以劃分為服務(wù)器的虛擬化，網(wǎng)絡(luò)的虛擬化，存儲(chǔ)的虛擬化等多種不同形式。本文的資源調(diào)度主要針對的是服務(wù)器的虛擬化。服務(wù)器虛擬化是把一臺(tái)服務(wù)器抽象成為多臺(tái)服務(wù)器，這樣一臺(tái)物理主機(jī)就可以變成多臺(tái)虛擬機(jī)，并且多臺(tái)虛擬機(jī)是互相獨(dú)立的，是完全隔離的。這樣保證了虛擬機(jī)的安全性與可靠性。服務(wù)器虛擬化主要是將物理的CPU，內(nèi)存，硬盤，網(wǎng)絡(luò)設(shè)備，I/O接口等資源進(jìn)行抽象。其中CPU虛擬化會(huì)將物理的CPU虛化成多個(gè)虛擬的CPU。這樣，多個(gè)虛擬的CPU可以提高物理CPU的利用率。內(nèi)存虛擬化將物理內(nèi)存抽象成多個(gè)虛擬內(nèi)存，內(nèi)存空間完全隔離;網(wǎng)絡(luò)設(shè)備和I/O接口虛擬化，就是將真實(shí)的物理設(shè)備抽象為多個(gè)虛擬設(shè)備，為多臺(tái)虛擬機(jī)進(jìn)行I/O請求，提供服務(wù)[3]。

目前，較為流行的虛擬化管理軟件有KVM，Xen，vSphere，本文研究的OpenStack云計(jì)算對KVM提供很好的支持。KVM是基于Linux內(nèi)核對虛擬機(jī)進(jìn)行管理的，所以它要求底層硬件必須都支持虛擬化。

2.3 傳統(tǒng)遺傳算法

遺傳算法按照自然界的生存法則，將具體問題抽象化，把需要解決的問題虛擬成為染色體，接著把這些染色體進(jìn)行選擇，交叉和變異，直到得到目標(biāo)最優(yōu)解[4]。具體的算法過程按照以下描述，隨機(jī)產(chǎn)生初始化種群后，通過不斷地的選擇，交叉，變異來優(yōu)化，調(diào)度，擴(kuò)大下一代種群搜索空間。并利用適應(yīng)度函數(shù)對已經(jīng)編碼的種群進(jìn)行優(yōu)勝劣汰，留下適應(yīng)度較高的個(gè)體，淘汰掉適應(yīng)度較低的個(gè)體。篩選完個(gè)體之后，由新的個(gè)體產(chǎn)生新的種群。

3 改進(jìn)資源調(diào)度遺傳算法

3.1 改進(jìn)資源調(diào)度遺傳算法

傳統(tǒng)的遺傳算法，采用0，1的編碼方式對染色體完成編碼，但是資源調(diào)度的問題是有不同的分配方案的，需要明確每一個(gè)任務(wù)在每一個(gè)資源節(jié)點(diǎn)執(zhí)行，傳統(tǒng)的編碼方式不能覆蓋全部信息。本文采用一種間接編碼方式，規(guī)定任務(wù)的數(shù)量就是染色體的長度。染色體的每一位表示一個(gè)任務(wù)，對應(yīng)一個(gè)資源。比如染色體（3，5，2，6，8，7）表示染色體長度是6，需要執(zhí)行6個(gè)任務(wù)，第一個(gè)任務(wù)被分配到節(jié)點(diǎn)3，第二個(gè)任務(wù)被分配到節(jié)點(diǎn)5，以此類推。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)表示個(gè)體被度量的函數(shù)，用來計(jì)算個(gè)體被選中的概率。適應(yīng)度越大，個(gè)體越好，被選中概率越大，保證特性得到遺傳。適應(yīng)度函數(shù)的選擇能夠決定是否可以得到最優(yōu)解，所以選擇合適的是適應(yīng)度函數(shù)非常重要。

滿足用戶QoS的需求有四個(gè)指標(biāo)，分別是時(shí)間、可用性、成本、安全性。這四項(xiàng)指標(biāo)能夠滿足用戶的需求，決定最優(yōu)解。目標(biāo)函數(shù)值越大，代表優(yōu)化效果越好，也代表算法性能高。因此本文選用目標(biāo)函數(shù)的平方當(dāng)做適應(yīng)度函數(shù)。QoS四項(xiàng)指標(biāo)按照權(quán)重系數(shù)來影響適應(yīng)度函數(shù)。權(quán)重系數(shù)由資源的剛性和彈性偏好決定。也可以根據(jù)用戶自身需求進(jìn)行調(diào)節(jié)。

3.3 改進(jìn)遺傳算法操作過程

遺傳算法主要有三部分組成，選擇，交叉，變異。這三個(gè)部分直接影響到遺傳操作的效果。

（1）選擇

選擇是為了通過對當(dāng)代種群的篩選，利用適應(yīng)度函數(shù)對個(gè)體進(jìn)行評價(jià)，完成對種群的不斷優(yōu)化。因?yàn)檫m應(yīng)度函數(shù)的大小決定了個(gè)體被篩選的概率，所以可以將優(yōu)良的個(gè)體通過評價(jià)篩選后遺傳到下一代。本文采用的選擇方法是賭輪選擇法。當(dāng)個(gè)體的適應(yīng)度值比較大的時(shí)候，被選擇的可能性也越大。

（2）交叉

交叉算子可以使我們的搜索空間擴(kuò)大，是遺傳算法中的基因重組，具有核心作用[5]。交叉是指兩個(gè)父體結(jié)構(gòu)進(jìn)行替換，重新生成兩個(gè)新個(gè)體。交叉概率的選取非常重要，取值偏大會(huì)導(dǎo)致良好的結(jié)構(gòu)被破壞，取值偏小會(huì)影響個(gè)體的產(chǎn)生速度。本文設(shè)施了一種自適應(yīng)方式，避免交叉概率偏大或者偏小。調(diào)整公式1如下：

favg代表種群的品均適應(yīng)度，fmax代表種群最大的適應(yīng)度，f代表交叉雙方適應(yīng)值比較大的一方。k1和k2在（0，1）之間取值，從公式中可以看出，個(gè)體適應(yīng)度值接近最大適應(yīng)度值的時(shí)候，交叉概率就小，而當(dāng)適應(yīng)度值和最大適應(yīng)讀值相等的時(shí)候，交叉概率等于0。

（3）變異

變異可以為算法找到最優(yōu)解提供條件，可以豐富種群的多樣性。變異操作可以使算法向著最優(yōu)解的方向收斂。并且保持多樣性，變異概率設(shè)置太大，不會(huì)加速尋找最優(yōu)解，反而會(huì)破壞變異基因位。本文設(shè)計(jì)了一種自適應(yīng)的方式選取變異概率。調(diào)整公式2如下：

其中，favg代表種群的品均適應(yīng)，fmax代表種群最大的適應(yīng)度，代表變異雙方適應(yīng)值比較大的一方。k3和k4在（0，1）之間取值。從公式中可以看出，當(dāng)變異個(gè)體的適應(yīng)值接近最大的適應(yīng)值的時(shí)候，變異概率就小，而適應(yīng)度值與最大適應(yīng)讀值相同的時(shí)候，變異概率等于0。

綜上所述，本文的交叉算法有更強(qiáng)的全局搜索能力，而本文的變異算法可以提高局部的搜索能力。通過選擇交叉變異三種操作，遺傳算法可以擴(kuò)大全局搜索范圍，提高局部搜索能力，使得問題可以加速并保證精準(zhǔn)的尋求和接近最優(yōu)解。

4 總結(jié)

本文研究了云計(jì)算，OpenStack的基本原理和核心技術(shù)，對傳統(tǒng)的遺傳算法進(jìn)行了深入學(xué)習(xí)和實(shí)驗(yàn)。提出了一套可以改進(jìn)資源調(diào)度效果的遺傳算法，能夠?qū)崿F(xiàn)在滿足QoS的情況下，降低成本，提高資源利用率。