（计算机系统结构专业论文）分布式系统的通信和对共享资源互斥访问的研究与实现.pdf

摘要 摘要 随着人们对信息日益增长的需求，信息服务提供者们的服务器系统面临着巨 大的速度和容量压力。各种价格高居不下的大型服务器虽然能够缓解这种压力， 可是仍然无法足够应付越来越商的访问频率。因此借助于网络的飞速发展，分布 式系统应运而生。为了满足众多信息服务提供者对高性能、高性价比、高可扩展 性的分布式服务器系统的需求，我们将对本研究室已经实现的、基于l i n u x 内核的、 具有自主知识产权的分布式系统d p s ( 俗称打不烂) 进行全面的升级。d p s 的升 级目标是为用户提供一令更大流量，更高性能，更可靠的服务器系统。并且从目 前宽带视频点播( b o d ) 方面的应用，扩展到电子政务，电子商务等领域。 本文前半部分讨论了分布式系统的特征和设计问题，然后简要介绍了l i n u x 内核的相关技术，最后给出了d p s 的设计特征和框架。后半部分详细讨论了通信 机制( l k c c ) 的升级，互斥算法的重新设计和实现。主要包括以下内容：l k c c 会 话的改进，在l k c c 增加组播和对紧急数据的优先发送功能，新的互斥算法( d p h c ) 的提出以及实现和测试。 l k c c 以u d p 协议为基础，在此基础上采用了o t p 协议，通过会话来完成 数据的可靠传输。为了改善系统的性能和满足用户的需求，将原来o t p 协议中会 话的一一应答改成了组应答方式；由于d p s 系统的资源存在多个副本，所以在 l k c c 中加入了组播功能；又因为当系统繁忙时，某些紧急数据得不到优先发送， 降低了系统的性能，所以本文又实现了对紧急数据的优先发送。 d p h c 算法是一种采用自动迁移容错的、根据资源选择仲裁者的互斥算法。 该算法将不同锁对象( 共享资源) 的仲裁者分布到了系统中的各个节点，让每个 仲裁者都像集中式算法中的控制者一样的工作，因此，该算法具有集中式算法的 消息量和分布式算法的负载均衡。而且当请求加锁的进程发现它的仲裁者失效以 后，会马上为锁对象产生一个新的仲裁者并向它发送请求消息，如果节点相继失 效，直到只剩下它自己时，它仍然能够产生仲裁者，就是它自己，这种自动迁移 容错方法使得它还具有分布式算法的容错度。 关键字：分布式通信互斥网络锁 a b s t r a c t a b s t r a c t w i t ht h ei n c r e a s i n gi n f o r m a t i o nr e q u i r e m e n t ，s e r v e rs y s t e mo fi s p ( i n t e m e ts e r v e r p r o v i d e r ) i sb e i n gf a c e dw i t ht r e r n e n d o u st e n s i o n s o m ee x o r b i t a n tg r e a ts e r v e rc o u l db e r e s o l v et h eq u e s t i o n b u tc r n tc o m eu p 谢t l lt h ei n c r e a s i n g 疳e q u e n c yo fa c c e s s i n g w i t h t h er a p i dd e v e l o p m e n to ft h ec o m p u t e rn e t w o r k , d i s t r i b u t e da p p l i c a t i o n sb e c o m em a i n s t r e a mg r a d u a l l y i no r d e rt om e e tt h en e e do fd i s t r i b u t e da n dp a r a l l e ls e r v e rs y s t e m ， w h i c hh a sh i 曲p e r f o r m a n c e ，h i 咖s c a l a b i l i t ya n d 、枷mar e a s o n a b l ep r i c e ，w eh a v e e n t i r e l yd e v e l o p e dd p st h a ti sad i s t r i b u t e da n dp a r a l l e ls y s t e mb a s e do nl i n u xk e r n e l b o ds e r v e rs y s t e mi sj u s tat y p i c a le x a m p l e ，i nf u t u r ed p sw i l lb ea p p l i e di ne l e c t r o n g o v e r n m e n ta f f a i ra n db u s i n e s sa f f a i r sa n ds oo n i nt h ef i r s tp a r to f t h i st h e s i s ，w ef i r s t l yd i s c u s ss o m ed e s i g ni s s u e sa n dc h a r a c t e ri n d i s t r i b u t e ds y s t e ma n d 也e ni n t r o d u c es o m el i n u xk e r e e li n f o r m a t i o nb r i e f l y ，l a s t l y d e s c r i b e t h e f r a m e w o r k a n d t h ec h a r a c t e r o f d f s 。i n t h es e c o n d p a r t ，t h i s t h e s i s d e s c r i b e t h e u p g r a d eo fl k c ca n dt h ei m p l e m e n to fn e tm u t u a le x c l u s i o n ，i n c l u d i n g t h e a m e l i o r a t i n go fc o m m u n i c a t i o ns e s s i o nm e c h a n i s m ，t h ei m p l e m e n to fm u l t i s e n da n d p r e f e r e n t i a ls e n d i n go f e m e r g e n tm e s s a g e ，a n dd p h ca l g o r i t h m l k c c ，al i n u xk e m e lc o n c u r r e n tc o m m u n i c a t i o nm e c h a n i s m ，u s e so b j e c t t r a n s f e rp r o t o c o lt os e n da n dr e c e i v ed a t a 。i no r d e rt oi m p r o v i n gs y s t e mp r o c e s s i n g c a p a b i l i t ya n dt or e s p o n s ec l i e n tr e q u e s t s ， s e s s i o nm e c h a n i s mi sc h a n g e d ；b e c a u s ea g r e a to fs o u r c eh a v es e v e r a lc o p y , m u l t i s e n di sa d d e d ；b e c a u s ed p so f t e nh a sg r e a tl o a d ， s o m ee m e r g e n tm e s s a g ec a n n o tb es e n dd u l y ；c a p a b i l i t yo fs y s t e mi sd e p r e s s e d ，m e s s a g e p r ii sa d d e dt ol k c c d p h cu s e sa u t o - t r a n s f e rt oi m p l yd e p e n d a b i l i t ya n dc h o o s e si n t e r c e d e rb yt h e n a l t l eo fs o u r c e b e c a u s ei td i s t r i b u t e si n t e r c e d e r so fd i f f e r e n ts o u r c et oe a c hn o d ei n s y s t e m ，l e t se a c hi n t e r c e d e rw o r k a sc o n t r o l l i n gn o d ei nc e n t r a l i z i n gc o n t r o la r i t h m e t i c ， i th a sm e s s a g en u m b e ro fc e n t r a l i z i n gc o n t r o la r i t h m e t i ca n dl o a de q u i l i b r i u mo f d i s t r i b u t e da r i t h m e t i c c h a r a c t e r i s t i co fa u t o t r a n s f e rb r i n g sd e p e n d a b i l i t yo fd i s t r i b u t e d a r i t h m e t i c ，b e c a u s ew h i l ean o d eh a sd o w n ，o t h e rn o d e s r e q u e s t st h a th a db e e ns e n tt oi t c a ns e n dt oo t h e rn o d e sb yp r o d u c i n gn e wi n t e r c e d e r s od p h cc a ns a t i s f yc o m p l e t e l y n e e do fd e p e n d a b i l i t y k e y w o r d s ：d i s t r i b u t e d c o m m u n i c a t i o nm u t u a le x c l u s i o nn e tl o c k i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。， 签名：损! 雪建 日期：2 一，z 年月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：粒臼垒 1 导师签名：! 竺查! 日期：a 年f 月乙日 第一章引言 第一章引言 鉴于人们对计算机越来越不可或缺的依赖，为了提高计算机系统的性能，人们 做了大量的尝试。首先设计出了具有共享主存的紧偶合多处理器系统，然后又研 制出了具有分布共享主存或无分布共享主存的大规模并行处理器系统( m p p ) 。虽 然这两种类型的计算机系统具有较高的速度，能够满足大多数用户的需要，但是 它们的价格过于昂贵，普通用户难以承受。而且当今世界用户的计算资源分布在 越来越广阔的地方，一个超级计算机只能矗立在一个地方，难以满足用户越来越 频繁的计算需求。 上个世纪八十年代以来，越来越多的信息处理系统从通过哑终端连接中心机房 大型机的集中式计算模式向网络化的个人工作站和服务器结构的网络计算模式转 移，进一步发展成为以网络为基础的分布式计算机系统。它通过高速的网络将各 种不同的计算单元连接起来，形成具有很高处理能力和协作能力的计算机系统， 其固有的分布性能够满足许多分布式应用的需求、通过将工作负载分散到众多的 系统节点中能够达到很高的并行性、可靠性、其渐增式的增长方式更符合企业业 务发展的需求。因此，国内外对分布式系统进行了大量的研究，从不同的研究角 度，可以将其分为三大部分：分布式操作系统、分布式文件系统、分布式数据库 系统。本研究室通过二十余年的努力，在分布式系统方面取得了许多令人振奋的 成果。更幸运的是，近年来，l i n u x 以其良好的开放性、内核源代码公开、免费获 得源代码等特点使人们有机会将其改造成为能够满足特殊应用的操作系统。作为 一种新的尝试，我们在l i n u x 内核下开发了能够满足各种用户应用的分布式系统 ( 包括操作系统和数据库系统) ，并且得到了用户的认可。从用户意见的反馈和我 们大量的研究和测试中，我们又对d p s 进行了全面的升级，使系统的容错性、可 靠性和可扩充性得到了进一步的提高。在整个升级中，我对支撑层中的通信模块 进行了升级，对互斥模块的进行了重新设计与实现。 本课题主要研究分布式系统的通信和分布式互斥算法。对于通信模块，是在原 有的基础上进行改进，提高它的效率和速度并且支持紧急数据的紧急发送；对于 互斥模块，本人提出了一种具有自动迁移特征的、根据资源选择仲裁者的互斥算 法d p h c 算法，并且实现了该算法，为上层提供了一个更高效、更公平、更健 壮的网络互斥锁。 电子科技大学硕士学位论文 全文安排如下： 第一章引言 本章简要介绍本文的目的、任务及结构。 第二章分布式系统概述 本章内容包括：简介分布式系统，描述分布式系统支撑层的结构框架及模块功 能、简介相关的l i n u x 内核技术。 第三章分布式系统的通信研究 本章简介几种常见的消息通信模式，重点从软件结构方面描述l k c c 通信模 块的设计；然后给出l k c c 的不足，并且提出解决方法。 第四章共享资源互斥访问的研究与实现 本章首先简要概述几种典型的互斥算法，分析各种算法的优缺点；然后提出一 种新的采用自动迁移容错，并且根据资源选择仲裁者的互斥算法，并将其实现； 最后分析该算法的性能。 第五章总结与展望 首先对本文所傲的工作进行总结，然后对所涉及的技术进行展望。 第二章分布式系统概述 第二章分布式系统概述 2 。1 分布式系统的概念和特征 在人类生产生活中一直存在着固有的分布式并行应用，例如，在我们的社会 中，人是相互独立的，而他们经常会相互合作来做某件事情，通常他们会将这件 事情支解成若干部分，不同的人做不同的部分，并且通过互相交换信息来并行的 作这件事情，以便能快速完成它。在计算机世界中，通过过去的半个世纪的发展， 计算机技术取得了惊人的进步，使硬件的性能价格比大大提高，网络的速度越来 越快，而大型计算机，超级计算机依然昂贵，且计算能力也相当有限。使用宽带 网络将大量单个计算机组成高速超级计算系统不仅成为可能，而且变得十分必要。 就像人类社会一样，以单个计算机作为自治个体，来相互合作的完成某件事情， 采用分布式并行的思想来组织的这种计算机系统，它们被称为分布式系统。 因此我们可以这样来定义分布式并行系统：一个分布式系统是一个对用户看起 来像普通系统，然而运行在一系列自治处理单元上的系统，每个处理单元有各自 的物理存储器空间并且信息传输延迟不能忽略不计。在这些处理单元间有紧密的 合作。系统必须支持任意数量的进程和处理单元的动态扩展。 一般分布式系统都具有以下四种特征。分布性：分布式系统具有功能分布和任 务分布的特征。对于松散耦合系统，还可能呈现地理分布的特征。自治性：不论 分布式系统的处理单元采用何种形势，至少它总含有处理机和局部存储器。并具 有独立执行任务的能力，因而每个处理单元都有一定的自治性。并行性：由于有 多个处理单元，因此可以把一个作业的诸任务，分配到多个处理单元上进行并行 处理。容错性：分布式系统中，并不会因为某些处理单元的出错而使系统无法运 转。相对于普通的并行系统，降低了对处理单元可靠性的依赖。基于分布式系统 的这些特点，近年来人们开始深入的研究分布式系统。可将其粗略分为分布式操 作系统、分布式文件系统、分布式数据库系统等各种各样的分布式系统。下一节 将举例说明各种分布式系统的研究现状以及本人参与的研究工作。 2 2 分布式系统实例 皇王型垫查堂堡主堂焦堡塞 前面两节介绍了分布式系统的概念和特征，并且简要的将其分为三个部分：分 布式操作系统、分布式文件系统、分布式数据库系统。文件系统本该是操作系统 的部分，但是在分布式环境下，它有了很强的独立性，一种文件系统可以被多 种操作系统所共享，并且作为系统资源的存在形式，它本身的具有很多独特和复 杂的特点，因此我们在介绍了分布式操作系统后，有必要再介绍一下分布式文件 系统。对于分布式数据库系统，是目前的研究热点，有兴趣的读者可以见参考文 献【4 】。 2 2 1 分布式操作系统 m a e h 系统 m a c h 系统是由c a m e g i e m e l l o 大学的m g ( r a s u d ，1 9 8 6 ) 和a c c e n t ( r a s h i da n d r o b e r t s o n , 1 9 8 1 ；r a s h i d ，1 9 8 5 ；f i t z g e r a l d ，1 9 8 6 ) 项目的后继者。它可以在由网络连接 的多处理器和单处理器机器上运行，并保持了对u n i x 的兼容性。它的主要设计 目标及特征如下有下面积几个方面。多处理器操作：m a c h 是在共享内存的多处理 系统上执行的，所以，内核程序和用户程序可以在任何一个节点上运行。网络搡 作的透明延伸：为了允许分布式程序通过网络在单处理器和多处理器系统之间透 明的延伸，m a e h 采用了将端口当成目标地址的独立的通信模型。用户级服务：m 越1 支持基于对象的模型，在这个模型中，资源由内核或用户级服务器管理。大多数 u n i x 工具的主要目的是在用户级应用，爿= 提供与现有n i n x 相兼容的二进制码。 操作系统仿真：为了支持u n i x 操作系统和其他操作系统的二进制仿真，m a t h 允 许将操作系统调用透明地转换为仿真库调用，然后转换为使用用户级操作系统服 务器。灵活的虚拟内存管理：m a c h 为了进行u n i x 仿真和支持其他子系统，做了 大量工作去增加虚拟内存功能。 总得来说，m a c h 是一个非常复杂的系统，为了保持对u n i x 的兼容性，它对 一些复杂工具进行了大量的仿真，但是仍然只有少数u n i x 程序可以按其原始的 形式在m a t h 中使用。 c h o r u s 系统 c h o r u s 项目开始于1 9 7 9 年的法国，起初它的目标的是建立一个基于消息的计 算模型，现在它已经成为了比较成功的操作系统了。一个c h o r u s 系统由网络连接 的单处理器和多处理器构成，在结构上与m a c h 有许多相似之处。c h o r e s 内核是一 个支持子系统的内核，一个c h o r u s 子系统是一个服务器集合，它提供对某个操作 电子科技大学硕士学位论文 作来达到高用性目的的。 服务器复制其实就是建立文件副本。c o d a 中复制的单位是卷( v o l u m e ) ，卷是存 放在服务器上的共享文件的集合，它构成了名字空间中的一棵子树。存放有某个 卷的副本的全部服务器构成了一个集合，称为该卷的v s g ( v o l u m es t o r e g r o u p ) 。 c o d a 仅支持只读副本，这是从a f s 继承下来的特性。c o d a 的客户端进程称为 v e n u s ，它负责使用文件副本。当客户机缓存了某个卷的数据之后，v e n u s 就维护 了该卷的可访问服务器集合，它是该卷v s g 的子集，称为a v s g ( a c c e s s i b l e v o l u m e s t o r a g eg r o u p ) ，如果没有故障发生，它和v s g 是相等的。如果探测到某个服务器 故障，就把该服务器从a v s g 中删除。v e n u s 在访问c o d a 中的文件时首先在本 地缓存中查找，如果本地缓存中有该文件的数据，v e n u s 就直接访问本地缓存。如 果本地缓存中没有所需数据，v e n u s 从a v s g 中选择一个服务器来访问，选择的标 准通常是服务器的性能指标，例如服务器和客户机之间物理连接的远近、服务器 负载、服务器c p u 处理能力等。 无连接操作( d i s c o n n e c t e do p e r a t i o n ) 就是在无连接操作状态下，客户机不访问 服务器，直接读取或修改本地缓存中的文件数据。c o d a 客户机把无连接操作看成 一种临时状态，它总是尽可能早地转变到正常操作状态，正常操作和无连接操作 之间的转换对用户是透明的。在正常操作中，查找缓存失败仅仅对性能有所影响， 但在无连接操作中，如果在缓存中找不到所需数据，用户程序会被挂起自到恢 复为正常操作或用户取消相应的文件系统调用为为止。可见，在无连接操作中避 免缓存查找失败是非常重要的。 2 3d e s 系统 2 3 1d 陌系统柏设计基础 在研究各种分布式系统的过程中，我们发现在分粕式系统中，对于任务的分配 调度和共享资源的管理是系统要解决的关键问题。而操作系统管理本地资源和提 供服务的功能已经有开放的l i n u x 为我们实现了，因此d p s 借助l i n u x 操作系 统内核，省去了很多有关的操作系统内核的设计和开发，并且保持了对u n i x 系 列操作系统的完全兼容，本节简单的介绍在支撑层的实现中大量地使用的内核线 程、互斥和同步等l i n u x 内核功能机制以及链表操作，以便在接下来的几个章 节中描述和理解通信和网络锁的设计和实现。 节中描述和理解通信和网络锁的设计和实现。 第二章分布式系统概述 系统的仿真支持，或提供一些应用的主要服务。 它有与m a t h 相似的设计目标，例如，为开放式系统服务以及消息传递式访问 提供微核支持，提供对操作系统( 特别是u n i x ) 和其他子系统的仿真，支持网络 操作的内核工具的透明性，对共享内存多处理器的利用、动态安装的服务器。 但是它也有自己不同的设计目标，例如，对服务器组和服务器重构的支持，分 布式内存多处理器的操作，实时操作等等。c h o r u s 为了在内核中提供对子系统的实 时支持，提出了线程特权的灵活分配方案，并允许采用习惯的线程调度策略。 还有很多其他优秀的分布式并行操作系统例如c d c s 、a m o e b a 等，他们都有 很好的应用和研究价值。在我们的研究中，这些优秀的操作系统给了我们很多的 启示。但是由于各种各样的原因，他们都存在着实用性差这个严重的缺点。 2 2 2 分布式文件系统 当前的分布式文件系统大致可以分为三类：一是基于共享文件和缓冲的文件系 统，如n f s 等；二是基于副本机制的文件系统，如c o d a 、i n t e r m e z z o 等；三是基 于并行处理的机群文件系统，如g f s ，m o s i x 等。 n f s n f s ( n e t w o r kf i l es y s t e m ) 是1 9 8 5 年山s u nm i c r o s y s t e m 公司开发，它是基于 u n i x 上作站上的，这些上作站通过它来透明存取远程服务器上的文件或目录。它 目前己被移植到几乎所有u n i x 系统( 包括l i n u x ，f r e e b s d ) 及v 1 v i s 和d o s 上， 并成为事实上的上业标准。 n f s 是一种典型的基于共享文档和缓冲的分布式文件系统，它是面向客户服 务器模式的，每个节点即可以作为服务器也可以作为客户，但客户与服务器是非 对称的。为了完成文件的共享操作，服务器的客户端必须做相应的操作：在服务 器端，必须把欲共享的目录写入配置文件，并执行输出共享命令：而客户端则要 执行挂接命令把服务器输出的目录挂接到本地的某目录下。 n f s 只是将文件系统从单机上扩展到网络中，为用户提供了存储网络文件的透 明性，但它不支持副本，一台服务器失效后系统无法再正常服务，因而它不是具 有高可用性的系统。 c o d a c o d a 在1 9 8 7 年山卡内基一梅隆大学开发，它的前身是a f s 。c o d a 和a f s 相 比，主要的改进在于系统可用性。c o d a 最著名的就是采用服务器复制和无连接操 电子科技大学硕士学位论文 作来达到高用性目的的。 服务器复制其实就是建立文件副本。c o d a 中复制的单位是卷( v o l u m e ) ，卷是存 放在服务器上的共享文件的集合，它构成了名字空间中的一棵子树。存放有某个 卷的副本的全部服务器构成了一个集合，称为该卷的v s g ( v o l u m es t o r e g r o u p ) 。 c o d a 仅支持只读副本，这是从a f s 继承下来的特性。c o d a 的客户端进程称为 v e n u s ，它负责使用文件副本。当客户机缓存了某个卷的数据之后，v e n u s 就维护 了该卷的可访问服务器集合，它是该卷v s g 的子集，称为a v s g ( a c c e s s i b l e v o l u m e s t o r a g eg r o u p ) ，如果没有故障发生，它和v s g 是相等的。如果探测到某个服务器 故障，就把该服务器从a v s g 中删除。v e n u s 在访问c o d a 中的文件时，首先在本 地缓存中查找。如果本地缓存中有该文件的数据，v e n u s 就直接访问本地缓存。如 果本地缓存中没有所需数据，v e n u s 从a v s g 中选择一个服务器来访问，选择的标 准通常是服务器的性能指标，例如服务器和客户机之间物理连接的远近、服务器 负载、服务器c p u 处理能力等。 无连接操作( d i s c o n n e c t e do p e r a t i o n ) 就是在无连接操作状态下，客户机不访问 服务器，直接读取或修改本地缓存中的文件数据。c o d a 客户机把无连接操作看成 一种临时状态，它总是尽可能早地转变到正常操作状态，正常操作和无连接操作 之间的转换对用户是透明的。在正常操作中，查找缓存失败仅仅对性能有所影响， 但在无连接操作中，如果在缓存中找不到所需数据，用户程序会被挂起，自到恢 复为正常操作或用户取消相应的文件系统调用为为止。可见，在无连接操作中避 免缓存查找失败是非常熏要的。 2 3d 陌系统 2 3 1d 陌系统的设计基础 在研究各种分布式系统的过程中，我们发现在分布式系统中，对于任务的分配 调度和共享资源的管理是系统要解决的关键问题。而操作系统管理本地资源和提 供服务的功能已经有开放的l i n u x 为我们实现了，因此d p s 借助l i n u x 操作系 统内核，省去了很多有关的操作系统内核的设计和开发，并且保持了对u n i x 系 列操作系统的完全兼容本节简单的介绍在支撑层的实现中大量地使用的内核线 程、互斥和同步等l i n u x 内核功能机制，以及链表操作，以便在接下来的几个章 节中描述和理解通信和网络锁的设计和实现。 第二章分布式系统概述 l i n u x 是一个符合i e e ep o s i x 标准，支持多任务、多线程的操作系统，它将 进程( 或线程) 的状态分为就绪状态、轻度阻塞状态( 可以响应信号) 、深度阻塞 状态( 不响应信号) 、僵死状态、暂停状态等五个状态。在内核态下，使用 k e r n e l _ t h r e a d 函数来创建内核线程。一旦创建成功，新的内核线程被设置为运行 态状态从而接受内核的调度。 在多线程应用模型中，解决线程间互斥访问共享资源的一种手段就是使用信 号量机制。l i n u x 也提供了操作信号量的函数d o w n 0 和u p 0 。信号量的实质就是一 个计数器c o u n t 加上一个等待队列w a i t 。当线程要进入临界区时，它调用d o w n ， 如果c o u n t 值大于0 ，则可以访问共享资源；否则线程被加入到等待队列w a i t 中， 阻塞等待其它线程退出临界区。当线程结束访问共享资源而退出临界区时，它调 用u p 来唤醒等待队列w a i t 中阻塞的线程。被唤醒的线程脱离等待队列w a i t 并被 加入系统的运行队列中，从而被调度运行并访问共享资源。 限于篇幅，不再讨论其他操作，相关内容请参看l i n u x 内核源码。 2 3 2 d p s 系统 本研究室基于l i n u x 自主开发了了一种分布式系统一d p s ，它主要由文件系统 d p f s 和调度系统d p s s 实现。d p f s 实现了对资源的管理，d p s s 实现了对任务的 调度。下面首先介绍d p s 的大体特征，然后介绍支撑层的作用。 d p s 是面向服务器的，它的服务对象是各种服务器程序，总的目标是让这些服 务器程序能透明地访问整个系统的资源，并且必须为这些程序提供最优的运行环 境，它主要有以下鲜明的特征： l 、对用户的透明性：呈现给用户的只是单一的系统镜像，而隐藏其底层的分 布式特性。对于连接到每台机器上的用户，可以像访问单机系统那样访问整个系 统的所有共享资源，而无需知道这些资源实际在哪台机器上。 2 、高可靠性：系统中一个或几个节点的失效，不会影响系统的正常服务。所 有系统中的共享资源，将根据用户的需求建立多个副本，并且由系统动态保证这 些副本的一致性。当系统中正在访问的资源所在的机器出现故障时，对该资源的 访问将自动转移到其它正常工作的服务器的副本上。当故障机重建后，将通过目 志系统完成其故障期间未完成的操作，以保证系统的一致性。 3 、高可扩展性：系统中的每个节点都是一个自治系统，加入系统后既能为其 它服务器提供服务，又可获得其它服务器的服务，从而使其功能、性能得以扩展。 电子科技大学硕士学位论文 并且系统中的节点数可按需动态增加或减少，而不会影响整个系统的服务。 2 3 3 d p s 的支撑层 从2 3 节中我们可以看出，分布式系统的所有优点都严重的依赖网络质量，因 此通信是分布式并行系统最基本的要求；对于系统中共享资源的安全访问，则是 需要互斥的，因此互斥也是必须的；系统是一个有机的整体，有协作、有分工， i 司此，每个节点都必须了解系统的状态信息；我们在d p s 中将这三种功能放在支 撑层中实现。其中有四个模块：通信模块、时钟同步模块、节点管理模块，网络 锁模块；通信模块实现了消息通信a p i ，能够为上层模块提供统一的消息通信接口， 时钟同步模块；网络锁模块提供了分布式互斥机制，为分布式系统中多进程对共 享资源读写一致性的访问提供支持。本人在开发d p s 时主要改进了支撑层中的通 信模块和重新实现了网络锁模块，第三、四章将重点论述这两个模块。由于网络 锁的实现除了需要通信模块外，还需要节点管理模块和时钟同步模块的支持，所 以下面就简要描述这两个模块的功能。 节点管理器 众所周知，分布式系统是由多台计算机组成的，作为个有机的协作整体，每 个节点必须充分了解和掌握整个计算机系统的基本状态信息，这包括系统是由哪 些节点构成的、每个节点的节点名和网络地址、一个节点是何时加入系统、何时 退出系统的，节点是否发生了故障等等信息。所以节点管理器的功能就是负责收 集和维护这些系统节点信息，并且向其他子模块提供相应的节点服务。有取得本 节点的地址g e 幽c m a d d r ( ) 、取得本节点的节点名g e t l o c a l n m e ( ) 、判断一个 节点是否是活动的i s a c f i v e ( ) 等服务。 节点管理器还为上层其他模块提供了注册和注销节点事件处理函数的功能。节 点事件分为s i t eu p 、s i t ed o w n 和s i t ee r r o r ，分别表示节点刚启动、节 点退出、崩溃节点。一旦这些节点事件发生，节点管理器就会调用相应的处理函 数，那么其它模块就能根据事件的发生作相应的处理。 时钟同步 在分布式并行系统中，由于没有统一的硬件时钟，所以采用了网络时间协议提 供的算法，并且在实验中进行多次分析和改进，为分布式并行系统提供了统一的 逻辑时间。时钟同步模块主要为我们提供了一个函数g e 恤。诫i m e 0 - 得到当前时 间。它的误差范围为2 9 s 。 第三章分布式系统的通信 第三章分布式系统的通信研究 在分布式系统中，各节点之间频繁的交换信息、相互协作，构成一个有机整 体。通信是分布式系统的基础，其效率的高低将决定系统的整体性能。目前存在 各种各样的消息传递模型，例如发布一订阅模型、f i f o 通道模型、消息中间件 通信平台。但是，这些消息模型实现相对复杂，而且都是面向应用的，不适合内 核下开发的分布式操作系统使用。在d p s 的研究过程中，我们已经实现了一种 l i n u x 内核下基于会话的并发消息通信机制l k c c ( l i n u xk e r n e lc o n c u r r e n t c o m m u n i c 觚o n ) 。l k c c 以面向非连接的u d p 协议为基础，在u d p 协议之上 采用o t p 协议，并通过会话控制来完成数据的可靠传输。l k c c 中采用动态线 程池技术来并发处理客户请求，极大地提高了处理能力。l k c c 封装了底层的通 信细节，为分布式操作系统的其他模块提供一个统一透明的调用接口。l k c c 兼 顾了效率和可靠性的要求，可以为分布式系统提供高效和可靠的通信服务。但是 l k c c 对来自上层的所有消息都同等对待，在网络异常繁忙的分布式并行系统中， 某些紧急性较高的消息不能得到及时处理，这样可能严重降低系统的性能，在网 络锁中，甚至可能会引起系统的死锁和瘫痪，因此本文提供一种处理紧急消息的 枫制；另外，由于系统中很多资源存在着多重副本，很多时候都会用到组播而 l k c c 并没有实现组播，因此，本文又提供了一种可靠的组播功能( m u l s e l l d ) ； 最后，l k c c 中的会话层采用的是一一应答方式，效率比较低下，本文改进了应 答方式，减少了应答次数：这种改进后的通信模块，我们把它叫做l k c c 2 。 3 1 常见的消息通信模式 当今除了少数媒体和大型软件系统运行在单机上以外，绝大多数都使用了计 算机网络。使用分布式系统的原因和好处很多，诸如实现资源共享、提高系统可 靠性、降低商业成本等等。实现应用的分布式的一个重要先决条件就是：分布式 系统中的子系统必须相互协作，需要一种相互通信的手段。然而，问题在于有太 多的通信机制可供选择。以u n 为例，可能要用到t c p i p 、套接字、t l i ( 传 输层接口，t r a l l s p o r tl a y e ri n t e r f a c e ) 或r p c ( 远程过程调用，r e m o t e p r o c e d u r e c a l l ) 等等。本节先介绍几中常见的通信模式和消息模型，这些模式和 电子科技大学硕士学位论文 模型对l k c c 的理解具有重要的参考价值和借鉴意义。 3 1 1 转发器一接收器模式( f o r w a r d e r - - r e c e i v e r ) 该模式由转发器、接收器和对等体( p e e r ) 三种组件构成。图3 1 给出了 该模式的静态关系。 斤磊品鬲 厂而面；i s e n d ms 9 i f p i + 8 d e e n l l v d e m r o i + m a r s h a s l o g o p e e r l 幽r e c e i v e a m r e c e i v e rs gi r e c e h t e 0 u n m 甜s h a l ( ) r e c e l v e m s g o r ec e i v e 0 u n m a r s h a l o rrecerecelvemego 川s g”日m 硝 p e e r 2 f o r w a r d e r il s e n d ms g h ! ! ! ! ! ! ma r e h a l o d ei v e r ( ) s e n d ms 9 0 煳3 1f o r w a r d e r - - r e c e i v e r 模式荧系吲 对等体组件负责应用任务，它使用转发器向远程对等体发送消息，使用接收 器接收其它对等体传送来的消息。如图3 1 所示。 转发器组件跨越进程边界发送消息。它提供了个通用接口，该接口是一个 特殊i p c 机制的抽象，并且包括列集( m a r s h a l ) 消息功能和传送消息的功能。 接收器负责接收消息。它提供了一个通用接口，该接口是一个特殊i p c 机制 的抽象，它包括接收消息的功能和散集( u n m a r s h a l ) 消息的功能。 f o r w a r d e r r e c e i v e r 模式为对等交互模型的软件系统提供了透明的进程问通 信，它引入转发器和接收器将对等体从底层通信机制中分离处理。 3 1 2 客户机分配器- 服务器模i ；( c l i e n t d i s p a t c h e r - s e r v e r ) 该模式由客户机、分配器和服务器三部分组成，其静态关系如图3 - 2 所示。 第三章分布式系统的通信 图3 2 ：c l i e n t - - d i s p a t c h e r - - s e r v e r 模式关系图 客户机的任务是去执行特殊领域的任务。为了执行处理任务，客户机访问由 服务器提供的操作。在发送请求给服务器之前，客户机向分配器请求信道，利用 这个信道与服务器通信。 服务器为客户机提供一组操作。它既可以注册自身，也可以通过其名字和地 址向分配器进行注册。一个服务器组件可以与客户机位于同一主机，也可以位于 网络中某个节点上。 分配器提供在客户机与服务器间建立通信信道的功能。分配器将服务器组件 的名字映射为其物理地址，利用现有的通信机制建立与服务器的通信链路并将通 信旬柄返回给客户机。为了提供名字服务，分配器实现了用来注册和定位服务器 的功能。 c l i e n t - d i s p a t c h e r - s e r v e r 模式通过在客户机与服务器间引入一个中间层一一分 配器组件，并借助分配器提供的名字服务来实现位置透明性，从而隐藏了客户机 与服务器间建立通信连接的细节。 3 1 3 出版者一订阅者模式哪b 啮h e r _ s h b s c b e r ) 在该模式中，关键对象是出版者( 有时也被称为目标，s u b j e c t ) 和订阅者( 有时 也被成为观察者，o b s e r v e r ) ，它们的关系如图3 3 所示。 9 电子科技大学硕士学位论文 图3 - 3 ：p u b l i s h e r s u b s c r i b e r 模式关系图 订阅者的状态依赖于出版者的状态，一旦出版者的状态发生改变，所有的订 阅者都得到通知。为此，出版者为订阅者提供注册和注销功能，订阅者自行订阅 或取消订阅。出版者在通知订阅者时，可以采用p u s h 或p u l l 模式。在p u s h 模式 中，当出版者通知订阅者时，自接发送更改的数据，订阅者无权选择是否和何时 取回数据，只能被动接收：在p u l l 模式中，出版者仅仅发送最少量的信息给订阅 者，由订阅者决定是否和何时取回数据。p u b l i s h e r s u b s c r i b e r 模式提供了一种合 作组件状态同步化的机制。 3 1 4 消息中间件( m o m ，m e s s a g e o r i e n t e dm i d d l e w a r e ) 在异步分布式系统中，可以采用消息中间件来发送和接收消息。图3 - 4 给出 了消息中间件一般的消息模式。 图3 4 消息中间件 对于消息发送者，它只需要将消息发送给消息中问件而无需阻塞等待。剩下 的上作完全交给消息中间件，消息中间件负责将消息转发给消息接受者。对于支 持可靠传输( g u a r 锄t e e dd e l i v e r y ) 的消息中间件，更能保证在消息接受者暂时不可 达的情况下不会丢失消息。典型的消息中间件有i b m 的m q s e r i e s ，m i r c r o s o f t 的 m s m q ，它们均能实现可靠传输、容错处理、负载平衡等功能。 3 2l k c c 的模型 1 0 蔓三童坌塑塞薹竺塑望焦 3 2 1 重要定义 1 消息 在l k c c 中，将消息定义为如下三元组： m e s s a g e = i d 定义为整数，用来唯一的标识一条消息；d a t a 定义为一段任意长度的字 节流：l e n 定义为整数，用于指明消息长度。可以这样理解该三元组：把d 看成消 息的名字，消息的内容为d a t a ，消息的长度为l e n 。 对于底层的通信来说，它并不关系消息的内容，而只负责正确传输它们，消息 的具体含义由消息的接受者负责解释。 2 对象 在l k c c 中，将对象定义为如下三元组： o b j e c t = i d 定义为整数，用来唯一区分对象类型