分布式:如何实现分布式互斥
发布日期:2022-03-16 03:25:38 浏览次数:18 分类:技术文章

本文共 3139 字,大约阅读时间需要 10 分钟。

什么是分布式互斥

对于同一共享资源,同一时刻只能由一个程序能够访问这种资源。在分布式系统中,这种排他性的资源访问方式,叫做分布式互斥,而这种被互斥访问的共享资源就叫做临界资源

如何实现分布式互斥

独裁者:集中式算法

我们可以引入一个协调者,每个程序在需要访问临界资源时,先给协调者发送一个请求。如果当前没有程序使用这个资源,协调者直接授权请求程序访问;否则,按照先来后到的顺序为请求程序“排一个号”。如果有程序使用完资源,则通知协调者,协调者从“排号”的队列中取出排在最前面的请求,并给它发送授权信息。拿到授权信息的程序,可以直接从访问临界资源。

这个互斥算法,就是我们所说的集中式算法,也可以叫做中央服务器算法。之所以这么称呼,是因为协调者代表着集中程序或中央服务器。其示意图如下:

在这里插入图片描述

  • 如图所示,程序 1、2、3、4 为普通运行程序,另一个程序为协调者。当程序 2 和程序 4需要使用临界资源时,它们会向协调者发起申请,请求协调者授权。
  • 不巧的是,程序 3 正在使用临界资源。这时,协调者根据程序 2 和 4 的申请时间顺序,依次将它们放入等待队列。在这个案例里,程序 4 的申请时间早于程序 2,因此排在程序 2的前面。
  • 程序 3 使用完临界资源后,通知协调者释放授权。此时,协调者从等待队列中取出程序4,并给它发放授权。这时,程序 4 就可以使用临界资源了。

从上述流程可以看出,一个程序完成一次临界资源访问,需要如下几个流程和消息交互:

  1. 向协调者发送请求授权信息,1 次消息交互;
  2. 协调者向程序发放授权信息,1 次消息交互;
  3. 程序使用完临界资源后,向协调者发送释放授权,1 次消息交互。

因此,每个程序完成一次临界资源访问,需要进行 3 次消息交互。

可以看出,集中式算法的优点在于直观、简单、信息交互少、易于实现,并且所有程序只需要和协调者通信,程序之间无需通信。但是,这个算法的问题也出在了协调者身上。

  • 一方面,协调者会成为系统的性能瓶颈。比如,如果有100个程序要访问临界资源,那么协调者就要处理100*3=300条消息。也就是说,协调者处理的消息数量会随着需要访问的临界资源的程序数量而线性增长。
  • 另一方面,容易引发单点故障问题。协调者故障,会导致所有的程序均无法访问临界资源,导致整个系统不可用。

因此,在使用集中式算法的时候,一定要选择性能好、可靠性高的服务器来运行协调者。

小结:集中式算法具有简单、易于实现的特点,但是可用性、性能容易被协调者影响。在可靠性和性能有一定保障的情况下,比如中央服务器计算能力强、性能高、故障率低,或者中央服务器进行了主备备份,主故障后备可以立马升为主,而且数据可恢复的情况下,集中式算法可以适用于比较广泛的应用场景。

民主协商:分布式算法

怎么解决引入协调者的问题呢?我们可以在一个程序要访问临界资源时,先向系统中的其他程序发送一条请求消息,在接收到所有程序返回的同意消息后,才可以访问临界资源。其中,请求消息需要包含所请求的资源、请求者的ID,以及发起请求的时间。

这就是民主协商法。在分布式领域中,我们称之为分布式算法,或者使用组播和逻辑时钟的算法

如图所示:

  • ·程序 1、2、3 需要访问共享资源 A。在时间戳为 8 的时刻,程序 1 想要使用资源 A,于是向程序 2 和 3 发起使用资源 A 的申请,希望得到它们的同意。在时间戳为 12的时刻,程序 3 想要使用资源 A,于是向程序 1 和 2 发起访问资源 A 的请求。

在这里插入图片描述

  • 此时程序 2 暂时不访问资源 A,因此同意了程序 1 和 3 的资源访问请求。对于程序 3 来说,由于程序 1 提出请求的时间更早,因此同意程序 1 先使用资源,并等待程序1 返回同意消息

在这里插入图片描述

  • 程序 1 接收到其他所有程序的同意消息之后,开始使用资源 A。当程序 1 使用完资源 A 后,释放使用权限,向请求队列中需要使用资源 A 的程序 3 发送同意使用资源的消息,并将程序 3 从请求队列中删除。此时,程序 3 收到了其他所有程序的同意消息,获得了使用资源 A 的权限,开始使用临界资源 A 的旅程

在这里插入图片描述

从上述流程可以看出,一个程序完成一次临界资源的访问,需要进行如下的信息交互:

  1. 向其他 n-1 个程序发送访问临界资源的请求,总共需要 n-1 次消息交互;
  2. 需要接收到其他 n-1 个程序回复的同意消息,方可访问资源,总共需要 n-1 次消息交互。

可以看出,一个程序要成功访问临界资源,至少需要2*(n-1)次消息交互。假设,现在系统中的n个程序都要访问临界资源,则会同时产生2n(n-1)条消息。在大型系统中使用分布式算法,消息数量会随着访问临界资源的程序数量呈指数级增加,容易导致高昂的“沟通成本”

