鄧見光，趙躍龍，袁華強，劉 霖

(1.東莞理工學院工程技術(shù)研究院，廣東東莞523808;2.華南理工大學計算機科學與工程學院，廣東廣州510006)

云計算技術(shù)是互聯(lián)網(wǎng)迅速發(fā)展的必然結(jié)果.在云計算平臺中，用戶無需購買和部署IT基礎設施，而只需按需租用各類硬件、軟件、計算設備以及存儲資源，并通過向云平臺提交任務來實現(xiàn)計算任務與存儲業(yè)務.在進行任務調(diào)度時，作為一種商業(yè)服務，云計算系統(tǒng)在滿足用戶QoS(quality of service)要求的同時，還應盡可能地最大化其服務收益.給定任務和計算資源集，云計算任務調(diào)度問題就是為了尋找一種調(diào)度策略，基于該策略，云平臺將用戶任務分別指派給不同的計算節(jié)點，以實現(xiàn)大量任務在計算資源之間的合理分配和高效執(zhí)行.任務調(diào)度是一個NP完全問題，其不可能在多項式時間復雜度內(nèi)求得全局最優(yōu)解.目前，研究人員提出了多種方法來逼近其最優(yōu)解，然而現(xiàn)有調(diào)度方法大多耗時過長且結(jié)果不可預測，很難應用于實際的云計算環(huán)境.遺傳算法具有較好的全局搜索能力，可以快速遍歷一個較大的搜索空間，并且能夠避免陷入局部最優(yōu)解，可以很好地應用于復雜的目標優(yōu)化問題.

根據(jù)上述分析，從云服務提供方的角度出發(fā)，基于遺傳算法，文中提出一種成本驅(qū)動的云計算任務調(diào)度策略.提出的方法充分考慮云服務的商業(yè)特性，在滿足用戶任務QoS要求的前提下，盡可能地最大化云環(huán)境單位計算開銷的服務收益.

1 相關(guān)工作

近年來，任務調(diào)度問題吸引了大量研究人員參與其中，在提出的眾多方法中，經(jīng)典的Min-min［1］和Max-min［2］算法常被用來作為評價一個調(diào)度算法優(yōu)劣的標準.

云計算基于虛擬化技術(shù)，將分布在不同位置的資源進行整合，形成統(tǒng)一的資源池，向廣大用戶提供各種計算或存儲服務.云計算的服務器規(guī)模龐大，廣大用戶可按需購買任意規(guī)模的資源或服務，以處理各類計算密集型或數(shù)據(jù)密集型任務.根據(jù)不同的任務類型，目前有大量的調(diào)度方法被提出.對于計算密集型應用，文獻［3］提出了一種高效的任務調(diào)度方法，該方法可并行處理分布于異構(gòu)平臺同時包含獨立任務袋的多個應用.文獻［4］提出了一種預算約束的調(diào)度器，對于QoS要求各異的任務，該調(diào)度器可分別為其分配相應性能指標的計算資源;相對于固定的任務預算，該調(diào)度器可以最小化總的任務完成時間.文獻［5］提出了一種動態(tài)云環(huán)境下的工作流任務調(diào)度策略，該策略充分考慮了科學工作流的任務特征，并基于概率機制不斷調(diào)整其調(diào)度定價模型以適應云計算環(huán)境的動態(tài)多變特性.考慮到在數(shù)據(jù)密集型應用中，數(shù)據(jù)存儲之間往往相互關(guān)聯(lián)，文獻［6］開發(fā)了一個數(shù)據(jù)重用模型，并在此基礎上提出了一個啟發(fā)式的任務調(diào)度算法;文獻［7］則通過同時考慮調(diào)度任務的數(shù)據(jù)需求和計算需求，提出了一種自適應的任務調(diào)度方案.前述兩種方案均可以很好地應用于數(shù)據(jù)密集型的任務調(diào)度.

