黃 少 榮

(廣東司法警官職業(yè)學(xué)院 信息管理系, 廣州 510520)

?

云計(jì)算任務(wù)調(diào)度算法研究

黃 少 榮

(廣東司法警官職業(yè)學(xué)院 信息管理系, 廣州 510520)

云計(jì)算是一種新型的商業(yè)計(jì)算模式,應(yīng)用大規(guī)模的虛擬化資源通過計(jì)算機(jī)網(wǎng)絡(luò)向用戶提供不同服務(wù)。云計(jì)算面對(duì)的用戶眾多,系統(tǒng)要處理的任務(wù)量與數(shù)據(jù)量十分巨大,并且云計(jì)算系統(tǒng)結(jié)構(gòu)復(fù)雜,對(duì)大量任務(wù)進(jìn)行高效調(diào)度是云計(jì)算中一個(gè)必須解決的難題。云計(jì)算任務(wù)調(diào)度算法決定了用戶任務(wù)的執(zhí)行效率和系統(tǒng)資源的使用效率,直接關(guān)系到云計(jì)算系統(tǒng)的整體穩(wěn)定性和整體效果。在對(duì)云計(jì)算任務(wù)調(diào)度算法的相關(guān)研究現(xiàn)狀進(jìn)行深入分析和研究的基礎(chǔ)上,從模型高效和算法高效2個(gè)層面上指出未來云計(jì)算任務(wù)調(diào)度算法的發(fā)展趨勢,提出構(gòu)建基于多目標(biāo)優(yōu)化的云計(jì)算任務(wù)調(diào)度模型。

云計(jì)算; 任務(wù)調(diào)度; 啟發(fā)式算法; 多目標(biāo)優(yōu)化; 群智能

0 引 言

云計(jì)算是下一代計(jì)算機(jī)網(wǎng)絡(luò)與應(yīng)用的新技術(shù),是網(wǎng)絡(luò)計(jì)算、分布式計(jì)算、并行計(jì)算、效用計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、虛擬化和負(fù)載均衡等傳統(tǒng)計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展和延伸。云計(jì)算的核心思想是把計(jì)算任務(wù)分配給一個(gè)由大量計(jì)算機(jī)器組成的資源池,使用戶能夠按需獲得云中的計(jì)算能力、存儲(chǔ)空間以及信息服務(wù)[1]。云計(jì)算包含了基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)以及軟件即服務(wù)(SaaS)這3個(gè)層次的服務(wù),這些服務(wù)都存在任務(wù)與資源之間的調(diào)度問題,即云計(jì)算需要同時(shí)處理大量的計(jì)算任務(wù),對(duì)用戶提交的各種任務(wù)快速分配所需的計(jì)算資源。高效的任務(wù)調(diào)度策略決定了云計(jì)算的工作效率,是保證云計(jì)算服務(wù)質(zhì)量的關(guān)鍵[2]。

1 云計(jì)算任務(wù)調(diào)度模型

云計(jì)算任務(wù)調(diào)度主要研究如何為用戶提交的任務(wù)分配資源,也就是將多個(gè)相互獨(dú)立的多樣化任務(wù)分配到云中規(guī)模寵大的虛擬資源上,滿足用戶QoS要求、總?cè)蝿?wù)的完成時(shí)間最小,負(fù)載均衡最高等目標(biāo),其調(diào)度模型如圖1所示[3]。

云計(jì)算任務(wù)調(diào)度工作于云任務(wù)和虛擬機(jī)之間,即圖1中左邊虛線圈所示的眾多箭頭所在之處。任務(wù)執(zhí)行所需要的成本、耗費(fèi)的時(shí)間、負(fù)載均衡、系統(tǒng)穩(wěn)定性、用戶需求以及對(duì)系統(tǒng)的滿意度等都是由任務(wù)調(diào)度策略決定的。因此,云計(jì)算任務(wù)調(diào)度算法決定了用戶任務(wù)的執(zhí)行效率和系統(tǒng)資源的使用效率,影響了整個(gè)云計(jì)算系統(tǒng)的工作性能。

2 云計(jì)算任務(wù)調(diào)度算法

目前的云計(jì)算任務(wù)調(diào)度機(jī)制還未形成統(tǒng)一的標(biāo)準(zhǔn)和規(guī)范,各大云計(jì)算服務(wù)供應(yīng)商都是自己搭建云平臺(tái),并根據(jù)云平臺(tái)的特點(diǎn)采用不同的任務(wù)調(diào)度策略,所用算法大致分為以下幾種:

