一種云計算環境下的改進任務調度算法*

張思豪，田建宇，劉銀良，劉經天，劉衛新

（北方自動控制技術研究所，太原 030006）

0 引言

云計算已經成為當前大規模和復雜計算的最突出的架構。它只需最少的管理工作和信息交互，便能夠完成對共享資源的按需網絡訪問，快速地提供和釋放訪問資源。隨著數以百萬計的用戶向云系統提交計算任務，任務調度機制在其中的作用越發顯著。

任務調度是指將一組任務分配給可用虛擬機的技術。任務調度機制的主要作用是在不影響服務質量的情況下提高資源利用率。任務調度算法分為兩種：確定性算法和元啟發式算法。

確定性調度算法包括先來先服務調度算法（first come first served，FCFS）、輪詢算法（round robin，RR）、短進程優先算法（shortest job first，SJF）和慢速資源負載均衡算法（load balance over slow resources，LBSR）等傳統調度算法。確定性算法是任務調度中常見的基本算法。

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

粒子群優化算法是元啟發算法中最常用的求解最優問題的算法之一。但是，使用該算法調度大量任務會降低系統性能。本文在粒子群算法的基礎上，通過改進提出一種新的調度算法，在不影響系統性能的前提下對大量任務進行調度。它以均衡、動態的方式將提交的任務劃分為多個批次。該算法主要考慮兩個參數：任務的數量和每批任務的總長度。……