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

馬文+耿貞偉+張莉娜

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

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

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[T1=mint=1NumTTaskTt] （2）

[T2=min1NumTt=1NumTTaskTt] （3）

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

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

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

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

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

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

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

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

式中[ei]為回歸偏差。

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 仿真平臺(tái)

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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ì)算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究，2010，27（2）：429?433.

[3] 陳全，鄧倩妮.云計(jì)算及其關(guān)鍵技術(shù)[J].計(jì)算機(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] 左利云，左利鋒.云計(jì)算中基于預(yù)先分類的調(diào)度優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（4）：1357?1361.

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

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

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

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