分布式操作系统2325课件

2.3命名服务

2.3.1概述（名字、属性、名字服务系统、名字服务的要求）2.3.2一般的命名方式2.3.3分布式系统中的命名方式2.3.4名字服务器的设计12.3命名服务

2.3.1概述（名字、属性、名字服务系统2.3命名服务

2.3.1概述

在一个分布式系统中，名字可用于指称或索引各种类型的资源，包括计算机、服务、端口、个体对象以及用户。分布式系统中资源的共享与通信需要名字；用户(客户)请求计算机操作诸多资源中的某特定的对象时需要使用名字；进程之间不能共享由计算机系统管理的资源，除非它们能协调一致地对资源进行命名；用户之间也不能通过分布式系统相互通信，除非他们能对其他用户进行命名。22.3命名服务

2.3.1概述

在一个分布式系统中，名字可用一、名字与属性

名字，统称为名称(name)人们可读的文本名，便于人们识别和记忆系统标识符，软件用来对资源进行解释和存储的名字形式，是一个定长的位串下面是几种名称：物理网址和逻辑网址：这类名称可视为名字的位置或地址端口、进程和组标识符：这类名称可视为消息的目的地资源标识符：由服务器和内核管理的资源的低层独立定位的标识符文件：使用人们可读的文本名字进行存取的信息集3一、名字与属性

名字，统称为名称(name)3一、名字与属性（续）

客户用文本名对资源的操作过程(Amoeda)存取一个资源涉及到将其文件名映射成对应的资源标识符，再将该资源标识符映射成一个端口标识符和一个特定服务的标识符；然后将这个端口标识符映射成一个网络地址，将这个特定服务的标识符映射到相关服务器中的资源。4一、名字与属性（续）