圖1 云計(jì)算任務(wù)調(diào)度模型

2.1 傳統(tǒng)任務(wù)調(diào)度算法

分布式計(jì)算是云計(jì)算技術(shù)的一種,分布式任務(wù)調(diào)度與云計(jì)算任務(wù)調(diào)度具有一定的相似性,一些用于分布式環(huán)境下的傳統(tǒng)調(diào)度算法經(jīng)過適當(dāng)改進(jìn)也可用于云計(jì)算任務(wù)調(diào)度問題。典型的有:

1) Min-min算法[4]。Min-min算法的設(shè)計(jì)思想是盡可能將任務(wù)指派給最早可用并且執(zhí)行速度最快的計(jì)算資源,通過獲取任務(wù)執(zhí)行的2個(gè)最小值(最早執(zhí)行開始時(shí)間和最快執(zhí)行速度)完成選擇。該算法屬于貪婪算法的一種,通過先易后難的策略,任務(wù)集中在計(jì)算能力較強(qiáng)的節(jié)點(diǎn)上,而性能較低節(jié)點(diǎn)沒有充分利用,容易造成負(fù)載不均衡。

2) Max-min算法。Max-min算法與Min-min算法類似,也是貪婪算法的一種,但采用的是先難后易的策略,分配任務(wù)時(shí),按任務(wù)執(zhí)行的難度考慮,選擇最大最早完成時(shí)間的任務(wù)映射到具有最早執(zhí)行時(shí)間的資源上執(zhí)行。Min-min算法是先完成執(zhí)行時(shí)間短的任務(wù),而Max-min算法則先完成執(zhí)行時(shí)間長的任務(wù)。在異構(gòu)計(jì)算環(huán)境中,當(dāng)短的任務(wù)數(shù)量遠(yuǎn)遠(yuǎn)多于長任務(wù)數(shù)量時(shí),該算法具有一定的優(yōu)勢。

3) Sufferage算法[5]。Sufferage算法也是貪婪算法的一種,任務(wù)的Shfferage值就是該任務(wù)的最早完成時(shí)間與次早完成時(shí)間之間的差,該值代表某個(gè)任務(wù)如果不分配到完成時(shí)間最早的資源上將造成的損失。在任務(wù)間發(fā)生競爭時(shí),比較各任務(wù)的執(zhí)行損失,將損失最大的任務(wù)優(yōu)先分配給計(jì)算資源。

這些算法都是為了提高用戶任務(wù)的執(zhí)行效率而設(shè)計(jì)的,但由于云計(jì)算中的任務(wù)資源的動(dòng)態(tài)性、異構(gòu)性和差異性,因此云計(jì)算的計(jì)算模式比傳統(tǒng)的計(jì)算模式更加復(fù)雜,這些傳統(tǒng)算法必須經(jīng)過適當(dāng)改進(jìn)才能用于云計(jì)算任務(wù)調(diào)度問題。

2.2 Hadoop中的任務(wù)調(diào)度算法

大多的云計(jì)算環(huán)境是基于開源云計(jì)算框架----Hadoop架構(gòu)的,針對(duì)云系統(tǒng)用戶任務(wù)調(diào)度中不同的QoS目標(biāo)約束要求,Hadoop實(shí)現(xiàn)了3種不同的調(diào)度算法:

1) 先進(jìn)先出調(diào)度算法。FIFO算法(First In First Out,FIFO)根據(jù)用戶提交任務(wù)的時(shí)間先后和優(yōu)先級(jí)的高低來進(jìn)行調(diào)度執(zhí)行,當(dāng)系統(tǒng)中有空閑的Worker請(qǐng)求任務(wù)時(shí),Master會(huì)選擇一個(gè)最早提交并且優(yōu)先級(jí)最高的任務(wù)分配給該Worker節(jié)點(diǎn)。該算法簡單,容易實(shí)現(xiàn),但由于不對(duì)用戶任務(wù)進(jìn)行區(qū)分,并且云中用戶任務(wù)調(diào)度的優(yōu)先級(jí)和QoS要求各不相同,很難同時(shí)滿足不同用戶的QoS要求。

