顧陽(yáng)，李敏，李華

（廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，南寧 530023）

0 引言

云環(huán)境是一個(gè)異構(gòu)的分布式計(jì)算平臺(tái)，為用戶提供方便的可用資源，包括網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)、軟件等。由于成千上萬(wàn)的用戶同時(shí)使用云環(huán)境，任務(wù)數(shù)量龐大，因此任務(wù)調(diào)度算法對(duì)云平臺(tái)的性能穩(wěn)定有著重要影響，具有理論研究意義。任務(wù)調(diào)度一般可分為動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度。動(dòng)態(tài)調(diào)度算法會(huì)根據(jù)實(shí)時(shí)調(diào)度來(lái)調(diào)整結(jié)果，具有較強(qiáng)的適應(yīng)性和靈活性，但存在諸多不確定因素。靜態(tài)調(diào)度算法則通常需要獲取實(shí)時(shí)任務(wù)信息，具有簡(jiǎn)單高效、成本低廉等特性。本文總結(jié)了當(dāng)前部分任務(wù)調(diào)度算法，包括傳統(tǒng)的任務(wù)調(diào)度算法、啟發(fā)式任務(wù)調(diào)度算法和商業(yè)應(yīng)用中的任務(wù)調(diào)度算法，并在此基礎(chǔ)上對(duì)其進(jìn)行評(píng)估總結(jié)。

1 問題定義

在云環(huán)境中，任務(wù)調(diào)度的任務(wù)通?？梢员怀橄鬄樗脑M（T,?,C,D）[1],在這個(gè)四元組中，T=（t1，t2，...，tn）是可執(zhí)行任務(wù)的集合；?描述任務(wù)之間的部分順序，例如，ti? tj表明任務(wù) ti應(yīng)該在任務(wù) tj之前執(zhí)行；C={c1，c2，...，cn}是任務(wù)集 T 中所有任務(wù)的計(jì)算，ci是任務(wù) ti的計(jì)算；D是n×n矩陣，Dij是從任務(wù)ti到任務(wù)tj的數(shù)據(jù)量。根據(jù)任務(wù)之間是否存在依賴關(guān)系或優(yōu)先約束條件，我們可以將任務(wù)劃分為獨(dú)立的組件任務(wù)和工作流任務(wù)，獨(dú)立的組件任務(wù)可以用一個(gè)二元組（T，C）來(lái)描述，工作流任務(wù)因?yàn)橐蕾嚮騼?yōu)先約束可以用有向無(wú)環(huán)圖（DAG）來(lái)表示。

2 任務(wù)調(diào)度算法分析

2.1 傳統(tǒng)的任務(wù)調(diào)度算法

一般地，我們假設(shè)可以得到每個(gè)任務(wù)的執(zhí)行時(shí)間和每個(gè)機(jī)器最早可用時(shí)間。機(jī)器最早的可用時(shí)間加上任務(wù)的執(zhí)行時(shí)間等于機(jī)器上任務(wù)的最小完成時(shí)間。我們將從任務(wù)集T中的第一個(gè)任務(wù)開始到任務(wù)集T中的上一個(gè)任務(wù)結(jié)束的時(shí)間定義為完工周期。我們的目標(biāo)是獲得最小完工時(shí)間。

（1）OLB，MET，MCT，Duplex和 KPB

OLB算法主要考慮到機(jī)器最早的可用時(shí)間，所以無(wú)法保證任務(wù)將被分配到最小的機(jī)器執(zhí)行時(shí)間。而MET算法是以最短的執(zhí)行時(shí)間將任務(wù)分配給機(jī)器，而不是最早的可用時(shí)間，結(jié)果可能出現(xiàn)負(fù)載不平衡。MCT算法選擇以最早的完成時(shí)間分配一個(gè)任務(wù)給機(jī)器，但是可能導(dǎo)致一些任務(wù)不能以最小的執(zhí)行時(shí)間分配給機(jī)器，結(jié)果使得制造時(shí)間變長(zhǎng)，MCT算法優(yōu)于OLB算法和MET算法。Duplex算法和KPB算法都是基于MET和MCT的，它們的區(qū)別在于Duplex算法是根據(jù)系統(tǒng)負(fù)載均衡參數(shù)來(lái)選擇MET或MCT算法。而KPB算法設(shè)置一個(gè)名為K（100/n≦K≦100）的參數(shù)，并選擇n×（K/100）個(gè)機(jī)器按任務(wù)的執(zhí)行時(shí)間分配任務(wù)。

（2）MinMin算法、MaxMin算法和Sufferage算法

