基于負載均衡的任務調度算法

張 臘，劉淑芬，韓 璐

（吉林大學 計算機科學與技術學院，長春 130012）

隨著互聯網技術的飛速發展，信息產業的需求發展愈加趨于高服務端低終端方向［1］.服務器集群已成為一個必然的發展方向，而任務調度及負載均衡則是服務器集群性能的核心問題.

Min－Min算法（簡稱MM算法）是較經典的任務調度算法之一［2］，其主要思想為首先映射小的任務，且映射到執行快的機器上.MM算法采用貪心策略，每次選取最有利于自己的調度方式，最終獲得執行效率較高的任務處理方案［3］.但傳統的MM任務調度算法雖然是一種實現簡單、執行較快的算法，但其并未考慮服務器的負載均衡問題，本文在MM算法的基礎上，通過引入任務連接數，增設了服務器的最佳期望序列，提出Min－Linked算法（簡稱ML算法）.ML算法通過當前任務連接數考慮集群的負載平衡，從而進一步提高任務執行效率.

1 基于負載平衡任務調度模型的建立

本文通過數學模型的方法對任務調度問題進行形式化描述［4－5］.首先假設集群中每個服務器處理能力相同，且每個服務器都可獨立處理單元，即不需要其他服務器的輔助.此外，定義每個任務調度開始到結束需要的時間為任務執行時間與任務映射時間，且每個任務到不同機器的映射時間不同，基本定義如下.

方差可判斷數據的離散程度，因此，本文用任務連接數的方差表示負載均衡指數［7］.結果表明，μ值越小，任務連接數分布越均勻，負載均衡性能越高；μ值越大，任務連接數分布越分散，負載均衡性能越低.

2 Min－Linked算法

以任務執行時間為標準，對任務隊列進行排序（即選取最小的任務）；以任務執行時間和到每臺機器的映射時間總和對服務器期望序列（即能最早完成該任務的服務器序列）進行排序.MM算法中，任務選取執行機器時直接選取能執行較快的機器，則當任務都集中在一臺服務器執行時，會導致其他服務器空閑，而產生負載不均衡［8］.在ML算法中，根據任務連接數，在該任務服務器期望執行序列中選取任務鏈接數＜n／m（n／m為平均每臺機器所需完成的任務數）的機器運行.算法步驟如下：

1）初始化集合V和H，V為所有未調度的任務集合，對其進行快速排序；

2）計算Wij＝ci＋rij，初始化Q（排序）；

3）判斷V是否為空，若不為空，取出一個任務vi，繼續執行；若為空，則轉7）；

4）根據當前任務連接數排列集合H（從小到大）；

5）遍歷Qi，結合當前任務連接數排列集合H，找到第一個滿足當前連接數小于n／m（當前任務總數／機群的服務器總數）的服務器，加入該服務器的等待隊列中；若不存在這樣的服務器，則加入Qi中第一個服務器的隊列中；

6）在V中刪除任務vi，返回2）；

7）執行完畢.

ML算法的步驟1）中對V進行初始化，時間復雜度為O（nlog2n），在步驟2）中，計算Wij＝ci＋rij，初始化Q，共有n個任務，m臺機器，故需要計算n×m次對Q進行快速排序，時間復雜度為O（nmlog2m）；步驟3）～6）的循環中，最差情況下，每次在Qi中，遍歷到最后一個才找到合適的機器進行任務處理，則處理完所有任務時間復雜度為O（nm）；最好情況下，每次在Qi中，第一個即滿足要求，任務得到處理，此時處理完所有任務的時間復雜度為O（n）.

綜上所述，ML算法時間復雜度為O（nm），而MM算法的時間復雜度為O（n2m），其中m為服務器總數，n為任務總數.本文算法的時間復雜度為O（nm），時間復雜度較MM算法進行了優化［9］.

3 實驗與結果分析

采用C語言編程模擬兩種算法，計算其任務完成時間及負載指數［10］.設定時間單位為1，采用隨機產生的實驗數據，在ML算法和MM算法中分別進行實驗，記錄任務的完成時間及負載指數μ.為了比較MM算法和ML算法在不同情形下的性能，本文采用數學分析中的控制變量法思想分別進行實驗［11］.

情形1）當服務器數不變，任務數增加時，兩種算法比較結果如圖1和圖2所示.

圖1 情形1）中ML算法與MM算法完成時間的比較Fig.1 Comparison of completion time by ML and MM algorithms in case 1）

圖2 情形1）中ML算法與MM算法均衡指數μ的比較Fig.2 Comparison of load balancing index by ML and MM algorithms in case 1）

由圖1可見，當服務器數不變時，MM算法和ML算法完成任務的時間都隨任務數的增加而呈上升趨勢，但ML算法優于MM算法.圖2為相對于圖1的集群負載均衡指數μ的變化，由圖2可見，ML算法可達到較好的負載均衡度且較穩定，而MM算法則易出現負載不均且較不穩定.

