基于改進(jìn)禁忌搜索的云任務(wù)負(fù)載均衡調(diào)度策略研究

陸佳煒，李 杰，張?jiān)Q，肖 剛

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310000)

1 引 言

云計(jì)算源于分布式計(jì)算、網(wǎng)格計(jì)算，是一種完全基于互聯(lián)網(wǎng)的計(jì)算方式[1]，其遵循"按需付費(fèi)"的模式為用戶提供低成本、高可靠性、可伸縮的計(jì)算資源及服務(wù).在云環(huán)境中，采用合理的任務(wù)調(diào)度算法可以有效的提高計(jì)算資源利用率、縮短總?cè)蝿?wù)完成時(shí)間、降低云計(jì)算環(huán)境中的負(fù)載均衡.因此，任務(wù)調(diào)度已經(jīng)成為云計(jì)算中的一個(gè)研究熱點(diǎn)[2,3].

任務(wù)調(diào)度是指在一段時(shí)間內(nèi)分配執(zhí)行一組任務(wù)的資源[4].任務(wù)調(diào)度的目標(biāo)之一是最小化任務(wù)的完成時(shí)間[5].通常來說，任務(wù)調(diào)度問題已被證明是一個(gè)NP-hard問題[6]，即隨著問題規(guī)模的增加，總能找到一種較優(yōu)的解決方案.良好的任務(wù)調(diào)度算法必須在滿足用戶服務(wù)質(zhì)量的同時(shí)，降低負(fù)載均衡保證云環(huán)境的穩(wěn)定性及節(jié)約能耗.

云環(huán)境中任務(wù)的處理單元稱為虛擬機(jī)(VMs)，因此，減少虛擬機(jī)上任務(wù)的總體執(zhí)行時(shí)間是用戶的一個(gè)重要關(guān)注點(diǎn)[7].從業(yè)務(wù)的角度出發(fā)，虛擬機(jī)應(yīng)盡可能早地并行執(zhí)行任務(wù).即任意時(shí)刻，單臺虛擬機(jī)上的任務(wù)量不會過載，并且所有虛擬機(jī)都盡可能保持工作狀態(tài).因此，云任務(wù)負(fù)載均衡調(diào)度算法要盡可能保證資源利用的最大化，并能改善用戶提交的云任務(wù)完成時(shí)間[8].

迄今為止，國內(nèi)外研究者已經(jīng)提出了許多啟發(fā)式和元啟發(fā)式算法用來解決任務(wù)調(diào)度問題，如文獻(xiàn)[9,10]提出了盡可能將小任務(wù)分配到執(zhí)行速度快的資源上運(yùn)行的Min-Min算法；文獻(xiàn)[11]提出了一種對時(shí)間貪心的Min-Max算法，其將小任務(wù)和大任務(wù)"捆綁"在一起執(zhí)行調(diào)度，從而有效地解決了負(fù)載不均衡的問題；文獻(xiàn)[1,12]將遺傳算法運(yùn)用到任務(wù)調(diào)度中，用于求解任務(wù)調(diào)度最優(yōu)解；文獻(xiàn)[13,14]考慮任務(wù)執(zhí)行時(shí)間和負(fù)載均衡的優(yōu)先級影響，提出一種粒子群優(yōu)化算法提高任務(wù)調(diào)度效率；文獻(xiàn)[7]提出了一種模擬蜜蜂采蜜機(jī)理的負(fù)載均衡策略，基于負(fù)載均衡評價(jià)模型進(jìn)行任務(wù)交換以有效降低任務(wù)完成時(shí)間；文獻(xiàn)[15]以最小化任務(wù)完成時(shí)間為目標(biāo)給出了一種基于蟻群優(yōu)化算法的云任務(wù)調(diào)度策略.

禁忌搜索[16]算法是一種啟發(fā)式算法，具有智能記憶功能，求出的最優(yōu)解優(yōu)于傳統(tǒng)算法，同時(shí)具有效率較高的搜索功能，在解決NP-hard問題時(shí)具有一定的優(yōu)勢.文獻(xiàn)[17]將其運(yùn)用于倉庫調(diào)度多目標(biāo)優(yōu)化問題，建立了兼顧質(zhì)量和路徑的多目標(biāo)優(yōu)化模型，但其未完全克服禁忌搜索算法對任務(wù)初始解依賴性較強(qiáng)的缺點(diǎn).文獻(xiàn)[18]中提出了一種基于禁忌搜索的負(fù)載均衡任務(wù)調(diào)度算法，通過動態(tài)規(guī)劃方法形式化推導(dǎo)出任務(wù)初始解，結(jié)合任務(wù)完成時(shí)間的收益值進(jìn)行任務(wù)交換，在一定程度上降低了資源的負(fù)載均衡度，但其未考慮任務(wù)量較大時(shí)，可能會陷入局部最優(yōu)的問題.

