分布式互斥

2017, Apr 05    

要点

  • 临界区问题
  • 解决分布式互斥问题的解决方案：基于消息传送的解决方案
  • 这种解决方案独立于特定的资源管理方案，下面会具体描述其算法
  • 部分算法后在还会进一步描述

[NOTE] 有些应用场景是没有服务器的，且需要协调它们（一对进程）对共享资源的访问。这种情况经常出现在以太网、”自组织”模式的IEEE 802.11 无线网等网络中，其中网络接口作为对等成分进行协作，使得在共享介质上一次只有一个节点进行传输。

[NOTE] 简单的解决方案是这些进程只要通过互相通信就能互斥，就能不需要服务器。

  • NFS文件服务器是无状态的，因此不支持文件加锁
  • UNIX系统提供由locked（守护进程）实现的一个文件加锁服务。

互斥算法

假设：

  • 无共享变量的N个进程p~i~(i=1,2,···,N)的系统。这些进程只在临界区内访问公共资源。
  • 只有一个临界区。一个就够了，完成后就可以扩展到其他临界区。
  • 系统是异步的，进程不出故障，消息传递是可靠的。这样的传递的任何消息最终都被完整地恰好发送一次。

临界区的应用层协议：

enter() //进入临界区——如果有必要，可以阻塞进入 resourceAccesses() //在临界区反问共享资源 exit() //离开临界区——其他进程现在也可以进入 —-

对互斥的基本要求：

  • ME1：（安全性） 在临界区（CS）一次最多有一个进程可以执行

  • ME2：（活性）进入和离开临界区的请求最终成功执行。既无饥饿也无死锁

  • ME3：（顺序）如果进入CS请求在先，那么进入cs也是这个顺序。

[TIP] 没有饥饿问题是一个公平性条件。

[TIP] 进程进入临界区的顺序也是一个公平性问题。不可能按照请求的时间决定顺序，因为没有全局时钟。可以用进入临界区之间的发生在先顺序。

互斥性能标准：

  • 消耗的带宽（bandwidth），与在每个entry和exit操作中发送的消息数成比例
  • 每次entry和exit操作由进程导致的客户延迟
  • 算法对系统吞吐量的影响。假设一组进程之间通讯是必要的，一组进程作为一个整体访问临界区的比率。通过一个进程离开临界区到下一个进程进入到临界区之间的同步延迟（synchronization delay）来衡量这个影响。同步延迟较短时，吞吐量较大。

== 中央服务器算法

这是最简单的方法，使用一个服务器授予进入临界区的许可。

  1. 请求令牌
  2. 释放令牌
  3. 授予令牌

等待进程队列：先进（请求顺序）先出（移除并授予该进程令牌）

此算法满足ME1，ME2，不满足ME3。

性能：

  • 带宽消耗：一个进程要进入临界区需要2个消息，请求和授权。因为往返时间而使请求进程延迟。离开临界区需要发送1个释放（release）消息。采用异步消息传递，就不会对离开的进程造成延迟。
  • 客户延迟：消息往返时间导致进程延迟。
  • 同步延迟：1个消息的往返时间。
  • 服务器成为系统的瓶颈。同步延迟是下面两个消息往返一次要花费的时间：
  • 发到服务器的释放消息
  • 随后让下一进程进入临界区的授权消息

== 基于环的算法

N个进程中安排互斥而不需其他进程的简单方法之一：将这些进程放到一个逻辑环中。这样只要求每个进程P~i~与环中下一个进程P~(i+1)modN~有一个通讯通道。

通过获得在进程间沿着环单向（顺时针/逆时针）传递的消息为形式的令牌来实现互斥。

环拓扑结构可以与物理结构互连无关

满足ME1，ME2，令牌不必按照发生在先顺序获得

性能：

  • 带宽消耗 ： 会不断消耗网络带宽（当一个进程在临界区中时除外）：进程需要不断沿着环发送消息，即使进程不需要令牌。
  • 客户延迟：进入到获取0～N个消息传输。
  • 同步延迟：在一个进程离开和下一个进程进入临界区之间的同步延迟是1～N个消息传输 性能

== 使用组播和逻辑时钟的算法 -An algorithm using multicast and logical clocks [1981]

基于组播的实现N个对等进程间互斥的算法。

进入临界区的进程组播一个请求消息，并且只有在其他进程都回答了这个消息时才能进入。进程回答请求的条件满足ME1，ME2，ME3

进程p{1},p{2},···,p{N}具有不同的数字标识符，且每个进程p~i~保持一个根据LC1和LC2更新的Lamport时钟。请求进入的消息如<T,p~i~>,其中T是发送者的时间戳，p~i~是发送者的标识符。

每个进程在标亮state中记录它的状态，这些状态包括在临界区外（RELEASED）、希望进入（WANTED）以及在临界区内（HELD）。

伪代码：

  • On initialization ** state：=RELEASED； **

  • For pi to enter the critical section ** state：=WANTED；

组播请求给所有进程；

T：=请求的时间戳； 设置该请求至自己的变量中<T,p~i~>。

Wait until 接收到的应答数 = N-1；（阻塞）

state：=HELD； **

  • On receipt of a request <T~i~, p~i~> at p~j~ (i不等于j)
if( state=HELD or ( state=WANTED and (T,p{j}) < (T{i},p{i}) ) )

_如果 我已经HELD 或者 我也想要而且你的时间比我晚_

then

将请求放入p~i~的队列中（先入先出）,不给出应答；

else

马上给p~i~应答 // <1>

endif

[TIP] 请求处理在这里被延期 **

  • For pi to exit the critical section： ** state：=RELEASED;

对已入队列的请求给出应答； **

