馬文+耿貞偉+張莉娜

摘 要： 針對當(dāng)前云作業(yè)調(diào)度算法效率低的不足，為了獲得理想的云作業(yè)調(diào)度結(jié)果，以便給用戶提供更好的服務(wù)質(zhì)量，提出基于數(shù)據(jù)挖掘的混合云作業(yè)調(diào)度算法。對混合云作業(yè)調(diào)度的原理進行分析，指出當(dāng)前云作業(yè)調(diào)度算法性能差的原因，建立云作業(yè)調(diào)度的目標(biāo)函數(shù)，并采用數(shù)據(jù)挖掘技術(shù)找到最理想的混合云作業(yè)調(diào)度方案。在CloudSim環(huán)境下，通過具體混合云作業(yè)調(diào)度實驗對算法的性能進行驗證。結(jié)果表明，該算法不僅大幅度提高了混合云作業(yè)調(diào)度的成功率，而且加快了混合云作業(yè)完成的時間，具有較好的實際應(yīng)用價值。

關(guān)鍵詞： 云計算系統(tǒng)； 作業(yè)調(diào)度； 完成時間； 數(shù)據(jù)挖掘； 服務(wù)質(zhì)量

中圖分類號： TN911?34； TP393 文獻標(biāo)識碼： A 文章編號： 1004?373X（2017）19?0049?03

Hybrid cloud job scheduling algorithm based on data mining

MA Wen， GENG Zhenwei， ZHANG Lina

（Information Center of Yunnan Power Grid Co.， Ltd.， Kunming 650217， China）

Abstract： Aiming at the low efficiency of the current cloud job scheduling algorithms， a hybrid cloud job scheduling algorithm based on data mining is proposed to obtain the ideal cloud job scheduling results and provide better service quality for users. The principle of the hybrid cloud job scheduling is analyzed. The reason why the current cloud job scheduling algorithm has poor performance is pointed out. The objective function of cloud job scheduling is established. The data mining technology is used to seek out the most ideal hybrid cloud job scheduling scheme. The performance of the algorithm was verified by means of the specific hybrid cloud job scheduling experiment in CloudSim environment. The results show that the proposed algorithm can improve the success rate of the hybrid cloud job scheduling greatly， and speed up the completion time of the hybrid cloud job， which has high practical application value.

Keywords： cloud computing system； job scheduling； completion time； data mining； service quality

0 引 言

云計算是一種新的計算模式，主要用于解決大規(guī)模數(shù)據(jù)處理問題，集成了計算機、通信、模式識別等技術(shù)，通過Internet進行資源共享，用戶可以通過平臺申請自己的資源，完成相應(yīng)的任務(wù)，具有價格低、靈活、通用性強等特點，在許多領(lǐng)域得到了成功的應(yīng)用[1?2]。根據(jù)云規(guī)模大小，可以劃分為私有云、公有云和混合云三種類型，其中混合云是公有云和私有云的綜合，其實際應(yīng)用價值更高，已經(jīng)成為云計算將來的發(fā)展方向[3]。

在混合云的實際應(yīng)用中，由于每一類用戶對云計算資源的需求不同，如何快速、有效地完成用戶提交的混合云作業(yè)，為用戶提供高質(zhì)量的服務(wù)，顯得尤為重要，成為當(dāng)前云計算系統(tǒng)研究中的熱點[4]。為了解決云計算混合云作業(yè)調(diào)度問題，一些學(xué)者進行了深入研究，當(dāng)前有許多計算作業(yè)調(diào)度算法[5]。最初采用公平調(diào)度算法實現(xiàn)云計算混合云作業(yè)調(diào)度，對于規(guī)模較小的云計算混合云作業(yè)調(diào)度問題，可以獲得理想的云計算混合云作業(yè)調(diào)度方案，當(dāng)云計算混合云作業(yè)調(diào)度問題規(guī)模較大時，求解速度很慢，而且難以獲得最優(yōu)的云計算混合云作業(yè)調(diào)度方案，尤其對于超大規(guī)模的云計算混合云作業(yè)調(diào)度問題，無法順利求解[6]。為此有學(xué)者采用啟發(fā)式算法，如粒子群算法等，它們將云計算作業(yè)調(diào)度問題看作啟發(fā)式算法求解的目標(biāo)，通過不斷搜索找到云計算作業(yè)調(diào)度最優(yōu)或者次優(yōu)方案[7?9]，求解效率明顯要高于公平調(diào)度算法，然而云計算作業(yè)調(diào)度屬于NP難題，當(dāng)云計算作業(yè)調(diào)度問題的規(guī)模較大時，它們性能急劇下降，求解時間相當(dāng)長，無法滿足云計算作業(yè)在線調(diào)度要求，也不能滿足用戶服務(wù)的實時性，同時這些算法只是簡單針對公有云和私有云的作業(yè)調(diào)度問題，當(dāng)前混合云作業(yè)調(diào)度的研究很少[10?11]。