2) 公平調(diào)度算法[6]。公平調(diào)度算法(Fair Scheduling, FS)保證任務(wù)一個(gè)提交作業(yè)的用戶在一定時(shí)間內(nèi)得到響應(yīng),有很好的公平性和效率。按照該算法,當(dāng)只有一個(gè)作業(yè)提交到系統(tǒng)后,整個(gè)系統(tǒng)的所有計(jì)算資源都會(huì)被這個(gè)作業(yè)獨(dú)占。當(dāng)有新作業(yè)提交時(shí),原作業(yè)所占資源中已經(jīng)完成任務(wù)的Worker會(huì)被釋放,供那些新提交的作業(yè)使用。

3) 計(jì)算能力調(diào)度算法[7]。計(jì)算能力調(diào)度算法(Capacity Scheduling, CS)通過建立作業(yè)隊(duì)列來管理和維護(hù)作業(yè)。該算法的核心思想是按照各個(gè)隊(duì)列不同的需求將相應(yīng)的資源分配出去,保證各個(gè)作業(yè)都能占用各自需要的資源。

這3種算法較為簡單,但性能不佳,存在QoS(Quality of Service)差、頻繁調(diào)度、資源碎片多、不夠靈活等弊端,而且任務(wù)隊(duì)伍和資源池配額受人為設(shè)置影響。

2.3 啟發(fā)式任務(wù)調(diào)度算法

云計(jì)算任務(wù)調(diào)度本質(zhì)上是一種組合優(yōu)化類的NP-Hard問題,很難在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)求得全局最優(yōu)解。隨著資源和任務(wù)的急劇增加,傳統(tǒng)的任務(wù)調(diào)度算法已經(jīng)難以很好地滿足實(shí)際應(yīng)用的需求。針對(duì)此問題,很多研究者提出了不同的改進(jìn)算法,這些算法中除了改進(jìn)一些經(jīng)典調(diào)度算法外,也逐漸被引入啟發(fā)式優(yōu)化算法。啟發(fā)式算法能在一個(gè)較短的時(shí)間內(nèi)得到一個(gè)滿意的調(diào)度方案,在短時(shí)間內(nèi)將大量用戶任務(wù)分別映射到合適的計(jì)算資源上,其中表現(xiàn)比較優(yōu)異的是遺傳算法和群智能算法中的蟻群算法和粒子群算法,這3種算法的工作原理以及在云計(jì)算任務(wù)調(diào)度中的應(yīng)用如下:

1) 遺傳算法[8]

遺傳算法(Genetic Algorithm, GA)是一種借鑒生物進(jìn)化過程中的優(yōu)勝劣汰機(jī)制而提出的一種隨機(jī)搜索算法。GA隨機(jī)生成一個(gè)固定數(shù)目的初始群體,群體中每個(gè)個(gè)體代表問題的一個(gè)解,該群體通過選擇、交叉和變異等操作,根據(jù)適者生存的原則不斷迭代進(jìn)化,進(jìn)化到一定代數(shù)的末代群體中的最優(yōu)個(gè)體即代表問題的近似最優(yōu)解。

GA的并行計(jì)算方式適合大規(guī)模運(yùn)算和對(duì)復(fù)雜系統(tǒng)進(jìn)行優(yōu)化,算法具有全局收斂性,能較快地收斂到全局近似最優(yōu)解,已經(jīng)在云計(jì)算任務(wù)調(diào)度問題中展現(xiàn)出優(yōu)越性能。Joanna等[9]在充分考慮云環(huán)境中的資源安全和信任機(jī)制問題等要素的基礎(chǔ)上,利用遺傳算法對(duì)云環(huán)境下的的資源進(jìn)行調(diào)度。張水平等[10]對(duì)遺傳算法進(jìn)行改進(jìn),避免算法陷入局部最優(yōu),并利用改進(jìn)的元胞自動(dòng)機(jī)遺傳算法對(duì)云環(huán)境下的資源進(jìn)行合理調(diào)度。Sean Marston等[11]提出一種簡單高效的遺傳算法,對(duì)云環(huán)境下的資源進(jìn)行分層排序,并根據(jù)資源利用屬性提供訪問順序。該算法在資源離散分布時(shí)容易出現(xiàn)資源搜索困難。劉愉等[12]在充分考慮云計(jì)算環(huán)境的動(dòng)態(tài)異構(gòu)性和大規(guī)模任務(wù)處理特性的基礎(chǔ)上,提出了一種基于染色體編碼方式和適應(yīng)度函數(shù)的改進(jìn)遺傳算法(IGA)對(duì)任務(wù)進(jìn)行調(diào)度。