从上可以看出,分布式算法根据“先到先得”以及“投票全票通过”的机制,让每个程序按照时间顺序公平的访问资源,简单粗暴,已于实现。但是,这个算法可用性很低,原因如下:

  • 当系统内需要访问临界资源的程序增多时,容易产生“信令风暴”,也就是程序收到的请求完全超过了自己的处理能力,而导致自己正常的业务无法开展
  • 一旦某一程序发生故障,无法发送同意消息,那么其他程序均处在等待回复的状态中,使得整个系统处于停滞状态,导致整个系统不可用。所以,相对于集中式算法的协调者故障,分布式算法的可用性更低。

针对可用性低的一种改进方法是,如果检查到一个程序故障,则直接忽略这个程序,无需再等待它的同意消息。但是这样的话,每个程序都需要对其他程序进行故障检查,这无疑带来了更大的复杂性。

因此,分布式算法适合节点数目少而且变动不频繁的系统,而且由于每个程序均需要通信交互,因此适合P2P结构的系统。比如运行在局域网中的分布式文件系统。

归纳一下:分布式算法是一个“先到先得”和“投票全票通过”的公平访问机制,但通信成本较高,可用性也比集中式算法低,适用于临界资源使用频度较低,且系统规模较小的场景。

轮值CEO:令牌环算法

如下图所示,所有程序构成一个环结构,令牌按照顺时针或者逆时针的方向在程序之间传递,收到令牌的程序有权访问临界资源,访问完成之后将令牌传送到下一个程序;如果该程序不需要访问临界资源,则直接把令牌传输给下一个程序。

在分布式领域,这个算法叫作令牌环算法,也可以叫作基于环的算法。

在这里插入图片描述

因为在使用临界资源之前,不需要像分布式算法那样挨个征求其他程序的意见了,所以相对而言,在令牌环算法中单个程序具有更高的通信效率。同时,在一个周期内,每个程序都能访问到临界资源,因此令牌环算法的公平性很好。

但是,不管环中的程序是否想要访问资源,都需要接收并传递令牌,所以也会带来一些无效通信。假设系统中有 100 个程序,那么程序 1 访问完资源后,即使其它 99 个程序不需要访问,也必须要等令牌在其他 99 个程序传递完后,才能重新访问资源,这就降低了系统的实时性。

综上,令牌环算法非常适合通信模式为令牌环方式的分布式系统,例如移动自组织网络系统。

令牌环算法是一种更加公平的算法,通常会和通信令牌结合,从而取得很好的效果。特别是当系统支持广播或者组播通信模式时,该算法更加高效、可行。

对于集中式和分布式算法都存在的单点故障问题,在令牌环中,如果某一个程序出现故障,那么直接将令牌传递给故障程序的下一个程序,从而很好的解决程序的单点故障问题,提高系统的健壮性。但这就要求每个程序都要记住环中的参与者信息,这样才能知道在跳过一个参与者令牌应该传递给谁。

小结:令牌环算法的公平性高,在改进单点故障之后,稳定性也很高,适用于系统规模较小,并且系统中每个程序使用临界资源的频率高而且使用时间比较短的场景。

小结

在这里插入图片描述

转载地址:https://blog.csdn.net/zhizhengguan/article/details/122813238 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:分布式:分布式选举算法
下一篇:算法:多维数组的行优先和列优先

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月24日 11时20分18秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

hibernate mysql 缓存_hibernate和mysql的缓存问题,没辙了! 2019-04-21
abp框架 mysql_ABP框架使用Mysql数据库 2019-04-21
mysql树形递归删除_使用递归删除树形结构的所有子节点(java和mysql实现) 2019-04-21
linux mysql 不能连接远程_linux mysql 远程连接 2019-04-21
mysql $lt_mongodb中比较级查询条件:($lt $lte $gt $gte)(大于、小于)、查找条件... 2019-04-21
install python_Install python on AIX 7 2019-04-21
jquery查找div下第一个input_jquery查找div元素第一个元素id 2019-04-21
如何修改手机屏幕显示的长宽比例_屏幕分辨率 尺寸 比例 长宽 如何计算 2019-04-21
mysql 的版本 命名规则_MySQL版本和命名规则 2019-04-21
no java stack_Java Stack contains()用法及代码示例 2019-04-21
java动态代码_Java Agent入门学习之动态修改代码 2019-04-21
python集合如何去除重复数据_Python 迭代删除重复项,集合删除重复项 2019-04-21
iview 自定义时间选择器组件_Vue.js中使用iView日期选择器并设置开始时间结束时间校验功能... 2019-04-21
java 验证码校验_JavaWeb验证码校验功能代码实例 2019-04-21
java多线程初学者指南_Java多线程初学者指南(4):线程的生命周期 2019-04-21
java进程user是jenkins_java 学习:在java中启动其他应用,由jenkins想到的 2019-04-21
java添加资源文件_如何在eclipse中将资源文件夹添加到我的Java项目中 2019-04-21
java的三种修饰符_3分钟弄明白JAVA三大修饰符 2019-04-21
mysql source skip_redis mysql 中的跳表(skip list) 查找树(btree) 2019-04-21
java sun.org.mozilla_maven编译找不到符号 sun.org.mozilla.javascript.internal 2019-04-21