針對混合云作業(yè)調(diào)度問題，提出基于數(shù)據(jù)挖掘的混合云作業(yè)調(diào)度算法。首先對云計算系統(tǒng)的作業(yè)調(diào)度原理進行分析，并描述混合云體系結(jié)構(gòu)；然后建立混合云作業(yè)調(diào)度的目標(biāo)函數(shù)，采用數(shù)據(jù)挖掘技術(shù)進行求解；最后在CloudSim環(huán)境下實現(xiàn)仿真實驗，驗證其有效性。

1 云計算系統(tǒng)以及混合云的架構(gòu)

1.1 云計算系統(tǒng)的構(gòu)架

云計算系統(tǒng)通過Internet將不同地點、不同區(qū)域的單臺計算機資源連接起來，計算機資源主要包括CPU、存儲器、網(wǎng)絡(luò)帶寬等，它們組成一個龐大的計算機系統(tǒng)，采用分布式方式給用戶提供相應(yīng)的資源，用戶通過自己的具體要求分配到相應(yīng)的資源，從而完成自己的作業(yè)，具體架構(gòu)如圖1所示。

1.2 混合云的架構(gòu)

混合云采用一定技術(shù)將私有云和公有云組合在一起，基本架構(gòu)如圖2所示。其中私有云主要控制隱私數(shù)據(jù)，保密性高，但單一的私有云有其局限性，無法全面提供給用戶滿意服務(wù)，因此公有云是私有云的有益補充，可擴展性更好。

2 混合云作業(yè)調(diào)度算法

2.1 混合云作業(yè)調(diào)度的目標(biāo)函數(shù)

在實際應(yīng)用中，云作業(yè)規(guī)模很大，單采用一個云計算節(jié)點無法正常完成，因此需要對云作業(yè)進行分解，劃分為多個子作業(yè)，根據(jù)每一個子作業(yè)特點分配相應(yīng)的資源節(jié)點。當(dāng)全部子作業(yè)都完成后，通過管理節(jié)點將它們組合在一起，將最終結(jié)果反饋給用戶。云作業(yè)通常采用Map/Reduce模式，通過Map和Reduce函數(shù)實現(xiàn)用戶作業(yè)的調(diào)度，Map/Reduce工作原理如圖3所示。

Map/Reduce完成混合云作業(yè)的步驟如下：

（1） 用戶提交作業(yè)，每一個作業(yè)根據(jù)其特點劃分為多個子作業(yè)（work），那么作業(yè)[t]的運行時間[TaskTt]為：

[TaskTt=maxj=1NomWM（i，j）+x=1NorWR（k，x）] （1）

式中：[WM（i，j）]為第[j]個子任務(wù)所需的時間；Nom和Nor表示作業(yè)在隊列中的次序。

（2） 混合云作業(yè)調(diào)度目標(biāo)，保證用戶提交的作業(yè)總完成時間[T1]和平均完成時間[T2]盡可能最小，同時滿足用戶要求，則有：

[T1=mint=1NumTTaskTt] （2）

[T2=min1NumTt=1NumTTaskTt] （3）

綜上可知，混合云作業(yè)調(diào)度的目標(biāo)函數(shù)可以寫為：

[T=mint=1NumTTaskTt+min1NumTt=1NumTTaskTt] （4）

為了給每一子作業(yè)分配合理的云資源，盡可能加快作業(yè)的完成時間，采用數(shù)據(jù)挖掘技術(shù)對作業(yè)完成的時間進行預(yù)測，根據(jù)預(yù)測結(jié)果分配相應(yīng)的云計算資源。

2.2 數(shù)據(jù)挖掘技術(shù)

對于訓(xùn)練樣本[xi，yi，]采用數(shù)據(jù)挖掘?qū)ζ渥兓攸c進行分析，可以建立如下的回歸函數(shù)：

[f（x）=ωT?（x）+b] （5）

對式（5）進行適當(dāng)轉(zhuǎn)換，得到一個如下的約束條件：

[minω2+12Ci=1nξ2i s.t. yi-ωT?（x）+b=eii=1，2，…，n] （6）

式中[ei]為回歸偏差。

通過拉格朗日乘子[αi]進行變換，得到其對偶形式為：

[L（ω，b，ζ，α）=minω2+12Ci=1nξ2i+i=1nαiωT?（x）-b+ei-yi] （7）

引入核函數(shù)[K（xi，xj）=?T（xi）?（xj）]，使得其可以求解非線性回歸問題，核函數(shù)定義如下：

[k（xi，xj）=exp-xi-xj22σ2 ] （8）

因此，非線性回歸問題的數(shù)據(jù)挖掘結(jié)果為：

[f（x）=i=1Nαiexp-xi-xj22σ2+b] （9）

