第三章分布式协同处理.ppt

* 第三章 分布式协同处理 3.1事件定序与时戳 从任何一个单一的进程来看，其中的事件可由本地时钟进行惟一的排序。但是，在分布式系统中不能完美地进行时钟同步，那么一般就不能用物理时间指明其中任意一对事件发生的次序。 一般，在分布式系统中，可以使用类似于物理因果关系的方案来判断不同进程中事件发生的次序，这样一种定序思路是基于下面两个基本观点的： （1）若两个事件发生在同一进程中，则可用观察到的次序来确定它们发生的次序。 （2）无论何时在进程间传递消息，发送消息的事件先于接收同一消息的事件。 用这两种观点得到的定序为HB关系（Happened-Before relation），有时也称之为因果定序 （causal ordering）。 定义HB关系，并“ →”表示HB关系： HB1：如果存在进程p，且xp→y，则有x→y； HB2：对任何消息m，send（m）→receive（m），其中send（m）是发送消息m的事件，receive（m）是接收同一消息m的事件； HB3：对于事件x,y,z，如果有x→z，且y→z，则有x→z。 图3.1说明了进程P1、P2、P3中一些事件之间的“→”关系。 从图3.1中还可看出，并不是所有的事件之间都存在关系→例如a/→e，e/→a。 逻辑时钟是一种单调增长的软件计数器。一般而言，它的值与任何物理时钟都没有特别的关系。每个进程p保持它自己的逻辑时钟Cp，并将其作为事件的时戳（time stamp）。用Cp（a）表示事件a在进程p中的时戳，用C（b）表示事件b在任何进程中的时戳。 为了刻化“→”关系，进程按下面方式更新它们的逻辑时钟并传递逻辑时钟的值： LC1：Cp在进程p上每一事件之前增值： Cp=Cp+1； LC2：①当进程p发送消息m时，它在m上携带逻辑时钟值t=Cp； ②当进程q收到消息（m,t）时，它计算Cq=max（Cq，t）+1。 显然，通过施归纳法于两个事件a和b相关的事件序列的长度，可以证明，如果a→b，则C（a）＜C（b）。但反过来并不成立。 逻辑时钟仅能对事件集进行部分排序，因为由不同进程产生的不同事件组可能有相同的数字化时戳。但可以通过考虑发生事件的进程的标识符（例如，给它们赋以惟一的编号）来将这种部分排序扩充为完全排序，这是对系统中所有不同事件进行排序的一种定序方法。 假定进程Pa上发生的事件a的时戳为Ta，在进程Pb上发生的事件b的时戳为Tb。设事件a和b的全局逻辑时戳分别为（Ta，Pa）和（Tb，Pb），可以定义： （Ta，Pa）＜（Tb，Pb）当且仅当Ta＜Tb或者Ta=Tb但Pa＜Pa。 这样就称进程Pa中的事件a先于进程Pb中的事件b发生，用a==b表示。 3.2分布式互斥算法 实现分布式互斥的几点要求如下： （1）安全性：在某一时刻至多只有一个进程在临界段内执行。 （2）可用性：请求进入临界段的进程终将准入。 可用性要求还隐含这种实现能避免死锁且不会发生饥饿现象。 （3）定序：按关系“==”排定的次序进入临界段。 3.2.1分布式互斥算法的基本假定 分布式算法有如下的基本假定： （1）一个分布式系统由n个站点组成，它们从1到n惟一地编号，每个站点含有一个进程，而且进程和站点间存在一一对应的关系。 （2）pipeline特性成立，即从一个进程发送给另一个进程的消息是按它们发送的次序接收的。 （3）每条消息在有穷时间间隔内都能正确地传递到它的目的地。 （4）系统是全互连的，因而每个进程都可直接给其他的进程发送消息。 ＊为了解决分布式系统中的同步问题，必须提供类似分布式信号量的机制。为简化讨论，下面只考虑初值为1的二元信号量的实现问题，这也就等价于解决互斥问题。 3.2.2集中式算法 用于解决分布式互斥问题的集中式算法中，通常选定某个进程负责协调进入临界段的工作，每个希望进入临界段（引用互斥）的进程都给协调者进程发送一个Request消息，仅当此进程接收到协调者的Reply消息时，它才可以进入它的临界段。当它退出临界段时，此进程发送一个Release消息给协调者进程，然后继续它的执行。 在接收到一个Request消息后，协调者进程检查是否有某个进程位于临界段，若没有进程位于它的临界段，协调进进程马上回送一个Release消息后；否则，便将该Request消息置入Request队列。当协调者进程接收到一个Release消息后，它（用某种调度策略）从Request队列中取出一个Request消息，并发送一个Reply消息给该请求服务的进程。