分布式操作系统中进程同步.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)必须保证逻辑环中，在任何时候都有一个令牌在循环，一旦发现令牌丢失，应立即选定一个进程产生新令牌。利用令牌传送法实现互斥，所需要的消息数目是不定的。因为，不管是否有进程要求进入其临界区，令牌总是在逻辑环中循环，当逻辑环中所有进程都要求进入临界区时，平均每个进程访问临界区只需要一个消息