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

朱宗斌，杜中軍

四川大學(xué) 計算機(jī)學(xué)院，成都 610065

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

朱宗斌，杜中軍

四川大學(xué) 計算機(jī)學(xué)院，成都 610065

1 引言

云計算概念提出以來就成為一個熱點研究方向。文獻(xiàn)[1]綜述了當(dāng)前云計算所采用的技術(shù)，剖析其背后的技術(shù)含義以及當(dāng)前云計算參與企業(yè)所采用的云計算實現(xiàn)方案，并對工業(yè)界3個具體的云計算實例，具體包括Google的云計算平臺以及云計算的網(wǎng)絡(luò)應(yīng)用程序、IBM公司的“藍(lán)云”平臺產(chǎn)品以及Amazon公司的彈性計算云進(jìn)行了研究。文獻(xiàn)[2]對云計算的概念進(jìn)行了定義，并對云計算發(fā)展所面臨的問題與機(jī)遇作了分析與描述。

云計算提供了基礎(chǔ)設(shè)施、平臺和軟件的服務(wù)，其基本原理是通過網(wǎng)絡(luò)將計算處理任務(wù)拆分成多個較小子任務(wù)，再由多個服務(wù)器組成的龐大系統(tǒng)搜索、計算分析后將處理結(jié)果回傳給用戶[3]。云計算可視為分布式計算、并行計算、網(wǎng)格計算的發(fā)展，并在商業(yè)領(lǐng)域得以實現(xiàn)。文獻(xiàn)[4]全面比較了網(wǎng)格計算和云計算，并指出云計算“按需使用，按量付費”的商業(yè)模型。

由于云計算所面對的計算任務(wù)數(shù)量十分龐大，任務(wù)調(diào)度和資源分配問題是決定云計算效率的重點與難點。目前，對云計算中任務(wù)調(diào)度和資源分配的相關(guān)研究不多，而網(wǎng)格計算已經(jīng)對相關(guān)問題進(jìn)行了廣泛的研究[5-8]，在一定程度上，兩者具有相似性。網(wǎng)格計算中任務(wù)調(diào)度算法的一個最主要目標(biāo)就是使所有任務(wù)運(yùn)行完成所需要的時間最小，大多數(shù)的任務(wù)調(diào)度算法都是以這一目標(biāo)來對任務(wù)調(diào)度進(jìn)行優(yōu)化的。然而，在云計算模型中，任務(wù)執(zhí)行所需要的成本也是一個不可忽略的因素，不同計算能力的資源，其使用成本也不同。對于時間敏感的應(yīng)用，提供較強(qiáng)處理能力的資源，使得任務(wù)運(yùn)行完成所需的時間較短；對于成本敏感的用戶應(yīng)用，提供較低處理成本的資源，使得任務(wù)運(yùn)行完成所需的成本較低。本文通過研究如何對云計算中的資源進(jìn)行合理的分配，任務(wù)進(jìn)行高效的調(diào)度問題，提出了一種考慮時間-成本約束的基于遺傳算法的任務(wù)調(diào)度算法（Time and Cost constraints Genetic Algorithm，TCGA），并通過實驗，驗證了算法的有效性。

2 任務(wù)調(diào)度問題的定義

目前，大部分云計算平臺都采用Google提出的Map/ Reduce編程模型，用于大規(guī)模數(shù)據(jù)集的并行計算。通過Map和Reduce兩個階段，將較大的任務(wù)分割成為多個較小的子任務(wù)，然后分配給多個計算資源并行執(zhí)行，并得到最終的運(yùn)行結(jié)果。在Map/Reduce編程模型下，如何對數(shù)量眾多的子任務(wù)進(jìn)行調(diào)度是個復(fù)雜的問題。云計算同時需要向多個用戶提供服務(wù)，要考慮到每個用戶的響應(yīng)時間，同時，也要考慮到服務(wù)所需的成本。已有的一些調(diào)度算法通常只考慮了其中一個因素的優(yōu)化，容易造成任務(wù)完成時間較為短，而成本較為高的情況。因此本文提出TCGA對云計算中任務(wù)調(diào)度和資源分配策略進(jìn)行改進(jìn)，以最大限度地提高云計算效率。

云計算中的資源包括處理器、存儲器、網(wǎng)絡(luò)等，資源的使用是按需使用、按使用量付費的。本文將云計算中的資源統(tǒng)一視為計算資源，并作如下假設(shè)：

