来源：电子技术应用 作者：中国石油大学 梁鸿 张千 丁仁伟

    摘要：以传统、经典的min-min调度算法为基础，提出了一种基于“分段”思想的改进策略，并且采用hypelsim网格模拟器对算法进行了仿真。改进的算法较好地解决了传统min-min算法存在的负载不平衡的问题。仿真结果表明，改进的算法合理，具有较高的性能。

    关键词：调度min-min divided-min-min模拟hypersim

    网格(grid)技术是当今计算机领域的研究热点之一。在网格技术飞速发展的同时，网格计算中的任务调度问题也变得越来越重要。网格环境中各处理器的运行速度、主机的负载、网络通信的时间等都是动态变化的，资源的管理和调度十分复杂，多机环境下的任务调度问题便成为一个众所周知的np问题。目前，围绕着网格计算中的任务调度算法，国内外已经做了大量的研究工作，先后提出了各种静态和动态的调度算法。本文对传统的、经典的min-min调度算法进行深入的分析和研究，指出该算法存在的缺陷，并在此基础上提出一个基于“分段”思想的改进算法，并且在网格模拟器环境下进行仿真实验。仿真结果验证了改进后算法的合理性和有效性。

    1 min-min算法概述

    在网格环境下，高效的调度策略或算法可以充分利用网格系统的处理能力，从而提高应用程序的性能。任务调度同题的实质就是在一个由m个需要调度的任务和n个可用的任务执行单元(主机或集群)构成的网格环境下，把m个任务t={t1,t2,……tm]以合理的方式调度到n个主机h={h1,h2,……hn}上去，目的是得到尽可能小的总执行时间(makespan)。m个任务在n个不同机器上的预测执行时间etc(expected time to compute)是一个m×n的矩阵。etc(i，j)表示第i个任务在第j台机器上的预测执行时间，矩阵中的每一行代表某一任务在n台机器上的不同执行时间，每一列代表在同一台机器上m个任务的不同执行时间。

    以完成时间为优化目标的任务一资源映射是一个np完全问题，所以需要辅助的启发式算法。对于传统的min-min、max-min、a*和ga等静态启发式算法，tracyd.braun等人已经做了详细的研究。结果表明，ga算法在不同etc矩阵下的性能是最好的，min-min和a*次之。并且tracy d.braun的研究表明：对于每个etc矩阵，ca算法的平均执行时间是60秒，而a*算法是20分钟。由于算法中各项参数是通过nws等服务得到的一些提前预测值，因此在参数随时问剧烈变化的网格环境下，ga或a*的计算时间会显得很长，因而得到的调度策略也很不合理。

    min-min算法仍然是目前网格调度算法的研究基础之一。该算法的主要思想是：当需要调度的任务集合非空时，反复执行如下操作直至集合为空：

    (1)对集合中每一个等待分配的任务ti，分别计算出把该任务分配到n台机器上的最小完成时间，记为mintime(i)，可以得到一个含有m个元素的一维数组mintime；

    (2)设第k个元素是mintime数组中最小的，其对应的主机为b，把任务k分配到机器b上；

    (3)在任务集合中把任务k删除。

    由于btin-min算法总是优先调度短任务，当机器空闲时一些执行时间较长的任务才能得以执行，这样便导致了主机负载不均衡，利用率降低。对此，本文提出一个改进的算法来优先调度执行时间长的任务，即分段min-min算法dmm(divided-min-min)。

    2 基于分段思想改进的min-min算法

    dmm算法首先根据任务的etc进行排序，即根据平均etc或最小眦或最大etc将任务归为一个从大到小的有序序列；然后将这个任务序列分成相同大小的段，先调度长任务段，后调度短任务段。对于每个任务段，仍然使用min-min算法进行任务调度。dram算法描述如下：

    (1)计算每一个任务的排序值keyi。在阿格异构环境下，同一任务在不同机器上的执行时间是不同的，这被称为网格的任务异构。考虑到任务异构性，在确定排序值时测试了三种子策略——平均、最小、最大预期执行时间。

    子策略l：dmm-avg计算etc矩阵中每一行的平均值：