分布式操作系统中进程同步
在单机条件下，诸进程运行于同一个处理机和内存环境中，进程通信十分简单。进程之间可以借助于“共享存储
器”进行直接通信。而在多机条件下，相互合作的进程可能在不同的处理机上运行，进程间的通信涉及处理机的通信
问题。在松散耦合系统中，进程间通信还可能要通过较长的通信信道，甚至网络。因此，在多机条件下，广泛采用间
接通信方式，即进程间是通过消息进行通信的。 在分布式操作系统中，为了实现进程的同步，首先要对系统中发生
的事件进行排序，还要有良好的分布式同步算法。
首先，看事件排序问题。在单处理机系统及紧密耦合的多处理机系统中，由于共有一种时钟又共享存储器，确定
两个事件的先后次序比较容易。而在分布式系统中，既无共用时钟，又无共享存储器，自然也就难于确定两个事件发
生的先后次序了。 这里所说的排序，既包括要确定两个事件的偏序，也要包括所有事件的全序。下面我们简单介绍
一下 Lamport于1978年提出的一个算法。该方法建立在以下基础上：
（1） 事件之间存在的偏序；
（2） 为每一个进程设置一个逻辑时钟。所谓逻辑时钟，是指能为本地启动的所有活动，赋予一个编号的机构，他
可以用计数器来实现。在系统中，每一个进程都拥有自己的逻辑时钟 c。在一个系统的逻辑时钟系统，应满足条件：
对于任何活动 a(ini)和 b(inj)，如果 a->b,则相应的逻辑时钟c(i,a) < b(j,b)。其中i，j表示处于不同物理
位置的进程。为了满足上述条件，必须遵循以下规则：
第一，根据活动发生的先后，赋予每个活动唯一的逻辑时钟值。
第二，若活动 a 是进程 i 发送的一条消息 m，消息 m中应包含一个时间邮戳 T(m)=c(i,a);当接受进程 j在收
到消息时，如果其逻辑时钟 c(j,b)<c(i,a),则应当重置c(j,b)大于或等于c(j,b)。
这里我们对第二个规则作些说明。由于每个进程都拥有自己的逻辑时钟，这些时钟的运行并非同步，因此可能出
现这种情况：一个进程 i发送的消息中所含的逻辑时钟c(m)=100，而接收进程 j在收到此消息时的逻辑时钟c(j)=
96，这显然违背了全序的要求，因为发送消息事件 A和接收事件 B 之间存在着A->B 的关系。因而提出了第二项规
则，用于实现逻辑时钟的同步。根据这个规则，应该调整进程 j 的时钟，使 c(j)>=c(m),例如 c(j)=c(m)+1=101。
其次，看同步算法。在所有的同步算法中，都包含以下四项假设：
（1） 每个分布式系统具有N个节点，每个节点有唯一的编号，可以从1 到 N。每个节点中仅有一个进程提出访
问共享资源的请求。
（2） 按序传送信息。即发送进程按序发送消息，接收进程也按相同顺序接收消息。
（3） 每个消息能在有限的时间内被正确地传送到目标进程。
（4） 在处理机间能实现直接通信，即每个进程能把消息直接发送到指定的进程，不需要通过中转处理机。
在同步算法中，比较著名的有 Lamport 算法， Ricart and Agrawla 算法，Mackawa(Square-Root)算法等，下面我们
就介绍其中的几个。
1、 Lamport 算法
在该方法中，利用事件排序方法，对要求访问临界资源的全部事件进行排序，并且按照先来先服务的原则，对事件
进行处理。该算法规定，每个进程Pi,在发送请求消息Request时，应该为它打上时间邮戳(Ti,i),其中Ti是进程Pi的逻
辑时钟值，而且在每个进程中都保持一个请求队列，队列中包含了按逻辑时钟排序的请求消息。Lamport 算法用以下五
项规则定义：
（1）当进程 Pi要求访问某个资源时，该进程将请求消息挂在自己的请求队列中，也发送一个Request(Ti,i)消息
给所有其他进程。
（2）当进程 Pj收到 Request(Ti,i)消息时，形成一个打上时间邮戳的 Reply(Tj,j)消息，将它放在自己的请求队
列中。应该说明，若进程 Pj 收到 Request(Ti,i) 消息前，也提出过对同一资源的访问请求，那么其时间邮戳应该比
T(Ti,i)小。
（3）若满足以下两个条件，则允许进程Pi访问该资源：
●Pi自身请求访问该资源的消息已经处于请求队列的最前面。
●Pi已经接收到从其他所有进程发回的响应消息，这些消息上的邮戳时间晚于T(Ti,i)。
（4）为了释放该资源，Pi从自己的请求队列中消除请求消息，并发送一个打上时间邮戳的Release 消息给其他所
有进程。
（5）当进程 Pj收到Pi的 Release 消息后，从自己的队列中消除Pi的Request(Ti,i)消息。
这样，当每一个进程要访问一个共享资源时，本算法要求该进程发送3（N-1)个消息，其中(N-1)个Request消息，
(N-1)个Reply消息，(N-1)个 Release消息。
2、 Ricart and Agrawla 算法
Ricart 等提出的分布式同步算法，同样基于Lamport 的事件排序，但又做了些修改，使每次访问共享变量时，仅
需发送 2(N-1)个消息。 下面是对Ricart and Agrawla 算法的描述。
（1）当进程Pi要求访问某个资源时，它发送一个Request(Ti,i)消息给所有其他进程。
（2）当进程Pj收到Request(Ti,i)消息后，执行如下操作：
●若进程Pj正处在临界区中，则推迟向进程Pi发出Reply响应；
●若进程Pj当前并不要求访问临界资源，则立即返回一个有时间邮戳的Reply消息；
●若进程Pj也要求访问临界资源，而在消息Request(Ti,i)中的邮戳时间早于(Tj,i),同样立即返回一个有时
间邮戳的 Reply消息；否则，Pj保留 Pi发来的消息Request(Ti,i)，并推迟发出Reply响应。
（3）当进程Pi收到所有其他进程发来的响应时，便可访问该资源。
（4）当进程释放该资源后，仅向所有推迟发来 Reply消息的进程发送Reply消息。
该算法能够获得较好的性能：能够实现诸进程对共享资源的互斥访问；能够保证不发生死锁，因为在进程--资源图
中，不会出现环路；不会出现饥饿现象，因为对共享资源的访问是按照邮戳时间排序的，即按照FCFS原则服务的；每
次对共享资源访问时，只要求发2(N-1)个消息。下图说明了进程在访问共享资源时的状态转换：
当然这个算法也有一定的问题：第一，每个要求访问共享资源的进程，必须知道所有进程的名字，因此，一旦有
新进程进入系统，它就将通知系统中所有进程。第二，如果系统中有一个进程失败，则必然会使发出Request消息的
进程无法收到全部响应，因此，系统还应该具备这样的功能，即一旦某个进程失效，系统能将该进程的名字通知其他
进程。
3、令牌传送法
为实现进程互斥，在系统中可设置令牌（token），表示存取权力。令牌本身是一种特殊格式的报文，通常只有一
个字节的长度，它不断地在由进程组成的逻辑环（logical ring）中循环。环中的每一个进程只有唯一的前驱者
（prodecessor）和唯一的后记者（successor）。当环路中的令牌循环到某个进程并被接收时，如果该进程希望进入
临界区，它便保持该令牌，进入临界区。一旦它推出临界区，再把令牌传送给后继进程。如果接收到令牌的进程并不
要求进入临界区，便直接将令牌传送给后继进程。由于逻辑环中只有一个令牌，因此也就实现了进程的互斥。 使用
令牌时，必须满足以下两点要求：
（1）逻辑环应该具有及时发现环路中某进程失效或退出，以及通信链路故障的能力。一旦发现上述情况，应立即
撤消该进程，或重构逻辑环。
（2）必须保证逻辑环中，在任何时候都有一个令牌在循环，一旦发现令牌丢失，应立即选定一个进程产生新令牌。
利用令牌传送法实现互斥，所需要的消息数目是不定的。因为，不管是否有进程要求进入其临界区，令牌总是在
逻辑环中循环，当逻辑环中所有进程都要求进入临界区时，平均每个进程访问临界区只需要一个消息。但如果在令牌
循环一周的时间内，只有一个进程要求进入临界区，则等效地需要N个消息（N是逻辑环中进程数）。即使无任何进程
要进入临界区，仍需不断的传输令牌。另一方面， 在令牌传送法中，存在着自然的优先级关系，即上游站具有更
高的优先级，它能够优先进入临界区。就好象FCFS队列一样，环路中的进程可依次进入自己的临界区，因而不会出现
饥饿现象。