因此，本文提出了一種基于多因素優(yōu)值和懲戒策略的禁忌搜索算法(Benefit Punishment Tabu，BP-Tabu)的云任務(wù)負(fù)載均衡策略，對任務(wù)調(diào)度進(jìn)行多方面的綜合優(yōu)化.即通過綜合考慮任務(wù)總體完成時(shí)間、虛擬資源負(fù)載均衡、虛擬機(jī)使用效益等多個(gè)因素的優(yōu)值函數(shù)，作為衡量不同任務(wù)調(diào)度方案的優(yōu)值，然后基于虛擬機(jī)隨機(jī)分量函數(shù)提出一種跳出局部最優(yōu)的懲戒策略，最后進(jìn)行實(shí)驗(yàn)對比證明此算法在云任務(wù)調(diào)度中的可行性.

2 問題描述及數(shù)學(xué)建模

2.1 問題描述

由于云計(jì)算采用虛擬化技術(shù)實(shí)現(xiàn)資源的按需提供服務(wù)，資源可分為物理資源和虛擬資源.因此，云計(jì)算環(huán)境下的資源調(diào)度又分為虛擬資源層面的調(diào)度和物理資源層面的調(diào)度[19].圖1為云計(jì)算中的資源調(diào)度模型.

圖1 資源調(diào)度模型圖Fig.1 Resource scheduling model

虛擬資源層面的調(diào)度又稱為任務(wù)調(diào)度，即用戶需求(Client requirements)提交后，被分解成一組互相獨(dú)立的子任務(wù)集合(Task)，每個(gè)子任務(wù)都是一個(gè)執(zhí)行特定功能的單元，并且是任務(wù)調(diào)度的最小粒度，這些子任務(wù)調(diào)度至合適虛擬機(jī)(VM)進(jìn)行執(zhí)行的過程稱為虛擬資源層面的調(diào)度[20]；物理資源層面的調(diào)度指虛擬機(jī)選擇合適的物理主機(jī)(host)上運(yùn)行的過程.本文重點(diǎn)研究虛擬資源層面的調(diào)度，即任務(wù)調(diào)度.在數(shù)學(xué)建模之前，我們先歸納需要使用的術(shù)語，如表1所示.

表1 符號和參數(shù)定義Table 1 Symbol and parameter definitions

2.2 數(shù)學(xué)建模

假設(shè)給定一個(gè)任務(wù)集合Tasks={t1,t2,…,tn}，包含n個(gè)待分配的任務(wù)，任務(wù)ti的總指令長度為MIi.云環(huán)境中存在一組工作中的虛擬機(jī)集合VMs={vm1,vm2,…，vmm}，虛擬機(jī)vmj的指令執(zhí)行速度為MIPSj.假設(shè)所有虛擬機(jī)都是互不干擾，并行執(zhí)行的，任務(wù)之間相互獨(dú)立，互不搶占資源.任務(wù)ti在虛擬機(jī)vmj上執(zhí)行的預(yù)期完成時(shí)間為ctij，定義如下：

(1)

2.2.1 虛擬機(jī)負(fù)載

對于某任務(wù)分配方案P，假設(shè)虛擬機(jī)vmj上已經(jīng)完成了前k-1個(gè)任務(wù)分配，定義虛擬機(jī)vmj的當(dāng)前負(fù)載vlj為分配給虛擬機(jī)vmj的所有任務(wù)所需執(zhí)行時(shí)間：

(2)

同一時(shí)刻，對于任務(wù)tk，定義其在虛擬機(jī)vmj上的時(shí)間跨度為makespankj，即任務(wù)tk在vmj上執(zhí)行的最早完成時(shí)間.根據(jù)公式(1)、公式(2)，makespankj為虛擬機(jī)vmj當(dāng)前負(fù)載vlj與任務(wù)tk在vmj上的預(yù)期完成時(shí)間的和值：

