云計算環(huán)境下獨立任務(wù)調(diào)度算法研究

徐星辰

（中共懷寧縣委黨校，安徽 安慶 246121）

云計算系統(tǒng)擁有數(shù)量眾多的處理器，龐大的使用群體，多樣化的任務(wù)類型，其數(shù)據(jù)中心時刻面臨海量數(shù)據(jù)和應(yīng)用任務(wù)。云計算環(huán)境下任務(wù)調(diào)度問題的研究具有較高的學(xué)術(shù)和實際應(yīng)用價值[1]。任務(wù)調(diào)度一般分為靜態(tài)調(diào)度和動態(tài)調(diào)度[2]。靜態(tài)調(diào)度能夠事先獲取更多任務(wù)信息（如任務(wù)之間的關(guān)聯(lián)性，任務(wù)在各服務(wù)器上的運算時間等），具有易實現(xiàn)、效率高、成本小等特征，因而，許多科學(xué)計算如圖像識別、網(wǎng)格任務(wù)、路徑規(guī)劃[3]等都采用靜態(tài)調(diào)度的方法對任務(wù)進行處理。動態(tài)調(diào)度在程序運行過程中，根據(jù)服務(wù)器和網(wǎng)絡(luò)運行負載情況來隨時調(diào)整調(diào)度算法，具有優(yōu)異的適應(yīng)能力和靈活度，但也存在難以解決的實際問題，相較于靜態(tài)調(diào)度，動態(tài)調(diào)度的實際應(yīng)用與理論研究成果不多，一般用于并行計算。云計算任務(wù)由若干子任務(wù)組成，按照前后執(zhí)行的任務(wù)之間是否存在關(guān)聯(lián)性，將任務(wù)調(diào)度分為獨立任務(wù)調(diào)度和關(guān)聯(lián)任務(wù)調(diào)度[4]。本文關(guān)注的是云計算中靜態(tài)獨立任務(wù)調(diào)度，重點分析典型的云環(huán)境下靜態(tài)獨立任務(wù)調(diào)度算法的發(fā)展趨勢，為相關(guān)領(lǐng)域的研究提供參考。

1 云計算靜態(tài)獨立任務(wù)調(diào)度

