第六章向量时钟

1、第11章 分布式操作系统系统11.1 分布式系统的体系结构分布式系统（distributed system)是由若干非共享内存和时钟的计算机组成，它们通过一个计算机网络彼此交换消息；并且每台计算机由自己的内存和运行自己的操作系统，如图1所示。图1 分布式系统的体系结构分布式系统的优点：l 资源共享l 增强的性能l 改善的可靠性和可用性l 模块可扩张性11.1.1 分布式系统的体系结构类型Tanenbaum和Renesse将分布式系统分成三类：l 小型机类型(minicomputer model)：在小型机类型中，分布式系统由若干小型机组成（例如，VAX)。每个计算机支持多个用户并且提供访问远程

2、资源。处理机个数和用户数之比通常小于1。l 工作站类型(workstation model)：在工作站类型中，分布式系统由直到几百台工作站组成。每个用户有一台工作站完成用户的任务。藉助于分布式文件系统，用户可以访问任何数据，而不管其位置。处理机个数和用户数之比通常等于1。Athena和Andrew是其例子。l 处理机池类型(processor pool model)：在处理机池类型中，按照用户的需求分配一个或多个处理机给用户。一旦完成任务它们返回处理机池等待新的分配。处理机个数和用户数之比通常大于1。Amoeba是一个工作站和处理机池类型组合的试验系统。分布式操作系统是由一个通信网络连接的若干

3、自治的计算机所组成的分布式计算系统的操作系统。从用户观点看分布式操作系统是由一个虚拟单机组成。11.1.2 分布式操作系统的课题l 全局知识(Global knowledge)l 命名(Naming)l 可伸缩性(Scalability)l 兼容性(Compatibility)l 进程同步(Process Synchronization)l 资源管理(Resource Management)l 安全(Security)l 构造(Structuring)全局知识命名可伸缩性兼容性兼容性指的是在一个系统中的资源之间互操作性。在分布式系统中存在三种不同级比级别的兼容性。即二进制级(binary le

4、vel)，执行级(execution level)，协议级(protocol level)。进程同步资源管理分布式系统的资源管理涉及以一种有效的方式给用户使用本地和远程资源。分布式系统的用户应该能够象访问本地资源那样容易地访问远程资源。换句话说，资源的特定位置应该对用户隐藏。分布式系统的资源以下列方法可供用户使用：l 数据迁移(Data migration)l 计算迁移(Computation migration)l 分布式调度(Distributed scheduling)11.1.3 数据迁移过程中数据由分布式操作系统带到计算需要访问它的位置。数据可以是一个本地或远程文件也可以是本地或其它

5、计算机的内存的内容。如果计算修改了数据，原来位置也必须类似地被修改。如果所访问的数据是文件，则所计算的数据访问请求由分布式文件系统权限下处理。分布式文件系统是分布式操作系统的组成成分，它实现对系统中的自治计算机可用的公共文件系统。分布式文件系统的基本目标是提供和分时主机操作系统同样的访问文件的能力，而不管文件在网络中的位置这种性质熟知为网络透明性(network transparency)。如果所访问的数据是在另一台计算机内存中，则所计算的数据访问请求由分布式共享存储管理权限下处理。分布式共享存储提供由分布式系统中所有计算机共享的虚拟地址空间。一个分布式共享存储是共享内存概念在没有物理共享内存

6、的分布式系统中的一种实现。11.1.4 计算迁移在计算迁移情况下，计算迁移到另一位置。迁移的计算在某些情况下可能是有效的。例如，当需要一个远程文件目录有关信息时，比较有效的是发送一个消息（即一个计算）请求必要的信息并接收返回的信息，而非转移整个目录，然后本地找到所需信息。在分布式调度中，一台计算机可能需要另一台计算机的状态（例如，它的负载水平）更有效和安全是在远程计算机上找到这个信息并返回所要求的信息，而不是把远程计算机上操作系统的私有数据结构传输到请求的计算机使之得到所需信息。远程过程调用(Remote procedure call简称RPC)机制已被广泛地用于计算迁移和提供计算机间通信。注

