分布式互斥
在分布式系统里，排他性的资源访问方式，叫作分布式互斥（Distributed Mutual Exclusion），而这种被互斥访问的共享资源就叫作临界资源（Critical Resource）。
集中式算法
引入一个协调者程序，得到一个分布式互斥算法。每个程序在需要访问临界资 源时，先给协调者发送一个请求。如果当前没有程序使用这个资源，协调者直接授权请求程序访问；否则，按照先来后到的顺序为请求程序“排一个号”。如果有程序使用完资源，则通知协调者，协调者从“排号”的队列里取出排在最前面的请求，并给它发送授权消息。拿到授权消息的程序，可以直接去访问临界资源。 这个互斥算法，就是集中式算法，也可以叫做中央服务器算法,之所以这么称呼，是因为协调者代表着集中程序或中央服务器。
原理图
一个程序完成一次临界资源访问，需要如下几个流程和消息交互：
- 向协调者发送请求授权信息，1 次消息交互；
- 协调者向程序发放授权信息，1 次消息交互；
- 程序使用完临界资源后，向协调者发送释放授权，1 次消息交互。
小结
集中式算法具有简单、易于实现的特点，但可用性、性能易受协调者影响。在可靠性和性能有一定保障的情况下，比如中央服务器计算能力强、性能高、故障率低，或者中央服务器进行了主从备份，主故障后从可以立马升为主，且数据可恢复的情况下，集中式算法可以适用于比较广泛的应用场景。
分布式算法
当一个程序要访问临界资源时，先向系统中的其他程序发送一条请求消息，在接收到所有程序返回的同意消息后，才可以访问临界资源。其中，请求消息需要包含所请求的资源、请求者的 ID，以及发起请求的时间。 在分布式领域中，称之为分布式算法，或者使用组播和逻辑时钟 的算法。
一个程序完成一次临界资源的访问，需要进行如下的信息交互：
- 向其他 n-1 个程序发送访问临界资源的请求，总共需要 n-1 次消息交互；
- 需要接收到其他 n-1 个程序回复的同意消息，方可访问资源，总共需要 n-1 次消息交互。
一个程序要成功访问临界资源，至少需要2*(n-1)次消息交互。假设，现在系统中的 n 个程序都要访问临界资源，则会同时产生 2n(n-1) 条消息。总结来说，在大型系统中使用分布式算法，消息数量会随着需要访问临界资源的程序数量呈指数级增加，容易导致高昂的“沟通成本”。
分布式算法适合节点数目少且变动不频繁的系统，且由于每个程序均需通信交互，因此适合 P2P 结构的系统。
Hadoop 是分布式系统，其中的分布式文件系统 HDFS 的文件修改就是一个典型的应用分布式算法的场景。
令牌环算法
所有程序构成一个环结构，令牌按照顺时针（或逆时针）方向在程序之间传递，收到令牌的程序有权访问临界资源，访问完成后将令牌传送到下一个程序；若该程序不需要访问临界资源，则直接把令牌传送给下一个程序。
在分布式领域，这个算法叫作令牌环算法，也可以叫作基于环的算法。
令牌环算法非常适合通信模式为令牌环方式的分布式系统。
小结
令牌环算法的公平性高，在改进单点故障后，稳定性也很高，适用于系统规模较小，并且系统中每个程序使用临界资源的频率高且使用时间比较短的场景。
总结
| 算法 | 概念 | 优点 | 缺点 | 应用场景 |
|---|---|---|---|---|
| 集中式算法 | 引入一个协调者，将所有请求者进行排序，最早请求的参与者可以使用资源 | 简单、易于实现；通信高效 | 可用性低；性能受协调者影响 | 在协调者可靠性和性能有一定保障情况下，可以适用于比较广泛的场景 |
| 分布式算法 | 征求其它参与者同意后，使用临界资源 | 可用性高 | 通信成本高；复杂度高 | 临界资源使用频度低且系统规模较小的场景 |
| 令牌环算法 | 所有参与者组成一个环，轮流使用资源 | 单个参与者通信效率高；可用性较高 | 当参与者对临界资源使用频率较低时，带来较多无用通信 | 系统规模较小，系统中每个程序使用共享资源频度较高且使用时间较短的场景 |