makespankj=vlj+ctkj

(3)

最終定義虛擬機(jī)的負(fù)載VLj為分配給第j個(gè)虛擬機(jī)vmj所有任務(wù)的預(yù)期完成時(shí)間.VLj越大，說明虛擬機(jī)vmj負(fù)載越高.

(4)

2.2.2 負(fù)載均衡度

(5)

對于任務(wù)調(diào)度方案P，結(jié)合公式(4)、(5)，給出虛擬機(jī)總的負(fù)載均衡度定義如下：

(6)

若方案P的負(fù)載均衡度LBp越小，說明該任務(wù)調(diào)度方案下，云環(huán)境的任務(wù)負(fù)載越均衡.

2.2.3 多因素優(yōu)值函數(shù)

針對任務(wù)調(diào)度方案集合η中的不同調(diào)度方案，本文給出優(yōu)值函數(shù)用于衡量該任務(wù)調(diào)度方案的優(yōu)值，最終選擇優(yōu)值高的調(diào)度方案完成任務(wù)集合Tasks的調(diào)度.

首先根據(jù)虛擬機(jī)處理能力MIPS、指令的執(zhí)行成本α以及延遲成本DP，定義虛擬機(jī)利用效益函數(shù)VMUj，用于衡量虛擬機(jī)的使用效益.則虛擬機(jī)vmj當(dāng)前狀態(tài)下VMUj為虛擬機(jī)vmj的利用效益，表示如下：

VMUj=vmu(α,DP,MIPSj)

(7)

結(jié)合公式(6)、公式(7)，給出用于衡量任務(wù)調(diào)度方案P的優(yōu)值函數(shù)Bp定義：

(8)

其中w1，w2為權(quán)重值.優(yōu)值函數(shù)Bp越高，說明此任務(wù)調(diào)度方案越優(yōu).

2.2.4 懲戒策略

由于原始Tabu搜索算法的藐視準(zhǔn)則無法保證搜索陷入局部最優(yōu)時(shí)一定能夠跳出，本文在此基礎(chǔ)上提出了懲戒策略，其基本思想是：對修改禁忌表tabuList中禁忌對象的次數(shù)進(jìn)行記錄，其記錄次數(shù)用pt表示，初始值為0.當(dāng)禁忌對象進(jìn)入禁忌表時(shí)，pt加1，當(dāng)連續(xù)h次tabuList集沒有更新時(shí)，即pt=h時(shí)，將會啟動懲戒策略.

定義虛擬機(jī)隨機(jī)分量函數(shù)P*(h)如下：

P*(h)=P(h)+w×h

(9)

其中P(h)為當(dāng)前最小虛擬機(jī)的索引量，w為隨機(jī)懲戒常量，h為記錄次數(shù)閾值.

虛擬機(jī)分量函數(shù)的增加會對任務(wù)負(fù)載VLmin最小的虛擬機(jī)VMmin的選擇產(chǎn)生影響，VMmin的索引量P(h)會偏移，根據(jù)最新的P(h)選擇相應(yīng)的虛擬機(jī)代替VMmin，最終引導(dǎo)搜索跳出局部最優(yōu).

3 BP-Tabu搜索算法

3.1 算法思想

云計(jì)算環(huán)境下，各個(gè)任務(wù)調(diào)度方法都存在著一定的不足，例如Min-Min[9,10]、Min-Max[11]等啟發(fā)式算法重點(diǎn)考慮任務(wù)完成時(shí)間，而未考慮到云資源利用率的最大化及虛擬資源的負(fù)載情況；遺傳算法[1,12]、粒子群算法[13]等元啟發(fā)式算法在大任務(wù)量情況下易陷入局部最優(yōu)的困境.本文提出的BP-Tabu搜索算法適用于云任務(wù)調(diào)度，能夠克服現(xiàn)有云環(huán)境下任務(wù)分配不均衡、單臺虛擬機(jī)資源負(fù)載過大或者空閑較多的問題.

3.2 初始解構(gòu)造

