（计算机应用技术专业论文）分布式智能搜索引擎技术.pdf

摘要 摘要 随着信息技术的飞速发展，i n t e h 垃t 已经发展成为当今世界最大的信息库，并 且成为全球范围内传播信息和获取信息的最主要途径之一。计算机网络上出现越 来越多的文本信息，这就对用计算机高效智能地处理自然语言信息提出了越来越 高的要求，同时也对搜索引擎这种网络软件的体系结构提出了更高的要求。 本文首先研究了中文文本w 曲搜索引擎设计中面临的关键技术以及相应的 设计与实现，包括：搜索引擎的基本体系结构以及设计时应考虑的问题并且给出 了实现。然后介绍了分布式计算中的负载平衡技术，可扩展标记语言x m l 技术 以及w i n d o w s 后台服务程序的设计原理。接下来较详细地介绍了分布式搜索引 擎系统的体系结构，系统整体工作流程以及各个功能模块描述。最后，对搜索引 擎软件未来的发展进行了几点展望。 关键词：搜索引擎，负载平衡，分布式计算，可扩展标记语言 a b s t r a c t w i t ht 1 1 eh i 曲一s p e e dd e v e l o p m e n to fi n f o 咖a t i o nt c c l l l l o l o g y ，i n t e m e th a sb e c o m e n o to n l vt h er i c h e s ti n f o m l a t i o nw a r e h o u s eb u ta l s ot h e1 e a d i n ga p p r o a c ho f j n f o r m a t i o nt r a n s m i s s i o na n da c q u i r e m e n ti nt h ew o r l d w i t h t h ea p p e a r a n c e o fm o r ea n dm o r et e x ti n f o h n a t i o no nt h ei m e m e t ，w em u s t i m p r o v e o u r t c c h n o l o g y o f也et r e a n n e n ta b o u th u m a nl a n g u a g ea j l dw em u s ta d j u s tt h ea r c h i t e c t u r eo f s o f t w a r ct oa g r e e 丽mn e t 、v o r kc o m p u t i n g t h ef 0 1 1 0 w i n gc o n t e n t sa r ec o n t a i n e di nt 1 1 i sp 印e lf i r s t l y ，w ef o c u so nt h ek e y t e c l l i l o l o g i e s i n d e s i g n a 1 1 d i m p l e m e n t a t i o n o fc h i n e s et e x t u a lw e bs e a r c h e n g i n e a r e rg i v i n gad e m o n s t r a t i o no f t 1 1 eb a s i cs t m c t u r eo fw e bs e a r c he n g i n e ， 曲括p a p c r 凼s c u s s e s ) eq u e s d s ) a t 曲。出dt 址e 抽l oc 0 玎s j d e m 丘o ni 玎d e s i 鲫a n d b r i n g s f 0 九a r dm ec o r r e s p o n d i n gi m p l e m e m a t i o n s e c o n d l y ，w et a l ka b o u tt h e t t ：c h n 0 1 0 9 yo f l o a db a l a n c eo fd i s t r i b u t e ds y s t e m 、x m la n dt h ed e s i g no fw i n d o w s n ts e r v i c ep r o c e s s t h i r d l y ，、e 诅l ka b o u tt h ea r c h i t e c t u r eo fd i s t r i b u t e di n t e l i i g e n t s e a r c he n g i n e ，t h ew o r kf l o wo ft h j sw h o l es y s t e ma i l dd e s c r i p t i o no f c t i o n a l m o d u l e s l a s t l y ，w eb r i n gf 0 刑a r ds o m et e c h n o l o g i e s 、v h i c ha r er e l e v a n tt o o u r s y s t e ma n dm a y b e c o m e p o p u l a r i nt h ef m l l r e k e y w o r d s ：s e a r c h e n g i n e ，l o a db a l a n c e ，d i s 仃i b u t e dc o m p u t e ，x m l 第l 章绪论 1 1 论文选颇考虑 第一奄绪论 信息技术飞速发展、计算机网络上出现越来越多的文本信息，对用计算机 态效餐黥逡处理爨然语言信悫疆懑了越来越遥秘麓需求。蒽豹采说，这静需求 嘲以具体化为下厕的四个；一、突破语言障碍，让全世界使用不同语言的人共 攀售惠。二、快速、准确建放大鬃豹镶惑中我羁翔户掰辫酶信惑。三、傻计算 机与人的交互变得更容易、更自然。四、改进软件的体系结构，使计算性能不 羧提亵，叛适应镲患迅速澎联懿瓣求。逡霆个要求必人工餐能赣域酌自然语言 理解和分布式系统设计方面的研究提供了广阔的发展空间。机器翻译和机助翻 译可娃鼹予鼹决第一个避题；文献资辩汝鑫凌分类、搜索弓l 擎、全文检索、鑫 动文摘、文本信息提取( i n f o r m a t l o ne x t r a c t i o n ) 技术可以用于解决 第二个阉题；蟹戆入凝接霹、浯密汲烈、软转a g e k t 等技术霹毅释决第三令 问题；分布式系统设计和分布式计算方面的研究可以解决第四个问题。本研究 谍题主要集中在搜索弓l 擎以及其分布式髂系结搀戆磅突上。选送鹃依据除了满 足上述第二个迫切需求之外，还有下面的两个原因：一、搜索引擎的研究涉及 了自然语畜处理盼各个层露扶词到甸子，麸甸子到簇耄这些不弼层次磷究工 作。只有对它们都进行研究，并搬这些研究成果商机地缩合起来，才能研究出 好的搜索g l 擎系统。二、分布式计算是一个古老识又缀热瓣课题，睫罄瓣络的 发展分布式计算注定要在甄联网耐代扮演很重要的角色，只有对分布式的体系 结构进行一定研究，才能傻撂研究啦的分枣式智搜索弓l 擎更镣会鼹终爨感发 展的需要。三、中文智能搜索引蘩是首都信息股份发展有限公司网络多媒体实 验室承担的国家八六三科研课题。有了这样的鸷凝，不仪使研究骞了必簧救经 费保障，烫重要蛾是有了一个共同奋斗的课题组可以在一起切磋、讨论和共享 资源，有利于系统完成。 1 2 课题研究的意义 1 2 1 网络资源的极大丰富 随着信息科技的进步和互联网的日益普及，人类正在进行信息史上最巨大 的一) 页工程，即将现实世界现有的信息，诸如报纸、期刊、书籍、专利文献等 都放到网络上去，同时也不停地在网络上生产出数不胜数的新信息。任何人在 任何时间、任何地点都可以通过网络发布任何信息。整个网络正在堆积成一个 前所未有的超级大型数据库，也就是说网络已经成为一个庞大而杂乱无章的桌 面图书馆。面对潮水般涌来的电子文献，人们迫切需要能够自动实现信息采集、 过滤整理和利用的各种网上智能业务。搜索引擎、自动文摘、文本分类、机 器翻译、信息安全等等都是非常有力的智能工具。我们难以想象，如果没有搜 索引擎等相应的智能工具，人们如何在浩瀚无边、拥有着各种各样信息的 i n t e m e t 上冲浪。 1 2 2 现有搜索引擎的不足 搜索引擎( s e a r c he n g i n e ) 旨在为用户在页面的海洋中导航，可是现有的搜 索引擎( 例如a 1 t a v i s t a ) 没有一个可以完全有效地检索网络资源。输入一项 检索请求的网络用户会被数以千计的回答弄得不知所措。检索结果常常涉及一 些无关的网址，却漏掉了那些存有重要资料的其它网址。可以说我们现在已经 拥有了一个桌面图书馆，但却无法有效地使用它。究其原因主要是因为目前中 文搜索引擎普遍存在三个问题：一、信息量不够丰富；二、检索处理缺乏智能； 三、单机版的体系结构对信息的扩展形成了严重的瓶颈。因此，必须研究提高 i n t e r n e t 中文信息搜索引擎性能的关键技术，从根本上解决目前众多中文搜索 引擎存在的问题。 1 3 本课题研究依赖的理论知识自然语言处理技术和分布 式计算技术 自然语言是通向人类知识宝库的一把钥匙。作为智能搜索引擎，首先要掌 握这把钥匙，才能方便自如地跟人类交换信息。随着信息时代的发展，网上信 也提出了更高的要求。集中式的架构已经很难满足大型网站系统的需求，甚至 成为信息导航的瓶颈，因为随着信息量的增大和用户的增加，它对w e b 服务器 提出了太高的要求。为了很好地介绍本论文，首先需要介绍分布式系统设计和 自然语言理解的有关知识。 1 3 1 自然语言理解理论引入 现代科技的发展使人类进入了信息时代。对于人类而言，最自然、最重要、 效率最高的信息载体之一就是自然语言。人类能够利用自然语言进行信息的传 递和交流，这是人类与动物的本质区别之一。语言是思维的载体，是人际交流 的重要工具。在人类历史上以语言文字形式记载和流传的知识占知识总量的8 0 以上。在信息化社会里，语言信息处理的技术水平和每年所处理的信息总量已 成为衡量一个国家现代化水平的重要标志之一。 语言是人类最重要的交际工具。语言交际的模式主要是表达和理解，一方 表达，另一方理解。语言交际就是在一定的场合、依据一定的规则、表达和理 解一定的意思，句法、语义和语用在实际中是三位一体的。 从第一台电子计算机诞生到现在半个多世纪过去了，人类已经由发明工具延 伸自己的四肢进化到延伸自己的大脑。计算机一开始只是科学家、工程师的计 算【具，现在已经逐步进入大众的日常生活。i n t e r n e t 将世界各地的电脑连成 一片，人们可以在网上查询或发布信息，可以在网上聊天、漫游、购物甚至在 网上生存。“电脑+ 网络”正在从延伸人的大脑发展为延伸人的生存空间，网络社 会使人类的交际行为和方式发生重大变化，语言开始从单纯人类最重要的交际 工具发展到可以进行人和机器之间的交流。 从表达方和理解方来看，现在交际行为至少有以下四种模式： a 人表达一一 人理解 b 机器表达一 人理解 c人表达 机器理解 d 机器表达 机器理解 以电脑为发送信息的“一方”或接受信息的“另一方”，研究电脑如何表 达人的语言( 模式b ) 是“自然语言生成”，研究电脑如何理解人的语言( 模 式c ) 是“自然语言理解”。机器翻译( m t ) 需要电脑理解一种自然语言，然 后转化生成为另一种语言，所以是既包含自然语言理解研究，也包含自然语言 北京工业大学工学硕士学位论文 生成研究( 属于模式d ) ，还包含语言之间的转换研究。因此，研究“自然语言 处理“，不可以不研究语言交际，不可以不研究人脑的语言机制和模拟人脑的 语言机制。 1 3 2 自然语言理解研究进程 人工智能是以建立智能化的，自主的计算机为目标的一门学科，它研究的课 题包括：专家系统、问题求解、逻辑和不确定问题、自然语言处理、机器人学、 学习机、视觉和模式识别等等。其中自然语言处理是人工智能的核心课题，包 括自然语言的分析理解和综合生成。起初，自然语言处理强调立新主义，用人 工智能的方法( 如状态空间搜索、知识表示和机器学习等) 来处理自然语言。 在这个阶段，人们集中力量建立各种规则系统，试图通过规则地演算来解决语 言的分析和生成问题。但是不久，人们发现自然语言远不是一个精确定义的符 号体系，精心构造的规则只能在严格受限的领域内起作用，无法处理大规模真 实文本中的种种复杂的语言现象。 到了8 0 年代后期，计算语言学开始注重对大规模真实文本的处理，出现了 语料库语言学，其特点是以经验主义为旗帜，以对大规模真实文本的统计为主 要方法。语料库语言学认为，人类的一切语言知识都蕴含在大规模的语料之中， 可以通过统计来发现这些知识。以前人们凭主观内省而得到的语言知识是不完 整的，甚至可能是错误的。语料库语言学在真实文本的词性标注上打了一个大 胜仗。以前人们制定了各种语言学规则来标注词性，正确率并不高，而运用统 计方法和训练语料( 已标注过的语料) 来标注词性，准确率高达9 5 左右。然 而，语料统计的方法也不是万能的，随着语言信息处理层次的提高，简单的统 计模型越来越暴露出其缺点：难于处理长距离依赖的语言现象，难以获得高度 概括的知识以顺利地处理训练语料之外的语料。目前，在对大规模真实文本进 行自动句法分析这一关键问题上，还没有取得突破性进展。 1 3 3 分布式系统设计理论的引入 显然，未来对计算速度、系统的可靠性和成本实效性的要求必然将促使发 展另外的计算机模型来代替冯诺依曼结构的计算机。随着计算机网络的发展， 一个新的梦想成为可能一分布式计算。当用户需要完成任何任务时，分布式计 算提供对尽可能多的计算机处理能力和数据的透明访问，同时实现高性能和高 第1 苹绪论 可靠性的目标。在过去的十多年里，人们对分布式计算系统的兴趣迅猛增加。 分布式计算的主题是多种多样的，许多研究人员在研究有关分布式硬件结构和 分布式软件设计的各方面问题以开发利用其潜在的并行性和容错性。 分布式计算系统( 或分布式系统) 多种多样并涉及不同的体系结构。对一 些用户来说，一个分布式系统是为解决单个问题而紧密结合在起工作的多处 理机的集合。对另一些用户来说，一个分布式系统可能意味着一个由地理上分 散的各自独立的处理机组成的计算机网络，这些处理机连接在一起以实现对不 同资源的共享。然而，分布式系统这个词在计算机系统中被如此广泛应用以至 于它的使用变得有点贬值。许多这方面的混乱来源于缺乏对物理的分布和逻辑 的分布的区分。通过区分这两个概念，就可以更准确地描述一个分布式系统的 属性。 对于分布式系统，我们使用以下定义：一个分布式系统是一个对用户看起 来像普通系统，然而运行在一系列自治处理单元上的系统，每个处理单元有各 自的物理存储器空间并且消息的传输延迟不能忽略不计。在这些处理单元问有 密切地合作。系统必须支持任意数量的进程和处理单元的动态扩展。 1 3 4 分布式系统设计的目的 建立一个分布式系统的主要目的在于： 固有的分布式应用。分布式系统以一种很自然的方式开始存在，例如， 在我们的社会中，人群在地理上是分布式的并且分布式地共享信息。一 方面，个分布式数据库系统中的信息产生于不同的分支机构，所以能 够快速地完成本地访问。另一方面，系统也提供了全局视图来支持各种 全局操作。 性能成本。分布式系统的并行性降低了处理的瓶颈，提供了全面改进 的性能，也就是说，分布式系统提供了更好的性能价格比。 资源共享。分布式系统能有效地支持不同位置的用户对信息和资源( 硬 件和软件) 的共享。 灵活性和可扩展性。分布式系统可以增量扩展，并能方便地修改或扩展 系统以适应变化的环境而无需中断其运行。 实用性和容错性。依靠存储单元和处理单元的多重性，分布式系统具有 在系统出现故障的情况下继续运行的潜力。 可伸缩性。分布式系统能很容易地扩大以包括更多的资源( 软硬件) 。 第2 章搜索引擎的基本工作流程 第二章搜索引擎的基本工作流程 2 1 搜索引擎的概述 搜索引擎是指对唧站点资源和其它资源进行索引和检索的一类检索系 统机制。搜索引擎是由数据采集( 搜索s p i d e r ) 、文档组织和索引、查询服务三 个模块组成，如图2 1 所示： 1 ) 搜索s p i d e r ：用于w w w 网遍历和网页的下载； 2 ) 文档的组织和索引：s p i d e r 采集到的网页和相关描述信息经索引组织后 存储在索引数据库中； 3 ) 查询服务：负载接收用户查询和进行数据库检索，并将结果按相关度大 小反馈给用户。 随着w e b 页面的不断增加，搜索引擎也要处理越来越多的文档。要使搜索 引擎技术的发展能够充分适应迅速增长的w e b ，必须考虑下面的问题： 1 ) 快速而有效的数据采集技术：从而能够获得更多的文档，并且不断更新 旧的文档； 2 ) 有效地使用存储空间：从而能够存储大量的索引库，甚至是文档集本身； 3 ) 合理的索引系统：必须合理有效地索引，组织大量的数据： 4 ) 快速准确地处理查询：做到每秒能处理成千上万次查询。 北京工业大学工学硕士学位论文 2 2 数据采集 图2 一l 搜索引擎的基本结构 2 2 1 数据采集过程概述 要建立一个全面的搜索引擎，必须对，、v 、v 进行系统而全面地遍历。这是由 一个搜寻程序s p i d e r ( m b o t ) 来完成的。s p i d e r 模块利用h n p 协议来读取w e b 页面并沿着h n 1 页面中的超链接在唧上自动漫游，同时按照用户的要求自 动访问w w w 资源。在上述的处理过程中可将嗍抽象成一个有向图来处理， 将每个页面看作图中的一个节点，将页面中的超链接看作图中的有向边。因此 可以使用有向图的遍历算法( 深度优先和广度优先) 来对州进行遍历。 简单来讲，s p i d e r 模块从一个u r l 开始得到第一个页面p 0 ，然后从p o 中提 取所有的u r l ，并把它们加入到l l r l 队列。以后每次从队列中取出一个u r l 并且重 复上述的过程，所有取到的页面都提交给索引组织模块进行处理。 上面只是简单地描述了搜索程序的工作机制，在实际的设计中还要考虑很 多问题。一方面，搜索程序必须能在自己工作的同时不对正在访问的w e b 站点 造成很重的负担。另一方面它还要处理大量的数据，因此必须考虑遍历页面的 r 第2 章搜索引擎的基本工作流程 次序和优先问题。搜索程序运行好坏很大程度上取决于这些问题的解决，在下 面我们会分别讨论这些问题。 2 2 2 搜索程序的专用协议 在很多情况下，、v e b 服务器管理员并不希望自己的某些内容被搜索程序来 访问。一方面，有些网站的内容是经常改变的，比如一些新闻站点，在很短时 间内这些页面就要更换，并且这些页面不是文本文件，所以不希望被搜索程序 访问。另一方面很多搜索程序由于设计上的问题往往过度频繁地访问某个站点 的、v c b 服务器，加重了w e b 服务器的负载，从而影响了正常用户的访问，管理 员当然不希望这种情况发生。 为了方便网站管理员的管理，出现了搜索程序专用协议，当然这些协议需 要依靠搜索程序的合作，因为不是每个搜索程序都遵循这些协议的，所以如果 要进一步限制对内容的访问就要通过口令或限制访问的i p 地址来实现。 1 r o b o te x c l u s i o n 标准 r o b o te x c l u s i o n 标准是网站管理人员来管理网站各部分是否能被 s p i d e r 搜寻程序遍历的方法。采用的做法是在服务器上创建一个r o b o t t x t 文件， 并且应具有“h t i p ：s i t e n a m e r o b o t 戗t ”的u r l ，其中s i t e n a m e 是网站的名字。 这个文件分别存放对各个搜寻程序的访问控制指令，格式如下： u s e r a g n e t ： d i s a l l o w ： 其中，u s e r a g n e t 是用来指定要限制的搜寻程序名字，d i s a l l o w 指定被限 制网站的某个部分的u r l 。如果一行的开始是# ，那么表示这一行是注释内容。 当一个搜寻程序在访问这个站点时，首先要取得“r o b o t t x t ”这个文件，然后 按照里面的访问限制来进行相应地访问。搜寻程序在设计时都要考虑支持这个 标准。 2 r o b o t m e t a 标记 除了网站管理员可以搜寻程序对网页的访问权限外，网站用户也可以限制 搜寻程序对自己主页的访问权限。为了达到此目的，用户可以在自己的主页中 加入一个m e l a 标记。r o b o tm e t a 标记允许一个页面的所有者可以在页面 中指定是否允许搜寻程序来访问自己的页面，或者从页面中提取链接。例如： 这个例子表明任何搜寻程序都不能索引这个页面，并且不能从中提取链接。 北京工业大学工学硕士学位论文 目前还只有很少的搜寻程序支持这个规定。 另外，网页的制作者还可以在网页中加入d e s c r i p t l 0 nm e l a 和 k e y w 0 r dm e t a 标记以描述网页的内容和关键词，便于搜寻程序提取关键 词。 2 2 3 搜索程序的优化 1 分散对同一个w e b 服务器的访问 搜索程序往往是同时启动多个线程或进程来进行抓站操作，每秒钟建立几 百个链接，而每个服务器每秒钟只能处理几十个请求。如果都同时用来访问同 一个w e b 服务器，那么就会使得正在访问的w e b 服务器超载，从而造成其它用 户不能访问。一般的做法是让搜索程序采用“轮询”的方法来从服务器获得页 面：可以用h a s h 表的方法来把不同的w e b 服务器的u d 放在不同的队列中，每 次建立链接时就依次从这些队列中分别取得l l r l 。这样，如果说有5 0 0 个队列， 那么就意味着搜索程序每5 0 0 次才能重新访问同一个w e b 服务器。 2 遍历时的优先策略 对于大多数的搜寻程序来说，不可能遍历i m e m e t 网中的所有页面，因为存 储空间总是有限的。其次，遍历w c b 要花费很长的时间，并且要不断地重新遍 历以更新以前得到的网页。为了尽可能地获得最感兴趣、最有价值的页面，在 每次从u r l 队列中选取新的l l r l 时，就要尽可能地选择最为重要的页面。下面介 绍两种定义权重的方法。 ( 1 ) b a c k l i l l k 数w b ( p ) ：此时w b ( p ) 代表这个w e b 中有多少个页面中会 有链接指向这个页面p 。其实从直观的角度来讲，一个页面被链接得 越多就说明越重要。这种表示页面重要性的方法被很多的搜索引擎 用来对查询页面进行排列。当然，对w b ( p ) 的估计需要首先获得整个 w e b 的所有页面。而搜寻程序在用这种方法时可用一个近似值来代 替。这个近似值可以根据取到的页面计算出来。 ( 2 ) p a g e r a l l k 值w p ( p ) ：在w b ( p ) 方法中，假定所有指向该页面中的 链接是平等的，但实际上不是这样的，往往有些页面重要得多。因 此，可采用p a g e r a n k 来定义一个页面的重要性。 一。耋鎏鋈型坠譬耋譬坠。一 2 2 4 搜寻的结果及其更新 为了及时地和w e b 上的页面保持一致，定期地对访问过的页面进行重新遍 历，这样就要记录下每个页面的访问时间，以便检查更新情况；同时在遍历时， 不但要保存页面，而且也要把连接文本保存下来，因为这些文本往往被用来作 为索引内容的一部分。 2 2 5 专题型搜索引擎的数据采集技术 对于专题型搜索引擎来说，其数据采集技术和综合型搜索引擎有很大区别。 在专题型搜索引擎中，其数据采集系统从、 删中采集回来的数据需要再进一 步处理，把此专题范围内的网页放入索引库中，丢弃范围之外的网页。因此这 里引入数据采集有效率u 来衡量专题搜索引擎数据采集系统的数据采集准确 性。 u = 单位时间内专题范围内网页数单位时间内收集的网页数 下面介绍两种提高数据采集有效率的方法。 1 首页关联技术 首页关联技术是建立在以下的假设基础上的：绝大多数、v c b 站点的首页是 这个站点内容的概括。从目前删的情况来看这个假设对绝大多数站点，特 别是大型站点来说是成立的。 首页关联技术的具体方法就是在第一次访问一个新站点是对其首页用专题 范围内的关键词进行检索，如果在首页内没有任何一个关键词出现，则认为此 站点和本主题无关，其将被放入r o b o t 禁止访问的主机列表中，r o b o t 以后 再遇到这个站点列表内的u r l 时，直接丢弃而不是将其放八待访问的u r l 列 表中。 2 链长比技术 链长比技术主要是针对目录页面的。网页中那些主要由链接组成而自身内 容很少的页_ 酝成为目录页，目录页因为自身的内容很少，在索引库中没有保留 的必要，在提取完链接信息以后，可以丢弃掉。那么怎么判断目录页呢? 链长 比技术给出了一个解决方法。链长比y 的定义如下： y = 页面中的链接数页面中文本信息长度 目录页的判断算法如下： i fy v ( t ) 负载代价来自三个方面： 曲处理器间传播的负载信息。 b 1 任务转移前的任务选择的决策过程。 c 1 任务移植的通信延迟。 5 位置策略 位置策略是寻找合适的节点共享负载。最常用寻找节点的方法是询问。通常 是开始负载平衡的节点询问其它节点，以决定它是否适于共享负载。局部范围方 法中，只有相邻节点才是询阆的候选节点；相反，全局范围的方法中，系统的任 何一个节点都是询问的对象。从所有候选节点中选取一个节点要么是随机的，要 么基于上一次轮询收集的信息。轮询的替代方法是广播要求，适用于所有节点都 能负载共享的情况。 6 信息策略 信息策略决定收集系统中其他节点状态信息的时机、收集的方位和收集的信 息。在每个节点收集的信息越多，负载平衡过程就越有效。然而，信息收集过程 会产生新的代价。因此，要有所折衷。 3 3 2 动态负载分配算法 动态负载分配算法必须是普适的、适应性的、稳定的、可扩展的、容错的和 对应用程序透明的。负载平衡算法可以分为以下几类： 1 ) 全局的和局部的。局部负载平衡算法在邻接的节点间转移工作负载。全 局负载平衡算法不仅在邻接节点间交换负载，还在全系统间计算负载， 根据全局情况调整处理器负载。 2 ) 集中控制的和分散控制的。在集中控制算法中，中心控制器收集状态信 息，做出负载平衡决策。分散控制算法把控制机制分散到全系统各个节 点。 3 ) 不协作的和协作的。在不协作方法中，各个节点不知道系统中其他节点 的状态，独立决定自己的位置和转移规则。协作算法中，节点间相互配 合来决定负载平衡决策。 4 ) 适应性的和非适应性的。在适应性算法中，负载平衡策略根据系统状态 北京工业大学工学硕士学位论文 变化而改变；而非适性方法中，这些策略是不变的。 3 3 3 负载平衡使用的参数 负载平衡算法的选择和组成依赖于一个可计算对象的集合。这些对象是系统 参数加下： 1 ) 系统大小。系统中处理器的个数。 2 1 系统负载。所有处理器上的负载。 3 1 系统交通强度。各个处理器上任务的到达率。 4 ) 移植极限。触发任务移植的负载水平。 5 ) 任务大小。使移植高效的任务大小。 6 、管理成本。通信和任务放置的成本。 7 ) 响应时间。任务结果的返回时间。 8 ) 负载平衡地平线。决定任务移植目的节点时需要探测邻节点的个数。 9 )