（计算机软件与理论专业论文）网格计算任务调度算法的研究与实现.pdf

阆格计算任务调度算法的研究与实现东南大学硕士学位论文 网格计算任务调度算法的研究与实现 摘要 随着超级计算机的不断发展，它已经成为复杂科学计算领域的主宰。但以超级计算机为 中心的计算模式存在明显的不足，而且目前正在经受挑战。超级计算机虽然是一台处理能力 强大的“巨无霸”，但它造价极高，通常只有一些国家级的部门，如航天、气象等部门才有 能力配置这样的设备。而随着人们日常：j ：作遇到的商业计算越来越复杂，人们越来越需要数 据处理能力更强大的计算机，而超级计算机的价格显然阻一i ：= 了它进入普通人的j i ：作领域。于 是，人们开始寻找一种造价低廉而数据处理能力超强的计算模式，最终人们找到了答案 网格计算( g r i d c o m p u t i n g ) 。“网格是一个由硬件和软件系统组成的架构，它可以提供可靠 的，协调的，无处不在的和低廉的高端计算能力”。计算网格是将网络上众多的处理器计 算资源连接起来，组成一台虚拟的高性能计算机，使刚户可以获得较高性能的计算服务。 本文的研究重点主要集中在对计算网格涉及的计算任务调度算法方面。虽然，众多研究 者已经对此方面进行了较为深入的研究，但是目前被广泛采川的算法，如2 - p h a s e 调度算法、 基丁优先级和b e s tf i t 机制的c o r s p b 、c o r s b f 、c o r s b f r 调度算法以及基丁市场供求 关系的调度算法等，都不具有以卜综合的能力：既保证高效的调度效率，又可以准确地对计 算资源动态特性进行描述，并且对这种动态性所带米的消极影响实施规避行为，同时还可以 满足计算任务提山者的q o s 需求。因此，作者在对网格计算汞l 计算网格系统的知识背景以 及该领域的研究现状进行认真分析的基础上，提山了可以解决此问题的基丁信任机制和q o s 测量的计算任务调度算法，并在计算网格仿真系统实现中对此算法进行了模拟仿真利验证。 具体的 ：作主要包括： 在研究分析计算网格计算资源发现管理模型现有成果的基础上，仿照人类社会现实政治 模型，构建了一种基于“上访卜察”的计算资源发现管理模型。 利用人类社会信任机制的概念，结合高性能网络研究中对服务质量( o o s ) 的研究成果， 提出了一种基丁信任机制矛q o s 测量的计算任务调度算法； 在对g l o b u s 等计算网格底层设计和实现原野! 进行研究分析的基础上，结合计算任务的 特点，初步构建出一种侧重任务调度的网格计算底层支撑系统的实现模型。 出于全面的评价一个计算任务调度算法性能的优劣，从整个计算网格的兼容性、健壮性 等调度出发，提出了包含九人测度的计算任务凋度算法性能评价模型。 考虑到计算网格实际的运行环境雨i 实验室研究环境的局限，详细殴计了一套计算网格仿 真系统并进行了实现。 关键字：网格计算、资源发现管理、任务渊度、性能评价、信任、q o s 、仿真 r e s e a r c ha n di m p l e m e n t a t i o no fs c h e d u l i n ga l g o r i t h m s i nc o m p u t a t i o n a lg r i d a b s t r a c t w i t hd e v e l o p i n gc o n t i n u a l b s u p e rc o m p u t e r sh a v e b e e nd o m i n a n ti nc o m p l e xs c i e n c e c o m p u t i n g m e a n w h i l e ，t h e r ea r eo b v i o u sd i s a d v a n t a g ei nt h es u p e r - c o m p u t e r - c e n t e r e dc o m p u t i n g m o d e l , w h i c hh a st of a c et h es e r i o u sc h a l l e n g ea l t h o u g hs u p e rc o m p u t e r sh a v eu n i m a g i n a b l e c o m p u t i n gc a p a c 砂l i k eag i a n t , t h e i rh i g hd e s i g na n dm a i n t a i nc o s tp r e v e n tt h e i ru b i q u i t y , a n d o n l ys o m en a t i o n a li n s t i t u t i o n s , s u c ha sa e r o n a u t i c sa n da e r o g r a p hd e p a r t m e n t s c o u l da f f o r d t h e m b e c a u s ep e o p l en e e dm o r ea n dm o r ec o m p l e xc o m m e r c ec o m p u t i n gi no u r 聪詹，w eh a v et o p u r s u em o r ea n dm o r e p o w e r f u lc o m p u t i n gd e v i c e s , b u tt h ec o s to f s u p e rc o m p u t e r si so u rb i g g e s t o b s t a c l e t h e r e f o r e , p e o p l es t a r td e v e l o p i n gt h el o wc o s tb u th i g h - p e r f o n n a n cc o m p u t i n gm o d e l g r i dc o m p u t i n gi j r j u s to n ek e y “c o m p u t a t i o n a lg r i di sah a r d w a r ea n ds o f t w a r ei t 矿 a s t r u c t u r e t h a t p r o v i d e sd e p e n d a b l e ，c o n s i s t e n t ，p e r v a s i v e ，a n di n e x p e n s i v ea c c e s st oh i g h e n dc o m p u t a t i o n a l c a p a b i l i t i e s ”c o m p u t a t i o n a lg r i di su s e dt oc o n n e c tv a r i e dc o m p u t a t i o n a lf e s o u r c e st oc o n s t r u c t av i r t u a l 确珈p e r f o r m a n c ec o m p u t e r , w h i c hc o u l do f f e rh i g hp e r f o r m a n c ec o m p u t i n gs e r v i c e o u rr e s e a r c hf o c u s e so nt a s ks c h e d u l i n ga l g o r i t h m t h o u g hm a n ys c h o l a r sh a v ea l r e a 妙 d o n ed e e pr e s e a r c ht ot h i sr e s p e c t , b u tt h ea l g o r i t h m sa d o p t e de x t e n s i v e l ya tp r e s e n t , s u c ha s2 一 p h a s e ，c o r s p b ，c o r s b ec o - r s b f ra n dm a r k e t b a s e d , e t c ，d on o to w nt h ec o m p r e h e n s i v e a b i l i t i e si n c l u d i n gg u a r a n t e e 矿h i g hs c h e d u l i n ge f f i c i e n c y , a c c u r a t ed e s c r i p t i o no fr e s o u r c e s d y n a m i cc h a r a c t e r i s t i c , e v a d i n gt ot h en e g a t i v ei n f l u e n c eb r o u g h to ft h e s ed y n a m i c s ，a n d s a t i s f y i n gt a s kr a i s e r s q o sd e m a n d t h e r e f o r e , r e f e r r i n gt oc u r r e n tr e s e a r c hr e s u l t s t h ea u t h o r p r e s e n t sa 乃4 u s t b a s e da n dq o s - m e a s u r e ds c h e d u l i n ga l g o r i t h m 。a n dt h e ns i m u l a t e si t 0 7 1t h e c o m p u t a t i o n a lg r i ds i m u l a t i o ns y s t e m o u rr e s e a r c hw o r k sm a i n l yi n c l u d e r e f e r r i h gc u r r e n tr e s e a r c hr e s u l t so nc o m p u t a t i o n a lr e s o u r c ed i s c o v e r ya n dm a n a g e m e n t m o d e l , c o n s t r u c taf e e d b a c ka n db z v e s t i g a t i o nb a s e dr e s o u r c e sd i s c o v e r ) , a n dm a n a g e m e n t m o d a l ； r e f e r r i n gt r u s tc o n c e p ti n h u m a ns o c i e t ya n dr e s e a r c hr e s u l t s0 1 lh i g h - p e r f 0 1 7 1 l a n c e n e t w o r k , c o n s 护u c tat r u s t - b a s e da n dq o s - m e a s u r e ds c h e d u l i n ga l g o r i t h m ； r 豸西r i n g t ot y p i c a lc o m p u t a t i o n a lg r i dr e a l i z a t i o nm o d e l , s i m p l yc o n s t r u c t u s c h e d u l i n g - e m p h a s i z e d d e s i g nm o d e l , p r e s e n t9p e r f o r l n a u c e e v a h t a t i o nm e a s u r e s 。a n dt h e nc o n s t r u c tas i m p l f i e dm u m m e a s u r e s p e r f o r n l a n c ee v a h t a t i o nm o d e l , d e s i g na n di m p l e l ，l e n tt h ec o m p u t a t i o n a lg r i ds i m u l a t i o n s t e i n a n dt h e nh a v et h ev a r i e d s c h e d u l i n ga l g o ，i t h m ss i n t u l a t e d c o m p a r e da n de v a l u a t e d k e j , w o r d s ：g t 。i dc o m p u t i n g ，r e s o m c ed i s c o v e o a n d , i v i i l i t i j j u d l e l h t a s k5 2 ：h e d u l i n g p e t b , 。n l a l l c e 凸1 a h l o l l o i l7 1 。f i s t q o s s i o l u l o t i o n 塑鳖兰簦堡叁塑壅簦墨塑塑查皇壅墨 查塑垄堂婴主兰堡堡查 东南大学学位论文 y 6 4 4 7 2 独创性声明及使用授权说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 签名日期：皇竺：! ：兰 二、关于学位论文使用授权说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位沦文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许沦文被 查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括 刊琶) 授权东南大学研究生院办理。 l 签名： i 垒型垃导师签名：邋日期： o 满3j ，_ j 网格计算任务调度算法的研究与实现东南大学硕士学位论文 第一章绪论 本章首先简单介绍了网格计算的应用和研究背景；然后重点针对计算资源发现和管理 模型、计算任务调度算法和底层支撑代表系统这几个计算网格的关键技术，讨论了当前的 研究现状和存在的问题；接着阐述了本文要研究和解决的问题以及采用的研究策略；并且 在本章最后部分勾画了本文的组织结构。 i i 研究背景 网格计算( g r i dc o m p u t i n g ) 1 , 9 , 1 0 , 1 l ，”】是当今计算机科学领域最新兴起的一 项有很高学术价值和应用价值的研究课题。众所周知，高性能计算已经成为许 多科学和工程实践的关键技术。科学家们也越来越多地使用超级计算机来研究 复杂现象，例如可以用来预测复杂的非线性现象，或者是在做实验之前，就可 探索物理参数的变化规律，甚至还可以用来模拟现实世界中所发生的某些事件。 然而，尽管超级计算机的能力在不断增长，仍然有许多应用无法实现。因为这 些应用往往需要处理能力强大的超级计算机的支持，但是超级计算机造价极高， 通常只有一些国家级的部门，如航天、气象等部门爿有能力配置这样的设备： 另一方面，某些应用对计算的要求非常高，即使是现在最大的超级计算机也无 法提供它们所需的资源，这时就需要将高性能计算依托i n t e r n e t 或其他高速网 络将遍布世界各个角落的能力千差万别的计算资源联结在一起，形成大规模的 几乎可以无限扩展的计算能力。比如由美国n s f ( 国家自然科学基金) 支持建 设的网格计算系统d z f ( d i s t r i b u t e dt e r a s c a l ef a c i l i t y ) 就是一个较为成功的 网格计算项目。该系统利用高速互联网络将n s c a 、s d s c 、a n l 以及加州理工 学院等多家高性能计算中心连接起来，为数以万计的科研人员提供了力亿次的 计算能力和超过6 0 0 t 的存储能力。与传统的高性能计算机不同，d t f 不是位 于一个地点，而是由网络连接起来的一个计算联盟。通过分布在不同地点的高 性能计算设备的接入，d t f 可以很容易的扩充计算能力和存储能力，同时也便 于各地的研究者进行协同工作。d 丁f 所拥有的每秒1 36 万亿次的计算能力大约 是“深蓝”超级计算机的1 0 0 0 倍，强大的计算和存储能力使其能够满足如生命 科学、大气分析、高能物理等众多领域对高性能计算的要求。除d t f 以外，i p g 、 n t g 、a s c i 、d a t ag 1 一i d 等项目也都充分体现了网格计算的可行性和优越性。由 此看来，网格计算的研究具有很强的现实意义。 网格计算任务调度算法的研究与实现东南大学硕士学位论文 “计算网格是一个由硬件和软件系统组成的架构，它可以提供可靠的，协 调的，无处不在的和低廉的高端计算能力”。传统的网格计算系统由于自 身系统的庞大性，因此它涉及了很多方面的关键技术，如：资源描述与发现、 资源管理与组织、计算任务调度、性能评价、通信协议规范、安全体系和容错 机制等。 1 2 研究现状 由于计算网格的目标是利用网络上一切可利用的、空闲的计算资源来对计 算量巨大的、高度复杂的任务进行计算求解，因此，如果要提高计算网格的计 舆淑率孤么必孤贰：资源发现稻管理、计算任务的调发、底甚支撑系统警责 面进行更深入的研究，提出更有效的模型、算法以及解决方案。目前，研究界 对计算网格以上三个方面的研究主要包括： 1 2 1 计算资源发现和管理模型 提高计算网格计算效率的首要任务是能够尽快发现可利用的计算资源、然后 对这些计算资源动态变化带来的信息进行管理。资源发现管理模型 1 5 , 1 9 】的结构 不仅依赖于需要调度的计算任务和需要管理的资源数量，而且还依赖于资源所 处的域的类型( 单个域中还是多个域) 。从资源的组织、发现和管理方式来看， 目前国内外对网格资源管理基本模型的研究主要体现为集中式、分布式、层次 式和基于多a g e n t 式等四种形式。 集中式发现管理模型：以统一的策略管理位于一个或多个域中的资源。但是 集中式发现管理模型实施的前提是所有资源的状态信息必须是确定的，然而 网格中的资源是以“动态的虚拟组织”形式存在的，所以这种静态的约束严 重影响了网格的自适应性和高扩展性。另外，集中式发现管理模型所采取的 是全局统一的管理策略，这又与不同的虚拟组织中各自不同的本地管理策略 相悖。所以全球规模的网格系统并不适合。 分布式发现管理模型 1 5 , 1 9 ：通过资源管理系统之削各自的相互作用，来决定 哪个资源适合作业执行。分布式发现管理模型强调各个系统之间是对等的， 过多注重系统内部资源的状况，忽视了系统问的配合，因此虽然具有高度的 可扩展性，但是却缺少了全局性的宏观调控能力。更重要的是，这种分布式 发现管理模型却恰恰与网格发展的初衷大规模、大范围服务资源共享相 悖。 网格计算任务调度算法的研究与实现东南大学硕士学位论文 层次式发现管理模型：一种混合模型( 集中式和分布式模型的结合) ，即根据 管理域( 地域) ，以及具体应用因素，资源的数量和类型等因素，以站点资源 为单位组成树型结构，为资源的联合分配提供了一种管理机制。对于所有 子树，父节点相当于它们的联合分配器。与树型结构的资源信息服务相配合， 在实际的资源调度过程中，只要管理本节点所“拥有”的资源即可。这样， 当在某一个子节点上提交了大型资源请求的应用时，即需要联合分配时，该 子节点可将请求快速地上传至父节点，而父节点作为联合分配器，它拥有各 个子节点的系统状态信息，从而可以快速判断自身拥有的资源集合是否能满 足应用程序的资源请求，并将资源请求分割开来，定位和分配资源，将最终 的资源组作为一个整体来操作，同样，如果这个父节点自身拥有的资源仍不 能满足需求时，它可以继续向上一层父节点传送请求，直到能够满足应用需 求并定位好资源。层次式发现管理模型的优点主要体现在资源的动态性更容 易掌握和管理，尤其是当资源发生诸如增减站点或设备、关闭机器、网络故 障等变化时，在相关的节点上能够很快地体现出来，从而维护了整个系统状态 信息的完整性和正确性，故而具有高度的可扩展性。但是，层次式发现管理 模型需要将资源的动态更新信息一层一层地由叶结点反溯到根结点，而这样 的反溯过程需要较长的时间完成，因此，在资源动念性很强、经常发生变化 并且变化的频率较快的环境下，层次式发现管理模型的这种层层反溯过程将 不能很及时地反映计算网格资源的变化。 多a g e n t 式发现管理模型：通过将代理( a g e n t ) 小程序“释放”在所管辖 的网络内，进行计算资源的发现和管理。和上述三种资源发现管理模型相比， 基于a g e n t 的发现管理模型具有快速、准确、可配置性和可控性强的优点， 但是这种模型本身对用来发现资源和汇报资源信息的代理( a g e n t ) 要求较 高，同时对所辖网络中支持该代理的计算节点上的s t u b 要求也比较苛刻。 1 2 2 计算任务调度算法 高效的任务调度算法也可以提高整个计算网格的计算效率，因此作为计算 网格关键技术之一的任务调度算法，也历来都受到国内外网格研究者的重视和 关注【2 ，5 。8 ，2 2 。”。在众多的任务调度算法中，以下几种算法思路比较新颖并且也具 有了较高的参考价值。 两阶段( 2 - 1 1 1 a s e ) 调度策略2 l ：将一个刊算任务的计算范围依次划分为l a n 问和l a n 内两个阶段，并分别在l a n 问阶段和l a n 内阶段设立全局的、 集中的任务调度者，以负责制定该阶段的仟务渊度疗案和舱督任务执行情 网格计算任务调度算法的研究与实现 东南大学硕士学位论文 况。2 - p h a s e 式的调度策略，的确在某种程度上反映了计算网格的网络组成， 也为实施网络层次的其他调度算法提供一定的支持。但是，由于仅用涉及 削的两层结构来刻画计算网格是不准确的，所以，2 - p h a s e 调度策略还不 能很好地描述计算网格的调度，需要更深入的扩展。 基于优先级和b e s t f i t 机制的c o - r s p b 、c o - r s b f 、c o - r s b f r 调度算法【7 1 ： 首先提出了“联合预留”( c o - r e s e r v a t i o n ) 的思想，即当计算请求被提出时， 应用和计算网格系统之间将签订一个资源预留协议，只有当s 的要求发 生冲突时，调度者才会检查计算请求，同时如果在整个计算请求中有一个需 要的资源不可得，那么整个计算请求将被全部抛弃。在此思想土，该算法提 出了“基于优先级利益的联合预留调度算法”( c 。琅s p b ) 、“基于尽力服务 的联合预留调度算法”( c o - r s b f ) 和“基于尽力和优先级的联合预留调度 算法”( c d 琅s b f r ) 其中，c o - r s p b 具有较高总体调度效益，c o r s b f 具 有较低的请求拒绝量，而c d 求船职则是上述二者的折衷。 基于市场供求关系的调度算法【8 l ：仿照日用品买卖市场调控策略来对计算资 源进行优化组合。具体的，计算资源的“价格”被设定为介于资源的需求和 提供之间，当计算资源的“价格”确定后，对它们的分配过程就按照“先来 先服务”的原则进行，统一地由调度者进行调度。对于同一个计算资源，在 实际的调度过程中可能会由于所选的策略和所处的环境不同而被标上不同 的“价格”，因而需要调度者进行策略级的全局优化。基于市场供求关系的 调度算法利用经济学理论进行调度策略的分析，为其他调度算法提供了新颖 的思路。 1 2 3 底层支撑系统 目前，国外成熟的网格计算底层支撑系统【1 2 ，”，1 4 】主要有g l o b u s 、l e g i o n 、 w e b f l o w 等，而我国在这一方面的研究还处于刚刚起步阶段。 g l o b u s ：g l o b u s 是美国多家研究机构提出的建立计算网格的研究项目。 g l o b u s 是一种软件基础设施，它使应用能以单一虚拟机的方式处理分布的 异构计算资源。其系统核心为一个可以提供建构计算网格所需基本服务( 如 安全、任务调度、资源定位和管理以及通信) 的工具集( g l o b u s m e t a c o m p u t i n gt o o l k i t ，g m t ) 。此外g l o b u s 是一种多层机构，因此它可以 被看成基于底层服务上的元计算框架，并且可以以a p i 方式提供对外的接 口，以便其他研究人员在其基础上丌发各种应用执行环境。 l e g i o n ：l e g i o n 是美国l t ，t w i n i a 大学丌发的基于对象的元计算系统，它和 g l o b u s 类似，提供地理分m 的正缝n 勺异掏系统集成，l e g i o n 正要山类和元 网格计算任务调度算法的研究与实现 东南大学硕士学位论文 类组成，它具有以下3 个特点，使得用户可以自行增加和删除功能：软硬 件部分都是对象、类管理自身的实例、用户可以自定义类。l e g i o n 与g l o b u s 相比存在的差异就是：l e g i o n 通过把系统中所有组件封装成对象来实现元 计算环境，因此它具有面向对象方法的所有好处，如数据封装、继承等， 进而可以方便地构建元计算系统。 w e b f l o w ：w e b f l o w 是w e b 模拟计算的扩展，是一种广域分布计算框架。其 主要目的就是建立一个分布的和可重用的计算模块的框架，使得用户可以 通过浏览器异地地参与计算。w e b f l o w 本身是基于j a v a 的3 层结构系统， 前端是用a p p l e t 进行定制的控制环境，中间件采用s e r v l e t 技术来进行管理 和同支持模块层进行交互。在开发和发布模块时，集成人员可以使用可视 化工具把源模块的输出直接连接到目标模块的输入，从而建立计算的分布 计算图。因此w e b f l o w 可以在支持服务上插入新服务，并且可以更加灵活 地装在任何具有支持s e r v l e t 的w e b 服务器的机器上。 n h p c e ：n h p c e 是由我国自行研制的大分布式计算系统。它将国家高性 能中心下属的分布在不同区域的曙光、银河及神威等异构超级计算机，通 过i n t e r n e t 或专用高速网连通起来，以构成强大的国家性质的计算节点。它 主要具有以下几个功能：全网格统一的资源信息管理、全网格统一的用户 管理、全网格统一的作业管理、全网格统的安全和认证机制。因此m 妒c e 为网格应用提供了支持平台和开发平台，可以根据对各种计算资源的特殊 要求，为网格应用提供必要计算资源的查询和获取，向网格提交作业并获 得相应计算结果，以及保证重要数据和文件的安全。 1 2 4 存在的问题 尽管众多的研究者对计算网格做出了大量的研究工作，并且其中也不乏丌 创性，但是仍然存在以下问题，制约了计算网格的计算效率： 缺少有效的资源发现和管理模型以提供智能化的宏观调控手段和资源信息 更新变动等快速反映能力：虽然集中式、分和式、层次式和基于多a g e n t 式等四种资源发现和管理模型为我们提供了多种形态的发现和管理资源的 策略，但是却没有为我们提供一种对智能化宏观调控、快速响应资源变动 等需求的整合：集中式虽然具有较高的宏观调控能力，但是却妨碍了计算 网格的可扩展性；分布式虽然对计算网格的可扩展性提供了很好的支持， 但是却过多地集中于局部，缺少大j 动观：层次式是集中式与分川，式的折衷， 以树结构管列! 资源和发现资源变动，似足更新的资源信息i 7 , j 婴层一层地 网格计算任务调度算法的研究与实现东南大学硕士学位论文 汇报给上层管理节点直至根节点，因此很难达到快速响应的要求；多a g e n t 以可移动的a g e n t 方式收集资源变动信息，扩展性高、自由性强，但是这种 方式对a g e n t 本身的要求比较高，对a g e n t 所需要附驻的s t u b 的要求也比 较苛刻，尤其对于计算网格这种大型的、全球规模的、或者是并不太安全 的环境。 缺少有效的任务调度算法将高效的调度效率、对参与计算网格的虚拟组织 或网络的动态特性的描述和对这种动态性所带来的消极影响的规避以及满 足计算任务提出者的o _ o s 需求等进行整合：2 - p h a s e 调度策略虽然可以在某 种程度上刻划网络的动态性，但是由于它仅限于两个阶段( l a n 间和删 内) ，因而缺少对层次结构复杂的虚拟组织的刻画，可以用虚拟组织来扩展 2 一p h a s e 调度策略，但是与l a n 相比，v o 的动态性更强；c 0 嘏肼氇虽然具 有较高总体调度效益，但是较高的请求拒绝量严重影响了它的性能，相反 地，( 。一足鼢f 虽然具有较低的请求拒绝量，但较低的总体调度效益也很难 使人选择，而c o - r s b f r 只能算是c o - r s ：p 口和c 0 琅& ，的折衷，较低的请 求拒绝量和较高的总体调度效益的指标达到的程度也差强人意；基于市场 供求关系的调度算法利用经济学理论进行调度策略的分析，虽然充满新意， 但是利用“价格杆杆”进行调控，其收敛性可能较慢，也不太适合快速多 变的计算网格的应用。 缺少统一的底层支撑实现模型以实现统一的计算网格实际运行系统：目前 国内外对网格计算底层支撑系统的研究还处于初级阶段。人们虽然已经对 网格计算底层支撑系统做出了一定的研究，但是由于系统自身的庞大性和 涉及技术的多样性，使得人们还有很多探索和研究需要继续，如任务的划 分目前还是一个n p 问题，尚没有有效的方法解决? 什么样的计算资源描述 机制和发现管理模型可以使系统具有更高的资源利用率? 什么样的任务调 度算法可以使系统具有更高的计算效率? 网格计算本身类似于黑客的分布 式攻击，很可能会被黑客利用，又如何解决系统的实现和运行的安全性? 此外，目前存在的众多实现系统，如g l o b u s 、l e g i o n 、w e b f l o w 等，虽然各 自都有一定的适应领域，但是仍然还没有做到资源的无缝计算和系统的无 缝连接。 1 3 研究内容 为了解决以上存在的问题，同时为网格计算的进一步研究提供更好的想法， 本文旨在对网格计算的核心之一一训算任务渊度算法进行深入研究。但是考 虑到计算任务调度算法的实施设计的其他技术环1 ，众多，特别是硝= 调度之阿的 网格计算任务调度算法的研究与实现东南大学硕士学位论文 计算资源发现管理、调度之后调度成果的性能评价等。鉴于此，本文的研究内 容主要包括以下几点： 计算资源发现和管理模型 计算网格的基石是众多的计算资源，但是由于计算网格的根本特性是随机 的共享，所以众多的计算资源存在着种类繁多、服务不确定，能力不统一 等性质，因此设计出一个模型能够快速并且准确、有效地发现和管理计算 资源是本文研究的重点之一。 计算任务调度算法研究 一个运算量巨大的任务能否在网格环境下正确、快速和高效的运行和运行 成功，与高效任务调度算法密不可分，因此本文需要重点对计算任务调度 算法进行研究。 多种算法的性能比较 计算任务调度算法研究的目的是要寻找在某一或某些测度上更好的调度算 法，但是如何评价算法的优劣，需要对算法进行形式化分析或仿真的网络 环境下的模拟比较。 侧重任务调度的网格系统设计模型的建立 建立一个逻辑上侧重任务调度的网格系统设计模型，从而更好地实现所提 出的计算任务调度算法以及对多种算法进行比较。 性能评价模型的建立 对算法的优劣进行比较是需要一定的比较策略和模式的，并且这些比较策 略和模式是建立在某个或多个测度上的，这些测度之间的关系如何刻画， 才能比较客观、公正地分析算法、评价算法，同样需要构造合适的评价模 型。 仿真系统的实现 计算网格涉及的相关算法、机制和模型，在实际实施于i n t e r n e t 之前，均需 要进行模拟和仿真。但是这些算法、机制和模型绝大部分需要考虑i n t e r n e t 所独有的不稳定性和用户的q o j 需求，因此怎样使仿真系统可以模拟出 知f 绷鲥的上述特性，以及将提出的算法、机制和模型在模拟的h t e r n e t 上 进行仿真，也是本文研究的重点之。 1 4 研究方法和技术路线 计算资源发现和管理模型 目前的计算资源发现和管理模型虽然为我们提供了多种形态的发现和管理 资源的策略，但是却没有为我们提供一种对智能化宏观调控、快速i f 向应资 源变动等需求的整合。熬r 此本文将确：i 众彩的h 蜉资源发现和管理 网格计算任务调度算法的研究与实现东南大学硕士学位论文 模型的基础上，仿效人类社会政治管理的模型，提出一种基于“上访下察” 的资源发现管理模型。 计算任务调度算法研究 计算任务调度算法是提高网格计算整体性能的关键，在传统分布式计算领 域和计算机网络领域都对其进行了较多的研究，但是如何满足计算网格的 独特性以及针对i n t e r n e t 的具体境况进行合适的调整或重新设计，将是本文 的研究重点。因此，本文将提出一种基于信任和s 测量的任务调度算法， 希望可以将i n t e r n e t 的特性考虑进去，并且在一定程度上满足用户服务质量 ( q o s ) 上的需求。 多种算法的性能比较 只有通过性能的比较才能说明某种算法的优劣性，因此本文将首先在自行 设计的仿真系统内对多种算法进行仿真模拟，然后在得到的模拟结果的基 础上，结合评价性能评价模型，对多种算法进行定性的论证和说明。 侧重任务调度的网格系统设计模型的建立 本文将在吸取c o r b a 系统的架构模式和相关技术的基础上，结合计算网格 的随机共享的特点，提出一种网格系统设计模型，以重点支持计算任务调 度算法的实施以及相关安全传输、用户门户、资源发现和管理等实现。 性能评价模型的建立 计算网格系统的性能评价模型的建立以及评价标准的制定直接关系到计算 任务调度算法的效果。鉴于计算网格的特点和i n t e r n e t 本身所具有的不确定 性、突发性、不稳定等特点，因此本文将在性能评价模型的研究上融入一 定的冗余计算手段，以及关于计算任务完成的q o s 测度方面的约束，以保 证整个计算任务可以高效、快速地完成。 仿真系统的实现 仿真系统是本文研究中实践编程丌发环节的重点，也是难点。仿真系统以 j a v a 语言丌发，以单机运行版本的形式存在，但是也提供了为今后网络仿 真开发的接口。仿真系统需要模拟的i n t e r n e t 上的随机因素，均采用排队论 相关知识构建；同时，当前版本的仿真系统虽然重点为计算任务调度算法 的研究服务，但是仍然系统地、有预见性地提供网格计算研究其他方面( 如： 资源描述、资源发现管理、安全传输等) 的接口。 1 5 文章结构 本文的总体结构大体分为三个部分：第一部分理论研究，主要包括第一至 第五章：第二部分系统实现，主要为第六章；最后第七章，总结全文。具体的 内容安排如下： 网格计算任务调度算法的研究与实现 东南大学硕士学位论文 第一章首先简单介绍了网格计算的应用和研究背景；然后重点针对计算资 源发现和管理模型、计算任务调度算法和底层支撑代表系统这几个计算网格的 关键技术，讨论了当前的研究现状和存在的问题；接着阐述了本文要研究和解 决的问题以及采用的研究策略。 第二章首先概述了基于“上访下察”的资源发现管理模型，然后针对其核 心模块进行了详细的浇明，最后定性地论述了该模型的优点。 第三章为本文的重点和核心。在对任务调度定义、信任机制、i n t e r n e t 的 q o s 需求的说明的基础上，提出了基于信任和q 。s 测量的任务调度算法以及该 算法的j a v a 类描述；然后讨论了第二章提出的基于“上访下察”的资源发现管 理模型对该算法的支持；最后在仿真系统模拟的结果之上分析该算法的特点。 第四章结合c0 _ 船爿系统的架构模式和相关技术，设计出侧重于任务调度的 网格计算底层支撑系统的实现模型，并对其运行结构、体系结构、贺信组成部 件进行说明，随后对其进行定性的分析。 第五章结合计算任务的定义和用户对任务计算的q o s 需求以及计算网格的 特点，提出计算网格任务调度算法性能评价模型。 第六章详细地介绍计算网格仿真系统的体系结构和各功能模块的说明、以 及运行样例的演示。 第七章对整篇论文进行总结，并对未来工作进行展望。 网格计算任务调度算法的研究与实现东南大学硕士学位论文 第二章基于“上访下察”的资源发现和管理模型 虽然目前的资源发现和管理模型，如集中式、分布式、层次式和基于多a g e n t 式等， 为我们提供了多种形态的发现和管理资源的策略，但是却没有为我们提供一种对智能化宏 观调控、快速响应资源变动等需求的整合。因此，我们在结合集中式、分布式、层次式和 基于多a g e n t 式等四种资源发现管理模型的基础上，提出了一个改进的基于“上访下察” 的资源发现管理模型( f e e d b a c ka n di n v e s t i g a t i o nb a s e dr e s o u r c e sd i s c o v e r ya n d m a n a g e m e n t m o d a lf d d b r d & m m ) ：首先图文并茂地介绍了模型的总体结构；然后详细地 对模型的核心模块进行分析描述；最后，通过定性比较揭示出模型的优点。 2 1 模型总体结构 f d d b r d & m m 模型( 如图2 1 ) 采用层次式管理结构，以虚拟组织为基本管 理单位，利用众多可移动a g e n t 的探寻，以及基层计算资源或者管理结点的汇 报，对整个计算网格现有的全部计算资源进行统一的管理，同时及时地发现新 计算资源的加入和原有计算资源的退出。 图2 1f & i b r d & m m 结构图 与传统的层次式和基于多a g e n t 式资源发现管理模型不同，f & i b r d & m m 模型为了加快对计算资源动态变化的反映速度和准确性，除了提供常规管理通 道以外，还提供了另外两种特殊的通道：e 访通道和f 察通道，以使资源变化 网格计算任务调度算法的研究与实现东南大学硕士学位论文 信息可以及时地反映到根管理结点处为任务计算提供更有效、准确的支持；同 时，根管理结点也可以通过下察通道直接向某个具体的虚拟组织甚至是某个具 体的计算资源下发指令、直接交流，从而加快了整个计算网格整体计算效率， 而这样的高效率也是层次式资源管理模型“层层下达”和基于多a g e n t 式资源 管理模型分发a g e n t 、移动a g e n t 所不能具备的。 具体的模型描述如下。 2 2 核心模块 2 2 1 管理结点( m a n a g e m e n tn o d e s , m n ) 管理结点是f & i b r d & m m 模型实现的核心，也是从层次式管理模型汲取来 的关键技术。从管理范围和所处地位的角度，可以将管理结点划分为：根管理 结点和虚拟组织内管理结点。也就是： 整个计算网格任一时刻有且仅有一个根管理结点以实施全局调控。当然可以 出于冗余保护的考虑，为整个计算网格安排若干个备份根管理结点，但是这 些备份根管理结点在主根管理结点正常运行时处于“休眠”状态，即对资源 管理没有任何影响，同时对整个计算网格所有计算资源来说也是“透明的”， 而对主根管理结点来说需要时刻保证这些备份根管理结点上的信息与自己 保持一致。当且仅当主根管理结点发生崩溃时，这些备份根管理结点才可以 通过选举算法产生出新的主根管理结点来接管整个计算网格的资源管理工 作。 虚拟组织的生成( 包括虚拟组织的迭代生成) 采用组播组生成技术，虚拟组 织的维护( 包括虚拟组织的迭代维护) 也采用组播组维护技术。 每个虚拟组织存在一个管理结点以发现和管理其统辖范围内所有结点的资 源。虚拟组织内管理结点的冗余备份可以采用根管理结点相同的备份策略。 当某个虚拟组织发生资源变动时，该虚拟组织的管理结点收集这些信息，然 后按照管理树结构由叶向根，利用常规通道将变动信息上传给它的直接上 级，一直到根管理结点，然后根管理结点根据需要以组播的方式法送给所有 下属管理结点。 网格计算任务调度算法的研究与实现东南大学硕士学位论文 2 2 2 上访站( f e e d b a c kp o i n t , f p ) 与通道( c h a n n d ) 上访站和通道概念是f & i b r d & m m 模型的创新之处，也是f & i b r d & m m 模型优点体现的最重要的支持。f d d b r d & m m 模型除了提供常规管理通道以 外，还提供了另外两种特殊的通道：上访通道和下察通道。这两种通道只有在 特殊的时刻才能使用： 上访通道：允许普通( 基层) 计算结点直接向所在虚拟组织以上的管理结点 ( 甚至是根管理结点) 反映自己或同级结点计算资源的信息；但是考虑到这 种上访过程很容易造成上访连接的拥塞，因此需要根管理结点规定上访时间 片间隔。 下察通道：允许上级管理结点( 包括根结点) 绕开正常通道上的管理结点， “微服私访”地、直接地了解基层计算资源信息，取得第一手更新资料，同 时一旦发现资源更新，立即进行资源均衡、调度等宏观调控措施。由于考虑 到下察方向是由根到叶，所以这种通道的开放时间具体由各级管理结点自行 控制，但是若开放时间存在冲突，则管理树上等级低( 离根较远) 的管理结 点将听从等级高( 离根较近) 的管理结点的统筹安排。 上访站与上层管理结点( 包括根管理结点) 是上访通道的两个端口。每个虚 拟组织中都