7、意，在计算迁移中，通常仅仅一个进程的计算的一部分被在一个不同的计算机上进行。11.1.5 分布式调度在分布式调度中，进程由分布式操作系统从一台计算机转移到另一台计算机。即一个进程可以在与之原来不同的计算机上执行。如果进程原来计算机超载或者没有进程所要求的必须的资源（例如数学协处理器），进程的重定位可能是值得的。分布式调度负责明智地和透明地在计算机间分布进程，使得整个性能最大。改善性能主要由于通过进程的并发执行增强计算机的利用率。11.1.6 构造l 整个一块内核(Monolithic Kernel)：构造操作系统的传统方法是将它们构造为一个大的整个一块内核。这个内核由操作系统所提供的全部服务组

8、成。但是，在由无盘工作站组成的分布式系统情况下，当不是每个计算机都使用操作系统所提供的每一个服务，对于每个计算机都运行一个巨大的整个一块操作系统似乎是浪费。l 集合的内核(Collective Kernel)：在集合的内核构造中，操作系统服务（例如，分布式内存管理，分布式文件系统，分布式调度，名字服务，RPC，时间管理等）作为独立的进程来实现。操作系统的核心也称为微内核(microkernel)通过消息支持提供系统服务的进程之间的交互。此外，微内核也提供在分布式系统中的每个计算机所典型的实质性的服务。诸如，任务管理（例如任务的本地调度），处理机管理，虚存管理等。微内核运行在分布式系统中的每台计

9、算机上。其余的进程可以或不可以运行在一台计算机上，取决于需要和该台计算机的硬件。集合的内核结构可以容易地使用熟知为“策略与机制分离”的有用的设计技术。在实现中由将策略与机制分离，人们可以改变任何给定的策略而无须改变底层机制。Mach,V-kernel,Chorus及Galaxy都是集合的内核结构的例子。l 面向对象操作系统：操作系统所提供的服务作为对象集合来实现。Eden,Choices,x-kernel,Medusa, Clouds,Amoeba和Muse是面向对象操作系统例子。11.2 理论基础l 分布式系统固有的限制l LAMPORT逻辑时钟l 向量时钟l 消息的因果次序l 全局状态l

10、分布式计算的切割l 终止检测11.2.1 引言一个分布式系统是一个空间上分开的没有共享一个公共内存的计算机集合。在这些计算机上执行的进程彼此通过在通信通道上交换消息来通信。在任意传输延迟后消息被传递到。在这一节中，我们首先讨论由于缺乏一个公共内存和一个可以被所有进程共享的全系统范围的公共时钟所引起的分布式系统固有的限制。然后讨论如何克服这些固有的限制。在这一节中所开展的理论基础是对分布式计算最基础的并且用于全书。11.2.2 分布式系统固有的限制：在这一小节中，我们讨论分布式系统固有的限制以及它们在分布式系统设计和实现上的影响。借助于一个例子的帮助，我们演示由于在分布式系统中限制所遇到的困难。

11、11.2.2.1 缺乏一个全局时钟在一个分布式系统中，不存在系统范围的公共时钟（全局时钟）。换句话说，全局时间的概念不存在。读者可能认为这个问题可以容易地加以解决，或者有一个对在系统中的所有计算机（进程）公共的时钟，或者在每一台计算机上各有一个同步的时钟。不幸地，由于下列原因这两个途径不能解决这个问题。假设有一个对在系统中的所有进程的全局（公共）的时钟，在这种情况下，由于不可预测的消息传递延迟，两个不同的进程可以观察到一个全局时钟值在不同的时刻。因此，两个不同的进程可能不正确地看出在物理时间上两个不同的时刻是在物理时间上一个时刻。另一方面，如果系统中每一个计算机提供一个物理时钟，并且试图同步它

