基于貪心改進算法的云計算任務調度*

楊武軍， 郝 凱

(西安郵電大學 通信與信息工程學院,陜西 西安 710061)

?

基于貪心改進算法的云計算任務調度*

楊武軍， 郝 凱

(西安郵電大學 通信與信息工程學院,陜西 西安 710061)

基于云計算的存儲和計算架構的特征上，對資源存儲算法和任務分配進行了研究。針對云計算的資源管理中單純考慮算法的時間和空間復雜度，而忽略在數據鏈路層因調度所消耗的時間問題，因此將網絡存儲感知和貪心算法相結合，提出了一種貪心改進算法，目的在于大幅減少數據在數據鏈路層所消耗的時間。最終在CloudSim平臺上進行云環(huán)境下的仿真，將得出的結果和一般的貪心算法相比較，經過對比分析表明：改進后的貪心算法對于任務的執(zhí)行而言時間更短，效率更高。

云計算； 任務分配； 副本； 網絡感知

0 引 言

這些年來隨著社會大眾對計算要求和服務的的提高，基于云計算(cloud computing)的服務得到迅速發(fā)展。云計算化分成了三層：基礎設施即服務(IaaS)，平臺即服務(PaaS)和軟件即服務(SaaS)[1]。而云計算效能的高低則很大程度上取決于IaaS層算法的高效性。對于云計算資源管理它主要分為存儲資源和計算資源的管理。在存儲資源管理方面主要關注于數據的調配和數據副本機制的研究，以及元數據的管理；在計算資源管理方面則注重于計算節(jié)點的高效性和節(jié)點域整體的負載均衡。

無論是一般的云計算還是快速發(fā)展的移動云計算，云端增效模式是最常見的云計算模式[2]。因此在云計算方面主要的研究關注在云端計算資源和存儲資源的管理，負載均衡的實現(xiàn)，以及任務合理的分配等幾個方面。例如：在存儲資源管理方面，文獻[3]中介紹的基于P2P組織結構通過數據副本的管理來提高對數據的訪問效率或者系統(tǒng)的容錯性能，它詳細闡述了數據采用靜態(tài)機制和動態(tài)機制各自的特點；以及在文獻[4]中提出以DHT為核心的開放對等云存儲服務系統(tǒng)，通過Kademlia算法對文件的可用性分析來管理文件；在文獻[5]中提出的基于DHT模型的Chord算法提高了數據副本的查詢效率。這些算法雖然相提高了對數據的管理效率和實現(xiàn)了一定程度上的存儲負載均衡但卻沒有突出計算方面的優(yōu)勢。

在計算資源管理方面，文獻[6]研究了在不同的移動云計算環(huán)境下根據各自不同的特點提出了對應的解決方案。文獻[7]提出的基于蟻群優(yōu)化算法，預測潛在可用節(jié)點的計算質量，來獲取一組最優(yōu)的計算資源；文獻[8]提出了在網絡感知計算資源的前提下的對虛擬機的放置算法。但是這些算法的不足之處是單一地考慮某一個計算資源管理方面的問題，缺乏綜合考慮存儲方面數據鏈路傳輸所帶來的影響。

因此，本文從傳統(tǒng)的云計算中著手，從實際的云計算應用出發(fā)，充分考慮云計算的存儲特征在實際情況中的應用，以最大程度降低用戶服務等待時間為目標，通過將云計算數據副本的部署方式和任務分配的算法相結合，為用戶提供高效的云計算服務。

1 云計算相關描述

1.1 云計算資源管理

云計算資源管理問題基本上可以描述成n個計算節(jié)點對應著m個相互獨立的任務，每個計算節(jié)點上運行著一個虛擬機VM提供計算資源，將相互獨立的任務采取某種特定的策略部署到各個虛擬機計算節(jié)點上以完成計算任務。其中，T={t1,t2,t3,…,tm},ti表示第i個子任務，vm={vm1,vm2,vm3…vmn}其中vmj表示 第j個子任務。而任務結合可以和對應虛擬機計算節(jié)點組成一個矩陣，用M表示[9]

式中 Mij∈{0,1}為了虛擬機計算節(jié)點和子任務之間的分配關系，Mij為第i個任務部署到第j個計算節(jié)點上，當任務部署到節(jié)點上時值取1，否則取值為0.然后根據虛擬機和子任務之間這樣的對應關系來進行相關的實驗仿真。在IaaS(基礎設施即服務)這層中，通常將數據的3個副本鏡像都存儲在專門存儲數據的存儲節(jié)點中[10]。副本指的是在不同的數據節(jié)點上存儲數據拷貝，它能夠在原始數據丟失的情況下，幫助用戶或者管理員來快速的恢復所丟失的數據。

