分布式操作系统分布式操作系统中进程同步事件排序问题分布式同步算法这个算法应满足：资源分配的互斥性、不产生饿死现象、且各资源管理者处于平等地位而无主控者。通常把这种资源分配算法称分布式同步算法，由同步算法构成的机制称分布式同步机制。垂直方向代表空间，水平方向代表时间，带标志的水平线代表进程（process），带标志的点代表事件，带箭头的线代表消息(message)。事件排序先定义一个关系称作“先发生”，表达为“a→b”读作“a在b之前发生”，意思是指系统中所有进程认为事件a先于事件b发生，有两三种情况会产生“先发生”关系：(1):如果a和b是同一进程中的两个事件，且a发生在b之前，则a→b为真。(2)：如果a是一个进程发送消息事件，b为另一个进程接受该消息事件，则a→b为真。(3):存在某个事件c，若有则a→c并且则c→b,则a→b为真.(4):如果两个事件x和y发生在不同进程中，而且这两个进程也不交换信息，那么x→y和y→x都不成立，这两个事件就称为并发事件，简单的说，无法确定这两个事件谁先谁后。例如：有三个进程p1,p2和p3,它们分别发生以下事件：事件a:p1发送消息给p2;事件b:p2接收来自p1的消息；事件c:p2接收到p1的消息后发消息给p3;事件d:p3接收来自p2的消息；显然，我们有：a→b→c→d;然而，如果假设p2在事件b之前发生过某事件f，例如，打印输出，尽管可以确定：f→b,f→c,f→d这些关系，但a和f之间的先后关系是无法确定的。逻辑时钟逻辑时钟形式(m,V,i)(其中，m为消息内容，V为该消息的向量时钟，i为结点编号)。基于传送的假定，通道可以分为：FIFO（先进先出）、因果顺序传送和随机顺序传送。FIFO:如果一个通道保持通过它发送的消息的顺序因果顺序传送：假设进程P1和P2分别在事件e1和e2中给进程P3发送消息m1和m2。如果e1在e2之前发生，则进程P3在接收m2之前接收m1。随机顺序传送的通道没有限制。在没有明确说明给定通道的类型时，我们都假设它是FIFO通道。令牌传送法使用令牌时，必须满足以下两点要求：（1）逻辑环应该具有及时发现环路中某进程失效或退出，以及通信链路故障的能力。一旦发现上述情况，应立即撤消该进程，或重构逻辑环。（2）必须保证逻辑环中，在任何时候都有一个令牌在循环，一旦发现令牌丢失，应立即选定一个进程产生新令牌。利用令牌传送法实现互斥，所需要的消息数目是不定的。因为，不管是否有进程要求进入其临界区，令牌总是在逻辑环中循环，当逻辑环中所有进程都要求进入临界区时，平均每个进程访问临界区只需要一个消息。但如果在令牌循环一周的时间内，只有一个进程要求进入临界区，则等效地需要N个消息（N是逻辑环中进程数）。即使无任何进程要进入临界区，仍需不断的传输令牌。另一方面，在令牌传送法中，存在着自然的优先级关系，即上游站具有更高的优先级，它能够优先进入临界区。就好象FCFS队列一样，环路中的进程可依次进入自己的临界区，因而不会出现饥饿现象。