12、们，由于技术限制这些物理时钟可能偏移物理时间以及偏移率可能随时钟而变。因此，这种途径也可能有运行在不同的计算机上的两个不同的进程看出在物理时间上两个不同的时刻是在物理时间上一个时刻。因而，我们不可以有一个完全同步的时钟的系统。缺乏全局时钟的影响。事件的时间定序遍及于我们关于系统的见解，并且被集成到分布式系统的设计和开发之中12。例如，一个操作系统负责调度进程。在调度中所使用的一个基本准则是请求执行进程到达的时间次序（一个请求的到达是一个事件）。由于缺乏全局时钟，在一个分布式系统中很难推断事件的时间次序。因而，和集中式系统的算法相比分布式系统的算法更难设计和诊断。此外，缺乏一个全局时钟使得更难收

13、集整个系统状态上的最新信息。下面将讨论这个缺点的详细描述和分析。11.2.2.2 缺乏共享内存因为在一个分布式系统中的计算机不共享公共内存，整个系统的最新状态不提供给任何个别进程使用。系统的最新状态对推断系统的行为，诊断和从失效中恢复（见第12章）等等是必要的。在分布式系统中的一个进程可以得到系统的一个一致的（coherent）但部分的视图（view），或者一个完全的但非一致的系统的视图13。一个视图被称为一致的，如果不同的进程（计算机）的观察是在同样的物理时间上作出的。一个完全的视图包含在所有计算机上的局部视图（局部状态）和在分布式系统中正在传递中的任何消息。一个完全的视图也被指为一个全局状

14、态。类似地，一个分布式计算的全局状态包含所有进程的局部状态以及进程之间正在传输的任何消息。由于在一个分布式系统中缺乏一个全局时钟，获得系统的一个一致的全局状态是困难的。例6-1设S1和S2分别是一个维护银行帐户A和B的一个分布式系统的两个不同的场点（实体）（见图6-1）。在我们的例子中一个场点指的是一个进程。系统的全局状态知识对于计算这两个帐户净余额可能是必须的。这两个帐户的初始状态如（a）所示。设场点S1从帐户A转移$50到帐户B。在收集一个全局状态期间，如果场点S1在借贷已经出现之后立即记录A的状态，并且场点S2在资金转移消息到达B之前保存了B的状态，则系统的全局状态将表明丢失$50（见图

15、（b）。注意通信信道自身不能记录它的状态。因此，为了记录通道状态，场点不得不协调它们的状态记录活动。另一方面，如果在转移之前立即记录A的状态，并且在帐户B已经记入贷方$50之后记录B的状态，则全局系统状态将表示一个额外的$50（见图（b）。图6-1 两个场点的分布式系统下面我们将介绍在一个分布式系统中给事件定序的虚拟时间的抽象概念的两种实现方式。11.3 LAMPORT逻辑时钟见上册11.3.1 LAMPORT逻辑时钟此外，微内核也提供在分布式系统中的每个计算机所典型的实质性的服务。诸如，任务管理（例如任务的本地调度），处理机管理，虚存管理等。微内核运行在分布式系统中的每台计算机上。其余的进程

16、可以或不可以运行在一台计算机上，取决于需要和该台计算机的硬件。11.3.2 向量时钟向量时钟系统是独立地由Fidge和Mattern提出，在此之前为了恢复目的而追踪进程之间传递依赖关系Strom和Yemini提出了一个类似于向量时钟概念。设n为分布式系统中进程个数，每个进程Pi装配一个时钟Ci，它是一个长度为n的向量。可以把想象为一个函数，赋给任何事件a一个向量Ci(a)。Ci(a)被称为进程Pi的事件a的时间戳。 Ci的第i个分量Cii对应于Pi自己的逻辑时间。 Cij，ji是Pi对Pj逻辑时间最佳猜测。更具体讲，在任何时间点， Ci的第j个分量Cij指示在Pi当前时间点“发生之前HB ”在

17、Pj最近事件出现的时间。这个“发生之前HB ”关系可以由到直接通信或通过其它进程间接通信来建立。向量时钟的实现规则如下：IR1 时钟Ci，在进程Pi的任何两个相继事件之间被增加。Cii:= Cii+d (d>0)IR2如果进程Pi的事件a是发送消息m事件，则消息m被赋予一个向量时间戳tm=Ci(a)；进程Pj接收同样消息m时Cj作如下修改："kCjk:=max(Cjk,tmk)注意，在接收消息时进程可以知道系统中其余进程最当前的时钟值。在规则IR1中我们将进程的消息发送和接收处理为事件。在规则IR2中在发送进程由于IR1已经增加它的时钟之后，消息被赋予一个时间戳。如果必须允许消