不同于前面提到的算法，MinMin和MaxMin算法都考慮到了所有集中任務(wù)，而不僅僅是當(dāng)前的任務(wù)。MinMin算法在任務(wù)長(zhǎng)度變得不均勻時(shí)，性能會(huì)有所下降，因?yàn)樗偸窍确峙湫∪蝿?wù)會(huì)導(dǎo)致大任務(wù)的長(zhǎng)時(shí)間等待，并且這個(gè)完成時(shí)間會(huì)迅速增加，此外，系統(tǒng)的負(fù)載將會(huì)是不平衡的。而MaxMin算法在這種情況下會(huì)先分配大任務(wù)，同時(shí)執(zhí)行大任務(wù)和小任務(wù)，從而減少執(zhí)行時(shí)間。為了解決這一問題，Zhou[2]提出了一種基于MinMin和MaxMin算法的動(dòng)態(tài)啟發(fā)式H-MM算法。該算法將提高分配的質(zhì)量，但該算法通過每個(gè)處理單元分配的狀態(tài)值來(lái)判斷是否將任務(wù)分配給機(jī)器，否則，算法將比較任務(wù)的超時(shí)和機(jī)器上任務(wù)的超時(shí)，選擇更大的任務(wù)分配任務(wù)。另一個(gè)任務(wù)將回到未分配的任務(wù)集并等待下一個(gè)分配，所以可能會(huì)增加算法復(fù)雜度。

2.2 基于啟發(fā)式思想的任務(wù)調(diào)度算法

（1）遺傳算法（GA）

遺傳算法于1975年由美國(guó)教授Holland J提出[3]。這是一個(gè)隨機(jī)搜索算法，參考生物圈中自然規(guī)律和機(jī)制。一般情況下，我們用1×n向量來(lái)描述染色體，n是任務(wù)數(shù)量，向量的各個(gè)元素代表被分配的某個(gè)機(jī)器。例如，假設(shè)有六個(gè)任務(wù)D和三個(gè)機(jī)器M，名為R=[1,3,2,3,1,2]的染色體，指的是D1和D5分配給M1，D3和D6分配到M2，D2和D4分配到M3。當(dāng)染色體被隨機(jī)生成一定數(shù)量，再根據(jù)每個(gè)任務(wù)執(zhí)行在所有機(jī)器上的最早可用時(shí)間，計(jì)算任務(wù)分配解決方案的完工時(shí)間，并將完工時(shí)間設(shè)置為染色體的適應(yīng)度。然后，算法通過不斷地選擇、交叉和變異，以獲得最優(yōu)的調(diào)度方案。

（2）模擬退火算法（SA）

模擬退火算法是1953年Metropolis被固體材料的退火過程所啟發(fā)而提出的[4]，并被Kirkpatrick于1983年應(yīng)用于最優(yōu)組合問題[5]。它是采取循環(huán)搜索的搜索策略來(lái)尋求最優(yōu)解。首先是對(duì)空間經(jīng)行進(jìn)行編碼，SA的編碼風(fēng)格與GA相同，不同之處在于SA在一個(gè)周期內(nèi)只考慮一個(gè)解。SA通過變異得到新的解，同時(shí)由公式（1）得到基于概率的非最優(yōu)解。經(jīng)過一輪循環(huán)搜索后，如果新解決方案的完工時(shí)間少于原解決方案，SA將接受新解決方案作為當(dāng)前的解決方案；否則SA將產(chǎn)生一個(gè)隨機(jī)數(shù)z ? random[0,1]。如果z>y，SA將接受新的解為當(dāng)前解；否則，將維持原始解決方案。

在公式中，Tk是系統(tǒng)的當(dāng)前溫度，一般是調(diào)度的完成時(shí)間；f（s1）是提出調(diào)度完成時(shí)間的新解決方案。我們可以發(fā)現(xiàn)，當(dāng)f（s0）和f（s1）大小相同或者Tk的值大時(shí)，y接近于0.5，這意味著非最優(yōu)解的接受概率為50%；否則，y接近于1，表示非最優(yōu)解的接受概率為0。所以，SA具有較好的漸進(jìn)收斂性和并行性，但它可能容易陷入局部最優(yōu)解中。

（3）蟻群優(yōu)化算法（ACO）

蟻群優(yōu)化算法是1992年由Marco Dorigo提出的[6]，靈感來(lái)自螞蟻在尋找食物時(shí)尋找路徑的行為。ACO由于其并發(fā)性和可擴(kuò)展性而在解決調(diào)度問題上有很好的效果。在文獻(xiàn)[7]中，作者將ACO應(yīng)用在調(diào)度任務(wù)中。我們利用信息素來(lái)隨時(shí)描述可能影響資源狀況的因素。當(dāng)資源進(jìn)入系統(tǒng)時(shí)，應(yīng)該將其性能參數(shù)的值提交給系統(tǒng)，例如PE的個(gè)數(shù)等。資源監(jiān)控器會(huì)根據(jù)公式（2）對(duì)這些信息素進(jìn)行初始化，并分別驗(yàn)證其參數(shù)。當(dāng)資源出現(xiàn)故障或者新的任務(wù)被分配或者某些任務(wù)已經(jīng)完成時(shí)，算法將根據(jù)公式（3）更新從調(diào)度中心到相關(guān)資源的路徑上的信息素。在任務(wù)完成之后，新任務(wù)分配給資源的概率將根據(jù)公式（4）重新計(jì)算。

