网格(Grid)技术是当今计算机领域的研究热点之一。在网格技术飞速发展的同时，网格计算中的任务调度" title="任务调度">任务调度问题也变得越来越重要。网格环境" title="网格环境">网格环境中各处理器的运行速度、主机的负载、网络通信的时间等都是动态变化的，资源的管理和调度十分复杂，多机环境下的任务调度问题便成为一个众所周知的NP问题。目前，围绕着网格计算中的任务调度算法，国内外已经做了大量的研究工作，先后提出了各种静态和动态的调度算法。本文对传统的、经典的Min-Min调度算法进行深入的分析和研究，指出该算法存在的缺陷，并在此基础上提出一个基于“分段”思想的改进算法，并且在网格模拟器环境下进行仿真实验。仿真结果验证了改进后算法的合理性和有效性。
1 Min-Min算法概述
　　在网格环境下，高效的调度策略或算法可以充分利用网格系统的处理能力，从而提高应用程序的性能。任务调度问题的实质就是在一个由m个需要调度的任务和n个可用的任务执行单元(主机或集群)构成的网格环境下，把m个任务T={t₁，t₂，……t_m}以合理的方式调度到n个主机H={h₁，h₂，……h_n}上去，目的是得到尽可能小的总执行时间(Makespan)。m个任务在n个不同机器上的预测执行时间ETC(Expected Time to Compute)是一个m×n的矩阵。ETC(i，j)表示第i个任务在第j台机器上的预测执行时间，矩阵中的每一行代表某一任务在n台机器上的不同执行时间，每一列代表在同一台机器上m个任务的不同执行时间。
　　以完成时间为优化目标的任务-资源映射是一个NP完全问题，所以需要辅助的启发式算法" title="启发式算法">启发式算法。对于传统的Min-Min、Max-Min、A*和GA等静态启发式算法，Tracy D.Braun等人已经做了详细的研究^[2]。结果表明，GA算法在不同ETC矩阵下的性能是最好的，Min-Min和A*次之。并且Tracy D.Braun的研究表明：对于每个ETC矩阵，GA算法的平均执行时间是60秒，而A*算法是20分钟。由于算法中各项参数是通过NWS等服务得到的一些提前预测值，因此在参数随时间剧烈变化的网格环境下，GA或A*的计算时间会显得很长，因而得到的调度策略也很不合理。
　　Min-Min算法仍然是目前网格调度算法的研究基础之一。该算法的主要思想是：当需要调度的任务集合非空时，反复执行如下操作直至集合为空：
　　(1)对集合中每一个等待分配的任务t_i，分别计算出把该任务分配到n台机器上的最小完成时间，记为Min-Time(i)，可以得到一个含有m个元素的一维数组MinTime；
　　(2)设第k个元素是MinTime数组中最小的，其对应的主机为b，把任务k分配到机器b上；
　　(3)在任务集合中把任务k删除。
　　由于Min-Min算法总是优先调度短任务，当机器空闲时一些执行时间较长的任务才能得以执行，这样便导致了主机负载不均衡,利用率降低。对此，本文提出一个改进的算法来优先调度执行时间长的任务，即分段Min-Min算法Dmm(Divided-Min-Min)。
2 基于分段思想改进的Min-Min算法
　　Dmm算法首先根据任务的ETC进行排序，即根据平均ETC或最小ETC或最大ETC将任务归为一个从大到小的有序序列；然后将这个任务序列分成相同大小的段，先调度长任务段，后调度短任务段。对于每个任务段，仍然使用Min-Min算法进行任务调度。Dmm算法描述如下：
　　(1)计算每一个任务的排序值key_i。在网格异构" title="异构">异构环境下，同一任务在不同机器上的执行时间是不同的，这被称为网格的任务异构。考虑到任务异构性，在确定排序值时测试了三种子策略——平均、最小、最大预期执行时间。
　　子策略1：Dmm-avg 计算ETC矩阵中每一行的平均值：

　　(2)根据排序值，降序排列任务集合，形成一个有序序列。
　　(3)将任务序列平均分为N段。
　　(4)运用Min-Min算法依次调度各任务段。
　　与Min-Min算法不同的是，Dmm算法在调度执行之前先进行任务排序，这意味着执行时间长的任务较早被调度。然后在每个任务段内局部运用Min-Min算法。该算法的关键就是如何确定任务的排序值，确保长任务能够优先调度。
　　Dmm算法的第三步是将任务序列分为N段，重点在于如何选择最优的N值。一方面，N值越大负载越趋于均衡；另一方面，N值过大会使Min-Min算法降低效率。图1中的曲线表明，在选取不同的N值时，采用Dmm-avg子策略的Dmm算法相对Min-Min算法的改进度。如图1所示，当c=m/n的值较小时，也就是平均分配到每台机器上的任务数量较少时，Dmm算法就表现出良好的性能。无论c取值多大，图1中的曲线总是在N值为4或5时达到最高的算法改进度。因此，将N的值定为4，在任务序列划分时通常都分为4段。

3 仿真实验及结果分析
　　这里使用HyperSim模拟器对改进的算法进行仿真研究。HyperSim实际上是一个基于C++开发的通用离散事件模拟库，提供了一系列库函数，用以建立特定计算环境或专业应用领域的模拟器。HyperSim提供了丰富的类，诸如事件发生器、统计分析器、自动轨迹仿真器、事件操纵器等来构造仿真环境。它遵循事件图模型，这种模型可以优化模拟速度、提高可扩展性。相对其他模拟器而言，HyperSim最大的优点就是运行速度快，可以用来模拟大规模的网格环境。此外，它还具有通用性，可扩展性和易配置等特点。
　　HyperSim提供了一系列的库函数，可以方便地随机生成不同的主机处理能力、网络带宽、通信延迟等参数。本文设计了一个模拟程序，以检验改进后的算法性能。取N值为4，计算资源数量为10，并且每个任务的预测执行时间给定。图2是网格任务中包含不同的任务数量时，调度到10台处理机的模拟结果。图中每个点表示的是均取5次模拟结果的平均值。从图中可以看出，Dmm算法的三个子策略性能均优于Min-Min算法；Dmm-min的性能在有些情况下优于Dmm-avg，但多数情况下不如Dmm-avg；而Dmm-max的性能总是低于Dmm-avg。因此，采用Dmm-avg子策略作为Dmm算法。模拟结果表明，Dmm-avg算法的性能比Min-Min算法提高了4.2%～6.1%。

　　图3给出了四种算法的负载均衡" title="负载均衡">负载均衡性比较。其中，Min-Min算法中每个处理机的负载极不平衡，主要原因在于Min-Min算法将执行时间最短的任务分配在负载最小的机器上，这导致执行时间长的任务分配到负载较大的机器上。Dmm算法的负载均衡性均高于Min-Min算法。其中，Dmm-avg的曲线最平滑，说明该算法的负载均衡性最高。