网格任务调度算法

网格任务调度算法（精选7篇）

网格任务调度算法 篇1

网格就是把整个因特网整合成一台巨大的超级计算机,实现计算资源、存储资源、数据资源、信息资源、知识资源和专家资源的全面共享。任务调度技术是网格核心服务之一。一个良好的任务调度能有效地协调和分配网格任务,有效降低网格计算的总执行时间和总耗费量,从而使网格达到最大的性能。任务调度技术对网格系统的应用是至关重要的。

1 网格中任务调度算法概述

在异构的网格系统中,根据任务一机器的映射策略在任务执行前是否可以调整,可将这些启发式任务调度算法分为静态调度算法和动态调度算法两大类。

1.1 静态任务调度算法

静态调度算法[1,2]是指所有的机器一任务映射策略在执行任务调度前就已经全部确定。现在网格计算中,常用的静态调度算法有OLB(Opportunistic Load Balancing)、MET(Minimum Execution Time)、MCT(Minimum Completion Time)、Min-min、Max-min、Duplex(Min-min算法与Max-min算法的结合)、GA(Genetie Algorithms)、SA(Simulated Annealing)、GSA(Genetic Simulated Annealing)、Tabu(禁忌调度算法)、A*(基于u叉树算法)、蚁群优化等。

1.2 动态任务调度算法

动态调度算法[1]是指,部分机器一任务映射策略在执行任务调度期间根据实际情况进行确定。现有的动态调度算法可以分为两类:在线模式(on-Line mode)和批模式(Batch mode)[3]。在线模式是指,每当网格调度器收到一个用户提交的任务,立即为之选择适合的计算系统,并将任务发送到该计算系统。而在批模式下,每当网格调度器收到一个任务,不是立即映射到计算系统,而是检查是否凑够一批任务,当凑够一批任务时,才为这些任务确定各自适合的计算系统。

1.3 静态和动态任务调度算法比较

静态算法相对较为简单,调度算法运行开销低,对数据的依赖性小,因而静态调度算法是网格计算中最早被研究的算法。由于此类调度算法有充足的时间投入调度计算,因而在实时性要求不高的计算系统中,使用该类算法可能更好。动态调度算法能够有效的解决负载评估、作业选择和作业迁移等问题,因此,在异构平台中,动态调度带来的负载均衡优势更加明显。但是动态调度算法解决上述问题时需要付出较高的系统开销。本文研究的是静态算法中遗传算法在网格任务调度的应用。

2 遗传算法在任务调度中的应用

2.1 遗传算法概述

2.1.1 遗传算法基础术语

1)种群(Population)和个体(Individuals):遗传算法处理的是染色体,或者叫基因型个体,通常以一串结构信息来表现一定数量的个体组成了种群(Population)。

2)种群规模(Population Size):种群中个体的数目。

3)适应度函数(Fitness Function):各个个体对环境的适应度值叫适应度。对于优化问题,适应度函数即为目标函数。遗传算法要求适应度函数为可以加以比较的非负函数。

4)编码(Coding)、译码(Decoding)操作:遗传算法必须包含两个必须的资料转换操作,即把搜索空间中的参数或解转换成遗传空间中的染色体或个体,称为编码操作;反之,称为译码操作。

5)选择(Selection)、交叉(Crossover)、变异(Mutation)算子:这三个算子是遗传算法的三个主要操作算子,遗传算子(Genetic Operatoin)是遗传算法的特点。

2.1.2 遗传算法的基本过程

一般遗传算法主要步骤:

1)随机产生一个有确定长度的特征字符串组成的初始种群。

2)对该字符串种群迭代执行下面两步,直到满足停止准则为止。

(1)计算种群中每个个体字符串的适应值。

(2)应用复制、交叉和变异等遗传算子产生下一代种群。

把在后代中出现的最好的个体字符指定为遗传算法的执行结果,这个结果可以表示问题的一个解。

2.2 遗传算法的实现过程

以下从染色体的编码和解码、种群的产生、适应度函数、遗传操作对遗传算法的实现进行分析网:

2.2.1 编码和解码

二进制编码方法是遗传算法中常用的一种编码方法,它使用的编码符号集由二进制符号。和1组成的二值符号集{0,1},它所构成的个体基因是二进制符号串。

二进制编码符号串的长度与问题所要求的求解精度有关。

假设某一参数的取值范围是[A,B],等分成2l-1个子部分,记每个等分的长度为,则它能够产生2l种不同的编码,参数的对应关系如下[4]:

假设某一个的编码是:X:xlxl-1xl-2…x1x2

则上述二进制编码所对应的编码公式为:

二进制编码优点:编码、解码操作简单易行;交叉、变异等遗传操作便于实现;符合最小字符集编码原则。缺点是长度较大,对于一些多维、高精度要求的连续函数优化问题,使用二进制编码来表示个体时将会有一些不利之处。

2.2.2 产生种群

产生初始种群方法通常有两种。一种是完全随机方法产生,它适合于对问题解无任何先验知识的情况;另一种是由某些先验知识转变为必须满足的一组要求,然后在满足这些要求的解中再随机地选取样本。在网格任务调度问题中,产生初始种群的方法即属于后者。

2.2.3 适应度函数

为了体现染色体的适应能力,引入了对问题中的每个染色体都能进行度量的函数,叫做适应度函数(fitness function)。通过适应度函数来决定染色体的优劣程度,它体现了自然进化中的优胜劣汰原则。对于优化问题,适应度函数就是目标函数。例如Tsp(Travelling Salesman Problem)问题目标是路径总长度为最短,自然地,路径总长度就可作为Tsp问题的适应度函数:

其中wn+1=w1,d(wj,wj+1)表示两个城市间的距离(路径长度)。

适应函数要有效地反映每个染色体与问题的最优解染色体之间的差距。若一个染色体与问题的最优染色体之间的差距较小,则对应的适应度函数值差就较小,否则就较大。适应度函数的取值大小与求解问题对象有很大关系。

2.2.4 遗传操作

简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。

选择操作也叫做复制(reproduction)操作,根据个体的适应度函数值所度量的优劣程度决定它在下一代是淘汰还是被遗传。一般地,选择将使适应度较大(优良)的个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小,例如通常采用的轮盘赌选择机制,∑fi表示群体的适应值之总和,fi表示群体中第i个染色体的适应度值,它产生后代的能力为其适应度值所占份额fi/∑fi。

交叉操作的简单方式是将被选择出的两个个体P1和P2(如图1所示)作为母体个体,将两者的部分码值进行交换。假设有如图1所示的8个位长的两个个体。

产生一个在1~7之间的随机整数c,假设现在产生的是3,将P1和P2的低三位交换:P1的高五位与P2的第三位组成10001001,这就是P1和P2的一个后代Q1个体;P2的高五位与P1的低三位组成数串1101110,这就是P1和P2的另一个后代Q2个体。其交换过程如图2所示。

变异操作的简单方式是改变数码串的某个位置的数码只有0和1这两种可能,有如下二进制编码表示:

其码长为8,随机产生一个1}8之间的数k,假如现在k=5,对从右往左的第五位进行变异操作,将原来的0变为1,得到如下数码串(第五位的数字1是经变异操作后出现的):

二进制编码表示的简单变异操作是将0与1互换,0变为1,1变为0。

现在对tsp的变异操作作简单介绍:随机产生一个l~n之间的数k,决定对回路中的第k个城市的代码w,做变异操作,又产生一个l~n之间的数w替代wk,并将wk加到尾部,得到:w1w2…wk-1wwk+1…wnwk

这个串有n+1个数码。注意,数w在此串中重复了,必须删除与数w重复的数以得到合法的染色体。

3 结束语

遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象,从而解决非常困难的问题。它不受搜索空间的限制性假设的约束,由于它固有的并行性,遗传算法非常适用于大规模并行计算,已在优化、机器学习和并行处理等领域得到了越来越广泛的应用。

摘要：该文首先分析比较了网格中任务调度的动态和静态算法,然后对遗传算法在任务调度中的应用进行了讨论,并给出了具体实现步骤,提供了一定的借鉴意义。

关键词：网格,任务调度,遗传算法

参考文献

