基于改進GA的云計算任務調度算法

朱宗斌，杜中軍

四川大學 計算機學院，成都 610065

基于改進GA的云計算任務調度算法

朱宗斌，杜中軍

四川大學 計算機學院，成都 610065

1 引言

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

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

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

2 任務調度問題的定義

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

云計算中的資源包括處理器、存儲器、網絡等，資源的使用是按需使用、按使用量付費的。本文將云計算中的資源統一視為計算資源，并作如下假設：

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

（2）子任務的數量遠大于資源的數量。

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

（4）各個計算資源節點上任務運行單元時間所需的成本已知。

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

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

3 TCGA任務調度算法

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

3.1 染色體的編碼與解碼

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

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

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

圖1 資源-任務編碼

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

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

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

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

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

3.2 初始種群的生成

取種群規模為S，資源數為M，子任務數為N，則初始化描述為：由系統隨機產生S條染色體，染色體長度為N，基因值為[1，M]之間的隨機數。

3.3 適應度函數

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

定義時間的適應度函數為：

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

定義成本的適應度函數為：

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

其中，α∈[0，1]，β∈[0，1]，α+β=1。取α=1，β=0時，算法調度產生的結果為完成所有子任務的最短時間調度；取α=0，β=1時，算法調度產生的結果為完成所有子任務最小成本調度。

3.4 遺傳操作

3.4.1 選擇操作

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

適應度函數考慮了任務調度的時間和成本約束，通過上述選擇操作，使得種群中既有任務完成時間較短的個體，又有任務完成成本較小的個體。

3.4.2 交叉與變異操作

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

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

3.5 TCGA重新調度

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

4 實驗結果與分析

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

表1 實驗參數設置

算法的初始條件：S取值為60，M取值為5，N取值為1 000，ETC矩陣和RCU數組由系統隨機生成。

算法的終止條件：考慮到用遺傳算法對任務進行調度自身運行的開銷，設置最大進化代數（MaxGn）為100，而不等待算法自身收斂，算法終止。

實驗結果如圖2、圖3所示。

圖2 總任務完成時間對比

圖3 總任務完成成本對比

從圖2可以看出，在遺傳算法進化初期，TCGA與TGA、CGA運行產生的最優子任務調度結果所需的總任務完成時間相差不大。隨著進化代數的增長，TCGA和TGA調度結果對總任務完成時間的優化越加明顯，而CGA調度結果對總任務完成時間無明顯的優化作用。

從圖3可以看出，在遺傳算法進化初期，TCGA與TGA、CGA運行產生的最優子任務調度結果所需的總任務完成成本相差不大。隨著進化代數的增長，TCGA和CGA調度結果對總任務完成時間的優化越加明顯，而TGA調度結果對總任務完成時間無明顯的優化作用。

綜上所述，TGA得到的子任務調度結果可以取得最短的總任務完成時間，而對任務完成成本的優化作用不明顯；CGA得到的子任務調度結果可以取得最小的總任務完成成本，而對任務完成時間的優化作用不明顯；TCGA同時考慮了時間-成本對算法的約束，故得到的子任務調度的結果，使得總任務完成時間較短、成本較小。

5 結束語

任務調度算法通常以總任務完成時間作為標準對任務進行調度，本文結合云計算的特點，提出了一種考慮時間-成本約束的遺傳算法的任務調度算法，該算法把總任務完成時間和總任務完成成本同時作為標準，對任務進行調度。實驗結果表明，通過本算法可以在云計算平臺中實現較為合理的任務調度，并產生理想的任務調度結果。

在未來的工作中，將把重點放在云計算中動態任務調度的資源負載均衡上，并考慮云計算中其他資源，如網絡服務質量、數據分布等因素對任務調度結果的影響。

[1]陳康，鄭緯民.云計算：系統實例與研究現狀[J].軟件學報，2009，20（5）：1337-1348.

[2]Armbrust M，Fox 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]羅紅，慕德俊，鄧智群，等.網格計算中任務調度研究綜述[J].計算機應用研究，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]林劍檸，吳慧中.基于遺傳算法的網格資源調度算法[J].計算機研究與發展，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]王小平，曹立明.遺傳算法——理論、應用于軟件實現[M].西安：西安交通大學出版社，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

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

云計算；遺傳算法；任務調度；時間；成本

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—），男，碩士研究生，研究方向：計算機網絡；杜中軍（1965—），男，副教授，碩士生導師，研究方向：計算機網絡。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