改进的Min-Min网格任务调度算法

赵英，李栋

（北京化工大学 信息科学与技术学院，北京 100029）

网格通过网络连接地理上分布的各种资源，形成一个对用户相对透明的环境。在网格技术[1]中，任务调度是一个研究热点。任务调度的目的是对所有任务进行合理调度，使其完成时间尽可能的短，并且尽可能地提高系统资源的利用率。

经典的任务调度算法有遗传算法[2]、模拟退火算法、Suffrage[3]算法、Min-Min[4]算法、Max-Min 算法等，这些算法被广泛应用于网格任务调度。其中Min-Min算法是一种简单快速的算法，但它忽略了网格任务对QoS[5]的要求。本文对网格任务的优先级进行划分和量化，结合网格任务的等待时间，提出了一种基于权值的改进Min-Min网格任务调度算法，并通过仿真实验，验证了其有效性。

1 网格任务调度

与传统的任务调度相比，网格任务调度必须针对网格资源的特点进行[6]。网格资源具有以下3个特点：

1）异构性 每个网格资源都不尽相同，主要体现在计算资源、存储资源和网络资源等方面的差异。同样的一个任务在不同资源上执行的时间不同，通信方式有可能不同，网络延迟也会不同。

2）动态性 网格资源工作时性能会不断变化，有些时候还会出现故障，比如断电等，调度必须考虑这些突发因素来适应网格资源的动态性。

3）独立自主性 每个网格资源都具有独立自主性，不受网格的完全控制，正是由于这个特性，网格资源不能专用于某个应用。

网格任务调度问题通常被认为是一个NP问题，其完成时间随着任务规模的增长而呈现指数级的增长。在实际的任务调度过程中，除了要考虑完成时间这个因素外，还有一些其它重要因素也是需要考虑的：

1）经济原则 网格资源不是无偿使用的，用户在使用资源的同时应对资源的提供者缴纳一定的费用作为补偿。一旦涉及到利益，所有网格用户的目标是在满足一定条件下使自己的收益最大化或者成本最小化。在网格任务调度的经济调度模型中，需要综合考虑任务成本和执行时间[7]，要么优先任务成本，要么优先执行时间，两者不可兼得。

2）QoS（Quality of Service）要求 在网格计算中，向用户提供有质量保障的服务是很重要的。不同的网格用户会要求不同的QoS，QoS一般是指网格任务的价格、安全性、稳定性、成功率、优先级等[8]。没有QoS的任务调度的效率是很低的。

3）负载均衡 在网格任务调度中，要尽可能的使得每个网格资源上都有任务在运行，也就是充分利用网格资源。对网格资源的主机负载进行预测，然后根据预测的结果对网格任务进行调度并执行[9]，在实现负载均衡的同时也会缩短总任务的完成时间，效率也会得到提高。

2 Min-Min调度算法

当前大部分调度算法研究都集中于独立型任务调度，这类调度算法假设任务之间不存在依赖关系，任务的预期执行时间可知。在众多静态独立启发式算法中，Min-Min算法是一个相对简单、快速、有效的算法，该算法的主要思想如下：

假设网格环境是由n个需要调度的任务T={T1，T2，…，Tn}和m个资源R={R1，R2，…Rm}组成。当集合T不为空时，循环执行如下操作直到集合T为空：1）对集合T中的每一个任务分别计算出它在所有网格资源上的最小完成时间，可以得到最小完成时间数组M；2）从数组M中选出完成时间最小的任务进行调度；3）从集合T中删除被调度的任务。如果集合T为空，则退出调度过程。

表1中列出了5个任务，3个网格资源以及相应的ETC（Expected Time to Compute）矩阵的值，其中∞表示该任务在该资源上无法运行，也就是说任务T5只能在资源R2上执行，可以认为任务T5具有很高的服务质量要求。由Min-Min调度算法可以得出调度的结果以及调度的顺序：任务T3调度到资源R1上，任务T2调度到资源R1上，任务T4调度到资源R1上，任务T5调度到资源R2上，任务T1调度到资源R1上。从调度的结果中可以看出大部分的任务都在资源R1上运行，而资源R3一直空闲。从调度的顺序中可以发现任务的调度顺序是按任务预期执行时间从小到大的顺序排列的。

表1 任务在资源上的预期执行时间Tab.1 Expected execution time of task

尽管Min-Min算法可以有效地进行调度，但是从调度的结果中能看出算法缺点：1）忽略了网格任务的QoS要求；2）每次调度总是先调度预期执行时间最短的任务，并且总是将任务调度到完成本任务最快的资源上，执行时间相对较长的任务得不到立即执行，这样很容易导致系统的负载不均衡。

3 基于权值改进的调度算法

针对Min-Min算法在调度网格任务时的缺点，文中提出了一种带权值的Min-Min改进算法。该算法中的权值由优先级和等待时间两部分组成。系统采用权值的高低来进行任务的调度。

3.1 权值计算

