一種云計(jì)算環(huán)境下的改進(jìn)任務(wù)調(diào)度算法*

張思豪，田建宇，劉銀良，劉經(jīng)天，劉衛(wèi)新

（北方自動(dòng)控制技術(shù)研究所，太原 030006）

0 引言

云計(jì)算已經(jīng)成為當(dāng)前大規(guī)模和復(fù)雜計(jì)算的最突出的架構(gòu)。它只需最少的管理工作和信息交互，便能夠完成對(duì)共享資源的按需網(wǎng)絡(luò)訪問，快速地提供和釋放訪問資源。隨著數(shù)以百萬計(jì)的用戶向云系統(tǒng)提交計(jì)算任務(wù)，任務(wù)調(diào)度機(jī)制在其中的作用越發(fā)顯著。

任務(wù)調(diào)度是指將一組任務(wù)分配給可用虛擬機(jī)的技術(shù)。任務(wù)調(diào)度機(jī)制的主要作用是在不影響服務(wù)質(zhì)量的情況下提高資源利用率。任務(wù)調(diào)度算法分為兩種：確定性算法和元啟發(fā)式算法。

確定性調(diào)度算法包括先來先服務(wù)調(diào)度算法（first come first served，F(xiàn)CFS）、輪詢算法（round robin，RR）、短進(jìn)程優(yōu)先算法（shortest job first，SJF）和慢速資源負(fù)載均衡算法（load balance over slow resources，LBSR）等傳統(tǒng)調(diào)度算法。確定性算法是任務(wù)調(diào)度中常見的基本算法。

元啟發(fā)算法包括爬山（hill climbing，HC）、模擬退火（simulated annealing，SA）、禁忌搜索（tabu search，TS）、蟻群優(yōu)化（ant colony optimization，ACO）、布谷鳥搜索（cuck searc，CS）和粒子群優(yōu)化（particle swarm optimizatio，PSO）等算法。這些算法的作用在于尋找一個(gè)近似解，當(dāng)使用確定性算法無法獲得精確的解決方案時(shí)，尋求近似解的方式將會(huì)大大提高工作效率。

粒子群優(yōu)化算法是元啟發(fā)算法中最常用的求解最優(yōu)問題的算法之一。但是，使用該算法調(diào)度大量任務(wù)會(huì)降低系統(tǒng)性能。本文在粒子群算法的基礎(chǔ)上，通過改進(jìn)提出一種新的調(diào)度算法，在不影響系統(tǒng)性能的前提下對(duì)大量任務(wù)進(jìn)行調(diào)度。它以均衡、動(dòng)態(tài)的方式將提交的任務(wù)劃分為多個(gè)批次。該算法主要考慮兩個(gè)參數(shù)：任務(wù)的數(shù)量和每批任務(wù)的總長(zhǎng)度。

1 云計(jì)算環(huán)境下的任務(wù)調(diào)度

任務(wù)調(diào)度是一個(gè)將傳入任務(wù)分配給可用資源的進(jìn)程。任務(wù)調(diào)度算法的主要目標(biāo)是在不影響云的服務(wù)參數(shù)情況下最大化資源利用率。圖1 顯示了在云環(huán)境中完成基本調(diào)度的過程。由圖可知，任務(wù)調(diào)度分為3 個(gè)階段，第1 個(gè)流程是信息提供，任務(wù)調(diào)度程序?qū)娜蝿?wù)管理器中搜集信息，計(jì)算任務(wù)屬性，并在資源管理器中監(jiān)視現(xiàn)有可用資源，以便為任務(wù)進(jìn)行合理的資源分配；第2 個(gè)過程是選擇過程，根據(jù)資源和任務(wù)的具體參數(shù)選擇目標(biāo)資源。這些參數(shù)包括任務(wù)規(guī)模、任務(wù)優(yōu)先級(jí)、可靠性因子、基于作業(yè)的資源消耗成本和任務(wù)的動(dòng)態(tài)時(shí)間長(zhǎng)度，然后，任務(wù)調(diào)度程序?qū)⑷蝿?wù)分配計(jì)劃發(fā)送給資源管理器；第3 個(gè)過程是任務(wù)分配過程，該過程中任務(wù)管理器會(huì)將現(xiàn)有任務(wù)分配給適當(dāng)?shù)馁Y源進(jìn)行處理。