[1]Braun T,Siegel H,Beck N,et al.A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C].8th IEEE Heterogeneous Computing Workshop(HCW'99),1999:1529.

[2]Singh H,Youssef A.Mapping and scheduling heterogeneous task graphs using genetic algorithms[C].5th IEEE Heterogeneous Computing Workshop(HCW'96),1996:8697.

[3]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002:9-11.

[4]郭海燕.基于混沌优化的量子遗传算法[J].西南科技大学学报,2005,20(3).

网格任务调度算法 篇2

互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布式计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算技术[1]的发展则迎合了21世纪并行与分布式计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境。

网格资源包括计算资源、存储资源和通信资源。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。如何使这些资源高效地完成计算任务是网格系统的研究重点之一。

由于在网格环境下的任务调度主要考虑的是一组相互独立、任务之间没有通信和数据依赖的元任务(metatask)映射。现有的任务调度算法可以分为在线模式(on-line)和批模式(batch-mode)两种。在线模式是任务一到来就加以映射,而批模式则是把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言,批模式得到了大量的资源信息,从而可以做出更合理的任务映射策略。在这里讨论的是批处理模式的任务调度,即调度程序的执行周期到时再集中映射。

以时间跨度(makespan)为优化目标的任务—资源映射是一个NP完全问题,解决这类问题常用启发式算法。经典的批模式算法有Min-min、Max-min、Suffrage、遗传算法、蚁群算法等。T.Braun[3]等人通过对一些常用的算法进行了比较,在一定规模时遗传算法所求出的时间跨度要优于其他算法一些,但随着规模扩大,其收敛性降低[4],因此本文提出了将遗传算法和Min-min算法相结合的改进遗传算法的任务调度优化模型,该算法也适合大规模任务的调度,并进行了仿真实验。

1 问题描述

任务调度问题的实质[2]就是在一个有n个需要调度的任务、m个可用的资源(主机或集群) 的网格环境下,把n个子任务J={J1,J2,…,Jn}以合理的方式调度到m个资源R={R1,R2,…,Rm}上去,目的是得到尽可能小的总执行时间,提高系统吞吐量等。具体描述如下:

(1) J是n个需要调度的任务集合,Ji表示第i个任务。每个任务的任务量大小用百万指令(MI)表示,且每个任务只能一个资源上执行完成。

(2) R是m个可用的资源集合,Rj表示第j个资源。每个资源的计算能力用百万指令每秒(MIPS)表示。

(3) n个任务在m个不同资源上的预测执行时间ETC( Expected Time to Compute)是一个n×m的矩阵。矩阵中的每一行代表某一个任务在m台资源上的不同执行时间,每一列代表在同一台资源上n个任务的不同执行时间。ETC(i,j)表示第i个任务在第j个资源上的执行时间。

(4) 资源j的最早可用时间为STARTTIME(j)。

(5) 把任务i所需的数据从存储系统传输到资源j上的传输时间为TRANS(i,j)。

(6) 第i个任务在第j台资源上的预测最小完成时间为MCT(i,j),则MCT(i,j)=STARTTIME(j)+TRANS(i,j)+ETC(i,j)。

(7) 任务i的最小完成时间为Ci,当任务分配给第j个资源时,Ci=MCT(i,j)。

(8) 所有任务都执行完成的时间为时间跨度(makespan),即makespan=Max{Ci,i=1,2,…,n}。

2 设计与实现

遗传算法(GA)是Holland于1975 年受生物进化论的启发而提出的,并行性和全局解空间搜索是GA的两个最显著的特点。网格任务调度问题是一个NP问题,在一定规模时,用遗传算法进行网格任务调度能得到很好的性能。Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的时间跨度。遗传算法随着调度规模的扩大,在一定调度时间限制内,它的收敛性会逐渐降低。因此,本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法。

2.1 Min-min算法

Min-min算法的主要思想如下(仍然考虑n个任务,m个执行单元的情况):

(1) 对集合中每一个等待分配的任务T,分别计算出分配该任务到m台机器上的最小完成时间,这就得到了一个n×m的MCT矩阵。

当需要调度的任务集合非空时,反复执行以下操作直至集合为空:

(2) 利用MCT矩阵,对集合中每一个等待分配的任务分别找到能够最短时间完成该任务的执行单元及最短完成时间,在所有的最短完成时间中找出最小的最短完成时间对应的任务a,设其对应的主机为b,把任务a分配到机器b上。

(3) 从任务集合中把任务a删除,同时更新MCT矩阵。

2.2 染色体的编码与解码

染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码)或者间接编码。本文采用间接编码方式,对每个子任务占用资源编码。染色体的长度等于子任务的数量,染色体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号。假设有10个子任务,3个可用资源,则染色体串长为10,每个基因的值则为随机产生的3个资源的编号,则可以随机产生了下面的一个染色体编码:

{2,1,3,2,2,3,1,1,3,1}

这个染色体代表第一个任务由第二个资源上运行,第二个任务由第一个资源执行,以此类推,第十个任务由第一个资源执行。染色体以数组形式存放。

产生了一个染色体后,还必须对其进行解码,得到不同资源上任务的分布情况。将任务按照占用的资源分类,生成多组按照资源编号分类的任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的任务,这样我们就得到了所有任务在多个资源上运行的分布情况。以上面的染色体为例,解码后产生3个资源的任务序列:

R1:{2,7,8,10} R2:{1,4,5} R3:{3,6,9}

这样就可以计算出每个资源完成该资源上分配的所有任务花费的时间,最大花费时间即为时间跨度。

2.3 初始种群生成与适应度函数

在网格环境下,对任务调度的实时性有较高的要求,为提高算法收敛的速度以及改善算法的结果,要求初始种群既具有随机性的个体,又具有一些比较优秀的个体。本调度算法是在Min-min算法基础上,采用遗传算法对其性能进行提高,又可以避免单独采用遗传算法对大规模任务资源匹配的低收敛性。我们可以先将用Min-min算法产生的染色体作为初始种群的优秀个体,再随机产生其他个体。

遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。由于网格调度的目标是时间跨度尽可能小,因此适应度可定义为:

fitness(i)=1/makespan(i)

即染色体i的适应度值等于该染色体的时间跨度的倒数。若时间跨度越小,则适应度值越大,被选择的可能性越大。

2.4 个体选择

选择操作是决定父代种群中哪些个体,以及能以多大可能性被挑选来复制或遗传到下一代的进化操作。选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向:挑选最优秀个体,使算法避免无效搜索且能快速搜索到问题的最优解。

假设本算法的种群大小为popsize,为了保留优秀个体,先选择Min-min算法产生的个体和父代中的最优个体,其他的popsize-2个个体采用轮盘赌法[5]进行选择。个体的选择概率为:

Pi=fitness(i)/∑fitness(j)

需要进行popsize-2轮选择。每一轮产生一个[0,1]均匀随机数,若该数位于某个体累积概率下的那个区间,则选择该个体。

2.5 交叉与变异

交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。这里的交叉算子采用多点交叉,对于m个交叉点的多点交叉,随机选择m个交叉位置,在交叉点之间的变量间续地相互交换,产生两个新的后代,但在第一位变量与第一交叉点之间的一段不做交换,交叉点的个数根据染色体的长度进行选择。多点交叉具有很强破坏性,可以促进解空间的搜索。

变异本身是一种局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,是遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。

这里变异算子实质上就是将某个子任务迁移到另一个资源上执行,为了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行。

2.6 算法流程

(1) 随机产生n个任务,m个资源,根据任务的任务量大小和资源的计算能力生成一个n×m的初始MCT矩阵。

(2) 根据Min-min算法生成一条对应该调度的染色体。

(3) 随机产生大小为M的初始种群,根据每个资源上的子任务的执行序列,计算每条染色体的适应值。

(4) 选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群。

(5) 判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(4)。

3 仿真结果与分析

本文的实验是对gridsim、遗传算法、Min-min算法深入研究的基础上进行的,任务的长度范围、资源的执行能力范围、任务分配给某一资源的执行时间等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法用到的主要参数有:解的群体规模为20,交叉和变异概率分别为0.8和0.2,任务个数为表2中的几种,资源个数为10,算法终止条件设为到达一定的进化终止代数,最大进化代数设为100,如果算法连续20代没有找到更好的解我们则认为算法基本收敛。

图1描绘了三种算法时间跨度随任务数大小的变化曲线。从图中我们可以看出:改进GA相对于Min-min算法在性能上会普遍有所提高;对于GA,当任务数较少时(小于40个),性能对于Min-min算法也会提高,较小还高于IGA,随着任务数的增加,性能会逐渐下降,甚至还低于Min-min算法。所以GA不太适合用于大规模的网格任务调度,而本文提出的这种改进遗传算法对网格任务调度普遍适用。

4 结束语

用遗传算法和Min-min算法作为网格任务调度算法已经得到广泛的应用。当规模较小时,遗传算法被证明是一种最有效的启发式调度算法,但随着资源数和任务数的不断增加,遗传算法的性能逐渐降低,到达一定规模时甚至还低于Min-min算法,这样不仅性能得不到提高,而且还会增加调度时间。本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法,这种算法对于大规模任务调度性能也比较高。

由于本文在设计时没有将经济因素考虑在内,下一步的工作可以将开支预算与时间期限考虑在内,再结合本算法,可用于基于经济模型的网格任务调度。另外,模拟退火算法局部搜索能力比较强,遗传算法全局搜索能力较强,将两者结合搜索能力会尽一步提高,性能可能会有所提高。

参考文献

[1]Foster I,Kesselman C.The Grid-Blueprint for a New Computing Infra-structure.Morgan Kaufmann Publishers,1998.

[2]Abraham A,Buyya R,Nath B.Nature’s heuristics for scheduling jobs on computational grids.In The8th IEEE International Conference on Advanced Computing and Communications India,2000.

[3]Braun T,Siegel H,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810-837.

[4]Carretero J,Xhafa F.Using genetic algorithms for scheduling jobs in large scale grid applications.In Workshop of the European Chapter on Metaheuristics EUME2005,Metaheuristics and Large Scale Optimiza-tion.Vilnius,Lithuania,2005(5):19-21.

浅析网格环境中的任务调度算法 篇3

网格是以资源共享为目的,利用互联网将分散与不同地域的计算机组织起来,成为一个虚拟的“超级计算机”。每台参与的计算机就是一个“节点”,成千上万的节点组合起来,成为一张“网格”。从而能够充分地利用网络中的空闲计算能力,实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源等全面的共享。

随着Internet的发展, 网格计算技术逐渐成为新的研究领域。网格系统由大量异构资源组成,具有复杂、动态和自治等特点。高效的调度算法可以充分利用网格系统和处理能力,从而提高应用程序的性能。为了实现网格资源的优化配置,并为网格用户提供较为满意的服务质量,任务调度技术一直以来成为人们研究的热点。

文献[1]对当前现有的网格任务调度算法进行了深入而详细的讨论。文献[2]提出了一种基于任务池模型的分级调度方法,保持了系统资源之间的共享关系和高度可控性。文献[3]提出基于Min一Min算法的最小完成时间偏差调度算法(Dev_Min一Min),解决了任务调度的负载均衡和吞吐率高的问题。文献[4]提出了MD一sufferage算法,缩短调度跨度的同时保证较小的任务等待时间。文献[5]提出了同时考虑任务带宽要求和负载均衡要求的改进算法,设计了一种有依赖关系的任务调度算法。本文提出Segment Qos Min-Min RR任务调度算法,平衡了负载,提高了任务的完成时间和平均等待时间,达到算法简单并且效率较高的要求。

2 RR 算法

RR算法是一种动态调度算法。首先将网格任务以任意的顺序被提交到可用的处理单元(PE)上,直到所有的网格任务都提交完。然后把未执行完的任务连接成一个环,一旦此时有执行完的任务,立即从环中把一个还没有执行完的网格任务调度在此可用的处理单元上,即此时有多个处理单元同时在运行同一个网格任务。只要其中一个处理单元上的网格任务执行完,立即杀死所有的任务。重复上述过程,直到所有的任务执行完。如果此时动态有新的任务加入,就立即开始执行。

设T是一个大小为L的n个任务的集合,m为一个计算网格上处理器的数目,定义T的调度如下:

T的一个在具有m个处理器的网格上的调度S是一个三元组 <v,p,t> 的集合, 它们满足R1和R2规则,v∈T,1≤p≤m,t是任务v的起始时间,<v,p,t>∈S,意味着处理器p在时间间隔t~t+d执行任务v,d是通过p的处理能力和v的L计算出来的, 所以称t+d为任务v的完成时间。

R1:对每一个v∈T,至少有一个 <v,p,t>∈S。

R2:不存在这样的两个三元组 <v,p,t>,<v',p',t'>∈S;t≤t'≤t+d,t+d为任务v的完成时间。上述功能可以描述如下:

R1保证每一个任务v至少执行一次 ,R2是说每一个处理器在任何一个时刻最多只能执行一个任务,<v,p,t>∈S称为一个任务实体。

用下列公式来计算处理器的代价:

RR算法确定可以提高资源的利用率 , 但同时也造成了资源的浪费,另外,同一时刻有多个处理单元在运行同一个任务也是一种浪费。

改进的RR算法:就是所有的任务对处理单元都是共享的,只要有到来的任务想让它立即执行就可以。根据任务分配的处理速度 (MIPS), 定义了最大处理速度(MaxM IPS)、最小处 理速度 (Min MIPS) 和最大任 务数(Maxcount),所有的任务可以同时执行 ,所以任务的状态只有停止和运行,没有等待状态。此改进和算法大大提高了任务的完成时间,提高了系统的性能。

3 Min-Min 算法

在Min-Min算法中,首先分别计算每个任务在所有机器上的最小执行时间,执行时间最短的那个任务被选出来并被分配到相应的机器上,然后把这个最近被映射的任务从集合中删除,重复执行这个过程直到所有的任务都被映射。文献[3]研究表明,在不同的ETC矩阵下,Min一Min比OLB、MET、MCT、Max一min等算法均有更好的调度性能。 但还存在局限性:(1)潜在的负载不均衡,使得资源利用率低;(2)没有考滤网格任务的服务要求。

对于一个由n个元任务构成的集合T,以及m个主机集合M,Min一Min算法的执行过程如下:

(l)对主机的就绪时间向量R进行初始化 ,使得对于任意Mj∈M有R(j)=0,然后根据预测执行时间矩阵ETC计算出每个任务Ti在每个主机Mj上的预测完成时间,根据预测完成时间定义,有CT(i,j)=ETC(i,j)+R(j);

(2)当任务集合T不为空时 ,反复执行以下操作直至任务集合为空:

a.对集合中的每个任务Ti(i=1,2,…,n),计算它在所有主机上的最小预测完成时间, 若它在主机Mj上的预测完成时间最小,记minC T(i)=CT(i,j),并记录min CT(i)所对应的主机编号host_min CT(i)=j;

b.找出min CT矩阵中的最小值 ,即找出具有最小的最小完成时间的任务, 并将它分配给对应的主机执行。例如,若任务Ta对应的min CT(a)最小,则将编号为host_min CT(a)的主机分配给任务Ta;

c. 从任务集合T中删除任务Ta, 更新主机Mk(k=host_minC T(a))的就绪时间R(k)=min CT(a),并更新预测完成时间矩阵CT。

4 Qo S Guided Min-Min 算法

这种算法是让高服务质量的任务先执行,低服务质量的后执行,并且不让高的服务质量的任务长期处于等待状态,从而减少了等待时间。

5 Segmented Min-Min 算法

每一个任 务在每一 台机器上 都有一个 期望时间ETC (Expected Time to Comput), 如果这里有t个任务和m台机器,就获得一个t X m的ETC矩阵,ETC(i,j)表示任务i在机器j上的执行时间。

Segmented Min-Min算法根据ETC来对这些任务进行排序。根据平均这些任务按序排成链表。然后这些链表中的每一个任务分成同样大小的片,并且大任务的所有片先调度。每一个任务中的片均采用Min-Min算法来调度。

6 Segment Qos Min-Min RR 算法

这种算法是在改进的RR算法的基础上,一是先加入Min-Min算法的思想, 让完成时间最短的任务先执行,让尽可能多的任务找到合适的机器来执行;二是加入Qos Guided Min-Min算法的思想,对任务和资源分别设定服务质量级别,有某个服务质量级别的任务只能在同等级别或高于此级别的任务和资源之间达到最合理的匹配;三是利用Segmented Min-Min算法的思想,让大的任务先执行并且考虑到任务的分解,这样不但平衡了负载,也同时在任务的完成时间和平均等待时间上得到了提高。

以上算法得到了几种实现。

(1)实现RR算法和改进和RR算法(RR1)。由于原始的任务提交是任意顺序的,因此在这里采用先来先服务的方式,即先到达的任务先被提交,后来的只能等待前面的都提交了才能被调度。

(2)实现Min-Min算法。由于要让最小完成时间的任务先提交,因此就要有一个衡量标准,即评价任务的完成时间。在这里只考虑任务的大小,而不考虑其他因素的影响,那任务越小,完成时间越短,也就意味着要先调度小的任务。

(3)实现Qos Min-Min算法。为了定义任务和资源的服务质量级别,这里增加了一个参数Qos。

(4)实现Segment Qos Min-Min RR算法。为了实现任务的分解,可以编写一个任务分解函数segmentgridlet(),把任务分成几个子任务片来调度。

7 实验仿真

常用的模 拟器有Bricks、MicroG rid、Sim Grid、GridS im、Chic Sim、EDGSim等 ,其中重点Sim Grid。表1中的数据就是用Sim Grid模拟器仿真的。表1中记录了在任务数分别取200、300、400、500时,不同算法的任务最终完成时间。

8 结束语

网格任务调度算法 篇4

网格计算在现代社会成为解决大型工程科学计算的趋势, 同时也是实现全球资源共享的一种途径[1]。任务调度问题一直以来都是计算网格技术的关键技术和难点, 对它的研究在基础理论和系统开发等方面都具有重大的意义。近年来, 出现了很多多目标优化算法来解决网格调度问题, 比如蚁群算法、进化算法等, 但是一直网格调度问题是一个NP难题, 很难找到最优解。

已经有很多学者在任务调度中做了大量研究:Vincenzo介绍了一种基于遗传算法的资源调度算法[2], 其目的是为了尽可能地提高资源的使用率和吞吐量;叶春晓等提出了基于改进遗传算法的网格任务调度算法[3], 引进了min-min和min-max算法初始化种群, 有效的解决了网格任务调度问题。本文在现有算法的研究基础上, 提出了一种基于改进的进化优化网格任务调度算法 (简称IE-GTSA) 。

1 问题描述

由于网格环境受异构性、安全性、成本等诸多因素的制约, 一个好的任务调度系统对网格是至关重要的。因此, 本文在设计网格环境中的调度系统时, 主要考虑是基于网格中的所有任务的执行时间 (makespan) 和总执行费用 (cost) 考虑的。调度系统作以下条件假设:

(1) 每个计算机程序可分解成多个相互间独立的任务;

(2) 任务的数量远远大于资源数量;

(3) 每个任务在标准资源上运行所需要的时间已知;

(4) 不考虑任务所占用的存储资源和传输延迟;

2 目标函数定义

调度算法考虑两个因素:任务运行的任务的执行时间和总执行费用。目标函数定义如下:

其中, n表示任务数;m表示计算资源数;Z1表示所有任务执行完所需的总时间函数;Z2表示所有任务执行完所需的总费用函数;ETij表示任务Ti在处理节点Rj上的预期执行时间;Tj表示处理节点Rj的最早可用时间;Uj表示资源Rj在单位时间内的价格。

3 算法设计与实现

3.1 染色体编码

算法采用任务-资源相对应的浮点数编码方式, 对每个任务占用的资源进行编码, 每条染色体的长度等于任务的总体数量, 染色体中的每一位都是正整数, 代表的是任务编号, 而该基因位置上的正整数代表该任务所占用的资源的编号, 如图1所示。

3.2 种群初始化

(1) 初始化交叉概率Pc, 变异概率Pm, 种群大小popsize, 进化代数maxgen。

(2) 输入任务书n、资源数m, 生成初始种群。算法伪代码如算法1所示。

算法1

3.3 遗传操作

遗传操作包括选择、交叉、变异三种形式。

3.3.1 选择操作

选择操作采用本文作者公开发表的一篇文献中的选择算子, 即基于目标空间分割思想的选择方案[4]。首先, 根据文献[4]中的目标空间分割算法将网格环境中基于makespan和cost的目标空间进行分割;其次, 当算法选择下一代群体时, 把个体之间的Pareto支配关系转换成分割区间总索引值的排序关系, 使得多维关系的比较转换为一维关系的比较, 根据个体的分割区间总索引值来选择下一代群体, 索引值越小的越容易被选择, 这样可以保证非支配解和最好的支配解被选择。

3.3.2 交叉操作

算法采用算术交叉的方法, 在交配池中随机选择两个父个体P1和P2, 根据交叉的概率Pc, 按下列公式产生新的两个子代个体P1和P2。

3.3.3 变异操作

变异操作的目的是为了提高算法的全局搜索能力, 增加种群的多样性。用其它变异概率为Pm的染色体值替换交叉算法产生的子个体的编码串中的某些染色体值, 形成新个体。选择染色体上的两个随机资源R1和R2, 分别在其对应的任务队列上随机选取对应的任务Tx和Ty, 并进行位置交换, 得到一个新的子个体。

3.4 算法实现

算法实现的流程图如图2所示。

4 仿真实验与结果分析

算法在网格仿真平台上Grid Sim进行了多组测试, 并与Min-min和Max-min算法进行了对性能比和分析。其参数设置如下:变异概率0.01, 交叉概率0.85, 种群规模为100, 进化代数为300, 并分别对资源处理节点和任务集进行了100次实验, 结果取平均值。实验结果如表1和表2所示。

以上实验结果表明了本文提出的网格任务调度算法IE-GTSA, 在资源数和任务数都不同的情况下, 其Makespan和Cost都比Min-min和Max-min算法优越。

5 结束语

本文针对网格环境中基于Makespan和Cost两个目标的任务调度问题, 提出了一种改进的进化优化网格任务调度算法 (IE-GTSA) , 该算法融合了目标空间分割的进化算法的思想, 在选择算子的设计上是非常有效的。算法经过模拟实验, 与Min-min和Max-min算法进行了性能比较, 体现出了IE-GTSA的优越性。

参考文献

[1]都志辉, 陈渝, 刘鹏.网格计算[M].北京:清华大学出版社, 2002.

[2]Vincenzo Di Martino, M Mililotti.Sub-optimal scheduling in a grid using genetic algorithm[sJ].Parallel Computing, 2004, 30 (5/6) :553-565.

[3]叶春晓, 陆杰.基于改进遗传算法的网格任务调度研究[J].计算机科学, 2010, 37 (7) :233-235.

[4]任长安, 李智勇, 陈友文.一种改进的基于目标空间分割的多目标进化算法[J].计算机应用研究, 2010, 27 (4) :1311-1314.

网格任务调度算法 篇5

关键词：市场驱动,QoS,任务调度算法,网格工作流

0 引 言

在网格环境中调度工作流应用是一个NP完全问题,目前已经提出了许多启发式的调度算法对其进行调度。这些算法所采用的调度策略可分为三类:性能驱动、市场驱动和信任驱动。性能驱动策略的目标是调度系统有效的分配工作流任务到合适的网格资源,使完成整个应用所花费的时间最少。目前,大多数网格工作流调度系统都采用这种策略(如GrADS,Prodan)。市场驱动策略则是在满足用户QoS需求的情况下,使完成整个应用所花费的成本最低。也有一些网格系统采用这个策略(如Nimrod-G)[1]。而信任驱动的策略才提出不久,应用较少。

本文旨在讨论一个市场驱动的网格工作流任务调度算法,即要在用户指定的时间约束范围内,使完成整个工作量所花费的成本最低。

1 问题描述

在网格环境中,不同的第三方提供了许多相似或相等的资源,使用这些资源都可以完成某项任务。但根据服务质量的不同,所需要花费的时间和成本就各不相同。因此,网格用户可以根据他们自身需求选择合适的资源。对于一个网格工作流管理系统,只考虑功能性的需求是不够的,必须考虑不同的QoS需求,如时间约束、成本约束等。目前,对工作流QoS的一般分类如图1所示。

在本文中我们只考虑时间约束。因为对于大部分用户,他们可能并不需要在最短的时间获得最好的服务,而是希望在某个时间期限内能够用最低的成本来完成某个应用。所以,我们提出的任务调度算法的目标就是在满足用户的时间需求的情况下,使完成应用所花费的成本最低。

2 工作流任务调度算法

为了实现上述目标,可以采用分治法来解决任务调度,实现的步骤分为三步:

(1) 资源发现和需求识别[2,3]

对工作流图中的每个任务,使用网格信息服务分别识别所有可用的资源,列出可用资源列表,并对资源按价格进行降序排列;同时获得用户的QoS参数,如时间约束。

(2) 分配时间约束:

将用户给定的总时间期限分配给每个任务 网格工作流的流程运转模型分为四类:简单运转模型、发散运转模型、聚合运转模型、特殊运转模型。在本文中只考虑流程的结构为串行、并行发散和同步聚合的情况,如图2所示。

为了讲述问题的方便,也使读者更容易理解,本文后面部分都将以下述流程(图3)为例,对其进行任务调度。

a) 对于串行的情况,我们采用动态规划的方法来分配时间约束

