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

祝衍軍

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

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

祝衍軍

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

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

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

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

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

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

1基于雙目標(biāo)的遺傳迭代算法框架

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

至此,代表資源利用率的R和處理效率的t就成為虛擬機(jī)簇任務(wù)調(diào)度時的2個優(yōu)化目標(biāo),這2個目標(biāo)也是遺傳迭代中構(gòu)建適應(yīng)度函數(shù)的基礎(chǔ)?？紤]到2個優(yōu)化目標(biāo),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ù),進(jìn)而在遍歷全部個體的過程中選出最優(yōu)個體。對于本文而言,最優(yōu)個體確定后,就可以根據(jù)這個個體的染色體來確定其基因排布,也就可以確定各個虛擬機(jī)上完成的具體任務(wù)了。

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

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

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

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

(4)

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

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

(5)

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

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

(6)

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

2實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

圖2　資源利用率實(shí)驗(yàn)結(jié)果

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

時間效率實(shí)驗(yàn)結(jié)果如圖3所示。

圖3　時間效率實(shí)驗(yàn)結(jié)果

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

3結(jié)束語

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

[參考文獻(xiàn)]

[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ī)部署機(jī)制[J].計(jì)算機(jī)工程,2012,38(11): 17-19.

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

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

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

[8]王光波,馬自堂,孫磊,等.基于架構(gòu)負(fù)載感知的虛擬機(jī)聚簇部署算法[J].計(jì)算機(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è)大學(xué)學(xué)報(bào):自然科學(xué)版,2015,38(7): 914-917,991.

(責(zé)任編輯張淑艷)

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

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

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

doi:10.3969/j.issn.1003-5060.2016.05.012

中圖分類號:TP393.01

文獻(xiàn)標(biāo)識碼：A

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