祝衍軍

(東莞職業(yè)技術(shù)學院 計算機工程系,廣東 東莞　523808)

虛擬機簇的雙目標優(yōu)化遺傳迭代調(diào)度算法

祝衍軍

(東莞職業(yè)技術(shù)學院 計算機工程系,廣東 東莞523808)

摘要:文章在遺傳算法的基礎(chǔ)上,構(gòu)建了一種用于虛擬機簇部署的調(diào)度算法。此算法的核心是適應(yīng)度函數(shù)的構(gòu)建,構(gòu)建的基礎(chǔ)是2個優(yōu)化目標:一個是結(jié)合CPU、內(nèi)存、硬盤、帶寬等參數(shù)的資源利用率,另一個是基于計算時間的處理效率。為了考察此算法的效果,選取啟發(fā)式算法和GC(graph cut)算法作為比較算法。實驗結(jié)果表明基于雙目標優(yōu)化的遺傳迭代調(diào)度算法,具有更高的資源利用率和處理效率。

關(guān)鍵詞:虛擬機簇;遺傳算法;資源利用率;處理效率

虛擬化技術(shù)的出現(xiàn),為云計算實現(xiàn)資源和硬件平臺之間的松耦合連接創(chuàng)造了條件,使得云端的服務(wù)更加靈活、便利、高效[1]。云服務(wù)請求和執(zhí)行被清晰地分割為2個階段,根據(jù)任務(wù)需求調(diào)度虛擬機資源,再將虛擬機配置在最合理的物理主機之上[2]。

對于計算量小、任務(wù)單一的云服務(wù)請求,虛擬化技術(shù)較好地解決了實際問題[3]。研究者主要考慮單虛擬機在不同硬件平臺上的調(diào)度和部署問題,如應(yīng)用蟻群算法、多屬性決策等優(yōu)化技術(shù),盡可能提升云服務(wù)過程中的資源利用效率[4-5]。隨著大數(shù)據(jù)技術(shù)和云計算的發(fā)展,先前的針對單虛擬機的調(diào)度和部署算法已經(jīng)很難滿足實際需求。文獻[6]認為,要解決大任務(wù)的最佳云服務(wù)問題,需要將大任務(wù)分解成多個子任務(wù),進而設(shè)置多個優(yōu)化目標來進行虛擬機資源的優(yōu)化調(diào)度和部署。對于計算量較大的任務(wù),往往需要多個虛擬機和多個物理主機來配合完成,虛擬機的調(diào)度問題則從單虛擬機調(diào)度轉(zhuǎn)化為虛擬機的批量調(diào)度。為此,文獻[7]對蟻群算法進行了改進,取得了較好的效果。文獻[8]將多虛擬機部署問題,用虛擬機簇來描述,并構(gòu)建了一種基于負載感知的調(diào)度方法,也取得了優(yōu)于單虛擬機的部署效果。文獻[9-10]提出了一種機器學習技術(shù),能夠?qū)μ摂M機和基于虛擬機的應(yīng)用同時進行實時的自動化配置和再配置,并在此基礎(chǔ)上提出一種基于強化學習方法虛擬機簇管理技術(shù)。

虛擬機簇的調(diào)度和配置問題,就是簇內(nèi)多個虛擬機同時調(diào)度和配置的問題。因為虛擬機簇不僅包含了多個虛擬機,簇內(nèi)各個虛擬機之間還存在一定的關(guān)聯(lián),這對于調(diào)度算法的要求就大大高于單個虛擬機的調(diào)度[11]。從現(xiàn)有的研究成果來看,虛擬機部署正在從單個虛擬機部署逐步演變?yōu)槎嗵摂M機調(diào)度,也就是虛擬機簇的調(diào)度問題[12-13]。本文借助遺傳算法和雙目標優(yōu)化的適應(yīng)度函數(shù),實現(xiàn)虛擬機簇的調(diào)度。

1基于雙目標的遺傳迭代算法框架

1.1虛擬機簇的染色體設(shè)置