将本文的目标函数描述成静态规划问题,如下:

$\{\begin{array}{l}\text{Μ}\text{i}\text{n}c=g{}_1(t{}_1)+g{}_2(t{}_2)+\cdots +g{}_n(t{}_n)\\ t{}_1+t{}_2+\cdots +t{}_n\le D\\ t{}_i\ge 0i=1,2,\cdots ,n\end{array}$

其中D表示总的时间约束, ti表示分配给单个任务的子时间约束, gi(ti)表示在ti范围内对应的所采用资源的价格,c表示完成该流程所花费的总的成本。

把问题中的变量ti作为决策变量,将累积的量或随递推过程变化的量作为状态变量。设状态变量Si表示分配给任务Ti到任务Tn的子时间约束;决策变量di表示分配给任务Ti的子时间约束,即di=ti;这样就可以得到状态转移方程:Si+1=Si-di=Si-Ti,以及运行决策集合:

Di(Si)={di|0≤di=Ti≤Si}

从而写出动态规划的递推关系式为:

$\{\begin{array}{l}f{}_i(S{}_i)=\underset{0\le {\rm T}{}_i\le S{}_i}{{\displaystyle \min }}\{g{}_i({\rm T}{}_i)+f{}_{i+1}(S{}_i-{\rm T}{}_i)\}i=n-1,\cdots ,1\\ f{}_n(S{}_n)=\underset{{\rm T}{}_n=S{}_n}{{\displaystyle \min }}g{}_n({\rm T}{}_n)\end{array}$

利用这个递推关系式进行逐段计算,最后求得f1(D) 即为所求问题的最小花费。

b) 对于并行发散和同步聚合的情况,采用如下准则进行时间约束的分配

准则1:从开始任务到结束任务的每一条支路上的所有子时间约束之和小于等于总的时间约束D。

准则2:并行发散的每个分支所分配的子时间约束相同。如由Task9和Task10组成的分支和Task11的分支具有相同的时间约束。

准则3:分配给每个任务的子时间约束必须大于或等于其最小执行时间。

准则4:根据用三点时间估算法估计出来的时间来分配总的时间约束。

三点时间估算法所涉及的三个时间分别为:最早完成时间a;最可能完成时间m;最晚完成时间b。显然,完成某项任务所需要的上述三种时间都具有一定的概率。根据经验,这些时间的概率分布可以认为近似于正态分布,一般情况下,可按下列公式计算执行时间:T=(a+4m+b)/6。

根据上述准则,就可以将总的时间约束合理地分配给并行发散和同步聚合的任务。

(3) 任务调度

分别为每个任务在其所分配的时间约束的允许范围内选择价钱最低的服务,对这个价钱求和,就得到了完成这个工作流应用的总的花费。该调度算法的伪代码如下:

3 仿真实验及性能评价

GridSim[5]是为R Buyya开发的,是一种基于计算经济模型的网格仿真平台,可以提供时间约束和/或成本约束的调度,能够模拟网格的多方面特性,因此,本文将扩展Gridsim来进行仿真实验。

根据流程的需要,我们模拟了12种类型的资源,每种类型的资源都有4个不同的服务提供者,因服务质量不同,所需要花费的时间和价钱就有所不同,因此我们总共模拟了48个服务提供者。表1仅列出了用GridSim模拟的对Task1的测试资源。

在实验中,我们比较了两种不同的调度算法,一是本文提出的市场驱动的Market-Driven调度算法,二是不考虑约束条件,只要保证完成任务所花费成本最低的Min-Cost调度算法。我们以时间约束为横坐标,分别以所花费时间和所花费成本为纵坐标,对两种算法进行比较。

从图4中可以看出,本文提出的市场驱动的任务调度算法可以在用户时间约束范围内获得局部最优解,以按时抢占市场;而Min-Cost调度算法虽然可以以最低的成本完成某个应用,但所花费的时间却远远超出了用户的需求,这样就有可能导致用户错过市场先机,造成不可估量的损失。

4 总结和展望

本文在充分考虑了用户的QoS需求的情况下,提出了一种市场驱动的、对网格工作流进行调度的任务调度算法。仿真实验结果表明,该算法可以在用户指定的时间约束内完成某个应用,并获得较优的执行代价,能够满足市场的需求。

另外,在本文中只考虑了两种工作流运转模型,也只关注了QoS的一个方面——即时间约束。在未来的工作中,将充分考虑各种运转模型,并研究QoS其它方面对网格工作流任务调度的影响,以进一步改进本算法。

参考文献

[1]Buyya R.Economic-based Distributed Resource Management and Scheduling for Grid Computing.PhD Thesis,Monash University,Aus-tralia,2002,12.

[2]Buyya R,Murshed M.A Deadline Budget Constrained Cost-Time Opti-mize Algorithm for Scheduling Parameter Sweep Applications on the Grid.GridSim Toolkit Release Document,Dec.2001.

[3]Buyya R,Murshed M,Abramson D.ADeadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Appli-cations on Global Grids.Technical Report,Monash University,March2002.

[4]Wolski R,Plank J,Brevik J,Bryan T.Analyzing Market-based Re-source Allocation Strategies for the Computational Grid.International Journal of High-performance Computing Applications,2001,15(3).

网格任务调度算法 篇6

为了使计算任务调度算法具有如下的综合能力:既保证高效的调度效率,又可以准确地对计算资源动态特性进行描述,同时还可以满足计算任务提出者的QoS需求,我们在信任模型的基础上,结合高性能网络上的QoS概念和研究成果,提出了基于信任和QoS测量的任务调度算法。

1TB&QMSA算法

1.1几个基本定义

· 任务计算效率PE(Processing Efficiency) 是计算任务调度算法实施于具体计算任务的性能评价尺度之一。设Te为调度者在调度之前对计算任务的预计完成时间,Tα为计算任务实际的计算时间,则任务计算效率PE=Te/Tα,PE值越大,表明任务计算效率越高。

· 任务调度效率SE(Scheduling efficiency) 设Ne为调度者在调度之前预计的任务处理者数量,t${}_i^e$为预计的每个调度者处理同一任务的次数(理想t${}_i^e$=1,但是若发生任务回滚则t${}_i^e$≥2),任务Nα为实际的任务处理者数量,t${}_i^{\alpha }$为实际的每个调度者处理同一任务的次数,则任务调度效率$SE=\frac{{\displaystyle \sum _t}\left(t{}_i^e\times {\rm N}{}^e\right)}{{\displaystyle \sum _t}\left(t{}_i^{\alpha }\times {\rm N}{}^{\alpha }\right)}$。

· 服务预保评价PES(Pre-assured Service Estimate) 任务计算者在任务调度之前,向任务调度者报告它预计可以在本次任务计算中保证提供的计算能力,任务调度者采用信任等级制度描述提供服务预保的任务计算者所承诺的服务保证。假设:每次预保服务的完成评价。

$perf=\left(\begin{array}{l}+w{}^{+},\text{当}\text{预}\text{保}\text{服}\text{务}\text{正}\text{常}\text{提}\text{供}\\ -w{}^{-},\text{当}\text{预}\text{保}\text{服}\text{务}\text{不}\text{能}\text{正}\text{常}\text{提}\text{供}\end{array}\right)$

其中w+为预保服务正常提供的奖赏值,w-为预保服务不能正常提供的惩罚值,均可以由任务调度者自己设定;∑perf是某个任务计算者所有以前预保服务完成情况的统计,当wk≤∑perf<wk+1,任务调度者将这个任务计算者的预保服务等级设定为第k级,并且同时赋予调度者自己设定的服务预保评价WPSE。

1.2信任机制

网格计算系统中各个节点之间的信任包括以下两个部分:

1) 直接信任 源节点与目标节点通过直接交互和合作,进而产生的信任,由源节点直接获得;