圖1 云計(jì)算下的任務(wù)調(diào)度

在粒子群算法中，種群中的每個(gè)成員被稱為粒子，種群稱為群。一個(gè)隨機(jī)初始化的種群中粒子向隨機(jī)選擇的方向移動(dòng)，每個(gè)粒子通過搜索空間，記住自己與其他例子間的最好位置。最后，在搜索過程中，所有粒子都會(huì)逐漸趨向更好的位置，直到整個(gè)種群分布到一個(gè)最優(yōu)位置。但是粒子群算法會(huì)導(dǎo)致算法速度和方向調(diào)節(jié)能力的降低，當(dāng)粒子群算法的種群和搜索空間擴(kuò)大時(shí)，尋找最優(yōu)解的過程會(huì)變得更加困難。

在云環(huán)境下，基于粒子群的任務(wù)調(diào)度算法的最終目的在于最小化最大完工時(shí)間和提高任務(wù)調(diào)度服務(wù)質(zhì)量水平。由于粒子群算法在數(shù)據(jù)較大的情況下性能較差，研究人員為此提出了許多改進(jìn)算法，這些算法包括改進(jìn)的粒子群算法和混合粒子群算法?；旌狭Ｗ尤核惴軌蛟谡{(diào)度少量任務(wù)時(shí)降低最大完工時(shí)間和標(biāo)準(zhǔn)偏差，但在提高調(diào)度性能方面并沒有太多優(yōu)勢(shì)。針對(duì)目前改進(jìn)算法的局限性，本文提出了一種新的任務(wù)調(diào)度算法——改進(jìn)粒子群優(yōu)化算法（improved particle swarm optimization，IPSO）。

2 改進(jìn)粒子群優(yōu)化算法

改進(jìn)粒子群優(yōu)化算法的主要目標(biāo)是將大量任務(wù)優(yōu)化調(diào)度到云計(jì)算環(huán)境中的可用虛擬機(jī)，并在調(diào)度中使完工時(shí)間最小化，資源利用率最大化。下頁表1 為數(shù)學(xué)分析所用到的符號(hào)說明。

表1 數(shù)學(xué)分析符號(hào)說明

VM 由L 個(gè)主機(jī)組成，每個(gè)主機(jī)上存在m 個(gè)可用虛擬機(jī)。使用VM表示第i 個(gè)資源；假設(shè)云系統(tǒng)已經(jīng)接收到n 個(gè)任務(wù)，使用T表示第j 個(gè)任務(wù)，這些任務(wù)具有不同的大小，并且彼此獨(dú)立。

調(diào)度器負(fù)責(zé)為提交的n 個(gè)任務(wù)找到m 個(gè)可用虛擬機(jī)VM 的最優(yōu)分配方案。分配方案矩陣P 可表示為：

分配方案矩陣由表示第j 個(gè)任務(wù)T是否分配給虛擬機(jī)VM的二進(jìn)制變量組成。它可以表述如下：

IPSO 的控制結(jié)構(gòu)由分批收集任務(wù)、分批調(diào)度和最終分配計(jì)劃再平衡3 個(gè)階段組成。其流程結(jié)構(gòu)如圖2 所示，算法的主要階段描述如下：

圖2 改進(jìn)任務(wù)調(diào)度算法流程結(jié)構(gòu)

2.1 階段1：分批收集任務(wù)

在這個(gè)階段，任務(wù)到達(dá)就緒隊(duì)列。當(dāng)所有的待調(diào)度任務(wù)完成排隊(duì)，就會(huì)計(jì)算任務(wù)屬性。

為了最大限度地利用資源，使用了一個(gè)新的參數(shù)μ 作為資源利用狀態(tài)的領(lǐng)先指標(biāo)。它是表示可用資源平均值的利用率檢查的主要參考，計(jì)算如下：

采用自適應(yīng)拆分方法批量收集任務(wù)。IPSO 通過式（4）來累積任務(wù)長(zhǎng)度之和BL：

當(dāng)批量收集任務(wù)的長(zhǎng)度超出資源使用狀態(tài)時(shí)，停止批量收集任務(wù)。該算法將批處理長(zhǎng)度設(shè)定為始終小于或等于平均可用資源，可以表示為：

2.2 階段2：分批調(diào)度

在將任務(wù)分批收集后，調(diào)度程序嘗試為每批任務(wù)尋找最優(yōu)分配方案，此階段將通過任務(wù)調(diào)度算法將每批次的任務(wù)分配到相應(yīng)虛擬機(jī)。

首先，粒子群算法用創(chuàng)建的一組隨機(jī)解來對(duì)粒子群進(jìn)行初始化，然后通過群體內(nèi)粒子的更新迭代來搜索最優(yōu)解。因此，首先對(duì)迭代T 中的粒子位置矩陣和速度矩陣進(jìn)行隨機(jī)初始化；其次在每次迭代中，每個(gè)粒子需要兩個(gè)最優(yōu)值進(jìn)行更新，即個(gè)人最優(yōu)值和全局最優(yōu)值。此外，該過程考慮了用于控制速度的慣性權(quán)重（ω）的值。它取決于預(yù)定義的慣量權(quán)值的最大可能值（ω）和預(yù)定義的最小可能值（ω）。

在找到個(gè)人最優(yōu)值和全局最優(yōu)值的最佳值后，粒子以式（8）和式（9）來更新其速度和位置。

對(duì)于每個(gè)粒子分配矩陣，VM執(zhí)行分配的S 任務(wù)的完成時(shí)間可以表示為：

粒子的最優(yōu)位置解由適應(yīng)度函數(shù)來評(píng)估，適應(yīng)度函數(shù)以目標(biāo)完工時(shí)間為基礎(chǔ)，估計(jì)調(diào)度之間的效率。為了滿足所提算法的主要目標(biāo)，找到PSO 的最優(yōu)解，適應(yīng)度函數(shù)表示為式（11），使用該公式計(jì)算每個(gè)VM 的完成時(shí)間，并返回最高完成時(shí)間作為每個(gè)PSO 粒子的適應(yīng)度值：

PSO 將所有粒子的最優(yōu)位置更新為：

粒子群算法將對(duì)種群內(nèi)的每個(gè)粒子重復(fù)上述步驟，直到達(dá)到設(shè)置的最大迭代次數(shù)。最后，粒子群算法考慮到目前為止所找到的最優(yōu)解為最終解。一旦PSO 終止，則建立當(dāng)前批次的次最優(yōu)分配方案。IPSO 將這個(gè)次優(yōu)分配計(jì)劃附加到最終分配計(jì)劃中。IPSO 開始對(duì)前面的步驟進(jìn)行新的迭代，以找到下一批產(chǎn)品適當(dāng)?shù)拇巫顑?yōu)分配計(jì)劃。最后，將所有次優(yōu)分配方案添加到最終分配方案中。

