分布式计算应用实例（《分布式技术原理与算法解析》学习笔记Day03）
分布式互斥方法
什么是分布式互斥？
对于同一个共享资源 ，当一个程序正在使用的时候 ，不希望被其他程序打扰 ，这种排他性的资源访问方式 ，叫做分布式互斥 ，被互斥访问的共享资源被称作临界资源(Critical Resource).
有什么方法可以让分布式系统里的程序互斥地访问临界资源？
我们一般有三种方法：
集中式算法（霸道总裁） 分布式算法（民主协商） 令牌环算法（轮值CEO）集中式互斥算法
我们引入一个协调者程序 ，每个程序在访问临界资源时 ，先向协调者发送一个请求 ，如果当前没有其他程序使用这个资源 ，协调者直接发送授权信息给请求程序去访问；否则 ，协调者会按照先来后到的顺序为请求程序“排个号 ” 。如果有程序使用完资源 ，则通知协调者 ，协调者从“排号 ”的队列里取出排在最前面的请求 ，并给它发送授权消息 。拿到授权消息的程序 ，可以直接去访问临界资源 。
集中式算法也被称为中央服务器算法 。
使用该算法 ，一个程序访问一次临界资源 ，需要完成3次消息交互：
向协调者发送请求授权信息 协调者向程序发放授权信息 程序使用完临界资源后 ，向协调者发送释放授权信息集中式算法的优点在于直观 、简单 、信息交互量少 、易于实现 ，并且所有程序都只和协调者通信 ，程序彼此之间无需通信 。
集中式算法的缺点在于协调者：
协调者会成为系统的性能瓶颈 。 协调者容易引发单点故障 ，协调者不可用时 ，会导致整个系统不可用 。分布式互斥算法
当一个程序要访问临界资源时 ，先向系统中的其他程序发送一条请求信息 ，在接收到所有程序返回的同意消息后 ，才可以访问临界资源 。其中请求消息包括所请求的资源 、请求者ID以及发起请求的时间 。
它是一种使用组播和逻辑时钟的算法 。
使用该算法 ，一个程序访问一次临界资源 ，需要进行2*(n-1)次消息交互：
向其他n-1个程序发送访问临界资源的请求 ，总共需要n-1次消息交互 需要接收到其他n-1个程序回复的同意消息 ，才能访问资源 ，总共需要n-1次消息交互它的缺点主要包括：
当系统内需要访问临界资源的程序增多时 ，或者需要访问的临界资源数量增多时 ，容易产生“信令风暴 ” ，也就是程序收到的请求完全超过了自己的处理能力 ，导致自己正常的业务无法展开 。 一旦某一程序发生故障 ，无法发送统一消息 ，那么其他程序均处于等待回复的状态中 ，使得整个系统处于停滞状态 ，导致不可用（一种改进可用性的办法是如果检测到一个程序故障 ，那么直接忽略该程序 ，无需再等待它的同意消息） 。分布式算法提供了一个“先到先得 ”和“投票全票通过 ”的公平访问机制 ，但是它的通信成本比较高 ，可用性也比集中式算法低 ，适用于临界资源使用频度较低 ，且系统规模较小的场景 。
令牌环算法
所有程序构成一个环结构 ，令牌按照顺序在程序之间传递 ，收到令牌的程序有权访问临界资源 ，访问完成后将令牌传送给下一个程序 ，如果该程序不需要访问临界资源 ，则直接把令牌传送给下一个程序 。
令牌环算法也被称作基于环的算法 。它非常适合通信模式为令牌环方式的分布式系统 。
令牌换算法的优点在于单个参与者通信效率高以及可用性比较高 。它的缺点在于当参与者对临界资源使用频率比较低时 ，会带来大量无用通信 。
令牌环算法的公平性高 ，适用于系统规模较小 ，并且系统中每个程序使用临界资源频率高且使用时间较短的场景 。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！