2) 声誉 目标节点与非源节点通过交互和合作产生的信任,由其他非源节点推荐给源节点。

· 直接信任的定义(Definition of Direct Trust)

设节点i和节点j在某次计算任务中存在着直接的合作与交流,因此源节点i对目标节点j的直接信任TrustD(i,j)可以定义为:

$\text{Τ}\text{r}\text{u}\text{s}\text{t}{}_{(i,j)}^D=({\displaystyle \sum _{k=1}^{{\rm N}}\alpha }{}_k^{D}p{}_k^j)\times \rho {}_i^j$ (1)

其中,p${}_k^j$是节点j在以往计算过程中的统计参数,N为参数总数,α${}_k^D$为权重,ρ${}_i^j$为源节点i对目标节点I的好感系数。

· 声誉的定义

声誉是目标节点j与非源节点通过直接交互和合作产生的信任,由其他非源节点推荐给源节点i,因此目标节点的声誉Reputation,可定义为:

Reputationj=∑${}_{\begin{array}{l}k=1\\ k\ne i,j\end{array}}^{{\rm N}-1}$(β${}_k^R$×Trust${}_{(k,j)}^D$) (2)

其中,N=计算系统中非源节点数,β${}_k^R$为源节点i与非源节点k之间的关系测度(如合作成功率等),关系测度是可以动态调整的,并且有Σβ${}_k^R$=1,初始时$\beta {}_k^R=\frac{1}{{\rm N}}$。

