分布式操作系统进程
同步分析
杨利辛2015022497
2015 10 15
在分布式操作系统中，为实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法。

本文对分布式操作系统中的一些常见算法进行了分析，从而解析才能使进程在分布式操作系统中更加正确有效地协同工作。

在分布式系统中，处于不同物理位置的若干进程通过传递消息相互通信，进行协同工作完成同一任务。

工作过程中，进程产生了大量的事件和消息，这些事件和消息在时间上的先后顺序对工作正确有效的完成往往是有影响的。

由于进程所处的物理位置不同带来的时钟差异如各地时钟值的差异和时钟运行精度的差
异等）和网络传输延时等方面的原因，一个进程所看到的系统内事件和消息的先后顺序很可能与它们的实际顺序是不一致的，这样就带来了问题
布式系统都要求系统内的事件和消息的产生时间是精确的，甚至有些系统的任务结果是否正确直接有赖于这些精确的时间值，比如大型分布式数据库系统、电子商务和证券交易等金融业服务系统、分布式文件系统等。

在这些系统中，各进程间的同步就必须达到基于物理时钟同步的程度。

以证券系统为例，如果客户机的时钟与服务器的时钟不同步，那么客户按照自己的时钟所提出的服务请求将会被服务器提早或推迟执行，这可能会给客户带来巨大的损失。

这时，客户的服务请求是否被顺序公平的响应已失去了意义。

在单机条件下，诸进程运行于同一个处理机和内存环境中，进程通信十分简单。

进程之间可以借助于“共享存储器”进行直接通信。

而在多机条件下，相互合作的进程可能在不同的处理机上运行，进程间的通信涉及处理机的通信问题。

在松散耦合系统中，进程间通信还可能要通过较长的通信信道，甚至网络。

因此，在多机条件下，广泛采用间接通信方式，即进程间是通过消息进行通信的。

在分布式操作系统中，为了实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法。

首先，看事件排序问题。

在单处理机系统及紧密耦合的多处理机系统中，由于共有一种时钟又共享存储器，确定两个事件的先后次序比较容易。

而在分布式系统中，既无共用时钟，又无共享存储器，自然也就难于确定两个事件发生的先后次序了。

这里所说的排序，既包括要确定两个事件的偏序，也要包括所有事件的全序。

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）在处理机间能实现直接通信，即每个进程能把消息直接发送到指定的进程，不需要通过中转处理机。

在同步算法中，相对比较著名的算法还有Ricart and Agrawla算法和Mackawa(Square-Root)算法等。

1、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消息的进程无法收到全部响应，因此，系统还应该具备这样的功能，即一旦某个进程失效，系统能将该进程的名字通知其他进程。

2、令牌传送法
为实现进程互斥，在系统中可设置令牌（token），表示存取权力。

令牌本身
是一种特殊格式的报文，通常只有一个字节的长度，它不断地在由进程组成的逻辑环（logical ring）中循环。

环中的每一个进程只有唯一的前驱者（prodecessor）和唯一的后记者（successor）。

当环路中的令牌循环到某个进程并被接收时，如果该进程希望进入临界区，它便保持该令牌，进入临界区。

一旦它推出临界区，再把令牌传送给后继进程。

如果接收到令牌的进程并不要求进入临界区，便直接将令牌传送给后继进程。

由于逻辑环中只有一个令牌，因此也就实现了进程的互斥。

使用令牌时，必须满足以下两点要求：
（1）逻辑环应该具有及时发现环路中某进程失效或退出，以及通信链路故障的能力。

一旦发现上述情况，应立即撤消该进程，或重构逻辑环。

（2）必须保证逻辑环中，在任何时候都有一个令牌在循环，一旦发现令牌丢失，应立即选定一个进程产生新令牌。

利用令牌传送法实现互斥，所需要的消息数目是不定的。

因为，不管是否有进程要求进入其临界区，令牌总是在逻辑环中循环，当逻辑环中所有进程都要求进入临界区时，平均每个进程访问临界区只需要一个消息。

但如果在令牌循环一
周的时间内，只有一个进程要求进入临界区，则等效地需要N个消息（N是逻辑环中进程数）。

即使无任何进程要进入临界区，仍需不断的传输令牌。

另一方面，在令牌传送法中，存在着自然的优先级关系，即上游站具有更高的优先级，它能够优先进入临界区。

就好象FCFS队列一样，环路中的进程可依次进入自己的临界区，因而不会出现饥饿现象。

进程同步是分布式系统尤其是松耦合分布式系统中一个非常重要的问题，对系统的工作效率和工作精度等性能指标有着至关重要的影响。

因此，必须在系统中采用某种机制来实现进程间的同步。

不同的系统对进程之间同步程度的要求是不相同的，某些分布式系统中，要求进程之间达到物理时钟上的同步，才能正确有效地协同工作。

目前,无论是在国际上还是在国内, 有关分布式系统的理论和实践都是处在探索、研究和发展阶段。

但分布式系统是系统结构的总趋势。

因此,如何借助于现有的计算机科学研究成果,把常用的机种组成分布式系统,将是一个具有重大实用意义的课题。