（1）任務(wù)的輸入是多個較大的計算任務(wù)分解成的一批子任務(wù)，子任務(wù)劃分的粒度均勻，即所需要運(yùn)行的時間差異不大。

（2）子任務(wù)的數(shù)量遠(yuǎn)大于資源的數(shù)量。

（3）子任務(wù)在各個計算資源上運(yùn)行所需的時間已知。

（4）各個計算資源節(jié)點上任務(wù)運(yùn)行單元時間所需的成本已知。

用N表示子任務(wù)的數(shù)量，M表示計算資源的數(shù)量，并用M×N的ETC（Expect Time to Complete）矩陣[9]（ETC（i，j）表示第j個子任務(wù)在第i個計算資源上運(yùn)行完成所需的時間）來計算各個計算資源上任務(wù)隊列運(yùn)行完成所需要的時間。用RCU（i）（Resource Cost per Unit）表示各個計算資源單元時間任務(wù)運(yùn)行的成本。子任務(wù)用Tj表示，計算資源用Pi表示，那么子任務(wù)實例可以描述為(Tj，Pi，ETC(i，j)，RCU(j))(i∈[1，M]，j∈[1，N])。

在以上假設(shè)條件下，可將云計算中任務(wù)調(diào)度問題定義為如何合理地將子任務(wù)分配到各個計算資源，使得任務(wù)運(yùn)行完成所需的時間較短、成本較小。

3 TCGA任務(wù)調(diào)度算法

遺傳算法（Genetic Algorithm，GA）是由Holland教授受到生物模擬技術(shù)的啟發(fā)，創(chuàng)造出的一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化的自適應(yīng)概率優(yōu)化技術(shù)。其本質(zhì)是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最優(yōu)解[10]。

3.1 染色體的編碼與解碼

染色體的編碼有很多種方式，可以采用直接編碼（對任務(wù)的執(zhí)行狀態(tài)編碼），也可以采用間接編碼。本文采用文獻(xiàn)[8]中提出資源-任務(wù)的間接編碼方式，對子任務(wù)占用的資源編碼。染色體的長度為子任務(wù)的數(shù)量，染色體中每個基因的取值為該位置對應(yīng)的子任務(wù)占用的資源編號，如圖1所示。其中，Ti表示任務(wù)編號，Pi表示任務(wù)Ti執(zhí)行時占用的資源編號。在產(chǎn)生初始種群時，每一個染色體中的資源編號Pi都是隨機(jī)產(chǎn)生的，經(jīng)過交叉、變異算子后，子任務(wù)Ti可能占用任何一個可用的資源，所以最優(yōu)解一定對應(yīng)某一個染色體編碼。假設(shè)有10個子任務(wù)，3個可用資源，則染色體長度為10，每個基因取值為1～3之間的隨機(jī)數(shù)，如隨機(jī)產(chǎn)生如下的染色體編碼：

{2，1，2，1，3，1，3，3，2，3}

則這個染色體代表第1個子任務(wù)在第2個資源上運(yùn)行，第2個子任務(wù)在第1個資源上運(yùn)行，以此類推，第10個子任務(wù)在第3個資源上運(yùn)行。

圖1 資源-任務(wù)編碼

產(chǎn)生染色體后，還必須對其進(jìn)行解碼，得到不同資源上子任務(wù)的分布情況。將子任務(wù)按照占用的資源分類，生成多組按照資源編號分類的子任務(wù)序列。將上述染色體解碼為：

通過解碼得到分配到各個計算資源上子任務(wù)的序列，利用ETC矩陣，可以計算得到各個計算資源完成子任務(wù)序列所需要的時間。由于云計算中各個計算資源間具有并發(fā)處理的特性，取上述計算結(jié)果的最大值，即為所有子任務(wù)運(yùn)行完成的時間：

其中，n表示被分配到各個計算資源上的子任務(wù)數(shù)量，Time(i，j)表示被分配到計算資源Pi上的第j個子任務(wù)執(zhí)行完成所需的時間。此時，利用上面求得的sumTime(i)，結(jié)合RCU(i)可以求得完成所有子任務(wù)所需要的成本：

本文提出的任務(wù)調(diào)度算法需要同時考慮所有子任務(wù)完成的時間與成本，在此利用貪心算法，求得所有子任務(wù)運(yùn)行完成所需的最大時間與最大成本約束分別為：