基于時(shí)間貪心算法，定義任務(wù)集合Tasks根據(jù)MI的大小進(jìn)行降序排列后得到的結(jié)果集為STasks；定義虛擬機(jī)集合VMs根據(jù)MIPS的大小進(jìn)行升序排列后得到的結(jié)果集為SVMs.根據(jù)公式(1)，結(jié)合排序之后的STasks和SVMs生成預(yù)期完成時(shí)間矩陣CT.從行號h=1開始，每次都將任務(wù)th自CT矩陣最后一列對應(yīng)的虛擬機(jī)vmm往前分配，依次計(jì)算任務(wù)th分配給各虛擬機(jī)后的時(shí)間跨度makespanhj(公式(3))，選擇使makespanhj最優(yōu)的虛擬機(jī)vmj完成分配，若存在多個(gè)分配方案，挑選任務(wù)運(yùn)行數(shù)最少的虛擬機(jī)資源進(jìn)行分配，實(shí)現(xiàn)初步的負(fù)載均衡.待所有任務(wù)均完成分配，則結(jié)束算法(圖2)，整個(gè)初始解構(gòu)造偽代碼如圖2所示.

圖2 初始解構(gòu)造偽代碼Fig.2 Initial solution algorithm

3.3 BP-Tabu搜索算法設(shè)計(jì)

在給出通過時(shí)間貪心求得的任務(wù)調(diào)度初始解(3.2節(jié))、多因素優(yōu)值函數(shù)(2.2.3節(jié))以及懲戒策略(2.2.4節(jié))的基礎(chǔ)上，本文提出了一種改進(jìn)的基于BP-Tabu搜索的云任務(wù)負(fù)載均衡算法，其設(shè)計(jì)流程如圖3所示.

圖3 基于BP-Tabu搜索的云任務(wù)負(fù)載均衡算法流程圖Fig.3 BP-Tabu flow diagram

下面給出BP-Tabu搜索算法的具體步驟：

1) 初始化設(shè)置.定義禁忌數(shù)組tabuList[1,2,…,n]，其中數(shù)組的各元素初始值均為1，用于標(biāo)識該任務(wù)可以被交換；設(shè)置虛擬機(jī)隨機(jī)分量函數(shù)P*(h)，初始化記錄次數(shù)閾值h、隨機(jī)懲戒常量w以及記錄次數(shù)pt=0；

VMmax=max{VLj|j∈m,j=1,2,…,m}

(10)

VMmin=min{VLj|j∈m,j=1,2,…,m}

(11)

判斷記錄次數(shù)pt是否達(dá)到記錄次數(shù)閾值h，若是，觸發(fā)懲戒策略，根據(jù)虛擬機(jī)隨機(jī)分量函數(shù)P*(h)(公式(9))重新選擇VMmin；

Ifh≤pt,VMmin=VMp*(h)%m

(12)

3) 任務(wù)交換.選擇虛擬機(jī)VMmax上可被用于交換的任務(wù)tk，設(shè)置其禁忌值tabuList[k]=0；若VMmax上的任務(wù)均被標(biāo)記為不可交換，則完成任務(wù)分配，結(jié)束算法；否則，定義TVMmin為分配在虛擬機(jī)VMmin上的任務(wù)集合，并計(jì)算得出任務(wù)交換函數(shù)MBT(k,l)(公式(13))，其中Bkl、Blk分別表示未交換及交換狀態(tài)下的優(yōu)值函數(shù)值(公式(8)).

MBT(k,l)=max{Blk-Bkl|l∈TVMmin,l=1,2,…,m}

(13)

圖4 BP-Tabu搜索算法偽代碼Fig.4 BP-Tabu algorithm

如果存在任務(wù)l使任務(wù)交換函數(shù)MBT(k,l)大于0，則進(jìn)行任務(wù)交換，定義A?B為A和B值的互換，設(shè)置禁忌值tabuList[l]=0；否則，設(shè)置記錄次數(shù)pt=pt+1.BP-Tabu搜索算法的偽代碼如圖4所示.

在一個(gè)有n個(gè)任務(wù)和m個(gè)虛擬機(jī)資源的云環(huán)境中，假設(shè)任務(wù)數(shù)量n不小于虛擬機(jī)資源數(shù)量m(n≥m)，本文的算法時(shí)間復(fù)雜度主要分為兩部分：

2)BP-Tabu搜索算法中使用禁忌數(shù)組及優(yōu)值交換的策略，計(jì)算可得時(shí)間復(fù)雜度為O(n2).

