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

摘要 “网格”是一个新出现的概念，代表了一种先进的技术和基础设施，是继i n t e r a c t 之后又一次重大的科技进步。网格是以资源共享为目的，支持对可计算资源的远程和 并发的访问，用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统 镜像的高性能计算和信息服务环境。由于网格所具有的广域性、动态性、异构性的特 点，如何对任务进行调度以满足用户的需求是一个极具挑战性的问题。 本文介绍了网格的概念，特点和研究现状，随后介绍了网格的体系结构，分别描 述了当前比较流行的五层沙漏结构和开放网格服务体系结构o g s a 。研究了任务调度及 几种任务调度算法，如m i n m i n ，m a x m i n ，遗传算法g a ，蚂蚁算法a a ，基于a g e n t 的任务调度，基于任务池的任务调度算法等，从而设计出了一种新的任务调度算法 io a db a n d w i d t h a l g o r i t h m ，它主要考虑了两个因素：一个是负载平衡，主要是根 据负载平衡情况轮回应用m a x - r a i n 和m i n - m i n 算法，实现了整个任务调度算法的负载均 衡；另一个因素是服务质量q o s ( 本文我们主要考虑网络带宽) ，它解决了低q o s 要求的 任务占用提供高q o s 的资源，而高q o s 要求的任务却只能等待，同时提供低q o s 的资源 却处于空闲的问题，从而提高了系统的资源利用率。最后，利用o p t o r s i m n 格模拟器对 所设计的算法进行模拟，根据模拟结果得出l o a db a n d w i d t h a l g o r i t h m 调度算法是优化 计算和存储资源利用率，降低作业执行时间的最佳选择。 关键词：网格，任务调度，负载平衡，网络带宽 a b s t r a c t g r i di san e wc o n c e p t ，ad e p u t yt oaa d v a n c e dt e c h n o l o g ya n dai n f r a s t r u c t u r e ，ag r e a t a d v a n c eo f t e c h n o l o g ya f t e ri n t e m e t t h eg o a lo f ag r i di st os h a r er e s o m c e $ ，s u p p o r tr e m o t e a n dp a r a l l e la c c e s s e st oc o m p u t i n gr e s o u r c e s ，g r i di sh i g hp e r f o r m a n c ec o m p u t i n ga n d i n f o r m a t i o ns e r v i c ee n v i r o n m e n t so fas i n g l es y s t e mi m a g et h a ti sc o n s i s t e db yn e t w o r k c o n n e c t i o n sa n dg e o g r a p h i c a l l yd i s t r i b u t e dc o m p u t i n gr e s o u r c e s b e c a u s et h er e s o u r c e si n g r i da r ed i s t r i b u t e d ，h e t e r o g e n e o u sa n dd y n a m i c ，h o wt os c h e d u l et a s k si ng r i dt om e e t u s e r s r e q u i r e m e n t si sac h a l l e n g i n gp r o b l e m i nt h i s p a p e r , c o n c e p t i o n , c h a r a c t e r i s t i ca n di n v e s t i g a t i o na c t u a l i t y o fg r i da r e i n t r o d u c e d , a n dg r i ds y s t e ms t r u c t u r eo fg r i ds u c ha st h ef i v e - l e v e ls a n d g l a s sa r c h i t e c t u r e a n dt h eo p e ng r i ds e r v i c e sa r c h i t e c t u r ei sa l s oi n t r o d u c e d an e wt a s ks c h e d u l i n g a l g o r i t h m l o a d _ b a n d w i d t ha l g o r i t h mi ss c h e m e do u ta f t e rr e s e a r c ho ft a s ks c h e d u l i n g a n ds o m et a s ks c h e d u l i n ga l g o r i t h ms u c ha sm i l l - m i n , m a x - m i n , g a , a 九t a s kp o o lc t c l o a db a n d w i d t ha l g o r i t h mc o n s i d e rt w of a c t o r s m a x m ma n dm i i l - r a i na l g o r i t h ma r e a d o p t e da l t e r n a t e l ya c c o r d i n gt o 1 0 a db a l a n c i n g s o1 0 a db a l a n c i n go ft h i st a s ks c h e d u l i n g a l g o r i t h mi si m p l e m e n t e d t h eo t h e ro n ei sq o s ，w ec o n s i d e rm a i n l yn e t w o r kb a n d w i d t hi n t h i sp a p e r t h ea b o v et h o u g h ts o l v e st h a th i g hq o sr e s o u r c e sa r eo c c u p i e db yl o wq o st a s k s ， b u th i g hq o st a s k sw a i ta n dl o wq o sr e s o u r c e sa r ef r e e ，s ou t i l i z a t i o no fs y s t e mr e s o u r c e si s e n h a n c e d f i n a l l y , w ei l s eg r i ds i m u l a t o ro p t o r s i mt ot e s tt h i sn e w t a s ks c h e d u l i n ga l g o r i t h m i nt h i sp a p e r , t h ee x p e r i m e n t ss h o wt h a tl o a d b a n d w i d t ha l g o r i t h mi sab e t t e rc h o i c et o o p t i m i z ec o m p u t a t i o na n ds t o r a g er e s o u r c eu t i l i z a t i o n ，d e p r e s sm e a nj o bt i m e k e yw o r d s ：鲥d ，t a s ks c h e d u l i n g ，l o a db a l a n c i n g ，n e t w o r kb a n d w i d t h 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 4 7 论文作者签名：灵丽碉f 日期：冽年；月3 0 n 1 1 研究背景 第一章绪论 当前随着人们对信息需求的不断拓展，所遇到的问题也越来越复杂，而且规模越 来越大，解决这些问题所需要的计算能力也在大幅度提高。“网格”是一个新出现的概 念，代表了一种先进的技术和基础设施，是继i n t e m e t 之后又一次重大的科技进步。 任务调度和负载均衡是网格计算环境中影响系统性能的重要问题。由于网格资源 通常是位于不同的地理位置，由不同的组织管理，加之系统可能发生故障，所以在大 型网格环境中任务调度和负载均衡是一个非常复杂的问题。 网格环境中组织大规模分布并行计算存在相当大的难度，这种难度来自网格环境 的通信传输延迟大、通信带宽和服务质量不确定、计算平台异构性、资源节点高度自 治等特性，这些特性制约了网格计算的性能。 因此，为了提高网格计算的性能，除提高网格硬件设施的性能外，通过改进任务 调度策略提高网格计算资源利用率和任务吞吐率，这是一个既经济、又有效的方法。 1 1 1 网格简介 网格是一个计算与资源的环境，或者说是一个计算资源池。网格能够充分吸纳各 种计算资源，并将他们转化成一种随处可得的、可靠的、标准的同时还是经济的计算 能力。除了各种类型的计算机，这里的计算资源还包括网络通信能力、数据资料、仪 器设备，甚至是人等各种相关的资源，基于网格的问题求解就是网格计算。 这里网格和网格计算是广义的定义，狭义网格定义中的网格资源主要是指分布的 计算机资源，而网格就是指将分布的计算机组织起来协同解决复杂的科学计算问题。 广义的网格一般就被称为计算网格( c o m p u t i n gg r i d ) ，即主要解决科学与工程计算问 题的网格。 基于求解问题的特点，人们又提出了多种名称的网格，比如以数据密集型问题的 处理为核心数据网格，以解决科学问题为核心的科学网科2 1 ，以全球地球系统模型问 题求解为主要目的的地球系统网格3 1 等等。此外还有地震网科4 】、军事网格【5 】，n a s a ( n a t i o n a la e r o n a u t i c sa n ds p a c ea d m i n i s t r a t i o n ) 的i p g t 6 】等行业网格。 1 网格的起源 “网格”( g r i d ) 一词来源【刀于人们熟悉的电力网( p o w e r g r i d ) 。目前对计算力的 需求正在持续不断地增长。高速网络、功能和性能更加强大的大规模计算系统、高性 能存储系统以及高级数据分析软件的应用为解决商业领域和科学领域的计算问题带来 了希望。但是利用这些新的能力意味着应付不断增加的工作负荷要求所带来的空前挑 战。当一个组织机构在努力保持竞争力的时候他们面临许多前所未有的挑战：减少计 算费用、增加计算吞吐量、加快对市场的响应、改进生产服务质量和产品创新等都是 非常重要的。一个组织机构在硬件方面的投资需要谨慎地进行权衡，并且必须找到利 用可得资源完成更多工作的方法。 尽管对计算力的需求是非常大的，但是许多现有的系统都没有得到充分利用。其 中一些单个服务器也许满负荷工作，但是大多数系统却不是满负荷工作的，使许多计 算周期( c o m p u t i n g c y c l e s ) 没有使用，而实际上这些计算周期可以用于满足不断增长 的计算资源需求。网格计算使组织机构可以更加有效地和灵活地用他们的分布式计算 资源，从现有的系统中获取更加有用的计算力，帮助组织机构获得竞争优势。 2 网格的特点 网格是一个集成的计算与资源环境，它能够吸纳各种包括计算机、网络、数据资 料、仪器设备等在内的计算资源，并将它们转化成为一种随处可得的、可靠的、标准 的同时还是经济的计算能力，它具有一些区别于其他计算系统的特性，下面将从几个 方面来论述1 8 j 。 ( 1 ) 分布与共享 分布性是网格的一个最主要的特点。网格的分布性首先是指网格的资源是分布的。 组成网格的计算能力不同的计算机，各种类型的数据库乃至电子图书馆，以及其他的 各种设备与资源，是分布在地理位置不同的多个地方，而不是集中在一起的。这些资 源的类型复杂，规模较大，跨越的地理范围较广。这就决定了网格的计算一定是分布 式计算而不是集中式计算。在网格这一分布式环境下，需要解决资源与任务的分配和 调度问题，安全传输与通信问题，实时性保障问题，人与系统以及人与人之间的交互 问题等等。 网格资源虽然是分布的，但它们却是可以充分共享的。共享是网格的目的，没有 共享便没有网格。解决分布资源的共享问题，是网格的核心内容。 分布是网格硬件在物理上的特征，而共享是在网格软件支持下实现的逻辑上的特 征，这两者对网格来说都是十分重要的。 ( 2 ) 自相似性 网格的整体和局部之间存在着一定的相似性，局部往往在许多地方具有全局的某 些特征，而全局的特征在局部也有一定的体现。 可以认为国家级网格是在省一级的网格基础上建造起来的，国家级主干网要有更 大的带宽，只有这样才能把不同省份的子网格连接起来提供满意的通信服务，国家级 和省级网格都会有各自的计算中心，只不过在计算能力上有差异而己，他们也都需要 有管理节点，只不过国家级的管理节点功能更多更强大而已。 ( 3 ) 动念性与多样性 2 网格并不是一成不变的。原来捌有的资源或者功能，在下一时刻就可能出现故障 或不可用，而原来没有的资源，可能随着时问的推移会不断加入近来。网格的动念性 包括动态增加和动态减少两个方面。 网格资源是异构的和多样的。在网格环境中可以有不同体系结构的计算机系统和 类别不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资源之间的通 信和互操作问题。 ( 4 ) 自治性与管理的多重性 网格上的资源首先是属于某个组织或者个人的，因此网格资源的拥有者对该资源 拥有最高级别的管理权限，网格允许资源拥有者对他的资源有自主的管理能力，这就 是网格的自治性。 但是网格资源也必须接受网格的统一管理，否则不同的资源就无法建立相互之间 的联系无法实现共享和互操作，无法作为一个整体为更多的用户提供服务。 因此网格的管理具有多重性，一方面它运行网格资源拥有者对网格资源具有自主 性的管理，另一方面又要求网格资源接受网格的统一管理。 3 网格与i n t c m e t 的比较f g l ( 1 ) 网格可以实现全面的资源共享 网格是建立在i n t e r a c t 和w c b 基础上的不会替代它们。i n t e m e t 的出现将独立的计 算机连成网络，但是没办法共享其他机器的资源。w c b 的兴起实现了通过网络的方式 将部分应用层的工作连接起来，计算机可以做包括电子商务在内的更多事情。但各行 业在应用层面上的互联互通远远没有实现，计算机的使用也远不如电话方便。而网格 将能实现应用层面上的互联互通，即用户使用层面上的互联互通。 ( 2 ) 计算平台和技术发生变化 网格的应用会改变计算平台，带动网络界的发展。这是一个新的计算平台，因为 平台的使用模式变了，其自身的技术和商业模式必然会变化，从而会涌现出大量的新 产品和利用这些技术提供的各类服务。 ( 3 ) 网格优越的功能和性能 1 ) 网格的互联网络比i n t e m e t 具有更大的带宽。现今欧美的网格计划都会使用 更高速度的主干网，c f r n 的科学家这样形容网格的带宽：“它就像用1 0 0 条车道的 高速公路取代今天的道路”。 2 ) 网格上将有更多高性能计算机，因此网格的计算速度、数据处理速度可以大 幅度提高。 3 ) 网格的体系结构比i n t e m e t 更能有效地利用计算资源。比如：网格将采用 种所谓的“广域缓存技术”，自动地把用户最需要的信息放在离用户最近的服务器上。 假如洛阳的用户要查找奥运会的信息，只需访问洛阳的服务器即可，尽管这些信息是 在中央电视台发布在北京的服务器上。 4 ) 另外，网格将促进更多、更大的网上社区的出现。这些相互联结的社区最终 构成一个庞大的网格社区，把地球上所有公民连为一体，根据网络的麦特考夫定律网 格的价值与网格用户数的平方成j 下比。 1 1 2 网格研究现状 1 国内网格相关研究 网格是高性能计算和信息服务的战略性基础设施，它将地理上分布、异构的各种 资源通过高速网络连接并集成起来，共同完成重大的科学问题研究。它不仅能够为信 息资源的获取、分布、传输和有效利用带来革命性和结构性的巨大变化，而且将根本 改变我们的研究方式、教育方式以及生产和生活方式。从1 9 9 8 年国家科技部的国家高 技术研究发展计划( 8 6 3 ) 启动中国的。高性能计算环境”项目开始至今，网格计算已 在中国经历了9 个年头。尤其是在国家。十五”计划期间，国家各部委先后启动了包 括国家科技部的国家高技术研究发展计划( 8 6 3 ) “中国国家网格( c n c n - i d ) ”、教育 部2 1 1 公共服务体系建设项目。中国教育科研网格计划( c h i n a g r i d ) ”、国家自然科 学基金委的重大专项“以网络为基础的科学活动环境研究”、国家重点基础研究发展 规划( 9 7 3 ) 中的“语义网格的基础理论、模型、方法及关键技术”和“虚拟计算环境 聚合与协同机理研究”等在内的国家级网格研究、开发和建设项目。这些研究项目在 网格的各个方面都取得了有代表性的成果。 我国科技界自2 0 世纪9 0 年代中后期。就开始密切关注国外相关领域的动向，并 及时开展跟踪研究。中科院计算所的织女星( g a ) 网格计划强调“服务网格”的思 想，其不仅面向科学计算，还提供消息、邮件、内容、交易、计算等服务。江南计算 所、清华大学、中国科技大学、西安交通大学等单位都开展了网格计算技术方面的研 究，在资源信息表示与存储、任务调度与管理、网格安全机制、访问与编程模式等关 键技术方面取得了重要成果。 2 0 0 2 年4 月，国家8 6 3 计划“高性能计算机及其核心软件”重大专项启动，通过本 专项的实施，使我国在网格技术方面达到世界先进水平，大幅度地提高我国的综合国 力和国际竞争能力。经过近两年的研究开发，专项已经取得一些成果。联想公司研制 的联想“深腾6 8 0 0 ”超级计算机峰值速度达5 3 万亿次，l i n p a c k 速度4 1 8 3 万亿次，列 世界t o p s 0 0 第1 4 位。网格软件完成了第一版，并己在中国国家网格节点部署。 2 0 0 4 年l o 月2 0 日，国际网格与协同计算大会( g c c ) 正在武汉举行。会上， c h i n a g r i d 正式对全世界发布了c g s p ( c h i n a g r i ds u p p o r tp l a t f o r m ) 的b e t a 版本。 随后在2 0 0 5 年5 月3 日，亚洲网格大会在新加坡举行，在i a nf o s t e r 所做的视频 报告中，他只提到了全世界的两个网格，一个是英国的e s c i e n c e ，另一个便是中国的 4 c h i n a g r i d ，这充分说明了c h i n a g r i d 在国际上的地位。而现在，c h i n a g r i d 的实力已经 追上、甚至超过了某些国外组织。 2 国外网格技术研究现状 近年来，国际上从美国、欧洲、日本等发达国家到印度这样的发展中国家，都启 动了大型网格计划，并得到了产业界的大力支持。目前，已有许多网格研究的组织和 项【9 】。 世界信息技术大国都认识到网格对当前网络技术巨大的拓展功能和宏伟的发展前 景，把发展网格技术放到了战略高度，纷纷投入巨资，争相发展网格技术，力图抢占 至高点，获取竞争新优势。 美国政府用于网格技术的基础研究经费己达5 亿美元。美国自然科学基金会资助 的网格项目有n p a c i g r i d 和t e r a c n i d 等。美国军方对网格技术更为重视，正规划实施 名为“全球信息网格( g l o b a ll i l f o r m a t i o ng r i d ) ”的巨型网格计划，此外还有美国宇航局 ( n a s a ) 支持的i p g 网格项目等。美国各大i t 公司如s u n ，m m ，o r a c l e ，l i p 等也 纷纷投入巨资进行网格研究。 欧洲的数据网格e u r o p e a nd a t ag r i d ( e d g ) 是一个国际性大型研究和技术发展项 目，该项目由c e r n ( e u r o p e a n o r g a n i z a t i o n f o r n u c l e a r r e s e a r c h ) ，欧洲粒子物理实验 室) 领导，另外包括e s a ( e u r o p e a ns p a c e a g e n c y ) ，法国c n r s ( c e n t r en a t i o n a lr e s e a r c h s c i e n t i f i c ) 、意大利i n f n 、荷兰n i k h e f 、英国p p a e c 共5 个主要合作伙伴以及欧洲 各国的1 5 个相关研究机构。d a t ag r i d 主要针对c e r n 的高能物理应用，解决海量数 据的分解存贮和处理问题，提供突破地理局限，允许分布在世界各地的工作者交互、 共享数据和设备，共同开展科学研究的合作环境。 欧洲网格( e u r o p e a ng r i d ) 的基本目标是建立一个为用户提供安全、简单、透明 访问全欧洲范围内的信息资源的平台，为欧洲的科学研究服务。该项目从网格基础设 施、应用开发、基本技术三个方面开展工作。研究机构有法国、德国、英国、瑞士、 波兰以及挪威的主要大学和计算中心，包括天文、航天、高能物理等应用领域的机构 和组织参加。欧洲还建成了欧洲网格计算数据库，包括查找数据库( 即进行网格计算 和相关活动的欧洲超级计算中心、组织，项目、研究小组和有关人员的相关信息) 和 计算机数据库( 存储了欧洲所有在研究活动中可以使用的超级计算机) 。另外，英国政 府已投资l 亿英镑，研制“英国国家网格”( u k n a t i o n a lg r i d ) 。法国也启动了国家网格 计划。荷兰国家网格计算计划将使5 个大学的研究人员能够更有效地在生物信息、粒 子物理等科研项目方面进行合作。这一网格计算计划包含5 台l i n u x 群集系统( 每个 大学各一台) ，通过荷兰大学的高性能网络s u r f n e t 连接在一起。 亚太地区网格a p c n i d ( a s i ap a c i f i cg r i d ) 是亚太地区的合伙网格计算项目。2 0 0 4 年5 月底，已有来自1 5 个国家( 包括澳大利亚、加拿大、中国、日本、美国等) 共4 9 个组织加入a p g 嗣。a p g r i d 主要支持两大应用：地球科学( 如气候模拟、流体模拟、 地震工程等) 和生物信息( 如基因科学等) 。 日本是亚洲开展网格研究比较早的国家。日本的d a t af a r m 网格项目，主要用于 p e t a b y t e 数据量的高能物理实验数据的分析和处理，与欧洲数据网格相连。日本还确定 了基础实验室( i t b l ) 、东京大学网络、大阪大学生物网格中心、电子科学计划( 架 构超级计算机网络) 等机构和发展网络计算机科技计划、国际研究网格计划 ( n a g e g i ) 、商务网格计算机等计划，并逐年拨经费推动网格技术研究。 韩国的网格计划之一是ng r i d ，这是韩国信息通讯部支持的一个项目，ng r i d 的 目标是建立韩国国家网格，该项目包括计算网格、数据网格、访问网格和应用网格。 它将韩国的超级计算机和高性能机群连接在一起，建立应用试验床、应用门户和开发 具体的应用程序。 印度在其第十个五年发展计划期间开发ig r i d 。主要是由高级计算开发中心把印度 技术研究所、印度科学研究所等7 个著名的学术机构连接在一起，以网格的理念令其 发挥资源共享等作用。 1 2 研究内容 1 2 1 网格任务调度 随着互联网的飞速发展，利用互联网上大量计算资源的网格计算将成为解决规模 庞大、复杂的问题的必由之路。要实现高效的网格计算需要处理许多复杂的问题，其 中，任务调度问题是网格研究中所必须解决的一个关键问题，也是网格应用的基础。 高效的任务调度策略和算法可以充分利用网格系统的处理能力，从而提高网格应用程 序的性能，以便更好地利用网格资源。然而，一般网格任务调度问题已经被证明是一 个n p 完全问题，因此，它引起了众多学者的关注，成为目前网格计算研究领域中的一 个焦点。 在网格系统中任务调度系统是其重要的组成部分，它要根据任务信息采用适当的 策略把不同的任务分配到相应的资源节点上去运行，由于网格系统的异构性和动态性， 以及运行于网格系统之中的应用程序对于资源的不同需求，使得任务调度变得极其复 杂不好的任务分配策略，将会增加任务的执行时间、降低整个网格系统的吞吐量。 1 网格任务调度的特点 网格任务调度系统具有以下几个特点： ( 1 ) 任务调度是面向异构平台的由于网格系统是由分布在i n t e m e t 上的各类资源 组成的包括各类主机、工作站甚至p c 机，它们是异构的，可运行在u n i x ，w i n d o w sn t 等各种操作系统下，也可以是上述机型的机群系统、大型存储设备、数据库或其他设 备。因此，网格系统中的任务调度必须面向异构平台，并在这些平台上实现网格任务 6 的调度。 ( 2 ) 任务调度是大规模的、非集中式的。由于网格系统是一个人到整个i n t e m e t 的分布式巨系统。要实现一种全局的统一集中的任务调度管理是根木不可能的。因此， 网格的任务调度必须以分布、并行方式进行任务的管理与调度。 ( 3 ) 任务调度不干涉网格节点内部的调度策略。在网格系统中，各网格节点的内 部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要的，也是 不可能的。 ( 4 ) 任务调度必须具有可扩展性。网格系统初期的计算规模较小，随着超级计算 机系统的不断加入，系统的计算规模也必将随之扩大。因此，在网格资源规模不断扩 大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性，不致降低网格 系统的性能。 ( 5 ) 任务调度能够动态自适应。网格中的资源不但是异构的，而且网格的结构总 是不停地改变，有的资源出现了故障，有的新资源要加入到网格中，有些资源重新开 始工作等，总之，网格的动态性是明显的，所以任务调度系统必须适应网格的这种动 态性，从可利用的资源中选取最佳资源为用户提供应用服务。 2 网格计算任务调度的主要目标 简单地说，网格计算任务调度的目标就是要对用户提交的任务实现最优调度，并 设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度( o p t i m a lm a k e s p a n ) 、 服务质量q o s ( q u a l i t yo f s e r v i c e ) 、负载均衡( l o a db a l a n c i n g ) 、经济原则( e c o n o m i c p r i n c i p l e s ) 等。 ( 1 ) 最优跨度。跨度是一个最主要、最常见的目标，指的是调度的长度，也就是 从第一个任务开始运行到晟后一个任务运行完毕所经历的时间。跨度越短说明调度策 略越好。当用户向网格系统提交任务后，最大的愿望是网格系统尽快完成自己的任务 可见，实现最优跨度是用户和网格系统的共同目标。 ( 2 ) 服务质量q o s 。网格系统要为用户提供计算和存储服务时，用户对资源需求 情况是通过q o s 形式反映出来的任务管理与调度系统在进行分配调度任务时，保障网 格应用的q o s 是完全应当的。 ( 3 ) 负载均衡。在开发并行和分布计算应用时，负载平衡是一个关键问题网格系 统更进一步扩展了这个问题。网格任务调度是涉及交叉域和大规模应用的调度，解决 好系统的负载均衡是一个非常重要的问题。 ( 4 ) 经济原则。网格环境中的资源在地理上是广泛分布的，而且每个资源都归属 于不同的组织，都有各自的资源管理机制和政策根据现实生活中的市场经济原则，不 同资源的使用费用也应是不相同的，市场经济驱动的资源管理与任务调度必须使消费 双方( 资源使用者和资源提供者) 万惠万利，才能使网格系统长久地发展下去。 3 网格任务调度算法 目前，围绕着网格计算中的任务调度算法，国内外已经做了大量的研究工作，先 后提出了各种静态和动态的调度算法：静态调度算法是指所有的任务机器映射策略在 执行任务调度前就已经全部确定；动态调度算法是指一些任务机器映射策略在执行任 务调度期间根据实际情况进行确定。 静态算法相对较为简单，调度算法运行开销低，对数据的依赖性小，因而静态调 度算法是网格计算中最早被研究的算法。在网格计算环境中，常见的静态调度算法有： o l b ( o p p o r t u n i s t i cl o a db a l a n c i n g 随机负载均衡算法) 、m e t ( m i n i m u me x e c u t i o n t i m e 最小执行时间调度算法) 、m c t ( m i n i m u mc o m p l e t i o nt i m e 最小完成时间调度 算法) 、m i n - i m n 、m a x m i n 、d u p l e x ( m i n r a i n 和m a x r a i n 结合) 、g a ( g e n e t i ca l g o r i t h m s 遗传算法) 、s a ( s i m u l a t e da n n e a l i n g 模拟退火算法) 、g s a ( g e n e t i cs i m u l a t e da n n e a l i n g 遗传模拟退火算法) 、t a b u ( 禁忌调度算法) 、a 等1 1 种。 动态调度算法可以分为在线模式( o n 1 i n em o d e ) 和批模式( b a t c hm o d e ) 两类： 在线模式是指任务一到来就映射到机器，该模式对每一个任务的映射只考虑一次，也 就是说一旦任务被映射就不会再改变。常见的在线模式启发式调度算法有：o l b 、m c t 、 m e t 、s a ( s w i t c h i n ga l g o r i t h m 开关调度算法) 、k p b 。 批模式下，任务到来并不立即映射到机器，而是把任务收集起来组成一个任务集 合，等映射事件到来后才对该集合中的任务进行集中映射。这个独立任务的集合称之 为元任务，因此，批模式下的元任务包括新到达的任务( 也就是在最后一个映射事件 之后到达的任务) 和已经映射但还没有开始执行的任务。批模式对独立任务的集合中 每一个还没有开始执行的任务在每一次映射事件中都进行考虑直到该任务开始执行为 止，因此，批模式可以得到整个元任务的资源需求信息和更多任务的执行时间，从而 可以做出更合理的任务映射策略。批模式下常见的启发式调度算法有：m i l l m i n 算法、 m a x m i n 算法和s u f f e r a g e 算法。 1 2 2 网格体系结构 随着网格计算研究的深入，人们越来越发现网格体系结构的重要。网格体系结构 是关于如何建造网格的技术，包括对网格基本组成部分和各部分功能的定义和描述， 网格各部分相互关系与集成方法的规定，网格有效运行机制的刻画。显然，网格体系 结构是网格的骨架和灵魂，是网格最核心的技术，只有建立合理的体系结构，才能使 网格有效地发挥作用；只有考虑到当前已有的物理资源部署和实际应用，才能够设计 和建造好网格，才能满足将来的需求和应用的发展。 目前，比较重要的网格体系结构有两个：一个是伊安福斯特( i a nf o s t e r ) 等在早 些时候提出的五层沙漏结构【l 叫；另一个是以i b m 为代表的工业界的影响下，在考虑到 w e b 技术的发展与影响后，在五层沙漏体系结构的基础上，结合最新的w e bs e r v i c e 技 术提出的开放网格服务体系结构0 ( 3 s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) 。 1 五层沙漏体系结构 五层沙漏结构是一种影响十分广泛的结构，它是一种以“协议”为中心的结构，强 调协议在网格的资源共享和互操作中的地位，也十分强调a p l ( a p p l i c a t i o n p r o g r a m m i n g i n t e r f a c e s ) 和s d k ( s o r w a r ed e v e l o p m e n tk i t s ) 的重要性。 五层沙漏结构根据与底层具体物理资源的距离，从下到上将网格划分为五层，分 别是构造层( f a b r i cl a y e r ) ，连接层( c o n n e c t i v i t yl a y e r ) ，资源层( r e s o u r c el a y e r ) ， 汇聚层( c o l l e c t i v el a y e r ) 和应用层( a p p l i c a t i o nl a y e r ) 。五层沙漏结构的一个重要特 点就是“沙漏”形状，其原因是由于各层协议的数量是不同的，其最核心的部分，由于 既要能够实现上层各种协议向自身协议的映射，同时也要实现自身协议向下层其它各 种协议的映射，并且核心协议在所有支持网格计算的地点都应该得到支持，所以核心 协议的数量不应该太多，这样核心协议就形成了协议层次结构中的一个瓶颈，在五层 结构中，资源层和连接层共同组成该体系结构的瓶颈部分。 2 开放网格服务体系结构 开放网格服务体系结构o g s a 被称为是下一代网格体系结构，它是在原来“五层沙 漏结构”的基础上，结合最新的w e bs e r v i c e 技术提出来的。o g s a 包括两大关键技术 即网格技术和w e bs e r v i c e 技术。以服务为中心是o g s a 的基本思想，在o g s a 框架 中，将一切都抽象为服务，包括计算机、程序、数据、仪器设备等。这种观念有利于 通过统一的标准接口来管理和使用网格。 w e bs e r v i c e 提供了一种基于服务的框架结构，但是，w 曲s e r v i c e 面对的一般都 是永久服务，而在网格应用环境中，大量的是临时性的短暂服务，比如一个计算任务 的执行等。考虑到网格环境的具体特点，o g s a 在原来w e bs e r v i c e 服务概念的基础 上，提出了“网格服务( g r i ds e r v i c e ) ”的概念，用于解决服务发现、动态服务创建、 服务生命周期管理等与临时服务有关的问题。 基于网格服务的概念，0 g s a 将整个网格看作是“网格服务”的集合，但是这个集合 不是一成不变的，是可以扩展的，这反映了网格的动态特性。网格服务通过定义接口 来完成不同的功能，服务数据是关于网格服务实例的信息，因此网格服务可以简单地 表示为“网格服务= 接n 行为+ 服务数据”。 1 3 论文的结构 全文包含四个章节，分别安排如下：第一章是“绪论”，包括研究背景和研究内容 9 第二章是。网格体系结构及g l o b u s 中间件”，简单介绍了现在网格研究领域中两种主 要的体系结构( 五层沙漏结构和开放网格服务体系结构) 以及g l o b u s 网格中间件；第 三章是“网格任务调度及算法设计”，主要包括m i n m i n 算法、m a x r a i n 算法、遗传算 法g a 、蚂蚁算法、基于a g e n t 的任务调度、完全分布任务调度算法、基于任务池的任 务调度算法等几种典型的任务调度算法的简介，针对算法的不足进行的一些分析和改 进，最后设计出一种新的任务调度算法；第四章是“任务调度的模拟”，包括对b r i c k s ， m i c r o g r i d ，s i m g r i d ，g r i d s i m ，c h i c s i m ，e d g s i m ，g r i d n e t ，o p t o r s i m 等几种网格模 拟器的简介，重点介绍o p t o r s i m ，并用其模拟新设计出来的任务调度算法，最后根据模 拟结果对此算法进行结果对比和评估；最后总结全文。 1 0 第二章网格体系结构及g l o b u s 中间件 2 1 网格体系结构 网格体系结构就是关于如何建造网格的技术。它给出了网格的基本组成和功能， 描述了网格各组成部分的关系以及它们集成的方式或方法，刻画了支持网格有效运转 的机制。 到目前为止，比较重要的网格体系结构有两个，一个是f o s t e r 等在早些时候提出的 五层沙漏结构 1 0 1 ，然后就是在m m 为代表的工业界影响下，在考虑到w e b 技术的发展与 影响后，f o s t e r 等结合w 曲s e r v i c e 提出的开放网格服务机构o g s a ( o p e ng r i ds e r v i c e s a r c h i t e c t u r e ) 。 2 1 1 五层沙漏结构 在网格环境中，互操作性是首要考虑的问题，而互操作性意味着共同的协议。因 此，网格体系首先是协议体系，由协议定义了虚拟组织( v i r t u a lo r g a n i z a t i o n ) 的用户 与资源协商、建立、管理与利用共享关系的机制。网格体系通常为层次结构，每一层 的组件共享了一些共同的特征，并且构建于更低一层提供的服务上。分层的网格体系 与i n t e m e t 协议体系的关系【1 1 】如图2 1 所示。 i 应用层( a p p l i c a t i o n ) i 汇聚层( c o l l e c t i v e ) 资源层( r e s o u r c e ) l 连接层( c o n n e c t i v i t y ) 图2 1 五层结构及其与t c p i p 网络协议的对比 器一 五层沙漏结构根据该结构中各组成部分与共享资源的距离，将对共享资源进行操 作、管理和使用的功能分散在五个不同的层次，越向下层越接近物理的共享资源，因 此该层与特定资源相关的成分就比较多；越向上层就越感觉不到共享资源的细节特征， 也就是说上层是更加抽象共享资源的表示，因此就不需要关心与底层资源相关的具体 实现问题。 在五层沙漏结构中，最底层是构造层( 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 l i c a t i o n ) 和资源的距离最远，它关心的是有什么样的资源可以由下面提供给虚拟组织，解决不 同虚拟组织的具体问题。各层的功能特点如下【”】： ( 1 ) 构造层( f a b r i c ) 局部控制的界面。网格构造层的基本功能就是控制局部的资源，向上提供访问这 些资源的接口。构造层的资源是非常广泛的，可以是计算资源，存储系统目录，网 络资源和传感器。构造层网格组件实现对本地特定资源的访问，向上提供访问这些资 源的接口。因此在构造层各种功能实现上，有紧密和互相依赖的联系，还有对共享的 支持。构造层实现的基本功能包括查询机制、控制服务质量的资源管理能力等。 ( 2 ) 连接层( c o n n e c t i v i t y ) 支持便利安全的通信。连接层的基本功能是保证构造层的资源实体问相互通信的 便利和安全，在这一层，网格定义了核心的网络事务处理所需要的通信和认证协议。 通信协议允许在构造层资源之间交换数据，建立在通信服务上的认证协议提供加密的 安全机制，用于识别用户和资源。通信的必要条件包括传输，路由和命名等功能。在 实际上，通信协议大部分是从t c p i p 协议栈中抽出的。比如i n t e m e t 体系结构的i n t e m e t 层( 口与i c m p ) ，传输层( t c p 与u d p ) ，和应用层( d n s ，o s p f ，r s v p 等) ( 3 ) 资源层( r e s o u r c e ) 共享单一的资源。资源层建立在连接层的通信和认证协议之上，定义的协议包括 安全的连接、初始化、监视和控制、审计、计费等。资源层的协议实现调用构造层的 功能以访问和控制本地资源。资源层的最重要的两个协议是信息协议和管理协议，前 者用于获得关于资源结构和状态的信息，后者用来协商对共享资源的访问。 ( 4 ) 汇聚层( c o l l e c t i v e ) 协调各种资源。汇聚层的基本功能是协调多个资源的共享，实现虚拟组织。汇聚 层组件建立在资源层和连接层形成的协议瓶颈之上，它们能够在不对资源强加新的要 2 求的情况下实现广泛的和多样化的共享行为，如目录服务，协同分配，调度和代理服 务等。 ( 5 ) 应用层( a p p l i c a t i o n ) 虚拟组织中的所