1.3信任的定义

由于源节点i对目标节点j的信任由他们之间的直接信任Trust${}_{(i,j)}^D$和目标节点j的声誉Reputationj组成,因此源节点i对目标节点j的信任Trust(i,j)可以定义为:

Trust(i,j)=α×Trust${}_{(i,j)}^D$+β×Reputationj (3)

其中,α和β分别是直接信任Trust${}_{(i,j)}^D$与声誉Reputationj的权重,可以通过设置这两个系数来体现源节点i对目标节点j的信任的侧重方面。

1.4TB&QMSA算法描述

1.4.1 结合PE,SE,PSE的直接信任测度

对于每个VO而言,它们对分配到其上的计算任务进行调度,最直接的测度应该是计算任务的响应时间,VO可以利用对这个响应时间的各种优化和比较建模来提高任务计算效率(PE)。

因此,我们对于由源VOi发起的一个计算任务,设:在目标VOj上,预计的任务响应时间T${}_j^e$

T${}_j^e$=E${}_j^e$+Tr${}_j^e$+Sche+Q${}_j^e$ (4)

其中,E${}_j^e$为该计算任务在VOj上进行计算预计的执行时间,并有:

$E{}_j^e=\frac{\text{计}\text{算}\text{任}\text{务}\text{的}\text{计}\text{算}\text{量}}{V{\rm O}{}_j\text{的}\text{计}\text{算}\text{能}\text{力}\text{测}\text{度}}$