2.3 數(shù)據(jù)挖掘技術(shù)的混合云作業(yè)調(diào)度算法

設(shè)云計算系統(tǒng)共有[m]個計算機資源[{v1，v2，…，vm}，]不同作業(yè)要求的服務(wù)不一樣，導(dǎo)致需要的資源也不相同，因此本文用數(shù)據(jù)挖掘技術(shù)對作業(yè)的需求進行預(yù)測，具體工作步驟如下：

（1） 對于一個具體的云計算作業(yè)，收集與其相似的歷史樣本數(shù)據(jù)。

（2） 對歷史樣本數(shù)據(jù)進行聚類分析，選擇與待完成云計算作業(yè)相似度較高的樣本。

（3） 將聚類分析獲得的樣本輸入到數(shù)據(jù)挖掘算法進行分析，通過學(xué)習(xí)確定最優(yōu)參數(shù)，得到該云計算作業(yè)完成的預(yù)估時間。

（4） 根據(jù)云計算作業(yè)的預(yù)估時間，向云計算系統(tǒng)申請相應(yīng)的資源。

（5） 計算該云計算作業(yè)實際完成的時間，并得到預(yù)估時間和實際完成時間之間的偏差。

（6） 如果偏差太多，返回步驟（2），直到偏差達到預(yù)先設(shè)置的要求為止，從而完成云計算作業(yè)調(diào)度。

3 仿真實驗

3.1 仿真平臺

為了分析基于數(shù)據(jù)挖掘的混合云作業(yè)算法的有效性，建立混合云實驗平臺，其參數(shù)具體如表1和表2所示，仿真軟件采用CloudSim。

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

不同規(guī)模的云作業(yè)條件下，作業(yè)的平均完成時間和總完成時間如圖4所示。對圖4的實驗結(jié)果進行對比分析可以發(fā)現(xiàn)，當(dāng)作業(yè)規(guī)模增大時，作業(yè)完成時間延長，但本文算法的作業(yè)完成時間要遠遠少于公平調(diào)度算法，這主要是由于本文算法通過數(shù)據(jù)挖掘技術(shù)對作業(yè)完成時間進行預(yù)估，可以選擇最優(yōu)云計算資源完成作業(yè)，得到更優(yōu)的云計算作業(yè)調(diào)度方案，加快云計算作業(yè)完成的時間。

文算法更能適應(yīng)云作業(yè)調(diào)度問題的求解，具有顯著的優(yōu)越性。

4 結(jié) 語

作業(yè)調(diào)度是云計算系統(tǒng)的一項關(guān)鍵技術(shù)，針對當(dāng)前云作業(yè)調(diào)度算法效率低的不足，提出基于數(shù)據(jù)挖掘的混合云作業(yè)調(diào)度算法。首先建立云作業(yè)調(diào)度的目標(biāo)函數(shù)，然后采用數(shù)據(jù)挖掘技術(shù)對目標(biāo)函數(shù)進行求解，最后在CloudSim環(huán)境下對算法的性能進行驗證，實驗結(jié)果表明，本文算法不僅可以獲得使用戶滿意的混合云作業(yè)調(diào)度方案，且具有較好的實際應(yīng)用價值。

參考文獻

[1] BUYYA R， YEO C S， VENUGOPAL S， et al. Cloud compu?ting and emerging IT platforms： vision， hype， and reality for delivering computing as the 5th utility [J]. Future generation computer systems， 2009， 25（6）： 599?616.

[2] 張建勛，古志民，鄭超.云計算研究進展綜述[J].計算機應(yīng)用研究，2010，27（2）：429?433.

[3] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應(yīng)用，2009，29（9）：2562?2567.

[4] ONCHAGA Richard. Quality of service management framework for dynamic chaining of geographic information services [J]. International journal of applied earth observation and geoinformation， 2006（8）： 137?148.

[5] SOTOMAYOR B， MONTERO R， LLORENTE I， et al. Virtual infrastructure management in private and hybrid clouds [J]. IEEE Internet computing， 2009， 13（5）： 14?22.

[6] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software practice & experience， 2011， 41（1）： 23?50.

[7] 左利云，左利鋒.云計算中基于預(yù)先分類的調(diào)度優(yōu)化算法[J].計算機工程與設(shè)計，2012，33（4）：1357?1361.

[8] 李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用，2011，31（1）：184?186.

[9] 申麗君，劉麗，陸銳.基于改進免疫進化算法的云計算任務(wù)調(diào)度[J].計算機工程，2012，38（9）：208?210.

[10] 楊海軍.云計算環(huán)境下人工蜂群作業(yè)調(diào)度算法設(shè)計[J].數(shù)學(xué)的實踐與認識，2012，42（10）：115?120.

[11] 劉穎，甘泉，王宇.混合云環(huán)境中改進的工作負載分配方案[J].電信科學(xué)，2015，24（1）：77?81.