在公式（2）中，Δτj(0)是資源j路徑上的原始信息素；m代表PE的數(shù)量；c代表參數(shù)長(zhǎng)度；p代表單個(gè)PE的處理速度；sj代表資源j的傳輸時(shí)間。公式（3）中，Δτj是資源監(jiān)測(cè)中心到資源sj的路徑上的信息素變化值，ρ（0≤ρ≤1）是信息素的保留因子，1-ρ是信息素的揮發(fā)因子。當(dāng)任務(wù)分配給資源j時(shí)，Δτj=-K，K是任務(wù)的計(jì)算；當(dāng)資源j上的任務(wù)執(zhí)行成功并返回任務(wù)時(shí)，Δτj=Ce°K，Ce是鼓勵(lì)因子。當(dāng)任務(wù)執(zhí)行失敗并返回任務(wù)時(shí)，Δτj=Cp°K ，Cp為懲罰因子。在公式（4）中，R是可用資源集合；τj(t)是時(shí)刻t從調(diào)度中心到資源j的路徑上的信息素；ηj是資源j的固有屬性，τu(t)是時(shí)間u從調(diào)度中心執(zhí)行到j(luò)的路徑上所包含的信息素；α和β分別代表信息素和固有屬性的權(quán)重。

（4）粒子群優(yōu)化算法（PSO）

粒子群優(yōu)化算法于1995年由Dr.Eberhart和Dr.Kennedy提出[8],是模擬魚類和鳥類在飼養(yǎng)期間的遷移和聚集。粒子群優(yōu)化算法是一種基于群體的多目標(biāo)優(yōu)化算法，它將搜索過程中基于目標(biāo)函數(shù)的粒子群中的粒子移動(dòng)到最優(yōu)解的位置。該算法將每個(gè)個(gè)體視為在D維搜索空間中以給定速度移動(dòng)的粒子。粒子的速度將根據(jù)個(gè)體和全局最優(yōu)值進(jìn)行動(dòng)態(tài)調(diào)整。我們假設(shè)i={1,2，...，N}是粒子的個(gè)數(shù)，d={1,2，...，D}是每個(gè)粒子的 D維搜索空間，所以是第i個(gè)粒子的位置，然后算法根據(jù)預(yù)先設(shè)定的目標(biāo)函數(shù)計(jì)算xi的當(dāng)前適應(yīng)度，從而說(shuō)明粒子位置的優(yōu)劣。是粒子i的速度，p是每個(gè)粒子從迭代開始找到的最優(yōu)解的位置。是即刻所有粒子的最優(yōu)解位置。所有粒子在每次的迭代過程中通過公式（5）（6）來(lái)不斷更新自己的速度和位置：

在這些公式中，k是第k代。在公式（5）中，w是慣性權(quán)重，c1和c2是加速系數(shù)，也稱為學(xué)習(xí)因子，用于維持種群多樣性。r1和r2是[0,1]之間的隨機(jī)數(shù)。此外，vij是三部分的線性組合。

3 結(jié)語(yǔ)

任務(wù)調(diào)度是一個(gè)非確定多項(xiàng)式（NP）問題，也是云環(huán)境下分布式平臺(tái)資源管理的核心功能。雖有已有的很多算法和技術(shù)不斷地成熟，但實(shí)際上還存在很多問題。例如，由于資源可以隨時(shí)加入和離開系統(tǒng)，用戶的需求也一直在變化，任務(wù)調(diào)度的失敗是不可避免的。而且，由于云環(huán)境中的資源是異構(gòu)的，因此可能會(huì)分配一些資源來(lái)執(zhí)行不能完成的任務(wù)或不好的任務(wù)，從而降低系統(tǒng)的性能。因此，我們需要從不同方面量化資源評(píng)估，制定統(tǒng)一的績(jī)效評(píng)估標(biāo)準(zhǔn)和模型。另外，我們需要對(duì)資源進(jìn)行適當(dāng)?shù)姆诸?，并根?jù)用戶的需求進(jìn)行資源分配，一些人工智能算法也必將被應(yīng)用于商業(yè)云系統(tǒng)中的任務(wù)調(diào)度。

[1]Li Jia.Research on DAG Task Scheduling Algorithm in Grid Environment[D].Central South University,2008.

[2]Yanhui Zhou,Kai Zhang.New Distributed Task Scheduling Algorithm[J].Computer Systems&Applications,2008,17（10）:40-42.

[3]Holland J H.Adaptation in Natural and Artificial Systems[J].University of Michigan Press Ann Arbor Mich,1975.

[4]Steinbrunn M,Moerkotte G,Kemper A.Heuristic and Ran2 Domized Optimization for the Join Ordering Problem[J].The VLDB Journal,1997,6（3）:8-17.

[5]Vecchi M P,Kirkpatrick S.Global Wiring by Simulated Annealing[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1983,2（4）:215-222.

[6]Dorigo M,Di C G,Gambardella L M.Ant Algorithms for Discrete Optimization[J].Artificial Life,1999,5（2）:137-172.

[7]Xue S,Li M,Xu X,et al.An ACO-LB Algorithm for Task Scheduling in the Cloud Environment[J].Journal of Software,2014,9（2）.

[8]Kennedy,James,Eberhart,et al.Particle Swarm Optimization[C],1995.