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

朱建宇

1 引言

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

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

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

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

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

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

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

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

2.1 云計算

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

2.2 虛擬化技術(shù)

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

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

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

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

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

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

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

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

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

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

3.3 改進遺傳算法操作過程

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

（1）選擇

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

（2）交叉

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

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

（3）變異

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

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

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

4 總結(jié)

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