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

1、MinMin任务调度算法的研究与仿真摘 要：文章首先对Min-Min算法进行分析，介绍了算法的思想和执行过程。然后使用GridSim模拟器对算法模拟实现，给出了算法的JAVA实现代码，并统计了Min-Min算法实验结果的完成时间。关键词：Min-Min算法；任务调度；GridSim模拟器1 概述在网格计算中，大量的计算任务被调度到资源上，如何使任务得到最少的完成时间，在很大程度上是由它的调度算法所决定的【1】。良好的任务调度算法是任务调度的重要组成部分。目前，关于网格计算的任务调度算法，国内外学者已经取得了大量的研究成果。这些调度算法大多是基于启发式的思想来解决问题的，比如有遗传算法、蚂蚁算法

2、、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在

3、资源Hj上的完成时间计算公式如下：ECT（i，j）=ETC（i，j）+R（j）（5）n个任务在m个资源上的ETC可以用一个nxm的矩阵来表示，矩阵元素ETC（i，j）表示第i个任务在第j个资源上的执行时间，该矩阵的一行表示任务Ti在资源集合Hosts中所有资源的执行时间，一列表示在同一资源上n个任务的执行时间。Min-Min算法的思想是：首先，计算出任务列表中所有任务在所有资源上的最小完成时间。其次，从这些最小完成时间中找出一个值最小的，把这个最小时间对应的任务资源对找出来，把该任务提交给该资源执行，从任务列表中删除这个任务。最后，更新最小完成时间矩阵。重复以上步骤，直到任务列表为空。该算法的

4、目的是将任务指派给不仅完成它最早的，而且执行它最快的机器，使得全部的任务完成时间最小【3】。该算法的执行过程如下：（1）计算任务集合中的任务Ti在m个资源上的完成时间，得到nxm的ECT矩阵。如果任务集合Tasks不为空时，重复以下步骤直到任务全部调度。（2）得出每个任务的最小完成时间即ECT（i，j），把这些最小完成时间放入一个集合M内，然后找出这个集合内最小的值，根据最小值所对应的任务资源对（i，j），这就是任务到资源的映射。（3）把该任务Ti提交到对应的资源Hj上执行，同时还要更新此ECT矩阵。3 Min-Min算法的模拟实现文章采用GridSim模拟器对该算法进行仿真实验，GridSi

5、m工具包设计的实体类有：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_NU

6、M = 4；/ 任务数与资源数double ETC = new double；double CT = new double；double R = new double； /资源就绪时间数组int MAX_JOB_RUN_TIME = 0x7ffffff；double minCT = new double； /任务的最小完成时间数组int host_minCT = new int； / 任务最小完成时间对应的主机int scheduled = 0； / 调度的任务数，初始为0；int min_minCT_index=0； /具有最小完成时间的任务索引号while （scheduled JOB_N

7、UM） for （int i = 0； i JOB_NUM； i+） / 计算每个任务的预测完成时间CTGridlet gridlet= （Gridlet） list_.get（i）；for （int j = 0； j RES_NUM； j+） int mip = resCharS.getMIPSRating（）；if （ETC =Double.MAX_VALUE）CT = ETC； elseETC=gridlet.getGridletLength（）/mip；CT = ETC + R； / CTfor （int i = 0； i JOB_NUM； i+）for （int j = 0； j R

8、ES_NUM； j+）if （CT minCT）minCT = CT； / 计算minCThost_minCT = j； / 计算host_minCTfor （int i = 0； i JOB_NUM； i+）if （minCT ！= 0） && （minCT minCT）min_minCT_index = i；Gridlet gridlet = （Gridlet） this.list_.get（min_minCT_index）；super.gridletSubmit（gridlet，resourceID）；/提交任务到资源R+= minCT；scheduled+；根据以上代码

9、进行仿真实验，任务数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】王建锋.网格计算的应用及发展前景.大众科技，2005.【2】Ian Foster， Carl Kesselm