（计算机系统结构专业论文）普适分布式互斥算法及应用.pdf

摘要 摘要 在分布式系统中，很多进程能够在微观上并行执行。但由于共享资源的有限 性，以及全局数据要求的一致性，一些临界资源的访问需要以互斥的方式实现同 步。实现分布式互斥的算法一般分为基于令牌的分布式互斥算法和基于竞争的分 布式互斥算法。基于令牌的分布式互斥算法具有较小的消息复杂度，但其同步时 间较长，基于竞争的分布式互斥算法具有较大的消息复杂度，但其同步时间较短。 同时，基于竞争的分布式互斥算法由于具有良好的对称性在全分布系统中得到了 广泛的应用。本文着重研究了基于竞争的分布式互斥算法。特别是基于请求集的 适用于任意规模分布式系统的普适分布式互斥算法。 基于竞争的分布式互斥算法主要分为两类：全局互斥和局部互斥。全局互斥 以l a m p o r t 和r a 算法为代表；局部互斥以m a k a w a 算法为代表。虽然全局互斥 具有十分优良的对称性和极高的避免死锁的能力，但其极大的消息复杂度( d ( ) ) 使得系统的规模受到了较大的限制。局部互斥虽然对称性不如全局互斥，同步延 迟也较大( 一般为2 t ) ，但m a k a w a 算法提出了请求集( q u o r u m ) 的概念，使得局部 互斥的消息复杂度降为o ( ) 。因此，局部互斥在系统规模的限制方面的性能比 全局互斥要好得多。局部互斥在打破全局互斥对系统规模的限制的同时，由于请 求集的生成需要时间和存储空间，以及同步延迟的增加，因此使得互斥算法的实 际性能受到很大影响。 局部互斥算法的运行过程分为两部分。一部分是请求集生成算法；另一部分 是基于请求集的互斥算法。请求集生成算法决定了整个互斥算法的消息复杂度和 对称性，并对算法运行的实际时间消耗具有重要影响。互斥算法对请求集的组织 及通信容错处理形式决定了分布式互斥算法的对称性，同步延迟，死锁避免能力， 节点与通信的失效容错能力，并对消息复杂度具有重要影响。因此，寻求对任意 规模系统都能生成对称请求集的请求集生成算法( 普适请求集生成算法) ，降低请 求集算法的时间复杂度和空间复杂度以降低由于生成请求集所耗费的时间与空间 给互斥算法性能带来的额外影响的问题是本文研究的一个重要内容。在此基础上 提出消息复杂度低，同步延迟短，失效容错能力强的没有死锁的适用于任意规模 分布式系统的普适对称分布式互斥算法也是本文研究的主要内容之一。 首先本文对适用于任意规模分布式系统的普适分布式互斥请求集生成算法进 行了研究。其目的在于寻找请求集长度、时间复杂度与空间复杂度都较低的对称 摘要 请求集生成算法。为降低算法的复杂性，同时根据循环请求集的优良特性，本文 提出的对称请求集生成算法都是循环请求集生成算法。本文提出了基于循环编码 的对称循环请求集生成算法，基于循环松弛差集的对称请求集生成算法以及基于 循环请求集性质的对称请求集生成算法。 其次本文对普适分布式互斥算法进行了研究。以往的互斥算法多数是对 m a k a w a 算法的某一方面性能进行改进。它们多数需要牺牲互斥算法的一方面性能 以提高其另一方面性能。如对容错能力，死锁检测能力或者同步时间的改进一般 会以提高分布式互斥算法的消息复杂度为代价。本文将基于竞争的互斥算法的低 同步延迟与基于令牌的互斥算法的低消息复杂度结合起来提出了新的互斥算法， 这种算法能同时具有令牌算法和竞争算法的优点，克服上述二种算法的缺点。另 一方面本文基于网络系统的自组织特性，将分布式网络划分成一定数量的子网， 在予网内采用令牌算法，在由子网组成的上层采用竞争算法以确定各节点的请求 时序与权限转移，提出了分层结构的分布式互斥算法，对降低分布式互斥算法的 消息复杂度具有很大作用。 本文还对非稳定环境下互斥算法的平均消息复杂度进行研究并提出了相应的 复合算法。实际上，以前的所有分布式互斥算法，都是以假设系统的节点与通信 都可靠作为算法运行的前提的。但实际系统中，节点与通信并不总是可靠的。因 此，在实际应用中，对节点与通信容错的处理对分布式互斥的平均消息复杂度影 响很大。通过对互斥算法的容错处理方式进行研究，并对不同容错处理方式下， 互斥算法的平均消息复杂度进行分析，提出了在实际应用中采取有效的容错处理 方式以提高互斥算法的性能的复合容错算法。 本文还对分布式互斥算法的应用范围进行了扩展，对其在现场总线控制和数据 交换机的性能改进领域的应用进行了研究。提高了算法的理论层次和应用范围。 关键词普适分布式互斥算法应用 a b s tr a c t i nd i s t r i b u t e ds y s t e m ，m a n yp r o c e e d i n g sc a nb e e x e c u t e d s y n c h r o n o u s l y o n m i c r o c o s m i cs c a l e b e c a u s ei ti sl i m i t e do ft h es h a r i n gr e s o u r c ea n dt h ec o n s i s t e n c y r e q u e s t so ft h et o t a ld a t a ，s o m ec r i t i c a lr e s o u r c en e e dt oi m p l e m e n tt h es y n c h r o n i z a t i o n a c c e s st h r o u g hm u t u a le x c l u s i o n t h ea l g o r i t h m sw h i c hi m p l e m e n tt h es y n c h r o n i z a t i o n a c c e s st h r o u g hm u t u a le x c l u s i o ni nd i s t r i b u t e ds y s t e ma r en a m e da sd i s t r i b u t e dm u t u a l e x c l u s i o na l g o r i t h m s g e n e r a l l yt h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m sc a nb e i m p l e m e n t e db a s e do nt o k e no rc o m p e t i t i o n t h o s ea l g o r i t h m sb a s e do nt o k e n h a v el e s s m e s s a g ec o m p t e x i t ya n dm o r es y n c h r o n i z a t i o nt i m e t h o s ea l g o r i t h m sb a s e d o n c o m p e t i t i o nh a v e l e s ss y n c h r o n i z a t i o nt i m ea n dn i c es y m m e t r y s ot h ed i s t r i b u t e d m u t u a le x c l u s i o na l g o r i t h m sb a s e do nc o m p e t i t i o nc a nb eu s e dw i d e l yi nt h ed i s t r i b u t e d s y s t e m t h i sp a p e rw i l le m p h a s i z et o r e s e a r c ht h o s eu n i v e r s a lm u t u a le x c l u s i o n a l g o r i t h m sb a s e do nc o m p e t i t i o na n d t h o s eu n i v e r s a lm u t u a le x c l u s i o na l g o r i t h m sb a s e d q u o r u me x p r e s s l yf o ra n ys c a l ed i s t r i b u t e ds y s t e m t h eu n i v e r s a ld i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m sb a s e do nc o m p e t i t i o nc a l lb e d i v i d e di n t ot w ot y p e s ：t o t a l l ym u t u a le x c l u s i o na l g o r i t h mo rl o c a l l ym u t u a le x c l u s i o n a l g o r i t h m t h et y p i c a la l g o r i t h m so ft o t a l l ym u t u a le x c l u s i o na l g o r i t h m sa r el a m p o r t a n dr & aa l g o r i t h m s t h et y p i c a la l g o r i t h mo fl o c a l l ym u t u a le x c l u s i o na l g o r i t h mi s m a e k a w aa l g o r i t h m t h o s et o t a l l ym u t u a le x c l u s i o na l g o r i t h m sh a v e v e r y n i c e s y m m e t r ya n de x c e l l e n ta b i l i t yt od e a d l o c kf r e eb u tm o r em e s s a g ec o m p l e x i t y ( d ( ) ) l i m i t st h es y s t e ms c a l e t h el o c a lm u t u a le x c l u s i o na l g o r i t h mi sl e s sm e s s a g e c o m p l e x i t ya n ds y m m e t r ya n dm o r es y n c h r o n i z et i m e ( 2 3 3t h a nt o t a l l ym u t u a l e x c l u s i o na l g o r i t h m t h eq u o r u mb r o u g h tf o r w a r db ym a e k a w aa l g o r i t h mr e d u c e dt h e m e s s a g ec o m p l e x i t y o f l o c a l l y m u t u a le x c l u s i o na l g o r i t h m t o o ( 4 n ) s o t h e l i m i t i o n o f t h es y s t e ms c a l eo fl o c a l l ym u t u a le x c l u s i o nm u t u a la l g o r i t h mi sl e s st h a nt o t a l l ym u t u a l e x c l u s i o na l g o r i t h m a tt h es a m et i m e ，t h em n n i n go ft h eq u o r u mg e n e r a t i o na l g o r i t h m n e e d st i m ea n ds t o r a g ec o s t s ot h ep e r f o r m a n c eo ft h eq u o r u mg e n e r a t i o na l g o r i t h m w i l la f f e c tt h ep e r f o r m a n c eo ft h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h mo b v i o u s l y l o c a l l ym u t u a le x c l u s i o na l g o r i t h mc a nb ed i v i d e di n t ot w op a r t s o n ei sq u o r u m g e n e r a t i o na l g o r i t h m a n dt h eo t h e ri sm u t u a le x c l u s i o na l g o r i t h m t h eq u o r u m g e n e r a t i o na l g o r i t h md e c i d e st h em e s s a g ec o m p l e xa n ds y m m e t r ya n d t h et i m ec o s to f t h em u t u a le x c l u s i o na l g o r i t h m t h eo r g a n i z a t i o nm o d eo fq u o r u ma n dt h ed i s p o s i n g m o d eo ff a u l tt o l e r a t i o ni nt h em u t u a le x c l u s i o na l g o r i t h mw i l la f f e c tt h es y m m e t r y , s y n c h r o n i z a t i o nt i m e ，d e a d - l o c kf r e ea b i l i t y , f a u l tt o l e r a t i o nt os i t ea n dc o m m u n i c a t i o n o ft h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m s e a r c h i n gs o m eu n i v e r s a lq u o r u m g e n e r a t i o na l g o r i t h m sw h i c hc a l lg e n e r a t es y m m e t r i cq u o r u m st oa n ys c a l es y s t e ma n d r e d u c et h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t yo ft h eq u o r u mg e n e r a t i o na l g o r i t h m s i sav e r yi m p o r t a n ts u b j e c ti nt h i sp a p e r p r o p o s i n gs o m el e s sm e s s a g ec o m p l e x i t y , l e s s s y n c h r o n i z a t i o nt i m ea n dm o r ef a u l tt o l e r a t i o na n dd e a d l o c kf r e eb a s e do nt h eu n i v e r s a l q u o r u mg e n e r a t i o na l g o r i t h mi sav e r yi m p o r t a n ts u b j e c to ft h i sp a p e r t o o a tf i r s tw ew i l lr e s e a r c ht h eu n i v e r s a la n ds y m m e t r i cq u o r u mg e n e r a t i o na l g o r i t h m s f o ra n ys c a l ed i s t r i b u t e ds y s t e mi nt h i sp a p e r t h ea i mi st os e a r c hs o m eu n i v e r s a la n d s y m m e t r i cq u o m mg e n e r a t i o na l g o r i t h m sw h i c hh a v e s h o r t q u o r u m ，l e s st i m e c o m p l e x i t y a n ds p a c ec o m p l e x i t y f o rd e d u c i n gt h ec o m p l e x i t yo ft h eq u o r u m g e n e r a t i o na l g o r i t h m s ，a n db a s e do nt h ee x c e l l e n tp r o p e r t i e so ft h ec y c l i cq u o r u m ，a l l q u o r u mg e n e r a t i o na l g o r i t h m sp r o p o s e di nt h i sp a p e ra r ec y c l i cq u o r u ma l g o r i t h m s t h e q u o r u ma l g o r i t h mb a s e do nc y c l i cc o d i n g ，t h eq u o r u ma l g o r i t h mb a s e do nr e l a x e d c y c l i cd i f f e r e n c es e ta n d t h eq u o r u ma l g o r i t h mb a s e do nt h ep r o p e r t i e so fc y c l i cq u o r u m w i l lb ep r o p o s e di nt h i sp a p e r a ts e c o n dw ew i l lr e s e a r c ht h eu n i v e r s a ld i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m s f o ra n ys c a l ed i s t r i b u t e ds y s t e mi nt h i sp a p e r t h em u t u a le x c l u s i o na l g o r i t h m sf o r m e r a l m o s ti m p r o v e dm a e k a w aa l g o r i t h m sa ts o m ea s p e c t s t h e yi m p r o v e do n ea s p e c t p e r f o r m a n c ea tc o s to fd e d u c i n ga n o t h e ra s p e c tp e r f o r m a n c e f o re x a m p l e ，i m p r o v i n g t h ef a u l tt o l e r a n ta b i l i t y , d e a dl o c kd e t e c t i o na b i l i t yo rr e d u c et h es y n c h r o n i z a t i o nt i m e w i l lm a k et h em e s s a g ec o m p l e x i t yi n c r e a s i n gu s u a l l y t h r o u g hi n t r o d u c i n gt h ed y n a m i c t o k e nc o n c e p ta n dc h a n g i n gt h ef u n c t i o n so rt r a n s f e rd i r e c t i o n so fs o m em e s s a g e sw e p r o p o s e dam u t u a le x c l u s i o na l g o r i t h mw h i c hh a st h ev i r t u e so fc o m p e t i t i o na n dt o k e n a l g o r i t h m s i nt h eo t h e rh a n dw ep r o p o s e dah i e r a r c h i c a ld i s t r i b u t e dm u t u a le x c l u s i o n a l g o r i t h mb a s e do ut h ep r o p e r t yo fo r g a n i z e d s e l fo fan e t w o r ks y s t e m i tw i l ld e d u c e t h em e s s a g ec o m p l e x i t yo ft h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m se v i d e n t l y w er e s e a r c ht h ea v e r a g em e s s a g ec o m p l e x i t yo ft h em u t u a le x c l u s i o na l g o r i t h mi n u n r e l i a b l ee n v i r o n m e n ta n dp r o p o s ea no p t i m a ls i t ef a u l t t o l e r a n c em u t u a le x c l u s i o n a l g o r i t h m i nf a c t ，a l lt h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m sa r ep r o p o s e db a s e do n t h ec o n d i t i o nt h a tt h es i t e sa n dc o m m u n i c a t i o n so ft h es y s t e ma r er e l i a b l e i na na c t u a l 1 7 s y s t e m ，t h es i t e sa n dc o m m u n i c a t i o n s a r en o ta l w a y sr e l i a b l e s ot h em o d eo f p r o c e s s i n gt h es i t e sa n dc o m m u n i c a t i o n sf a u l t t o l e r a n c ew i l la f f e c tt h ea v e r a g em e s s a g e c o m p l e x i t y o ft h ed i s t r i b u t e dm u t u a le x c l u s i o n a l g o r i t h me v i d e n t l y t h r o u g h r e s e a r c h i n gt h ef a u l t - t o l e r a n c em o d e sa n dc o m p a r i n gt h ea v e r a g ec o m p l e x i t yo ft h e d i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m si nd i f f e r e n tm o d e s ，w ep r o p o s e da no p t i m a l f a u l t - t o l e r a n c ea l g o r i t h mt o i m p r o v et h ep e r f o r m a n c eo f t h ed i s t r i b u t e dm u t u a l e x c l u s i o na l g o r i t h mi nt h i sp a p e r w ee x t e n dt h ea p p l i c a t i o ns c o p eo ft h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m s ，w e u s et h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h mi nf i e l d b u sa n dt oi m p r o v et h e p e r f o r m a n c eo ft h ed a t ae x c h a n g es ot h a t t oi m p r o v et h et h e o r yl e v e la n dt h e a p p l i c a t i o ns c o p eo ft h ed i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m k e y w o r d s ：u n i v e r s a l ，d i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m s ，a p p l i c a t i o n s v 皇- 王型垫盔堂垫主兰笪堡奎 勘误表 1 增加参考文献3 7 6 2 ； 2 题目从“分布式互斥算法及应用”改为“普适分布式互斥算法及应用； 3 英文题目从“d i s t r i b u t e dm u t u a le x c l u s i o na l g o r i t h m sa n d i t sa p p l i c a t i o n s ”改为“u n i v e r s a l d i s t r i b u t e dm u t u a le x c l u s i o n a l g o r i t h m sa n dt h e i r a p p l i c a t i o n s ”； 4 a b s t r a c t ：r e q u e s t 改为r e q u e s t s ，b a s e 改为b a s e d ，n i c e r 改为n i c e ，d i v i d e d 改为 d i v i d e di n t oo 5 第5 页：1 2 1 与1 2 2 节，增加了背景分析和研究意义的内容； 6 增加加2 4 节； 7 第3 0 页，“表1 ”改为表3 3 3 1 ； 8 第5 4 页，重画图4 1 1 。 9 重新核查了第2 2 页的循环操作定义式3 1 到第3 4 ； 1 0 重新核查了定义3 3 1 1 ，3 3 4 1 ，3 3 4 ，2 ； 1 1 重新核查了定理3 3 1 1 ，3 3 1 2 ，3 3 4 1 ，3 3 5 1 ，3 3 5 2 ； 1 2 重新核查了推论3 3 4 1 ； 1 3 对“计算复杂度”进行了详细说明，并在第二章进行了定义； 1 0 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：赵望日期：唯弓月初日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 导师签名：建f ! ! ! 日期：7 年弓月w 日 第一章引言 第一章引言 1 1 分布式互斥的发展史与研究现状 1 1 1 分布式互斥的发展历史 分布式互斥是随着分布式系统的出现而出现的，并随着分布式系统理论发展而 发展。因此，和分布式系统的体系结构发展史类似，分布式互斥的发展经历了如 下几个发展阶段。 ( 1 ) 完全中心式算法。在该类算法中，一个节点被指定为控制( 裁决) 节点， 它控制对所有共享对象的访问。当任何进程请求对一个临界资源进行访问时，就 向本地资源控制进程发送一个请求消息，该进程接着向控制节点发送一个请求消 息。当共享对象可用时，将返回一个应答消息。当进程结束使用资源后，向控制 节点发送一个释放消息。这类算法有两个共同点，其一是只有控制节点能控制资 源的分配，其二是所有需要的信息都集中在控制节点中，包括所有资源的实体和 位置以及每个资源的分配状态。 完全中心式算法实现简单，控制也很方便，但存在以下缺点：如果控制节点崩 溃，则互斥机制终止，同时由于所有请求资源的进程都需与控制节点交换消息， 因此，控制节点可能存在通信瓶颈。 ， ( 2 ) 局部中心式算法。由于完全中心式算法可能出现的控制节点容错问题与 通信瓶颈问题，人们采取了相应措旌以期解决或缓解这些问题给整个系统带来的 影响。因此出现了局部中心式算法。局部中心式算法是将各临界资源按一定规则 分为几个区域，每个区域包含一定数量的临界资源和一个中心控制点。任何需要 请求某临界资源的进程都需向该l 晦界资源所在区域的中心控制节点发送请求消息 并由该控制节点安排进程访问临界资源的次序。该类算法具有多个控制点，各控 制点间互不干涉，每一个控制节点故障只影响系统内节点对该控制节点管理区域 内的临界资源访问，不会对非该区域内资源的访问造成影响。因此可以缓解完全 中心式算法的控制节点容错问题与通信瓶颈问题。 ( 3 ) 局部分布式算法。局部中心式算法虽然缓解了其完全中心式算法的控制 节点容错及通信瓶颈问题，但并未使这些问题得到解决。特别是随着通信技术的 电子科技大学博士学位论文 发展，节点间的通信带宽已经能够较大程度满足互斥的消息通信要求，因此使中 心式算法的控制节点容错变得更加重要。因此，人们将局部中心式算法中互不干 涉的控制节点改为互相备份的方式。当一个控制节点失效时，其控制的资源将转 向其备份的控制节点，使得互斥能够继续进行。该类算法继续发展，出现了多点 共同决策的资源访问模式，即任何一次的关键资源访问，不再是由唯一的一个控 制节点决定，而是由所有控制节点共同决定。因此申请访问临界资源的节点不再 只是向唯一的资源控制节点发送请求消息，而是需要向所有控制节点发送请求消 息。当所有控制节点都同意申请节点的请求时，申请节点获得临界资源访问机会。 因为多点控制使得节点间需要交换的消息数量增加，同样可能出现通信瓶颈，因 此该类算法是在通信技术发展到一定阶段的产物。该类算法在解决控制节点容错 方面具有较好的性质。 ( 4 ) 完全分布式算法。局部分布式互斥算法虽然使得分布式互斥的控制节点 容错问题得到了一定解决，但其容错能力不高，并增加了互斥所需的消息量。因 此，l a m p o r t 提出了完全分布式互斥的概念，并对分布式系统的消息排序进行了 深入研究。m a e k a w a ”3 对完全分布式算法的对称性特性作出了如下刻画。 1 ) 所有节点具有相同的信息量； 2 ) 所有节点只能掌握完整系统的部分情况，且必须基于这一信息作出决 定； 3 ) 所有节点对最终决定承担相同责任； 4 ) 所有节点在对最终决定的影响上付出相同的努力； 5 ) 一个节点的故障从整体上不会导致整个系统的崩溃： 6 ) 不存在系统范围的共同时钟来规范时间的定位与排序。 其中第2 ) 点是属于可选项，因为有些分布式互斥算法要求任何节点都要将自 己所知道的所有信息通告系统内其他节点，这样，如果忽略通信延迟，则任何节 点都将知道系统的全局信息。当然，由于通信延迟的影响，节点不可能知道全局 最新信息，因此，也可以说任何节点只能掌握系统的局部信息。 完全分布式互斥算法在节点的容错能力上比前面三种算法提高了很多，但同样 提高了决策所需交换的信息量。当然，随着通信技术的发展，节点间的通信带宽 将大大增加，虽然节点的通信瓶颈仍可能在一定条件下存在，但其几率已有很大 程度下降。因此，研究如何降低消息复杂度，如何降低同步延迟以及提高节点与 通信容错能力，成为完全分布式互斥研究的三个重要方向。完全分布式互斥的算 法发展又可以分成如下三个阶段。 第一章引言 1 )起步阶段。该阶段以l a m p o r t 算法为基础，以r i c a r t a g r a w a l a ”。 算法与m a e k a w a 乜1 算法为标志，将分布式互斥算法从集中控制或非完全 分布式互斥阶段推进到完全分布式互斥阶段。 2 )特殊发展阶段。在以上三类算法的基础上，在二十世纪八十年代后期到 九十年代初，随着分布式系统的发展，出现了几种完全分布式互斥算法。 它们改进了m a e k a w a 乜1 算法的各项性能指标，对分布式互斥算法的发展 起到一定推动作用。这一时期的分布式互斥算法与m a e k a w a 。1 算法类似， 都以研究特定系统规模条件下请求集的生成算法为主。 3 )全分布式互斥阶段。从二十世纪九十年代后期开始，分布式互斥算法不 再仅仅是实验室中学术讨论的课题和纸上谈兵的目的，而是存在了实际 需要。如何在上述全分布式互斥特性条件下，设计完全保证这些特性的 分布式互斥算法，成为这一时期的主要课题。 四类算法都是在一定历史条件下出现的，并没有哪类算法在性能上占绝对优 势，都在一定条件下具有相对优势。因此，在合适的条件下选择合适的算法，是 分布式互斥应用的一个重要研究课题。 1 1 2 研究现状 从各类文献数据库上检索的情况看，分布式互斥的研究在国外比国内更加充分 和系统。到目前为止，在c n k i 数据库中检索到的分布式互斥的研究论文仅四篇， 在i e e e 数据库中检索到的分布式互斥的研究论文达到7 3 篇，其中研究分布式互 斥算法的论文达到3 3 篇。在a c m 数据库中检索到的分布式互斥的研究论文达到1 8 6 篇，其中研究分布式互斥算法的论文达到6 6 篇。在e i 数据库中检索到的分布式 互斥的研究论文达到6 3 4 篇，其中研究分布式互斥算法的论文达到3 8 1 篇。分析 所有这些文献，发现目前国际上的分布式互斥研究正处于全分布式互斥发展的第 三阶段，同时也取得了较大的成果。 1 1 2 1 成果 ( 1 ) 理论较充实 l a m p o r tn 3 给出了全分布式系统中事件的逻辑时钟排序算法，并给出了相应的 全分布式互斥算法，为以后的分布式互斥研究及分布式互斥算法设计提供了理论 基础。m a e k a w a 乜1 将有限射影平面理论引入请求集的设计，并得出了分布式互斥算 电子科技大学博士学位论文 法的消息复杂度最小为o ( 万) 的结论，为设计分布式互斥算法的性能评估提供了度 量标准。 ( 2 ) 算法较丰富 在l a m p o r t “3 与m a e k a w a 乜3 算法的基础上，人们提出了数十种分布式互斥算法， 它们集中解决了竞争分布式互斥算法的请求集生成、减少分布式互斥算法的消息 复杂度、同步延迟、提高分布式互斥算法的容错能力等问题，给分布式互斥算法 的应用提供了丰富的选择。 ( 3 ) 应用广泛 分布式互斥算法由于是对临界资源的控制，因此，凡是分布式系统中存在对临 界资源的控制问题，都可以用分布式互斥算法解决。因此，分布式互斥算法不仅 在分布式计算机系统中得到广泛应用，在分布式控制，分布式决策等等方面都有 非常广阔的应用前景。 ( 4 ) 紧跟时代 分布式互斥算法与分布式系统的结构理论发展是分不开的。当市场上或学术界 以研究主从式分布式系统为主时，人们就会着重研究主从式的分布式互斥算法。 当市场上或学术界以研究对等网络为主时，对等的全分布时分布式互斥算法会成 为人们研究的重点。 1 1 2 2 问题 ( 1 ) 理论研究不充分 由于目前对分布式互斥算法的研究正处于研究全分布式互斥算法的阶段，因此 如何构造非特定条件下或任意系统规模条件下的全分布、全对称的分布式互斥算 法成为目前人们研究的重点。但是，任意系统规模条件下全对称、全分布的分布 式互斥算法的请求集长度与系统规模的关系问题一直困扰着各位研究人员。由于 这种关系不明朗，因此目前设计的全分布对称分布式互斥算法，只能以应用为主， 以改善分布式互斥算法的某一方面性能为目标。所以现阶段人们只能做到设计出 性能更优的全分布对称分布式互斥算法，却不能设计出任意系统规模条件下性能 最优的普适对称分布式互斥算法。 ( 2 ) 全分布对称分布式互斥算法数量太少 目前真正全分布对称的分布式互斥算法只有四个，l a m p o r t 算法，r i c a r t a g r a w a l a 朝算法，w a i s h i n g 算法，n g 5 1 算法。其中l a m p o r t 1 1 算法，r i c a r t 第一章引言 a g r a w a l ad 1 是全局互斥算法，完成互斥需要发送全局请求，虽然其对称及控制 性能优异，但其消息复杂度达到o ( n ) 的水平，消息复杂度高，对通信带宽要求巨 大，同时对分布式系统的规模限制较大。w a i - s h i n g “1 算法，n g 口1 算法都是基于 竞争的分布式互斥算法，它们都提出了一种具有全对称、全分布的分布式互斥请 求集的生成算法，对分布式互斥算法的性能具有了较大的改善。但他们还存在很 多不足，还有很大的提高空间。 1 2 分布式互斥研究背景及意义 1 2 1 研究背景 ( 1 ) 分布式系统规模的发展 随着计算机网络技术的发展，全球联系日益紧密，资源共享成为知识经济时代 的基本要求。各种大规模的服务器系统，包括分布式数据服务系统，g i s 系统，以 及全球空间数据库系统，都获得了很大发展。其规模也从几个节点发展到几千个 甚至上万个。老的全分布式互斥算法，如l a m p o r t 算法，r i c a r t a g r a w a l a 。3 算法已越来越不能适应分布式系统规模的快速增长。同时，分布式并行计算机系 统规模越来越大，计算节点数量也快速增长。利用l a m p o r tn 1 算法，r i c a r t a g r a w a l an 1 算法作为其系统使用的互斥算法将大量占用分布式计算机系统的计算 资源及内部通信资源，降低分布式计算机系统的使用效率。 ( 2 ) 分布式服务系统结构的发展 分布式服务系统从最初c s 结构，发展到现在的p 2 p 结构，迫使分布式软件 系统与这些硬件结构相适应，从而出现了全分布对称分布式互斥。全分布式互斥 作为与流行的p 2 p 结构相适应的互斥方式，能够与p 2 p 结构的服务系统很好配合， 出色完成系统的互斥任务。因此，研究和设计任意系统规模条件下对称的普适分 布式互斥算法成为解决p 2 p 系统的互斥问题的关键。 ( 3 ) 各种实用系统的发展 随着分布式计算、分布式服务的优点被人们大量发掘、分布式的概念已逐渐深 入人心。各种类型的分布式系统大量发展起来。由于各种实用分布式系统的运行 平台、组织结构、采用协议不完全相同，为提高系统的运行效率，要求根据系统 的实际条件，采用不同的分布式互斥算法。如实时分布式控制系统，要求时间效 率最高，因此需采用同步延迟低的分布式互斥算法。 电子科技大学博士学位论文 ( 4 ) 数字有机体概念的提出 电子科技大学8 0 1 0 研究室提出了数字有机体的概念，对分布式系统的规模做 了较大扩展，使分布式系统的构建从局域网发展到广域网，使分布式系统的规模、 通信条件都发生了很大改变。解决数字有机体系统的分布式互斥问题，需要各种 优秀的分布式互斥算法。 1 2 2 研究意义 ( 1 ) 推动分布式互斥技术的发展 由于目前所有的分布式互斥算法，都是基于一个基本假设：即分布式系统的节 点与同行都可靠。但由于实际分布式系统规模具有不确定性，而构成分布式系统 的通信网络也并不总是可靠的，因此，任何一个确定的分布式系统，其节点规模 不会一成不变。系统规模的不确定性与通信系统的不可靠性，决定了研发具有普 适性能的分布式互斥算法的必要性。虽然经过四十多年的发展，分布式互斥技术 已经取得了长足进步，但世界上目前仅有四种能够适应任何规模分布式系统的全 分布对称分布式互斥算法。提出更高效率、更优性能的分布式互斥算法，