基于负载均衡的任务调度算法

张 腊，刘淑芬，韩 璐

（吉林大学 计算机科学与技术学院，长春 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.）