（计算机软件与理论专业论文）计算网格中调度算法研究.pdf

论文摘要 论文摘要 随着网络计算技术的快速发展，地理分布的各种资源可组织成网格。过去，高 性能计算一般局限于一个管理域。现在，计算网格可平衡各管理域的作业负载，改 善用户作业的执行性能，可协同运用多个管理域中的计算资源，解决一些大规模复 杂问题，因此计算网格被认为是未来高性能计算的一种主流平台。作为一种新的计 算基础设施，计算网格在体系结构、安全、资源管理与调度、编程环境等方面还未 成熟，这些方面成为最近许多计算机国际会议的讨论主题。 网格由大量的异构资源组成，具有复杂性、动态性和自治性特点高效的网格调 度算法可以充分利用网格系统资源，提高网格处理应用程序的能力。m i n - m i n 算法是 一个简单、快速、有效的调度算法，它选取每个任务的最小完成时间，再从所有最 小完成时间中选取最小的完成时间进行任务和计算资源匹配，但是由于m i n - m i n 算 法总是先分配小任务，从而不能确保负载平衡。 本文首先对网格系统中任务的数据传输和执行进行分析，计算并优化m i n - m i n 算法的任务完成时间，再根据任务需求赋予任务优先级，通过优先级安排任务调度， 提高算法负载平衡能力，最后在上述分析基础上提出c r r em i n - m i n 调度算法。 通过采用网络模拟工具g r i d s i m 对改进的m i n - m i n 算法进行数据仿真检测，结 果表明，o t em i n - m i n 算法在任务数和计算节点数较高时，性能比m i n - m i n 算法有 了较大的提高，此时一个计算节点被分配了多个任务，f i r em i n - m i n 算法将分配在 同一计算节点上任务的传输时间与执行时间重叠，从而减少任务的总完成时间。所 以对m i n - m i n 算法的改进是可行的。 关键词：网格；m i n - m i n 算法；完成时间；优先级 a b s t r a e t a b s t r a c t a l o n gw i t ht h er a p i de v o l u t i o no fn e t w o r kc o m p u t i n gt e c h n o l o g i e s ，g r i d sc a l lb e b u i l to ng e o g r a p h i c a l l yd i s t r i b u t e dr e s o u r c e s i nt h ep a s t ，h i g h - p e r f o r m a n c ec o m p u t i n gi s c o n f i n e dt oo n ea d m i n i s t r a t i o nd o m a i n n o w , c o m p u t a t i o n a lg r i d sc a l li m p r o v et h ej o b e x e c u t i o np e r f o r m a n c eb yb a l a n c i n gt h ej o bl o a d so fa d m i n i s t r a t i o nd o m a i n s ，a n ds o l v e s o m el a r g e s c a l ec o m p l i c a t e dp r o b l e m sb y c o o r d i n a t i n gc o m p u t a t i o nr e s o u r c e si n m u l t i p l ed o m a i n s s o ，c o m p u t a t i o n a lg r i d sa r ec o n s i d e r e da st h ep r e v a i l i n gp l a t f o r mf o r f u t u r eh i g h p e r f o r m a n c ec o m p u t i n g a san e wc o m p u t i n gi n f r a s t r u c t u r e ，c o m p u t a t i o n a l 鲥d sh a v en o ty e tb e e ni n v e s t i g a t e dw e l li nm a n ya s p e c t s ，i n c l u d i n g ，b u tn o tl i m i t e dt o ， a r c h i t e c t u r e ，s e c u r i t y , r e s o u r c em a n a g e m e n t a n d s c h e d u l i n g , a n dp r o g r a m m i n g e n v i r o n m e n t ，w h i c hb e c o m et h ed i s c u s s i o nt o p i c so fm a n yi n t e r n a t i o n a lc o m p u t e r - r e l a t e d c o n f e r e n c e sr e c e n t l y g r i ds y s t e mc o n s i s t so faw i d ev a r i e t yo fg e o g r a p h i c a l l yd i s t r i b u t e dr e s o u r e 圮, sa n d t h e s er e s o u r c e sa r e h e t e r o g e n e o u s ，g e o g r a p h i c a l l y d i s t r i b u t e da n d d y n a m i c a l l y a v a i l a b l e h i g hs c h e d u l i n ga l g o r i t h mw o u l db ea b l et o i n c r e a s et h t o u g h p u t ，m a x i m i z e s y s t e mu t i l i z a t i o n ，a n df u l f i l le c o n o m i c a ls y s t e ma n du s c rc o n s t r a i n t s ，m i n - r a i na l g o r i t h m i sas i m p l ea n df a s ta l g o r i t h m ，a n da b l et od e l i v e r9 0 0 dp e r f o r m a n c e ，b u t 埘t l lt h e d r a w b a c ko f l i m i t a t i o no f l o a db a l a n c e i nt h i sp a p e rt h et r a n s m i s s i o na n de x e c u t i o no fj o b sw e r ea n a l y z e df i r s t t h e nt h e c o m p l e t i o nt i m eo ft h em i n - m i na l g o r i t h mw a sc o m p u t e da n di m p r o v e db a s e do nt h e s c h e d u l em o d e l f u r t h e r m o r e ，i no r d e rt oi m p r o v et h el o a db a l a n c eo ft h em i n - m i n a l g o r i t h m ，p r i o r i t yw a sa s s i g n e dt ot h ej o b sa c c o r d i n gt od i f f e r e n ts c h e d u l el i m i t a t i o n s ， a n dj o b sw e r es c h e d u l e db a s e do nt h e s ep r i o r i t i e s f i n a l l yt h eo t em i n - m i na l g o r i t h m w a sp r o p o s e db a s e do nt h ea n a l y s i s t h r o u g ht h eu s eo f n e t w o r ks i m u l a t i o nt o o l sg r i d s i mt ot e s tt h es i m u l a t i o nd a t a w h i c hh a sb e e ni m p r o v e db yt h em i n - m i na l g o r i t h m t h er e s u l t ss h o w , w h e nt h et a s k n u m b e ra n dc o m p u t i n gn u m b e ro f n o d e sh i g h e r , t h ep e r f o r m a n c e so fm i n - m i n i m p r o v e d a l g o r i t h mh a sb e e ne n h a n c e dt h et h em i n - m i na l g o r i t h m a tt h i sp o i n t , ac o m p u t i n gn o d e a r ea s s i g n e dan u m b e ro f t a s k s m i n - m i ni m p r o v e da l g o r i t h mm a k et h et r a n s m i s s i o nt i m e a n de x e c u t i o nt i m eo v e r l a p p e dw h i c hw e r ed i s t r i b u t i o n e di nt h es a m ec o m p u t i n g n o d e s ，t h e r e b yr e d u c i n gt h et o t a lt a s kc o m p l e t i o nt i m e s ot h ei m p r o v e m e n t so f m i n - m i n a l g o r i t h ma r ef e a s i b l e k e yw o r d s ：g r i d ：m i n - r a i na l g o r i t h m ；c o m p l e t i o nt i m e ：p r i o r i t y i i 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：刍罐易日期：k 司年办日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密佤 ( 请在以上方框内打“4 ”) 论文作者签名：编日期：b 印年6 日日 名诱叫复1 妯伊产臼日 第一章绪论 1 1 引言 第一章绪论 现代计算机时代从1 9 4 5 年开始到现在，经历了半个多世纪i 从1 9 4 5 年到1 9 8 5 年， 计算机一直是庞大昂贵的设备。然而，从年代开始，两项技术进步改变了这种局面： 一是功能日益强大的微型计算机的发展；二是高速局域网的出现。这两项进步的直接 结果是；通过高速网络，将许多c p u 连接起来构成一个计算系统的做法变得可行，并 且非常容易，这种系统通常称为分布式系统分布式系统已成为计算机界中的研究热 点，j h g i l d e r 早在1 9 7 6 年就预言，下一代计算机体系结构的关键与核心必然是以分 布式结构为主的。 分布式系统的求解过程大体分为四个步骤： 任务分解：指把一个大任务划分为可并行执行的相关的子任务的过程。 任务调度：指将这些子任务分配到各个并行处理机上，并安捧处理机上子任务 的执行次序的过程 并行运算：指这些子任务在被分配的处理机上进行并行运算。 解的合成：指将子任务的运行结果合成为整个大任务的运行结果 其中任务调度这一步骤对发挥系统的并行计算能力、提高系统吞吐量具有非常重 要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力，避免有的处 理机没有可执行的任务，而有的处理机待执行的任务捧起了长队，致使总任务的执行 时间较长。 网格从广义上说是一个集成的计算和资源环境作为一个分布式计算平台，网格 能够解决科学、工程和经济中的大规模计算问题和数据密集型问题，能够实现地理上 广泛分布的高性能计算资源、信息资源、应用系统、服务系统、组织、人员等各种资 源的共享与聚合。网格为计算机和网络之间提供了标准和中间件，允许个人、研究机 构、公司和组织相互之间充分的共享资源，动态地将空闲计算资源提供给其他远端用 户。由于各种资源、管理机制、用户和应用程序间存在大规模的异构性、网格资源的 高效管理和任务的有效调度已成为网格研究的重要内容之一 1 2 研究背景 1 2 1 计算网格的起源与演变 上世纪8 0 年代中期诞生了一个思想，那就是，利用网络上的计算资源产生解决大 规模复杂问题的计算能力，这种在多个异构计算资源上构建的网络环境被称作元计算 青岛大学硕士学位论文 机。元计算机的开发包括两个阶段。第一阶段，用高性能网络将地理分布的资源互联 起来，实现一个分布式文件系统，设法让用户能访问各个计算要素，并使网络环境与 已有技术无缝结合，这些工作需要在各超级计算中心的支持下才能顺利进行。第二阶 段，将一个应用展开在多个计算机上，使异构的一组计算机协调地工作于一个单个问 题。 一些发达国家进行了元计算机的开发与实验。i w a y l l 】项目用a t m 网络互联美国北 部1 7 个地点的超级计算机、大规模存储系统、高级显示设备等建立了一个大规模、多 用途的元计算机测试床，有超过6 0 个的应用群体在这个测试床上进行高性能计算、协 同设计、远程资源与本地环境的耦合等实验德国g t b - w e s t 项目的目标是建立一个千 兆位测试床，收集高速广域计算机网络上的实验数据，实现一些需要巨大数据吞吐率 的应用，耦合各种超级计算机( 元计算) 等。文献 2 介绍了在日本、美国、英国、德 国的超级计算机上进行的元计算实验，验证了耦合不同类型计算机的可行性，以及跨 计算机运行并行应用的有效性 1 9 9 8 年的文献 3 提出建立计算网格，以满足不断增长的计算需求。计算网格被定 义为一种硬件和软件的基础设施，它提供对高端计算能力的可靠的，一致的、无处不 在的、廉价的访问。之所以称计算网格为基础设施，原因是网格汇聚了计算、数据、 传感器等资源，必然有硬件基础设施实现资源之间的互联，有软件基础设施监视和控 制整个系统。可靠的服务是用户的基本要求，即从各式各样的网格组件获得可预测的、 响应时间能忍受的服务服务的一致性是指访问接口的标准性、操作的标准性。就如 同电力网格中的标准电压、额定功率无处不在的访问是指用户无论在哪里总能获得 所需的网格服务，只要那里支持网格接入廉价的访闯是指网格的使用开销是用户普 遍可接受的。与元计算机相比，计算网格除了可进行元计算，更强调多种多样的计算， 如临时需要的高性能计算、协同计算等 计算网格是对元计算机的进一步扩展，许多原先的元计算项目转变为计算网格项 目。最初的6 1 0 b u s 项目为元计算机开发了一个低层工具包，提供基本机制的实现，如 通信、信息、资源定位与调度、认证和数据访问等，这些机制定义了一个元计算抽象 机，在抽象机上可容易地构建更高级组件，如并行编程工具、元计算应用等。9 8 年后 g l o b u s 项目成为计算网格项目，开发的工具包用于实现计算网格中的基本服务。 l e g i o n 4 l 最初是美国弗吉尼亚州立大学建立的一个校园级元计算机，远期目标是建立世 界范围的虚拟计算机，且也被称作计算网格。 如果计算网格着重数据分析与处理，则又被称作数据网格；如果计算网格着重信 息整理与挖掘，则又被称作信息网格。从用途角度，计算网格又可以是各种各样的应 用网格，如生物网格、流体计算网格和远程教育网格目前建立或在建的网格有i p g 、 a p g r i d 、e u r 0 6 r i d 、g r i p h y n 、t e r a g r i d 和c h i n a g r i d 等。 2 第一章绪论 1 2 2 计算网格的中间件 建立计算网格，就是通过系统软件( 又称中间件) 将地理分布的资源整合在一起， 使这些分布的资源可以协同解决用户的问题。与工作站群或元系统相比，网格中的资 源异构、资源动态性、资源跨管理域、资源扩展、资源互连方式、网格应用等变得更 为复杂，因而网格系统软件比较复杂目前，中间件的许多方面仍处于研究阶段，包 括体系结构、安全、作业调度与资源管理、应用编程环境等。 从体系结构上，网格中间件的实现方案可分为两类，即逐层抽象和模块互动，逐 层抽象方案得到较多的认可。逐层抽象方案是从面向计算仿真的网格提出的，文献【5 】 参照i n t e r n e t 协议栈把网格系统软件的体系结构分为构造( f a b r i c ) 层、连接 ( c o n n e c t i v i t y ) 层、资源( r e s o u r c e ) 层、聚合( c o l l e c t i v e ) 层和应用( a p p f i c a t i o n ) 层构造层封装异构的资源，连接层实现简便安全的数据通信，资源层实现单个资源 的网格共享，聚合层实现协同运用多个资源，应用层包含了在一个虚拟组织中操作的 用户应用。在逐层抽象方案中，找出最少的公用服务有时是困难的，某些复杂的服务 既会用到。下层”服务，也会用到。同层”或“上层”的服务。模块互动方案中允许 任两个服务之闻的访问，对于任一个服务而言，其他所有服务都是可用的，如网格应 用可直接访问到系统或硬件特有的函数 w e b 服务可用于封装中间件中的各种服务，这是目前被广泛接受的中间件实现技 术w e b 服务擅长于处理商务，而电子科学( c - s c i e n c e ) 和电子商务( e - b u s i n e s s ) 侧 重于不同的处理，故全球网格论坛( g g f ) 讨论并公布了开放的网格服务体系结构 ( o g s a ) 和开放的网格服务基础设施( o g s i ) 。符合o g s a o g s i 的网格系统软件已 经出现，如g 乃。 1 2 3 计算网格的作业类型 在网格研究的早期，根据元计算实验曾提出过五种网格运用模式1 6 1 ，分别是分布式 超级计算、高吞吐率计算、临时需要的高性能计算、数据密集的计算和协同计算。无 论网格采用哪种运用模式，一个网格作业的运行或者局限于一个管理域，或者跨越多 个管理域。一个管理域就是一个调度系统负责管理的资源区域，通常是一个计算系统， 如f l c 、机群或肝p 系统因此，网格作业可分为单系统和多系统两类l ” 定义1 1 单系统作业 如果用户提交的作业被完整指派到某一个计算系统，即运行局限于一个计算系统， 则该作业称作单系统作业。 定义1 2 多系统作业 如果用户提交的作业被划分成若干子作业，子作业分布于多个计算系统，即作业 青岛大学硕士学位论文 是在多个计算系统上运行的，则该作业称作多系统作业 正如文献【8 】介绍的，网格透明地实现了分布资源的共享，实现了两个目的，一是 运行那些计算需求超过本地资源的大规模应用，即多系统作业，二是通过平衡各计算 系统的运转负荷，达到缩短作业响应时间的目的，即改善单系统作业的执行性能。 过去的很多并行程序都是在一个高端计算系统上执行的，如果把这些程序提交到 网格，则会被当作单系统作业发送到适合的计算系统。解决一些大规模复杂问题，如 飞行器整体仿真、生物领域的参数研究，需要大量的计算资源，这样的大规模网格应 用属于多系统作业 根据多系统作业是否需要计算系统问的数据传输，多系统作业还可分为两个子类， 即蒙特卡洛作业和分布式作业。 定义1 3 蒙特卡洛作业 如果不需要计算系统间的数据传输，或者需要的数据传输开销可以忽略，则多系 统作业的编程一般基于蒙特卡洛方法，这类多系统作业称作蒙特卡洛作业 蒙特卡洛方法是一种通过计算众多采样点处的目标函数以发现分布规律的方法， 因在摩纳哥的蒙特卡洛提出而得名。 定义1 a 分布式作业 如果需要计算系统间频繁的数据传输，则多系统作业的编程方法与传统的分布式 作业类似，这种多系统作业仍称作分布式作业。 在计算网格中，分布式作业可通过动态组合分布的多个单系统作业产生 2 4 计算网格的作业调度 在网格全球论坛( g l o b a lg r i df o r u m ) 公布的草案中，低级调度实例实现计算系统 的本地调度。高级调度实例实现网格中的协同调度。通常，高级调度实例又称网格调 度器，低级调度实例又称本地调度器。网格调度器一般不直接控制计算系统中的资源， 而是根据网格作业的资源分配请求，为作业选择一个或一组计算系统，然后将分解后 的资源分配请求发送给这些计算系统上的本地调度器，由本地调度器完成最终的资源 分配。 可见，网格调度器完成网格层次的调度，本地调度器完成本地层次的调度，网格 层次的调度主要完成作业到资源的映射，本地层次的调度主要完成作业的资源分配与 运行网格中的作业调度分网格层次调度和本地层次调度两个阶段进行，在逐层抽象 的中间件中，网格层次调度位于聚合层。 在加入网格后，计算系统通常保留自己的本地调度器，只是增加本地调度器与网 格调度器的访问接口因此，建立计算网格中的作业调度系统，主要是设置( 若干个) 网格调度器，建立网格调度器之间、网格调度器与本地调度器之间的联系，并在网格 4 第一章绪论 调度器上实现网格层次的一些调度方法。计算网格中的作业调度主要指网格层次的调 度。论文中，如不特别声明，作业调度均指网格层次的调度。 网格作业是否可模压( 即并行度可变) 、是否指定完成期限、是否需要资源预留， 本地调度器是否支持c p u 排他式分配、是否支持作业动态迁移，这些因素导致作业调 度的多样性。 如果作业的计算系统选择只进行一次，在被发送到计算系统后作业不再迁移到其 他计算系统，则这种作业调度称作静态调度。如果在运行前，作业仍可迁移到其他计 算系统，则这种作业调度称作动态调度 如果在选择计算系统时，不过分考虑作业的详细特征，以提高平均的作业执行性 能为目标，则这种作业调度称作网格系统级调度经验表明，一种网格系统级调度不 可能使所有类型作业的调度取得最优性能。如果作业调度是在仔细分析作业和网格的 性能模型基础上完成的，并以优化该类型作业的执行性能为目标，则这种作业调度称 作网格应用级调度。 每当网格调度器收到一个用户提交的作业，立即为之选择适合的计算系统，并 承 作业发送到该计算系统，这种作业调度称作在线调度每当网格调度器收到一个作业， 检查是否凑够一批作业，当凑够一批作业时，才为这些作业确定各自适合的计算系统， 这种作业调度称作批调度。 如果仅在一部分计算系统中优化作业的计算系统选择，则这种作业调度称作网格 局部调度。如果在所有计算系统中优化作业的计算系统选择，则这种作业调度称作两 格全局调度。 不同类型的作业调度适用于不同的场合网格局部调度、计算系统作业负载的动 态变化等因素会使静态调度的性能不够理想，而动态调度可使作业动态迁移到更适合 的计算系统，削弱这些因素对调度性能的负面影响批调度可取得比在线调度更好的 网格系统性能，如c p u 利用率，但要求用户对作业完成期限的要求不能苛刻。如果完 成期限临近或要求尽可能短的响应时闻，则应采用在线调度。单系统作业一般采用网 格系统级调度，而多系统作业常采用网格应用级调度 1 3 计算网格作业调度的研究现状 管理域可以是低端计算系统( p c 或工作站) ，也可以是高端计算系统( 如工作站 群) 。对于各管理域均为高端计算系统的计算网格( 如图1 1 ) ，在调度框架、调度方法， 性能尺度和实验环境等方面的研究存在多样性。下文中，如不特别声明，计算系统均 指高端计算系统 青岛大学硕士学位论文 圈1 1 各管理域均为高端计算系统的计算网格 ，3 1 调度框架的多样性 定义1 5 作业调度框架 网格中可以存在多个网格调度器和多个计算系统，网格调度器之闻的作业迁移关 系以及网格调度器与计算系统本地调度器之间的资源分配关系构成作业调度框架。 这里，“作业迁移关系”是指彼此可接收来自对方的作业的关系，“资源分配关系” 是指本地调度器允许为网格调度器分配处理机资源，以运行来自网格调度器的作业。 对于任意两个网格调度器g s i 和g 鸯，若g 鸯的作业可迁移到g $ 1 ，且g s i 的作业可迁移 到c s j ，则称g 两和g 两之间有作业迁移关系。对于任意的网格调度器g & 和本地调度 器l s ，g s i 请求l s 分配处理机资源，以运行6 发来的作业，这种行为称作6 鸯请求 l s j 分配资源。如果6 磷和工西位于不同的计算系统，则g s i 请求l s j 完成的是远程资源 分配；如果位于同一个计算系统，则请求完成的是本地资源分配。若工两允许为g s l 分 配资源，则称蕊和i 西之间有资源分配关系。作业迁移关系隐含着双方建立了安全信 任关系、作业迁移机制等，但这种关系或机制对于资源分配关系而言往往只是单向的， 即本地调度器信任网格调度器，可接收网格调度器发来的作业。 从可扩展性和健壮性角度，作业调度框架可分为全局式、层次式和无中心式三类。 定义1 全局式调度框架 6 第一章绪论 如果每个网格调度器与所有计算系统的本地调度器建立了资源分配关系，这种作 业调度框架称作全局式调度框架。 ， 文献【8 】【9 1 2 】【1 3 】中采用全局式调度框架，如图1 2 0 0 o g 长网格调度嚣l s ：本地调度器彳：计算系统，作业 实线箭头；提交作业虚线箭头；发送作业虚线：资源分配 圈1 2 全局式调度框架 文献【1 1 】f 1 2 】假设网格中只有一个网格调度器，如图1 2 a ，文献【9 】假设网格中有多 个网格调度器，如图1 2 b 。文献【8 】【1 0 1 中，每个计算系统上部署一个网格调度器，如 图1 2 c 。在全局式调度框架中，各网格调度器的功能是一样的，都可接收用户作业， 并完成指派。网格调度器越多，全局式调度框架的健壮性越强。 全局式调度框架方便了网格调度器在所有计算系统中为作业选择适合的计算系 7 束：回 青岛大学硕士学位论文 统。另一方面，网格调度器为作业优化计算系统选择的开销与计算系统总数成正比， 当计算系统总数很大时，网格调度器的工作开销就很大，故应限制一个网格调度器可 整合计算系统的数目。可见，全局式调度框架的可扩展性较差，只适用规模不大的网 格。 定义1 7 层次式调度框架 如果计算系统表示为结点，计算系统的相邻关系表示为边，这样获得的图是一棵 树，则这种作业调度框架称作层次式调度框架。 当增加一个计算系统时，只需建立与若干计算系统的相邻关系，其它计算系统的 网格配置不必修改，故层次式调度框架有较好的可扩展性。但中间结点发生故障时， 树就会分裂，故层次式调度框架不够健壮。文献【1 4 】采用层次式调度框架，如图1 3 ， 并规定每个结点的计算能力不小于子结点，这方便了网格调度器为作业寻找适合的计 算系统，但对框架扩展增加了约束。文献【1 5 睬用了另一种层次式调度框架，它的非叶 子结点代表网格调度器，叶子结点代表计算系统 g s ：网格调度器岱：本地调度嚣 ：计算系统j 作业 实线箭头：提交作业虚线箭头；发送作业虚线：计算系统相邻 圈1 3 层次式调度框架 定义1 8 无中心式调度框架 如果计算系统表示为顶点，计算系统相邻关系表示为边，这样获得的图是一个非 完全图，则这种作业调度框架称作无中心式调度框架。 文献【1 6 】f 1 7 l 采用无中心式调度框架，如图1 4 8 第一章绪论 g s ：同格调度器z 5 ；本地调度嚣一：计算系统，作业 实线箭头：提交作业虚线箭头：发送作业虚线：计算系统相邻 图1 4 无中心式调度框架 在无中心式调度框架下，即使一个计算系统或网格调度器失败，计算系统之闻的 多条路径使调度框架仍不致于分裂，故无中心式调度框架有很好的健壮性另一方面， 一个计算系统与哪些计算系统相邻通常是任意的，这使无中心式调度框架有很好的可 扩展性。 1 3 2 作业调度方法和衡量尺度的多样性 调度框架在一定程度上决定了调度方法。如果每个网格调度器与所有本地调度器 建立了资源分配关系，则便于实现网格全局调度；反之，实现网格全局调度的策略比 较复杂对于不同类型的作业，往往需要采用不同的作业调度方法，衡量作业调度的 尺度也会不同。 文献【1 3 】采用全局式调度框架，各计算系统的处理机数目可以不等，但处理机性能 必须相等，处理机间的网络性能也必须相等，即单系统作业在各计算系统上的运行时 间是相等的。宽作业( 即并行度大于一个计算系统的处理机数量) 将被批开，分布在 多个计算系统执行，宽作业属于本论文中的多系统作业。模拟实验中，本地调度策略 9 青岛大学硕士学位论文 采用进取式装填法，用宽度加权的平均减慢率评估调度性能。文献 1 3 1 的缺点在于要求 各计算系统的并行计算能力必须相等，以及用宽度加权的减慢率反映作业的调度优先 级。 文献【1 0 】采用全局式调度框架，各计算系统有同样的并行计算能力，都采用进取式 装填法维护本地作业队列针对单系统作业提出一种多请求法，实现动态调度。当一 个网格调度器收到用户提交的作业时，将作业请求发送给每个本地调度器，每个作业 在各计算系统的作业队列中都有一个请求。当一个计算系统即将为一个作业请求分配 资源时，向其它计算系统发送消息，通知它们在各自作业队列中删除该作业的请求。 多请求法可使作业等待时间最短，但未必使作业响应时间最短，因为实际网格中计算 系统的并行计算能力往往不同，作业在不同计算系统的运行时间也会不同，等待时间 最短不一定意味着响应时间最短。采用多请求法时，各计算系统本地调度的开销过大， 因为每个计算系统的作业队列长度是单请求时的一倍，露是网格中等待运行的作业总 数。文献 1 0 1 用平均减慢率衡量作业调度的性能也是不妥的，因为实际网格中作业响应 时问和减慢率的变化不总是一致，即响应时间变短，减慢率不一定变小 文献 1 2 1 采用全局式调度框架结构，各计算系统的总计算能力相等，即处理机性能 与处理机数目的乘积相等。每个计算系统采用基于先来先服务( f c f s ) 的处理机空间 划分方法维护本地作业队列。针对单系统作业采用批调度，用遗传算法优化每个计算 系统上分配哪些作业，以及那些作业进入本地作业队列的次序，用作业运行时间跨度 衡量批调度的性能。文献 1 2 1 的缺点是对各计算系统总计算能力和本地调度策略的限 制，调度性能依赖作业运行时间的精确估计，运行时间的估计误差对调度的影响尚不 清楚。 文献【8 1 采用图1 2 c 所示的全局式调度框架，每个计算系统包含多个c p u ，本地调 度采用c p u 空间划分方法。作业可提交到任一个网格调度器，网格调度器立即请求本 地调度器预测作业的等待时间，若等待时闻小于某个设置的门槛值，作业被直接发送 给本地调度器( 且不再迁移到其他计算系统) ，否则放入网格调度器维护的作业队列中。 提出了发送者发起、接收者发起和对称发起等三种算法，实现网格调度器之问交换计 算系统的利用率、作业响应时间等信息，用于决定是将作业发给本地调度器，还是发 给其他某个网格调度器文献【8 】研究单系统作业在计算网格中的调度问题，通过比较 计算系统之间的作业响应时间和资源利用率，优化作业的计算系统选择，衡量调度的 尺度是平均响应时间、平均等待时间等 文献 1 4 1 采用层次式调度框架，每个网格调度器用在线或批调度实现网格局部的负 载平衡，网格调度器之间采用服务广告和发现机制来平衡彼此的工作量，从而间接实 现网格全局的负载平衡。实验表明，负载平衡可以缩短作业的响应时问，提高网格资 源的利用率。这里的调度方法针对单系统作业，属静态调度，因为每个作业在指派后 第一章绪论 不能再迁移。此外，没有分析作业提交点分布( 即作业提交到各网格调度器的概率分 布) 对实现网格全局负载平衡的影响。 文献【1 6 】采用无中心式调度框架，每个计算系统称作网格结点，每个网格结点可有 任意数目的处理枫，可采用任意的调度方法。每个网格结点可接收用户提交的作业， 并知道和相邻网格结点的网络性能。每个网格结点维护两个队列，即外部队列和内部 队列提交来的作业先被放入本结点上的外部队列，然后根据结点间的网络性能和结 点上作业队列的状态，在附近结点中选择负载最轻的一个，将外部队列中最前面的一 个作业发送过去，后者将该作业放入内部队列。结点上作业队列的某个长度是触发网 格局部负载平衡的门槛，网格全局的负载平衡是间接实现的文献【1 6 】针对单系统作业， 没有考虑作业提交点分布，作业调度属于静态，因为内部队列中的作业不再迁移 文献【1 8 1 用非完全图表示计算系统间的网络拓扑，分别研究数据并行流水线和一般 分布式应用的调度问题，这两类应用都属于本论文中的分布式作业提出的调度方法 属于面向应用的静态调度，计算系统既可以是高端系统，也可以是低端系统( p c 或工 作站) 文献f 1 9 1 采用全局式调度框架，计算系统可以是低端系统，也可以是高端系统。 提出针对参数实验应用的一个自适应调度算法，以减小应用运行时间的跨度，参数实 验应用属于本论文中的蒙特卡洛作业文献【1 8 】【1 9 】中的资源要求与本论文的网格资源 要求不符，更主要的缺陷是假设应用独占网格，而实际上网格是多作业的共享平台， 网格负载失衡对分布式作业和蒙特卡洛作业的影响也没有考虑 1 3 3 实验环境的多样性 网格实验可以在三种环境下进行，即测试床、仿真环境和模拟系统。在测试床上 可以获得真实可信的实验结果，但测试床的配置比较固定，难以进行各种配置下的网 格实验；另外，网格环境的动态性使测试床上无法进行可控制、可重复的实验在网 格仿真环境中，实验结果比较精确，但仿真环境的建立比较复杂。模拟网格( 调度) 的系统一般是基于离散事件设计的，支持可控制、可重复、可省时的网格实验，而且 模拟系统的实现比较简单 s i m g r i d 是一个工具包，提供了一些核心功能，用于建立基于离散事件的调度模拟 器，通常这种调度模拟器只针对一个网格应用，无法用于网格系统级调度的测试。b r i c k s 是一个基于离散事件的模拟系统，按组件结构设计在b r i c k s 中，网格是一个多客户 多服务器架构，计算系统为服务器，用户机器为客户，互连客户和服务器的是广域网 客户发出任务请求，这些请求在调度算法的安摔下在一个或一些服务器上完成b r i c k s 是一个可配置的网格实验平台，用户可规定b r i c k s 系统中的网络拓扑、服务器体系结 构、通信模型和调度框架，但目前的任务模型只针对串行程序，服务器模型只针对低 端计算系统，故b r i c k s 难以用于本论文的研究工作。g f i d s i m 是个基于j a v a 的离散 l l 青岛大学硕士学位论文 事件网格模拟工具包，用面向对象编程实现，针对全局式调度框架，无法模拟无中心 式调度框架下的作业调度。 文献【8 】f l o 】f 1 3 】用并行计算机真实的运转负荷作为提交到网格调度器的作业流，通 过软件模拟作业调度的过程及结果，但都未阐述模拟软件的框架和设计原理。文献1 1 2 】 为评估基于遗传算法的网格作业调度设计了一个模拟软件，但不清楚能否用于评估其 它调度方法。值得注意的是，文献 8 1 1 1 0 1 2 1 1 1 3 q b 的调度模拟软件都是用于全局式调 度框架。 1 4 网格调度常用算法简介 在动态、复杂的网格系统中，资源的失效非常频繁，网格资源的失效会导致在该 节点上执行的计算任务无法正常完成，从而影响计算网格的服务质量和效率。好的调 度算法可以有效的解决这些问题。 网格调度目前多采用启发式调度算法。m i n 咖i n 算法选取每个任务的最小完成时 间，再从所有最小完成时间中选取最小的完成时间进行任务和计算资源匹配。m a x l i n 算法在得到每个任务的最小完成时间后，选取最大的完成时间进行任务和计算资源匹 配。s u f f r a g e 算法计算每个任务的最小完成时间和次小完成时间的差值，选取所有任 务中差值最小的任务和计算资源。s a 算法将传统的模拟退火算法应用到网格调度中， 采用迭代技术得到一个可能被接受的任务资源匹配对。a p p l e s 基予有效的协同数据定 位和适应性调度提出x s u f f r a g e 算法。n i m r o d 基于经济预算网格模型，提出根据运行 时间限制和经济预算限制的调度算法。n i m r o d 基于经济预算网格模型，提出根据运行 时间限制和经济预算限制的调度算法。这些算法基于不同调度模型、从不同角度研究 了调度问题。在众多算法中，m i n - - m i n 算法是一个简单、快速、有效的算法，但由于该 算法总是先分配小任务而不能确保负载平衡针对m i n - - m i n 算法的缺陷，s e g m e n t e s m i n - - m i n 将所有任务根据其预期完成时问分为n 段，从完成时间最长的任务所在段开始 按照m i n - - m i n 算法调度。q o sg u i d e dm i n - m i n 在调度过程中考虑了任务对计算节点数 据处理能力的需求，对需要高数据传输能力计算节点的任务先进行调度。上述文献虽 然从某一角度改进了m i n - - m i n 算法，但都没有对任务完成时问的计算进行深入分析， 且没能全面考虑任务自身对调度的影响。 1 5 论文的研究内容及创额点 基于这一事实，本文提出一种o t em i n - - 恤i n 算法。该算法首先根据网格系统中与 任务匹配的计算节点上没有存储所需的数据，需要进行数据传输的特点，将任务的执 行分为数据传输和计算两个部分，通过对m i n - m i n 调度算法的任务完成时间进行计算 1 2 第一章绪论 和优化，达到降低任务完成时间、提高网格系统的任务吞吐率的目的。继而，算法采 用优先级反映任务需求对调度的影响，将任务按照优先级划分为多个子集合，对各子 集合中的任务按照优化完成时间的m i n - m i n 算法进行调度，达到提高算法负载平衡能 力的目的。 青岛大学硕士学位论文 第二章分布式系统及其任务调度问题 2 1 分布式系统概述 分布式系统是二十世纪九十年代以来计算机领域的研究热点之一作为网络一 体化和并行处理分布化的产物，分布式系统解决了系统透明性及处理机动态分配等 问题，表现出了强大的生命力。 随着i n t e r n e t 的迅猛发展，传统的信息系统概念发生了巨大的变化，突出表现 在信息的存储、传递、发布以及获取方式所发生的革命性交革。基于互联网的分布 式信息系统在各个领域得到广泛的应用，在整个社会生活中发挥着日益突出的作用。 i n t e r n e t 已经越来越多地成为构建信息系统的一个关键组成部分。如何在更为 广域和异构的计算环境中有效地发布和获取信息，已成为急待解决的问题，分布式 系统很好的解决了上述问题。 一个被大家公认的分布式系统的定义是：。分布式系统是一些独立的计算机的集 合，但在用户看来却是一台计算机”例 在硬件结构上，尽管所有的分布式系统都是由多个c p u 构成的，但可以用不同 的方法将硬件组织起来，形成不同的系统。按照体系结构划分，当前典型的分布式 系统可分为两种；共享存储多处理机，分布存储多计算机如果结点间通过公用存 储器中的共享变量实现相互通信，就称为多处理机( m u l t i p r o c e s s o r s ) ；如果结点 间使用消息传递方式来实现相互通信，就称为多计算机( m u l t i c o m p u t e r s ) 1 2 1 1 共享存储多处理机属于紧密耦合的分成式系统，采用共享主存通信一个典型 的共享存储多处理机系统由m 个存储模块、p 个处理器和d 个i o 通道组成，( 珥p ，d ) 的数目按情况而定由于处理机与主存之间互连网络带宽有限，所以当处理机数增 多时，访问主存的冲突概率会加大，互连网络会成为系统性能的瓶颈。但由于是单 一地址空间，所以较易于编程 分布存储多计算机属于松散耦合的分布式系统，它的每个处理单元都是一个独 立性较强的节点，系由c p u 、本地存储器、i o 设备和消息传递通信接口所组成。由 于每个计算节点的本地存储器容量较大，所以运算时所需的绝大部分指令和数据均 可取自本地存储器。当不同计算节点上的进程需要通信时，就可通过接口进行消息 交换在有的松散耦合的多计算机系统中，其计算节点本身就是一台完整的计算机， 这样就演变成了现代的机群系统。这种松散性耦合结构易于扩展，但多地址空间却 使编程较困难。 分布式系统与集中式系统相比，有其自身的优点分布式系统有较高的性能价 格比，它还可能具有任何价位上的大型机都无法达到的性能随着计算机的发展， 1 4 第二章分布式系统及其任务调度问题 其应用领域越来越广，其中许多应用本身就是分布式的