由此可得，BP-Tabu搜索算法總時(shí)間復(fù)雜度為O(n2).

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)工具與算法實(shí)現(xiàn)

本文實(shí)驗(yàn)使用CloudSim云計(jì)算仿真工具，它是一個(gè)用于云計(jì)算基礎(chǔ)設(shè)施和服務(wù)建模的仿真框架[21].由于BP-Tabu搜索算法添加了工作負(fù)載、多因素優(yōu)值函數(shù)和懲戒策略等特性，因此對工具包CloudSim進(jìn)行擴(kuò)展以滿足模擬實(shí)驗(yàn)要求.

圖5為CloudSim仿真數(shù)據(jù)流圖.在仿真開始前，每個(gè)數(shù)據(jù)中心(DataCenter)實(shí)體會在云信息服務(wù)(CloudInformationService)注冊表中注冊.仿真開始時(shí)，數(shù)據(jù)中心代理類(DataCenterBroker)通過云信息服務(wù)中注冊的數(shù)據(jù)中心，獲取數(shù)據(jù)中心特征信息，為用戶提供合適的資源列表.之后在匹配的數(shù)據(jù)中心中創(chuàng)建虛擬資源進(jìn)行任務(wù)調(diào)度.任務(wù)完成之后，銷毀虛擬資源.

其中DataCenterBroker為數(shù)據(jù)中心代理的功能實(shí)現(xiàn)類，作為云環(huán)境下數(shù)據(jù)中心和云任務(wù)共同協(xié)作的中介者.本文算法的實(shí)現(xiàn)主要通過對DataCenterBroker類進(jìn)行二次開發(fā)來完成，讀者可下載和運(yùn)行BP-Tabu算法相關(guān)程序代碼(https://github.com/viivan/BP-Tabu-for-cloudsim)進(jìn)行深入了解.

圖5 CloudSim仿真數(shù)據(jù)流圖Fig.5 CloudSim simulation data flow

4.1.2 案例背景及CloudSim參數(shù)設(shè)置

有限元分析是指工程項(xiàng)目借助于計(jì)算機(jī)完成，建立計(jì)算模型并進(jìn)行分析計(jì)算，一個(gè)完整的有限元分析過程包括前處理、計(jì)算和后處理三個(gè)過程.其中，計(jì)算過程是有限元分析過程中最重要的一部分，但由于有限元分析計(jì)算量極大，對服務(wù)器性能要求較高，因此，提升有限元求解的計(jì)算效率是當(dāng)前有限元分析領(lǐng)域的研究熱點(diǎn)之一[22].

班主任制度下的PDCA學(xué)風(fēng)管理模式是以班級為單位，以學(xué)生為主體，以班主任為主導(dǎo)的學(xué)習(xí)質(zhì)量控制體系。其中，班級整體學(xué)風(fēng)建設(shè)是大的PD-CA循環(huán)，每個(gè)學(xué)生個(gè)體學(xué)習(xí)質(zhì)量提升是小的PDCA循環(huán)，班級整體學(xué)風(fēng)建設(shè)要依靠學(xué)生個(gè)體學(xué)習(xí)質(zhì)量提升作為動力和檢驗(yàn)指標(biāo)。

本文以有限元分析在云環(huán)境下的任務(wù)調(diào)度為案例展開研究.由于工程項(xiàng)目中，有限元分析的計(jì)算任務(wù)都較為復(fù)雜，因此在使用云計(jì)算仿真框架CloudSim對有限元子任務(wù)進(jìn)行模擬之前，我們采用EBE[23]方法先將有限元計(jì)算任務(wù)拆解為互不干涉的子任務(wù).每個(gè)有限元分析計(jì)算子任務(wù)需要各自計(jì)算單元剛度矩陣、單元載荷向量并進(jìn)行邊界條件處理，然后計(jì)算各子任務(wù)的位移和應(yīng)力，最終整合得到計(jì)算任務(wù)的總體節(jié)點(diǎn)位移和應(yīng)力.

我們首先使用有限元分析軟件對一個(gè)劃分成10萬個(gè)網(wǎng)格節(jié)點(diǎn)的機(jī)械結(jié)構(gòu)進(jìn)行單機(jī)分析，多次計(jì)算后得出平均求解時(shí)間計(jì)為δ≈170s.然后，根據(jù)真實(shí)的有限元分析過程選擇參數(shù)進(jìn)行，仿真實(shí)驗(yàn)設(shè)定實(shí)驗(yàn)的任務(wù)總數(shù)為100～4000，每個(gè)任務(wù)的指令長度MI由隨機(jī)數(shù)產(chǎn)生且各不相同，近似代表了每個(gè)網(wǎng)格節(jié)點(diǎn)數(shù)的計(jì)算量，取值范圍在[1000,5000]；設(shè)定實(shí)驗(yàn)中有10個(gè)虛擬機(jī)資源，每個(gè)虛擬機(jī)的處理能力MIPS由隨機(jī)數(shù)產(chǎn)生且各不相同，取值范圍在[200,400].在以上條件設(shè)定下，模擬環(huán)境中一臺MIPS為300的虛擬機(jī)處理MI總量為10萬的任務(wù)所消耗的時(shí)間可與δ近似.具體參數(shù)設(shè)置如表2所示.

表2 參數(shù)設(shè)置表Table 2 Parameter setting

4.2 仿真實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文提出的BP-Tabu搜索算法的性能及有效性，以有限元分析在云環(huán)境下的任務(wù)調(diào)度為應(yīng)用背景，與常見的任務(wù)調(diào)度算法進(jìn)行比較，包括有限元分析中的默認(rèn)輪詢算法RR[24]、融入貪心策略的Min-Max調(diào)度算法[11]、基于蟻群優(yōu)化任務(wù)調(diào)度算法ACO[15]、基于禁忌搜索的負(fù)載均衡任務(wù)調(diào)度優(yōu)化算法[18](以下簡稱Tabu).為了保證對比的公平性，實(shí)驗(yàn)環(huán)境均為：Mac OS X 10.11.3 EI Capitan系統(tǒng)平臺、主頻2.7Hz、內(nèi)存8GB，編程及調(diào)試環(huán)境MyEclipse 2014.

本文主要用來驗(yàn)證的評價(jià)指標(biāo)如下：

1) 任務(wù)總體完成時(shí)間；