情形2）當任務數不變，服務器數增加時，兩種算法比較結果如圖3和圖4所示.

圖3 情形2）中ML算法與MM算法完成時間比較Fig.3 Comparison of completion time by ML and MM algorithms in case 2）

圖4 情形2）中ML算法與MM算法均衡指數μ的比較Fig.4 Comparison of load balancing index by ML and MM algorithms in case 2）

由圖3可見，當任務數不變時，ML算法和MM算法都隨著服務器數的增多，其任務完成時間整體呈下降趨勢，但ML算法始終優于MM算法.圖4為相對于圖3的集群負載均衡度μ的變化，由圖4可見，ML算法可達到較好的負載均衡度且較穩定，而MM算法則易出現負載不均且較不穩定.

綜上所述，當任務數及服務器數量增大，工作負載增大時，ML算法比MM算法的處理時間更快且保證了負載均衡性能.實驗結果表明，基于負載的任務調度算法ML算法在MM算法的基礎上得到了優化.

［1］鄭洪源，周良，吳家祺.WEB服務器集群系統中負載平衡的設計與實現 ［J］.南京航空航天大學學報，2006，38（3）：347－351.（ZHENG Hongyuan，ZHOU Liang，WU Jiaqi.Design and Implementation of Load Balancing in Web Server Cluster System ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2006，38（3）：347－351.）

［2］戴娜，肖杰，邸瑞華.異構計算環境下任務調度模型的啟發式算法研究 ［J］.微電子學與計算機，2006，23（增刊1）：119－121.（DAI Na，XIAO Jie，DI Ruihua.Task Scheduling Algorithms in a Classical Model of Heterogeneous Computing Environment［J］.Microelectronics ＆ Computer，2006，23（Suppl 1）：119－121.）

［3］羅宇平.基于 Min－Min改進后的網格調度算法 ［J］.微電子學與計算機，2009，26（3）：86－88.（LUO Yuping.Scheduling Algorithm Based on Modified Min－Min in Grid ［J］. Microelectronics ＆ Computer，2009，26（3）：86－88.）

［4］蔣文保，郝雙，戴一奇，等.高速網絡入侵檢測系統負載均衡策略與算法分析 ［J］.清華大學學報：自然科學版，2006，46（1）：106－110.（JIANG Wenbao，HAO Shuang，DAI Yiqi，et al.Load Balancing Algorithm for High－Speed Network Intrusion Detection Systems［J］.Journal of Tsinghua University：Science and Technology，2006，46（1）：106－110.）

［5］鐘紹波.基于動態負載均衡策略的網格任務調度優化模型和算法 ［J］.計算機應用，2008，28（11）：2867－2870.（ZHONG Shaobo.Optimal Resource Model and Task Scheduling Algorithm Based on Dynamic Load Balancing Strategy in Grid［J］.Computer Applications，2008，28（11）：2867－2870.）

［6］王德民，何立東，劉菲菲，等.基于消息的加權負載均衡算法 ［J］.吉林大學學報：工學版，2012，42（1）：140－144.（WANG Demin，HE Lidong，LIU Feifei，et al.Message－Oriented Load Balancing Algorithm ［J］.Journal of Jilin University：Engineering and Technology Edition，2012，42（1）：140－144.）

［7］呂棟雷，曹志耀，鄧寶，等.利用方差分析法進行模型驗證 ［J］.計算機仿真，2006，23（8）：46－48.（LüDonglei，CAO Zhiyao，DENG Bao，et al.Application of Variance Analysis in Model Validation ［J］.Computer Simulation，2006，23（8）：46－48.）

［8］杜玉霞，劉方愛，郭磊.Min－Min調度算法的研究與改進 ［J］.計算機工程與應用，2010，46（24）：107－109.（DU Yuxia，LIU Fangai，GUO Lei.Research and Improvement of Min－Min Scheduling Algorithm［J］.Computer Engineering and Applications，2010，46（24）：107－109.）

［9］胡峰，王國胤.二維表快速排序的復雜度分析 ［J］.計算機學報，2007，30（6）：963－968.（HU Feng，WANG Guoyin.Analysis of the Complexity of Quick Sort for Two Dimension Table［J］.Chinese Journal of Computers，2007，30（6）：963－968.

［10］李中健.32 位 Windows下使用 VC＋ ＋ 進 行 多任務編程 ［J］.微 計 算機 信 息，2000，16（2）：38－40.（LI Zhongjian.Multi－task Programming under 32Bit Windows Using Visual C＋＋ ［J］.Control ＆ Automation，2000，16（2）：38－40.）

［11］孫偉峰，覃振權，李明楚，等.QIACO：一種多 QoS約束網格任務調度算法 ［J］.電子學報，2011，39（5）：1115－1120.（SUN Weifeng，QIN Zhenquan，LI Mingchu，et al.QIACO：An Algorithm for Grid Task Scheduling of Multiple QoS Dimensions［J］.Acta Electronica Sinica，2011，39（5）：1115－1120.）