2) 蟻群算法[13]

蟻群算法(Ant Colony Algorithm, ACA)是模擬自然界中螞蟻的群體協(xié)作覓食過程而提出的一種基于群智能的啟發(fā)式仿生算法。該算法最早被應(yīng)用于解決TSP問題,充分利用蟻群之間的信息傳遞,采用分布式正反饋機(jī)制在解路徑圖中搜索從蟻穴到食物間的最短路徑。

ACA具有全局搜索和快速收斂等優(yōu)點(diǎn),并且容易與其他方法結(jié)合,魯棒性強(qiáng),已經(jīng)在云計(jì)算任務(wù)調(diào)度問題上取得一定成績。劉永等[14]在Google公司的Map/Reduce框架上提出了2個(gè)基于蟻群優(yōu)化的資源調(diào)度策略,并在這兩個(gè)資源調(diào)度策略中引入雙向螞蟻機(jī)制。張春艷等[15]將蟻群分為搜索蟻、偵察蟻和工蟻,提出一種多態(tài)蟻群算法對(duì)云環(huán)境下的任務(wù)進(jìn)行調(diào)度,優(yōu)化目標(biāo)是最小化任務(wù)的平均完成時(shí)間。李坤[16]在考慮節(jié)點(diǎn)計(jì)算能力、網(wǎng)絡(luò)帶寬和任務(wù)難度等因素的基礎(chǔ)上,利用改進(jìn)蟻群算法對(duì)云環(huán)境下的任務(wù)進(jìn)行調(diào)度,以任務(wù)執(zhí)行時(shí)間和負(fù)載均衡為優(yōu)化目標(biāo)。查英華等[17]提出了一種增強(qiáng)蟻群算法對(duì)云環(huán)境下的任務(wù)進(jìn)行調(diào)度,在優(yōu)化任務(wù)完成時(shí)間同時(shí)兼顧了負(fù)載均衡。

3) 粒子群算法[18]

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)是模擬鳥群覓食過程而提出的一種基于群智能的隨機(jī)優(yōu)化算法。PSO是一種基于迭代的優(yōu)化工具,系統(tǒng)初始化為一組隨機(jī)解,通過更新速度和位置來不斷進(jìn)化到全局最優(yōu)解。

PSO具有簡單通用、可調(diào)參數(shù)少、優(yōu)化性能高等優(yōu)點(diǎn),是目前計(jì)算智能領(lǐng)域的一個(gè)研究熱點(diǎn),并且已經(jīng)被應(yīng)用于很多領(lǐng)域的優(yōu)化問題中,也成功應(yīng)用于云計(jì)算任務(wù)調(diào)度問題。Suraj等[19]在考慮任務(wù)之間的依賴關(guān)系的基礎(chǔ)上,利用粒子群算法對(duì)云計(jì)算環(huán)境中的資源進(jìn)行調(diào)度。劉萬軍等[20]在粒子群優(yōu)化算法中引入變異粒子逆向飛行思想和動(dòng)態(tài)多群體協(xié)作以提高全局搜索能力,提出一種改進(jìn)粒子群算法對(duì)云計(jì)算資源進(jìn)行調(diào)度。王登科等[21]提出一種基于粒子群優(yōu)化和蟻群優(yōu)化的任務(wù)調(diào)度算法,以總?cè)蝿?wù)完成時(shí)間最小為優(yōu)化目標(biāo)。李依桐等[22]提出一種混合粒子群優(yōu)化算法用于云任務(wù)調(diào)度,以最小化工作流費(fèi)用為優(yōu)化目標(biāo)。算法中引入遺傳算法的交叉和變異思想,并結(jié)合隨迭代次數(shù)變化的變異指數(shù),保證種群進(jìn)化初期具有較高的全局搜索能力,避免陷入局部最優(yōu)。

4) 其他智能算法

