Min―Min任务调度算法的研究与仿真

摘 要：文章首先对Min-Min算法进行分析，介绍了算法的思想和执行过程。然后使用GridSim模拟器对算法模拟实现，给出了算法的JAVA实现代码，并统计了Min-Min算法实验结果的完成时间。

关键词：Min-Min算法；任务调度；GridSim模拟器

1 概述

在网格计算中，大量的计算任务被调度到资源上，如何使任务得到最少的完成时间，在很大程度上是由它的调度算法所决定的[1]。良好的任务调度算法是任务调度的重要组成部分。目前，关于网格计算的任务调度算法，国内外学者已经取得了大量的研究成果。这些调度算法大多是基于启发式的思想来解决问题的，比如有遗传算法、蚂蚁算法、Min-Min算法、Max-Min算法等[2]。由于Min-Min算法是一个经典的任务调度算法，文章对Min-Min算法进行研究，然后用模拟器对算法模拟实现。

2 Min-Min算法

为了研究的方便，文章进行了如下的定义：

（1）假设网格任务集为Tasks={T1，T2，T3，... ，Tn}，集合内有n个待调度的独立任务。

（2）网格资源集为Hosts={H1，H2，H3，...，Hm}，该资源集合内有m个资源。设资源Hj的就绪时间（即资源最早的可以使用的时间）为R（j）。

（3）任务Ti在资源Hj上的完成时间定义为ECT（i，j），定义任务在资源上的执行时间为ETC（i，j）。

（4）从上面定义得出，一个任务Ti在资源Hj上的完成时间计算公式如下：

ECT（i，j）=ETC（i，j）+R（j）

（5）n个任务在m个资源上的ETC可以用一个n×m的矩阵来表示，矩阵元素ETC（i，j）表示第i个任务在第j个资源上的执行时间，该矩阵的一行表示任务Ti在资源集合Hosts中所有资源的执行时间，一列表示在同一资源上n个任务的执行时间。

Min-Min算法的思想是：首先，计算出任务列表中所有任务在所有资源上的最小完成时间。其次，从这些最小完成时间中找出一个值最小的，把这个最小时间对应的任务资源对找出来，把该任务提交给该资源执行，从任务列表中删除这个任务。最后，更新最小完成时间矩阵。重复以上步骤，直到任务列表为空。该算法的目的是将任务指派给不仅完成它最早的，而且执行它最快的机器，使得全部的任务完成时间最小[3]。该算法的执行过程如下：

（1）计算任务集合中的任务Ti在m个资源上的完成时

间，得到n×m的ECT矩阵。

如果任务集合Tasks不为空时，重复以下步骤直到任务全部调度。

（2）得出每个任务的最小完成时间即ECT（i，j），把这些最小完成时间放入一个集合M内，然后找出这个集合内最小的值，根据最小值所对应的任务资源对（i，j），这就是任务到资源的映射。

（3）把该任务Ti提交到对应的资源Hj上执行，同时还要更新此ECT矩阵。

3 Min-Min算法的模拟实现

文章采用GridSim模拟器对该算法进行仿真实验，GridSim工具包设计的实体类有：Gridlet类、User类、Broker类、Resource类、GIS类等[4]。Gridlet类是用来对任务进行描述的，包含的属性有任务ID，任务的状态，任务的计算量。User类是描述网格上的用户，一个用户有唯一的ID。Broker类是用户的。Resource类是描述网格上异构资源的类，通常一个资源类包括多个Machine类，一个Machine类由多个PE组成。GIS是网格的信息服务中心，它负责资源的发现、注册和管理的功能。使用模拟器编写一个MyTest继承GridSim类，然后编写Min-Min算法如下关键代码：

int JOB_NUM = 10， RES_NUM = 4；// 任务数与资源数

double ETC[][] = new double[JOB_NUM][RES_NUM]；

double CT[][] = new double[JOB_NUM][RES_NUM]；

double R[] = new double[RES_NUM]； //资源就绪时间数组

int MAX_JOB_RUN_TIME = 0x7ffffff；

double minCT[] = new double[JOB_NUM]； //任务的最小完成时间数组

int host_minCT[] = new int[JOB_NUM]； // 任务最小完成时间对应的主机

int scheduled = 0； // 调度的任务数，初始为0；

int min_minCT_index=0； //具有最小完成时间的任务索引号

while （scheduled < JOB_NUM） {

for （int i = 0； i < JOB_NUM； i++）

{ // 计算每个任务的预测完成时间CT[i][j]

Gridlet gridlet= （Gridlet） list_.get（i）；

for （int j = 0； j < RES_NUM； j++） {

int mip = resCharS[j].getMIPSRating（）；

if （ETC[i][j] ==Double.MAX_VALUE）

{

CT[i][j] = ETC[i][j]；

} else

{

ETC[i][j]=gridlet.getGridletLength（）/mip；

CT[i][j] = ETC[i][j] + R[j]； // CT[i][j]

}

}

}

for （int i = 0； i < JOB_NUM； i++）

{

for （int j = 0； j < RES_NUM； j++）

{

if （CT[i][j] < minCT[i]）

{

minCT[i] = CT[i][j]； // 计算minCT

host_minCT[i] = j； // 计算host_minCT

}

}

}

for （int i = 0； i < JOB_NUM； i++）

{

if （（minCT[i] ！= 0） && （minCT[i] < minCT

[min_minCT_index]））

{

min_minCT_index = i；

}

}

Gridlet gridlet = （Gridlet） this.list_.get（min_minCT_index）；

super.gridletSubmit（gridlet，resourceID[host_minCT[min_minCT_index]]）；

//提交任务到资源

R[host_minCT[min_minCT_index]]+= minCT[min_minCT_index]；

scheduled++；

}

根据以上代码进行仿真实验，任务数JOB_NUM为50，资源数RES_NUM为10，仿真实验进行100次，用Min-Min算法进行任务调度，得到的Makespan去平均值。经模拟实验计算出Makespan的值为550。

当JOB_NUM为100，RES_NUM为10，采用以上同样的方式调度，计算出Makespan的值为1000。当JOB_NUM为150，资源数RES_NUM为10，得出的模拟结果Makespan的值为1620。当任务数JOB_NUM为200，资源数RES_NUM为10，得出的模拟结果Makespan的值为2100。

由以上的实验，我们可以得到如图1模拟结果，其中横坐标表示任务数，纵坐标为整个调度系统所有的时间。

4 结束语

基于以上对Min-Min算法的分析，我们可以得出Min-Min算法由于对任务选择执行它最快的资源，因此，它的完成时间较快。在今后的网格计算研究中，还需要考虑其它的因素，比如经济原则、负载均衡和服务质量，对改进后的算法使用GridSim模拟器进行仿真验证。

参考文献

[1]王建锋.网格计算的应用及发展前景[J].大众科技，2005.

[2]Ian Foster， Carl Kesselman. The Grid： Blueprint for a New Computing Infrastrueture[M].Morgan Kaufmann Publishers，1999：1-30.

[3]王向慧.网格计算中任务调度算法的改进[D].2009.

[4]吴淞.基于网格仿真平台GRIDSIM的任务调度算法[D].

2006.