2) 負(fù)載均衡度；

3) 資源利用率；

4.2.1 任務(wù)總體完成時(shí)間

本節(jié)實(shí)驗(yàn)側(cè)重任務(wù)總體完成時(shí)間的比較，因此設(shè)置在任務(wù)總數(shù)分別為1000、2000、3000和4000的情況下，使用RR算法、Min-Max算法、ACO算法、Tabu算法和BP-Tabu算法這5種不同的任務(wù)調(diào)度算法進(jìn)行實(shí)驗(yàn)對比，五種算法的任務(wù)總體完成時(shí)間如圖6所示.

圖6 5種算法的任務(wù)總體完成時(shí)間Fig.6 Makespan of the five algorithms

從圖6得出：在任務(wù)數(shù)量的不斷增長的情況下，任務(wù)總體完成時(shí)間呈線性增長；在相同任務(wù)總數(shù)的情況下，BP-Tabu算法的任務(wù)總體完成時(shí)間最優(yōu)，且各類算法都優(yōu)于有限元分析默認(rèn)的輪詢RR算法.

同時(shí)，為了評估本文提出的懲戒策略的有效性，在相同實(shí)驗(yàn)條件下，本文將BP-Tabu算法與其未添加懲戒策略的情況下(稱為B-Tabu)進(jìn)行實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果如圖7所示.

從圖7可以得出：任務(wù)量較小時(shí)，BP-Tabu算法與B-Tabu算法的任務(wù)總體完成時(shí)間大致趨于一致，當(dāng)任務(wù)量逐漸增大時(shí)，擁有懲戒策略的BP-Tabu算法的任務(wù)總體完成時(shí)間漸漸優(yōu)于B-Tabu算法.由此可以得出，任務(wù)量較大時(shí)，B-Tabu算法容易陷入局部最優(yōu)的局面，本文的懲戒策略在局部最優(yōu)問題上具有一定程度的優(yōu)化效果.

圖7 BP-Tabu與B-Tabu的任務(wù)總體完成時(shí)間Fig.7 Makespan of BP-Tabu and B-Tabu

4.2.2 負(fù)載均衡度

