楊武軍， 郝 凱

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

?

基于貪心改進(jìn)算法的云計(jì)算任務(wù)調(diào)度*

楊武軍， 郝 凱

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

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

云計(jì)算； 任務(wù)分配； 副本； 網(wǎng)絡(luò)感知

0 引 言

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

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

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

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

1 云計(jì)算相關(guān)描述

1.1 云計(jì)算資源管理

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

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

1.2 云計(jì)算數(shù)據(jù)副本管理描述

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

在云計(jì)算架構(gòu)中，數(shù)據(jù)副本塊的放置是分布式的存放，所以數(shù)據(jù)塊和存儲(chǔ)節(jié)點(diǎn)之間可以組成一個(gè)的矩陣[8]

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

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

2 改進(jìn)算法的描述

2.1 算法基本原理

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

在云計(jì)算中，各個(gè)節(jié)點(diǎn)之間的相關(guān)聯(lián)系都可以用一個(gè)矩陣來表示。相應(yīng)各個(gè)數(shù)據(jù)節(jié)點(diǎn)之間的網(wǎng)絡(luò)帶寬BW，也可以用一個(gè)矩陣B表示出來，此處定義一個(gè)矩陣B

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

T=D/B=DB-1

T2=MI/MIPS

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

Ttotal=T1+T2

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

2.2 算法流程

1)找出用戶任務(wù)所需數(shù)據(jù)副本所在的各個(gè)節(jié)點(diǎn)的位置；

2)采用貪心算法部署任務(wù)指令最長的mession A，將其部署至其任務(wù)對應(yīng)的存有它所需要副本的三個(gè)節(jié)點(diǎn)中計(jì)算能力最強(qiáng)的節(jié)點(diǎn)上；

3)部署剩余任務(wù)指令中最長的B，同樣采用貪心算法將其同樣部署到存有它所需的副本的三個(gè)節(jié)點(diǎn)中計(jì)算能力最強(qiáng)的節(jié)點(diǎn)上；

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

3 實(shí)驗(yàn)與分析

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

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

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

4 結(jié) 論

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

[1] 羅軍舟.云計(jì)算體系機(jī)構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報(bào)，2011,32(7)：4-12.

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

[3] 王意潔，孫偉東.云計(jì)算環(huán)境下的分布式存儲(chǔ)關(guān)鍵技術(shù)[J].軟件學(xué)報(bào)，2012,23(4)：962-986.

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

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

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

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

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

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

[10] 孫知信，黃涵霞.基于云計(jì)算的數(shù)據(jù)存儲(chǔ)技術(shù)研究[J].南京郵電大學(xué)學(xué)報(bào)，2014,34(4):14-18.

[11] 李 冰.云計(jì)算環(huán)境下動(dòng)態(tài)資源管理關(guān)鍵技術(shù)研究[D].北京：北京郵電大學(xué)，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陜西省國際科技合作項(xiàng)目(2014KW02—02)

TP 316

A

1000—9787(2016)12—0143—03

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