Tr${}_j^e$为该计算任务在VOi和VOj之间的网络传输时间开销,并有:

${\rm T}r{}_j^e=\frac{\left(\text{计}\text{算}\text{任}\text{务}\text{的}\text{代}\text{码}\text{描}\text{述}\text{量}+\text{计}\text{算}\text{任}\text{务}\text{的}\text{结}\text{果}\text{描}\text{述}\text{量}\right)}{V{\rm O}{}_i\text{和}V{\rm O}{}_j\text{间}\text{的}\text{网}\text{络}\text{传}\text{输}\text{能}\text{力}\text{测}\text{度}}$

Sche为预计调度算法的时间开销,并也有:

Sche=计算任务复杂度×VOj复杂度

Q${}_j^e$为该计算任务在VOj的子单元上排队预计的时间开销。

在此基础上,VOj的任务计算效率:

${\rm P}E{}^j=\frac{{\rm T}{}_j^e}{{\rm T}{}_j^{\alpha }}$

结合 PE,SE和服务预保评价(PSE)$W{}_{{\rm P}SE}^j\left(0<W{}_{{\rm P}SE}^j\le 1\right)$的定义,VOi和VOj之间的直接信任定义为:

$\text{Τ}\text{r}\text{u}\text{s}\text{t}{}_{(i,j)}^D=\left[\alpha {}_1^D\times \frac{{\displaystyle \sum _{k=1}^G{\rm P}}E{}_k^j}{G}+\alpha {}_2^D\times \frac{{\displaystyle \sum _{k=1}^{G}S}E{}_k^j}{G}\right]\times \left(\rho {}_i^j\times W{}_{{\rm P}SE}^j\right)(5)$

其中,G为VOi和VOj之间的历史合作总次数。

1.4.2 满足QOS需求的扩展

我们将计算网格看作一个以计算资源(虚拟组织)为结点的有向图,所以给出以下几个定义:

定义1 将计算网格看作有向图$G=\left(V{\rm O},E\right)$,VO是结点集,表示虚拟组织;E是边集,代表通信链路。${\rm N}=\left|V{\rm O}\right|$,${\rm M}=\left|E\right|$,边eij∈E,标识为$l{}_{ij}=\left(V{\rm O}{}_i,V{\rm O}{}_j\right)$表示从结点VOi到VOj之间的一条直通的链路,i,j=1,…,n;VOi,VOj∈VO。

定义2 每个结点有3个函数:

延迟函数 Dn:E→R+; 代价函数Cn:E→R+;

分组丢失率 Lr:E→R+;

定义3 每条边有4个函数:

延迟函数De:E→R+; 代价函数Ce:E→R+;

分组丢失率 Lre:E→R+; 瓶颈带宽Bwe:E→R+;

定义4 对于G上任意两点VOi和VOj,i,j≤N,i≠j:

· 若存在一条路径P(i,j)=(VOi,…,VOl,…,VOj),l≤N,l≠i,j,同时将(VOi,…,VOl,…,VOj)重新标${\rm P}{}_{(i,j)}=p{}_{(1,q)}=(v{}_1,v{}_2,\cdots ,v{}_q),q=\left|p{}_{(i,j)}\right|$,该路径上的延迟、代价、分组丢失率和瓶颈带宽为:

延迟:$D({\rm P}{}_{(i,j)})=D(p(1,q))={\displaystyle \sum _{k=1}^{q-1}D}n(v{}_k)+{\displaystyle \sum _{k=i}^{q-1}D}e(v{}_k,v{}_{k+1})(6)$

代价:$C({\rm P}{}_{(i,j)})=C({\rm P}{}_{(1,j)})={\displaystyle \sum _{k=1}^{q-1}C}n(v{}_k)+{\displaystyle \sum _{k=1}^{q-1}C}e(v{}_k,v{}_{k+1})(7)$

分组丢失率:

$Lr({\rm P}{}_{(i,j)})=Lr(p{}_{(1,q)})={\displaystyle \prod _{k=1}^{q-1}L}r(v{}_k)\times {\displaystyle \prod _{k=1}^{q-1}L}re(v{}_k,v{}_{k+1})(8)$

瓶颈带宽:

$Bw({\rm P}{}_{(i,j)})=Bw(p{}_{(1,q)})=\min \{Bwe(v{}_k,v{}_{k+1})|k=1,2,\cdots ,q\}(9)$

· 若VOi和VOj之间不连通,则D(P(i,j))=+∞,C(P(i,j))=+∞ ,Lr(P(i,j))=+∞ ,Bw(P(i,j))=0。

当计算任务本身具有一些特殊的QoS要求时,任务调度者此时必须还要考虑由定义2和3所定义的诸如延迟、代价、分组丢失率和瓶颈带宽等QoS影响因素。

定义5 对于G上任意两点VOi和VOj,i,j≤N,i≠j,设它们互相连通的路径集合为p(i,j),$L=\left|p{}^{(i,j)}\right|V{\rm O}{}_i$与VOj之间的最高信任、最小延迟、最小代价、最小分组丢失率和最大瓶颈带宽指标的矩阵分别为T′,D′,C′,LR′和BW′:

${{\rm T}}^{\prime }=\left[\begin{array}{ccc}+\infty & \cdots & {\rm T}rus{t}^{\prime }{}_{(1,{\rm N})}\\ ⋮& \cdots & ⋮\\ {\rm T}rus{t}^{\prime }{}_{({\rm N},1)}& \cdots & +\infty \end{array}\right]=\left[\begin{array}{l}{t}^{\prime }{}_1\\ ⋮\\ t^{\prime }{}_{{\rm N}}\end{array}\right]$

$D^{\prime }=\left[\begin{array}{ccc}0& \cdots & D^{\prime }(p{}_{(1,{\rm N})})\\ ⋮& \cdots & ⋮\\ D^{\prime }(p{}_{({\rm N},1)})& \cdots & 0\end{array}\right]=\left[\begin{array}{l}{d}^{\prime }{}_1\\ ⋮\\ d^{\prime }{}_{{\rm N}}\end{array}\right]$

$C^{\prime }=\left[\begin{array}{ccc}0& \cdots & C^{\prime }(p{}_{(1,{\rm N})})\\ ⋮& \cdots & ⋮\\ C^{\prime }(p{}_{({\rm N},1)})& \cdots & 0\end{array}\right]=\left[\begin{array}{l}{c}^{\prime }{}_1\\ ⋮\\ c^{\prime }{}_{{\rm N}}\end{array}\right]$

$L{R}^{\prime }=\left[\begin{array}{ccc}0& \cdots & L{r}^{\prime }(p{}_{(1,{\rm N})})\\ ⋮& \cdots & ⋮\\ L{r}^{\prime }(p{}_{({\rm N},1)})& \cdots & 0\end{array}\right]=\left[\begin{array}{l}l{r}^{\prime }{}_1\\ ⋮\\ l{r}^{\prime }{}_{{\rm N}}\end{array}\right]$

$Bw=\left[\begin{array}{ccc}+\infty & \cdots & B{w}^{\prime }(p{}_{(1,{\rm N})})\\ ⋮& \cdots & ⋮\\ B{w}^{\prime }(p{}_{({\rm N},1)})& \cdots & +\infty \end{array}\right]=\left[\begin{array}{l}b{w}^{\prime }{}_1\\ ⋮\\ b{w}^{\prime }{}_{{\rm N}}\end{array}\right]$

· T′(i,j)不存在传递性质,即T′(i,j)≠T′(i,k)×T′(k,j),因为T′(i,j)存在“声誉”;

· 若存在P${}_k^{(i,j)}$=(v${}_1^k$,v${}_2^k$,…,v${}_q^k$),k≤L则:

$D^{\prime }(p{}_{(i,j)})=\min \{D(p{}_k^{(i,j)})|p{}_k^{(i,j)}\in p{}^{(i,j)},k\le L\}(10)$

$C^{\prime }(p{}_{(i,j)})=\min \{C(p{}_k^{(i,j)})|p{}_k^{(i,j)}\in p{}^{(i,j)},k\le L\}(11)$

$L{r}^{\prime }(p{}_{(i,j)})=\min \{Lr(p{}_k^{(i,j)})|p{}_k^{(i,j)}\in p{}^{(i,j)},k\le L\}(12)$

$B{w}^{\prime }(p{}_{(i,j)})=\max \{Bw(p{}_k^{(i,j)})|p{}_k^{(i,j)}\in p{}^{(i,j)},k\le L\}(13)$

· 若P(i,j)为空,D′(p(i,j))=+∞,C′(p(i,j))=+∞,Lr′(p(i,j))=+∞,Bw′(p(i,j))=0。

定义6 假设任务调度者为VOi,它在调度计算任务之前需要对所有己知的计算资源进行结合满足用户Qos需求的评价。出于简化的目的,评价公式被定义为:

w′i=[α${}_i^{w1}$(d′i)T+α${}_i^{w2}$(c′i)T+α${}_i^{w3}$(lr′i)T+α${}_i^{w4}$(bw′i)T+β${}_i^w$(t′i)T] (14)

其中: α${}_i^{wj}$(1≤j≤4)为调度者VOi对用户关于延迟、代价、分组丢失率和瓶颈带宽等QoS测度的重视权重,β${}_i^w$为调度者VOi对结合了PE,SE和PSE测度的信任的重视程度。进一步,对于不同的任务调度者VOi,由于各自的α${}_i^{wj}$(1≤j≤4)和β${}_i^w$的取值不同,从而形成满足QoS需求的评价矩阵W′=[w′1,…,w′N]T。

2TB&QMSA算法仿真模拟

2.1仿真结果比较

对TB&QMSA算法的相关参数进行一下设定:

1) 设计算任务调度者在计算网格虚拟组织集合中的编号i=0;

2) 设公式(14)中各QoS测度权重为α${}_0^{w1}$=1,α${}_0^{w2}$=0,α${}_0^{w3}$=0,α${}_0^{w4}$=0,信任权重为β${}_0^w$=1;

3) 设公式(5)中PE,SE和各VMj的PSE的权重为α${}_1^D$=1,α${}_2^D$=1和ρ${}_0^j$=1,j=1,2,…,N-1;

4) 设PSE定义的w+=1,w-=2,TN为历史计算过的任务总数,则有:

$W{}_{{\rm P}SE}=\left(\begin{array}{cc}0.5& -\infty <{\displaystyle \sum {\rm P}}erf\le 0.5{\rm T}{}^{{\rm N}}\\ 1.0& 0.5{\rm T}{}^{{\rm N}}<{\displaystyle \sum {\rm P}}erf\le 0.9{\rm T}{}^{{\rm N}}\\ 2.0& 0.9{\rm T}{}^{{\rm N}}<{\displaystyle \sum {\rm P}}erf\le 1.0{\rm T}{}^{{\rm N}}\end{array}\right)$

5) 设公式(3)中直接信任和声誉的权重为α=1和β=1;

6) 设公式(2)中各VOk的声誉权重为β${}_k^R$=1, k=1,2,…,N-1;

7) 仿真网格中所有虚拟组织与虚拟组织之间的延迟在(0,1]内随机生成。

同时,为了验证TB&QMSA算法的效果,我们也在相同仿真环境下模拟了不包含QoS测度约束的任务调度算法(NSA)的调度过程。仿真模拟结果如图1所示。

2.2结论

由于TB&QMSA算法内含信任机制,并且我们对信任测度选取了任务计算效率(PE)、任务调度效率(SE)和服务预保信任(PSE)。其中,SE直接受网格环境的稳定性影响;而PE也能因为网格环境不稳定,进而使PE值较为低下;另外,PSE对虚拟组织提出的服务承诺的兑现情况进行奖励,而预保服务是否可以兑现,除了虚拟组织本身的投入态度,更重要也受网格不稳定因素的影响。因此,TB&QMSA算法中的信任机制对网格内的所有虚拟组织进行PE、SE和PSE的统计,从而在任务调度决策时,可以提高在不稳定的网格环境下的整体任务调度效率。

摘要：为了既保证高效的调度效率,又可以准确地对计算资源动态特性进行描述,并且对这种动态性所带来的消极影响实施规避行为,同时还可以满足计算任务提出者的QoS需求。因此在对网格计算和计算网格系统的知识背景以及该领域的研究现状进行认真分析的基础上,提出了可以解决此问题的基于信任机制和QoS测量的计算任务调度算法。

关键词：网格,任务调度,QoS

参考文献

[1] Chen Hongtu.Distributed Dynamic Scheduling of Composite Tasks on Grid Computing System.Proceeding of the International Parallel and Distributed Processing Symposium,IEEE,2002.

[2]Farag Azzedin,Muthucumam Maheswaran.Evolving and Managing Trust in Grid Computing System.Proceeding of the2002IEEE Canadian Con-ference on Electrical&Computer Engineering.

[3]Farag Azzedin,Muthucumaru Maheswaran.Towards Trust-Aware Re-source Management in Grid Computing Systems.Proceeding of the2nd IEEE/ACM International Symposium on Cluster Computing and the Grid(CCGRID02),IEEE,2002.

网格任务调度模型的研究 篇7