其中，completeTimeMIN與completeCostMIN是根據(jù)子任務(wù)在各個計算資源上運(yùn)行完成所需的最小時間與最小成本來進(jìn)行貪心選擇得到的結(jié)果；而completeTimeMAX與completeCostMAX則正好相反，是根據(jù)子任務(wù)在各個計算資源上運(yùn)行完成所需的最大時間與最大成本來進(jìn)行貪心選擇得到的結(jié)果。公式（4）中的t∈[0，1]為時間因子，公式（5）中的c∈[0，1]為成本因子，它們的值由用戶根據(jù)需求指定，且t和c成反比關(guān)系。對時間敏感的應(yīng)用，t應(yīng)指定為較小的[0.2，0.5]之間的值，而c應(yīng)指定為較大的[0.5，0.8]之間的值；對成本敏感的應(yīng)用，c應(yīng)指定為較小的[0.2，0.5]之間的值，而t應(yīng)指定為較大的[0.5，0.8]之間的值。

3.2 初始種群的生成

取種群規(guī)模為S，資源數(shù)為M，子任務(wù)數(shù)為N，則初始化描述為：由系統(tǒng)隨機(jī)產(chǎn)生S條染色體，染色體長度為N，基因值為[1，M]之間的隨機(jī)數(shù)。

3.3 適應(yīng)度函數(shù)

遺傳算法適應(yīng)度函數(shù)的選取至關(guān)重要，直接影響到遺傳算法的收斂速度與最優(yōu)解的查找。適應(yīng)度較大的個體遺傳到下一代的概率就越大；而適應(yīng)度較小的個體遺傳到下一代的概率就相對小一些。任務(wù)調(diào)度需要考慮所有子任務(wù)完成所需要的時間和成本。

定義時間的適應(yīng)度函數(shù)為：

公式（6）中的uLB定義為平衡任務(wù)負(fù)載因子，其值可由公式（7）求得，它代表各個計算資源的利用率情況。uLB的值越大，表示計算資源的利用率越高，那么completeTime(I)的值就會相對越小。

定義成本的適應(yīng)度函數(shù)為：

在只考慮時間約束的適應(yīng)度函數(shù)中，計算資源的利用率越高，所有子任務(wù)運(yùn)行完成所需時間越短的個體，其適應(yīng)度的值越大；在只考慮成本約束的適應(yīng)度函數(shù)中，所有子任務(wù)運(yùn)行完成所需成本越低的個體，其適應(yīng)度的值越大。那么，可定義考慮時間-成本約束的適應(yīng)度函數(shù)為：

其中，α∈[0，1]，β∈[0，1]，α+β=1。取α=1，β=0時，算法調(diào)度產(chǎn)生的結(jié)果為完成所有子任務(wù)的最短時間調(diào)度；取α=0，β=1時，算法調(diào)度產(chǎn)生的結(jié)果為完成所有子任務(wù)最小成本調(diào)度。

3.4 遺傳操作

3.4.1 選擇操作

選擇操作在種群中選擇適應(yīng)度強(qiáng)的個體，以產(chǎn)生新的種群的過程。根據(jù)“優(yōu)勝劣汰”的原理，個體的適應(yīng)度越高，被選擇遺傳到下一代的概率就越大，使得種群中個體的適應(yīng)度值不斷接近最優(yōu)解。TCGA采用輪盤賭選擇作為選擇操作算子，通過適應(yīng)度計算公式（9）計算出個體被選擇的概率。

適應(yīng)度函數(shù)考慮了任務(wù)調(diào)度的時間和成本約束，通過上述選擇操作，使得種群中既有任務(wù)完成時間較短的個體，又有任務(wù)完成成本較小的個體。

3.4.2 交叉與變異操作

交叉操作是產(chǎn)生新個體的主要方法，它決定了遺傳算法的全局搜索能力；而變異操作能改善遺傳算法的局部搜索能力，維持種群的多樣性，防止出現(xiàn)早熟現(xiàn)象。TCGA使用文獻(xiàn)[11]提出的自適應(yīng)遺傳算法（AGA），并對交叉概率和變異概率計算公式進(jìn)行改進(jìn)，自適應(yīng)地調(diào)整交叉和變異操作的概率。

式中，fmax表示群體中最大的適應(yīng)度值；favg表示每代群體的平均適應(yīng)度值；f′表示要交叉的兩個個體中較大的適應(yīng)度值；f表示要變異個體的適應(yīng)度值[11]。