差分演化算法(Differential Evolution, DE)是一種新興的基于群體進(jìn)化的計(jì)算技術(shù),通過模擬生物進(jìn)化過程中個(gè)體間的合作與競爭來實(shí)現(xiàn)對(duì)復(fù)雜優(yōu)化問題的求解,是一種具有保優(yōu)思想的貪婪遺傳算法。該算法實(shí)現(xiàn)簡單、全局優(yōu)化能力強(qiáng),但不能直接用于離散問題[23]。朱宇航根據(jù)云計(jì)算任務(wù)調(diào)度問題的特點(diǎn),對(duì)基本差分演化算法進(jìn)行離散化改進(jìn),并將改進(jìn)的離散差分演化算法(TC-MDDE)應(yīng)用于滿足用戶QoS需求的云計(jì)算任務(wù)調(diào)度問題[3]。

人工峰群算法(Artificial Bee Colony, ABC)是一種模仿蜜蜂行為的群智能優(yōu)化算法,通過蜂群覓食過程中不同分工的蜜蜂之間的信息共享和交流而實(shí)現(xiàn)問題空間的尋優(yōu)[24]。ABC具有計(jì)算簡單、參數(shù)少、容易實(shí)現(xiàn)等優(yōu)點(diǎn),成為云計(jì)算任務(wù)調(diào)度問題的一種新工具。卓濤等提出一種基于改進(jìn)人工蜂群算法(IABC)對(duì)云計(jì)算資源調(diào)度模型進(jìn)行求解,將個(gè)體當(dāng)前最優(yōu)值及隨機(jī)向量引入到蜂群搜索過程中以加快搜索速度。該算法提高了云計(jì)算資源利用率,并且減少了任務(wù)的執(zhí)行時(shí)間[25]。

人工魚群算法(Artificial Fish-warm Algorithm, AFA)是一種基于動(dòng)物自治體的優(yōu)化方法,根據(jù)水域中魚生存數(shù)目最多的地方就是本水域中富含營養(yǎng)物質(zhì)最多的地方這一特點(diǎn)來模擬魚群的覓食行為而實(shí)現(xiàn)尋優(yōu)。AFA不需要了解問題的特殊信息,只需要對(duì)問題進(jìn)行優(yōu)劣的人工魚個(gè)體的局部尋優(yōu)行為,達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來的目的,收斂速度快[26]。孫文等提出了一種基于郭濤思想的AFA對(duì)云計(jì)算環(huán)境下的任務(wù)實(shí)現(xiàn)調(diào)度,該算法主要優(yōu)化總?cè)蝿?wù)的完成時(shí)間,同時(shí)也把任務(wù)平均完成時(shí)間作為一個(gè)必要的參考量[27]。

蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是一種通過啟發(fā)性搜索來尋找全局最優(yōu)解的新型群體智能優(yōu)化算法[28],該算法結(jié)合了基于個(gè)體所帶模因(meme)進(jìn)化的模因演化算法和粒子群優(yōu)化算法的優(yōu)點(diǎn),先通過子群內(nèi)部尋優(yōu),再通過子群間的混合來交換全局信息實(shí)現(xiàn)全局尋優(yōu)。該算法具有高效的計(jì)算性能和優(yōu)良的全局搜索能力,主要應(yīng)用于解決多目標(biāo)優(yōu)化問題。駱劍平等改進(jìn)SFLA對(duì)云計(jì)算資源進(jìn)行調(diào)度,提出了2種不同的編碼結(jié)構(gòu)以及相應(yīng)的更新方程,并根據(jù)調(diào)度方案的QoS值進(jìn)行個(gè)體間的優(yōu)勝劣汰,最后得到最佳調(diào)度。該調(diào)度方案只考慮任務(wù)完成時(shí)間和帶寬資源,沒有考慮其他參數(shù)[29]。

人工螢火蟲算法(Artificial Firefly Algorithm,AFA)是受自然界中的螢火蟲通過螢光進(jìn)行信息交流這種群體行為的啟發(fā)演變而來的一種新型仿生優(yōu)化算法,該算法將搜索和優(yōu)化過程模擬成螢火蟲個(gè)體的吸引和移動(dòng)過程,通過求解問題的目標(biāo)函數(shù)量化各個(gè)個(gè)體位置的優(yōu)劣。該算法具有參數(shù)少、實(shí)現(xiàn)簡單、計(jì)算速度快等優(yōu)點(diǎn),在生產(chǎn)調(diào)度和路徑規(guī)劃等方面具有廣闊的應(yīng)用前景[30]。劉運(yùn)等[31]在人工螢火蟲算法的基礎(chǔ)上,引入高斯變異的概念以提高算法的搜索精度和收斂速度,并將改進(jìn)后的算法運(yùn)用到云計(jì)算環(huán)境下的資源進(jìn)行調(diào)度問題中,解決云計(jì)算中資源分配不均的問題。實(shí)驗(yàn)證明該算法能有效縮短云計(jì)算任務(wù)的完成時(shí)間。

