分布式操作系统中进程同步.doc

分布式操作系统中进程同步在单机条件下，诸进程运行于同一个处理机和内存环境中，进程通信十分简单进程之间可以借助于"共享存储器"进行直接通信而在多机条件下，相互合作的进程可能在不同的处理机上运行，进程间的通信涉及处理机的通信问题在松散耦合系统中，进程间通信还可能要通过较长的通信信道，甚至网络因此，在多机条件下，广泛采用间接通信方式，即进程间是通过消息进行通信的在分布式操作系统中，为了实现进程的同步，首先要对系统中发生的事件进行排序，还要有良好的分布式同步算法首先，看事件排序问题在单处理机系统及紧密耦合的多处理机系统中，由于共有一种时钟又共享存储器，确定两个事件的先后次序比较容易而在分布式系统中，既无共用时钟，又无共享存储器，自然也就难于确定两个事件发生的先后次序了这里所说的排序，既包括要确定两个事件的偏序，也要包括所有事件的全序下面我们简单介绍一下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队列一样，环路中的进程可依次进入自己的临界区，因而不会出现饥饿现象6503477�。