假設(shè)云端同時要解決15個任務(wù),并希望由4個虛擬機構(gòu)成的虛擬機簇來完成任務(wù)。根據(jù)遺傳迭代算法的基本設(shè)置需求,15即成為染色體的長度。分別用A、B、C、D來表征虛擬機簇中的4個虛擬機,可以構(gòu)建一個染色體為:r=[C,B,D,A,A,C,B,C,A,D,D,D,A,B,C],根據(jù)此染色體中的基因排布,4個虛擬機分別承擔了15個任務(wù)中不同數(shù)量的任務(wù)。

虛擬機A:完成4號、5號、9號、13號任務(wù)。

虛擬機B:完成2號、7號、14號任務(wù)。

虛擬機C:完成1號、6號、8號、15號任務(wù)。

虛擬機D:完成3號、10號、11號、12號任務(wù)。

所以,通過遺傳算法確定一個具體的染色體,就可以實現(xiàn)虛擬機簇適應(yīng)任務(wù)需要的合理調(diào)度。

1.2基于云端資源的初始種群生成

對于遺傳算法設(shè)置中的初始種群,需要依托虛擬機簇的數(shù)量來實現(xiàn),根據(jù)遺傳算法的實際應(yīng)用經(jīng)驗,初始種群的規(guī)模最好大于10。如果設(shè)定初始種群規(guī)模為20,就有20個虛擬機簇要參與任務(wù)調(diào)度算法的選擇比較。染色體的長度根據(jù)任務(wù)數(shù)量進行設(shè)置,基因的可能出現(xiàn)情況取決于虛擬機簇中虛擬機的個數(shù)和配置標號。

1.3基于雙目標優(yōu)化的適應(yīng)度函數(shù)構(gòu)建

虛擬機簇任務(wù)調(diào)度算法的適應(yīng)度函數(shù)應(yīng)該體現(xiàn)在不同部署后云端的資源利用率和處理效率。虛擬機資源需求主要包括4個因素——CPU、內(nèi)存、硬盤、帶寬,下面從這4個角度來考慮虛擬機簇進行任務(wù)調(diào)度時的資源利用率。令M表示虛擬機簇,有M={m1,m2,…,mi,…};令T表示任務(wù)集合,有T={T1,T2,…,Tj,…}。資源利用率計算公式為:

(1)

從處理效率的角度看,虛擬機簇完成任務(wù)集合中的任務(wù)所花費的時間越少越好,這個時間的衡量,即虛擬機簇中每個虛擬機完成自身承擔所有任務(wù)的最長時間,其計算公式為:

(2)

至此,代表資源利用率的R和處理效率的t就成為虛擬機簇任務(wù)調(diào)度時的2個優(yōu)化目標,這2個目標也是遺傳迭代中構(gòu)建適應(yīng)度函數(shù)的基礎(chǔ)?？紤]到2個優(yōu)化目標,R越大越好、t越小越好,據(jù)此構(gòu)建的適應(yīng)度函數(shù)如(3)式所示。

(3)

根據(jù)這個適應(yīng)度函數(shù)的構(gòu)造關(guān)系,在遺傳迭代的過程中,希望F(R,t)越小越好。

1.4遺傳迭代過程中的關(guān)鍵操作

根據(jù)遺傳算法的基本原理,種族中個體的誕生要經(jīng)過2個個體的交叉繁殖,通過遺傳和變異不斷生成新的個體。通過初始化種群個體的數(shù)量以及控制繁殖的代數(shù)來確定總的個體個數(shù),進而在遍歷全部個體的過程中選出最優(yōu)個體。對于本文而言,最優(yōu)個體確定后,就可以根據(jù)這個個體的染色體來確定其基因排布,也就可以確定各個虛擬機上完成的具體任務(wù)了。

(1) 交叉繁殖。本文采用按序交叉模式,設(shè)第1代父輩的2個個體的染色體如下:

選取母個體r2中的基因串“ACAB”為交叉基因串,對父個體r1進行調(diào)整,誕生新個體的過程如圖1所示。

(2) 變異繁殖。變異是個體染色體中某個基因發(fā)生突變的情況,變異發(fā)生的機率非常小,但對于種群進化起到非常重要的作用。在本文的算法中,用隨機數(shù)和小概率函數(shù)乘積來模擬變異的情況,如(4)式所示。

Bit(r)=Bit{Random[p(eJ-1)]}