啟發(fā)式任務(wù)調(diào)度算法雖然可以較好地對(duì)云環(huán)境下的任務(wù)進(jìn)行調(diào)度,但優(yōu)化目標(biāo)大多是單一地降低任務(wù)執(zhí)行時(shí)間、降低成本或改善負(fù)載平衡等,沒有綜合考慮實(shí)際應(yīng)用中更多的復(fù)雜因素,比如計(jì)算成本、用戶多樣化需求、網(wǎng)絡(luò)延遲、故障處理、節(jié)能環(huán)保等,并且通常存在著收斂性能或全局最優(yōu)解搜索能力較低的缺點(diǎn),算法的收斂速度和計(jì)算精度有待進(jìn)一步提高。此外,在啟發(fā)式任務(wù)調(diào)度算法中,如果僅僅采用一種優(yōu)化算法,得到的結(jié)果往往不是很理想,因此需要在啟發(fā)式算法中結(jié)合其他優(yōu)化技術(shù),形成混合算法,以使其對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度在綜合性能上達(dá)到最優(yōu)。

3 云計(jì)算調(diào)度算法的研究展望

目前的云計(jì)算任務(wù)調(diào)度主要存在著優(yōu)化目標(biāo)單一和算法性能不高這2方面問題,可以從模型高效和算法高效2個(gè)層面出發(fā),綜合考慮云計(jì)算的時(shí)間、成本、成功率、網(wǎng)絡(luò)故障等約束條件,兼顧云計(jì)算用戶和運(yùn)營商雙方的利益,構(gòu)建多目標(biāo)優(yōu)化模型,并利用改進(jìn)的算法對(duì)模型進(jìn)行求解。

3.1 構(gòu)建適合云環(huán)境下的任務(wù)調(diào)度模型,提出多個(gè)目標(biāo)的優(yōu)化

云計(jì)算任務(wù)調(diào)度主要采用的性能指標(biāo)有:最優(yōu)時(shí)間跨度(optimal makespan)、服務(wù)質(zhì)量(quality of service)、負(fù)載均衡(load balancing)和經(jīng)濟(jì)原則(economic principles)等。從用戶角度上考慮的是任務(wù)執(zhí)行時(shí)間、可靠性、經(jīng)濟(jì)成本等約束條件,并且用戶偏好多樣,目標(biāo)約束條件通常會(huì)包含多個(gè)指標(biāo)的要求;從服務(wù)提供商角度考慮的是降低能耗、減少開銷、提高資源利用率等。

針對(duì)傳統(tǒng)云計(jì)算任務(wù)調(diào)度算法優(yōu)化目標(biāo)單一的問題,提出同時(shí)將任務(wù)執(zhí)行時(shí)間、執(zhí)行費(fèi)用以及資源負(fù)載均衡等多個(gè)因素同時(shí)作為調(diào)度的優(yōu)化目標(biāo),建立有效靈活的多目標(biāo)優(yōu)化模型,保障系統(tǒng)選擇最佳的任務(wù)調(diào)度,最大化地滿足用戶多樣化需求并最大化地提高云服務(wù)提供者的資源利用率和經(jīng)濟(jì)效益,達(dá)到互利共贏。

3.2 改進(jìn)任務(wù)調(diào)度策略,提高算法性能

目前對(duì)云計(jì)算任務(wù)調(diào)度算法的研究仍處于探索階段,每一種調(diào)度算法都有其應(yīng)用領(lǐng)域和局限性,還沒有一種能適用于所有領(lǐng)域,同時(shí)獲得最佳調(diào)度效果的任務(wù)調(diào)度算法。

