基于負(fù)載均衡的任務(wù)調(diào)度算法

張 臘，劉淑芬，韓 璐

（吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012）

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，信息產(chǎn)業(yè)的需求發(fā)展愈加趨于高服務(wù)端低終端方向［1］.服務(wù)器集群已成為一個(gè)必然的發(fā)展方向，而任務(wù)調(diào)度及負(fù)載均衡則是服務(wù)器集群性能的核心問(wèn)題.

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

1 基于負(fù)載平衡任務(wù)調(diào)度模型的建立

本文通過(guò)數(shù)學(xué)模型的方法對(duì)任務(wù)調(diào)度問(wèn)題進(jìn)行形式化描述［4－5］.首先假設(shè)集群中每個(gè)服務(wù)器處理能力相同，且每個(gè)服務(wù)器都可獨(dú)立處理單元，即不需要其他服務(wù)器的輔助.此外，定義每個(gè)任務(wù)調(diào)度開(kāi)始到結(jié)束需要的時(shí)間為任務(wù)執(zhí)行時(shí)間與任務(wù)映射時(shí)間，且每個(gè)任務(wù)到不同機(jī)器的映射時(shí)間不同，基本定義如下.

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

2 Min－Linked算法

以任務(wù)執(zhí)行時(shí)間為標(biāo)準(zhǔn)，對(duì)任務(wù)隊(duì)列進(jìn)行排序（即選取最小的任務(wù)）；以任務(wù)執(zhí)行時(shí)間和到每臺(tái)機(jī)器的映射時(shí)間總和對(duì)服務(wù)器期望序列（即能最早完成該任務(wù)的服務(wù)器序列）進(jìn)行排序.MM算法中，任務(wù)選取執(zhí)行機(jī)器時(shí)直接選取能執(zhí)行較快的機(jī)器，則當(dāng)任務(wù)都集中在一臺(tái)服務(wù)器執(zhí)行時(shí)，會(huì)導(dǎo)致其他服務(wù)器空閑，而產(chǎn)生負(fù)載不均衡［8］.在ML算法中，根據(jù)任務(wù)連接數(shù)，在該任務(wù)服務(wù)器期望執(zhí)行序列中選取任務(wù)鏈接數(shù)＜n／m（n／m為平均每臺(tái)機(jī)器所需完成的任務(wù)數(shù)）的機(jī)器運(yùn)行.算法步驟如下：

1）初始化集合V和H，V為所有未調(diào)度的任務(wù)集合，對(duì)其進(jìn)行快速排序；

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

3）判斷V是否為空，若不為空，取出一個(gè)任務(wù)vi，繼續(xù)執(zhí)行；若為空，則轉(zhuǎn)7）；

4）根據(jù)當(dāng)前任務(wù)連接數(shù)排列集合H（從小到大）；

5）遍歷Qi，結(jié)合當(dāng)前任務(wù)連接數(shù)排列集合H，找到第一個(gè)滿(mǎn)足當(dāng)前連接數(shù)小于n／m（當(dāng)前任務(wù)總數(shù)／機(jī)群的服務(wù)器總數(shù)）的服務(wù)器，加入該服務(wù)器的等待隊(duì)列中；若不存在這樣的服務(wù)器，則加入Qi中第一個(gè)服務(wù)器的隊(duì)列中；

6）在V中刪除任務(wù)vi，返回2）；

7）執(zhí)行完畢.

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

綜上所述，ML算法時(shí)間復(fù)雜度為O（nm），而MM算法的時(shí)間復(fù)雜度為O（n2m），其中m為服務(wù)器總數(shù)，n為任務(wù)總數(shù).本文算法的時(shí)間復(fù)雜度為O（nm），時(shí)間復(fù)雜度較MM算法進(jìn)行了優(yōu)化［9］.

3 實(shí)驗(yàn)與結(jié)果分析

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

情形1）當(dāng)服務(wù)器數(shù)不變，任務(wù)數(shù)增加時(shí)，兩種算法比較結(jié)果如圖1和圖2所示.

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

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

由圖1可見(jiàn)，當(dāng)服務(wù)器數(shù)不變時(shí)，MM算法和ML算法完成任務(wù)的時(shí)間都隨任務(wù)數(shù)的增加而呈上升趨勢(shì)，但ML算法優(yōu)于MM算法.圖2為相對(duì)于圖1的集群負(fù)載均衡指數(shù)μ的變化，由圖2可見(jiàn)，ML算法可達(dá)到較好的負(fù)載均衡度且較穩(wěn)定，而MM算法則易出現(xiàn)負(fù)載不均且較不穩(wěn)定.

情形2）當(dāng)任務(wù)數(shù)不變，服務(wù)器數(shù)增加時(shí)，兩種算法比較結(jié)果如圖3和圖4所示.

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

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

由圖3可見(jiàn)，當(dāng)任務(wù)數(shù)不變時(shí)，ML算法和MM算法都隨著服務(wù)器數(shù)的增多，其任務(wù)完成時(shí)間整體呈下降趨勢(shì)，但ML算法始終優(yōu)于MM算法.圖4為相對(duì)于圖3的集群負(fù)載均衡度μ的變化，由圖4可見(jiàn)，ML算法可達(dá)到較好的負(fù)載均衡度且較穩(wěn)定，而MM算法則易出現(xiàn)負(fù)載不均且較不穩(wěn)定.

綜上所述，當(dāng)任務(wù)數(shù)及服務(wù)器數(shù)量增大，工作負(fù)載增大時(shí)，ML算法比MM算法的處理時(shí)間更快且保證了負(fù)載均衡性能.實(shí)驗(yàn)結(jié)果表明，基于負(fù)載的任務(wù)調(diào)度算法ML算法在MM算法的基礎(chǔ)上得到了優(yōu)化.

［1］鄭洪源，周良，吳家祺.WEB服務(wù)器集群系統(tǒng)中負(fù)載平衡的設(shè)計(jì)與實(shí)現(xiàn) ［J］.南京航空航天大學(xué)學(xué)報(bào)，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］戴娜，肖杰，邸瑞華.異構(gòu)計(jì)算環(huán)境下任務(wù)調(diào)度模型的啟發(fā)式算法研究 ［J］.微電子學(xué)與計(jì)算機(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ìn)后的網(wǎng)格調(diào)度算法 ［J］.微電子學(xué)與計(jì)算機(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］蔣文保，郝雙，戴一奇，等.高速網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)負(fù)載均衡策略與算法分析 ［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，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］鐘紹波.基于動(dòng)態(tài)負(fù)載均衡策略的網(wǎng)格任務(wù)調(diào)度優(yōu)化模型和算法 ［J］.計(jì)算機(jī)應(yīng)用，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］王德民，何立東，劉菲菲，等.基于消息的加權(quán)負(fù)載均衡算法 ［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，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ìn)行模型驗(yàn)證 ［J］.計(jì)算機(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］杜玉霞，劉方愛(ài)，郭磊.Min－Min調(diào)度算法的研究與改進(jìn) ［J］.計(jì)算機(jī)工程與應(yīng)用，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］胡峰，王國(guó)胤.二維表快速排序的復(fù)雜度分析 ［J］.計(jì)算機(jī)學(xué)報(bào)，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ìn) 行 多任務(wù)編程 ［J］.微 計(jì) 算機(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］孫偉峰，覃振權(quán)，李明楚，等.QIACO：一種多 QoS約束網(wǎng)格任務(wù)調(diào)度算法 ［J］.電子學(xué)報(bào)，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.）