（计算机软件与理论专业论文）solars下群集中英文搜索擎的设计和实现.pdf

，吖 煎篁 望垒显口一 摘要 学科专业：计算机软件与理论 论文题目： s o l a r i s 下群集中英文搜索引擎的设计与实现 硕士生；许腾 导师：卢显良教授 一 随着i n t e m e t 在迅速发展，各种网络资源变得越来越丰富。为了在网络海洋 中获取有用的信息，我们必须借助网络查询系统。但目前国内，中文网络信息 、 的查询系统还不成熟，这给用户有效利用网络资源带来很大的不便。， 本课题设计和实现的搜索引擎就是为用户提供网络信息的查询。它支持中 英文检索，并能根据用户需要支持多种逻辑组合查询。同时，它具有很高的响 应速度。 r 7 ，本论文分为两大部分，在前半部分，首先简要介绍了搜索引擎的基本原理 和一些相关技术，然后详细介绍搜索引擎的各个模块的设计和实现，其中重点 介绍了索引数据库的设计；为了提高系统的效率和容错性，在论文后半部分 我们引入了分布式计算技术一一群集计算。在介绍完群集的概念之后，我们详 细分析了几种成员协议的算法，最后阐述了我们的群集系统中成员协议和负载 平衡的设计方案。 在论文末，我们对整个系统作了系统性能测试和分析，并对以后的改进工 摘耍 作提出了一些的想法。j 关键词：搜索引擎索引数据库群集计算成员协议 ! 塑些l 一 a b s t r a c t s p e c i a l i t y ：c o m p u t e r s o f t w a r e t h e o r y t i t l e ： d e s i g n & i m p l e m e n t a t i o n o f c l a s t e r s e a r c h - e n g i n e i nc h i n e s e & e n g l i s h o ns o l a r i s m a s t e r ：x ut e n g a d v i s o r ：p r o f l ux i a n f i a n g w i t ht h e r a p i d l yd e v e l o p m e n t o fi n t e r a c t ，t h ei n f o r m a t i o no nn e t w o r ki s b e c o m i n g m o r ea n dm o r ea b u n d a n t f o rg e tt h ei n f ot h a tw en e e d ，w em u s tt u r no u r h e l pt ot h ei n f o - r e t r i e v a l - s y s t e m p r e s e n t l yi nc h i n a , h o w e v e r ，t h e s et o o l sa r e n o t m a t u r ee n o u g hm a tg r e a t l ye n c u m b e rt h ee f f i c i e n t l yu s eo f n e t w o r k r e s o u r c e s t h eg o a lo fo u rp r o j e c ti sj u s tt of i i lt h i s g a p t h i ss o f t w a r es u p p o r t s t h e c h i n e s e & e n g l i s hi n f o r m a t i o nr e t r i e v a la n ds e v e r a lm e a n so fl o g i c c o m b i n er e t r i e v a l a c c o r d i n g t ot h e r e q u e s t o fu s e r s m o s ti m p o r t a n t l y , i t p r o v i d e s a f a s t - r e s p o n s e s e r v i c e t h i sd i s s e r t a t i o nc o n s i s t so ft w op a r t s i nt h ef i r s tp a r t , a u t h o ri n t r o d u c e ss o m e c o n c e p t sa n d r e l e v a n tt e c h n o l o g i e sa b o u ts e a r c he n g i n e ，a n dt a k e sat h o r o u g h l y d e s c r i p t i o na b o u tt h ed e s i g na n di m p l e m e n to fs e v e r a lm a j o rm o d u l e si nw h i c ht h e i n d e x - d a m - b a s em o d u l ei s e m p h a s i z e d f o re n h a n c i n gt h ee f f i c i e n c y a n df a u k t o l e r a n c eo ft h es y s t e m ，i nt h es e c o n dp a r t ，w ei m p o r tt h ed i s t r i b u t i o nc o m p u t i n g m o d e c l u s t e r - c o m p u t i n g a f t e rb r i e f l yi n t r o d u c i n gt h ec o n c e p t so fc l u s t e r - c o m p u t i n g ，w et h o r o u g h l ya n a l y z et h ea l g o r i t h m so fs e v e r a lm e m b e r s h i pp r o t o c o l s ， a n dt h e nd e s c r i b eo u ra l g o r i t h mo f m e m b e r s h i pa n dl o a d - b a l a n c i n g ，f i n a l l yw e p r e s e n tt h ef r a m e - w o r ko f o u rs e a r c h e n g i n ec l u s t e r a tt h ee n do ft h ed i s s e r t a t i o n ，w eg i v ear e p o r to fo u rs y s t e m t e s t a n db r i n g f o r w a r ds o m ea d v i c eo nt h ef i t h e l w o r k ! 墅型g k e yw o r d s ：s e a r c he n g i n e i n d e x d a t a b a s e c l u s t e r c o m p u t i n g m e m b e r s h i p p r o t o c o l 1 1 搜索引擎概述 第一章绪论 在美圉9 i t 搜索引擎”通常指的是针对互联网的搜索，收集互联网上几千万到 几亿个数量不等的网页，并且每一个网页上的每一个词都被”搜索引擎”所收录。 也就是说，当网民使用”搜索引擎”进行信息查询的时候，这种搜索是针对整个互联 网的，而不是基于某一网站”目录”的搜索，其搜索的效果当然会有所不同。网虫们 通常会找一些稍微生僻的词汇考察”搜索引擎”，以检验其信息量。除此之外艘索 的速度、相关性( 搜索准确度) 、新闻性( 刷新频率) 等都是衡量”搜索引擎”好坏的 重要指标。 目前国内的互联网刚刚兴起，对于”搜索引擎”尚缺乏足够的重视，其效果更 是差强人意。主要表现在：所采用”搜索引擎”技术落后，观念落后，信息量小，查询 速度缓慢。用户得不到真正需要的信息，不是互联网上没有，而是”搜索引擎”搜索 不到。对于目前国内”搜索引擎”种种不足，如果不及早加以重视，势必将影响我国 未来互联网发展的步伐。 所以，需要我们重视的是：上网其实不是目的，信息才是你最为需要的，而” 搜索引擎”可以帮助你达到目的。”搜索引擎”也在不断发展，如今是各种商业、生 活信息；明天就会是声音，是图像，”搜索引擎”将帮助你进入多媒体的互联网世界。 1 2 搜索引擎分类 文档的索引与检索模型是搜索引擎的核心，检索模型的优劣直接影响到系 铺一章结论 统的性能。文本信息检索模型主要分为两大类：全文检索和目录分类检索。 1 2 1全文检索式搜索引擎 全文检索( f u l lt e x tr e t r i e v a l ) 是指以文档的全部文本信息作为检索对象 的一种信息检索技术。全文检索的关键是文档的索引，即如何将原文档中所有 基本元素的信息以适当的形式记录到索引库中。在中文文档中，“基本元素”可 以是单个汉字，也可以是词或词组。根据索引库中索引的元素不同，可以将全 文检索分为基于字表的全文检索和基于词表的全文检索两种类型。 字表法 字表法是对每个单字的出现位置进行索引，并依据单字的位置信息进行检 索的文本检索方法。字表法索引库的主要部分是每个字的字表信息，索引库中 的字表结构如图1 - 1 所示。其中字符i 对应的字表记录了该字符在源文档中所出 现的位置风，出现位置通常用字符相对于文档头的偏移字节数表示。建立字表 索引时，需要扫描整个源文档，对出现的每一个有效字符，计算其在文档中出 现的位置，并将该位置的值加入到对应的字表中。 啊 p11p12p13 阿p21p22p23 掰pi 1pi 2pi 3 pim 络 p j lp j 2 pj 3 pjn 图1 1 字表结构 字表记录了对应字符在源文档中的所有位置信息。考察一个字符串，例如 两个字的字符串x y ( 其中x 、y 表示任意的汉字字符) ，假设x 的位置为p 。， - 2 墨二茎笪丝一 如果字符串x y 在源文档中出现，则y 的位景p y 必定等于p x + 2 ( 2 为两个汉 字间的字节距离) 。在索引库中，x 的字表中将包含p x ，而y 的字表中也必然 包含p x + 2 。进行检索时，扫描x 和y 各自对应的字表，若文档中有该词出现， 则必定有x 对应的字表中存在位置值p x y 对应的字表中存在位置值p ，使得 p v = p x + 2 成立，每查到一对这样的位置值，就是检索到了字串x y 一次。扫 描完两字字表，就可以检索到字符串的所有。 词表法 与字表法相似，词表法是以能表达一定意义的词为基本检索单位，并根据 词的出现位置进行索引和检索的文本检索方法。建立索引时，首先需要对源文 档进行词条的切分，然后对切分后的文档词条进行统计，记录每一个出现的词 条及其出现的位置。 1 2 2目录分类式搜索引擎 这类搜索引擎提供按类编排的网站目录，有站名、网址及摘要信息。用户可 按信息类别查询，进行网站检索。在文字框中输入要查询的关键词，点击按纽，便 可将有关网站站名、网址及摘要信息拉取出来。 这类搜索引擎的将信息系统地分门归类，当遇到一个网站时，它并不像全 文搜索引擎那样，将网站上的所有文章和信息都收录进去，而是首先将该网站 划分到某个分类下，再记录一些摘要信息( a b s w a c t ) ，对该网站进行概述性的简 要介绍。最具代表性的目录式分类搜索引擎是y a h o o 网站。分类搜索引擎可以 使用户清晰方便地查找到某一大类信息，这符合传统的信息查找方式，尤其适 合那些“希望了解某一方面范围内信息，并不严格限于查询关键字”的用户。但 目录式搜索引擎的搜索范围较全文搜索引擎要小许多，尤其是当用户选择类型 ， 掰一臂钟西 不当时，这样有可能遗漏某些重要的信息源。 上述两类搜索引擎各有其优缺点： + 全文检索式搜索引擎比较复杂，可自动检索w w w 站点的最新网页，适用于文 档检索。 + 目录分类式搜索引擎比较简单，可有效地查询到所需的站点，适用于目录查询。 本课题所研究和设计的搜索引擎的核心索引库是通过全文检索模型中的字 表法建立的。其优点是适应性强，应用范围广，索引的生成简单，比较适用于 内容复杂、新词汇和特殊词汇多的网络页面的检索。 1 3 搜索引擎基本原理 1 3 1 工作原理 对于各种搜索引擎，它们工作原理的基本一样，包括以下三个方面： 一、派出“网页搜索程序”在网上搜寻相关信息，并将它们带回搜索引擎。 每个搜索引擎都派出绰号为“蜘蛛( s p i d e r ) ”或“机器人( r o b o t s ) ”的网页搜索软 件在各网址中爬行，访问网络中公开区域的每一个站点并记录其网址，从而创 建出一个详尽的网络目录。各搜索引擎工作的最初步骤大致都是如此。 二、建立搜索引擎数据库 不同的检索软件记录网页的内容是不同的，有些记录网页全文，有些记录 网页的地址、篇名、题名、特定的段落和重要的词。不同检索软件的数据库规 模也是不一样的。数据库规模的大小决定查询到的信息是否全面。数据库越大， 检索到的结果越多，检索软件知名度就越高。数据库的更新有累积式和重建式 两种方式。累积式是不断地将新发现的网页补充到原有的数据库中去，这种方 第一章姥论 式可能会存在一个网页重复出现的问题，检索结果中重复率也比较高。重建式 是指原有的数据库内容被重新更新。 三、通过w e b 服务器端软件，为用户提供浏览器界面下的信息查询 每个搜索引擎都提供了一个良好的界面，并具有帮助功能。用户只要把想 要查找的关键字或短语输入查询栏中，并按“s e a r c h ”按钮( 或其他类似的按钮) 。 搜索引擎就会根据用户输入的提问，在索引中查找相应的词语，并进行必要的 逻辑运算，最后给出查询的命中结果( 均为超文本链形式) 。用户只需通过搜索 引擎提供的链接，马上就可以访问到相关信息。有些搜索引擎将搜索的范围进 行了分类，查找可以在用户指定的类别中进行，这样可以提高查询效率，搜索 结果的“命中率”较高，从而节省了搜寻时间。 1 3 2检索软件的组成 现在在i n t e m e t 上有许多w w w 查询站点，这些站点的结构与工作原理一 般都很相似，一般都是由搜索r o b o t s 、搜索引擎、文档索引库和查询服务等四 丈模块组成。如图i - 2 所示。 j 图1 2 检索站点结构图 网络蜘蛛 r o b o t s 用于w w w 的漫游与网页的下载，是一个能利用h t t p 读取w e b 页面并沿着h t m l 文档中的超链在w w w 上进行自动漫游的程序，也被称为 s p i d e r 、w o r m 、c r a w l e r 。它按照用户的要求自动访问w w w 资源，并判断与 用户目标的相似度，将匹配结果返回给用户。但在巨大的而且呈指数增长的 w w w 上，每个用户都使用该方法是不现实的，通常采用的方法是有特定站点 负责对网络信息资源进行系统、广泛的遍历，并建立相应的索引数据库，用户 直接在索引数据库中进行查询。 要建立全面的索引数据库，必须对w w w 进行系统而全面的遍历。我们 可将w w w 作为一个有向图处理，将每一个页面看作图中的节点，将页面中的 超链看作图中的有向边。因此，我们可以使用有向图遍历算法( 深度优先算法 或广度优先算法) 对其进行遍历。因为w w w 是一个典型的c l i e n t s e r v e r 结构 6 - 墨二! 堑篓 系统，所以可以在一台或几台主机上完成w w w 的遍历。对w w w 的遍历一 般采用如下三种方法： 给r o b o t 设定一个子u r l ，r o b o t 提取其中的超链，并利用广度优先或深 度优先算法完成对w w w 的遍历。 选不同类别、被访问频率高的u r l ，r o b o t 从这些u r l 开始遍历。 根据域名或地域代码或i p 地址将w w w 空间划分为多个子空间，运行多 个r o b o t 程序，并行地在不同的子空间中进行遍历。 在实际使用中，一般是将这三种方法组合起来使用。按照上述遍历算法， r o b o t 可以系统地、周期性地访问w w w 。因此，采用r o b o t 技术能够建立较 为全面的w e b 索引库，并保持对库的不断更新。 w e b 端专用程序 w e b 端专用程序负责把w e b 服务器传来的用户查询进行分析，打成一个 查询请求包，通过套接口发给搜索引擎，然后接受搜索引擎服务器的查询结果， 最后把查询结果文本化返回给用户。 搜索引擎 搜索引擎是搜寻站点的核心( 整个检索软件以此命名) ，它对网络蜘蛛“爬” 下来的网页进行索引并建立数据库；接受w e b 端专用程序的查询请求，并到索 引数据库中去检索，然后把查询结果返回给w e b 端专用程序。这一部分主要包 括对“爬”下的网页建立索引数据库、对用户信息进行信息查询两部分。 信息索引机器人采集到的网页索引和相关描述信息全部存储在索引数据 库中。不同的检索站点记录的内容是不同的，有些记录了网页的全部内容，有 的只记录网页的地址、标题、关键词、摘要等信息。不同的检索站点数据库的 规模也不同，数据库的规模直接影响了系统查询的查全率。 信息索引就是创建文档信息的特征记录，它使用户能很容易地检索到所需 7 锖一章结论 信息。建立索引需要进行下列处理：对单字或词语进行切分，如果是以词语为 检索单位，则还需进行词法分析、词性标注和相关的自然语言处理，最后建立 检索项索引。这一步对于编写高性能的搜索引擎是至关重要的。相关信息一般 包括“检索项”、“检索项所在文件的位置”以及“检索项权重”。检索项信息的 建立准则是要易于文档信息的更新处理。 信息查询这部分是真正的服务器部分，其功能是把专用程序传来的请求 进行排队，然后由线程池中的查询线程对队列中的每个请求进行处理，也就是 到索引数据库中去检索相关信息，最后把查询结果返回给w e b 端专用程序。 8 鉴兰燮型型塑燮二一 2 1 套接字 第二章搜索引擎相关技术 套接字编程界面由4 b s du n i x 首先提出，目的是解决网间网进程通信问 题。 套接字既可看成是支持多种网络操作形式的接口，也可看成是一种进程间 通信接口。在一条通信连接中，每个参与通信的进程有一个套接字描述相应的 连接端。我们可以将套接字看成是某种特殊类型的管道，但和管道不同的是， 套接字并不限制其中可以包含的数据数量。操作系统支持多种套接字种类，不 同的套接字种类称为“地址族”，这是因为每种套接字种类拥有自己的通信寻址 方法。操作系统所支持的套接字地址族见表2 - 1 。 表2 - 1l i n u x 支持的套接字地址族 套接字地址族描述 u n u n i x 域套接字 通过t c p i p 协议支持的 n 呵e t i n t e r a c t 地址族 a x 2 5a m a t e rr a d i ox 2 5 i p xn o v e l l i p x a p p l e t a l k a p p l e t a l kd d p x 2 5x 2 5 和虚拟文件系统类似，操作系统将上述套接字地址族抽象为统一的b s d 套接字接口，应用程序关心的只是b s d 套接字接口，而b s d 套接字由各地 址族专有的软件支持。一般而言，b s d 套接字可支持多种套接字类型，不周的 - 9 镇二章搜索铂擎辐关技术 套接字类型提供的服务不同，操作系统所支持的b s d 套接字类型见表2 - 2 表2 - 2 中的套接字地址族并不一定全部支持这些套接字类型。 表2 - 2u n i x 所支持的b s d 套接字类型 b s d 套接字类型描述 这种套接字提供了可靠的双向顺序数据 流，并可保证数据不会在传输过程中丢 流( s t r e a m ) 失、破坏或重复出现。流套接字通过i n e t 地址族的t c p 协议实现。 这种套接字也提供双向的数据传输，但 是并不对数据的传输提供担保，也就是 数据报( d a t a g r a m )说，数据可能会以错误的顺序传递，甚 至丢失或破坏。这种类型的套接字通过 i n e t 地址族的u d p 协议实现。 和数据报套接字类似，但保证数据被正 可靠发送的消息 确传输到目的端。 和流套接字类似，但数据包大小是固定 顺序数据包 的。 进程在利用套接字进行通信时，采用客户一服务器模型。服务器提供某种 服务，而客户使用这种服务。w w w 服务器就是很好的例子，w w w 服务器 提供w e b 页，而客户程序，即浏览器则读取w e b 页并显示w e b 页的内容。 服务器首先创建一个套接字，并将某个名称绑定到该套接字上，套接字的名称 依赖于套接字的底层地址族，但通常是服务器的本地地址。套接字的名称或地 址通过s o c k a d d r 数据结构指定。对于i n e t 套接字来说，服务器的地址由两 部分组成，一个是服务器的i p 地址，另一个是服务器的端口地址。已注册的 标准端口可查看e t c s e r v i c e s 文件。将地址绑定到套接字之后，服务器就可以 监听请求链接该绑定地址的传入连接。连接请求由客户生成，它首先建立一个 套接字，并指定服务器的目标地址以请求建立连接，传入的连接请求通过不同 j 口 墨兰塑型塑塑鲨 的协议层最终到达服务器的监听套接字。服务器接收到传入的请求后，如果能 够接受该请求，服务器必须创建一个新的套接字来接受该请求并建立通信连接 ( 用于监听的套接字不能用来建立通信连接) ，这时，服务器和客户就可以利用 建立好的通信连接传输数据。 b s d 套接字上的详细操作和具体的底层地址族有关，底层地址族的不同 实际意味着寻址方式、采用的协议等的不同，因此t c p i p 连接的建立过程和 a x 2 5 连接的建立过程有很大的区别。前面提到，操作系统利用b s d 套接字 层抽象了不同的套接字接口。在内核的初始化阶段，建于内核的不同地址族分 别以b s d 套接字接口在内核中注册。然后，随着应用程序创建并使用b s d 套 接字，内核负责在b s d 套接字和底层的地址族之间建立联系。这种联系通过 交叉链接数据结构以及地址族专有的支持例程表建立。例如，每个地址族具有 专有的套接字创建例程，应用程序在建立新的套接字时，b s d 套接字接口可利 用该例程建立新的b s d 套接字。 在内核中，地址族和协议信息保存在p r o t o c o l s 向量中。每个地址族由其 名称( 例如“i n e t ) 以及相应的初始化例程地址代表。在引导阶段初始化套 接字接口时，内核调用每个地址族的初始化例程，这时，每个地址族注册自己 的协议操作集。协议操作集实际是一个例程集合，其中每个例程执行一个特定 的操作。注册的协议操作集保存在p o p s 向量中，向量中包含指向p r o t o _ o p s 数 据结构的指针。p r o t o _ o p s 数据结构由地址族类型和一组套接字操作例程指针组 成，这些例程是特定的地址族所特有的。p o p s 向量的索引是地址族的标识符， 例如，i n e t 地址族的标识符为2 。 2 2 线程机制 一个进程是一个复合的实体，可以分为两个部分线程的集合和资源集 合。线程是一个动态的对象，它表示进程中的一个控制点，并且执行一系列的 指令。资源包括地址空间，打开的文件，用户凭证和配额等等。这些资源为进 程中所有线程所共享。此外每一个线程有它自己私有对象，比如程序计数器， 堆栈和寄存器上下文。传统的u n i x 进程有一个单独的控制线程。在多线程系 统中对这个概念进行了扩展，允许在一个进程中有多于一个的控制线程。 在进程抽象概念中，把资源的所有权集中化有一些缺点。考虑一个服务器应用 程序代替远端的客户执行文件操作。为了保证和文件访问权限的一致性，服务 器在对请求进行服务时需要假定客户的身份。为了做到这点，服务器是用超 级用户特权安装的，它可以调用s e t u i d ，s e g i d 和s e t g r o u p s 来改变它的用户证书来 暂时匹配客户的信息。让这个服务器以多线程形式构造可以增加并发性，但是 同时也将引起安全问题。因为进程拥有单独的证书集合，它每次只能扮作一 个客户。因此，服务器必须强制地串行化( 单线程) 所有的系统调用去检查安全 性。 有几种不同类型的线程，每个都有不同的属性和使用方法。下面我们介绍 三种重要类型的线程内核线程，轻量级进程和用户线程。 2 2 1内核线程 一个内核线程不需要和一个用户进程联系起来。它的创建和撤销是由内核 的内部需求决定的，用来负责执行一个指定的函数。它共享内核正文字段和全 局数据，具有它自己的内核堆栈。它能够被单独地调度并能使用标准的内核同 步机制，如s l e 印0 和w a k e u p 0 等等。内核线程对于执行异步i o 操作非常有用。 一门 笙茎塑! 型墅塑坚一 内核可以简单的创建一个新的线程来处理这种请求，而不是提供一种特殊的机 制，这些请求被这些线程同步处理，而对于内核的其他部分出现异步a 内核线程的创建和使用开销并不是很大。它们使用的唯一资源就是内核堆 栈和在它们不运行时用来保存寄存器上下文的一个区域，( 我们也需一些数据结 构来保存调度和同步的信息) 。内核线程间的上下文切换是很快的，因为内存映 射不用重新刷新。 内核线程不是一个新的概念。系统进程如页面管理进程( p a g e d a e m o n ) 在传统 的u n i x 内核中，它在功能上等同于内核线程。守护进程如n f s d ( 网络文件系统 服务器进程) 在用户级启动，但是一旦启动，就完全在内核中运行。当它们进入 到内核态后，用户态上下文就不需要了。它们也等同于内核线程。因为在传统 的系统中缺少一种单独的抽象概念来代表内核线程，这些进程和那种传统进程 所有的不必要的”垃圾 - - p r o c 结构和u s e r 结构等纠缠在一起。多线程内核允许 这些守护进程作为内核线程来简单实现。 在s o l a r i s 中内核线程是一个基础的轻量级的对象，它可以独立地被调度和 分配到系统的处理器上去运行。内核线程不用和进程联系起来，它可以通过内 核执行特定的函数来创建、运行和释放。这样，内核就不用在内核线程切换时 重新映射地址空间。因此，内核线程的上下文切换耍比一个进程的上下文切换 花费少得多。 内核线程使用的资源仅仅是一个小的数据结构和一个堆栈。内核线程的数 据结构包含下列信息： 保存内核寄存器的拷贝值。 优先级和调度信息。 指向把线程放大调度器队列的指针，或者是线程阻塞时，把线程放大资 源等待队列的指针。 n 墨三兰塑塑型丝生一 堆栈指针。 指向相关的1 w p 和p r o c 结构的指针( 如果线程没有绑定到一个轻量级进 程上，指针为空) 。 维护一个进程中所有线程队列的指针和维护系统中所有线程队列的指 针。 如果有相关的轻量级进程，那么还包括相关轻量级进程的信息a s o l a r i s 的内核是内核线程的集合。这些内核线程中的一些运行轻量级进程， 另外一些执行内部的内核函数。内核线程是可以完全被抢占的，它们可以属于 系统中的任何一个调度类，包括实时类。它们使用特殊版本的同步原语( 信号量， 条件变量等) 来防止优先级逆转。低优先级的线程锁住了高优先级线程需要的资 源，因此阻止了高优先绒线程的向前执行。 内核线程用来处理异步事件，如磁盘延迟写操作，流服务过程和调出队列 节) 。内核把每一个事件同一个优先级联系起来( 通过设定线程的优先级) ，这样 内核就能够恰当的调度它们。内核线程也用来支持轻量级进程，每一个轻量级 进程都连着一个内核线程( 尽管不是所有的内核线程有一个轻量级进程) 。 2 2 2轻量级进程 一个轻量级进程( l w p ) 是一个内核支持的用户线程。它是个在内核线程基 础上的高层抽象，因此内核在支持轻量级线程之前必须支持内核线程。每个进 程可能有一个或多个轻量级进程，每一个都由一个单独的内核线程来支持( 图2 1 ) 。轻量级进程被独立调度并且共享地址空间和进程中的其他资源。它们可以 对i o 或其他资源进行系统调用，同时也能在i o 操作或资源访问的时候被阻 塞。在一个多处理器的系统中，一个进程能真正享受并行所带来的好处，是因 1 4 笙苎塑型兰燮丛 为每一个轻量级线程都能被分配到一个不同的处理器上运行。再者由于等待i o 操作完成或资源被阻塞的只是单个的轻量级进程而不是整个进程，在单处理器 环境中其优势也很明显。 口进程回獭耀口龇线程 图2 0 1 轻量级进程 ，、 j 地址空间 除了内核堆栈和寄存器，轻量级进程也需维护一些用户状态。这主要包括 用户寄存器上下文，当轻量级进程被抢占时这些内容必须被保存。尽管每个 轻量级进程都和一个内核线程相联系，但是一些内核线程是专门处理系统任务 而不支持轻量级进程。 当每一个线程是相当独立的，并且不经常与其他线程交互时，多线程的进 程是十分有利的。用户代码是可以完全被抢占的，所有的轻量级进程在一个进 程中共享一个公共的地址空间。如果任何数据可以被多个轻量级并发地访问， 这种访问必须被同步以保证数据的一致性。因此内核需要提供一些方法来锁定 共享变量，如果一个轻量级进程想访问一个被锁住的数据时它将被阻塞。 能够认识到轻量级进程的局限性是很重要的，大部分的轻量级进程的操作， 巧 笙苎塑型型塑i 垒立 如创建，释放和同步都需要系统调用。系统调用相对来说是开销很大的操作， 因为每个系统调用都需要在两个模式间切换，一个是在调用执行时，从用户态 到内核态，另一个是在调用完成时返回到用户态。在每一个模式切换时，轻量 级进程都要跨越一个保护边界。内核必须把系统调用的参数从用户空间拷贝到 内核空间，并且校验它们来防止恶意进程的破坏。同样地，在从系统调用返回 到用户态时，内核一定要把数据拷贝回用户空间。 当轻量级进程频繁访问共享数据时，同步的开销可能会抵销任何性能上的 优点。在多数的多处理机系统中提供了锁机制，如果锁没有被其他线程占有， 一个线程就可以在用户级上获得锁。如果一个线程企图拥有一个当前不可用的 资源时，它可能执行一个忙等待( b u s y - w a i t ) ( 在资源释放之前一直空循环) ，而不 需要内核的参与。忙等待方法对于那些被暂时占有的资源还是可行的，然而在 其他的情况下，必须阻塞这个线程。阻塞一个线程的操作是需要内核参与的， 因此开销极大。 每一个轻量级进程都要花费相当多的内核资源，包括内核堆栈的物理内存。 因此一个系统不能支持大量的轻虽级进程。进一步地讲，因为系统有一个单独 的轻垃级进程的实现，它必须要通用，能支持大多数合理的应用。它因此也必 须负担许多应用不需要的垃圾。轻量级进程对于使用大量线程，或是那些经常 创建和撤销线程的应用来说是不适合的。最后轻量级进程必须由内核来调度。 对于那些必须经常把控制从一个线程转移到另一个线程的应用，如果它们使用 轻量级进程，那么就不是很容易实现。轻量级进程也带来一些公平问题一 个用户能够通过创建大量的轻量级进程而垄断处理器的使用。 轻量级进程在一个单独的进程中提供多线程控制。这些轻量级进程被独立 地调度，可以并行在多处理器上运行。每一个轻量级进程都被绑定到它自己的 内核线程上，而且在它的整个生命期内这种绑定都有效。 ，6 笙兰壅茎型型塑塑 传统的p r o c 和u s e f 结构是不能充分地表示多线程进程的。在这些对象中的 数据必须被分成每个进程的信息和多个轻量级进程的信息。s o l a r i s 用p r o c 结构 保存所有进程的数据，包括在传统的u 区的和进程相关的部分。 一个新的1 w p 结构保存上下文中的每个轻量级进程的部分信息它包括以 下的信息： 用户级寄存器保存的值( 当轻量级进程不运行时) 。 系统调用的参数、结果和错误代码。 信号处理信息。 资源使用情况和统计数据。 - 虚拟时间报警。 - 指向内核线程的指针。 指向p r o e 结构的指针。 1 w p 结构可以和轻量级进程一起被换出内存，因此那些一定不能换出的信息 如信号掩码，必须要保存在相关的线程结构中。在s p a n 的实现中预留全局寄存 器来保存指向当前线程的指针。因此可以允许快速访问当前的轻量级进程和进 程。 对轻量级进程( 以及内核线程) 可用的同步原语有互斥锁，条件变量，计数信 号量和读写锁。每一个同步工具能表现出不同的行为特性。比如，一个线程想 获得被另一个线程占有的互斥锁，它可能忙等待或是阻塞等待互斥锁被释放。 一个同步对象在初始化的时候，调用者必须指定他所希望的是哪一种行为。 进程中的所有轻量级进程共享一组公共的信号处理程序。但是每一个信号 处理程序可能拥有自己的信号掩码，来决定忽略或阻塞哪一个信号。每一个轻 量级进程也可以指定自己的替换堆栈来处理信号。信号被分成两类陷入和中 断。陷入是由轻量级进程本身产生的同步信号( 如s i g s e g r , s i g f p e 和s i g s y s ) 。 ，7 丝兰塑型差燮塑 这些陷入信号总是传给产生信号的l w p 。中断信号( 如s i g s t o p 和s i g i n t ) 可 以被传递到任意没有屏蔽信号的轻量级进程a 田进程回轻酸进程 ? 核心线程ij 地址空间 、_ 图2 - 2 多路复用轻量级进程的用户进程 轻量级进程没有全局的名字空间，因此对于其他的进程是不可见的。进程 不能直接发送信号到另一个进程中指定的轻量级进程，或者知道发给它消息的 是哪一个轻量级进程。 2 2 3用户线程 用户线程是完全在用户级上提供的抽象概念，而无需内核知道它们的存 在，这通过使用像m a c h 的c t h r e a d s 和p o s i x 的p t h r e a d s 等线程库程序包可以 成功的实现。这些库提供所有的创建、同步、调度和管理线程的函数，而不用 内核的特殊帮助。线程间的交互不包含内核的参与，因此速度非常快。 图2 - 2 把用户线程和轻量级进程结合起来，创建了一个非常强大的编程环 境。内核来识别、调度和管理轻量级进程。一个用户级的库复用在轻量级进程 上的用户线程，并且提供线程的调度、上下文切换和同步等方法，而不涉及到 - 坩 苎苎塑塑燮 内核。实际上，库充当它所控制的线程的微内核。 用户线程有几个明显的优点，它以一个非常自然的方式来对向w i n d o w s 那样的应用进行编程，用户线程也通过把异步操作的复杂性隐藏在线程序中来 提供同步编程规范。这就足以说明用户线程是十分有用的，甚至在那种缺少任 何支持线程的内核的系统中，一个系统可以提供几个线程库，每一个都适用一 个不同类的应用。 用户线程的最大优点就是性能，用户线程是轻量级的，只有当它们附着在 轻量级线程上时才消耗内核资源，它们这种性能的获得是由于功能的实现是在 用户级上，而不是使用系统调用，这样就避免了陷入处理和跨越保护边界时移 动参数和数据的开销。一个非常有用的概念是关键线程大小，它指的是一个线 程用作一个单独实体时必须做的工作量，这个大小取决于创建和使用一个线程 的开销。对于用户线程，它的重要部分的大小一般在几百条指令左右，通过编 译器的辅助可以减少到少于1 0 0 条。用户线程需要非常少的时间去创建，撤销 和同步。表2 - 3 比较了在s p a r c 工作站上内核进程、轻量级进程和用户线程的 不同操作的所表现的执行时间。 表2 3 产生时间使用信号量的同步时间( us ) 用户线程 5 26 6 l w p3 5 03 9 0 进程 1 7 0 02 0 0 另一方面，用户线程也存在一些局限性，这主要是由于内核和线程库之间 信息的完全分离造成的。因为内核不知道用户线程的情况，这样它就不能使用 它的保护机制来保护用户线程不被其他的线程破坏。每一个进程拥有自己的地 址空间，内核保护它们防止其他非授权的进程的访问。用户线程就不享受这种 保护，它们在公共地址空间中操作。从线程互相操作的要求出发，线程库必须 j 9 塾三兰垒茎塑塑耋型 一 提供同步的方法。 这种分开的调度模型带来了许多其他的问题，线程库调度用户线程，内核 调度底层的进程或轻量级进程，两者都不需要知道对方在做些什么，比如，内 核可能抢占一个轻量级进程，而此时它的用户线程拥有一个自旋锁( p i nl o c k ) ， 如果另一个轻量级进程上的用户线程想得到这个锁，它将一直忙等待直到锁的 拥有者恢复运行。同样地，因为内核不知道用户线程的相对优先级，它可能抢 占一个运行高优先级用户线程的轻量级进程，而去调度运行低优先级用户线程 的轻量级进程。 在一些情况下，用户级的同步机制可能运行得不正常。所有的可执行线程 最终都能被调区，时多应用程序都是在这个假设的基础上编写的。当每一个用 户线程都绑定在一个单独的轻量级进程时，该假设是正确的，但当用户线程复 用少量的轻量级进程时，该假设可能不成立。因为当轻量级线程的用户线程在 某个系统调用上阻塞的时候，它可能也阻塞在内核，这使得一个进程中没有可 运行的轻量级进程，这种情况甚至在存在可运行的线程和可用的处理器时也可 能发生。异步i 0 机制有助于减少这类问题的发生。 最后由于没有内核显式地支持，用户线程可能改善其并发性，但是不能增 加其并行性，甚至在一个多处理器的系统中，一个轻量级进程也是不能并行执 行的。 在s o l a r i s 中，用户线程是通过线程库实现的。它们可以在没有内核参与下 创建、释放以及管理。线程库提供同步和调度的方法。这样进程可以使用大量 的线程而不消耗内核资源，而且省去大量的系统调用的开销。尽管s o l a r i s 是在 轻量级进程之上实现用户线程的，但是线程库隐藏了这些细节。大多数应用程 序开发者仅仅和用户线程打交道。 缺省的情况下，线程序为进程创建一个轻量级进程池，并且在此之上复用 2 0 籀二章搜索 | 擎相关技术 所有的用户线程。这个池的大小取决于处理器的数目和用户线程的数目。应用 程序可以对缺省情况重载并指定创建的轻量级进程的数目。它也可以要求系统 为每个特定的线程指定一个轻量级进程。因此一个进程可能有两种类型的用户 线程：绑定到轻量级进程上的线程和那些没有绑定的共享公共轻量级进程池的 用户线程。 通过在少量的l w p 上复用很多的线程可以以较低的代价实现并发。例如， 在一个窗口系统中，每一个对象( 窗口，对话框，菜单，图标等) 都可以用一个 线程代表。在某一时刻只有很少几个窗口是活动的，只有这些线程需要l w p 。 l w p 的数目决定了应用程序可以获得的最大的并行度( 假设至少我们有相同数目 的处理器) 。这个数目还限制了进程在某时刻最多的阻塞操作。 有些时候线程比l w p 多是不利的。例如，当计算两个二维数组的内积时， 我们可以为结果数组的每一个元素分配一个线程。如果处理器的数目很少，这 种方法可能就反而效率不高了，究其原因就是线程库花费了很多的时间来完成 线程切换。如果为结果乘积数组的每一行分配一个线程，并将其与一个l w p 绑 定在一起可能会更有效。 在涉及时间关键性处理的应用中，同时包含绑定的和非绑定的线程是非常 有用的。时间关键性处理可以绑定到分配了实时调度优先级的l w p 上完成，而 其他线程负责其他低优先级的后台处理。在前面的那个窗口系统例子中，用实 时线程来响应用户的鼠标移动书件，这样就可以立即在显示器上反映出鼠标的 移动了。 因为线程库在线程问上下文切换时浪费了大量的时间。如果对乘积数组的 每行创建一个线程，并把每个线程绑定到一个轻量级进程上，效率就会大大地 提高。 如果处理对时间要求很严格的话，应用程序中有绑定的和没绑定的用户线 2 ， 镶二章搜索铂擎相关技术 程是很有意义的。这些临界时间的处理可以由绑定到轻量级进程上的用户线程 来处理，系统分配给它们实时的调度优先级，而其他的用户线程则负责低优先 级的后台处理。在前面的窗1 3 系统的例子中，一个实时的线程可以被分配去响 应鼠标移动，因为这些鼠标移动必须在显示器上立即反映出来。 s o l a r i s 中每个用户线程必须维护以下的状态信息： 线程l d 它允许进程中的线程互相通过信号来通信等等。 保存的寄存器状态包括程序计数器和堆栈指针。 用户堆栈线程可能有出线程库分配的堆栈。内核不知道这些堆栈。 信号掩码每个线程有自己的信号掩码。当一个信号到来时，线程序可 以通过检查线程的信号掩码把信号发送到合适的线程。 优先级用户线程使用相关进程的优先级，由线程调度器使用。内核并 不知道这个优先级，因为它只是调度下面的轻量级进程。 线程局部存储线程允许有一些私有存储( 由线程库来管理) ，来支持c 线程库接口的再版本。举个例子，许多c 线程库例程返回一个错误代码到一个 叫做e n n o 的全局变垃中。如果多个线程并发的调用这个例程将出现混乱的现 象。为了避免这个问题的发生，多线程的线程库把e l t n o 放在线程的局部存储中。 线程使用线程库提供的同步方法，它们与内核中的同步方法相似( 信号量， 条件变量等) 。通过简单地使用放在共享内存中同步变量，s o l a r i s 允许在不同进 程中的线程相互间同步。这些变量也可以放在文件中，通过使用m m a p 映射文 件来访问这些变量。这样就允许同步对象的生命周期超过创建它们的进程，并 可以用它们来对不同进程中的线程进行同步。 2 2 丝兰塑堕型塑塑塑 2 3 内存映射文件 在s u n o s 4 0 中，s u nm i c r o s y s t e m ，引入一种称为v m ( 虚存的缩写) 的内存 管理体系。以往的s u n o s 版本都是采用基于b s d 的内存管理模型，它具有上 一章中所述的各种局限性。特别是s u n o s 希望能够提供内存共享，共享库以及 内存映射文件等支持。如果不对b s d 的设计进行大的修改，不可能实现这些功 能。另外，由于s t m o s 运行在许多不同的硬件平a z ( m o t o r o l a 6 8 0 x o ，i n t e l 3 8