1.2 云計算數據副本管理描述

在云計算中數據副本的管理機制，可以是靜態(tài)的也可以是動態(tài)的。如果采用靜態(tài)管理機制，數據會保存到直至被管理員刪除或者超過數據的保存期限自動銷毀，而采用動態(tài)管理機制，數據的保存和刪除都是自動的，動態(tài)機制會根據用戶對數據的訪問的頻率的高低而自動的進行創(chuàng)建和刪除[11]；或者可以間接地通過中間參數來管理副本例如基于QOS感知分布的數據副本放置算法[12],通過衡量每條鏈路的負載能力和各個數據副本服務器的負載能力來確定相關的參數，再通過參數來確定副本的刪除與否。通過這些方法可以提高文件的訪問效率也在一定程度上實現(xiàn)了存儲節(jié)點的負載均衡。

在云計算架構中，數據副本塊的放置是分布式的存放，所以數據塊和存儲節(jié)點之間可以組成一個的矩陣[8]

式中Dij為數據副本塊i存儲在節(jié)點j上，Dij∈{0,1}。

在云計算環(huán)境中，考察任務完成的快慢通常主要考察它的響應時間的快慢，而響應時間通常又包括用戶端發(fā)送信息自身的的發(fā)送時延，以及信息的網絡傳輸時延和云計算平臺自身系統(tǒng)的響應時間。對于云計算系統(tǒng)本身來說，系統(tǒng)自身的響應時間則主要考察任務的執(zhí)行時間，而此處的任務的執(zhí)行時間分為數據塊的傳輸時間和實際的執(zhí)行時間。因此，在這里主要考察數據塊的傳輸所耗的時間和計算節(jié)點的執(zhí)行任務所消耗的時間。

2 改進算法的描述

2.1 算法基本原理

貪心算法并沒有固定的算法框架，算法的關鍵是貪心策略的選擇。因此利用貪心算法的這個特性，將數據副本網絡感知和貪心算法相結合，在整個計算的過程中都優(yōu)先對存儲數據的節(jié)點進行匹配選擇，在任務分配前進行數據感知，找出它所需要的數據所在的節(jié)點上，然后將任務部署到相應的計算節(jié)點上去，這樣就可以為用戶節(jié)省大量的時間。對于數據網絡感知，在云端可以通過分析它的元數據來確定相關的副本所放的具體節(jié)點位置。

在云計算中，各個節(jié)點之間的相關聯(lián)系都可以用一個矩陣來表示。相應各個數據節(jié)點之間的網絡帶寬BW，也可以用一個矩陣B表示出來，此處定義一個矩陣B

不考慮其它因素，數據網絡傳輸感知時間T可以表示為數據塊的大小除以網絡帶寬的值。此處可以定義為：T=D/B=DB-1表示數據網絡傳輸感知所花費的時間等于數據塊矩陣D和網絡帶寬B的逆矩陣的乘積。而最終對于用戶而言，總的消耗時間T總等于副本鏈路傳輸響應的時間T1加上計算節(jié)點上計算所消耗的時間T2。相關的公式如下

T=D/B=DB-1

T2=MI/MIPS

式中MI為指令的長度，MIPS為虛擬機的執(zhí)行速度。

Ttotal=T1+T2

在仿真的時候，選擇具有最小的響應時間的計算節(jié)點來托管應用程序。一個任務i在虛擬機計算節(jié)點j上所消耗的時間可以組成一個矩陣time[i][j],在初始化time矩陣前，首先將虛擬機的計算能力的執(zhí)行速度MIPS按照由小到大升序排列，將需要進行計算的任務按照它的指令長度MI的大小進行由大到小的降序排列。此處我們在仿真時數據副本的放置采用靜態(tài)放置機制,每個副本存放至三個不同的節(jié)點處，并假設提前已經知道用戶所需要的各個數據副本的存放的位置，并且爭取將任務計算本地化。

2.2 算法流程

1)找出用戶任務所需數據副本所在的各個節(jié)點的位置；

2)采用貪心算法部署任務指令最長的mession A，將其部署至其任務對應的存有它所需要副本的三個節(jié)點中計算能力最強的節(jié)點上；

3)部署剩余任務指令中最長的B，同樣采用貪心算法將其同樣部署到存有它所需的副本的三個節(jié)點中計算能力最強的節(jié)點上；

4)以此類推，當存放有任務所需的數據副本的節(jié)點上已經部署了一定的計算任務時，我們就將新的計算任務部署到別的計算任務最少的節(jié)點上，并且將其運行所需要的數據副本遷移到它所在的節(jié)點，通過這種方式來實現(xiàn)簡單的負載均衡。

3 實驗與分析

