基于读写特征的分布式互斥算法 被引量：16

1

作者 刘丹 刘心松 +1 位作者 丘志杰 邱元杰 《电子学报》 EI CAS CSCD 北大核心 2004年第2期326-329,共4页

在LK算法基础上 ,提出一种对读写请求作不同互斥处理的分布式互斥算法———RWME(read/writemu tualexclusion)算法 .在同步延迟仍为T的前提下 ,降低了传统非令牌类型互斥算法的消息复杂度 .在Lamport全局时戳的基础上 ,定义了适合于读... 在LK算法基础上 ,提出一种对读写请求作不同互斥处理的分布式互斥算法———RWME(read/writemu tualexclusion)算法 .在同步延迟仍为T的前提下 ,降低了传统非令牌类型互斥算法的消息复杂度 .在Lamport全局时戳的基础上 ,定义了适合于读写互斥的全局时戳———读写时戳 ,并由其来保证各读写进程互斥访问临界区的公平性和正确性 .通过对算法的性能分析验证其是高效的 。 展开更多

关键词 RWME算法 分布式互斥 读写时戳 消息复杂度

下载PDF 职称材料

非稳定环境下基于竞争消息复杂度的分布式互斥节点容错算法 被引量：9

2

作者 李美安 刘心松 王征 《微计算机信息》 北大核心 2005年第12X期145-146,141,共3页

目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错... 目前人们已经提出了很多分布式互斥算法。为简化问题,这些算法多数要求假设系统的节点与通信均可靠,因此不存在容错处理问题。部分在先假定节点与通信可靠的基础上讨论的算法,为达到其结论的逻辑严密性,补充了节点与通信不可靠时的容错处理,但这些容错处理方式都是作为其分布式互斥算法的补充提出来的,有较大程度的理想化成分,基本上没用进行充分的性能分析。本文根据分布式互斥算法节点容错处理方式的不同,将其分为两类并对其对消息复杂度的影响进行详细讨论。在此基础上,提出一种混合的分布式互斥节点容错处理方法,以降低非稳定环境下分布式互斥算法的平均消息复杂度。 展开更多

关键词 非稳定环境 分布式互斥 节点容错 算法

下载PDF 职称材料

一种新的分布式互斥请求集生成算法 被引量：8

3

作者 陈志党 李美安 +1 位作者 战俊伟 申二威 《微计算机信息》 2010年第9期211-212,72,共3页

分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了... 分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。 展开更多

关键词 初始化 循环编码 分布式互斥 请求集

下载PDF 职称材料

基于负载可迁移的分布式计费系统研究 被引量：1

4

作者 樊富有 程玉昆 孟林 《计算机应用与软件》 CSCD 北大核心 2005年第10期115-117,共3页

宽带视频点播计费系统以分布式并行操作系统和分布式并行数据库系统为基础,通过量化的计费进程激活指数,结合计费进程互斥进入临界区算法,实现了多进程分布式协同计费。系统具有负载均衡能力,能够自动选择负载最轻的服务器作为计费节点... 宽带视频点播计费系统以分布式并行操作系统和分布式并行数据库系统为基础,通过量化的计费进程激活指数,结合计费进程互斥进入临界区算法,实现了多进程分布式协同计费。系统具有负载均衡能力,能够自动选择负载最轻的服务器作为计费节点。引入迁移惰性指数,使进程迁移的可控性得到进一步提高。系统具有很强的稳健性、实时性和不间断性的优点。该计费系统的设计方法不仅适用于宽带视频点播计费系统,也可供其它相近或相关计费系统借鉴。 展开更多

关键词 分布式并行 分布式计费 宽带视频点播 分布式互斥 负载均衡 计费系统 系统研究 进程迁移 分布式 并行数据库系统

下载PDF 职称材料

基于Token追踪的分布式互斥算法 被引量：1

5

作者 鄢勇 《计算机学报》 EI CSCD 北大核心 1993年第9期648-654,共7页

本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0～2(n—1)(n为结点数)的有效互斥算... 本文首先提出一切合实际的互斥信件量度量方法,该方法不仅考虑请求结点所发的信息数,同时还考虑信件的存储转发次数,然后针对任一拓扑结构,在充分利用局部信息与已知信息的基础上,给出了互斥信件量为0～2(n—1)(n为结点数)的有效互斥算法,该算法不仅在互斥信件量上是目前最优的,而且充分体现了分布式算法设计的一个重要原则,充分利用一切已知信息作为未来决策的依据。 展开更多