本節(jié)實(shí)驗(yàn)側(cè)重負(fù)載均衡度的比較，因此根據(jù)任務(wù)數(shù)量大小分別設(shè)置兩組實(shí)驗(yàn)進(jìn)行對比，第一組實(shí)驗(yàn)任務(wù)數(shù)量分別為100、200、300、400，第二組實(shí)驗(yàn)任務(wù)數(shù)量分別為1000、2000、3000、4000.使用RR算法、Min-Max算法、ACO算法、Tabu算法和BP-Tabu算法這5種不同的任務(wù)調(diào)度算法進(jìn)行實(shí)驗(yàn)對比.其中，對于某一任務(wù)調(diào)度方案P，其負(fù)載均衡為LBp(公式(6)).兩組實(shí)驗(yàn)的負(fù)載均衡度如圖8、圖9所示.

圖8 任務(wù)量較小時(shí)五種算法的負(fù)載均衡度Fig.8 Load balancing of the five algorithm with small tasks

圖9 任務(wù)量較大時(shí)五種算法的負(fù)載均衡度Fig.9 Load balancing of the five algorithm with large tasks

從圖8可以得出：有限元分析默認(rèn)的RR算法未考慮到計(jì)算資源的負(fù)載均衡，因此其負(fù)載均衡度最差；Min-Max算法通過大小任務(wù)"捆綁"的方式，一定程度上起到了負(fù)載均衡的作用，因此其負(fù)載均衡度優(yōu)于RR算法，但與Tabu、ACO和BP-Tabu三種算法相比，后三者的負(fù)載均衡度均更優(yōu).從圖9可以得出，隨著任務(wù)量的不斷增大，基于多因素優(yōu)值函數(shù)的BP-Tabu算法的負(fù)載均衡度較低，云環(huán)境下的虛擬機(jī)負(fù)載較均衡.

4.2.3 資源利用率

本節(jié)實(shí)驗(yàn)側(cè)重資源利用率的比較，因此設(shè)置在任務(wù)總數(shù)分別為1000、2000、3000和4000的情況下，使用RR算法、Max-Min算法、ACO算法、Tabu算法和BP-Tabu算法這五種不同的任務(wù)調(diào)度算法進(jìn)行實(shí)驗(yàn)對比，5種算法的資源利用率如圖10所示.

從圖10得出,RR算法未考慮到資源利用率情況，因此利用率最低；Min-Max和ACO算法資源利用率低于Tabu、BP-Tabu算法；而BP-Tabu相較Tabu算法，增加了包含虛擬機(jī)利用率的多因素優(yōu)值函數(shù)，因此資源利用率優(yōu)于Tabu算法.

圖10 系統(tǒng)整體資源利用率Fig.10 Utilization rate of entire system

5 結(jié)束語

本文提出了一種基于BP-Tabu的云任務(wù)負(fù)載均衡調(diào)度策略，適用于云環(huán)境下任務(wù)調(diào)度的負(fù)載均衡方面，能夠克服現(xiàn)有云資源任務(wù)調(diào)度方法陷入任務(wù)分配不均衡、單臺虛擬機(jī)資源負(fù)載過大或者空閑較多的問題.該策略綜合考慮任務(wù)總完成時(shí)間及虛擬機(jī)負(fù)載均衡度，首先通過時(shí)間貪心求得策略初始解，進(jìn)而結(jié)合多因素優(yōu)值函數(shù)的Tabu算法優(yōu)化任務(wù)調(diào)度的負(fù)載均衡，再進(jìn)一步提出懲戒策略幫助BP-Tabu算法跳出局部最優(yōu).并以有限元分析在云環(huán)境下的任務(wù)調(diào)度為應(yīng)用背景，通過CloudSim進(jìn)行仿真實(shí)驗(yàn)，證明此算法不僅縮短了復(fù)雜有限元任務(wù)執(zhí)行的總體完成時(shí)間，同時(shí)優(yōu)化了虛擬資源負(fù)載均衡度，可見云任務(wù)調(diào)度技術(shù)在優(yōu)化傳統(tǒng)行業(yè)的復(fù)雜工程計(jì)算任務(wù)方面，具有一定的研究價(jià)值和現(xiàn)實(shí)意義.但本文的工作默認(rèn)任務(wù)是相互獨(dú)立的，未考慮用戶QoS因素對任務(wù)調(diào)度的影響，因此在下一步研究中還需加入任務(wù)優(yōu)先級等QoS因素來改進(jìn)此算法.