在CloudSim平臺下，模擬相關的云環(huán)境，仿真時對平臺進行了擴展，修改datacenter類加入了自定義了的調度策略，并更改了其相關的幾個類。通過它來測試算法的相關性能。在仿真時，將改進的貪心算法與一般貪心算法分別進行仿真，然后將二者的仿真實驗結果進行比較分析，如圖1所示。

圖1 算法仿真對比圖Fig 1 Comparison diagram of algorithm simulation

從仿真結果圖可知，在進行虛擬機資源分配時，采用改進后的貪心算法執(zhí)行的時間要明顯的要比一般貪心算法的時間要少的多，說明改進后的貪心算法效率更高。這是因為貪心算法在進行任務的分配時，是單純的考慮計算節(jié)點的能力的大小，它將任務分配到恰好具有所需數據副本的節(jié)點上具有很大的隨機性，而且當計算節(jié)點越多，它的任務和具有數據副本的計算節(jié)點之間的成功耦合率就越小，而改進后的貪心算法，由于增加了網絡副本感知功能，它在分配任務時，會將任務盡量放置在具有任務所需副本的節(jié)點上或者距離它最近的鏈路上。這樣就減少了因為任務的隨機性分配而帶來的數據鏈路層的時間消耗，整體的效率也就提高了。

4 結 論

在本文中所介紹的基于貪心改進算法可以可以迅速找出數據副本所在的節(jié)點位置并且在數據共享方面體現(xiàn)出了共享性和動態(tài)性的特點。該改進算法可以快速地將任務動態(tài)地分配到相應的節(jié)點上，并且可以高效地完成相應的計算。從得出的仿真結果來看，該算法在云計算環(huán)境中為用戶節(jié)省大量的時間，快速完成任務是一種有效的改進算法。

[1] 羅軍舟.云計算體系機構與關鍵技術[J].通信學報，2011,32(7)：4-12.

[2] 姚慧峰.移動云計算環(huán)境下任務分配問題的研究[D].南京：南京郵電大學，2014:6-15.

[3] 王意潔，孫偉東.云計算環(huán)境下的分布式存儲關鍵技術[J].軟件學報，2012,23(4)：962-986.

[4] 吳吉義.基于DHT的開放對等云存儲服務系統(tǒng)研究[D].杭州：浙江大學，2011:34-58.

[5] 劉曉偉.一種基于P2P的云存儲模型研究[D].西安:西安電子科技大學，2012:33-42.

[6] 楊 洋.移動計算環(huán)境下數據副本放置策略的研究[D].哈爾濱：哈爾濱工程大學,2013:6-26.

[7] 華夏渝，鄭 鈞，胡文心.基于云計算環(huán)境的蟻群優(yōu)化算法資源分配算法[J].華東師范大學學報，2010,6(1):128-134.

[8] 常德成.移動云計算環(huán)境下網絡感知的虛擬機放置算法研究[D].長春：吉林大學，2014:26-35.

[9] 董紅蕓，高志棟，王登科.基于蟻群算法的云計算資源調度研究[J].中國西部科技，2013,12(4)：29-31.

[10] 孫知信，黃涵霞.基于云計算的數據存儲技術研究[J].南京郵電大學學報，2014,34(4):14-18.

[11] 李 冰.云計算環(huán)境下動態(tài)資源管理關鍵技術研究[D].北京：北京郵電大學，2012:14-21.

[12]RasoolQaisar,LiJianzhong,ZhangShuo.OnP2Pandhybridapproachesforreplicaplacementingridenvironment[J].InformationTechnologyJournal,2008,7(4):591-597.

郝 凱,通訊作者,E—mail:haoguangxuan@126.com。

Cloud computing task scheduling based on improved greedy algorithm*

YANG Wu-jun， HAO Kai

(School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

Based on characteristics of storage of cloud computing and computing architecture,resources storage algorithms and assignment of tasks are studied.In resource management of cloud computing,simply consider time and space complexity of algorithm,while ignoring time consuming in data link layer due to scheduling,so combined network storage perception with greedy algorithm,propose an improved greedy algorithm aimed at significantly reduce time consuming of data in data link layer.Eventually perform simulation on CloudSim platform in cloud environment,the obtained results is compared with general greedy algorithm,it is proved through comparative analysis that the improved greedy algorithm is shorter in time and more efficient for mission.

cloud computing; task scheduling; copies of data；network perception

10.13873/J.1000—9787(2016)12—0143—03

2016—01—21

2014陜西省國際科技合作項目(2014KW02—02)

TP 316

A

1000—9787(2016)12—0143—03

楊武軍(1975-)，男，陜西西安人，博士，副教授，碩士生導師，從事移動通信互聯(lián)網研究工作。