关键词 共享资源 分布式互斥 算法 TOKEN

下载PDF 职称材料

改进的分布式互斥请求集生成算法 被引量：3

6

作者 武鹏 李美安 +1 位作者 裴喜春 周根宝 《计算机应用》 CSCD 北大核心 2010年第A01期243-244,250,共3页

在分布式系统中,各节点必须互斥地访问临界区。节点的请求集的长度决定了系统的效率、性能。虽然最优请求集的节点数最少(大约槡n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算。提出了一种快速的请... 在分布式系统中,各节点必须互斥地访问临界区。节点的请求集的长度决定了系统的效率、性能。虽然最优请求集的节点数最少(大约槡n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算。提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集。与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集。本算法时间复杂度为O(n2),生成的请求集长度为槡n～2槡n。 展开更多

关键词 分布式互斥 请求集 贪心算法

下载PDF 职称材料

具有O(n)时间复杂度的分布式请求集生成算法 被引量：2

7

作者 武鹏 李美安 《计算机应用》 CSCD 北大核心 2013年第2期323-325,360,共4页

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本"求差"的过程变为"求和"的过程;进而利用"求和"步骤... 在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本"求差"的过程变为"求和"的过程;进而利用"求和"步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n2)的其他经典算法相比,生成的请求集长度仍保持在2槡n的数量级。 展开更多

关键词 分布式互斥 请求集 松弛差集 时间复杂度

下载PDF 职称材料

基于直径仲裁集的网格网络分布式互斥算法

8

作者 王征 刘心松 李美安 《计算机工程与应用》 CSCD 北大核心 2007年第14期141-143,176,共4页

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真... 分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。 展开更多

关键词 分布式互斥 网格 仲裁集 网络直径

下载PDF 职称材料

基于半环仲裁集的环网分布式互斥算法

9

作者 王征 刘心松 《计算机科学》 CSCD 北大核心 2008年第7期88-90,95,共4页

分布式互斥是环网分布式系统的重要问题。根据此类系统的特点,提出了新型的分布式互斥算法。该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容... 分布式互斥是环网分布式系统的重要问题。根据此类系统的特点,提出了新型的分布式互斥算法。该算法以请求者自身为中心,基于半环生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。 展开更多

关键词 分布式互斥 环网 仲裁集

下载PDF 职称材料

一种改进的分布式互斥请求集生成算法

10

作者 潘传中 周英 《西南民族大学学报（自然科学版）》 CAS 2014年第5期724-728,共5页

分布式互斥请求集的性能,对基于竞争的分布式互斥算法的消息复杂度、对称性、同步时间及容错能力等均具有直接影响.而分布式互斥请求集生成算法性能,如时间复杂度、空间复杂度,则对算法的运行速度、计算能力具有直接影响.通过对基于循... 分布式互斥请求集的性能,对基于竞争的分布式互斥算法的消息复杂度、对称性、同步时间及容错能力等均具有直接影响.而分布式互斥请求集生成算法性能,如时间复杂度、空间复杂度,则对算法的运行速度、计算能力具有直接影响.通过对基于循环编码的分布式互斥请求集生成算法运行过程的研究,特别是对该算法的时间复杂度的研究,提出一种改进的基于循环编码的分布式互斥请求集生成算法.此算法在不明显增加算法空间复杂度和请求集长度的基础上,能够显著提高请求集生成算法的时间复杂度,从而使得算法的运行速度和计算能力都得到显著增加. 展开更多

关键词 分布式互斥 请求集 生成算法

下载PDF 职称材料

基于网格网络的十字仲裁集互斥算法

11

作者 王征 刘心松 《计算机科学》 CSCD 北大核心 2008年第5期205-208,共4页

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理... 分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的行列生成分布式互斥十字仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"探测"消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的客错性能。 展开更多

关键词 分布式互斥 网格 仲裁集

下载PDF 职称材料

分布式系统进程互斥算法的研究与改进

12

作者 易苗苗 《计算机技术与发展》 2014年第11期74-78,共5页

随着网络技术的不断发展,分布式系统得到了广泛的研究与应用。然而由于分布式系统中网络带宽有限,且临界资源的数目是固定的,因此研究设计网络负载轻、临界资源利用率高的分布式互斥算法具有重要的意义。文中首先介绍了几种传统的互斥算... 随着网络技术的不断发展,分布式系统得到了广泛的研究与应用。然而由于分布式系统中网络带宽有限,且临界资源的数目是固定的,因此研究设计网络负载轻、临界资源利用率高的分布式互斥算法具有重要的意义。文中首先介绍了几种传统的互斥算法,对各个算法的性能加以比较,结合上述分析提出了一种新的基于令牌的算法,并详细阐述算法的设计思想及其数据结构。该算法最主要的特点是在分布式互斥中引入了优先级和选举算法的概念,能有效提高进程间的通信效率。 展开更多

关键词 分布式互斥 令牌 优先级 选举

下载PDF 职称材料

基于读写特征的现场总线分布式互斥算法

13

作者 杨王黎 吴雅娟 +1 位作者 杨永 唐世伟（审稿） 《大庆石油学院学报》 CAS 北大核心 2006年第2期100-102,153,共3页

针对传统分布式互斥算法中存在的消息复杂度高、延迟时间长等缺点,在传统Mackawa算法的基础上,提出了基于读写特征的现场总线分布式互斥算法.该算法通过区分读写特征,降低了消息复杂度;通过采用并行时序,缩短了响应时间.与传统算法的性... 针对传统分布式互斥算法中存在的消息复杂度高、延迟时间长等缺点,在传统Mackawa算法的基础上,提出了基于读写特征的现场总线分布式互斥算法.该算法通过区分读写特征,降低了消息复杂度;通过采用并行时序,缩短了响应时间.与传统算法的性能对比结果表明:该算法有较低的消息复杂度和较好的实时性. 展开更多

关键词 现场总线 分布式互斥 临界区 读写特征

下载PDF 职称材料

基于树拓扑网络的分布式互斥算法

14

作者 王莉 《计算机仿真》 CSCD 北大核心 2009年第2期143-146,178,共5页

分布式互斥是分布式系统的重要问题。根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME。算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大... 分布式互斥是分布式系统的重要问题。根据树拓扑网络的特点,提出了新型的分布式互斥算法TNDME。算法的运行范围限制在根节点到请求节点之间,采用循径方法生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用"最大残存树"探测方法进行系统的容错处理。描述了算法的模型、主要思想、数据结构、消息结构以及伪代码,并证明了算法的正确性。理论性能分析与仿真对比证明,算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。 展开更多

关键词 分布式互斥 树网络 循径 仲裁集

下载PDF 职称材料

分布式互斥算法的研究与改进 被引量：2

15

作者 胡吉明 毕伟 《计算机与现代化》 2006年第6期14-17,21,共5页

在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法... 在几种基于令牌算法的基础上,提出了一个对网络逻辑结构无要求的分布式互斥算法。算法不但能够在逻辑结构无要求的计算机网络中通过发送消息和传递令牌来同步对临界资源的访问,而且可以很好地解决请求丢失、令牌丢失等问题。通过对算法的性能进行分析验证了该算法是高效的,并给出了正确性证明。 展开更多

关键词 分布式互斥算法 令牌 临界资源 临界区

下载PDF 职称材料

一种基于松弛循环差集的对称分布式互斥算法 被引量：4

16

作者 李美安 刘心松 王征 《四川大学学报（工程科学版）》 EI CAS CSCD 北大核心 2005年第4期115-118,共4页

为在全分布系统中实现对称的分布式互斥,需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性,将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集问题,并在此基础上提... 为在全分布系统中实现对称的分布式互斥,需要设计出对称的分布式互斥算法。通过证明循环请求集与松弛循环差集的等价性,将求取包含任意数量节点的分布式系统对称请求集的问题转化为求取任意数量节点集合的松弛差集问题,并在此基础上提出了一种基于循环松弛差集的对称分布式互斥请求集生成算法。在请求集生成算法的基础上,引入了转移应答消息和请求集重构消息,重新定义应答消息的结构以使其能够携带更多的信息,重新设计了分布式互斥算法的相关过程,从而改进了Makawa类分布式互斥算法的性能。该算法具有较高的时间效率和空间效率,其求取的请求集尺寸较小,使分布式互斥算法的消息复杂度降为O(2N),同步时间降为T,节点容错能力达到N-1。基于松弛循环差集的分布式互斥算法克服了以往分布式算法必须牺牲一种性能指标以提高另一种性能指标的缺点,具有很高的应用价值。 展开更多

关键词 松弛循环差集 对称分布式互斥算法 全分布系统 节点 请求集生成算法

下载PDF 职称材料

一种广域网中的分布式互斥算法 被引量：1

17

作者 夏晨曦 邱毓兰 彭德纯 《计算机工程》 CAS CSCD 北大核心 2000年第3期59-60,F003,共3页

广域网可简单地看作由多个局域网通过远程通信线路互连组成。为了适应广域网环境的特点，文章提出了一种两层结构的分布式互斥算法模型，把广域网系统组织成由局部进程组成的局部网络和由每个局部网络中的协调进程组成的全局环两层。为... 广域网可简单地看作由多个局域网通过远程通信线路互连组成。为了适应广域网环境的特点，文章提出了一种两层结构的分布式互斥算法模型，把广域网系统组织成由局部进程组成的局部网络和由每个局部网络中的协调进程组成的全局环两层。为了互斥地访问共享资源，局部进程必须首先获得局部令牌，然后再向本地协调进程申请全局令牌，只有获得了局部和全局令牌的局部进程才能进入临界区。还讨论了对该算法可能的扩展。 展开更多

关键词 广域网 分布式互斥算法 进程 网络通信

下载PDF 职称材料

自适应Ad hoc分布式互斥算法 被引量：1

18

作者 王征 刘心松 李美安 《小型微型计算机系统》 CSCD 北大核心 2007年第8期1387-1392,共6页

Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX.ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,... Ad hoc网络的动态拓扑结构和节点自组织给分布式算法的实现带来了诸多困难.针对Ad hoc分布式互斥算法研究滞后的现状,提出了一种自适应的Ad hoc分布式算法ADMUTEX.ADMUTEX算法基于令牌查询方法,它采用Lamport逻辑时戳保证消息的时序性,避免了节点饿死.同时,它在消息复杂度与同步延迟之间作了折衷,而且它不需要节点了解系统的全局信息,能够适应Ad hoc网络的动态拓扑结构和节点频繁出入的情况.分析与仿真结果表明该算法具有较低的消息复杂度、小响应延迟和公平性. 展开更多

关键词 AD HOC 分布式互斥算法 令牌查询 逻辑时戳 消息复杂度

下载PDF 职称材料

基于优先级组的分布式互斥算法的改进

19

作者 王云 钱松荣 芮鹤龄 《计算机应用》 CSCD 北大核心 2003年第3期9-12,共4页

主要介绍了一种分布式互斥算法的改进方案。首先简要介绍了基于权标的常规算法 ,然后提出了优先级组算法的另一种方案 ,并详细阐述算法的设计思想及其数据结构。本算法最主要的特点是在分布式互斥中引入了优先级和树的概念 。

关键词 优先级组 分布式互斥算法 权标算法 有向树 数据结构 路由器 INTERENT

下载PDF 职称材料

一个分布式K互斥算法的概率模型检测

20

作者 刘来 骆翔宇 《计算机应用研究》 CSCD 北大核心 2015年第4期1036-1039,共4页

传统的验证方法难以保证分布式K互斥算法的有效性和安全性。为解决这一问题,给出了进一步的研究,提出一种基于概率模型检测器PRISM的方法,对Kerry Raymond的分布式K互斥算法进行形式化建模与分析验证。通过设置算法中各个进程进入临界... 传统的验证方法难以保证分布式K互斥算法的有效性和安全性。为解决这一问题,给出了进一步的研究,提出一种基于概率模型检测器PRISM的方法,对Kerry Raymond的分布式K互斥算法进行形式化建模与分析验证。通过设置算法中各个进程进入临界区的时间而得出的结果中发现,改变临界区的数目K,对于某一进程进入临界区的平均及时时间的影响并不大。如果某一进程的执行时间比其他进程大很多,则K的增加可以提高运行效率。最后证明了这一结论。 展开更多

关键词 分布式K互斥算法 概率模型检测 PRISM 平均及时时间

下载PDF 职称材料