最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

【天天新视野】《分布式技术原理与算法解析》学习笔记Day03

来源:博客园

分布式互斥方法

什么是分布式互斥?


(相关资料图)

对于同一个共享资源,当一个程序正在使用的时候,不希望被其他程序打扰,这种排他性的资源访问方式,叫做分布式互斥,被互斥访问的共享资源被称作临界资源(Critical Resource).

有什么方法可以让分布式系统里的程序互斥地访问临界资源?

我们一般有三种方法:

  • 集中式算法(霸道总裁)
  • 分布式算法(民主协商)
  • 令牌环算法(轮值CEO)

集中式互斥算法

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

集中式算法也被称为中央服务器算法。

使用该算法,一个程序访问一次临界资源,需要完成3次消息交互:

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

集中式算法的优点在于直观、简单、信息交互量少、易于实现,并且所有程序都只和协调者通信,程序彼此之间无需通信。

集中式算法的缺点在于协调者:

  1. 协调者会成为系统的性能瓶颈。
  2. 协调者容易引发单点故障,协调者不可用时,会导致整个系统不可用。

分布式互斥算法

当一个程序要访问临界资源时,先向系统中的其他程序发送一条请求信息,在接收到所有程序返回的同意消息后,才可以访问临界资源。其中请求消息包括所请求的资源、请求者ID以及发起请求的时间。

它是一种使用组播和逻辑时钟的算法。

使用该算法,一个程序访问一次临界资源,需要进行2*(n-1)次消息交互:

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

它的缺点主要包括:

  1. 当系统内需要访问临界资源的程序增多时,或者需要访问的临界资源数量增多时,容易产生“信令风暴”,也就是程序收到的请求完全超过了自己的处理能力,导致自己正常的业务无法展开。
  2. 一旦某一程序发生故障,无法发送统一消息,那么其他程序均处于等待回复的状态中,使得整个系统处于停滞状态,导致不可用(一种改进可用性的办法是如果检测到一个程序故障,那么直接忽略该程序,无需再等待它的同意消息)。

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

令牌环算法

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

令牌环算法也被称作基于环的算法。它非常适合通信模式为令牌环方式的分布式系统。

令牌换算法的优点在于单个参与者通信效率高以及可用性比较高。它的缺点在于当参与者对临界资源使用频率比较低时,会带来大量无用通信。

令牌环算法的公平性高,适用于系统规模较小,并且系统中每个程序使用临界资源频率高且使用时间较短的场景。

关键词: 临界资源 分布式系统 分布式算法