云計算任務調度算法綜述

顧陽，李敏，李華

（廣西師范學院計算機與信息工程學院，南寧 530023）

0 引言

云環境是一個異構的分布式計算平臺，為用戶提供方便的可用資源，包括網絡、服務器、存儲、軟件等。由于成千上萬的用戶同時使用云環境，任務數量龐大，因此任務調度算法對云平臺的性能穩定有著重要影響，具有理論研究意義。任務調度一般可分為動態調度和靜態調度。動態調度算法會根據實時調度來調整結果，具有較強的適應性和靈活性，但存在諸多不確定因素。靜態調度算法則通常需要獲取實時任務信息，具有簡單高效、成本低廉等特性。本文總結了當前部分任務調度算法，包括傳統的任務調度算法、啟發式任務調度算法和商業應用中的任務調度算法，并在此基礎上對其進行評估總結。

1 問題定義

在云環境中，任務調度的任務通常可以被抽象為四元組（T,?,C,D）[1],在這個四元組中，T=（t1，t2，...，tn）是可執行任務的集合；?描述任務之間的部分順序，例如，ti? tj表明任務 ti應該在任務 tj之前執行；C={c1，c2，...，cn}是任務集 T 中所有任務的計算，ci是任務 ti的計算；D是n×n矩陣，Dij是從任務ti到任務tj的數據量。根據任務之間是否存在依賴關系或優先約束條件，我們可以將任務劃分為獨立的組件任務和工作流任務，獨立的組件任務可以用一個二元組（T，C）來描述，工作流任務因為依賴或優先約束可以用有向無環圖（DAG）來表示。

2 任務調度算法分析

2.1 傳統的任務調度算法

一般地，我們假設可以得到每個任務的執行時間和每個機器最早可用時間。機器最早的可用時間加上任務的執行時間等于機器上任務的最小完成時間。我們將從任務集T中的第一個任務開始到任務集T中的上一個任務結束的時間定義為完工周期。我們的目標是獲得最小完工時間。

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

OLB算法主要考慮到機器最早的可用時間，所以無法保證任務將被分配到最小的機器執行時間。而MET算法是以最短的執行時間將任務分配給機器，而不是最早的可用時間，結果可能出現負載不平衡。MCT算法選擇以最早的完成時間分配一個任務給機器，但是可能導致一些任務不能以最小的執行時間分配給機器，結果使得制造時間變長，MCT算法優于OLB算法和MET算法。Duplex算法和KPB算法都是基于MET和MCT的，它們的區別在于Duplex算法是根據系統負載均衡參數來選擇MET或MCT算法。而KPB算法設置一個名為K（100/n≦K≦100）的參數，并選擇n×（K/100）個機器按任務的執行時間分配任務。

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

不同于前面提到的算法，MinMin和MaxMin算法都考慮到了所有集中任務，而不僅僅是當前的任務。MinMin算法在任務長度變得不均勻時，性能會有所下降，因為它總是先分配小任務會導致大任務的長時間等待，并且這個完成時間會迅速增加，此外，系統的負載將會是不平衡的。而MaxMin算法在這種情況下會先分配大任務，同時執行大任務和小任務，從而減少執行時間。為了解決這一問題，Zhou[2]提出了一種基于MinMin和MaxMin算法的動態啟發式H-MM算法。該算法將提高分配的質量，但該算法通過每個處理單元分配的狀態值來判斷是否將任務分配給機器，否則，算法將比較任務的超時和機器上任務的超時，選擇更大的任務分配任務。另一個任務將回到未分配的任務集并等待下一個分配，所以可能會增加算法復雜度。

2.2 基于啟發式思想的任務調度算法

（1）遺傳算法（GA）

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

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

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

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

（3）蟻群優化算法（ACO）

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

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

（4）粒子群優化算法（PSO）

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

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

3 結語

任務調度是一個非確定多項式（NP）問題，也是云環境下分布式平臺資源管理的核心功能。雖有已有的很多算法和技術不斷地成熟，但實際上還存在很多問題。例如，由于資源可以隨時加入和離開系統，用戶的需求也一直在變化，任務調度的失敗是不可避免的。而且，由于云環境中的資源是異構的，因此可能會分配一些資源來執行不能完成的任務或不好的任務，從而降低系統的性能。因此，我們需要從不同方面量化資源評估，制定統一的績效評估標準和模型。另外，我們需要對資源進行適當的分類，并根據用戶的需求進行資源分配，一些人工智能算法也必將被應用于商業云系統中的任務調度。

[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.