（计算机应用技术专业论文）基于遗传算法的网格任务调度研究.pdf

摘要 网格计算( g r i d c o m p u t i n g ) 是当前互联网研究中的一个热点，也是并行和分 布处理技术的一个发展方向。在网格计算中，任务管理、任务调度和资源管理是 网格必须具备的三个基本功能。其中任务调度的目的是在包含大量不同计算机的 网格环境中，同时考虑各网格节点的计算性能、节点之间的通讯性能等参数，把 不同的任务以最合理的方式分配到相应的网格结点去完成。任务调度也称为任务 映射。由于在网格环境中各处理器的运行速度、主机的负载、网络通讯的时间等 是动态变化的，因此任务调度问题同时也是一个非常困难的n p 完全问题。 目前，围绕着网格计算中的任务调度问题，国内外已经做了大量的研究工作： 网格资源管理与调度系统研究，以及任务调度算法研究。 本论文就网格任务调度算法展开了以下研究： 深入分析了网格任务调度问题，并对t i t a n 任务调度机理进行了剖析； 就目前网格任务调度算法存在的问题，提出了一种新的基于遗传算法的调度 方案。在该调度算法中，可以通过调整适应度函数中参数的值来满足网格用户和 资源提供者对任务调度的不同需求； 用g r i d s i m 模拟器对提出的调度算法进行了仿真实验，并且与n i m r o d g 算法 进行了比较，结果表明本文中提出的调度方案更适合网格环境中的任务调度，具 有更好的调度效果。 关键词：网格计算；任务调度；t i t a n ；遗传算法；g r i d s i m a b s t r a c t g r j dc o m p u t j n gj sah o t s p o tj nt h c ”s c a r c ho fi n t e 皿e ln o w a d a y s ，b u la l s oi sa d e v e l o p i n go r i e n t a t i o n0 fp a r a l l e la n dd i s t r i b u t e dp r o c e s s i n gt e c h n o l o g y i ng r i d c o m p u t i n g ，t h et a s km a n a g c m e n t ，t h et a s ks c h e d u l i n ga n dt h er c s o u r c em a n a g e m e n ta r e t h r e eb a s i cf u n c t i o n st h a t t h e 鲥dm u s th a v e t _ l l ep u r p o s eo ft a s ks c h e d u l i n gi st o a s s i g n d i f f c f e n t 、t a s k st o c o r r c s p o n d i n gg r i d n o d c r a t i o n a l l y ， s i m u l t 卸e o u s l y c o n s i d e r i n gt h cc o m p u t i n gp c 由r m a n c e0 fe a c hg r i dn o d ea n dt h ep a r 锄e t e r 锄o n g n o d e ss u c ha sc o m m u n i c a t i o np e r f o 瑚a n c ci n g f i de n v i r o n m e n tw h e r cc o n t a i n s m a s s i v ed i f f e r e n tc o m p u t e r s i a s ks c h e d u l i n gi sa l s ob e e nc a l l c dt a s km a p p i n g o w i n g t ot h cv a f i a b i l i t yo f p r o c c s s i n gv e l o c i t y i o a do fh o s tc o m p u t e r sa n dt h ct i m eo f n e 押o r kc o m m 岫i c a t i o n ，t h et a s k s c h e d u l i n gp r o b l e mi sl 【n o w nt ob ci ng c n e n l n p c o m p l e t c a tp ”s e n t ，t h et a s ks c h e d u l i n g ”s e a r c hi ng r i dc n v i r o n m e n ti sm a i n l yf o c u s e d0 n 柳o 髂p e c l s ：f e s 伽r c em a n a g 锄朋ta n ds c h e d u 】i n gs y s t e m ，a n dt h ca 】g o 订h m s i nt h i sp a p e r w ed os o m cr e s e a f c ho nt a s ks c l i e d u l i n ga i g o r i t h m ，弛dm a k et h e f o l l o w i n gc o n t r i b u t i o n s ： a n a l y z i n gt h et a s ks c h e d u l i n gp r o b l e m 姐dt h et 1 1 ：a ns c h e d u l i n gf r a m c d e e p l y a i m i n ga tt h et a s ks c h e d u l i n gp r o b l e m se x i s t e d ，w ep r o p o s ean e wg e n e t i c a 1 9 0 r i t h mf o r t a s km a t c h i n ga n ds c h e d u l i n gi ng r i de n v i r o n m e n t 1 nt h i ss c h e d u l i n g a l g o r i t h m ，w ec a nm e c tv a r i o u sn e e d so fu s e fa n dr c s o u r c ep r o v i d c rb ya d j u s t i n gt h e v a l u e0 ff i t n e s sf h n c t i o np a r a m e t e r s p e r f o 珊i n gae x p e r i m e n tb a s e do ng r i d s i mt oe m u l a t i n gt h ea l g o r i t h m ，a n d d o i n gc o m p a r j s o nw i t ht h ep o l i c ya n dt h en i m r o d ga l g o r “h m ，t h ee x p c r i m e n tf e s u l t s s h o wt h a tt h eg e n e t i ca l g o r i t h mp r o p o s e di nt h i sp a p e ri sf i tf o rg r i de n v i f o n m e n t ，a n d c a nr c c e j v eg r e a t c ra 矗c c t i 伽 k e yw o r d s ：g “dc 0 m p u t i n g ；i a s ks c h e d u l i n g ；t 1 1 ；g e n e t i ca l g o r i t h m ；g f i d s i m 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：爱破；乙日期：辟妒月歹名日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囵。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 嚼丕磊 t d h e t i ) ) z 。o ) 一( f 扣妇耐o ) 一i 叫“，o ) ) t 2 鼍l f it l i ) ) ( 4 3 ) 见式( 4 3 ) ，其中t d t 表示p 个作业的累加延迟时间。用t d 。表示累加延迟时 间的标准化值，用t 。表示最后一个任务的结束时间。则有公式( 4 4 ) ： 一缸p )荤( 4 4 ) 3 m a k e s p a n 值 用t 。( i ) 表示第i 个作业的关键时间，t c 为所有作业中t c ( i ) 的最大值。t 。t 表示 给定调度的最后一个任务的结束时间。用表示m a k e s p a n 值，见式( 4 5 ) ： = 1 一伍缸) ( 4 5 ) 4 网格计算节点空闲时间 由于有些网格节点没有得到充分利用，而使得空闲时间增加。 用m 表示第j 个网格节点的空闲次数，n 表示网格节点数。而铲0 ，k ) 表示第j 个节点的第k 次空闲起始时间，t g 。0 ，k ) 表示第j 个节点的第k 次空闲结束时间，见 式( 4 6 ) o 标准化见式( 4 7 ) ： r ，一主，睦。o ，( 肚) “( 肚】) ) 4 6 跏一强似p ) ( 4 7 ) 综上所述，可以选取适应度函数见式( 4 8 ) ： f 1 1 一( ( 口山+ ，。z + 口+ 死+ 亢+ z k ) 仁+ 卢+ 口+ a ) ) ( 4 8 ) 其中，a ，e ，e ， 为参数。根据网格用户和资源提供者对网格作业的要求对这 四个参数的大小进行相应的调整。 ( 1 )网格用户希望自己提交的作业能尽快完成，即周转时间要短： ( 2 )有些作业必须要在一定日期到来之前完成，即满足截止日期的要求： ( 3 )网格资源提供者希望自己提供的网格资源能被充分利用，即网格计算 节点空闲时问要短； ( 4 )每个网格计算节点上运行的若干作业要在尽量短的时间内完成，即 m a k e s d a n 值要小。 根据以上四个要求的紧迫性( 优先级) 程度，依次分别用9 ，o ，a ， 来 衡量。设9 ，o ，a ， 的取值均在0 1 之间，且b + o + a + = 1 。 如果网格用户和资源提供者对本次调度没有特殊要求，可以认为各个要求优 先级相同，那么设定这四个参数的值均为o 2 5 即可。 如果调度要求优先考虑网格用户的要求，则将参数b 和。的值适当调高，而 将a 和 的值相对调低。反之，如果网格资源提供者对自己网格计算节点是否被 充分利用的要求更严格，或者对m a k e s p a n 值有更高要求，则将q 和 的值适当调 高的同时降低b 和e 的值。 由上可知，我们可以根据具体调度要求来调整这四个参数的值，从而选定不 同的适应度函数，求得每种情况下的最佳调度方案。 4 3 3 遗传算子设计 遗传算法自身参数有3 个，即群体大小n 、交叉概率p 。和变异概率p m 。群体 大小n 太小时难以求最优解，太大则增长收敛时间。一般n = 3 0 一1 6 0 。交叉概率 p c 太小是难以向前搜索，太大则容易破坏高适应值的结构。一般取p 。= o 2 5 0 8 。 变异概率太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。 一般取p m = 0 0 1 o 2 。 4 3 3 1 选择算子的选取 在自然进化中，对生存环境适应程度高的生物将有更多机会遗传到下一代； 而对生存环境适应程度较低的物种遗传到下一代的几率相对较少，这就是所谓的 “优胜劣汰”。遗传算法使用选择算子模仿这个过程。适应度高的个体繁殖能力较 强，适应度较低的个体逐渐被淘汰，群体的整体品质得以提高。 个体选择的方法很多，例如轮盘赌选择方法、随机遍历抽样选择等等。由于 在标准遗传算法中采用轮盘赌方法选择后代，使适应度高的染色体具有较高的复 制概率，但是潜在的问题是：种群中最好的个体可能产生不了后代，造成所谓随 机误差。 本文中采用精英选择法避免上述所讲的随机误差。精英选择策略是把种群中 最优秀的个体直接复制到下一代。这个策略可以提高优秀个体对种群控制的速度， 改善局部搜索，从而改善了g a 特性。 4 3 3 2 交叉算子的选取 交叉算子是主要的基因重组过程，直观地讲，选择算子将原有的优良基因遗 传给下一代个体，而交叉算子则可以生成包含更多优良基因的新个体。 交叉算子的设计一般要考虑如下因素： ( 1 ) 必须保证优良基因能够在下一代中有一定的遗传机会； ( 2 ) 必须保证通过交叉操作存在生成优良基因的机会； ( 3 ) 结合编码格式设计高效的交叉算子。 本论文中的交叉算子采用两点交叉，交叉点的位置随机确定。经过交叉生成 的两个个体，分别对它们计算适应值。如果生成的子个体的适应值大于父个体， 则按照一定的概率替换父染色体。反之，则选择原种群中适应值最小的染色体比 较，如果新子个体的适应值大于最低适应值，则替换原染色体；否则舍弃生成的 子染色体，并重新选择父染色体进行交叉操作。 如图4 7 ( a ) 和4 7 ( b ) 为两个染色体，交叉位置分别为s 1 1 ，s 1 2 和s 2 1 ，1s 2 2 。 s 1 1s 1 2 p l p 2 p l p 2 ( b ) 图4 7 染色体例子 染色体交叉过程中问结果如图4 8 ( a ) 和4 8 ( b ) 所示： 粤胛 p 1 p 2 p l p 2 t ：t 1t 5t 4 k t ： t lt 3 t 4 t 3 ( b ) 图4 8 染色体交叉过程中闻结果 最后得到的下一代染色体分别如图4 9 ( a ) 和4 9 ( b ) 所示： p 。叵匿压圈 p 2 ( a ) p l p 2 t ：t 1t 5t 3 t 4 ( b ) 图4 9 下一代染色体 4 3 3 3 变异算子的选取 变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象，从而 改变染色体的机构和物理形状。在g a 进化中，变异算子从一定程序上克服了遗 传算法的早熟收敛，保证了群体具有一定程度的多样性，使群体具有进化能力。 同时，变异算子能够遍历整个编码空问，扩大算法搜索范围，保证算法收敛到最 优解。 在本论文中，我们采用基本位变异法，实质上就是将某个子任务迁移到另一 个资源上执行。为了防止子任务在迁移后，执行的时间增大而造成种群退化，在 此规定，迁移后子任务占用的资源不是随机产生的，而是在除了该子任务目前占 用的资源外的资源集中，选择使该子任务执行时问最短的资源，并将其迁移到该 资源上进行执行。 如图4 1 0 ( a ) 为一个染色体，经过变异之后，任务t 5 迁移到处理机p 2 上执行， 产生的新染色体如图4 1 0 ( b ) 所示。 叵匠压回 p 2 ( a ) p 1 p 2 it ： t lt 3t 4 i t ， ( b ) 图4 1 0 染色体变异过程 4 3 4 约束条件处理 实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各 样。在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未找到一种 能够处理各种约束条件的一般化方法。所以对约束条件进行处理时，只能是针对 具体应用问题及约束条件的特征，再考虑遗传算法中遗传算法的运行能力，选用 不同的处理方法。现有的处理方法主要有：搜索空间限定法、可行解变换法和罚 函数法。 搜索空间限定法的基本思想是对遗传算法搜索空间的大小加以限制，使得搜 索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。 对一些简单的约束条件，在个体染色体的编码方法上着手，就能够达到这种搜索 空间与解空间之间的一一对应的要求。用这种处理方法能够在遗传算法中设置最 小的搜索空间，所以它能够提高遗传算法的搜索效率。但需注意的是，除了在编 码方法上想办法之外，也必须保证经过交叉、变异等遗传算法作用之后所产生的 新个体在解空间中也要有确定的对应解，而不会产生无效解。 可行解变换法的基本思想是在由个体基因型到个体表现型的变换中，增加使 其满足约束条件的处理过程。即寻找出一种个体基因型和个体表现型之间的多对 一的变换关系，使进化过程中所产生的个体总能够通过这个变换而转化成解空间 中满足约束条件的一个可行解。这种处理方法虽然对个体的编码方法、交叉运算、 变异运算等没有附加的要求，但它却是以扩大搜索空间为代价的，所以一般会使 得遗传算法的运行效率有所下降。 罚函数法的基本思想是对在解空间中无对应可行解的个体，计算适应度时， 处以一个罚函数，从而降低该个体适应度，使该个体被遗传到下一代群体中的机 会减少。但是，当罚函数的强度太小的话，可能使不满足可行解的个体被遗传到 下一代，但是当罚函数的强度太大的话，又有可能使个体的适应度差异不大，降 低了个体之间的竞争力，从而影响到遗传算法的效率。 在本论文中，同一个资源上运行的任何两个子任务都必须满足d a g 图规定的 逻辑关系。假设t i ，j 都在某个序列中，且满足t i 一j ，即任务t j 必须在任务t j 之 前执行，但是如果在执行序列中任务t 先于任务t i 执行，则出现死锁现象，所以 必须采用一定的方法，避免出现死锁现象。 前面提到，所有任务之间的逻辑关系用一张d a g 图表示，可以对d a g 图进 行分层，每一层有一个深度值，深度值越小，代表优先级越高。可以采用深度遍 历的方法获取d a g 图节点的深度信息，获取深度信息之后，对在相同资源上运行 的任务序列，就可以按层次深度值由小到大排列，这样优先级越高的任务执行顺 序越靠前，对于同一资源上的所有任务，经过排序后得到的子任务执行序列就可 以避免出现死锁现象。 4 4 调度算法总体框架 如图4 1 1 所示为本文设计的基于g a 的调度算法总体流程图。 具体步骤如下： ( 1 ) 随机生成初始种群。 图4 1 l 调度算法流程图 3 8 ( 2 ) 根据适应度函数评价个体。对于每个个体，分配任务到所给资源上，得到 最早完成时间和最小时间问隔的资源，计算适应值。 在利用适应度函数评价个体时，首先要对网格用户和资源提供者所提出的要 求进行分析，通过分析，确定适应度函数中参数的取值，根据不同情况就可以选 用相应的适应度函数进行评价。 ( 3 ) 用精英选择方法从初始种群中选择最佳个体，即得到适应值高的任务一资 源对进入下一代。 ( 4 ) 根据交叉和变异概率分别进行交叉和变异操作，即重新分配任务到其它的 网格资源上。 ( 5 ) 计算经过优化后剩下的个体的适应值，适应值高的进入下一代。 ( 6 ) 判断是否满足遗传算法终止条件，满足则终止计算，得到最早完成时间和 最小时间间隔的资源，否则转步骤( 2 ) 。 4 5 本章小结 本章中首先对网格环境中的任务调度问题进行了定义及数学描述，然后设计 了一个基于遗传算法的调度方案，在该算法中，采用二进制字符串来进行染色体 编码，详细设计了适应度函数，并且可以通过调整适应度函数中参数的值来满足 网格用户和资源提供者对网格环境的不同需求，适合网格环境中的任务调度。 第五章仿真实验及分析 为了检验该调度算法的有效性和优越性，需要在不同情况下对其进行测试， 如资源的数量、用户的需求。当然，在真实的网格环境中有效地实现任务调度是 最终目标，但是就目前情况来看，使用仿真工具分析模型和算法是非常重要的。 首先，设计一个网格系统是一个非常复杂的系统工程，它需要考虑许多问题。 例如，资源广域共享带来的异构性、安全性和网络性能问题；网格中有效的资源 管理和调度也将是一个不容忽视的问题；此外，容错能力、可扩展性以及自适应 能力都是网格设计者需要考虑的内容。因此，网格系统设计者在实际部署新设计 的系统之前需要确保它能够可行并且具有所期望的执行效率。 再者，在网格环境中，由于资源和用户是分布在许多组织中，并且有自己的 规则，所以几乎不能可重复、可控制地测试某个调度算法的性能，所以结果也是 无法比较和估计的。 网格模拟器的出现，给研究者们带来了新的希望。模拟器的作用是模拟一个 网格环境，我们在这个模拟的环境中研究不同的问题，比如可行性和性能问题。 通过配置参数，可以更加真实的模拟出现实环境中的各种应用场景，使得模拟结 果更具真实性；通过分析在模拟器上试验的结果，还可以不断的改进设计。 本论文采用g r i d s i m 模拟器进行仿真实验。 5 1g r i d s i m 网格模拟器 g r i d s i m l 5 8 】由澳大利亚墨尔本大学r a j k u m a rb u y y a 领导开发，它的首要目标 是通过模拟来研究基于计算经济模型的有效资源分配方法。g r i d s i m 通过资源的 “买”和“卖”来引入“经济模型”，从而达到控制网格资源的使用的目的。 g r i d s i m 是在s i m j a v a l 5 9 j 的基础上开发的，它提供丰富的函数库以支持模拟网 格环境中的异构资源( 时间共享和空间共享) 、用户、应用程序、用户代理和调度 器。网格资源、用户和用户代理被视为不同的实体，它们通过消息事件( 输入和 输出) 来进行通信。除了通过手工编程来实现模拟外，g r i d s i m 还提供了一套图形 界面工具v i s u a lm o d e l e r ( v m ) 帮助用户配置网格环境并产生相应的代码。模拟 结束后，用户可以调用g r i d s i m 中的称为g r i d s t a t i s t i c s 的库函数来收集各种模拟 的统计数据。 5 1 1 g r i d s i m 关键特征及体系结构 g r i d s i m 工具包提供了全面的工具模拟不同种类的各异性资源，用户，资源 4 1 b m k c r ，应用程序和调度器。 圉回国国囡 图5 1g r i d s i m 平台和组件的模拟化体系 它的特色在于： ( 1 ) 可以模拟不同类型的资源； ( 2 ) 资源的操作模式包括t i m e f s h a r e d 和s p a c c s h a r e d ； ( 3 ) 可以定义资源的能力，以m i p s 或s p e c 为标准； ( 4 ) 资源可以定位于不同的时区： ( 5 ) 根据资源的当地周末和假期模拟非网格负载； ( 6 ) 可以预订资源； ( 7 ) 模拟不同并行模型的应用程序； ( 8 ) 程序也可以是各异性的，c p u 密集型或i o 密集型： ( 9 ) 一个资源上提交的作业数没有限制； ( 1 0 ) 多用户可以同时提交任务给一个资源； ( 1 1 ) 定义资源之间的网络速度； ( 1 2 ) 支持模拟动态和静态调度； ( 1 3 ) 记录所有或者选定的操作的统计数据，并用g r i d s i m 数据分析方法进 行分析。 g r i d s i m 的架构是层次化和模块化的，可以将现有的技术作为独立的元件纳入 其中。图5 1 是g r i d s i m 平台和组件的模拟化体系【6 们。 第一层，j a 、，a 接口和j a v a 虚拟机( j v m ) ，j v m 支持单个或多处理器，包括 集群。 第二层，利用第一层提供的接口，建立基本的离散事件基础结构，比较流行 的是s i m j a v a 。 第三层，包括核心网格实体模拟资源，信息服务等，应用程序模型，统 一访问接口，应用模拟原语，和建立更高层次实体的框架。主要利用第二层的离 散事件服务模拟系统实体。 第四层，模拟资源聚集，网格r e s o u r c eb m k e r 或s c h e d u l e f 。 第五层，不同情境下的资源和应用建模，利用第三层和第四层提供的服务， 评估调度，资源管理策略，算法。 5 1 2 网格核心实体的模拟 5 1 2 1网格应用程序模拟 g r i d s i m 没有明确定义应用程序模型，用户可以自由选择。每一个任务可能有 不同的处理时间和输入输出大小。g r i d s i m 的g r i d l e t 对象定义这些参数，包括用 户的需求。 g r i d l e t 包涵任务的所有信息，这些基本的参数用来决定执行时间，和在用户 和远程资源之间传输输入输出文件所需要的时间。g r i d l e t 也作为结果的返回类。 每一个u s e r 实体实例对应一个网格用户，有以下性质： ( 1 ) 作业的类型； ( 2 ) 调度优化策略； ( 3 ) 活跃度； ( 4 ) 时区： ( 5 ) 截止时间和预算；， ( 6 ) d ( d e a d l i n e ) 和b ( b u d g e t ) 因子。 5 1 2 2 网格资源模拟 g r i d s i m 可以创建各种速度的处理单元( p e ) ，一个或多个处理单元构成机器， 一台或多台机器可作为一个网格资源。因此，网格资源可以是单处理器，s m p ， 或计算机集群。单p e 或s m p ( s y m m c t r i c a lm u l t i p r o c e s s i n g ) 网格资源通常运行 t i m e s h a r e d 操作系统，多任务调度使用r o u n d m b i n 策略。而分布式存储多处理系 统运行队列系统，使用s p a c e s h a r e d 调度，即在特定的p e 上执行g r i d l e t 。调度策 略可以是f i r s t c o m e m r s t s e r 、，e d ，b a c kf i l l i n g ，s h o r t e s t - j o b f i r s t s c r v e d 等。高端的 s m p 也可以使用s p a c e s h a f e d 调度。 每个r e s o u r c e 实体实例对应一个网格资源，有以下性质： ( 1 ) 处理器个数； ( 2 ) 运行成本： ( 3 ) 运行速度： ( 4 ) 内部调度原则，t i m e s h a r c d 还是s p a c c s h a r e d ； ( 5 ) 当地负载因子； ( 6 ) 时区。 只要从网格信息服务获得资源的连接细节，b r o k e r 就可以直接查询资源的属 性。 5 1 2 3 网格资源代理的模拟 每一个用户连接一个b r o k e r 实例。用户的所有作业都提交给b r o k e r ，然后根 据用户的原则调度任务。b r o k e f 首先要从全局目录中动态获得可用资源的列表， 所有的b r o k e r 都是从自己的用户的利益出发，必须竞争有限的资源。所以，b m k e r 的调度算法要高度适应市场的供需状况。 为了模拟网格资源代理，研究者需要创建网格用户和调度系统的新实体，用 户定义的实体从g r i d s i m 的并行实体继承，具有通过事件通信的能力。具体的步骤 涉及资源和应用程序的模拟，b r o k c r 的模拟。 图5 2 是b r o k e r 的基本构架以及与其他实体之间的交互流程。b r o k e r 的主要 元件是实验接口，资源发现和交易，调度流程管理，g r j d l e t 分发器，g r i d l e t 接收 器。元件的功能及相互之间的通信如下： ( 1 ) 用户实体似建实验实例，然后通过实验接口，把描述应用程序的g r i d l c t 列表和用户的需求传递给b r o k e r ； ( 2 ) b r o k c r 资源发现和交易模块从g r i d s i mg l s 实体获得资源的联系信息， 然后与资源交互建立配置和访问代价；b r o k c r 有一个b r o k c rr e s o u r c c 列表维护资 源属性，每一项资源有一个提交执行的g r j d l e l 列表，资源的性能数据通过测量外 推法预测； ( 3 ) 调度流程管理根据用户的需求选择合适的调度算法把g r i d l e t 映射到资 源，g f i d l e t 将被加入到相应的b f o k e rr e s o u r c e 的g r i d l e t 列表中； ( 4 ) 对于每一个资源，g r i d l c t 分发器会根据资源的使用策略选择执行的 g r i d l e t 数量，避免超过资源的负载： ( 5 ) g r i d l e t 分发器使用g r i d s i m 异步服务，把g r i d l e t 提交给资源； ( 6 ) g r i d l e t 处理完成后，资源把它返回给b r o k e r 的g r j d l c t 接收模块，由接 收模块测量和更新运行时参数，帮助预测作业完成率和决定调度； 重复3 6 的步骤，直到所有的g r i d l e t 都处理完，或者b m k e r 过了极致时间 或预算限制。最后，b r o k e r 返回实验数据和处理过的g r i d l e t 给用户实体。 图5 2 网格r e s o u r c cb m k e r 系统构架及其他实体的交互 5 1 3g r i d s i m 网格环境模拟流程 模拟一个可用于分析调度算法的网格环境有四个步骤： ( 1 ) 创建各种能力和配置的网格资源，和不同需求的用户； ( 2 ) 创建大量的g r i d l c t 为应用程序建模，同时定义任务的参数； ( 3 ) 创建与我们的r e s o u r c eb r o k e r 交互的用户实体； ( 4 ) 最后，要实现一个r e s o u r c eb r o k e r 完成应用程序的调度，和资源分配。 5 1 4g rid s i m 的使用 1 安装准备 首先确认机器上是否有j 2 s d k 。可以从j a v a s u n c o m 上下载j 2 s d k 的最新版 本，安装即可。并对j a v a 环境变量进行设置。下面是在w i n d o w sx p 上的设置方 法：在控制面板一系统一高级一环境变量。双击p a t h ，加入c ：p r o g r a m f i l e s i a v a j d k 1 5 o _ 0 2 b i n ；点击“新建”，添加c l a s s p a t h 项，值如下：；c ：p r o g r a m f i i c s j a v a j d k 1 5 一0 2 、l i b ；c ：p r o g r a m f i i e s j a v 娟d k l 5 一0 2 u i b 、d t j a r ；c ：p m g r a m f i l e s j a v a j d k l 5 0 _ 0 2 l i b t o o l s j a r ；e ：g r i d s i m t o o l k i t 4 o 、j a r s 、a l l - j a r ；点击“确定”完成设置。 从网站h t t p ：、】l r w w b u y y a c o m 鲥d s i m 上下载最新版鲥d s i m t o o l k i t - 4 o 。 2 g r i d s i m 安装 把g r i d s i m t o o l k i t 4 0 的z i p 包解压缩到e 盘，点击解压后的安装文件。解压 文件夹结构如下： ( 1 ) s 彻r c e 包，这里面是g r i d s i m 的基础类的源代码，比如，资源类 ( g r i d r c s o u r c c 等) 。 ( 2 ) a p p l i c a t i o n 包，这里面主要有两个文件夹：一个是g r i d b r o k e r ，这个是 g r i d s i m 提供的一个调度算法的一个例子实现，也就是基于经济模型的调度算法； 一个v i s u a l m o d c l c r 包，这个包里面是可视化的用户配置，这个界面是和g r i d b r o k c r 调度算法配合使用的。在v i s u a l m o d e l e r 中做好配置后，会调用s o u r c e 包中相应的 类库来构建模拟试验的j a v a 代码，编译运行后会有相应的结果文件输出，然后分 析这些文件结果，得到试验数据。 ( 3 ) d o c ，文档包 ( 4 ) j 盯s ，j a r 包 ( 5 ) e x a m p l e s ，用s o u f c e 包中的类来构建的最基本的例子使用。 3 编译与运行 为了在任意目录下都可以编译运行g r i d s i m 的j a v a 程序，可以在c l a s s p a t h 加入e ：g r i d s i m t o o i k i t - 4 o a r s 、a 1 1 j a r 。 ( 1 ) 将本文中编好的源代码编译为c l a s s 文件，采用如下命令： j a v a c c l a s s p a t hg a j a v a ( 2 ) 再将编译好的c l a s s 文件拷贝到鲥d b r o k c r 包解压后的g r i 曲m k e r 文件夹 下，再打包成一个新的包。 ( 3 ) 运行仿真主程序。 5 2 仿真实验 5 2 1 实验环境 为了对调度算法进行测试，我们设计了一套测试方案。该方案在w i n d o w sx p 平台上进行，并且基于g r i d s i m 软件包。 5 2 2 实验数据的产生 2 0 0 2 年，k a s a h a r a 编译出一个标准的作业集合用来测试和比较集群中的调度 器和负载平衡算法。这个集合由s t g ( s t a n d a r dt a s kg r a p h s ) 图表示的作业组成。 它是一种特殊的d a g 图。 下面是k a s a h a m 实验室提供的具有5 0 到5 0 0 0 个任务的作业的s t g 图。 执行时间 o 9 4 3 6 4 3 3 8 9 2 1 父节点个数 o l 1 1 l 1 l l l l 3 l 第一个父节点序号第二个 第三个一 s t g 作业集的编译是用来将有n 个计算任务的一个网格作业调度到m 个处理 单元，来比较各启发式调度算法性能。在s t g 作业集提出之前，调度算法的性能 评价不是通过随机生成的任务来完成就是采用某个实际应用中的数据，但是这样 的的任务对于别的研究者来说是没有价值的，因此，在相同的条件下进行算法性 能比较是不可能的，所以k a s a h a r a 提出了s 1 g 图。 k a s a h a r a 和t b b i t a 已经获得了把d a g 图映射到具体的网格节点的最优调度范 围。通过随机选择一个作业中不同优先级和执行时问的任务画出任务图。k a s a h a r a 实验室分别提供了5 0 到5 0 0 0 个任务的d a g 图。每个d a g 图中的任务已经被映 射到2 到1 6 个节点上，并借助于高性能计算得出了每种情况下的最优调度长度。 实际上，即使在批模式下，任何一个调度也很难通过简单的计算得到最优的调度 值，因此，在s t g 任务集中的最优值被认为是实际可以达到的最好效果。 在本论文中，将采用k a s a h a r a 实验室标准任务图s t g 来进行仿真实验。并把 遗传算法得到的调度和n i m o r d g 算法得到的调度结果进行比较，从而验证本算法 性能。 86 0 o o o 1 5 o 6 o 2 9 一的一。，。m u 5 2 3 具体仿真过程 获得d a g 作业图和资源信息 上 初始化g r i d s i m 模拟器 j 采用遗传算法求解最佳调度 j i把任务映射到相应的资源上 上 l 求出会话完成时间，周转时间， i 空闲时间和截止延迟时间 图5 3 仿真过程 如图5 3 所示为本文设计的基于遗传算法的任务调度仿真过程。 首先，需要得到网格作业信息和可用的资源信息，然后初始化g r i d s i m 模拟器， 可以通过v i s u a l m o d e l c r 来方便地构建网格仿真环境，例如，可以构建拥有3 个用 户和5 个资源的网格环境。另外，还可以对用户和资源属性分别进行配置。如图 5 4 所示为用户的属性配置界面。 利用本文中设计的遗传算法求解最佳调度，当染色体适应度函数值收敛到最 高值时，该染色体代表最优调度。接着，把作业映射到相应的资源上。那么，就 可以计算出周转时间，截止时间，资源m a k e s p a n 和资源闲置时间。通过计算适应 度函数值评价个体，若收敛标准不满足，则重复后三个步骤，直到收敛到最优解。 5 2 4 遗传算子的调整 遗传算法中有两个很重要的参数：交叉算子和变异算子为了调整这两个参 数的值，我们分别进行了实验，从而选择了最适合的值。我们选择了1 0 个具有5 0 个任务的作业进行实验。初始种群为1 0 0 。分别对不同交叉、变异概率实验结果进 行比较，标准偏差为6 3 1 0 - 7 时产生下一代种群。 4 8 图5 4 用户的属性配置 对于变异概率，实验表明只有设为0 0 1 时能够收敛。如果选取比0 0 1 大的变 异概率，无论交叉概率为多大，都不可能收敛。所以本论文中把变异概率设为0 0 1 。 变异概率选为0 0 1 时，我们把交叉概率为0 7 0 8 的不同结果进行比较。 如图5 5 ，实验表明，交叉概率为o 7 4 和0 7 6 时，适应度函数值相同并且最 优。所以选取交叉概率为o 7 4 和0 7 6 均可。 7 1 3 7 1 2 7 1 1 7 l 7 0 9 7 0 8 7 0 7 7 0 6 o 70 7 20 7 40 7 60 7 80 8 交叉概率 图5 5 交叉概率比较 另外，我们将种群大小分别设在2 0 1 5 0 时进行了比较，如图5 6 所示，初始 种群大小为1 0 0 和1 5 0 时，可以达到相同的效果，即均在8 0 代收敛。 姆避通卿 图5 6 初始种群大小比较 因此，我们选择交叉概率为o 7 6 ，变异概率为o 0 l ，初始种群大小为1 0 0 进 行仿真实验。 5 3 实验结果及评价 为了检验该调度算法的优越性，需要将其与其它调度策略进行比较。n i m m d g 是r a j k u m a rb u y y a 领导开发的的基于计算经济的资源管理模型的一个实现，已经 在一些计算网格中投入使用。为了对n i m o r d g 的调度算法进行进一步的研究，他 的团队还开发了网格模拟器g r i d s i m 。而本算法是采用g r i d s i m 模拟器进行仿真验 证的。也可是说，可以通过采用本文中的调度策略与n i m m d g 算法处理同一个问 题，并且用g r i d s i m 进行仿真实验比较，从而有效的评价该算法。 5 3 1n i m r o d g 调度算法 n i m r o d g 是一个在全球计算网格中自动建模和执行参数应用程序的工具 【6 1 l 【6 2 l 它提供了一个简单的声明参数化建模语言来表示参数的实验。它基于经济学 原理使用了新颖的资源管理和调度算法。特别需要指出的是，它支持用户定义的 完成期限和代价约束来最优化调度，并使用一系列的资源交易服务来管理网格资 源的供需关系。 在n i m r o d g 网格资源管理系统中，本身的调度程序自带的代价最优和时间最 优算法均是较为成熟的算法。其中，代价最优算法是以尽可能小的成本在完成期 限内完成任务，基本思想是首先给资源按价格升序排序，对队列中的每个资源， 在不超过完成期限的范围内分配尽可能多的任务。 时间最优算法出发点是尽量快的在预算范围内完成任务，基本思想是对每个 资源考虑到以往分配的任务和完成率，估算一个任务的完成时间，再依据完成时 间对资源按升序排序，再从队列中依次取出资源，如果该任务的成本小于或等于 5 0 该任务的预算，则分配该任务给这个资源，重复以上步骤到所有任务分配完毕。 5 3 2 比较结果 将本文设计的调度算法和n i m f o d g 算法进行了比较分析，分别用1 0 个，2 0 个，3 0 个作业的任务，然后将它们分别映射到2 到8 台机器上，分别得到了两种 算法的m a k e s p a n 值。 如表5 1 所示为1 0 个作业时的比较结果，表5 2 为2 0 个作业时的比较结果， 表5 3 为3 0 个作业时的比较结果。 表5 1g a 算法与n i m r o d g 算法m a k e s p a n 值比较( 1 0 个作业) 1 0 j o b sm a c h i n em a c h i n e m a c h j n em a c h i n em a c h i n em a c h i n e m a c h i n e 2345678 n i m f o d g9 27 26 7 5 2 5 25 25 2 g a ( a v g ) 9 06 05 04 04 04 04 0 2 0 j o b sm a c h i n em a c h i n em a c h i n e m a c h i n em a c h i n e m a c h i n em a c h i n e 2345678 n i m m d g6 1 7