2.3 第3 階段：重新平衡最終分配計(jì)劃

在此階段，改進(jìn)算法將在所有資源上平衡負(fù)載。此階段的再平衡過程基于將任務(wù)從負(fù)載最重、完成時(shí)間最長(zhǎng)的虛擬機(jī)轉(zhuǎn)移到負(fù)載最輕、完成時(shí)間最短的虛擬機(jī)。在此階段開始時(shí)，可用資源列表中包含了所有可用的虛擬機(jī)。當(dāng)列表變?yōu)榭諘r(shí)，階段結(jié)束。重新平衡過程可以總結(jié)如下：

1）計(jì)算所有利用虛擬機(jī)的完成時(shí)間。

2）將完成時(shí)間最長(zhǎng)的虛擬機(jī)作為負(fù)載最大的虛擬機(jī)加入可用資源列表中。在最任務(wù)重的虛擬機(jī)中，第1 個(gè)任務(wù)被認(rèn)為是當(dāng)前任務(wù)。

3）將完成時(shí)間最短的虛擬機(jī)設(shè)置為負(fù)載最輕的虛擬機(jī)。并將負(fù)載最重的虛擬機(jī)中的當(dāng)前任務(wù)移動(dòng)到負(fù)載最輕的虛擬機(jī)中。

4）如果此動(dòng)作產(chǎn)生的最大完工時(shí)間小于之前計(jì)算的最大完工時(shí)間，則接受更改，并更新兩臺(tái)機(jī)器的完工時(shí)間。如果此移動(dòng)產(chǎn)生的最大時(shí)間間隔大于先前計(jì)算的最大時(shí)間間隔，則該動(dòng)作將被拒絕