<1> 如果一个进程请求进入，而且他进程的状态都是RELEASED，那么所有进程会立即回答请求，请求者将得以进入。 <2> 如果有某进程状态为HELD，那么该进程在结束对临界区的访问前不会回答请求，因此在这期间请求者不能得以进入。 <3> 如果有两个或多个进程同时请求进入临界区，那么时间戳最近的进程将是第一个收集到N-1个应答的进程，它将被准许下一个进入。 <4> 如有请求具有相等的Lamport时间戳，那么请求将根据进程的标识符排序。

[WARNING] 当一个进程请求进入时，它推迟处理来自其他进程的请求，知道发送了它自己的请求并且记录了该请求的时间戳T为止，这样做的目的是为了进程在处理请求时作出一致的决定。

性能：

  • 带宽消耗:获取进入的许可需要2（N-1）个消息：N-1个消息用于组播请求，对应这N-1个应答消息。
  • 客户延迟（请求进入）:1个消息往返时间（忽略组播请求消息带来的延迟）
  • 同步延迟：1个消息的传输时间
  • 如果硬件支持组播，请求只需要一个消息，那么共需要N个消息。
  • 因此，在带宽消耗方面，该算法比前面算法更昂贵。

优点

他的同步延迟仅是一个消息传输时间。前两个算法都有一个往返的同步延迟。

改进：

  • 最近一次进入过临界区且没有接到其他的进入请求的进程，仍需如描述的那样执行协议，即使它可以简单地在本地把令牌重新分配给自己。
  • Ricart和Agrawala改进了协议，使它在没有硬件组播时，在最坏（也是通常的）情况下需要N个消息来获得进入许可。见[Raynal 1988]

== Maekawa的投票算法 -Maekawa’s voting algorithm [1985]

为了让一个进程进入临界区，不必要求所有对等进程都同意。只要任意两进程使用的子集（subset）有重叠，进程只需要从其对等进程的子集获得进入许可即可，把这样的进入临界区想象成进程互相选举。

一个”候选”进程为进入必须收集到足够的选票。在两个投票集合的交集中的进程，通过把选票只投给以一个候选者，保证了ME1。

把每个进程p~i~(i=1,2,···,N)关联到一个选举集合（votingset）V~i~，其中V~i~ ⊆ {p~1~,p~2~,···,p~X~, }。

集合V~i~的选择，使得对所有i,j=1,···,N,有：

  • p~i~ ∈ V~i~
  • V~i~ ∩ V~j~ ≠ φ ，即任意两个选举集合至少有一个公共成员。
  • V~i~ =K ,(公平的说，应该是K ≈) ,公平起见，每个进程有同样大小的选举集合。
  • 每个进程p~j~包括在选举集V~i~中的M个集合中，M = K

最优解决方案：K最小且允许进程达到互斥的情况，具有K ～ √N 且 M = K （因此每个进程所在选举集合的数量K与每个集合的元素个数M相同）。

  1. N = M*(K-1)+1
  2. K = M
  3. N = K*(K-1)+1,消息复杂度为O(√N)
计算最优集合R~i~较为复杂。作为一种近似方法，通过一种简单的方法可以得到R~i~ : 把 R~i~ ～2√N 的进程放到一个√N×√N矩阵中，让V~i~是行（包含p~i~）和列（包含p~i~）的并集。

[TIP] 在集于投票集的分布式互斥算法中， 同步延迟主要依靠投票集的组织。组织好投票集以 达到最小同步延迟在分布式互斥算法中是非常重 要的。

[TIP] 计算最优集合，这关系到实现的复杂度，现在依然再进行研究，并产出各种的优化算法，很多毕业论文都以此为出发点，进行研究。

伪代码：

On initialization
	state := RELEASED;
	voted := FALSE;
For pi to enter the critical section
	state := WANTED;
	Multicast request to all processes in Vi;(也包括自己)
	Wait until (number of replies received = K);
	state := HELD;
On receipt of a request from pi at pj
	if (state = HELD or voted = TRUE)
	then
		queue request from pi without replying;
	else
		send reply to pi;
		voted := TRUE;
	end if
For pi to exit the critical section
	state := RELEASED;
	Multicast release to all processes in Vi;
On receipt of a release from pi at pj
	if (queue of requests is non-empty)
	then
		remove head of queue – from pk, say;
		send reply to pk;
		voted := TRUE;
	else
		voted := FALSE;
	end if

[TIP] Sanders[3]证明了Maekawa的互斥访问临界区消息机制存在死锁,并引入了带时间戳(时间戳概念最早在Lamport[4]提出)的请求消息.修改后的协议，进程按照发生在先顺序对待应答的请求排队，也满足ME3。

性能

  • 带宽消耗: 即进入需要2√N个消息，退出需要√N个消息
  • 客户延迟：1个消息往返时间
  • 同步延迟：较差，1个往返时间（a round-trip time），非单个消息的往返时间

== 容错

  • 当消息丢失时会发生什么？
  • 当进程崩溃时会发生什么？

当消息丢失：

  • 中央服务器算法：可以容忍一个既不持有也不请求令牌的客户进程的崩溃。
  • 环算法：不能容忍任何单个进程崩溃故障。
  • 组播和逻辑时钟算法：不能容忍在响应前、持有时、等待时崩溃。
  • Maekawa的投票算法：可以容忍一些进程的崩溃故障；如果一个崩溃进程不再所需要的投票集中，那么他的故障不会影响其他进程。

[TIP] 假设存在可靠的故障检测器，如何修改算法使之能容错。 [TIP] 即使有一个可靠的故障检测器，也需要注意允许在任何阶段出故障（包裹在恢复过程期间）并在检测到故障以后重构进程的状态。

Twitter Facebook Google+
# 分布式 # 算法