不僅如此，現(xiàn)有方法常常應用計算資源屬性和調(diào)度任務的QoS參數(shù)來對任務的完成時間進行預測，以輔助調(diào)度決策.文獻［8］基于統(tǒng)計分析的觀點，通過對基準測試集和編譯器進行分析，提出了一種任務完成時間的預測方法.文獻［9］通過對一個時間序列內(nèi)的歷史數(shù)據(jù)進行統(tǒng)計建模，基于一個K近鄰的方法來實現(xiàn)對任務完成時間的預測.文獻［10］提出了一種多策略的協(xié)同預測模型，并引入一個預測精度保障的概念來對任務完成時間的預測精度進行定量評估.

云計算本質(zhì)上是一種商業(yè)服務模型，其在滿足廣大用戶任務調(diào)度QoS要求的同時，還應盡可能地增加其服務收益.因此，上述的調(diào)度策略雖能夠滿足用戶調(diào)度的QoS要求，但并不太適應于云計算這一商業(yè)計算模式.文中基于云的商業(yè)特性，從云服務提供方的角度出發(fā)，提出一種成本驅(qū)動的云計算任務調(diào)度策略.

2 成本驅(qū)動的云計算任務調(diào)度策略

2.1 相關(guān)符號及約束條件

集合C={c1，c2，…，cn}表示云計算資源集，其中n表示計算節(jié)點數(shù);集合T={t1，t2，…，tm}表示系統(tǒng)中待調(diào)度的任務集，m表示待調(diào)度的任務數(shù).X是一個m×n的任務分配矩陣，若任務ti被分配給計算節(jié)點cj，則X中的元素xi，j=1，否則xi，j=0.文中假設一個任務只能被指派到一個計算節(jié)點上執(zhí)行調(diào)度，且任務調(diào)度不能搶占執(zhí)行.

Budgeti表示任務ti的預算，即云服務方在約定時間內(nèi)完成ti的調(diào)度時所獲得的收益;Deadlinei表示任務ti的調(diào)度時間底線，當云服務方在該底線之前完成ti的調(diào)度時，無需支付賠償金，否則需向用戶支付賠償金;I-counti表示任務ti的指令數(shù)，即任務規(guī)模，其由預處理模塊估算獲得;T-finii表示任務ti的預期完成時間;I-costj表示計算節(jié)點cj執(zhí)行單條指令的開銷成本;D-costi表示任務ti單位時間的延遲成本，即云服務方超過時間底線Deadlinei后，每延遲一個時間單位需向用戶支付的賠償金額;L-line表示任務ti所能接受的最遲完成時間，在該時間點，云服務方需要向用戶支付的賠償金達到最大值.不失一般性，文中約定任務的調(diào)度完成時間超過L-line時，云服務方的收益為0.

執(zhí)行調(diào)度時，用戶向云平臺提交調(diào)度請求.云服務提供方根據(jù)任務預算及其QoS要求來估算收益情況，以判斷是否接受該任務.接受調(diào)度請求之后，如云服務方未能在用戶要求的時間內(nèi)完成調(diào)度，則需根據(jù)其延遲時間向用戶支付賠償金.

就用戶而言，其任務的預期完成時間T-fini最遲不能超過L-line，否則不僅其QoS得不到滿足，云服務方也得不到任何收益.另一方面，在滿足調(diào)度任務QoS要求的條件下，假設任務ti被指派給計算節(jié)點cj，即xi，j=1，則節(jié)點cj調(diào)度任務ti的計算開銷為

相對于上述開銷，節(jié)點cj調(diào)度任務ti取得的服務收益為，其中為節(jié)點cj調(diào)度任務ti的延遲賠償金，具體為

進一步地，整個云系統(tǒng)調(diào)度任務集T={t1，t2，…，tm}的總收益為總的計算開銷為

在滿足用戶QoS要求的前提下，云計算應以盡可能小的成本獲得盡可能多的收益.因此，提出的成本驅(qū)動的云計算任務調(diào)度策略應盡可能地最大化其單位計算開銷的服務收益，即其求解目標為

很顯然，上述求解目標是一個NP完全問題，其不可能在多項式時間復雜度內(nèi)求得全局最優(yōu)解.

2.2 成本驅(qū)動的云計算任務調(diào)度模型

成本驅(qū)動的云計算任務調(diào)度模型如圖1所示.