客户用文本名对资源的操作过程(Amoe一、名字与属性（续）

分布式系统中使用的许多名称都是有特定含义的，客户(用户或进程)使用这样的名称请求服务系统对它管辖的命名对象和资源进行操作。若系统管理很多对象，那么每个对象都得命名，考虑到效率，这个名称应能直接映射它所代表的对象。例如，当要求删除一个文件时，该文件的名称就被传递给文件服务系统；请求向一个进程发信号时，该进程的标识符被提供给进程管理系统。这样一些名称仅用在管理这些命名对象的服务系统的上下文(共享对象除外)中。

5一、名字与属性（续）

分布式系统中使用的许多名称都是有特定一、名字与属性（续）

引用超出任何单一服务系统范围的实体时，也要命名。典型例子包括：用户(带有专用名、逻辑名、用户标识符和电子邮件地址等)计算机(带有名字—宿主名，如mac41)服务系统本身(如文件服务、打印服务等)。所有这些名称必须是有意义的、可读的因为用户和系统管理员需要通过这些名称访问分布式系统的主要组件和配置，程序员在编程过程中需要这些名称去访问相应的服务(系统)，用户借助它们进行通信。考虑到Internet提供的连接能力，这些命名要求在范围上应该是全球的。6一、名字与属性（续）

引用超出任何单一服务系统范围的实体时一、名字与属性（续）

名称和对象之间的联结称为联编(binding)。特定服务名被服务系统联编到相关对象或资源的实际表示上用户名、计算机名和服务(系统)名被联编到命名对象的属性上，所有这些对象都把地址作为属性之一。一般而言，属性值或是基本值，如整数；或是自身的名称，如Internet地址12等。最终，所有的名称被简化成基本值或不能再进一步“查找”的基本名。与名称相关的属性不仅对用户而且对其他服务都是有用的。例如，在电子邮件系统中，Internet域名系统(DNS)用来从电子邮件地址中查找邮件主机地址，但由另外的软件来传递和存储邮件消息。7一、名字与属性（续）

名称和对象之间的联结称为联编(bin二、名字服务系统

名字服务系统管理着一个联编数据库，其中存储着文本名(可读的)及其相关的属性。其支持的操作有：解析一个名字——在该数据库中查找给定名字的相关属性；为新名字生成新的联编；删除联编；列出已联编的名字等操作。注意：虽然把联编集看作一个数据库，但一般说来名字不是简单键，常常由若干部分组成(例如，he@)，这些部分需在数据库的不同区域中分别查找，这些不同区域即上下文(context)。8二、名字服务系统

名字服务系统管理着一个联编数据库，其中存储二、名字服务系统（续）

名字管理从其他服务中独立出来的原因：很大程度上是因为分布式系统的开放性；一致性(unification)：让不同的服务器或服务系统管理的资源出现在同一命名方案中似乎比较方便的。例如在UNlX中的NFS中，一些文件在本地磁盘上管理，而另一些则在远程服务器上，所有的文件出现在单一的名字空间层次结构中。此外，一些“文件”的名字涉及到本地设备或命名过的管道。……9二、名字服务系统（续）

名字管理从其他服务中独立出来的原因二、名字服务系统（续）

……集成(integration)：在分布式系统中，不一定总能预测共享的范围。有时候，需要共享和命名在不同管理域中创建的资源，这可能会引起问题，例如，合并两个用户集，分配给每个用户的登录名可能会发生冲突。更坏的情况是，这两组用户可能有完全不同的命名规则。10二、名字服务系统（续）

……10三、名字服务的一般要求

名字服务越来越复杂。几个例子：Grapevine：最早的可扩充多域名字服务系统之一GlobalNameService：DEC系统研究中心开发的全球名字服务，是Grapevine的下一代，目标为：处理任意数量的名字并为任意数量的管理组织服务：例如，该系统应能处理世界上所有计算机用户的E-mail地址。11三、名字服务的一般要求

名字服务越来越复杂。11三、名字服务的一般要求（续）……长生命期：在其生命期中，名字空间的组织和实现名字服务的一些组件将会发生许多变化。高可靠性：绝大多数服务系统依赖于名字服务系统，一旦它崩溃了，其他服务系统就无法工作。故障隔离：局部故障不会导致整个名字服务系统失效。容忍怀疑：在一个较大的开放系统中，不存在所有客户都信赖的组件。DNS：Internet域命名系统(DNS)使用得非常广泛，它命名Internet上的对象(用户和计算机)。12三、名字服务的一般要求（续）……122.3.2一般的命名方式

在计算机系统中，每个对象一般有两个名字：由用户识别的文本名(符号名)由系统使用的内部名内部名可以是该对象的实际位置，也可以是查询该对象的地址的一种表示形式。通过某种映射，系统可把用户定义的符号名转换成相应的内部名。名字和对象之间的关系：同一对象可能有多个名字；同一名字也可用来代表不同的对象(在不同的作用域内)132.3.2一般的命名方式

在计算机系统中，每个对象一般有两个2.3.2一般的命名方式（续）

A、B各有三个文件，其目录包含了每个文件的文件名及指向对应文件在磁盘上地址的指针。这里，相同的文件名可用来指称不同的文件。例如，两个目录中都含有s.pas，但它却代表两个不同的文件。不同的文件名也可以指称同一个文件。例如，A目录中的test.dat和B目录中的old.dat两者的指针都指向“文件1”。142.3.2一般的命名方式（续）

A、B各有三个文件，其目录包2.3.2一般的命名方式（续）

由于系统可以有多个用户，因此，目录常常组织成层次结构。文件名的含义：不仅指文件名本身而且也应包括它与根之间所有目录的名字(路径名)。一个例子：tset.dat文件的完全路径名是root:A:test.dat。152.3.2一般的命名方式（续）

由于系统可以有多个用户，因2.3.2一般的命名方式（续）

大多数系统允许用户设置一个默认目录或当前目录，此时用户不必写出完全路径名。一个例子：假定A设置它的默认目录为root:A，当用户使用文件名my.c时，操作系统就自动地把默认目录名作为my.c的前缀，形成完全路径名root:A:my.c。162.3.2一般的命名方式（续）

大多数系统允许用户设置一个2.3.3分布式系统中的命名方式

分布式系统中的命名更复杂：由于分布式环境中的名字可用来指称不同场点或不同场点的不同层次结构上的对象，因此与单机系统相比，其命名和名字的映射工作更加复杂。以下讨论分布式环境下的名字管理器的主要功能命名方案标识符和字符串名172.3.3分布式系统中的命名方式

分布式系统中的命名更复杂：一、名字管理器的主要功能

DOS中名字管理部分的功能：通过管理名字在系统的地址去定位命名过的对象；创建、删除、改变对象的名字；改变对象的位置，以支持对象在系统中的迁移；利用对象名字来支持对象的共享；创建一个对象组；……18一、名字管理器的主要功能

DOS中名字管理部分的功能：18一、名字管理器的主要功能（续）……从组中删除成员或将成员加入其中；枚举组中的成员；测试组中成员之间的关系；借助组名共享资源或共享服务程序；支持对象组的递归结构；完成外部名(符号名)到内部名(系统名)的映射工作。19一、名字管理器的主要功能（续）……19二、分布式系统中的命名方案

分布式系统中常用的命名方案有绝对命名、相对命名和层次式命名三种。由绝对命名方案命名的名字是全系统范围唯一的、无二义性的。在机内，这类名字通常是由时钟或计数器之值产生的位串。由相对命名方案命名的名字依赖于使用它的上下文。对于不同的使用者，一个对象的名字可以是不同的，或者说，一个对象的名字不唯一。20二、分布式系统中的命名方案

分布式系统中常用的命名方案有绝对二、分布式系统中的命名方案（续）

层次式命名方案用如下方式组织系统中的对象名：对象被分划成若干组；每组给定全局唯一的组名；每组中的每个对象在组内给定唯一的名字；一个组中对象名还可按此方式进一步分划成若干子组。21二、分布式系统中的命名方案（续）

层次式命名方案用如下方式二、分布式系统中的命名方案-实例1

VMS的命名体系：层次式，完全路径名由一个设备名接任何个数的目录名再接文件名和扩展文件名构成。图2-22展示了VMS中两个设备Userdisk和Sysdisk的目录结构。Userdisk有两个目录dirl和dir2。文件letter.dom的完全路径名是Userdisk:[dir2.me]letter.dom.22二、分布式系统中的命名方案-实例1

VMS的命名体系：层次式二、分布式系统中的命名方案-实例2

DEC网命名方式：把类似VMS的命名体系再向上扩充一层，使之包含场点名，如图2-23所示。远程场点上的文件可通过把该场点名加在相应文件的路径名之首来进行访问。例如，在sitel上的文件letter.dom的完全路径名现在为sitel::userdisk:[dir2.me]letter.dom.23二、分布式系统中的命名方案-实例2

DEC网命名方式：把类似二、分布式系统中的命名方案-实例2（续）

DEC网命名方案中，场点名必须唯一，且每个场点必须知道系统中所有其他场点的名字。这种方案容易实现，用户也比较容易掌握。但存在下面的问题：由于文件的位置事实上已作为文件名的一部分，那么当一文件从一场点迁移到另一场点时，意味着该文件的名字也必须改变，从而导致凡涉及到访问该文件名的所有操作也不得不作相应的修改。若一文件有多个副本且位于不同的场点上，它们就会有不同的名字，那么对它们的任何更改都容易导致不一致性。系统的某些细节(如场点)对用户是可见的。一般说来，这是分布式系统的设计者所不希望的。24二、分布式系统中的命名方案-实例2（续）

DEC网命名方案中二、分布式系统中的命名方案-设计原则

设计命名方案的一个基本观点：名字是依赖于位置还是独立于位置。这也可以说是性能对灵活性的问题。在不依赖于位置的命名方案中，对象的名字不含其在系统中的位置。这使得可对系统中的远程或本地资源(对象)进行一致的存取。但在依赖于位置的命名方案中，就可能出现像DEC网命名方案的问题。移动文件要注意改名，后续操作也要注意名字问题多副本情况一致性的维护问题透明性的问题25二、分布式系统中的命名方案-设计原则

设计命名方案的一个基本三、唯一标识符和字符串名

UID系统中的每一对象给定一个唯一的标识符(UID)，即在系统中，它唯一地指称该对象。一个对象的UID在其整个生命期内决不改变。特别，当一对象从一场点迁移到另一场点时其UID仍保持不变。一个UID是相关对象的绝对名字，它通常是利用系统时钟产生的。UID也可作为一种权限使用，此时，与其相关的对象是受保护的，它既不能由用户改变，也不应被用户忘却。为了使UID在全系统范围内唯一，也可以将局部宿主ID作为它的一部分。此外，它还可含有一些随机生成的位，使得它难以猜测，从而起到保密作用。26三、唯一标识符和字符串名

UID26三、唯一标识符和字符串名（续）

字符串名(简称串名)具有如下特征：同一串名可由不同的用户用来访问不同的对象；不同的串名可由(不同的)用户用来访问相同的对象；对象可以在场点间迁移不必改变其串名。27三、唯一标识符和字符串名（续）

字符串名(简称串名)具有如下三、唯一标识符和字符串名（续）-总结

在大多数系统中，字符串名主要供用户使用，而UID仅供操作系统使用。UID通常是定长、压缩形式的(一般有64~128位)，这就有利于系统级的构造、使用和管理；字符串名一般较长且往往是可变长的(如10-100字节)，这对用户是方便的，但不太适合在系统级使用。操作系统提供了从字符串名到UID的映射。28三、唯一标识符和字符串名（续）-总结

在大多数系统中，字符串2.3.4名字服务器的设计

名字服务器(nameserver)的主要功能：将一个符号串名(一个整数串名或字符串名)映射成系统内唯一的物理地址。名字服务器管理着包含有“名字及其物理地址”的对照表，系统中的所有服务程序都由名字服务器来寻址和定位。例子：292.3.4名字服务器的设计

名字服务器(nameserve2.3.4名字服务器的设计（续）剑桥大学设计CDCS中的服务程序族利用其名字服务器来寻址和定位。为了引用一个服务程序，client将代表某个服务程序名字的一个ASCII串发送给名字服务器，名字服务器收到这一信息后，就查看该串是否在其管理的表中。若在，它就返回所指服务程序的所在处理机编号、用于编址它的端口和相应的协议等。在CDCS中，名字服务器本身的地址是固定的，系统提供了向名字服务器管理的表中添加或从中删除信息的命令。不过，出于保护原因，这类命令只能由系统管理人员使用。302.3.4名字服务器的设计（续）剑桥大学设计CDCS中的服务2.3.4名字服务器的设计（续）设计名字服务器一般有中央方式、复制方式和分划方式三种途径。用中央方式设计时，全系统仅有一个(中央)名字服务器，系统中的所有服务程序都由它来寻址和定位。但由于性能及可靠性方面的原因，这种方式不常采用。用复制方式时，每个场点都有一个名字服务器的副本，用以管理该场点上的所有服务程序及本场点与其他场点间相互请求的服务信息。312.3.4名字服务器的设计（续）设计名字服务器一般有中央方式2.3.4名字服务器的设计（续）分划方式意指：若系统由若干子系统(子网)组成，则对于每个子系统，用一个名字服务器管理本子系统上的所有服务程序及本子系统与其他子系统相互请求的服务信息；或者若系统的名字空间可根据某种方式来分划，则对于每个经这样分划后的实体，用单独的或复制式的名字服务器管理；或者将名字空间组织成层次结构来管理。322.3.4名字服务器的设计（续）分划方式意指：322.4DOS中的同步

分布式系统中的进程通信消息传递（Send、Receive、Replay等原语）RPC组通信这并不是分布式系统的全部内容。与此紧密相关的是进程之间如何协作及如何彼此同步。比如说，在分布式系统中临界区如何实现，资源如何分配。332.4DOS中的同步

分布式系统中的进程通信332.4DOS中的同步（续）

在单CPU系统中，临界区、互斥和其它同步问题经常使用信号量、管程等方法来解决，这些方法在分布式系统中并不十分适用，因为它们依赖于共享存储器的存在。比如，有两个进程通过使用信号量而相互作用，它们必须都能访问信号量。如果它们在同一台机器上运行，能够共享内核中的信号量，并通过执行系统调用访问它。如果它们运行在不同机器上，这种方法就不适用了，而需要其它技术。甚至看似简单的问题，比如判断事件A在事件B之前还是之后发生的问题也需要认真考虑。342.4DOS中的同步（续）

在单CPU系统中，临界区、互斥2.4DOS中的同步（续）

2.4分布式操作系统中的同步2.4.1时钟同步问题提出逻辑时钟与事件定序时间戳时钟同步算法2.4.2互斥集中式算法、分布式算法、令牌环算法、选举算法352.4DOS中的同步（续）

2.4分布式操作系统中的同步2.4.1时钟同步

集中式系统的同步算法：在某地收集系统的所有有关信息，然后让某个进程分析并做出决定。在DOS中的分布式算法有如下性质：相关信息分散在多台机器中；进程决策仅仅依赖于本地信息；系统中单点故障应该避免；没有公用时钟或其它精确的全局时间资源存在。前三点都说明在一处收集所有信息并对它进行处理是不可接受的。比如，资源分配（以一种无死锁的的方式分配）向单一的管理进程发送所有I/O请求，由它来检查它们，根据表中的信息准予或拒绝请求是不实际的。在大系统中，这种解决方法会给某个进程带来太重的负担。362.4.1时钟同步

集中式系统的同步算法：在某地收集系统的2.4.1时钟同步

进一步而言，一个单点故障会造成系统不可靠。最理想的情况是，一个分布式系统应该比单机系统更可靠，一台机器崩溃不影响其它机器的继续运行，不通过集中而获得同步所使用的方法应该与传统操作系统所用的方法不同。上述的最后一点是十分关键的，在集中式系统中时间的概念很清楚，当进程想知道时间时，它使用系统调用，由内核提供。如果进程A询问时间，之后进程B也询问时间，B得到的时间值就应该大于或等于A所得到的时间值，但一定不会小于A得到的时间值。在分布式系统中，获得时间上的一致是并不容易。372.4.1时钟同步

进一步而言，一个单点故障会造成系统不可一个简单的例子：在缺少全局时间时的UNIX下的make程序---DOS中很难获得时间上的一致UNIX系统中一个大程序通常可被分割成多个源文件，如果某个源文件发生变化，只需将该文件重新编译即可，而不需要对所有的文件进行重编译。Make程序所使用的方法：当编程者修改完所有的源文件，他启动make程序，看一下源文件和目标文件最后一次修改的时间，如果源文件INPUT.C时间为2151，而相应的目标文件INPUT.O时间为2150，make就知道INPUT.C在INPUT.O创建后被改动过。因此，INPUT.C必须重新编译。相反，若INPUT.C时间为2144，而INPUT.O时间为2145，就不必再重编译了。make检查所有的源文件并找出哪一个需要重编译，调用编译器重新编译它。38一个简单的例子：在缺少全局时间时的UNIX下的make程序-一个简单的例子：在缺少全局时间时的UNIX下的make程序---DOS中很难获得时间上的一致（续）在没有统一时间的分布式系统中：假设OUTPUT.O的时间为2144，紧随其后OUTPUT.C被修改，但是由于它所在机器上的时钟略慢，造成OUTPUT.C时间为2143，如图2-24所示。make将不再调用编译器，最终可执行的二进制程序将包括由老的源文件和新的源文件所产生的混合目标文件，这样可能将不能再正常执行。39一个简单的例子：在缺少全局时间时的UNIX下的make程序-一、问题提出所有的计算机都有一个计时电路（计时器），通常是由一个精确的石英晶体制成，当其在张力限度内时，石英晶体以一定的频率振荡。与每个晶体相关的是两个寄存器、一个计数器和一个保持寄存器。每次振荡时使计数器减1，当计数器减为0时，产生一次中断，计数器重新从保持寄存器中装入起始值，通过这种方法可以编程使得一个计时器每秒能产生60次中断或以其它希望的频率产生中断成为可能，每次中断称作一个时钟点（clocktick）。当系统刚启动时，总是要求操作者输入日期和时间，然后将它们转换成某一已知起始时间后的时钟值，并将它存储在存储器中，在每个时钟点时，中断服务程序将此值加1，用这种方法进行（软）时钟计时。40一、问题提出所有的计算机都有一个计时电路（计时器），通常是由一、问题提出（续）在单机单时钟中，如果时钟被瞬间关闭其问题不会太大，因为这台机器上所有进程使用同一时钟，它们仍将内在地保持一致。比如，文件INPUT.C时间为2151，文件INPUT.O时间为2150，make将重新编译源文件，假设时钟关闭的时间为2，真正的时间则分别为2153和2152，有用的只是相对时间。41一、问题提出（续）在单机单时钟中，如果时钟被瞬间关闭其问题不一、问题提出（续）多CPU系统中，每个CPU将拥有自己的时钟，情况发生变化。尽管每个晶体振荡频率总是相当稳定，但保证不同计算机上的晶体以完全相同的频率振荡是不太现实的。实际上，当系统有N台计算机时，所有N个晶体将以略微不同的速度振荡，导致（软）时钟逐渐不同步，当同时读这些时钟时，也会得到不同的值。这种在时间值上的不同称作时钟偏移（clockskew）。一个程序期望与文件、目标文件、进程或消息相联系的时间应是正确的，且与产生它们的机器（即使用哪个时钟）无关。42一、问题提出（续）多CPU系统中，每个CPU将拥有自己的时钟一、问题提出（续）问题：同步所有时钟产生一个单一的、无二义的时间标准是否可能。解决：Lamport（1978）阐明了时钟同步是可能的，并且描述了实现的算法，他还继续对这个问题进行了一些研究（Lamport1990）。43一、问题提出（续）问题：同步所有时钟产生一个单一的、无二义的二、逻辑时钟与事件定序

Lamport的观点：时钟同步不需要绝对同步。如果两个进程无相互作用，它们的时钟无须同步，因为即使缺少同步也觉察不出来，不会产生什么问题。通常并不必需所有进程在时间上完全一致，而是它们在事件发生的顺序要上完全一致。在上述make程序的例子中，计时目的在于说明INPUT.C比INPUT.O早或晚产生，而并不是它们各自产生的绝对时间。44二、逻辑时钟与事件定序

Lamport的观点：44二、逻辑时钟与事件定序（续）

如有特殊限制，不仅时钟要完全一致，而且不能与真实时间有一点点的误差，这种时钟称作物理时钟(physicalclocks)，本节将讨论Lamport算法，它用逻辑时钟进行同步。45二、逻辑时钟与事件定序（续）

如有特殊限制，不仅时钟要完全二、逻辑时钟与事件定序（续）

Lamport为同步逻辑时钟定义了“先发生”关系：表达式A→B读做“A在B之前发生”，意思是所有进程认为先发生事件A，接着发生事件B，这种关系有如下两种情况：如果A和B是在同一进程中的两个事件，且A发生在B之前，则A→B为真。如果A是一个进程发送消息的事件，B为另一个进程接收这一消息的事件，则A→B为真，消息不能在发送之前接收，也不能在发送的同时接收，因为传送过程还需要一定时间。先发生是一个传递关系，即，若A→B且B→C则A→C。“先发生”也称为前趋关系（happen-beforerelation）如果两个事件X和Y，出现在不同进程中，但并不交换消息（甚至不由第三方间接交换），则X→Y为假，Y→X也为假。则事件X和Y称为并发事件，即它们之间不存在谁先谁后的问题。46二、逻辑时钟与事件定序（续）

Lamport为同步逻辑时二、逻辑时钟与事件定序（续）

水平方向表示空间(不同的进程)，垂直方向表示时间。设A、B为任意两个事件，当且仅当在图中不存在从A到B或从B到A的一条路径时，事件A与事件B是并发的。一些存在前趋关系的事件是：p1→q2，r0→q4，q3→rl，p1→q4。并发事件是：q0和p2，r0和q3，r0和p3，q3和p3。无法知道两个并发事件(例如q0和p2)哪一个先发生。既然这两个事件没有一个影响另一个，因此哪一个先发生并不重要。47二、逻辑时钟与事件定序（续）

水平方向表示空间(不同的进程三、时间戳

需要一种测量时间的方法，使得对每一事件a，在所有进程中都认可给它分配一个时间值C(a），即打上时间戳，这些时间值必须有如下性质：若A→B则C(A)<C(B)。若a和b是同一进程中的两个事件，且a→b，则C(a)<C(b)同理，若a是一个进程发送消息的事件，b为另一个进程接收消息的事件，那么C(a)<C(b)。时钟时间值C必须向前走（递增），不能倒退（减少）。校正时间的操作是给时间加上一个正值，而不是减一个正数。48三、时间戳

需要一种测量时间的方法，使得对每一事件a，在所有三、时间戳—Lamport算法怎么给事件分配时间

各进程运行在不同的机器上，每个机器都有自己的时钟，以各自不同的速率工作。进程0的时钟滴答（tick）了6下时，进程1的时钟滴答了8下，进程2的时钟滴答了10下。在时刻6，进程0把A消息发送到进程1，消息到达的时间取决于你信任哪一个时钟，不管怎样，当它到达时，进程1读到的时刻是16，若消息自身携带的起始时刻是6，进程1会推算到它需滴答10下才到达，这个值是可能的。依次类推，消息B从进程1到进程2需要滴答16下这也是可能的。问题：消息C从进程2到进程1是在60时刻离开，56时刻到达。同理，消息D从进程1到进程0是在64时刻离开，54时刻到达，这是绝对不可能出现的，必须防止这种情况的出现。49三、时间戳—Lamport算法怎么给事件分配时间各进程运行三、时间戳—Lamport算法怎么给事件分配时间（续）Lamport的解决方案：直接使用先发生关系，因为C在60时刻离开，它只能在61时刻或更晚时刻到达所以每条消息都携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟若比消息发送时钟小，就立即将自己的时钟调到比发送时间大1或更多的值。在图b中，C现在到达的时间是61。同样D到达的时间是70。50三、时间戳—Lamport算法怎么给事件分配时间（续）Lam三、时间戳—Lamport算法怎么给事件分配时间（续）为适应全局统一时间的需要，只需对此作一点补充即可，即在每两个事件之间，时钟必须至少滴答一下，如果一个进程以相当快的速度连续发送或接收两条消息，它必须在这中间至少滴答一下。在某些情况下需要一个附加条件：两个事件不会精确地同时发生，为了实现这个目标，我们可以将事件所在的进程号附加在事件发生时间的低位，并用小数点分开。这样，如果在进程1和进程2中同时发生了2个事件，发生时刻都是40，则前者记为40.1，后者记为40.2。51三、时间戳—Lamport算法怎么给事件分配时间（续）为适应三、时间戳-Lamport算法怎么给事件分配时间（续）使用这种方法，分布式系统中将时间分配给所有事件的方法遵照如下规则：若在同一进程中a发生在b之前，则C(a)<C(b)；若a和b分别代表发送消息和接收消息，则C(a)<C(b)；对所有事件a和b，C(a)≠C(b)这个算法给我们提供了对系统中所有的事件进行排序的一种方法，许多其它的分布式算法也需要这种排序以避免混乱。52三、时间戳-Lamport算法怎么给事件分配时间（续）使用这四、时钟同步算法所有算法都有相同的系统基础模型：每台机器上假设都有一个每秒产生H次中断的计时器。当时间到时，中断处理程序将软时钟加1，软时钟记录从过去某一约定值开始的中断次数。我们把这个时钟值记为C。更特殊的，当UTC时间为t时，在机器p上的时间值是Cp(t)，最完美的情况是对所有的p和t，有Cp(t)=t，换言之，dC/dt理想值为1。

UTC：世界协调时间(UniversalTimeCoordinated)。GPS系统中有两种时间区分，一为UTC，另一为LT（地方时）。两者的区别为时区不同，UTC就是0时区的时间，地方时为本地时间。53四、时钟同步算法所有算法都有相同的系统基础模型：53四、时钟同步算法（续）真正计时器并不是每秒精确的中断H次，理论上当H=60时，计时器每小时应该产生216,000个滴答。实际上，用现代计时时钟芯片可以获得相关的延迟是10-5，意味着一台机器每小时可以获得215,998～216,002范围的滴答，若存在某一常数ρ，便有：54四、时钟同步算法（续）真正计时器并不是每秒精确的中断H次，理四、时钟同步算法（续）计时器可以在它规定的范围内工作，制造商标明的常数ρ是最大漂移速度。稍慢的、精确的、稍快的时钟如图2-27所示。55四、时钟同步算法（续）计时器可以在它规定的范围内工作，制造商四、时钟同步算法（续）若两个时钟相对于UTC时间以相反方向漂移，在它们同步后的Δt时间内，它们可能的差值为2ρΔt，若操作系统的设计者要保证每两个时钟之间的相差不超过δ，时钟必须至少在每δ/(2ρ)秒内再同步一次（用软件方法），不同算法实现再同步的方法不同。56四、时钟同步算法（续）若两个时钟相对于UTC时间以相反方向漂1.Cristian算法

非常适合于只有一台机器上有WWV接收器，其它所有机器与它同步的系统。把拥有WWV接受器的那台机器称作时间服务器，算法是基于Cristian(1989)和以前的一些工作。每台机器以小于或等于δ/(2ρ)秒的周期定期地向时间服务器发送消息询问当前的时间，时间服务器接到消息后就尽快回答含有当前时间CUTC值的消息，如图2-28所示。

571.Cristian算法

非常适合于只有一台机器上有WWV接1.Cristian算法（续）

当发送者得到回答后，就将它的时钟设为CUTC，但是这种算法有两个问题：第一个重要的问题是时间决不能倒退，若发送者的时钟快，CUTC将会比发送者的时间值C小，若把发送者的时间值直接改成CUTC会导致严重的错误，比如在时钟变化后，编译产生的目标文件的时间早于时钟变化前源文件的修改时间。这种变化必须逐步进行，一种方法是假设将计时器设置为每秒产生100次中断，通常，每次中断将时间加10毫秒，当时钟需要慢下来时，中断服务程序每次仅加9毫秒，直到调整好为止。同样时钟要加快时，每次中断服务程序将时钟加11毫秒，而不是立即把时间调到所需要的值。581.Cristian算法（续）

当发送者得到回答后，就将它1.Cristian算法（续）

另一个小问题是从时间服务器端发送的应答到发送者要花费时间，这种延迟可能较大，而且随着网络负荷的改变而改变。Cristian的处理方法是试图测量这个延迟值。最简单的方法：发送者精确地记录从向时间服务器发送请求到接收到应答的时间间隔，假设起始时间是T0与结束时间T1，他们都是通过同一个时钟来测量的，就算发送者的时钟与UTC有一定的差值，它所测得的时间间隔还是较精确的。在没有其它任何信息时，消息传送时间的最佳估计值是（T1-T0）/2，当应答消息到达时，消息中的时间值再加上此值就得到了当前时间服务器的时间估计值，如果理论上知道了最小的传送时间，那么与时间估算相关的其它性质也能推算出来。591.Cristian算法（续）

另一个小问题是从时间服务器1.Cristian算法（续）

如果知道时间服务器中断处理的时间和处理消息的时间，这样的估算还能进一步改进，设中断处理的时间是I，那么传输时间间隔为T1-T0-I，所以估算单向传输时间为它的一半。系统中确实存在着从A到B的消息和从B到A的消息传输路径不同，因此就有不同的传输时间，但我们目前先不考虑这种情况。为了提高精确度，Cristian建议不要只做一次测量，而做一系列测量，测量中T1-T0超出一定范围就认为是网络阻塞，为不可信值。对剩余的测量值取平均值会得到较好的估算值，也就是说，最快返回的消息是最精确的，因为消息遇到阻塞最少，所以它最能代表纯粹的传输时间。601.Cristian算法（续）

如果知道时间服务器中断处理2.Berkeley算法

在BerkeleyUNIX中采取了完全相反的方法，这里的时间服务器（实际是时间守护进程）是主动的，它定期地询问每台机器的时间。然后基于这些回答，计算出平均值并告诉所有的机器将它们的时钟拨快或拨慢到一个新的值。这种方法适合于没有WWV接收器的系统，时间守护进程的时间必须由操作者定期地手工设置，这种方法如图2-29所示。612.Berkeley算法

在BerkeleyUNIX中采取2.Berkeley算法（续）

(a),时间守护进程在3:00把它的时间告诉其它机器，并且询问它们各自的时间(b)，各机器将它们各自的时间与时间守护进程时间的差值告诉时间守护进程，(c)守护进程计算出它们的平均值，通知各机器如何调整各自的时间。622.Berkeley算法（续）

(a),时间守护进程在3:3.平均值算法

上述两种方法都高度集中的，有不足之处。存在一些非集中式算法，如：一种分布式时钟同步算法：它是将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R，这里的T0是过去某一约定的时间，R是一个系统参数。在每次间隔的开始处，每台机器根据自己的时钟广播发送当前的时间，由于在不同机器上的时钟不可能完全同速工作，这种广播就不会完全同时发生。633.平均值算法

上述两种方法都高度集中的，有不足之处。存在一3.平均值算法（续）在机器广播发送时间之后，它启动本地计时器收集在S时间间隔中到达的其它广播，当所有广播到达后，执行一个算法，得到新的时间值。仅将这些值取平均值；——最简单先除去m个最大值和m个最小值，平均其余值。去掉两端值可认为是一种对m个错误时钟发出毫无意义的时间值的一种自我保护。给每条消息值加上一个从源到目的地的传送时间估计值，这种估计值可参考网络的拓扑结构或计算试探消息的响应时间而得出643.平均值算法（续）在机器广播发送时间之后，它启动本地计时器4.多个外部时钟源

对使用UTC进行同步又要求特别精确的系统来说，可给系统安装如WWV，GEOS或其它UTC源的多接收器来实现的。时间源自身固有的不精确性以及信号传送的不定性，最好的操作系统能做的也只是建立一个UTC时间范围。一般来说，不同的时间源会产生不同的时间范围，这种范围需要机器和它们达成一致。654.多个外部时钟源

对使用UTC进行同步又要求特别精确的系统4.多个外部时钟源（续）

为达到一致，每个具有UTC源的处理机定期在每一UTC精确分的开始处广播其时间范围，但没有处理机会同时获得时间包，传输和接收延迟依赖于缆线的距离和包必须经过的网关数，它对于每一对UTC源和处理机之间都不相同。其它因素，如多台机器要同时在以太网上传输而发生的碰撞。更进一步，如一台处理机忙于处理以前的包，它可能在相当长的几微秒内不去理会到来的时间包，从而导致了时间的不确定性。664.多个外部时钟源（续）

为达到一致，每个具有UTC源的处理4.多个外部时钟源（续）

解决：OpenSoftwareFoundation（开放软件组织）的分布式计算环境的处理方法某个接收器接收到所有时间源的UTC时间范围后，首先检查是否有与其他范围不相交的UTC范围。如果有，这些UTC范围一定是错误的，弃而不用。剩余的时间范围都是准确的UTC时间所在的范围；因此接着就求出这些范围相交的部分；最后将相交部分的中点作为准确的UTC时间，并将内部时钟设置为该值。674.多个外部时钟源（续）

解决：OpenSoftware4.多个外部时钟源（续）

684.多个外部时钟源（续）

682.4.2互斥

涉及多个进程的系统使用临界区容易编程当一个进程必须读或修改某些共享数据结构时，它首先进入临界区获得互斥锁，保证没有其它的进程能同时使用该共享数据结构。在单处理机系统中，使用信号量、管程和一些近似的结构来保护临界区。几个例子：在分布式系统中临界区和互斥是如何实现的。692.4.2互斥

涉及多个进程的系统使用临界区容易编程69一、集中式算法

在分布式系统中获得互斥的最直接方法是仿照单处理机系统的方法，选一个进程为协调者（比如在最大网络地址机器上运行的进程）。无论什么时候进程要进入临界区，它将向协调者发送请求消息，说明它想进入哪个临界区并希望获得允许。如果当前该临界区内没有其它任何进程，协调者就发送允许进入消息，如图2-30(a)所示。当应答到达时，请求者就可以进入临界区。70一、集中式算法

在分布式系统中获得互斥的最直接方法是仿照单处一、集中式算法（续）

现在假设有另一个进程，如图2-30(b)所示，请求进入同一个临界区，协调者知道该临界区已有一个进程，所以不能同意该请求，最好的办法是发出拒绝允许应答。而在图2-30中，协调者回避应答，这样就阻塞了进程2，使它等待应答。另一方面，协调者还可以发送“拒绝请求”应答。两种方法都会把进程2放入等待队列，等待临界区的释放。71一、集中式算法（续）

现在假设有另一个进程，如图2-30(一、集中式算法（续）

当进程1从临界区退出时，它向协调者发送释放互斥消息访问，如图2-30(c)所示，协调者从推迟请求队列中取出最前面的进程，向它发送允许进入消息。如果该进程仍然阻塞（即，这是第一条发给它的允许进入消息）它去除阻塞且进入临界区；如果明确发送一消息拒绝它进入临界区，此进程应该不时地查询输入的消息，或者接着将它阻塞等待许可响应。不管怎么样，当它发现允许进入时，它就可以进入临界区。72一、集中式算法（续）

当进程1从临界区退出时，它向协调者发一、集中式算法（续）

优点：算法保证了互斥的实现，协调者仅能让某一进程在某一时刻进入临界区。也很公平，因为允许请求的顺序同它们接收的顺序一致，没有进程永远等待（没有饥饿）。容易实现，每用一次临界区只需3条消息（请求，允许，释放），它不仅能管理临界区，也可用于更普遍的资源分配。缺点：协调者是一个单点故障，如它崩溃，整个系统将瘫痪，如果进程在请求之后被阻塞，以上这两种情况都没有消息返回，请求者不能从“拒绝请求”中辨认出协调者已崩溃。此外，大系统中单协调者会成为执行的瓶颈。73一、集中式算法（续）

优点：73二、分布式算法

分布式互斥算法，第一次出现的是在1978年Lamport关于时钟同步的论文中，后来Ricart和Agrawale对它作了进一步的改进，算法前提：Ricart和Agrawale算法要求系统中所有事件都是全序的。也就是说，对任何事件组如消息，哪个先发生必须无歧异。算法：当一个进程想进入临界区时，它要建立一个包括它要进入的临界区的名字、处理机号和当前时间的消息，然后将消息发送给所有其它进程。概念上讲也包括发送给它自身。发送的消息假设是可靠的，即每条消息都应该被确认，如可能应使用可靠的组通信，避免使用单个的消息通信。74二、分布式算法

分布式互斥算法，第一次出现的是在1978年L二、分布式算法（续）

当一个进程接收另一个进程请求消息时，根据接收方的状态以及临界区的名字。有三种情况要加以区别：若接收者不在临界区中，也不想进入临界区，它就向发送者发送OK消息。若接收者已经在临界区中，它就不必回答，而是负责对请求队列排队。若接收者要进入临界区，但是还没有进入时，它要将发来的消息和它发送给其余进程的时间戳对比，取小的那个，如果来的消息的时戳小，接收者发送OK消息，如果接收者本身的时间戳更小，那么接收者负责排列请求队列而不发送任何消息。75二、分布式算法（续）

当一个进程接收另一个进程请求消息时，二、分布式算法（续）

在发送完允许进入临界区的请求后，进程将不做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区，它从临界区退出时，向队列中的所有的进程发送OK消息，并把它从队列中删除。76二、分布式算法（续）

在发送完允许进入临界区的请求后，进程二、分布式算法（续）

分析：如果没有冲突，则正常工作。但是，假设两个进程要同时试图进入一个临界区，如图2-31(a)所示77二、分布式算法（续）

分析：如果没有冲突，则正常工作。但是二、分布式算法（续）

进程0发出时戳为8的请求，而同时进程2发出时间戳为12的请求。进程1不想进入临界区，所以它向2个发送者发回OK。进程0和2同时发现冲突，比较时间戳，进程2发现自己的大，它只好同意进程0进入临界区，向0发送OK，进程0就把进程2的请求排在队列中，为以后处理用，自己进入临界区，如图2-31(b)所示。78二、分布式算法（续）

进程0发出时戳为8的请求，而同时进程二、分布式算法（续）

当进程0结束退出临界区时，它把进程2的请求从队列中取出，并向进程2发送OK，允许进程2进入临界区，如图2-31(c)所示。算法之所以能够使用，因为在产生请求冲突时，遵守按时间戳排序，小时戳优先的规则。

79二、分布式算法（续）

当进程0结束退出临界区时，它把进程2二、分布式算法（续）

注意：如果进程2比进程0早发送消息，进程0在它请求进入临界区之前获得了进程2的请求消息，它允许进程2进入临界区，当进程2接收到进程0的请求时，它发现自己已经在临界区了，所以把进程0排在等待队列中。80二、分布式算法（续）

注意：如果进程2比进程0早发送消息，二、分布式算法（续）

问题：互斥必须无死锁或无饥饿。每次进入临界区需要2(n-1)条消息，这里n为系统中的进程数目。最好的是不存在单点故障。若有一个进程崩溃，它就不能回答请求，这种不发言将被解释为不允许进入临界区，这样就阻止了任何试图进入临界区的进程。因为n个进程之一失效的可能性是单协调者失效的n倍，我们必须设法换一种n倍复杂和需要更多启动网络通信的算法。81二、分布式算法（续）

问题：81二、分布式算法（续）

修补：当请求到达时，不管它是许可还是拒绝，接收者都要发送应答，一旦请求或应答消息丢失，发送者的等待时间到，它继续发送直到得到应答或者认为目的进程已经崩溃为止。在收到拒绝应答后，发送者应该阻塞等待直到获得OK消息。另一个问题：要么组间通信必须使用原语，要么每个进程必须维持一张组成员表，包括进入组进程、离开组进程和崩溃进程。这种方法最适用于小的从不改变成员的进程组。集中式算法中，处理所有请求会产生瓶颈的问题；在分布式算法中，所有进程都要参与决定是否进入临界区，若一个进程不能处理消息，那么强迫所有进程并行完成同一件事并不能改善整体的性能82二、分布式算法（续）

修补：当请求到达时，不管它是许可还是二、分布式算法（续）

对该算法有一点小的改进不需获得每个进程允许后方可进入临界区，只要防止任何两个进程同时进入同一个临界区即可，算法可改成：当一个进程从大多数进程那里获得允许而并不需要所有进程都允许时，它就可以进入临界区。这种算法中，一个进程在批准另一个进程进入临界区之后，在这个进程退出临界区之前，它不能再允许其它进程进入该临界区。总之，这种算法还是比原来集中式算法慢，复杂，昂贵，而且不健壮。83二、分布式算法（续）

对该算法有一点小的改进83三、令牌环算法

如图a所示的总线网，进程没有固定次序。用软件的方法，构造出一个逻辑环，环中每个进程都有一个位置，如图b所示。进程在环上的位置可以用网络地址的数字序号指定，也可以用其它方法指定。排序的方法并不重要，重要的是每个进程都要知道谁在它的下一个位置。84三、令牌环算法

如图a所示的总线网，进程没有固定次序。用软件三、令牌环算法（续）

算法思想：令牌环被初始化后，进程0首先获得令牌。这样，令牌开始绕环运动，它从进程K传递到进程K+1（以点到点的方式传递）。当进程从它的前一个邻居手中得到令牌时，检查它所试图进入的临界区，如果该临界区是空的，则该进程可以进入临界区，做它要做的工作，然后离开临界区。它退出后，将令牌传递到它的下一个邻居，不允许使用同一令牌进入第二个临界区。若一个进程得到了它相邻进程传递来的令牌，但它并不想进入临界区，就将该令牌往下传递。这样，如果没有任何其它的进程想进入临界区时，令牌就会高速地沿环绕行。85三、令牌环算法（续）

算法思想：85三、令牌环算法（续）

优点：在任何时刻只有一个进程拥有令牌，所以只有一个进程可以进入临界区。由于令牌以固定顺序运动，所以不会出现饥饿进程。一旦一个进程想进入临界区，最不理想的情况是等待所有其它进程进入后再退出临界区所用的时间之和。86三、令牌环算法（续）

优点：86三、令牌环算法（续）

算法存在的问题：比如，令牌一旦丢失，它必须重新生成。实际上，检测令牌丢失是很困难的，因为在网络上，令牌两次出现的时间是不定的，一个小时没有发现令牌并不意味着它丢失了，也许某个进程还在使用它。当进程崩溃时，该算法也会出现麻烦，但是恢复却容易得多。如果我们需要进程在接收到令牌后发回确认消息，当相邻进程试图传递给它令牌但却没有成功时，它就会检测到死进程。这时就将死进程从进程组中移出。它的下个进程就会从令牌持有者的手中接收到令牌。当然，这样做需要每个进程都能维持当前环设置情况。87三、令牌环算法（续）

算法存在的问题：87四、三种算法的比较

88四、三种算法的比较

88四、三种算法的比较（续）

有关“每次进入需要的消息”集中式算法最简单，也最有效的，它在进程进入和退出临界区时，只用了3条消息，即请求进入，同意进入和退出时释放。分布式算法需要N-1条，（给每个其它进程）请求消息，及另外的N-1条允许消息，总共有2(N-1)条消息，对于令牌算法该数目是可变的，如果每个进程总是想进入一个临界区，则令牌的每次传递将导致一次进出临界区。平均每一次进入临界区入口都有一条消息。在其它极限情况下，令牌也许将几小时几小时地沿环传递而没有进程想使用它，在这种情况下，每一次进入临界区入出口消息数是无界的。89四、三种算法的比较（续）

有关“每次进入需要的消息”89四、三种算法的比较（续）

有关“延迟”进程需要进入临界区到它能进入临界区的延迟也随着这三种算法而变化：当临界区很少被使用时，造成延迟的主要因素是控制进入临界区的机制。当临界区被经常使用时，延迟的主要因素是等待其它进程使用的过程。表2-1表示前一种情况，假设网络在某一时刻只能处理一条消息：在集中式算法的情况下，进入临界区只需要处理2条消息的时间，在分布式算法的情况下需要2(N-1)条消息，对令牌环算法，时间从0（刚接收到令牌）到N-1（释放令牌）变化。90四、三种算法的比较（续）

有关“延迟”90四、三种算法的比较（续）

问题：这三种算法在进程崩溃时都损失惨重，为了避免由于某些崩溃造成的系统瘫痪，必须引入特殊的方法和附加的复杂性。更具讽刺意义的是分布式算法比集中式算法对崩溃事件更敏感。这些算法都不能用于容错系统，但如果崩溃事件很少发生的话，这些算法都是可以接受的。91四、三种算法的比较（续）

问题：91五、选举算法许多分布式算法需要一个进程充当协调者、发起者、排序者或其他特定的角色。通常，选择哪个进程充当协调者并不重要，重要的是要有进程负责。如果所有进程的地位都相同，没有特性上的区别，就无法选择其中一个为特殊进程，假设每一个进程有一个特殊的号码，比如它的网络地址，通常选举算法总是找拥有最大号码的进程，把它指定为协调者，各算法在选举时有不同的方法。假设每个进程都知道所有其它进程的进程号，但不知道目前哪些进程正常，哪些进程不正常。选举算法的目的是确定选举何时开始，它在所有进程都同意的基础上选出协调者。92五、选举算法许多分布式算法需要一个进程充当协调者、发起者、排五、选举算法--1.欺负（Bully）算法1

由Garcia-Molina(1982)提出的当一个进程发现协调者不再响应请求时，它就发起选举。进程P负责选举如下：P向所有号码比它大的进程发送选举(ELECTION)消息。若无人响应，P获胜成为协调者。若有号码比它大的进程响应，响应者接管，P的工作完成。93五、选举算法--1.欺负（Bully）算法1

由Garcia五、选举算法--1.欺负（Bully）算法2

在某一时刻，一个进程只能从号码比它小的进程那里得到一个选举（ELECTION）消息，当它到达时，接收者就发送回OK消息，表明它的存在并接管，然后接收者主持选举（除非它正在主持别的选举）。除了一个进程外的其余进程都得放弃，这一个进程就是新的协调者，它把选举获胜的消息发送给所有进程，告之它是新的协调者。若一个进程刚刚崩溃过，而又得到恢复，它也有选举权，若它刚好是当前运行进程中号码最大的，它就会获得选举的胜利，从而接管协调者的工作，所以最大的进程总能取胜，故而将该算法命名为欺负算法。94五、选举算法--1.欺负（Bully）算法2

在某一时刻，一五、选举算法--1.欺负（Bully）算法3

95五、选举算法--1.欺负（Bully）算法3

95五、选举算法—2.环算法1

基于没有令牌的环，假设所有的进程是按物理或逻辑排序的，每一个进程都知道谁是它的后继者。当任何一个进程发现协调者不再起作用时，它就构造一个包含它自身进程号的选举消息发送给它的后继者，如果后继者失效，消息将绕过后继者，到达后继者的后继者，或者再下一个，直到找到一个运行进程。每次接收者都把自己的进程号加入到消息表中。最后，消息到达了始发者的手中，始发者接受到包括自己进程号的消息后，将消息的类型转化为协调者消息，该消息将再一次绕环运行，向所有的进程通知谁是协调者（在成员表中进程号码最大的那个）和新的环成员。当消息循环一周后，被去掉，每个进程都恢复工作。96五、选举算法—2.环算法1

基于没有令牌的环，假设所有的进程五、选举算法—2.环算法2

进程2和进程5同时发现协调者7失效两条消息沿环运动，消息中有完全一样的成员，相对顺序也相同，当两条消息再绕环一周时，都被去掉。有多余的消息循环没有坏处，最多是浪费了一点带宽。97五、选举算法—2.环算法2

进程2和进程5同时发现协调者7失2.5原子事务处理

迄今为止研究的所有同步技术在其本质上来说都是处于底层的，比如信号量。这些技术需要程序员密切注意互斥、临界区管理、死锁预防、崩溃恢复等问题的细节。需要的是更高层次的抽象，也就是隐藏技术问题，允许程序员将精力集中在算法和进程如何并行运行上。这样的抽象是存在的，而且被广泛应用在分布式系统中。我们称其为原子事务，或简称为事务。术语原子操作也被广泛使用。982.5原子事务处理

迄今为止研究的所有同步技术在其本质上来2.5原子事务处理

2.5.1原子事务简介2.5.2事务模型2.5.3实现992.5原子事务处理

2.5.1原子事务简介992.5.1原子事务简介

原子事务的最初模型来源于商业社会。计算机模型有些类似。一个进程宣布它想同其他的一个或几个进程开始一个事务。它们可以就不同的选择进行协商、创建、删除对象，执行一段时间的操作。然后发起者宣布它希望其它进程能保证任务完成。如果其它进程都同意，那么就达成了永久的协议。如果有一个或几个进程拒绝（或在同意前崩溃），那么就会返回到事务开始前的状态。这时对象，文件，数据库等方面的副作用都会神奇地消失。这种要么全有要么全无的特性简化了程序员的工作。1002.5.1原子事务简介

原子事务的最初模型来源于商业社会。2.5.1原子事务简介（续）

计算机系统中对事务的使用可以回溯到20世纪60年代。这种设计的最大优点：对任何原因引起的运行错误，所有的磁带都可以倒卷(rewound)，其工作可以毫无损失的重新开始。老式的磁带系统具有了原子事务要么全有要么全无的特性。1012.5.1原子事务简介（续）

计算机系统中对事务的使用可以2.5.1原子事务简介（续）

当前如何在线更新数据库的银行应用的例子。客户通过带有调制解调器的PC机连接到银行，想将一个帐户下的钱取出再存入另一帐户。操作通过下面两步执行：提取（金额，帐户1）。存入（金额，帐户2）。如果电话连接在第一步之后第二步之前中断，那么第一个帐户已被取出而第二个帐户却没有存入。钱就消失在了未知的空间中。将这两个操作组成一个原子事务可以解决这个问题。要么两个都执行，要么一个也不执行。关键是事务执行失败后能返回到最初状态。这种能力是原子事务必须提供的。1022.5.1原子事务简介（续）

当前如何在线更新数据库的银行2.5.2事务模型事务模型提出前的一些假设：假设系统由一些相互独立的进程组成，每个进程都会随机出错。假定通信错误已经被底层软件透明地处理尽管通信一般来说是不太可靠的，消息会丢失，但是底层可以采用超时重发协议恢复丢失的消息。1032.5.2事务模型事务模型提出前的一些假设：103一、稳定存储器存储器有三种分类。第一种是普通的RAM存储器，当电源出错或机器崩溃时会丢失信息。第二种是磁盘存储器，它不受CPU错的影响，但磁头错会导致信息丢失。最后一种是稳定存储器(stablestorage)。它不受洪水地震之类大灾难之外的任何其它错误的影响。104一、稳定存储器存储器有三种分类。104稳定存储器的实现稳定存储器可以通过两个普通磁盘来实现。如图所示，驱动器2上的每一块是驱动器1上相应块的精确拷贝。当更新一个块时，首先更新并检查驱动器1上的块，然后驱动器2上的块。105稳定存储器的实现稳定存储器可以通过两个普通磁盘来实现。105系统崩溃的恢复假设系统在更新驱动器1之后更新驱动器2之前崩溃，如图b。在恢复时，磁盘可以一块一块地进行比较，当两个相应块不一致时，可以假定驱动器1是正确的（因为驱动器1总是先于驱动器2更新），因此将新块从驱动器1拷贝到驱动器2。当恢复过程完成后，两个驱动器又一致了。106系统崩溃的恢复假设系统在更新驱动器1之后更新驱动器2之前崩溃磁盘块自然损坏后的恢复另一个潜在的问题是磁盘块的自然损坏。垃圾微粒或者一般的磨损和破裂都将使一个以前正确的磁盘块会无缘无故或没有警告地出现奇偶校验错，如图c所示。当检测到这样的错误时，坏块可以通过另一台驱动器上的相应块恢复。107磁盘块自然损坏后的恢复另一个潜在的问题是磁盘块的自然损坏。1一、稳定存储器（续）实现稳定存储器的价值：它很适合于需要高度容错的应用，例如原子事务。当数据写入稳定存储器并读出以检验它们是否正确写入时，它们相继丢失的机会非常小。108一、稳定存储器（续）实现稳定存储器的价值：108二、事务原语

使用事务编程需要由操作系统提供或者由语言运行系统提供特殊原语，例如：BEGIN_TRANSACTION：标记一个事务的开始。END_TRANSACTION：结束事务并设法提交。ABORT_TRANSACTION：取消事务；恢复旧值。READ：从一个文件（或其它对象）读取数据。WRITE：将数据写入一个文件（或其它对象）。109二、事务原语

使用事务编程需要由操作系统提供或者由语言运行系二、事务原语（续）

更精确的原语列表取决于事务中正在使用的对象类型。在一个邮件系统中，可能有发送、接收以及转发邮件等原语。而在一个帐目系统中可能会有很大的不同。读取和写入却是典型的应用。在一个事务中，也允许使用普通语句、过程调用等。110二、事务原语（续）

更精确的原语列表取决于事务中正在使用的二、事务原语（续）——事务体

BEGIN_TRANSACTION和END_TRANSACTION用来限定事务的范围。介于它们之间的操作构成了事务体。这些操作要么全部执行，要么一个也不执行。这些操作可能是系统调用，库过程，或者是某种语言中用括号括起来的语句，这取决于实现的需要。111二、事务原语（续）——事务体

BEGIN_TRANSACT二、事务原语-例子考虑到保定火车站买一张从保定到汕头的火车。由于没有直达火车，只能买联票。保定石家庄；石家庄广州；广州汕头。下面通过3个操作预定了这3条独立的路线的座票。

BEGIN_TRANSACTION reserve保定-石家庄 reserve石家庄-广州 reserve广州-汕头 END_TRANSACTION112二、事务原语-例子考虑到保定火车站买一张从保定到汕头的火车。二、事务原语-例子（续）现在假设前两条路线已经预定成功，但是第三条已经定满了。那么事务就会因此而中止，前两个预定的结果也将被取消——售票系统的数据库恢复到了事务开始前的状态，就像什么也没有发生一样。BEGIN_TRANSACTION reserve保定-石家庄 reserve石家庄-广州 广州-汕头full→ABORT_TRANSACTIONEND_TRANSACTION113二、事务原语-例子（续）现在假设前两条路线已经预定成功，但是三、事务的特性

事务有四个重要的特性，它们是：原子性(Atomic)：对外部世界来说，事务的发生是不可分割的。一致性(Consistent)：事务不会破坏系统的恒定。独立性(Isolated)：并发的事务不会互相干扰。持久性(Durable)：一旦一个事务提交，改变就是永远存在的。这几个属性通常按其首字母简称为ACID。114三、事务的特性

事务有四个重要的特性，它们是：114原子性所有事务具有的第一个特性是原子性。这个特性确保了每个事务要么全部发生，要么全部不发生。如果发生，就是不可分割的，瞬间的操作。当一个事务处在处理过程中时，其它进程（无论是否与事务有关）都不能看到任何中间状态。115原子性所有事务具有的第一个特性是原子性。115原子性—例假设某个事务要在一个10字节的文件末尾添加数据。如果在事务处理过程中其它进程读取了这个文件，那么无论该事务已添加了多少内容，那些进程看到的只能是10个字节。如果事务成功结束，这时文件在结束的瞬时增长到了新的大小，无论有多少个操作存在，都不会有中间状态。116原子性—例假设某个事务要在一个10字节的文件末尾添加数据。1一致性

第二个特性说明事务是一致的，这意味着如果系统拥有某种必须经常保持的不变性，那么一旦在事务开始之前保持有这样的性质，则事务结束后该性质就还应该存在。例如在一个银行系统中，最关键的不变性是资金守恒规则。在任何内部转帐之后，银行的资金帐目应与转帐前保持一致，但是在事务执行的短暂时刻内，这种不变性会受到损害。然而事务结束之后，这种损害就没有了。117一致性

第二个特性说明事务是一致的，这意味着如果系统拥有某独立性

第三个特性说明事务是独立的或连续的。这意味着如果两个或两个以上的事务在同时运行，那么对它们自己和其它进程来说，最终结果看起来就象是所有的事务是按某种次序（依赖于系统）顺序运行的。118独立性

第三个特性说明事务是独立的或连续的。118独立性—例下面三个事务被三个独立的进程同时执行。如果它们顺序执行，那么X的最终结果应该是1，2或3，取决于哪一个事务最后运行（X可以是一个共享变量，一个文件或其他对象）。119独立性—例下面三个事务被三个独立的进程同时执行。119独立性—例在d中我们看到了称之为调度表的不同次序，其中事务可以是交错的。调度1是真正串行的，即事务严格按顺序来运行，因此它满足连续性的定义。调度2不是串行的，但是它也是合法的，因为它返回的X值与严格串行返回的值一致。第三个调度是非法的，因为它将X的值置成了5，这是顺序执行所不可能产生的。120独立性—例在d中我们看到了称之为调度表的不同次序，其中事务可独立性（续）为保证独立的操作正确交替执行是系统的责任。通过给予系统按照自己需要选择操作执行顺序的自由——假设它得到的答案是正确的——我们消除了程序员自己进行互斥处理的需要，因此简化了编程。121独立性（续）为保证独立的操作正确交替执行是系统的责任。121持久性

第四个特性说明事务是持久的。这是指这样一个事实，即一旦一个事务提交，无论发生什么，这个事务都会向前进行，结果不会再变了。提交之后发生的任何错误都不可能使结果取消或丢失。

122持久性

第四个特性说明事务是持久的。122四、嵌套事务

事务可以包含子事务，这通常称作嵌套事务。顶层事务可以在不同的处理机上创建并行运行的子事务，以提高性能、简化编程。这些子事务中的任何一个都可以执行一个或多个子事务，或者创建自己的子事务。123四、嵌套事务

事务可以包含子事务，这通常称作嵌套事务。123四、嵌套事务（续）

子事务引起的问题：假设一个事务启动了几个并行的子事务，其中一个已经提交，其操作结果在父事务中已经生效。经过更进一步的计算，父事务被终止，并将系统恢复到了顶层事务开始前的状态。结果，已经提交了的子事务的结果也必须被恢复。于是上面提到的的持久性只是对顶层事务而言。持久性：提交之后发生的任何错误都不可能使结果取消或丢失。124四、嵌套事务（续）

子事务引起的问题：124四、嵌套事务（续）

由于事务可以嵌套任意多层，因此需要管理措施以使其一切正常。但语义却是清楚的。当任何事务或子事务开始的时候，在概念上给予它一个整个系统全部对象的私有拷贝，可以按照其意愿进行操作。如果事务被终止，那么它的私有空间就会消失，就象事务从来都没有存在过一样。如果事务提交了，那么它的私有空间就会取代父辈的空间。因此如果一个子事务提交后又开始了一个新的子事务，那么它就可以看到第一个子事务的结果了。125四、嵌套事务（续）

由于事务可以嵌套任意多层，因此需要管理2.5.3实现

如果每个进程执行一个事务仅仅只是更新它自己使用的对象（文件、数据库记录等），那么事务就不会是原子的，而且事务异常终止时它所作的更改也不会神奇的消失。此外，运行多个事务时也不会是串行的。显然，需要其它的实现方法。经常使用的有两种方法：私有工作空间写前日志1262.5.3实现

如果每个进程执行一个事务仅仅只是更新它自己使一、私有