网格任务调度模型是对网格任务调度问题的一个映射或是一种解释。一个结构合理的调度模型应该能够很好地反映任务调度问题的相关流程，完整地解释所要讨论的问题范围，并给出严密的条件约束，不至使建立的模型无解或是无可行解。本文分析研究了经典的任务调度模型，提出了一个具有两层结构的调度模型，包含树形全局调度模型和局部调度模型两层,很好地解决经典模型中存在的问题，并保证了网格调度系统具有高安全性和活性等其他优点。

1 网格任务调度模型

中心式网格调度模型和分布式网格调度模型是两种经典的网格任务调度模型。中心式网格调度模型便于管理整个网格系统，但如果发生单点失效，后果是严重的，适用于中小规模、单管理域的网格系统中;分布式网格调度模型解决了中心式模型单点失效的问题，但是也存在不足。

1.1 中心式网格调度模型

中心式网格调度模型[1,2,3,4]只有一个网格调度器(Grid Scheduler,GS)。调度器负责接受用户提交的应用并监测网格中所有计算资源的静态和动态信息，为每一个或是每一批任务映射合适的资源。中心式调度模型可分两层：第一层为网格调度器，第二层为各个网格资源的资源代理。调度器通过与资源代理通信来监测网格资源和任务的分配。

中心式网格调度模型中只有一个网格调度器，如果发生单点失效，整个网格系统就会瘫痪，用户提交的任务也将丢失，资源上处理完的任务结果无法进行返回，所以必须保证其安全性和可靠性。有效的措施是建立备用网格调度器，这样就增加了额外的经济开销。因此，中心式网格调度模型适用于中小规模、单管理域的网格系统中。

1.2 分布式网格调度模型

在分布式网格调度模型中，每个网格调度器只管理本地域的任务调度和资源管理。通过多个调度器之间的协作，为任务选择合适的资源。网格调度模型的拓扑结构是网格调度器之间相邻关系的集合。中心式模型中只有一个网格调度器，不存在调度器之间的协作，所以网格调度器的拓扑结构是空集。文献[5]中把分布式调度模型器的拓扑结构描述成一个完全图，即每个网格调度器都互相直接连接;文献[6]中把拓扑结构描述成一个非完全图;文献[7]中则把拓扑结构描述成一棵树。

完全图结构的调度模型中，当某一个单点失效时，剩余调度器的拓扑结构依然是完全图，可保证系统的安全性和可靠性，也可保证失效节点上任务的最终执行。因为每个调度器都与其它调度器连接，可以实现任务与资源的最优映射，调度器之间的任务迁移代价最小。缺点是在大规模网格中的实现代价昂贵。非完全图结构的调度模型是完全图结构调度模型的简化形式，其拓扑结构是不规则的。因此发生单点失效时，拓扑结构会发生很大的变化，原本具有相邻关系的调度器可能会不再相邻。如果非完全图具有桥[8]，失效节点恰恰是桥的端点，则该拓扑结构将分裂成两个独立的调度空间。

2 树结构的网格调度模型

树形结构的调度模型可简化网格平台的实现，降低节点的通信复杂度和便于网格资源的管理。树形结构是一种规则的拓扑结构，当发生单点失效时，可利用有关树的相关算法，对分裂成两个独立空间的部分进行合并。本文提出的调度模型采用树形结构的网格调度模型。调度模型采用两层结构：全局调度和局部调度。

2.1 全局调度模型

每个节点有一个权值P，表示该节点单位任务的处理能力。新的网格调度器加入网格或是一个网格调度器退出网格系统，此拓扑结构就根据平衡二叉树的插入和删除算法进行调整，把分裂成两个独立结构的树重新进行组合。由此可以实现网格系统的可扩展性、安全性和可靠性，如图一所示。

根节点调度器是网格系统的入口，负责接收任务和向其子节点分配任务。调度过程为：当根节点接收到任务集合时，向负载较轻的子结点进行负载迁移。如果子节点负载较重，则使任务处于等待状态，直到其子节点负载较轻或是能够自己进行处理。各层的节点与根节点的工作原理一样，负载较轻时，接受父节点分配的任务;负载较重时，向其子结点分配任务。树形结构的全局调度过程是一个可实现各个网格节点负载平衡的任务迁移过程。因此，树形结构的网格调度模型具有天然的负载平衡的优点。

2.2 局部调度模型

局部调度模型的主要功能是负责管理本地域内的任务调度和信息检测。主要模块包含有任务池、容错处理器、任务调度器和信息检测器，如图二所示。

(1)任务池

任务池保存了本域内新到达的和以往已经映射过但还没有调度的任务，任务池中的任务都是已分解的独立任务，不包含优先约束关系。任务池保存任务副本直到其执行完毕并返回结果。

(2)任务调度器

任务调度器为每个任务按照其特性分配一个相应特性的机器，并把任务发送到指定的机器上运行。任务调度器在内部节点无任务或是负载较轻的前提下向其分配任务。为了防止出现任务总是得不到执行的情况，引入了老化因子。基本思想是，将上次没有得到执行的任务在下次重新映射时让它变老，相应的提高了该任务的执行优先级。任务调度器根据老化因子来对任务进行调度。

(3)容错处理器

容错处理器具有任务死锁的检测和处理功能。当任务的等待时间超过了生命周期规定的期限，但是依然没有反馈信息，容错处理器自动认为此任务处于死锁状态，杀死此任务并重新调度。容错处理器具有节点失效的检测、处理功能。当局部管理域中的一个站点失效不可用时，任务调度器将保存在任务池中的任务副本重新分配，保证任务的最终完成。

(4)信息检测器

信息检测器的功能是及时地检测资源的动态信息。节点的负载情况采用状态驱动策略[9]，状态驱动策略可以有效地避免负载抖动，降低通信开销。如果节点的CPU占用率过低或过高，信息检测器及时主动地向任务调度器发送信息，任务调度器将根据情况进行追加调度或是进行负载迁移。

3 结束语

本文首先介绍了两种经典的网格任务调度模型，中心式网格调度模型和分布式网格调度模型，分析了各自的优点和缺点，并在其基础之上设计了具有两层结构的调度模型：全局调度和局部调度。全局调度模型采用二叉树拓扑结构，很好地解决了网格调度器的单点失效问题，并且很好地实现了各个网格调度器之间的负载平衡。

摘要：网格任务调度是采用适当的调度策略把应用程序分配到异构的计算节点上进行高效的执行并返回正确结果的过程。本文研究了经典网格任务调度模型,分析了各自的优缺点,并提出了一种包含有树形全局调度模型和局部调度模型的两层结构模型,此树形全局调度模型通过负载从根节点自上而下的迁移,能够很好地实现网格系统的负载平衡。通过二叉树的节点删除算法能够很好地解决模型中节点的失效问题,因此具有很好的安全性和可靠性。

关键词：网格,任务调度模型,树形调度模型

参考文献

[1]Martino D,Sub V.Optimal Scheduling in a Grid Using Genetic Algorithms.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:148-154.

[2]Ernemann C,Hamscher V,Schwiegelshohn U,et a1.On Advantages of Grid Computing for Parallel Job Scheduling.2nd IEEE/ACM International Sympo-sium on Cluster Computing and the Grid(CC-GRID2002),2002:31-38.

[3]Ranganathan K,Foster I.Decoupling Computa-tion and Data Scheduling in Distributed Data-Inten-sive Applications.11th IEEE International Sympo-sium on High Performance Distributed Computing,2002:352-258.

[4]Subramani V,Kettimuthu R,Srinivasan S,eta1.Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests.11th IEEE International Symposium on High Performance Distributed Computing,2002:359-366.

[5]Chen Hongtu,Maheswaran M.Distributed Dynam-ic Scheduling of Composite Tasks on Grid Computing Systems.16International Parallel and Distributed Processing Symposium(IPDPS’02),2002:88—97.

[6]Arora M,Das S K,Biswas R.A De-Centralized Scheduling and Load Balancing Algorithm for Hetero-geneous Grid Environments.International Conference on Parallel Processing Workshops,2002:499-505.

[7]Cao Junwei,Spooner D P,Jarvis S A,et a1.A-gent-based Grid Load Balancing Using Perfor-mance-driven Task Scheduling.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:49-58.

[8]左孝陵,李为监,刘永才等.离散数学[M].上海:上海科学技术文献出版社,2003:280-286.