（计算机系统结构专业论文）网格多集群环境和计算市场环境中的作业调度和资源分配研究.pdf

摘受 摘要 网格是建立在i n t e l l l e t 上的一种新型的信息技术基础殴施，目的是无缝地集成j “域资源 来合作解决问题，实现计算资源、存储资源、通信资源、软什资源、信息资源、知识资源的 全面共享。如何有效管理j “域的、异构的、动态的、自治的网格资源是网格技术研究的重点 和难点传统的作业凋皮方法难以奏效。 本文首先介 “网格的概念、演变和分类，分析了网格凋度面临的问题。随后第二章在同 顾传统调度理论的基础上。结合网格环境， 纳了调度问题住网格环境中的新特征：资源人 规模异构性、环境动态不可靠性以及面向川户需求的特性。从两种典型环境入手，通过分析 网格社l 叉：多集群环境硐l 网格计算市场的特点，针对多集群环境提出基丁“全局局部”模式 的层次调度方法，针对计算市场提出基丁双向选择的分布式调度方法。 本文第二章提出了多集群一致监控的解决方案，设计了一种臼描述方法以解决异构资源 信息的公共表示问题，基丁g a n 刚a ，g r i d v i e w p b s 等监控l ：具设计实现了一个通川的资源监 控系统。殴计了一种臼适应的r t t 感知的最小生成树策略以改善系统的可扩展性。 论文第四章针对多集群提出了“全局本地”的二阶段超级凋度算法。针对计算密集型 麻川，在传统的批调度算法中加入对任务完成时限h j 户q o s 的考虑。提山了多集群环境f o o s 感知的批凋度算法，并廊川了：多集群的全局队列凋度中，与传统批凋度算法相比，任务 按时完成比率有明显提高。同时，该算法对任务执行时间的预测误筹也具有良好的适应性。 论文第元章致力丁研究经济市场和信任评估相结合的激励机制，把信任机制融入b u y y a 的网格计算市场模删提出了网格中信任感知的资源交易模刑( g r i dt r u s ta w a r er e s o u r c e t r a n s a c t i o nm o d e l ，简弓g t a n 模砸) ，详细研究g t a n 模硝中的实体、模块、交易流程。 在g t a n 模刑中，把信任度作为衡鹫。1 ，点交易诚信度的重要指标，激励1 1 ，点履行已达成的 资源交易合约。引出了g t a r t 中两个关键问题，即任务代理的资源选择问题和资源代理的 任务接受问题。 论文第八章从刚户代理角度出发，提出了一种基丁信任过滤的资源选抒方法。该方法首 先根据川户信任需求过滤低可信资源，然后对剩余高可信资源综合考虑其价格雨i 风险冈素， 最后给出了最小机会成本启发式算法。实验表明，该方法能对供求舣方产生激励：对资源方 保证可靠资源提供者的整体利润：对州户方能显著降低作业火效率、减少成本8 1 0 。 论文第七章从资源代理角度出发，提出基丁收益和成本计算的任务接受策略，根据刖户 提交任务的相关信息，计算接受任务的沉没成本和机会成本以决定是否接受任务，使得资源 捉供者利资源请求者都实现臼身的经济目标，提高了服务方的收菇。 论文第八章基丁g t a r t 模融，利朋供求规律，没计了一种分布式i 舄度系统，实现了 o p p s i m 模拟器以模拟该系统。该系统采川川户与资源进行舣向选抒的模式，通过启发式的 策略，动态调1 ，资源价格，引导刚户和资源的行为。模拟结果表明该系统能有效解决网格环 l a b s t r a c t a b s t r a c t g r i di san e wt y p eo fi n f o r m a t i o nt e c h n o l o g yi n f h s t r u c t u r eb a s e do nt h ei n t e m e t ，w h i c hg o a l i ss e a m l e s s l yi n t e g r a t i n gw i d ea r e ar e s o u r c e st os o l v ep r o b l e m sa n da c h j e v et h ec o m p r e h e n s i v e l y s h a r i n go fc o m p u t i n gr e s o u r c e s ，s t o r a g er e s o u r c e s ，c o m m u n i c a t i o nr e s o u r c e s ，s o r w a r er e s o u r c e s ， i n f o n l l a t i o nr e s o u r c e sa n dk n o w l e d g er e s o u r c e s t h et r a d i t i o n a l j o bs c h e d u l i n gm e t h o di s i n e l ! f e c t i v ef b rc h ed i s t r i b u t e d ，h e t e r o g e n e o u s ，d y n a m i c ，a n da u t o n o m o u sr e s o u r c e si nt h eg r i d f i r s f l y ， t h ed i s s e 九a t i o ni n t r o d u c e st h ec o n c e p t ， e v a l u a t i o na n dc l a s s i n c a t i o no fg r i d c o m p u t i n g a f t e ra n a i y z i n gt h em a i np r o b i e m si ng “dj o bs c h e d u l j n g ，c h a p t e r 2r e c a l l st h e o 哆o f s c h e d u l i n ga n dc l ar i n e st h en e wf e a c u r e si ngr i d s c h e d u l i n g ，i e ，i a 唱e s c a i eh e t e r o g e n e o u s m a c h i n e ， d y n a m i ca n du n r e l i a b i ee n v i r o n m e n la n du s e 卜c e n t r i co b i e c t i v e i n p a r t i c u i a r ，t h e r e s e a r c hf o c u s e so nt h et w ok i n d so fg r i de n v i r o n m e n tn a m e dm u i t - c i u s t e r sa n dc o m p u t a t i o n a l m a r k e t t h e “g i o b a i l o c a l ”2s t a g em e t h o di st a k e nf o rt h em u l t i - c l u s t e r ss c h e d u l i n g ；w h i l et h e d i s t r i b u t e db i - d i r e c l i o 九a ic h o o s i n gm e c h a n i s mi sa d o p t e df b rt h ec o n l p u l a t i o n a lm a r k e t r e s o u r c em o n i t o r i n gj st h eb a s i so fm u l t i - c i u s t e rs c h e d u l i n ga n dn e e d st os o l v ei s s u e so f h e t e r o g e n e i f y a n d s c a l a b i l i t y c h a p t e r 3p r o p o s e sas e lf d e s c r i p t i o nm e t h o d f o rc o m m o n r e p r e s e n t a t i o no fh e t e r o g e n e o u sr e s o u r c e si n f o r m a t i o n au n i v e r s a lr e s o u r c em o n i t o r in gs y s t e mj s i m p l e m e n c e db a s e do nm o n i t o r i n gl o o i ss u c ha sg a n g l i a ，g r i d v i e w ，a n dp b s ，e t c a na d a p t i v e r 1 1 ：a w a r em s ta l g o r i t h mi s d e s i g n e dt oi m p r o v es y s t e ms c a l a b i i i t y e x p e r i m e n ts h o w st h i s m e t h o dr e d u c e si n t r u s i v eo v e r h e a da n d 1 t 1 p r o v e sr e a l t i m ea b i l i l y a 俞e rt h a t ，c h a p t e r4p r o p o s e sa n d ；m p l e m e n t st h e “g l o b a i l o c a l 2s t a g es u p e r s c h e d u l e r m o d e f a i m i n ga tc o m p u t i n gi n t e n s i v ea p p l i c a t j o n s ，t h i sc h a p t e rp r e s e n t saq o s a w a r eb a t c h m o d e s c h e d u l i n ga i g o r i t h m t h ea l g o r i c h m i su s e di nt h eg i o b a lq u e u es c h e d u i n g c o m p a r e dt o t r a d i t i o n a lb a t c h m o d es c h e d u l i n ga i g o “t h m ，i tp r o v e st ob ew i i he q u a lt h r o u g h p u to fs y s t e mb u t w i t h i m p r o v e di n t i m ec o m p i e t er a t j o t h i sa l g or i t h ma i s op r e s e n t sn i c ea d a p t a b i l i t yu n d e r p r e d i c t i o ne r r o ro ft a s ke x e c u t i o nt i m e 。 c h a p t e r5f o c u s e so nt h ei n c e n t i v em e c h a n i s mw i t hc o m b i n a t i o no fm a r k e ta n dt f l j s t b y i n t e g r a t i n gt h et r u s tn o t i o ni n t og r i dm a r k e tm o d e i ，t h ed i s s e n a t i o ni n t r o d u c e st h eg r i dt r u s t a w a r er e s o u r c et r a n s a c t i o nm o d e i ( g t a r t ) ，a n dd e s c r b e sd e s j g ni d e a s ，t h ee n t i t i e s ，c o m p o n e n t s a n dt h et r a n s a c t i o nf l o wi nt h em o d e i t h et r u s ti ss e ta sa ni m p o r t a n lm e t r i cm e a s u r i n gt h e r e p u t a t i o no fp e e f s nt h em a r k e tt r a n s a c t i o n s ，w h i c hc a nn o to n l ys t i m u i a t ep e e r st oo b e yt h e t r a n s a c t i o nc o n t r a c c ，b u ta l s op r o v i d ea ni n c e n t i v ef o rh o n e s ts e r v i c ep r o v i d e r s t h i sr a i s e st w ok e y i s s u e s ：h o wt os e l e c ta p p r o pr a t er e s o u r c e sa n dh o wt oa c c e p tp r o p e r j o b s ? t h u sc h a p t e r6p r o p o s e sat r u s t - f i l l e r e da p p r o a c hi sf o rr e s o u r c es e l e c t i o nt ob r i d g et h i sg a p i i i 中国h 学投术，l 、学博f j 学位论义 t h i sa p p r o a c hn r s tn i t e r sm o s to fc h el o w e r _ t r u s tr e s o u r c e sb a s i n gu s e r st r u s td e m a n d t bt h e r e m a i n i n gr e s o u r c e sa b o v ed e m a n d ，i tt h e nu s e sam i n i m a io p p o r t u n i t y c o s ta i g o r i t h mt og u i d et h e j u d g m e n c i t sm a i ni d e ai st ot a k e sb o t ho fp r i c ea n dr i s ki n t oc o n s i d e r a t i o n s s j m u i a t i o n ss h o wt h e a p p r o a c hg i v e st w o - f o l di n c e n t i v e s i te f 艳c t i v e l yg u a r a n t e e sp r o n to fr e l i a b l er e s o u r c e s ，r e d u c e s j o bf a ilu r er a t ea n ds a v e sc o s t8 l0 a v e r a g e l y c h a p t e r7i n v e s t i g a t e sam a r k e t - b a s e dt a s ks e r v i c ei ng i r de n v i r o n m e n t f r o mp r o v i d e r s s t a n d p o i n ta n db a s i n go nr e l a t i v ei n f o r m a t i o np r o v i d e db yu s e r s ，t h ep r o v i d e rc o m p u t e ss u n kc o s t a n do p p o r t u n i t yc o s ti fr e c e i v i n gt h et a s kt om a x i m i z ei t s e l fp r o f i t t h ee x p e r i m e n ts h o w st h a tt h e s c h e d u l e rf h r t h e rr e d u c e st h ec o s t0 fr e s o u r c e sp r o v i d e r sa n di m p r o v e st h e i rp r o n t f i na l l y 。b a s e do nt h eg - t a nm o d e l ，c h a p l e r8p r e s e n t sad i s t r b u t e dr e s o u r c es c h e d u 1 n g s y s t e mf b rg r i de n v i r o 九m e n tu s j n gs u p p l ya n dd e m a n dc h e o r y t h eo p p s i mi si m p i e m e n t e dt o f a c i i i c a t et h es y s t e ms i m u l a t i o n t h es y s t e mp r o v i d e sab i - d i r e c t i o n a lc h o o s i n gm e c h a n i s ma n da q o sg u a r a n t e e i n gm e c h a n i s mf o ru s e r sa n dr e s o u r c e st os u p e r v i s et h e m h e u r i s t i c a l l y t h e s i m u l a t i o nr e s u l to ft h es y s t e ms h o w st h a tt h es y s t e mi ss c a l a b i e ，f l e x b l e ，a n dc a p a b l eo fh a n d i i n g i o a db a l a n c ew e l l m e a n w h i i ei ig u a r a n t e e sq o so ft a s k s r a s ka c c o m p l i s h m e n tr a t i oi sg r e a t e r t h a nt h a ti nn i m r o d gb v2 2 5 b ya n a l y z i n gt h ec h a r a c t e r i s t i co fg r i ds u c ha si a 唱e s c a i e ，h e t e r o g e n e i t y ，u n r e i a b i | t ya n d u s e 卜c e n t r i c ，t h ed i s s e n a c i o ng i v e sd e e p i ya n a l y s i sa n db e n e f i c i a ip r a c t i c eo nt 、v ot y p i c a lg r i d e n v i r o n m e n t i ti sv e 吖u s e f u io ft h e “g l o b a l - l o c a l ，2s t a g em e t h o df o rt h e m u l t i c i u s t e r s s c h e d u l i n g m e a n w h i l et h ed i s s e r t a l i o np r o p o s e st h eg t a nm o d e lw h i c ho 唱a n i c a l l yc o m b i n e s t h em a r k e tm e c h a n i s ma n dt r u s tm e c h a n i s m ，a n dt h ei n c e n t j v e - dr i v e nd i s tr i b u l e ds c h e d u l i n g m e t h e ds h o w st h eb r a n dn e wv i e wa n dn n ep e r s p e c t i v ef o rt h ef u t u r eo ft h eg r i d k e y w o r d s ：m l i l i i - c i u s l e rg r i d ，g r i dc o m p u l a t i o n a lm a r k e t ，g l o b a ls c h e d u l e r ，r e s o u r c e s e l e c t i o n ，j o ba d m i s s i o nc o n t r o i ，o p p s j ms i m u l a t o r i v 幽索j v i i i 图索引 图1 1 网格技术发展经历的二个阶段2 幽i 2 一个典丌! 的网格作业凋度戍川场景4 剀1 3 主要的网格项目代表8 幽i 一4 儿个代表性网格项目标忠9 图1 5 论文组织结 = = f 1 2 图2 1 凋度系统的基本框架1 4 图2 2 与i ：期相芙的目标函数1 7 图2 3 尽力而为( b e s te 仃o r t ) 【5 6 】2 1 幽3 1u g m f 的架构2 4 幽3 2 一致性数据提供者的设计2 5 幽3 3 二种典型的数据访问拓扑结构2 6 幽3 4c n g r i d 监控系统快照2 7 图3 5 二种拓扑的入侵开销对比2 8 图3 6 二种拓扑的响应时间对比2 8 幽4 1 多集群超级调度的流科幽。3 0 幽4 2 批调度饽法的普遍性描述3 3 幽4 3r a n k 区问分布3 4 图4 4o o s 感矢【i 的批调度算法伪代码3 4 图4 5m l n m i n 与o o s 感矢i jm i n m i n 任务按时完成比率比较d r ( o ，5 ) 3 6 幽4 6m i n m i n 与o o s 感知的m j n m i n 任务按时完成比率比较d r ( o ，l o o ) 3 6 幽4 7 基丁1 0 预测误筹的m i n m i n 平q o s 感失l | 的m l n m i n 算法m a k e s p a n 3 6 幽5 1g t a r t 交易流稗图4 5 幽5 2 投标定价交易的二种典刑结果4 6 幽6 1 随着交易次数增加，可靠资源所l i l 利润比例5 3 幽6 2 场景二中使川不同的资源选择方法时作业火效率的比较5 4 幽6 3 场景二中使州不同的资源选择方法时州户成本的比较5 4 幽6 4 场景一中使川不同的资源选择方法时刖户成本的比较5 5 图7 1 基丁市场的任务调度模刑5 7 图7 2 不存在最高赔偿金时服务方收盗随时间变化的情况5 8 幽7 3 殴萱最高赔偿金时服务方收蕊随时间变化的情况5 8 图7 4 收箍与机会成本关系图6 l 幽7 5c 【和b 变化曲线幽6 l 图7 6c 【和d 调仃卜单何时间内收益的比较6 l 幽8 1 网格资源凋度系统逻辑框幽6 5 幽8 2 系统序列幽6 6 幽8 3o p p s i m 模拟器框架6 7 幽8 4o p p s i m 交互界面6 8 剀8 5 资源完成任务数分布幽6 9 图8 6 所有资源价格变动图7 0 剀8 7 任务提交次数分布7 0 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 坼厂月丫日 劫莉易 渺。6 2 ， 第1 章缔论 第1 章绪论 1 1 研究背景 人类住认识世界和改造憎= 界的实践中，对更高计算能力的需求从来都没有i ：步。近十年 来，随着计算技术和通信技术的琶速发展，我们止逐渐可以将人范嗣内的更多计算设备组织 在一起共同解决问题。使j j i n t e m e t 或专用高速网络作为联系的桥梁，研究人员可以整合这 些地理分布的孤立的计算机系统，形成一个更人规模协同共享的基础殴施平台，丁是“网格 计饽”( g r i d ) f l 】概念廊造而生。为此，近年米世界上很多国家和地区开展了网格相关研究， 并总体上经历了二个阶段，这些甲划实践给我f l 、j 带米了i 者多启示，而能否有效进行资源管理 和作业凋度对网格系统的成败起关键作刖。 1 1 1 网格的内涵 自从i 9 4 6 年世界上第一台计算机e n l a c 问世以来，计算机彻底政变了人类处理信息的能 力。从人刑士机时代刨p c 时代，再剑今大的网络时代，计算机技术得剑了k 足发展，其处 理能力曰新月异。然而随着科学的发展，人类在认识世界和改造世界的实践中，对更高的计 算能力的渴望从米都没有冈为单机计算能力的增k 而缓解。现实世界的许多科学问题无法用 单个计算机有效计算，例如利用f n t e m e t 上成千上万台计算机搜索外星人的s e t i h o m e 【2 】， 甲在2 0 0 2 年处理速度可以保持在6 0 t e r a f l o p s ；确定蛋白质的二维形状的r o s e t t a h o m e 【3 】 至今有效速度高剑7 2 8 t e r a f l o p s ；另外从2 0 0 5 以米的欧洲高能粒子实验侮大产生l5 p e t a 字 1 ，的数据，甚至欧洲作为一个整体也无法有效分析积处理l c g 试验的海鼙数据【4 】。 网格是建立住i n t e r n e t 上的种新刑的信息技术基础设施。它将高速且联网、高性能计 算机、人璎数据库、传感器、远料设备等融为一体，实现计算资源、存储资源、通信资源、 软彳，j ：资源、信息资源、知识资源的全面共享。2 0 世纪8 0 年代人们为了满足人规模麻川对计 算资源的需求，提出了元计算( m e t a c o m p u t i n g ) 5 】的概念，将一纽通过j 域网连接起来的性 质不同的计算资源集合起米，作为一个单独的对川户透明的计算环境向刚户提供计算服务- 1 9 9 5 年的i w a y 项目 6 是元计算的典刑代表。1 9 9 8 年，网格研究奠基人i a nf o s t e r 和c a r i k e s s e i m a n 住文献【7 中首次对网格进行定义：计算网格是一个包含硬 i ，l ：和软 ；，| ：的基础设施， 它能对高端计算能力提供可靠的、一致的、普遍的和不昂贵的接入。2 0 0 1 年l a nf o s t e 等人在 文献【l 】中进一步指出：网格芙心的是在动态的、多机构的虚拟绲织中协讽资源共享私协图 解决问题，核心思想是在一组参与饵点( 资源提供者和消费者) 中协商资源共享管理的能力， 利瑚协商得剑的资源池共同解决些问题。2 0 0 2 年1 a nf o s t e 提出了网格的二个判断标准【8 】。 ( 1 ) 协凋1 卜集中控制的资源：网格整合各种资源协凋各种使州者，这些资源和使川者 处丁r 不同的管理域。网格廊该解决住这种分布式环境中的安全、资源管理策略、使川费川利 成员权限等问题。 【2 ) 使川标准、开放和通川的协议平i | 接口：网格建立在多功能的协议和接口之上，这些 协议羽i 接口刚丁| 解决认证、授权、资源发现和资源存取等基本问题。 中国f ： 学技术人学博1 j 学位论义 ( 3 ) 提供1 | 平凡的( n o n t r i v i a l ) 服务：网格允许协调使用资源，以得剑多种服务质域，满 足不同使川者需求，如系统响应时间、吞吐簟、有效性、安全性等。 与i a nf o s t e r 严格限定网格的范同不同，有学者提出j 。义网格的概念，认为只要是在广域 网范闱内的资源共享与服务都可以称为网格，如现在被学术界和商业界都1 f 常看女，的云端计 算被视为网格的形态之一 9 】( c i o u dc o m p u t i n g ) 。尽管! 学者们对网格技术解释不同。但其核心 内涵综合起爿说就是利川网络将分散在不同地理位置的电脑组织成一台“虚拟的超级计算 机”，让刚户全面共享网格上的计算资源、数据资源、信息资源、软 ：，| ：资源、存储资源、通 信资源、知识资源、专家资源。 1 1 2 网格的演变 网格计算从诞生剑现在可以分为二个阶段 i o ，】，如图1 1 所示。 第一阶段是网格计算的萌芽阶段( 1 9 9 5 年之前) ，研究内容是关丁千兆网络的实验床以及 一些元计算方面的i ：作。典型的代表是f a f n e r 【1 2 】和i w a y 6 】两个项目。这个时期的网格 特点是把超级计算机1 y 点连接起米，为高性能虑川提供计算资源。 第二阶段是从1 9 9 5 年剑2 0 0 0 年左右，以人规模计算和数据共享的科学研究为目标。典型 的代表有g i o b u s 【1 3 】、l e g i o n 【1 4 】等项目。这个时期的网格计算要解决的问题涉及网格计算 的异构性、可扩展性、适应性等，网格计算的安全也被提剑了一定的高度。这个时期的主要 i ：作是支持人规模计算和数据中间件的开发，建立了面向协议和模块的网格体系结构。 第二阶段是从2 0 0 1 年至今，以商业廊刚与科学研究为目标，代表体系为开放网格服务结 构o g s a ( o p e ng r i ds e r v i c e a r c h i t e c t u r e ) 1 5 】，具体实现包括o g s i 刨w s r f 的演化【1 6 】，以及 对w 曲服务标准的同1 。这个阶段的士要特点是面向服务的体系结构。 第阶改：嗍杼 萌芽娜t 第二阶段：煳格的铲期诚齄第阶改：嘲i f f 窟氍期 7 一l zi 施；qb c 彀肼。! 。凡：i 跬；疆翟j 芦l 或避l lr f ： ，i fi f l ? ： 9 篱；! 怒，、v篆然葛瞥。汀i 蒜淤霉竺鬻姜 ! - f cm 圳： j w 5 批扣 tj l t b u h ，c 心o 1 9 q 5 ：i ： l ) 苓：f 】d 1 1q ： 2 0 0 j 一4 ： 幽卜i 州格技术发腱绛j 儿的三个阶段 在朱来，我1 f j 憧憬网格能像今天的且联网一样作为成熟的基础设施，为社会和个人生 活提供经济的网格服务，促进社会的进步，改善人们的生活。 1 1 3 网格的分类 甲期的面向科学研究发展剑现住的面向商业廊川，网格的席川范同越来越j “。根据系 统提供的服务不周，可以将网格系统分计算网格、数据网格、信息网格雨l 知识网格。 ( 1 ) 计算网格( c o m p u t a t i o ng r i d ) 7 】。这是最甲的一类以解决计算密集州任务为目标的 网格计算，可以将地理上分布、系统异构的各种高性能计算机、数据服务器、人璀检索存 储系统和可视化、虚拟现实系统等，通过高速互连网络连接并集成起来，形成对州户相对 2 第l 章绪论 透明的虚拟的高性能计算环境，以解决需要超人规模的计算量才能完成的科学研究问题。 计算网格系统是高性能计算应用发展的必然结果，它融合了目前高效可扩展的分布式并行 计算技术、计算机网络技术、面向川户的群序改计技术、可视化技术、高效的稃序编译模 型乖l 执行引擎技术等i 者多方面的最新研究成果。计算网格研究的内容包括资源的管理问题、 计算资源的协作问题、作业调度、安全管理问题、高效的程序编泽模型和执行弓i 擎等。 ( 2 ) 数据网格( d a t ag r i d ) 【1 7 】。计算网格之后出现的一类以解决数据密集刑任务为目标 的网格计算。住现代科学研究帚i 廊崩领域中。人鼙的数据是重要的资源，例如全球气候模 拟、高能物理、生物计算、战场仿真、核模拟、数字地球、人规模的信息和决策支持系统 等麻用其数据量将达到几十t e r a b y t e 至p e t a b ”e 的级剐。地理上广泛分布的该领域的科 研i ：作者或用户都希望能够访问币lj 分析这些庞人的数据，但其分析方法往往是计算复杂、 计算鼙人，许多数据分析处理要求干亿次或万亿次规模的计算能力。现有的数据管理体系 结构、方法币技术已经不能满足人f f j 对高性能、人容苗分布存储和分布处理能力的要求。 冈此，住计算网格的荩础上人们提出了数据网格的构想，以解决上述戍刖所面临的问题。数 据网格的研究内容包括元数据管理和信息服务，数据访问，复制管理，交全技术，高速数 据传输机制，资源凋度优化与远科执行等多方面的内容。 3 ) 信息网格( 1 n f o r m a t i o ng r i d ) 【1 8 】。这是继计算，数据网格之后出现的一类以解决信息 共享为目标的网格计算。利用现有的网络基础设施、协议规范、w 曲和数据库技术，为用 户提供一体化的衙能信息平台，其目的是创建一种架构在操作系统和w e b 之上的墓丁 i n t e m e t 的新一代信息平台利软f ，f ：基础设施。在这个平台上，信息的处理是分布式、协作和 智能化的， j 户可以通过单一入口访问所有信息。信息网格追求的最终目标是能够做剑按 需服务( s e r v i c eo nd e m a n d ) 。 ( 4 ) 知识网格( k n o w l e d g eg r i d ) 【1 9 ，2 0 】。知识网格是一个智能且联环境，它能使圳户或 虚拟角色有效地获取、发布、共享和管理知识资源，并为川户和其他服务提供所需要的知 识服务，辅助实现知识创新、协同l ：作、问题解决和决策支持。它包含了反映人类认知特 性的认识论雨i 本体论。矢u 识网格研究的侧重点是智能信息处理，主要研究内容包括语义网 ( s e m a n t i cw 曲) 、知识管理( k n o w i e d g em a n a g e m e n t ) 、知识本体( o n t o i o g y ) 、智能主体 ( a g e n t s ) 、一体化智能信息平台等等。 本文讨论集中在计算网格。 1 2 问题的提出 计算网格的有效性很人程度上取决丁其作业调度的有效性和效率【2 l 】。网格作业凋度 可以定义为将作业映射剑各管理域的网格资源的过程。一个典型的网格调度应川场景如图 卜2 所示。刚户首先把作业交给全局的网格凋度器，网格调度器平本地凋度器经过协商， 基r 一定的策略把作业最终提交剑合适的资源【2 2 】。 3 中国科学技术人学博 j 学位论艾 幽卜2 一个典型的纠格作业涮度心用场景 网格调度与本地调度的明显区别在丁其调度的对缘跨越多个管理域，不同的组织采川 不同的策略管理资源，而且资源州户和资源捉供方的目的可能不一致。传统作业凋度问题 本身是一个1 f ! 常重要的难题。考虑调度问题的基本目标函数跨度( m a k e s p a n ) 【2 3 】，即凋度系 统如何有效地分配网格资源，以实现整个系统内网格作业完成时间最小。给定资源集合， 从那些资源中选择合适的资源子集，使之满足预先定义好的约束条彳，l ：，井找剑最优的 m a j ( e s p a n 是n p 完全问题 2 3 】。网格环境中由丁网格作业本身的异构及需求的不同，其所 需资源住j 域上分布、本质上异构、由不同的个人或组织拥有、有不同的存取和花费模式、 负载和可州性动态变化，使得网格环境下的作业调度问题充满挑战。 首先由丁网格的人规模化，机器环境不再是单一的同构系统，原有仅考虑单个资源或 者单个集群的凋度方法难以直接麻川到网格环境中【2 4 ，2 5 】；需要采取层次化或分布式的可 扩展凋度模式。 其次由- 网格动态特点，资源的加入和退出楚允许的，冈此出现资源故障或者资源不 可达在网格中是一种常态，特别楚在缺乏信任的不可靠环境中，在调度中必须考虑“故障” 约求。对系统状态的准实时监控【2 6 2 9 】和i 激励资源保证可靠状态【2 6 ，3 0 3 2 】都是必要的。 同时由丁网格最终日的是满足川户的服务需求，其性能指标不再单纯以系统性能为目 标( 如吞吐鼙雨i 资源利川率等) ，在资源分配和调度时，系统为中心( s y s t e m - c e n t r i c ) 转向以用 户为中心( u s e 卜c e n t r i c ) 【3 3 3 5 】是网格调度的新特点，冈而目标函数常常! f 1 结r 刚户的效刚 ( u t i l i t y ) ；再考虑剑网格环境中不同实体的兴趣和利益，如资源提供者的目标是最人化资源 的纯收益，而朋户的目标则通常是花最少的费坩尽快完成自己的作业。因此其收豁函数也 会譬现出个性化特点，如何繁化个体偏好并指导调度决策，是1 卜常必要的一项f ：作。 1 3 研究现状和主要的网格项目 作q p 调皮和资源管理是戍川刑网格项目需要考虑的核，心问题，已有的网格项目通常面 4 第l 章绪论 向部分特性做了相应的改进和优化r ：作。它 l j 或者从更高的系统层面( 如安全性，灵活性， 拓扑，面向对象) 考虑调度系统的设计和实现，冈而把更贝体的l ：作留给了本地调度系统 及其适配爨左解决；或者基丁牛苛殊的癍心背景。从应刈i 出发解决某个或某类问题的一个方 面：或者从i ：群角度玄考虑简单易行的实现方案。但无论哪一种方法，凋度系统都不是一 个孤立的存住，而是和所属网格项目其他组什有千丝万缕的联系。冈此，卜面介幺f 几个土 要的网格项目，涉及剑项目的各方面特点，并做必要的比较。 1 3 1 国外的一些网格研究及项目 s e t i h o m e ：s e t i h o m e 使川冈特网连接的计算资源米执行十分人规模的数据 分析项目：搜索外帚智能1 2 】。这个项目搜索包括宇市背景辐射、有可能起源丁l 地球或者其 p 星、也可能起源丁外吊世界的信号辐射剑地球的电磁噪音。项目的s e t i h o m e 阶段分 析在波多黎各的a r e c b o 望远镜收到的数据。a r e c b o 望远镜人约已产生5 1 1 6 6 2 1 5 单元的 数据，每个单元人约为一兆字仃。s e t l h o m e 把这些数据分发剑运行s e t i h o m e 软件 的冈特网川户，这些用户然后搜索可能的外星信号。迄今为i 卜，川户已返同1 4 2 2 5 0 1 8 2 单 元结果。s e t i 固h o m e 项目尚朱有发现宁南信号，项目将继续另一个两年计划。s e t i h o m e 软卅：作为一个屏幕保护程序运行，川户臼愿地卜载它并执行l ：作。该项目的成功显示使用 忠愿计算机是建殴有效的网格环境的一个可行方法。 g l o b u s ：g i o b u s 是a r g o n n e 国家实验室和c a i i f o m i a n 技术学院i | ；j 合开发的网格计算 环境【1 3 ，3 6 】。它包含多个网格计算基础设施t 具集，能提供基本的通信、资源定