18、息传播时间，则IR2可以在完成下列步骤之后被执行。IF Cji tmi then Cji:= tmi+d (d>0) 但是，上述步骤对因果性相关事件并不必要，因此我们不利用它。定理在任何时刻都有"i"j Cii Cji 【证明】显然，由于没有进程PjPi可以有关于进程Pi时钟值更近代的知识，以及时钟是单调非减的。【证毕】【例】假定d=1并且时钟初始值为0。图6-2表示了在一个利用向量时钟的系统中时钟如何前进以及时间如何转播。事件e11是进程P1中初始事件，由IR1引起C11增加到1。e12是进程P1 消息发送事件，由IR1引起C11增加到2。e22是进程P2消息接收事

19、件，由IR1引起C22增加到2，以及由IR2 C21被置成2。 e31是进程P3 消息发送事件，由IR1引起C33增加到1。事件e23是进程P2消息接收事件，由IR1引起C22增加到3，以及由IR2 C23被置成1。e24是进程P2 消息发送事件， e13是相应的消息接收事件。注意，由IR2 C13被置成1，通过从P2来的消息进程P1已经知道P3本地时钟值至少为1。图6-2 向量时钟例子向量时间戳可以作如下比较：l 相等 ta =tb iff "i tai = tbi l 不相等 tatb iff $i tai tbi l 小于等于tatb iff "i taitbi l

20、不小于等于ta£tb iff $i tai>tbi l 小于 ta < tb iff (tatb tatb)l 不小于 ta < tb iff (tatb tatb)l 并发 ta | tb iff (ta< tb tb <ta)注意，关系是偏序的。但是，关系|不是偏序的，因为它是非传递的。上述步骤对因果性相关事件并不必要，因此我们不利用它。如果事件a和b满足ta < tb或tb < ta，则它们是因果相关的，否则它们是并发的。在向量时钟系统中 ab iff ta < tb因此，向量时钟系统允许我们给事件定序，以及决定两个事件是否因果相

21、关只要简单地看事件的时间戳。11.3.3 消息的因果次序消息的因果次序首先由Birman 和Joseph提出并在ISIS中实现。消息的因果次序处理维持在消息发送事件与相应的消息接收事件之间所持有的同样因果关系的概念。换句话说，如果Send(M1)Send(M2)，则必须在接收到消息M2之前接收到消息M1。其中Send(M)表示发送消息M的事件。不应该把消息的因果次序和事件的因果次序相混淆，后者是处理事件之间的因果关系。在分布式系统中并不自动地保证消息的因果次序。例如，如图6-3所示，表明了违反了消息的因果次序的例子。在此例子中Send(M1)Send(M2)。但是，在之前发送给进程P3。正确的

22、因果次序为带圈数字。消息的因果次序技术对开发分布式算法有用，它可以简化算法。例如，对于诸如复制数据库系统的应用，每个负责更新副本的进程以维护数据库一致性同样的次序来接收更新是很重要的。在缺少消息的因果次序时，每个更新必须检查以保证不违反一致性约束。图6-3 消息的因果次序11.3.4 两个协议两个协议的基本思想是仅当此消息的直接前面消息已经被传送到进程才将消息传递到该进程，否则将此消息缓冲直到其前一个消息被传送到。每个消息盘伴随一个向量含有对一个进程决定是否存在前一个消息所必须的信息。l BIRMAN-SCHIPER-STEPHENSON协议在广播一个消息m之前进程Pi增加向量时间VTPii和