圖1 成本驅(qū)動的云計算任務調(diào)度模型

用戶首先發(fā)出任務調(diào)度請求，預處理單元根據(jù)任務屬性及其QoS要求對任務規(guī)模進行估算.調(diào)度器接收到調(diào)度請求之后，將任務屬性信息、QoS參數(shù)以及從云資源管理器獲取的計算資源信息等一并發(fā)送至任務調(diào)度模塊.調(diào)度模塊根據(jù)任務及計算資源信息建立調(diào)度目標，并基于遺傳算法進行目標優(yōu)化，最后將優(yōu)化的調(diào)度方案返回至調(diào)度器.調(diào)度器在獲得調(diào)度方案之后，在云計算資源層執(zhí)行調(diào)度操作.調(diào)度結(jié)束后，由云計算資源層將任務調(diào)度結(jié)果返回至調(diào)度器.

3 基于遺傳算法的目標求解

應用遺傳算法，在多項式時間復雜度內(nèi)對前述調(diào)度目標進行近似求解，其求解過程如圖2所示.

圖2 基于遺傳算法的目標求解過程

3.1 初始化種群

首先確定遺傳算法的種群規(guī)模N和迭代計算器Count，Count的初始值為0.為了應用遺傳算法對提出的任務調(diào)度策略進行全局求解，需要將每一種可能的調(diào)度方案編碼成染色體.例如，對于m=7，n=4的云計算環(huán)境，根據(jù)其任務分配矩陣X，可采用下述方法進行染色體編碼:

在上述變換中，用00，01，10，11依次表示相應的任務被指派到計算節(jié)點c1，c2，c3，c4.將用二進制表示的任務分配矩陣按行展開即得到相應調(diào)度方案的染色體編碼.根據(jù)指定的種群規(guī)模N，將相應數(shù)量隨機生成的調(diào)度策略基于上述方法進行染色體編碼，即得到初始種群P(0).

3.2 適應度函數(shù)

適應度函數(shù)用于評價染色體的好壞，其函數(shù)值越大，相應的染色體在遺傳算法的進化迭代中越有利于被保留下來.文中遺傳算法以云計算單位計算開銷的服務收益作為其適應度函數(shù)，表示如下:

對于一條染色體，其適應度函數(shù)值越大，則它對應的調(diào)度方案的單位計算開銷的服務收益越多.

3.3 遺傳迭代操作

獲得初始種群P(0)之后，應用交叉、變異、選擇等遺傳操作算子對P(0)中的染色體進行迭代進化操作，重復上述過程，直至種群進化到一個可接受的解.首先確定交叉概率pc和變異概率pm.

交叉:從當前種群P(g)中隨機選取兩個染色體，然后對選取的兩個染色體的部分基因座以某種特定的方式進行交換，即實現(xiàn)染色體的交叉繁殖.其中，g表示種群的代數(shù)，對于初始種群，g=0;每條染色體均以概率pc的幾率被選取參與交叉操作.經(jīng)交叉操作生成的新染色體集合記作Scrossover.

變異:以變異概率pm從當前種群P(g)中隨機選取一定數(shù)量的染色體，對選取染色體的個別基因座以某種特定方式進行變異，即生成新的染色體.經(jīng)變異操作生成的新染色體集合記作Smutation.

選擇:對經(jīng)交叉和變異操作生成的新染色體集合以及當前種群進行合并，得到集合Scrossover∪Smutation∪P(g)，對于該集合中的元素，分別計算其適應度函數(shù)值，并選擇適應度函數(shù)值最大的前N個染色體作為下一代種群保留下來，記作P(g+1)，并令Count=Count+1.

3.4 算法終止

經(jīng)過上述迭代操作，可得到新一代種群P(g+1)，接下來根據(jù)調(diào)度策略的求解目標，即公式(3)來對新一代種群進行評估.若算法迭代次數(shù)超過預先設置的最大迭代次數(shù)iteration，或者在連續(xù)的多代種群中，適應性最好的染色體的適應度函數(shù)值沒有改進，則終止條件得到滿足，算法終止;否則令g=g+1，并繼續(xù)上述遺傳迭代操作，直至算法的終止條件得到滿足.