相對(duì)于傳統(tǒng)任務(wù)調(diào)度算法,啟發(fā)式算法具有更高的優(yōu)化效率,特別是群智能算法,其潛在的并行性和分布式的特點(diǎn)為處理海量數(shù)據(jù)提供了技術(shù)保證[32]。在對(duì)云計(jì)算環(huán)境下的多目標(biāo)任務(wù)調(diào)度問題的特點(diǎn)進(jìn)行詳細(xì)分析的基礎(chǔ)上,應(yīng)該進(jìn)一步對(duì)群智能算法(ACA、PSO、DE、ABC、AFA和SFLA等)進(jìn)行改進(jìn),充分調(diào)查群算能算法的參數(shù),對(duì)參數(shù)做出合理設(shè)置,根據(jù)群智能算法的優(yōu)缺點(diǎn),在群智能中加入其他優(yōu)化技術(shù),采用相應(yīng)的混合策略使各算法有效結(jié)合,取長補(bǔ)短,不斷提高算法的優(yōu)化性能,并將這些改進(jìn)后高效的混合群智能算法運(yùn)用到云環(huán)境下多目標(biāo)優(yōu)化的任務(wù)調(diào)度模型中,為用戶任務(wù)做出合理調(diào)度,使任務(wù)執(zhí)行時(shí)間短,費(fèi)用低,能夠有效應(yīng)對(duì)資源進(jìn)入退出、節(jié)點(diǎn)失效、資源故障這些突發(fā)事件,滿足用戶多樣化需求,提高任務(wù)執(zhí)行成功率。并且能夠平衡系統(tǒng)負(fù)載,提高資源利用率,節(jié)約成本,進(jìn)而提高云服務(wù)提供商的效益,同時(shí)滿足多個(gè)目標(biāo)的優(yōu)化。

4 結(jié) 語

云計(jì)算任務(wù)調(diào)度算法決定了整個(gè)云計(jì)算系統(tǒng)的運(yùn)行效率和工作性能,對(duì)云計(jì)算任務(wù)調(diào)度算法進(jìn)行研究對(duì)于提高云計(jì)算系統(tǒng)的服務(wù)能力具有重要的理論價(jià)值和現(xiàn)實(shí)意義。本文對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度算法做了分析和比較,重點(diǎn)闡述了啟發(fā)式算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用現(xiàn)狀。結(jié)合云技術(shù)的發(fā)展趨勢,指出構(gòu)建多目標(biāo)優(yōu)化的云任務(wù)調(diào)度模型的必要性,針對(duì)目前使用的任務(wù)調(diào)度算法的不足,提出利用改進(jìn)的混合群智能算法對(duì)云環(huán)境下的多目標(biāo)任務(wù)調(diào)度模型進(jìn)行優(yōu)化的思路,使云計(jì)算中的任務(wù)調(diào)度更科學(xué),保證云平臺(tái)高效率運(yùn)行。

[ 1 ]劉鵬. 云計(jì)算[M]. 2版. 北京:電子工業(yè)出版社, 2011:1-15.

[ 2 ]MICHAEL A, ARMANDO F, REAN G, et al. Above the clouds: a Berkeley view of cloud computing[M]. Berkeley: University of California, 2009:1-23.

[ 3 ]朱宇航. 差分進(jìn)化算法及其在云計(jì)算任務(wù)調(diào)度中的應(yīng)用研究[D]. 蘭州:蘭州交通大學(xué), 2013.

[ 4 ]BRAUN T D, SIEGEL H J, BECK N. A comparsion of eleven static heristics for mapping a class of independent tasks onto heterogonous distributed computing systems[J]. Parallel and Distributed Computing, 2001,61(1):810-837.

[ 5 ]鄭愛卿. 基于執(zhí)行時(shí)間方差的元任務(wù)網(wǎng)格調(diào)度算法研究[D]. 北京:北京交通大學(xué), 2008.

[ 6 ]ISARD M, PRABHAKARAN V, CURREY J, et al. Fair scheduling for distributed computing clusters[C]∥Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles, New York:ACM, 2009:261-276.

[ 7 ]遆鳴. 云計(jì)算下計(jì)算能力調(diào)度算法的研究和改進(jìn)[D]. 太原:太原理工大學(xué), 2012.

[ 8 ]HOLLAND J H. Adaptation in Nature and Artificial Systems[M]. Boston: MIT Press, 1992.

[ 9 ]JOANNA K, FATOS X, MARCIN B. Secure and task abortion aware GA-based hybridmetaheuristics for grid scheduling[J]. Computer Science, 2010,1:526-535.

[10]張水平,鄔海艷. 基于元胞自動(dòng)機(jī)遺傳算法的云資源調(diào)度[J]. 計(jì)算機(jī)工程, 2012,38(11):11-13.

