网格计算中Min-Min算法及改进算法的研究

摘要：讨论了Min-Min算法、QoS guided Min-Min算法以及基于任务优先级的QoS guided Min-Min算法，并分析了实验仿真结果。

关键词：网格计算；任务调度；Min-Min算法；实验仿真

0　引言

网格计算任务调度就是根据一定的调度规则和调度策略，把用户提交的一组任务，按照一定执行时序分配到网络上并行分布系统的多个计算节点上，以最小化并行应用程序的执行时间，使整个网格系统的资源利用率达到最高。网格计算任务调度的好坏在很大程度上取决于它的调度算法的有效性和效率。良好的任务调度算法是实现高效使用共享资源的重要保障之一。

在网格计算环境下的任务调度算法中，Min-Min算法是一个重要的网格调度算法，许多算法都以Min-Min算法为基础，并且都以Min-Min算法作为其比较优劣的对象。

1　基于最短完成时间的Min-Min算法

1.1　Min-Min算法思想

该算法是一个比较传统、经典的任务调度算法，它的主要调度原则就是将具有最短完成时间的任务分配到对应的资源上，保证以最短的时间执行完所有的任务。任务调度问题的本质是在一个由m个需要调度的任务、n个可用的任务执行单元(主机或集群)以及由k个数据存储单元构成的网格环境下，把m个任务T-{T1，T2，…Tm}以合理的方式调度到n个主机H={H1，H2，…，Hn)上去，使得总执行时间尽可能小。m个任务在n个不同机器上的预测执行时间ETC(Expected Time to Compute)是一个m×n的矩阵，矩阵元素ETC(i,j)表示第i个任务在第j台机器上的预测执行时间，矩阵中的每一行代表某一任务在n台机器上的不同执行时间，每一列代表在同一台机器上m个任务的不同执行时间。

1.2　Min-Min算法的不足之处

Min-Min算法总是优先调度短任务，以最快的速度减少调度队列中的任务，尽量缩短所有任务的完成时间，当机器空闲时一些执行时间较长的任务才能得以执行，这样便导致了主机负载不均衡，利用率降低。因为当网络传输等条件对局部任务调度影响很小的时候，整个网格处在一个异构的环境中，这时候机器的处理能力将完全决定了任务的调度策略。换句话说，如果某个节点的计算能力大于同一个局域网内其它节点的时候，所有调度到这个局部的任务都会调度到这台机器上去，其它机器则长期处于空闲状态，大量的任务处在等待调度的状态，造成局部的负载严重不平衡。

2　基于服务质量的QoS guided Min-Min算法

2.1　QoS guided Min-Min算法思想

该算法把任务对带宽的要求考虑进去，将其作为选择资源的一个标准。首先在网格资源中，将主机分为两类，一类是具有高QoS的主机群，另一类具备低QoS或者不具备QoS的主机群；其次，类似地将用户提交的任务也分为两类，具有高Qos要求的任务和具备低Q05或者不具备QoS要求的任务。该算法先对高QoS任务使用Min-Min算法进行调度，将其分配到高Qos资源上执行；然后再对低Qos任务使用Min-Min算法进行调度，将其分配到所有网格资源上执行。这种算法优先调度高QoS任务，避免了高QoS资源被低Qo$任务占据而得不到调度的问题。

设有m个需要调度的任务、n个可用的任务执行单元(主机或集群)和k个数据存储单元构成的网格环境，构造元任务集合为M；CTij为任务Ti在主机Mj上的完成时刻；ETij为任务Ti在主机Mj上的执行时间；Dj为主机Mi的下一个可用时刻，也就是下一个任务的开始时刻；则有CTij=CTij+Dj。该算法的步骤如下：

(1)首先根据性能预测模型和需调度的任务的要求。按照一定顺序依次计算出每个任务在每个主机E的执行时间巩。

(2)对元任务集合M中有高Qos要求的任务使用Min-Min算法依次进行匹配，直到这些任务全部映射完，并更新所有的Dj和CTij。

(3)对元任务集合M中剩下的任务使用Min-Min算法进行匹配，直到这些任务全部映射完。

2.2　QoS guided Min-Min算法的不足之处

(1)QoS Guided Min-Min算法仍然属于静态调度算法，只能对现存任务集合进行调度，而不能对动态变化的任务集合进行调度，算法适用的范围不大。