23、时间戳m。注意， VTPii-1指示在m之前从Pi发了多少消息。从Pi接收到带有时间戳VTm消息m的进程PjPi推迟它的传递，直到下列两个条件都满足： VTPji = VTmi - 1 VTPjk VTmi "k 1,2,.,n - i其中n是全部进程个数。延迟的消息在每个进程中按照消息的向量时间整序地排在队列中。并发的消息由它们的接收时间定序。当进程Pj传递一个消息，按照规则IR2 ， VTPj被修改。步骤是协议的关键。保证进程Pj已接收到从Pi来的m之前的所有消息。保证进程Pj已接收到在发送m之前由Pi所接收到的所有消息。因为由向量时钟所施加的事件定序关系是非循环的，所以该协议是

24、无死锁的。l SCHIPER-EGGLI-SANDOZ协议数据结构和记号每个进程P保持一个(N-1)个分量的向量，记为V_P，其中N是系统中进程数。 V_P的一个元素是一个有序对偶(P,t)其中P是一个消息的目的地进程的标识，t是一个向量时间戳。假定系统的进程利用向量时钟。通信通道可以是非FIFO。tM为发送消息M时的逻辑时间tPi为进程Pi的当前逻辑时间协议从进程P1发送一个消息M到进程P2l 发送时间戳为tM的消息M以及V_P1给P2。l 把对偶(P2,tM)嵌入到V_P1中。如果V_P1包含一个对偶(P2,t)简单地用新的(P2,tM)覆盖之。注意，对偶(P2,tM)不送给P2。任何携带

25、对偶(P2,tM)的进一步消息直到tM < tP2才可以传递给P2。消息M到达进程P2if伴随消息M的向量V_M不包含任何对偶(P2,t)， then消息可以被传递 else (*在V_M中包含对偶(P2,t) *) if t < tP2 then 不可以传递该消息(被缓冲以便稍后传递) else可以传递该消息如果消息M可以被传递到P2，则必须采取下列三个行动：以下列方式把与M伴随的V_M和V_P2合并：l if ($(P,t) V_M使得PP2)("P P (P,t) V_P2) then 把(P,t)嵌入到V_P2中。这个规则执行如下：如果在V_P2中没有进程P的条目

26、并且V_M包含进程P的一个条目，则把这个条目嵌入到V_P2中。l if ("P P2 (P,t) V_M) (P,t) V_P2) then (P,t) V_P2可以被(P,tsup)替换，其中tsup使得"itsup i = max(ti,ti) 。这个规则简单地对V_P2中每一项执行步骤IR2 。由于上述两个动作，算法满足下列两个条件：只要t<tp不为真就无消息可以被传递给P。只要t<tp不为真就无消息可以被传递给P。修改场点P2的逻辑时钟。检查自本地时钟已被修改以来现在可以被传递的缓冲的消息。对偶(P,t)在保证已经变成废弃即不再需要之后，可以从场点所维护

27、的向量中删除。11.3.5 局部状态对于一个场点（计算机）Si它在给定时间的局部状态定义为分布式应用的局部上下文(local context)。记 LSi为Si在任意时间的局部状态。令send(mij)表示由Si发送消息mij给Sj的发送事件。rec(mij)表示由场点Sj接收消息mij的接收事件。time(x)表示记录状态x的时间。time(send(m)表示出现事件send(m)的时间。对由Si发送给Sj的消息mij我们有send(mij) LSi iff time(send(mij) < time(LSi)rec(mij) LSj iff time(rec(mij) < ti

28、me(LSj)对于任何两个场点Si和Sj的局部状态LSi和LSj，我们定义如下两个包含从场点Si发送给场点Sj消息集合：transit(LSi, LSj) = mij | send(mij) LSi rec(mij)Ï LSj inconsistent (LSi, LSj) = mij | send(mij) Ï LSi rec(mij) LSj 11.3.6 全局状态定义一个系统的全局状态GS是一个它的所有场点的局部状态集合；即GS = LS1, LS2, ., LSn其中n是系统中场点的个数。定义一个全局状态GS = LS1, LS2, ., LSn是一致的(consistent)当且仅当"1£ i£ n"1£j£ n (inconsistent(LSi, LSj) = )因此，在一个一致的全局状态中，对于每个接收消息，一个相应的发送事