5）如果當(dāng)前最重的資源中有其他任務(wù)，則將下一個(gè)任務(wù)設(shè)置為當(dāng)前任務(wù)，執(zhí)行步驟3）。否則，將當(dāng)前最重的虛擬機(jī)從可用資源列表中移除。

6）如果可用資源列表中有任何可用資源，則轉(zhuǎn)到步驟2）。

7）最后當(dāng)可用資源列表為空時(shí)，均衡進(jìn)程停止。

2.4 改進(jìn)算法的時(shí)間復(fù)雜度

IPSO 算法的復(fù)雜性是基于其3 個(gè)主要階段來衡量的。為了找到在m 個(gè)虛擬機(jī)上分批為k 個(gè)批次的n 個(gè)任務(wù)的分配計(jì)劃，算法的復(fù)雜度計(jì)算如下所示：

階段1：（分批收集任務(wù)階段）此階段應(yīng)用于提交到系統(tǒng)的n 個(gè)任務(wù)。在這個(gè)階段，任務(wù)調(diào)度器從任務(wù)管理器和資源管理器收集信息來創(chuàng)建合適的批次。提交的n 個(gè)任務(wù)根據(jù)兩個(gè)閾值分成k 批任務(wù)。這個(gè)階段的復(fù)雜度是O（n）。

階段2：（分批調(diào)度階段）IPSO 系統(tǒng)提供k 個(gè)批次，可以覆蓋n 個(gè)提交的任務(wù)。利用粒子群優(yōu)化算法對(duì)每批數(shù)據(jù)進(jìn)行調(diào)度，得到其次優(yōu)解。PSO 算法的復(fù)雜度為O（n）。PSO 將這一步重復(fù)k 次，因此，這一階段的復(fù)雜度為k*O（n）。而k 被認(rèn)為是一個(gè)最小的數(shù)字，可以忽略。因此，該階段的復(fù)雜度為O（n）。

階段3：（重新平衡最終分配計(jì)劃階段）在這個(gè)階段，IPSO 試圖在所有m 資源上平衡負(fù)載。這個(gè)階段的再平衡過程是基于將任務(wù)從負(fù)載最重的虛擬機(jī)移動(dòng)到負(fù)載最輕的虛擬機(jī)。平衡器的復(fù)雜度是m*O（n），而m＜＜n，所以m 可以忽略，因此，該階段的復(fù)雜度為O（n）。

IPSO 算法總復(fù)雜度為O（n+n+n）=O（n+2n）≈O（n）。因此，IPSO 算法的復(fù)雜度為O（n）。

2.5 評(píng)價(jià)指標(biāo)

IPSO 的評(píng)價(jià)指標(biāo)由兩個(gè)性能指標(biāo)來衡量，不平衡程度（DI）和負(fù)載標(biāo)準(zhǔn)差（σ）。

不均衡DI 用來衡量各虛擬機(jī)之間的不平衡度。因此，在分配時(shí)考慮DI 可以避免不平衡的虛擬機(jī)工作負(fù)載。

標(biāo)準(zhǔn)差σ 表明從平均開始調(diào)度任務(wù)存在量的變化或彌散。

3 仿真實(shí)現(xiàn)及結(jié)果

為了評(píng)估IPSO 的效率，實(shí)驗(yàn)使用CloudSim 對(duì)不同的任務(wù)調(diào)度技術(shù)進(jìn)行建模和仿真。在仿真結(jié)果的基礎(chǔ)上，分析改進(jìn)算法的性能。

3.1 模擬配置

CloudSim 是一種仿真工具，可用于評(píng)估所提改進(jìn)算法與其他算法的性能，并在最大完工時(shí)間、標(biāo)準(zhǔn)偏差和不平衡程度方面與其他算法的結(jié)果進(jìn)行比較，實(shí)驗(yàn)仿真環(huán)境如表2 所示。

表2 實(shí)驗(yàn)仿真環(huán)境

3.2 仿真結(jié)果

為了評(píng)價(jià)該算法的性能，本文將改進(jìn)算法與基于蟻群的任務(wù)調(diào)度算法（PSO），蟻群優(yōu)化算法（ACO），蜂群算法（LBA_HB）和輪詢算法（RR）4 種群算法進(jìn)行了比較。

