分布式系统中进程互斥算法的研究

摘要：文章通过对几种互斥算法的研究，认识到集中式算法的性能瓶颈以及非基于令牌的分布式算法的不健壮性，得到了改进后的基于令牌的分布式算法；通过对该算法的性能分析，并与前几种算法进行比较，验证了该算法是高效的，并给出正确性证明。

关键词：互斥算法；令牌；临界区

一、引言

在单机操作系统中，临界区、互斥以及其他有关同步问题，通常是用信号量和P*V操作、管程来解决。而在分布式系统当中，各个进程被认为是运行在不同的处理机上，为了防止出现以下情况：多个进程同时处于临界区；临界区外的进程阻塞其他的进程；有些进程在临界区外无休止的等待等等，多处理机系统的互斥不能简单地用单机的方法来实现，而是要用更为方便和高效的手段来实现多处理机系统的互斥。

解决进程互斥问题有软件的方法和硬件的方法，本文重点介绍软件方法，硬件方法从略。

二、经典互斥算法的探讨

（一）集中式算法

算法：选择一个进程作为协调器，用于协调临界区得进入。

特点：协调器在同一时间只允许一个进程进入临界区，故能保证互斥；因为请求消息是顺序排队得，不会出现“饿死”现象；单一的协调器是瓶颈。

（二）分布式算法

算法：想进入临界区的进程首先建立一个消息，该消息包括待进入的临界区名、进程名和时间戳。一个进程收到消息后，会有如下操作：不在临界区内且不想进入的话回复一个消息；在临界区内的话不回消息，将请求放入队列；不在临界区，也想进入的话就比较时间戳，时间戳小的进入。

特点：算法复杂，易出现“饿死”现象，系统不健壮；但它从理论上表明了算法的可行性，必将发展出实际可行的算法。

1、Lamport算法。特点：Lamport算法统一定序所有对临界段的请求，按先来先服务的原则让请求临界资源的进程进入其临界段；进程Pi发送的请求消息形如request（Ti，i），其中Ti=Ci是进程Pi发送此消息时对应的逻辑时钟值，i代表消息内容；每个进程保持一个请求队列，队列中的请求消息根据?准关系定序，队列初始为空。

2、Ricart and Agrawala算法。特点：算法实现了进程互斥，其控制是全分布的。因为进入临界区是根据时间戳的顺序来安排的（即先来先服务方式），所以根本不可能有进程“饥饿”现象发生。死锁也不可能发生，因为不存在环路等待。问题：其一，当有一个进程请求进入临界段时，所有其他进程都被牵连到。这就是说，每个进程都要知道其他进程的名字，当有新进程出现时，必须把新进程名字通知其他各进程，同时新进程要获知全部其他进程名。其二，如果某一进程故障，那么该算法因无法收到全部应答消息而崩溃。其三，没能进入临界区的进程只能频繁地暂停，因而只适用于小的进程集。

（三）令牌环算法

算法思想：整个系统只有一块令牌，只有令牌持有者才具有进入临界区的资格。当进程i从进程i-1接到令牌时，它检查是否想进入临界区，如果是，则进入，待其推出后，将令牌传递给进程i+1；如果不想进入，则直接把令牌向下传递。

问题：一是令牌丢失，事实上，检测令牌丢失是很困难的。二是进程故障，较容易恢复。

三、算法的改进（基于令牌的解决方案）

将令牌的概念引入到分布式的Ricart和Agrawala算法中，通过令牌即动态的单一点控制，使用对称的不同定义，这个算法要求的消息数在0到2（n－1）之间。在这个算法中，进程Pi收到来自Pj的回答消息后可以进入临界区（假设它得到所有其他进程的回答消息）任意次而无需再请求Pj的许可。因为当进程Pi收到Pj的回答消息时，隐含在该消息中的授权保持有效直到Pi收到来自Pj的请求消息。

算法思想：进入临界区的进程保留令牌。初始时，令牌被赋予任意一个进程。希望使用临界区的进程Pj不知道哪个进程拥有令牌，所以它通过向所有其他进程广播一个带时戳的消息来请求令牌。如果当前拥有令牌的进程Pi不再需要使用临界区，它就按照i＋1，i＋2，……n，1，2，……i－1的顺序搜索其他进程，找出第一个j，满足Pj最后一次请求令牌的时戳大于在令牌中记录的Pj最后一次拥有令牌的时戳，也就是说，Pj有一个未决的请求。于是，Pi把令牌传递给Pj。注意，优先级不是严格基于每个请求的时戳的，但是，由于令牌是沿着一个方向环绕传递的，所以不会有饥饿现象发生。算法：

P（i）：＝?鄢[请求资源消费释放资源处理-请求-消息其他]

分布式－互斥（distributed-mutual-exclusion）：＝||P （i：1...n）

以下变量用于每个Pi中：

clock：0，1，...，（初始化为0）

token_present：Boolean（除了一个进程，对所有其他进程均为F）

token_held：Boolean（F）

token：array（1...n）of clock（初始化为0）

request：array（1...n）of clock（初始化为0）

每个Pi中的函数定义如下：

其他：=所有其他不请求进入临界区的动作

消费：=进入临界区后消费资源

请求资源：=

[token_present＝T

[send（request_signal，clock，i）toall；

receive（access_signal，token）；

token_present：=T；

token_held：=T

]

]

释放资源：=

[token（i）：＝clock；

token_held：=F；

min j in the order[i＋1，…，n， 1，2，…，i＋2，i－1]

∧（request（j）>token（j））

[token_present：=F；

send（access_signal，token）to Pj

]

]

处理-请求-消息：：=

[receive（request_signal，k，j）

[ request（j）：=max（request （j），k）；

token_present ∧token_held 释放资源

]

]

四、以上各种算法的性能分析

Lamport的算法需要3（n－1）个消息和两个时间单位的延迟来保证n个进程的互斥，消息量很大，且发送的应答信号的目的并不是出于可靠性。

Ricart和Agrawala算法在消息量上有了一定的改进，需要2（n-1）个消息来保证。

改进后的算法即基于令牌的Ricart和Agrawala算法：当请求进程没有持有令牌时，以上算法需要n个消息（n－1个用于广播请求，1个用于传送令牌）；当请求进程持有令牌时，以上算法需要0个消息。

五、结论

集中式算法比较健壮，不会出现“饿死”现象，但是单一的协调器是系统瓶颈。

分布式算法虽然没有前一算法健壮，但是从理论角度论证了分布式算法的可行性。

基于令牌的算法比非基于令牌的算法的时间复杂性和消息复杂性小。不会发生饥饿现象，不需要关心当前谁在临界区中，是通过竞争的方式进入临界区。这在基于令牌的Ricart和Agrawala算法中得以验证。

综上所述，基于令牌的算法在排除了令牌丢失和进程故障等问题之后，在今后的分布式系统中，能有更好的应用。

参考文献：

1、徐甲同.高级操作系统[M].西安电子科技大学出版社,1998.

2、Nancy A Lynch著;舒继武等译.分布式算法[M].机械工业出版社,2004.

3、刘丹,刘心松等.基于读写特征的分布式互斥算法[J].电子学报,2004(2).

4、Jie Wu.分布式系统设计(Distribute System Design)[M].机械工业出版社,2001.

5、邱建林.分布式系统互斥问题的研究[A].全国理论计算机科学学术年会论文集[C],2003.

（作者单位：武警工程学院基础部）