云環境下基于改進遺傳算法的資源調度分配算法

韓秋英　殷秀葉　張少輝

摘要：在云計算環境中，數據中心需要高效且快速的調度算法來滿足不同的任務要求。本文主要從分析Map/Reduce框架模型出發，在傳統遺傳算法的基礎上引入QoS用戶服務質量度量，考慮不同用戶的任務差別，并將其應用至云計算環境中的資源調度。在云仿真器CloudSim上進行仿真，實驗結果表明，相對于傳統遺傳算法，優化的遺傳算法能在大量任務的情況下取得更好的優化效果，能使任務快速合理地分配到虛擬資源上。

關鍵詞：云計算； 改進遺傳算法； 資源調度

中圖分類號：TP393 文獻標識碼：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引言

云計算是現今業界最具研討價值的課題之一。隨著互聯網數據中心的容量出現了快速擴充，當下以百萬臺計算的區域數據中心、云服務中心以及超算中心也隨之頻頻出現，甚至異軍突起的4G，都為云計算的加速發展起到了重大的推進作用[1]。

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

1云計算虛擬機資源調度

1.1Map/Reduce框架模型

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

1.2研究場景

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

2算法設計與實現

2.1經典遺傳算法

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

4結束語

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

參考文獻：

[1]劉永， 王新華， 邢長明，等. 云計算環境下基于蟻群優化算法的資源調度策略[J].計算機技術與發展，2011， 21（9）：20-27.

[2]宋杰， 李甜甜， 閆振興，等. 一種云計算環境下的能效模型和度量方法[J]. 軟件學報，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]譚一鳴， 曾國蓀， 王偉. 隨機任務在云計算平臺中能耗的優化管理方法[J].軟件學報，2012，23（02）：266-278.

[5]劉永.云計算環境下虛擬機資源調度策略研究[D]. 濟南：山東師范大學， 2012.

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

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