獨立任務(wù)調(diào)度指將沒有關(guān)聯(lián)的任務(wù)集合以一種合理的策略分配至不同的服務(wù)器上，實現(xiàn)任務(wù)的規(guī)?；幚恚{(diào)度過程中，前后兩個任務(wù)的執(zhí)行互相獨立、并列執(zhí)行，其模型如圖1所示。

圖1 獨立任務(wù)調(diào)度模型

關(guān)于靜態(tài)獨立任務(wù)調(diào)度算法的研究主要分為兩種。（1）傳統(tǒng)獨立任務(wù)調(diào)度算法。該算法大多以非智能化算法為主，側(cè)重于某個指標(biāo)的尋優(yōu)，具有簡單容易實現(xiàn)的特點，但是算法只注重某個指標(biāo)的最優(yōu)，為了實現(xiàn)它通常會放棄其他指標(biāo)，導(dǎo)致調(diào)度的結(jié)果是：雖然該指標(biāo)實現(xiàn)了最優(yōu)，但是其他指標(biāo)的效果往往不是很令人滿意，甚至很差。典型的算法包括Min-Min、Max-Min、Sufferage和RR算法等；（2）啟發(fā)式獨立任務(wù)調(diào)度算法。該算法大多采用群體智能的方式進行調(diào)度，其核心思想是多目標(biāo)優(yōu)化問題，在可接受的計算代價內(nèi)，給出滿足各個實例的可行解，而對于某個實例來說這個解未必是最優(yōu)解。啟發(fā)式獨立任務(wù)調(diào)度算法的調(diào)度性能優(yōu)良，在獨立任務(wù)調(diào)度中應(yīng)用較多，但也存在算法因需預(yù)設(shè)置參數(shù)和多次迭代以獲得最后的優(yōu)化結(jié)果，導(dǎo)致實現(xiàn)過程復(fù)雜。由此可見，啟發(fā)式獨立任務(wù)調(diào)度算法下一步的研究方向主要是進一步降低算法的復(fù)雜度。目前應(yīng)用較多的啟發(fā)式獨立任務(wù)調(diào)度算法主要有GA算法、PSO優(yōu)化算法、Ant算法等。

2 常見的靜態(tài)獨立任務(wù)調(diào)度算法

2.1 Min-Min算法

Min-Min算法[4]是一種典型的獨立任務(wù)調(diào)度算法，每次調(diào)度開始前，需計算出任務(wù)調(diào)度隊列中全部任務(wù)在各資源節(jié)點上的最早完成時間，然后將其中最短的任務(wù)分配到相應(yīng)的服務(wù)器上執(zhí)行，同時從隊列中將其刪除，接著更新任務(wù)隊列的期望時間，反復(fù)執(zhí)行上述過程，直至任務(wù)隊列為空時退出。

算法優(yōu)點：實現(xiàn)簡單，時間和計算復(fù)雜度低。

算法缺點：性能更優(yōu)的處理器負載過重和大任務(wù)調(diào)度時間太長，導(dǎo)致系統(tǒng)負載不均衡。

Min-Min算法最主要的問題是負載不均衡，文獻[5-8]針對這一問題進行了優(yōu)化，如表1所示。

表1 Min-Min算法優(yōu)化

2.2 Max-Min算法

Max-Min算法和Min-Min算法的基本思想類似，不一樣的地方是，Max-Min算法在調(diào)度前須計算出任務(wù)調(diào)度隊列中全部任務(wù)在各資源節(jié)點上的最早完成時間，并將最早完成時間中最長的任務(wù)優(yōu)先分配給相應(yīng)的處理器上執(zhí)行[9]。

算法優(yōu)點：簡單實用，時間復(fù)雜度低。

算法缺點：可能造成小任務(wù)調(diào)度延后，引發(fā)處理器負載不均衡現(xiàn)象的發(fā)生。

Max-Min算法的最主要問題就是貪心策略容易造成負載不均衡，文獻[9-11]主要針對這一問題進行了優(yōu)化，如表2所示。

表2 Max-Min算法優(yōu)化

2.3 Sufferage算法

Sufferage算法首先計算任務(wù)集合中的所有子任務(wù)在各處理器上的執(zhí)行時間，然后將任務(wù)最短完成時間與次短完成時間差的絕對值定義為Sufferage值。在進行任務(wù)調(diào)度時，先將任務(wù)分配至完成時間最短的處理器，假如該處理器已經(jīng)分配任務(wù)，則需計算兩個任務(wù)的Sufferage值，數(shù)值較大的優(yōu)先調(diào)度；否則，該處理器直接執(zhí)行已分配的任務(wù)，反復(fù)執(zhí)行上述流程，直至任務(wù)隊列為空時退出[12]。當(dāng)任務(wù)集合的子任務(wù)之間Sufferage值均較小時，適合使用Sufferage算法進行調(diào)度。

算法優(yōu)點：簡單可行；衡量子任務(wù)的時間損失度，減少任務(wù)調(diào)度跨度。

算法缺點：負載的平衡性能不高，缺乏對全局任務(wù)調(diào)度的考慮。

目前的主要研究方向是針對Sufferage算法的負載均衡性和全局調(diào)度進行優(yōu)化，如表3所示。

表3 Sufferage算法優(yōu)化

2.4 遺傳算法

遺傳算法是一種模擬自然界生物種群“優(yōu)勝劣汰”自然選擇過程的算法，隨機初始化一個種群，種群中所有個體都由基因編碼的染色體構(gòu)成，每次迭代更新，都會經(jīng)過一系列雜交、突變、繁殖等遺傳操作過程，淘汰基因劣質(zhì)的染色體，選擇適應(yīng)能力強的染色體形成新種群，重復(fù)上述迭代過程直至產(chǎn)生基因最優(yōu)的個體，該個體即代表任務(wù)調(diào)度問題在當(dāng)前環(huán)境下的最優(yōu)解[17]。

算法優(yōu)點：從群體出發(fā)，具備同時搜索能力，解決并行問題能力強；易與其他算法融合。

算法缺點：算法實現(xiàn)過程比較復(fù)雜，搜索時間耗費過長且效率不高；隨著計算規(guī)模的不斷擴大，易出現(xiàn)提前收斂。

應(yīng)用于云計算任務(wù)調(diào)度時，遺傳算法有很強的全局搜索能力，但是算法的搜索效率和解的多樣性方面還需要提高，為解決上述問題，學(xué)者們做了一系列優(yōu)化研究，如表4所示。

表4 遺傳算法優(yōu)化

2.5 粒子群優(yōu)化算法

受鳥群和魚群尋找食物的行為規(guī)律啟發(fā)，Eberhart和Kennedy提出了粒子群（PSO）優(yōu)化算法[23]。PSO算法的基本思想是通過集體協(xié)作和互通信息來尋找最優(yōu)解。首先初始化粒子群體，群體中的每個粒子都包含兩個屬性，即位置和速度；然后計算每個粒子的適應(yīng)度，將每個粒子的當(dāng)前適應(yīng)度與其歷史最佳位置對應(yīng)的適應(yīng)度作比較，如果當(dāng)前的適應(yīng)度更高，則用當(dāng)前位置替代歷史最佳位置；接著將每個粒子當(dāng)前適應(yīng)度與整個粒子群的全局最佳位置對應(yīng)的適應(yīng)度作比較，如果當(dāng)前適應(yīng)度更高，則用當(dāng)前位置替代全局最佳位置。反復(fù)迭代直到搜尋到與目標(biāo)最近的解。

算法優(yōu)點：具有參數(shù)設(shè)置少、搜索和收斂速度快等特點。

算法缺點：PSO算法初始種群隨機性強，其好壞直接影響算法的搜索空間，如果初始種群選擇不當(dāng)會降低算法的尋優(yōu)能力。

與蟻群算法類似，在應(yīng)用于云計算任務(wù)調(diào)度時，粒子群優(yōu)化算法搜索速度快，但局部最優(yōu)收斂速度快很容易導(dǎo)致陷入局部最優(yōu)解，目前主要針對算法多樣性進行優(yōu)化，如表5所示。

表5 粒子群算法優(yōu)化

2.6 蟻群算法

受螞蟻覓食行為的啟發(fā)，Marco提出了蟻群算法（ACO）[29]。該算法的核心思想是螞蟻在覓食路徑上通過分泌的信息素來傳遞信息，信息素濃度越高，被后來的螞蟻選擇的概率越大，后來的每只螞蟻都會在該路徑上留下外激素，路徑長度與外激素的濃度呈負相關(guān)關(guān)系，隨著時間推移，路徑越短其累計的信息素濃度就越高，螞蟻更傾向選擇這條路徑。最后，所有的螞蟻都會選擇集中于最佳的路徑上，此時對應(yīng)的便是最優(yōu)解。

算法優(yōu)點：具有優(yōu)異的擴展性、豐富的多樣性，其正反饋性和并發(fā)性也比較突出，適用于多目標(biāo)下最優(yōu)解問題的搜尋。

算法缺點：因信息匱乏，算法前期需花費時間積累信息素，速度慢、搜索時間較長。

應(yīng)用于云計算任務(wù)調(diào)度時，信息素積累起來之后，蟻群算法具有極高的搜索效率和解的精度，但是前期信息素積累需花費較長時間，易造成收斂速度過快和陷入局部最優(yōu)解。目前的主要研究方向是針對算法多樣性和前期搜索效率進行優(yōu)化，如表6所示。

表6 蟻群算法優(yōu)化

3 結(jié)束語

本文闡述了云計算環(huán)境下靜態(tài)獨立任務(wù)調(diào)度模型，對靜態(tài)獨立任務(wù)調(diào)度算法作了分類，選取了6個比較常見的靜態(tài)獨立任務(wù)調(diào)度算法：Min-min算法、Max-min算法、Sufferage算法、ACO算法、GA算法、PSO算法，分別對它們進行詳細分析，從優(yōu)化內(nèi)容、對比算法、優(yōu)化結(jié)果等方面歸納總結(jié)了以上算法的改進方式及效果，為相關(guān)領(lǐng)域的研究提供參考。目前絕大多數(shù)靜態(tài)獨立任務(wù)調(diào)度算法都是在理想的網(wǎng)絡(luò)環(huán)境下進行的，但現(xiàn)實云服務(wù)環(huán)境下的網(wǎng)絡(luò)帶寬每時每刻都在變化，因此，對于任何一種調(diào)度算法，如果不考慮網(wǎng)絡(luò)帶寬對調(diào)度結(jié)果產(chǎn)生的影響是不合理的，設(shè)計一種考慮實際網(wǎng)絡(luò)環(huán)境的任務(wù)調(diào)度算法成為目前云計算需要解決的一個關(guān)鍵性問題。