4 試驗測試與分析

為驗證成本驅(qū)動的云計算任務調(diào)度策略的性能，作者對該策略進行了模擬測試，同時將測試結(jié)果與傳統(tǒng)Min-min算法［1］以及改進的QoS約束的Minmin 算法［11］分別進行比較.

4.1 試驗環(huán)境與參數(shù)設置

基于Cloudsim［12］對提出的任務調(diào)度策略、Minmin算法以及改進的QoS約束的Min-min算法分別進行模擬測試.整個云計算仿真環(huán)境共有10個計算節(jié)點，各節(jié)點擁有的處理單元數(shù)量、處理單元的計算效率以及單位時間的計算成本如表1所示.

表1 云計算環(huán)境計算資源列表

請求調(diào)度的任務屬性包括I-count，Budget，Deadline，L-line，D-cost.試驗共用到 10 組一共 100個任務，各組任務的數(shù)量及參數(shù)設置見表2.

表2 請求調(diào)度的任務列表

在應用遺傳算法對提出的調(diào)度目標進行優(yōu)化求解時，設定初始種群規(guī)模為100，交叉概率為0.7，變異概率為0.15，最大迭代次數(shù)為300，連續(xù)3次迭代種群的最小進化速率為0.3%.

4.2 測試結(jié)果與分析

基于上述試驗環(huán)境及參數(shù)設置，依次對成本驅(qū)動的云計算任務調(diào)度策略、傳統(tǒng)的Min-min算法以及改進的QoS約束的Min-min算法分別進行測試，并對測試結(jié)果進行比較分析.在每組測試中，參與調(diào)度的用戶任務數(shù)量依次為10，20，…，100，它們均從表2所示的任務列表中隨機選取，每組測試結(jié)果均通過多次試驗并取平均值獲得.

任務的調(diào)度完成時間與參與調(diào)度的任務數(shù)量之間的關(guān)系如圖3所示.

圖3 不同任務數(shù)量下的調(diào)度完成時間

由圖3可見，隨著調(diào)度任務數(shù)量的增加，3種方法的調(diào)度完成時間均呈上升趨勢.相比之下，QoS約束的Min-min算法優(yōu)于傳統(tǒng)的Min-min，這是由于前者的調(diào)度決策兼顧了任務的Deadline約束.進一步地，成本驅(qū)動的調(diào)度方法明顯優(yōu)于前兩類方法，這是由于成本驅(qū)動的方法將計算開銷作為調(diào)度決策的關(guān)鍵因素，其以最大化單位計算開銷的服務收益作為調(diào)度目標，使得其總是從全局出發(fā)，盡可能地將全部任務均指派給最為合適的計算資源;另一方面，Min-min及QoS約束的Min-min算法總是趨向于將任務指派給具有最小最早完成時間的計算資源，導致負載不均，增大了部分任務的等待時間，最終延遲了任務的調(diào)度完成時間.

隨著參與調(diào)度的任務數(shù)量的增加，調(diào)度完成時間超過其Deadline的任務數(shù)占全部任務數(shù)比例的變化趨勢如圖4所示.

圖4 不同任務數(shù)量下調(diào)度完成時間超越Deadline的比例

由圖4可見，成本驅(qū)動的調(diào)度方法優(yōu)于另外兩種方法.如前所述，成本驅(qū)動的方法總是從全局出發(fā)，盡可能地將任務指派給最為合適的計算資源;而Min-min及其改進算法容易導致負載不均，增大了部分任務的等待時間，從而使得調(diào)度的完成時間超過其Deadline的任務數(shù)量增多.改進的QoS約束的Min-min算法由于更多地考慮了調(diào)度任務的Deadline約束，也使得其調(diào)度完成時間超過Deadline的任務比例明顯低于傳統(tǒng)的Min-min算法.就3種算法而言，由于任務之間的資源競爭，調(diào)度完成時間超過Deadline的任務比例隨著參與調(diào)度的任務數(shù)量的增加均呈上升趨勢.