[11]SEAN M, ZHI L, SUBBAJYOTI B. Cloud computing-the business perspective[J]. Decision Support Systems, 2011,51(1):176-189.

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

[13]DORIGO M, MANIEZZO V, COLOMI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on System, Man and Cybernetics, 1996,26(1):29-41.

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

[15]張春艷,劉清林,孟珂. 基于蟻群算法的云計(jì)算任務(wù)分配[J]. 計(jì)算機(jī)應(yīng)用, 2012,32(5):1418-1420.

[16]李坤. 云環(huán)境下的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D]. 長春:吉林大學(xué), 2012.

[17]查英華,楊靜麗. 改進(jìn)蟻群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2013,34(5):1716-1719.

[18]KENNEDY J, EBERHART R. C. Particle Swarm Optimization [C]∥Proceedings of the IEEE International Conference on Neural Networks, Piscataway: IEEE,1995:1942-1948.

[19]PANDEY S, WU L, GURU M, et al. A particle swarm optimization-based heuristic for scheduling workflow application in cloud computing environments[C]∥24th IEEE International Conference on Advanced Information Networking and Applications, Piscataway: IEEE, 2010:1109-1119.

[20]劉萬軍,張孟華,郭文越. 基于MPSO算法的云計(jì)算資源調(diào)度策略[J]. 計(jì)算機(jī)工程, 2011,37(11):43-44.

[21]王登科,李忠. 基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013,30(1):290-293.

[22]李依桐,林燕. 基于混合粒子群算法的云計(jì)算任務(wù)調(diào)度研究[J]. 計(jì)算技術(shù)與自動(dòng)化, 2014,33(1):73-77.

[23]STORN R, PRICE K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces[J]. J Global Optimization, 1997,11(4):341-359.

[24]KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR Filters [J]. J Franklin Institute, 2009,346(4):328-348.

[25]卓濤,詹穎. 改進(jìn)人工蜂群算法的云計(jì)算資源調(diào)度模型[J]. 微電子學(xué)與計(jì)算機(jī), 2014,31(7):147-150.

[26]李曉磊,邵之江,錢積新. 一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2002,22(11):32-38.

[27]孫文新. 人工魚群優(yōu)化在云計(jì)算環(huán)境中任務(wù)調(diào)度算法[J]. 安徽農(nóng)業(yè)科學(xué), 2012,40(11):6923-6929.

[28]EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management, 2003,129(3):210-225.

[29]駱劍平,李霞,陳泯融. 云計(jì)算環(huán)境中基于混合蛙跳算法的資源調(diào)度[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012,48(29):67-72.

[30]GROSSMAN R L. The case of cloud computing[J]. IT Professional, 2009,11(2):23-27.

[31]劉運(yùn),程家興,林京. 基于高斯變異的人工螢火蟲算法在云計(jì)算資源調(diào)度中的研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015,32(3):834-837.

[32]CHRISTIAN B, DANIEL M. 群智[M]. 龍飛,譯. 北京:國防工業(yè)出版社, 2010.

Study of task scheduling algorithm on cloud computing

HUANGShaorong

(Department of Information Management, Guangdong Justice Police Vocational College, Guangzhou 510520, China)

Cloud computing is a new business computing model which uses large-scale virtualized resources to provide services through the computer network. In the cloud computing environment, the users are multitudinous, and the number of tasks and the amounts of data are huge, and the structure of cloud computing system is very complex, and it is a difficult problem to be resolved to schedule tasks efficiently. Task scheduling algorithm determines the execution efficiency of user tasks and use efficiency of system resources, and is directly related to the integral stability and overall effect. After the analysis and comparison of the cloud computing scheduling strategies, based on two aspects of model efficiency and algorithm efficiency, this paper points out the development trend of cloud computing task scheduling algorithm, and proposes cloud computing task scheduling model based on multi-objective optimization.

cloud computing; task scheduling; heuristic algorithm; multi-objective optimization; swarm intelligence

2014-10-10。

廣東省科技廳自然科學(xué)基金資助項(xiàng)目(101754539192000000)。

黃少榮(1976-),女,廣東饒平人,廣東司法警官職業(yè)學(xué)院副教授,碩士。

1673-5862(2015)03-0417-06

TP306.1

A

10.3969/ j.issn.1673-5862.2015.03.022