集中互斥

while true:      
    Perform local operations        
    Acquire(lock)      
    Execute critical section        
    Release(lock)

1. 必须确保只有一个代码实例处于关键部分
2. 尽管多线程系统可以使用共享内存，但我们假设进程只能通过消息传递进行协调。

要求

1. 正确性/安全性：每次最多只有一个进程锁定/进入C.S.（critical section）
2. 公平性：任何提出请求的进程必须被授予锁定权限
   • 意味着系统必须是无死锁的
   • 假设没有进程将无限期地锁定在一个锁上
   • 最终公平：等待进程不会永远排除在外
   • 有限的公平性：等待进程将锁定在一定数量的周期内（通常为n）

其他要求

1. 少量的信息开销
2. 没有瓶颈
3. 容忍无序的消息
4. 允许进程加入协议或退出
5. 容忍失败的进程
6. 容忍丢弃的消息

相互排斥 一种集中式算法（1）

1 2 3

在分布式系统中达到互斥的最直接方法是仿照单机处理器系统中的方法，选举一个进程作为协作者。无论何时一个进程要访问共享资源，它都要向协作者发送一个请求信息，说明它想要访问哪个资源。如果当前没有其他进程访问资源，协作者就发送准许的应答消息。

1. 正确性
   • 显然安全
   • 公平取决于排队政策
     • 例如，如果总是优先考虑最低的进程ID，则处理1和2锁定3
2. 性能
   • “循环”是一个完整的协议，一个进程进入临界区，然后退出。
   • 每个周期3个消息（1个请求，1个授权，1个释放）
   • 锁服务器造成瓶颈
3. 问题
   • 当协调员崩溃时会发生什么？
   • 重启时会发生什么？

Selecting a Leader (Elections)

1. P注意到领导失败了
2. The Bully Algorithm（欺负算法）
   • P向所有具有较高号码的进程发送一个ELECTION消息。
   • 如果没有人回应，P赢得选举并成为协调员。
   • 如果其中一个上级回答，则接管。 P的工作已经完成了。

The Bully Algorithm

1. （a）程序4举行选举。 （b）过程5和6响应，告诉4停止。 （c）现在5和6各举行一次选举。

1.png

2. （d）过程6告诉5停止。 （e）流程6获胜并告诉所有人。

2.png

非集中式

1. 假设有n个协调员
   • 访问需要m> n / 2个协调员多数票。
   • 协调员总是立即响应GRANT或DENY的请求
2. 节点故障仍然是一个问题
   • 协调员可能会忘记重新启动投票
3. 如果你得到少于m票，怎么办？
   • 退后并在稍后重试
   • 大量请求访问的节点会影响可用性
   • 饥饿！

但是该算法也有自身的缺陷，即当某个协作者崩溃时，它将忘记之前投过的票，可能在回复后又投了重复的票给其他请求者；比如已经允许了p进程访问共享资源，之后该协作者重置了，又允许了q进程去访问共享资源，此时可能会出现不一致问题。

为了防止有很多个进程同时发起访问请求导致谁也无法访问共享资源，发起访问的进程可以把请求带上时间戳，其他协作者按照时间戳的先后顺序进行投票允许，同时请求者还需要在访问结束后通知所有其他协作者访问已释放。

参考

分布式系统互斥算法---非集中式算法