3.5 TCGA重新調(diào)度

在每一代遺傳操作結(jié)束以后，TCGA利用算法初始時求得的MaxTime和MaxCost約束與最優(yōu)子任務(wù)調(diào)度結(jié)果的染色體進(jìn)行比較。若TCGA算法運(yùn)行產(chǎn)生的最優(yōu)子任務(wù)調(diào)度結(jié)果不滿足completeTime(I)小于等于MaxTime，或completeCost(I)小于等于MaxCost約束條件，則需要重新運(yùn)行TCGA算法產(chǎn)生新的最優(yōu)子任務(wù)調(diào)度結(jié)果。

4 實驗結(jié)果與分析

本文采用CloudSim[12]平臺來模擬云計算環(huán)境，在相同的條件下，用TCGA與TGA（Time constraints Genetic Algorithm）、CGA（Cost constraints Genetic Algorithm）進(jìn)行對比實驗。算法中各參數(shù)的取值如表1所示。

表1 實驗參數(shù)設(shè)置

算法的初始條件：S取值為60，M取值為5，N取值為1 000，ETC矩陣和RCU數(shù)組由系統(tǒng)隨機(jī)生成。

算法的終止條件：考慮到用遺傳算法對任務(wù)進(jìn)行調(diào)度自身運(yùn)行的開銷，設(shè)置最大進(jìn)化代數(shù)（MaxGn）為100，而不等待算法自身收斂，算法終止。

實驗結(jié)果如圖2、圖3所示。

圖2 總?cè)蝿?wù)完成時間對比

圖3 總?cè)蝿?wù)完成成本對比

從圖2可以看出，在遺傳算法進(jìn)化初期，TCGA與TGA、CGA運(yùn)行產(chǎn)生的最優(yōu)子任務(wù)調(diào)度結(jié)果所需的總?cè)蝿?wù)完成時間相差不大。隨著進(jìn)化代數(shù)的增長，TCGA和TGA調(diào)度結(jié)果對總?cè)蝿?wù)完成時間的優(yōu)化越加明顯，而CGA調(diào)度結(jié)果對總?cè)蝿?wù)完成時間無明顯的優(yōu)化作用。

從圖3可以看出，在遺傳算法進(jìn)化初期，TCGA與TGA、CGA運(yùn)行產(chǎn)生的最優(yōu)子任務(wù)調(diào)度結(jié)果所需的總?cè)蝿?wù)完成成本相差不大。隨著進(jìn)化代數(shù)的增長，TCGA和CGA調(diào)度結(jié)果對總?cè)蝿?wù)完成時間的優(yōu)化越加明顯，而TGA調(diào)度結(jié)果對總?cè)蝿?wù)完成時間無明顯的優(yōu)化作用。

綜上所述，TGA得到的子任務(wù)調(diào)度結(jié)果可以取得最短的總?cè)蝿?wù)完成時間，而對任務(wù)完成成本的優(yōu)化作用不明顯；CGA得到的子任務(wù)調(diào)度結(jié)果可以取得最小的總?cè)蝿?wù)完成成本，而對任務(wù)完成時間的優(yōu)化作用不明顯；TCGA同時考慮了時間-成本對算法的約束，故得到的子任務(wù)調(diào)度的結(jié)果，使得總?cè)蝿?wù)完成時間較短、成本較小。

5 結(jié)束語

任務(wù)調(diào)度算法通常以總?cè)蝿?wù)完成時間作為標(biāo)準(zhǔn)對任務(wù)進(jìn)行調(diào)度，本文結(jié)合云計算的特點，提出了一種考慮時間-成本約束的遺傳算法的任務(wù)調(diào)度算法，該算法把總?cè)蝿?wù)完成時間和總?cè)蝿?wù)完成成本同時作為標(biāo)準(zhǔn)，對任務(wù)進(jìn)行調(diào)度。實驗結(jié)果表明，通過本算法可以在云計算平臺中實現(xiàn)較為合理的任務(wù)調(diào)度，并產(chǎn)生理想的任務(wù)調(diào)度結(jié)果。

在未來的工作中，將把重點放在云計算中動態(tài)任務(wù)調(diào)度的資源負(fù)載均衡上，并考慮云計算中其他資源，如網(wǎng)絡(luò)服務(wù)質(zhì)量、數(shù)據(jù)分布等因素對任務(wù)調(diào)度結(jié)果的影響。