设有n个任务，m个网格资源，第i个任务的优先级为p（i），等待时间为 t（i），权值为 w（i）。根据 ETC 矩阵（ETC[i，j]表示第i个任务在第j个资源上执行完成所需要的时间）可以得出第i个任务的权值为：

其中：α是一个平衡系数（0<α<1）。

3.2 任务调度

在每次决定调度的时候都需要重新计算当前任务集合中所有任务的权值，选择权值最高的任务调度到完成该任务最快的资源上。

假设在上一个任务调度时刻，wt（j）为资源j的剩余任务所需要的时间。经过Δt的时间，进入下一个调度时刻，wt（j）也需要相应的更新：

则任务i在所有资源上的预测完成时间为：

从f（j）中找出最小值所属的资源，此时的资源就是任务i所要调度的资源。

4 算法仿真与结果分析

文中采用GridSim[10]来模拟一个网格环境，在相同的环境条件下，分别用Min-Min调度算法与改进后的算法进行比较。

图1对应改进后的算法的低、中、高3种不同优先级的任务等待时间的模拟结果。从图中可以看出，低优先级的任务等待时间最长，高优先级的任务等待时间最短，这说明改进后的算法满足了任务的优先级要求。

图1 不同优先级的等待时间Fig.1 Waiting time of different priorities

图2对应在同优先级情况下的短任务等待时间的模拟结果。图3对应在同优先级情况下的中任务等待时间的模拟结果。图4对应在同优先级情况下的长任务等待时间的模拟结果。由图可知，改进后的算法与Min-Min算法相比，短任务的等待时间变长，而中任务和长任务的等待时间变短。

图2 短任务等待时间Fig.2 Waiting time of short task

图3 中任务等待时间Fig.3 Waiting time of middle task

图4 长任务等待时间Fig.4 Waiting time of long task

综合分析以上3个图，改进后的算法随着等待时间的增加，中任务和长任务的权值提高较快，从而占用了短任务的服务时间，增加了短任务的等待时间。不过，从图中可以看出，虽然短任务的等待时间有一定的增加，但是中任务和长任务的等待时间的减少程度就比较明显。

5 结 论

文中在对Min-Min算法进行研究之后，发现Min-Min算法在调度网格任务时没有QoS要求，并且大任务等待时间过长。为了解决这两个问题，提出了一种基于权值改进的Min-Min调度算法，该算法把任务的优先级和等待时间作为一个重要的因素。仿真实验证明，改进后的算法可以在网格环境下实现较为理想的任务调度，是一种有效的任务调度算法。

[1]史文翀，曾文华.网格技术的发展与其应用研究[J].计算机与数字工程，2006（7）:59-62.SHI Wen-chong，ZENG Wen-hua.Reserch of the development of grid technology and its application[J].Comuputer&Digital Engineering，2006（7）:59-62.

[2]李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）:184-186.LI Jian-feng，PENG Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing enivironment[J].Journal of Computer Applications，2011，31（1）:184-186.

[3]Casanova H，Legrand A，Zagorodnov D，et al.Heuristics for scheduling parameter sweep applications in grid environments[C]//Cancun，Mexico:Proceeding of the 9th Heterogeneous Computing Workshop，2000:349-363.

[4]Etminani K，Naghibzadeh M.A min-min max-min selective algorithm for grid task scheduling [C]//3rd IEEE/IFIP International Conference in Central Asia，2007:1-7.

[5]吴高峰，蒋玉明，杨林.基于QoS改进的Min-Min网格调度算法[J].微计算机信息，2009（27）:8-11.WU Gao-feng，JIANG Yu-ming，YANG Lin.Scheduling algorithm of modified Min-Min based on QoS in grid[J].Microcomputer Information，2009（27）:8-11.

[6]张海宾，唐琳莎，刘立祥.网格调度综述[J].计算机工程与设计，2009，30（9）:2151-2153.ZHANG Hai-bin，TANG Lin-sha，LIU Li-xiang.Survey of grid scheduling [J].Computer Engineering and Design，2009，30（9）:2151-2153.

[7]林晓鹏，郭东辉.基于经济机制的网格资源调度分析[J].信息与电子工程，2010，8（4）:495-499.LIN Xiao-peng，GUO Dong-hui.Analysis of grid resource scheduling based on economy[J].Information and Electronic Engineering，2010，8（4）:495-499.

[8]刘宴兵，陈杰，熊仕勇.基于QoS相似度的网格任务调度算法[J].重庆邮电大学学报，2009，21（3）:416-420.LIU Yan-bing，CHEN Jie，XIONG Shi-yong.Grid task scheduling algorithm based on QoS similarity[J].Joural of Chongqing University of Posts and Telecommunications（Natural Science Editon），2009，21（3）:416-420.

[9]程宏兵.基于资源预测的网格任务调度模型[J].计算机应用，2010，30（9）:2530-2534.CHENG Hong-bing.Task scheduling model based on resource prediction for grid computing[J].Joural of Computer Applications，2010，30（9）:2530-2534.