(2)在QoS guided Min-Min算法中，仅以带宽作为QoS评判标准进行调度，忽视了QoS的其它方面，可能造成高性能计算机(属于高QoS资源)被低QoS任务占据，网格中其它的一些低QoS资源空闲，而那个需要进行高性能计算的高Qos任务需要等待低QoS任务执行完毕才能执行的结果。这种现象严重浪费了网格资源。

3　基于任务优先级的QoS guided Min-Min算法

3.1　算法思想

在网格计算中对所有任务都赋予相应的优先级，有些任务对执行的时间要求很严格，而有些任务只须考虑满足用户费用要求，基于任务优先级的QoS guided Min-Miia算法可以使所有的任务获得最短的任务完成时间，尽管用户支付的费用并不一定最低，但不会超出用户容忍期限。算法简要描述如下：

(1)根据任务长度对任务进行降序排序，形成一个有序序列。

(2)根据序列的情况，将任务序列分为n段。

(3)运用Min-Min算法调度各任务段中的任务。其中长任务段具有较高的优先级，首先被调度到处理能力强的资源上。

与基于最短完成时间的Min-Min算法不同的是改进后的算法在调度执行前先根据任务长度进行排序，执行时间长的任务较早被调度，然后在每个任务段内运用基于最短完成时间的Min-Min算法。假设需要被调度的任务包含若干执行时间短的任务和若干执行时间长的任务，那么执行时间长的任务集合将会首先被调度到处理能力强的资源上执行，而后再调度执行时间短的任务。当任务队列中短任务数多于长任务数时，在执行长任务的同时能执行若干短任务，这样任务的整体执行时间可能只由长任务来决定，而长任务又被分配到了最佳的资源上，所以会使总的任务执行时间缩短。算法的第二步是将任务序列分为N段，N值的选择很关键。一方面，N值越大负载越趋均衡；另一方面，N值过大会使Min-Min算法降低效率。

3.2　算法的不足之处与优点

该算法的不足之处在于，N的不同取值会导致任务分配的均衡度与算法的执行效率之间的矛盾出现。

算法的优点在于调度时将特殊任务先进行处理，将它们分配到所需的特殊资源上执行，避免了这些特殊资源被普通任务占用而特殊任务需要等待的现象。同时在Min-Min算法中，考虑了任务数据的传输时间。对任务进行了排序，同时又考虑了QoS因素，从很大程度上节省了调度时间。

4　仿真实验和结果分析

为了验证以上几种算法的有效性，我们在不同的情况下对它们的性能进行了仿真实验，采用澳大利亚墨尔本大学开发的网格资源模拟器GridSim对算法进行模拟。仿真实验的目的是对Min-Min算法、QoS guided Min-Min算法和任务优先级的QoS guided Min-Min算法进行比较。仿真实验根据任务数、资源数和特殊任务的百分比不同分为三种情况：

(1)任务数20，资源数10，具体仿真数据情况见表l。

(2)任务数40，资源数20，具体仿真数据情况见表2。

(3)任务数60，资源数30，具体仿真数据情况见表3。

从上面三个表可以看出：

①不管任务量的多少，QoS guided Min-Min算法相对于Min-Min算法在执行效率上平均提高10％左右，而基于任务优先级的Qos guided Min-Min算法相对于QoS guidedMin-Min算法在执行效率上平均提高3.5％左右。

②随着资源数量的增加，三种算法的执行时间都在增加。因为随着资源数量的增加，网格环境中可供使用的资源增加。计算能力提高，可供选择的资源也随着增加。

③不管特殊资源百分比是多少，改进后的算法性能均有提高。当进行任务调度时，如果任务对资源有特殊要求，满足该要求的资源数量也会随着特殊资源百分比的增加而增加。因此不管采用何种算法，任务的完成时间都会随着特殊资源百分比的增加而减小。

④不管分段数N是多少，改进后的算法性能均有提高。无论任务数和资源数为多少，总是在N值为4时算法性能最好。因此，任务序列通常都分为4段。

5　结束语

网格任务的调度是一个非常复杂、重要且具有挑战性的问题。笔者分析研究了网格计算中常用的任务调度算法，并采用网格模拟器Gridsim针对这些算法进行了仿真实验。仿真结果表明，改进后的调度算法具有较高的性能，能够更加真实地体现并满足用户的需要。