(4)

其中,Bit(r)代表染色體中的某一位。

(3) 最優(yōu)個體選擇。要選擇整個種群中最優(yōu)秀的染色體,除了依托適應(yīng)度函數(shù)之外,還要根據(jù)遺傳代數(shù)計算其被選擇的累積概率。假設(shè)遺傳迭代過程進行D代,則在第d代中,ri被選中的概率為:

(5)

其中,Z為種群中這一代所有染色體的數(shù)量。

在全部D代中,ri被選中的累積概率為:

(6)

p(D)最大的ri將會成為最優(yōu)個體,也就是本文虛擬機簇調(diào)度的方案。

2實驗結(jié)果與分析

為了驗證本文方法的有效性,對基于雙目標優(yōu)化遺傳迭代的虛擬機簇調(diào)度算法進行實驗研究。實驗驗證平臺和程序編制選擇Matlab7.0,虛擬機數(shù)量設(shè)置為80～800個,每4個虛擬機為1個虛擬機簇,虛擬機簇個數(shù)則為20～200個。虛擬機簇的數(shù)目也就相當于個體種群的數(shù)量。任務(wù)的數(shù)量為15個,這些任務(wù)的4種資源需求見表1所列。

表1　各個任務(wù)的資源需求

所有虛擬機都可以承擔至少1項任務(wù),并且是表1中的最大任務(wù)。虛擬機資源配置最低的情況為:CPU 1 000 MIPS、內(nèi)存2.0 GB、硬盤50 GB、帶寬100 MB/s。資源配置高的虛擬機,則可以同時承載幾項任務(wù),對應(yīng)著遺傳迭代算法中染色體內(nèi)某個基因反復出現(xiàn)幾次。

實驗中,染色體的長度設(shè)置與云計算要完成的任務(wù)數(shù)相同,都為15個。遺傳迭代的適應(yīng)度函數(shù)設(shè)置中,α1、α2、α3、α4都設(shè)置為0.25,β1、β2都設(shè)置為0.5。為了和本文方法對比,在虛擬機簇調(diào)度過程中,選擇了另外2種方法作為比較方法,一個是啟發(fā)式算法,另一個是GC(graph cut)算法。3種方法形成虛擬機簇部署后,資源利用率的對比結(jié)果如圖2所示。

圖2　資源利用率實驗結(jié)果

從圖2可以看出,當虛擬機簇的個數(shù)為20時,3種方法調(diào)度后承擔任務(wù)的虛擬機簇的資源利用率都比較高,沒有造成過多的資源浪費。隨著虛擬機簇數(shù)目的增加,也就是種群規(guī)模的不斷擴大,本文算法的優(yōu)勢逐漸顯現(xiàn),其調(diào)度后的虛擬機簇的資源利用率依然能維持在85%左右。GC算法則呈現(xiàn)比較穩(wěn)定的下降趨勢,啟發(fā)式算法呈現(xiàn)波動性下降趨勢,當虛擬機簇增加到200時,這2種算法的資源利用率都下降到50%以下。

時間效率實驗結(jié)果如圖3所示。

圖3　時間效率實驗結(jié)果

從圖3可以看出,3種方法的調(diào)度時間有著明顯的區(qū)別,GC算法的調(diào)度時間最長,啟發(fā)式算法的調(diào)度時間次之,本文算法調(diào)度時間最短。隨著虛擬機簇數(shù)目的增加,本文算法的調(diào)度時間優(yōu)勢逐漸加大。

3結(jié)束語

針對虛擬機簇的調(diào)度問題,本文依托遺傳迭代算法構(gòu)建了一種全新的調(diào)度算法。在此算法中,根據(jù)虛擬機和所承擔任務(wù)的關(guān)系構(gòu)建個體的染色體,根據(jù)任務(wù)數(shù)量初始化種群規(guī)模,基于資源利用率和處理效率構(gòu)建適應(yīng)度函數(shù),依據(jù)按序模式完成個體的交叉運算,根據(jù)累積概率選擇最優(yōu)個體,進而解碼出虛擬機簇的調(diào)度結(jié)果。實驗結(jié)果表明,本文構(gòu)建的方法較好地完成了虛擬機簇的調(diào)度,調(diào)度結(jié)果具有更高的資源利用率和處理效率。

