云環(huán)境下基于改進遺傳算法的資源調(diào)度分配算法

韓秋英　殷秀葉　張少輝

摘要：在云計算環(huán)境中，數(shù)據(jù)中心需要高效且快速的調(diào)度算法來滿足不同的任務(wù)要求。本文主要從分析Map/Reduce框架模型出發(fā)，在傳統(tǒng)遺傳算法的基礎(chǔ)上引入QoS用戶服務(wù)質(zhì)量度量，考慮不同用戶的任務(wù)差別，并將其應(yīng)用至云計算環(huán)境中的資源調(diào)度。在云仿真器CloudSim上進行仿真，實驗結(jié)果表明，相對于傳統(tǒng)遺傳算法，優(yōu)化的遺傳算法能在大量任務(wù)的情況下取得更好的優(yōu)化效果，能使任務(wù)快速合理地分配到虛擬資源上。

關(guān)鍵詞：云計算； 改進遺傳算法； 資源調(diào)度

中圖分類號：TP393 文獻標(biāo)識碼：A文章編號：2095-2163（2014）04-0100-03

Abstract：Data centers need efficient and fast scheduling algorithms to meet the requirements of the different tasks in the cloud computing environment. This paper mainly from the analysis of Map/Reduce frame， introduces QoS in the traditional genetic algorithm， considering the correspon-ding user task difference， and applies it to the resource scheduling in the cloud computing environment. Simulation is realized in the cloud simulator CloudSim， experimental results show that， improved genetic algorithm can get better performance in a large number of tasks， which would make tasks reasonable allocation to virtual resources compared with the traditional genetic algorithm.

Key words：Cloud Computing； Improved Genetic Algorithm； Resource Scheduling

0引言

云計算是現(xiàn)今業(yè)界最具研討價值的課題之一。隨著互聯(lián)網(wǎng)數(shù)據(jù)中心的容量出現(xiàn)了快速擴充，當(dāng)下以百萬臺計算的區(qū)域數(shù)據(jù)中心、云服務(wù)中心以及超算中心也隨之頻頻出現(xiàn)，甚至異軍突起的4G，都為云計算的加速發(fā)展起到了重大的推進作用[1]。

Map/Reduce是一個將大型分布式計算表達為鍵值對結(jié)合、并可進行串行化分布式操作的編程模型。當(dāng)在云環(huán)境中使用時，Map/Reduce集群利用虛擬機可實現(xiàn)動態(tài)創(chuàng)建，同時由云提供者實施管理，而且利用特殊的時空權(quán)衡即可實現(xiàn)能量感知。在云計算能效和資源調(diào)度方面，國內(nèi)外專家們提出了許多的算法和策略。宋杰等學(xué)者提出了能效的概念和度量能效的方法[2]；另有部分學(xué)者把虛擬機問題抽象為NP難的裝箱問題以達到減少數(shù)據(jù)中心能源消耗的目的[3-4]；而文獻[5]則是從資源調(diào)度角度來發(fā)起研究與討論的。本文即從虛擬機調(diào)度策略入手，采用改進的遺傳算法針對云計算環(huán)境中的資源開展了合理調(diào)度的有關(guān)研究。

1云計算虛擬機資源調(diào)度

1.1Map/Reduce框架模型

Google公司設(shè)計研發(fā)的Map/Reduce模型，是當(dāng)今世界最為流行的海量數(shù)據(jù)處理編程模型，其工作原理是：Map函數(shù)將用戶提交的任務(wù)分解為多個子任務(wù)，并將這些子任務(wù)按照調(diào)度算法分配到虛擬機節(jié)點，待子任務(wù)執(zhí)行完畢，再由Reduce函數(shù)將產(chǎn)生的中間結(jié)果進行匯總處理，圖1表示其執(zhí)行流程。

1.2研究場景

對于Map/Reduce任務(wù)，利用適當(dāng)?shù)恼{(diào)度策略將其分配至對應(yīng)的虛擬機中，并將這些虛擬機按照一定的算法部署到物理機上，即虛擬機資源調(diào)度實際上分為兩級，一級調(diào)度是云計算中用戶任務(wù)和虛擬機資源的調(diào)度，二級調(diào)度是虛擬機和物理機的映射關(guān)系[6]。本文主要研究的是在任務(wù)調(diào)度中，如何快速而高效地獲得虛擬機。具體過程是：已經(jīng)定義的任務(wù)（用戶程序）開始執(zhí)行，而且由Map/Reduce庫劃分為若干份，之后將用戶進程拷貝到集群內(nèi)的其他機器上實現(xiàn)并行處理。

2算法設(shè)計與實現(xiàn)

2.1經(jīng)典遺傳算法

由圖4可以看出，在迭代的前期，兩種算法性能差別不大，但是隨著迭代次數(shù)的不斷增加，優(yōu)化后的IGA算法明顯地占據(jù)了優(yōu)勢，而且優(yōu)化的IGA算法在140～160代之間已經(jīng)接近于成熟；另外，從GA的圖像還可看出該算法具有超常的適應(yīng)度值，這是由于個別值引導(dǎo)了種群向錯誤方向進化。而IGA算法在適應(yīng)度計算方面因為進行了一定的調(diào)整，進化結(jié)果則更為理想。

4結(jié)束語

本文對云環(huán)境中的資源調(diào)度問題進行了詳細的分析，并且構(gòu)建分析了基于Map/Reduce編程框架的模型，同時依據(jù)此框架提出了基于改進遺傳算法的任務(wù)調(diào)度策略。IGA算法充分考慮了不用用戶的任務(wù)需求，引入了服務(wù)質(zhì)量概念，而且考慮了任務(wù)執(zhí)行時間、帶寬、成本和可靠性因素，由此而建立了適應(yīng)度函數(shù)模型。在此基礎(chǔ)上，對比原先的GA算法，大量任務(wù)的情況下仍能取得良好的優(yōu)化效果，從而做到了將任務(wù)快速合理地分配到對應(yīng)虛擬資源上。

參考文獻：

[1]劉永， 王新華， 邢長明，等. 云計算環(huán)境下基于蟻群優(yōu)化算法的資源調(diào)度策略[J].計算機技術(shù)與發(fā)展，2011， 21（9）：20-27.

[2]宋杰， 李甜甜， 閆振興，等. 一種云計算環(huán)境下的能效模型和度量方法[J]. 軟件學(xué)報，2012，23（2）：200-214.

[3]CARDOSA M， SINGH A， PUCHA H， et al. Exploiting spatio-temporal tradeoffs for energy-aware Map/Reduce in the Cloud [J]. IEEE Transaction on Computers， 2012， 12（61）：1737-1751.

[4]譚一鳴， 曾國蓀， 王偉. 隨機任務(wù)在云計算平臺中能耗的優(yōu)化管理方法[J].軟件學(xué)報，2012，23（02）：266-278.

[5]劉永.云計算環(huán)境下虛擬機資源調(diào)度策略研究[D]. 濟南：山東師范大學(xué)， 2012.

[6]劉愉，趙志文，李小蘭，等. 云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略[J]. 北京師范大學(xué)學(xué)報（自然科學(xué)版）， 2012， 48（4）：378-384.

[7]熊聰聰， 馮龍， 陳麗仙， 等. 云計算中基于遺傳算法的任務(wù)調(diào)度算法研究[J]. 華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2012，40（1）：1-4.