在不同數(shù)量的調(diào)度任務下，3種算法單位計算開銷的服務收益情況如圖5所示.

圖5 不同任務數(shù)量下單位計算開銷的服務收益

由圖5可見，成本驅(qū)動的方法優(yōu)于另外兩種方法，這是因為成本驅(qū)動的方法以最大化單位計算開銷的服務收益為求解目標，負載較為均衡，調(diào)度更為合理.Min-min算法容易導致系統(tǒng)負載不均，增大了部分任務的等待時間，最終導致系統(tǒng)單位計算開銷的服務收益受損.相比之下，QoS約束的Min-min算法在調(diào)度決策時兼顧了任務的Deadline要求，這使得其單位計算開銷的服務收益情況要優(yōu)于傳統(tǒng)Min-min算法.隨著參與調(diào)度的任務數(shù)量增多，任務之間的資源競爭加劇，3種算法單位計算開銷的服務收益均呈下降趨勢.

5 結(jié)論

從云服務提供方的角度出發(fā)，提出了一種成本驅(qū)動的云計算任務調(diào)度策略，并在Cloudsim模擬器上做了一系列仿真測試，結(jié)論如下:

1)提出的策略在任務完成時間上優(yōu)于傳統(tǒng)的Min-min算法和改進的QoS約束的Min-min算法.

2)相比于另外兩種算法，提出的調(diào)度策略調(diào)度完成時間超越截止時間底線的任務比例總體上更低，這一優(yōu)勢在任務數(shù)量較多時更為明顯.

3)提出的調(diào)度策略系統(tǒng)負載更為均衡，其單位計算開銷的服務收益明顯優(yōu)于另外兩種方法.

References)

［1］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.

［2］Bhoi U，Ramanuj P N.Enhanced Max-min task scheduling algorithm in cloud computing［J］.International Journal of Application or Innovation in Engineering and Management，2013，2(4):259-264.

［3］Benoit A，Marchal L，Pineau J F，et al.Scheduling concurrent bag-of-tasks applications on heterogeneous platforms［J］.IEEE Transactions on Computers，2010，59(2):202-217.

［4］Oprescu A M，Kielmann T.Bag-of-tasks scheduling under budget constraints［C］∥Proceedings of2nd IEEE International Conference on Cloud Computing Technology and Science.Indianapolis，USA:IEEE Computer Society，2010:351-359.

［5］Zhou Amelie Chi，He Bingsheng，Liu Cheng.Probabilistic scheduling of scientific workflows in dynamic cloud environments［R］.Singapore:Nanyang Technological University，2013.

［6］Santos-Neto E，Cirne W，Brasileiro F，et al.Exploiting replication and data reuse to efficiently schedule data-intensive applications on grids［C］∥Proceedings of the10th International Workshop on Job Scheduling Strategies for Parallel Processing.New York:Springer Verlag，2005:210-232.

［7］Liu Wantao，Kettimuthu R，Li Bo，et al.An adaptive strategy for scheduling data-intensive applications in grid environments［C］∥Proceedings of2010 17th International Conference on Telecommunications.Doha，Qatar:IEEE Computer Society，2010:642-649.

［8］Kiran M，Hashim A-H A，Kuan L M，et al.Execution time prediction of imperative paradigm tasks for grid scheduling optimization［J］.International Journal of Computer Science and Network Security，2009，9(2):155-163.

［9］Phinjaroenphan P，Bevinakoppa S，Zeephongsekul P.A method for estimating the execution time of a parallel task on a grid node［J］.Lecture Notes in Computer Science，2005，3470:226-236.

［10］Tao Ming，Dong Shoubin，Zhang Liping.A multi-strategy collaborative prediction model for the runtime of online tasks in computing cluster/grid［J］.Cluster Computing，2011，14(2):199-210.

［11］Liu Juefu，Li Gang.An improved MIN-MIN grid tasks scheduling algorithm based on Qos constraints［C］∥Proceeding of2010International Conference on Optics，Photonics and Energy Engineering. Wuhan， China:IEEE Computer Society，2010:281-283.

［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［R］.Australia:Grid Computing and Distributed Systems Laboratory，University of Melbourne，2009.