[1]陳康，鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀[J].軟件學(xué)報，2009，20（5）：1337-1348.

[2]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the clouds：a Berkeley view of cloud computing[EB/OL].[2009-02-10].http：// www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf.

[3]Wikipedia.云計算[EB/OL].[2010-06-26].http：//zh.wikipedia.org/ wiki/%E4%BA%91%E8%AE%1%E7%AE%97.

[4]Foster I，Zhao Y，Raicu I，et al.Cloud computing and grid computing 360-degree compared[C]//Proceedings of the 2008 GridComputingEnvironmentsWorkshop.Washington，DC：IEEE Computer Society，2008：1-10.

[5]羅紅，慕德俊，鄧智群，等.網(wǎng)格計算中任務(wù)調(diào)度研究綜述[J].計算機(jī)應(yīng)用研究，2005，22（5）：16-19.

[6]BuyyaR.Economic-based distributed resourcemanagement and scheduling for grid computing[D].Australia：School of Computer Science and Software Engineering，Monash University，2002.

[7]Abraham A，Buyya R，Nath B.Nature's heuristics for scheduling jobs on computational grids[C]//The 8th International Conference on Advanced Computing and Communications. New Delhi：Tata McGraw-Hill Publishing，2000：45-52.

[8]林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法[J].計算機(jī)研究與發(fā)展，2004，41（12）：2195-2199.

[9]Braun T D，Siegel H J，Beck N，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing，2001，61（6）：810-837.

[10]王小平，曹立明.遺傳算法——理論、應(yīng)用于軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[11]Srinivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Trans on SMC，1944，24（4）：656-667.

[12]Calheiros R N，Ranjan R，de Rose C A F，et al.CloudSim：a novel framework for modeling and simulation of cloud computing infrastructures and services[EB/OL].[2009-09-03]. http：//www.cloudbus.org/reports/CloudSim-ICPP2009.pdf.

ZHU Zongbin,DU Zhongjun

College of Computer Science,Sichuan University,Chengdu 610065,China

Cloud computing needs to manage a large number of computing tasks,while task scheduling strategy plays a key role in determining the efficiency of cloud computing.It is an important issue how to allocate computing resources reasonably and schedule tasks run effectively which can reduce the complete time and cost of all tasks.A Time and Cost constraints Genetic Algorithm（TCGA）is proposed,through which,a better scheduling result not only shortens time,but also costs less.The simulation shows that TCGA is an efficient task scheduling algorithm in cloud computing by contrast with Time constraints Genetic Algorithm（TGA）and Cost constraints Genetic Algorithm（CGA）.

cloud computing;Genetic Algorithm（GA）;task scheduling;time;cost

云計算通常需要處理大量的計算任務(wù)，任務(wù)調(diào)度策略在決定云計算效率方面起著關(guān)鍵作用。如何合理地分配計算資源，有效地調(diào)度任務(wù)運(yùn)行，使所有任務(wù)運(yùn)行完成所需的時間較短、成本較小是個重要的問題。提出一種考慮時間-成本約束的遺傳算法（TCGA），通過此算法調(diào)度產(chǎn)生的結(jié)果不僅能使任務(wù)完成所需的時間較短，而且成本較小。通過實驗，將TCGA與考慮時間約束的遺傳算法（TGA）、考慮成本約束的遺傳算法（CGA）進(jìn)行比較，實驗結(jié)果表明，該算法是云計算中一種有效的任務(wù)調(diào)度算法。

云計算；遺傳算法；任務(wù)調(diào)度；時間；成本

A

TP393

10.3778/j.issn.1002-8331.1108-0132

ZHU Zongbin,DU Zhongjun.Improved GA-based task scheduling algorithm in cloud computing.Computer Engineering and Applications,2013,49（5）：77-80.

朱宗斌（1988—），男，碩士研究生，研究方向：計算機(jī)網(wǎng)絡(luò)；杜中軍（1965—），男，副教授，碩士生導(dǎo)師，研究方向：計算機(jī)網(wǎng)絡(luò)。E-mail：zzbincd2008@163.com

2011-08-11

2011-10-18

1002-8331（2013）05-0077-04

CNKI出版日期：2011-12-09 http://www.cnki.net/kcms/detail/11.2127.TP.20111209.1002.052.html