[參考文獻]

[1]Rana S,Jasola S,Kumar R.A hybrid sequential approach for data clustering using K-Means and particle swarm optimization algorithm [J].International Journal of Engineering,Science and Technology,2010,2(6): 167-176.

[2]Calheiros R.N,Ranjan R,Beloglazov A,et al.CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J].Software: Practice and Experience,2011,41(1): 23-50.

[3]Jayasinghe D,Pu C,Eilam T.Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement[C]//2011 IEEE International Conference on Services Computing.Piscataway: IEEE,2011: 72-79.

[4]溫少君,陳俊杰,郭濤.一種云平臺中優(yōu)化的虛擬機部署機制[J].計算機工程,2012,38(11): 17-19.

[5]莊威,桂小林,林建材,等.云環(huán)境下基于多屬性層次分析的虛擬機部署與調(diào)度策略[J].西安交通大學學報,2013,47(2): 28-32.

[6]李強,郝沁汾,肖利民,等.云計算中虛擬機放置的自適應(yīng)管理與多目標優(yōu)化[J].計算機學報,2011,34(12):2253-2264.

[7]楊星,馬自堂,孫磊.云環(huán)境下基于改進蟻群算法的虛擬機批量部署研究[J].計算機科學,2012,39(9): 33-37.

[8]王光波,馬自堂,孫磊,等.基于架構(gòu)負載感知的虛擬機聚簇部署算法[J].計算機應(yīng)用,2013,33(5): 1271-1275.

[9]Xu Chengzhong,Rao Jia,Bu Xiangping.URL: a unified reinforcement learning approach for autonomic cloud management [J].Journal of Parallel and Distributed Computing,2012,72(2): 95-105.

[10]Rao Jia,Bu Xiangping,Xu Chengzhong,et al.VCONF: a reinforcement learning approach to virtual machines auto-configuration[C]//Proceedings of International Conference on Autonomic Computing and Communications.New York:ACM,2009: 137-146.

[11]Kim C,Jeon C,Lee W,et al.A parallel migration scheme for fast virtual machine relocation on a cloud cluster [J].Journal of Supercomputing,2015,71(12):4623-4645.

[12]Yang C T,Liu J C,Huang K L,et al.A method for managing green power of a virtual machine cluster in cloud [J].Future Generation Computer Systems,2014,37: 26-36.

[13]李晨,劉博,李云.云環(huán)境下基于碎片影響度的提前預(yù)定資源調(diào)度策略[J].合肥工業(yè)大學學報:自然科學版,2015,38(7): 914-917,991.

(責任編輯張淑艷)

Genetic iterative scheduling cluster algorithm for virtual machine based on double objective optimization

ZHU Yan-jun

(Dept. of Computer Engineering, Dongguan Polytechnic, Dongguan 523808, China)

Abstract:Based on the genetic algorithm, a scheduling algorithm for the virtual machine cluster was developed. The core of this algorithm is the construction of fitness function, and its basis is two optimization objectives: one is resource utility with four parameters of CPU, RAM, hardware and bandwidth; the other is processing efficiency based on computing time. In order to investigate the effect of this algorithm, heuristic algorithm and graph cut(GC) algorithm are selected as the comparison algorithm. The experimental results show that the genetic iterative scheduling algorithm based on double objective optimization has higher resource utility and processing efficiency.

Key words:virtual machine cluster; genetic algorithm; resource utility; processing efficiency

收稿日期：2015-07-01；修回日期：2016-03-10

基金項目：廣東省省級科技計劃資助項目(2014A010103002);東莞市高等院校、科研機構(gòu)科技計劃一般資助項目(2014106101037;2014106101033) 和東莞職業(yè)技術(shù)學院政校行企合作開展科研與服務(wù)資助項目(ZXHQ2014d010)

作者簡介：祝衍軍(1982-),男,湖南邵陽人,東莞職業(yè)技術(shù)學院工程師.

doi:10.3969/j.issn.1003-5060.2016.05.012

中圖分類號:TP393.01

文獻標識碼：A

文章編號：1003-5060(2016)05-0632-04