對(duì)于ACO 和LBA_HB，仿真參數(shù)是根據(jù)它們?cè)谠u(píng)估中使用的實(shí)驗(yàn)設(shè)置來配置的。圖3 顯示了任務(wù)數(shù)量從3 000～10 000 變化時(shí)任務(wù)調(diào)度算法的最大時(shí)間?？梢钥闯觯c其他算法相比，IPSO 算法實(shí)現(xiàn)了這5 種算法中最小的完工時(shí)間。在3 000 個(gè)任務(wù)時(shí)，IPSO 的最大完工時(shí)間小于LBA_HB（25%）。當(dāng)任務(wù)數(shù)量增加時(shí)，IPSO 算法的最大完工時(shí)間與其他4 種算法的最大完工時(shí)間之差也在增大。當(dāng)任務(wù)數(shù)達(dá)到10 000 時(shí)，IPSO 的最大完工時(shí)間約為190 ms，而蟻群算法的完工時(shí)間約為600 ms。這間接地證明了所提算法對(duì)資源的有效利用。

圖3 完成時(shí)間對(duì)比

圖4 顯示了被評(píng)估算法的標(biāo)準(zhǔn)差的變化。每個(gè)虛擬機(jī)完成時(shí)間的正常標(biāo)準(zhǔn)偏差是該虛擬機(jī)完成時(shí)間與所有虛擬機(jī)平均完成時(shí)間的變化。由圖知，與其他4 種算法相比，所提出的IPSO 大大降低了標(biāo)準(zhǔn)差。

圖4 負(fù)載標(biāo)準(zhǔn)差對(duì)比

IPSO 通過使用再平衡過程防止將請(qǐng)求分配給加載的虛擬機(jī)。因此，它在減少完成時(shí)間的同時(shí)有效地實(shí)現(xiàn)了負(fù)載均衡。在分配過程中，考慮虛擬機(jī)的不平衡程度將有助于避免虛擬機(jī)出現(xiàn)工作負(fù)載失衡的情況。圖5 給出了RR、ACO、LBA_HB、PSO和IPSO 算法的不平衡程度。由圖可知，所提出的IPSO 算法的不平衡程度最小，它可以防止失衡的工作負(fù)載情況。

圖5 不平衡度對(duì)比

此外，在與其他元啟發(fā)算法對(duì)比的基礎(chǔ)上，對(duì)比文獻(xiàn)［17-19］中所提3 種粒子群改進(jìn)算法：基于吞噬雙重判定的改進(jìn)遺傳算法任務(wù)調(diào)度（PGA_PSO）、自適應(yīng)t 分布的改進(jìn)粒子群任務(wù)調(diào)度算法（t-PSO）、基于混沌擾動(dòng)的粒子群優(yōu)化算法（NPSO）得到表3，當(dāng)任務(wù)數(shù)量為7 000 時(shí)，IPSO 算法的最大完工時(shí)間相比PGA_PSO 降低了約21%，比t-PSO 降低了約33%，比NPSO 降低了約27%。當(dāng)任務(wù)數(shù)量繼續(xù)增加時(shí)，IPSO 算法的標(biāo)準(zhǔn)偏差顯著降低。

表3 改進(jìn)粒子群算法與粒子群算法的比較

4 結(jié)論

為了節(jié)約調(diào)度任務(wù)完成時(shí)間，提高集群資源利用率，實(shí)現(xiàn)高效的任務(wù)調(diào)度，本文提出了一種新的任務(wù)調(diào)度算法IPSO。該算法通過將大的任務(wù)列表分批處理成小的子列表，以減少每個(gè)虛擬機(jī)上的工作量。使用領(lǐng)先指標(biāo)，在每次創(chuàng)建任務(wù)量時(shí)評(píng)估資源使用狀態(tài)。在使用粒子群算法（PSO）為每個(gè)批次獲得次最優(yōu)解的基礎(chǔ)上，改進(jìn)算法（IPSO）在資源之間進(jìn)行負(fù)載平衡。采用仿真建模的方式，本文將所提出的算法IPSO 與現(xiàn)有的ACO，LBA_HB 和PSO 任務(wù)調(diào)度算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法IPSO 能有效地縮短最大完工時(shí)間，同時(shí)還降低了標(biāo)準(zhǔn)偏差和不平衡程度。除此之外，本文提出的任務(wù)調(diào)度算法可以通過考慮其他目標(biāo)函數(shù)，如成本消耗等條件，進(jìn)一步得到擴(kuò)展和優(yōu)化。