分布式操作系统课件.ppt

《分布式操作系统课件.ppt》由会员分享，可在线阅读，更多相关《分布式操作系统课件.ppt（145页珍藏版）》请在三一办公上搜索。

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

2、)人们可读的文本名，便于人们识别和记忆系统标识符，软件用来对资源进行解释和存储的名字形式，是一个定长的位串下面是几种名称：物理网址和逻辑网址：这类名称可视为名字的位置或地址端口、进程和组标识符：这类名称可视为消息的目的地资源标识符：由服务器和内核管理的资源的低层独立定位的标识符文件：使用人们可读的文本名字进行存取的信息集,4,一、名字与属性（续）,客户用文本名对资源的操作过程(Amoeda)存取一个资源涉及到将其文件名映射成对应的资源标识符，再将该资源标识符映射成一个端口标识符和一个特定服务的标识符；然后将这个端口标识符映射成一个网络地址，将这个特定服务的标识符映射到相关服务器中的资源。,5,

3、一、名字与属性（续）,分布式系统中使用的许多名称都是有特定含义的，客户(用户或进程)使用这样的名称请求服务系统对它管辖的命名对象和资源进行操作。若系统管理很多对象，那么每个对象都得命名，考虑到效率，这个名称应能直接映射它所代表的对象。例如，当要求删除一个文件时，该文件的名称就被传递给文件服务系统；请求向一个进程发信号时，该进程的标识符被提供给进程管理系统。这样一些名称仅用在管理这些命名对象的服务系统的上下文(共享对象除外)中。,6,一、名字与属性（续）,引用超出任何单一服务系统范围的实体时，也要命名。典型例子包括：用户(带有专用名、逻辑名、用户标识符和电子邮件地址等)计算机(带有名字宿主名，如

4、mac41)服务系统本身(如文件服务、打印服务等)。所有这些名称必须是有意义的、可读的因为用户和系统管理员需要通过这些名称访问分布式系统的主要组件和配置，程序员在编程过程中需要这些名称去访问相应的服务(系统)，用户借助它们进行通信。考虑到 Internet 提供的连接能力，这些命名要求在范围上应该是全球的。,7,一、名字与属性（续）,名称和对象之间的联结称为联编(binding)。特定服务名被服务系统联编到相关对象或资源的实际表示上用户名、计算机名和服务(系统)名被联编到命名对象的属性上，所有这些对象都把地址作为属性之一。一般而言，属性值或是基本值，如整数；或是自身的名称，如 Internet

5、 地址230.1 32.123.112等。最终，所有的名称被简化成基本值或不能再进一步“查找”的基本名。与名称相关的属性不仅对用户而且对其他服务都是有用的。例如，在电子邮件系统中，Internet域名系统(DNS)用来从电子邮件地址中查找邮件主机地址，但由另外的软件来传递和存储邮件消息。,8,二、名字服务系统,名字服务系统管理着一个联编数据库，其中存储着文本名(可读的)及其相关的属性。其支持的操作有：解析一个名字在该数据库中查找给定名字的相关属性；为新名字生成新的联编；删除联编；列出已联编的名字等操作。注意：虽然把联编集看作一个数据库，但一般说来名字不是简单键，常常由若干部分组成(例如，)，这

6、些部分需在数据库的不同区域中分别查找，这些不同区域即上下文(context)。,9,二、名字服务系统（续）,名字管理从其他服务中独立出来的原因：很大程度上是因为分布式系统的开放性；一致性(unification)：让不同的服务器或服务系统管理的资源出现在同一命名方案中似乎比较方便的。例如在UNlX中的NFS中，一些文件在本地磁盘上管理，而另一些则在远程服务器上，所有的文件出现在单一的名字空间层次结构中。此外，一些“文件”的名字涉及到本地设备或命名过的管道。,10,二、名字服务系统（续）,集成(integration)：在分布式系统中，不一定总能预测共享的范围。有时候，需要共享和命名在不同管理域

7、中创建的资源，这可能会引起问题，例如，合并两个用户集，分配给每个用户的登录名可能会发生冲突。更坏的情况是，这两组用户可能有完全不同的命名规则。,11,三、名字服务的一般要求,名字服务越来越复杂。几个例子：Grapevine：最早的可扩充多域名字服务系统之一Global Name Service：DEC系统研究中心开发的全球名字服务，是 Grapevine的下一代，目标为：处理任意数量的名字并为任意数量的管理组织服务：例如，该系统应能处理世界上所有计算机用户的E-mail地址。,12,三、名字服务的一般要求（续）,长生命期：在其生命期中，名字空间的组织和实现名字服务的一些组件将会发生许多变化。高

8、可靠性：绝大多数服务系统依赖于名字服务系统，一旦它崩溃了，其他服务系统就无法工作。故障隔离：局部故障不会导致整个名字服务系统失效。容忍怀疑：在一个较大的开放系统中，不存在所有客户都信赖的组件。DNS：Internet域命名系统(DNS)使用得非常广泛，它命名Internet上的对象(用户和计算机)。,13,2.3.2一般的命名方式,在计算机系统中，每个对象一般有两个名字：由用户识别的文本名(符号名)由系统使用的内部名内部名可以是该对象的实际位置，也可以是查询该对象的地址的一种表示形式。通过某种映射，系统可把用户定义的符号名转换成相应的内部名。名字和对象之间的关系：同一对象可能有多个名字；同一名

9、字也可用来代表不同的对象(在不同的作用域内),14,2.3.2一般的命名方式（续）,A、B各有三个文件，其目录包含了每个文件的文件名及指向对应文件在磁盘上地址的指针。这里，相同的文件名可用来指称不同的文件。例如，两个目录中都含有s.pas，但它却代表两个不同的文件。不同的文件名也可以指称同一个文件。例如，A目录中的test.dat和B 目录中的old.dat两者的指针都指向“文件1”。,15,2.3.2一般的命名方式（续）,由于系统可以有多个用户，因此，目录常常组织成层次结构。文件名的含义：不仅指文件名本身而且也应包括它与根之间所有目录的名字(路径名)。一个例子：tset.dat文件的 完全路

10、径名是root:A:test.dat。,16,2.3.2一般的命名方式（续）,大多数系统允许用户设置一个默认目录或当前目录，此时用户不必写出完全路径名。一个例子：假定A设置它的默认目录为root:A，当用户使用文件名my.c时，操作系统 就自动地把默认目录名作为 my.c的前缀，形成完全路 径名root:A:my.c。,17,2.3.3分布式系统中的命名方式,分布式系统中的命名更复杂：由于分布式环境中的名字可用来指称不同场点或不同场点的不同层次结构上的对象，因此与单机系统相比，其命名和名字的映射工作更加复杂。以下讨论分布式环境下的名字管理器的主要功能命名方案标识符和字符串名,18,一、名字管理

11、器的主要功能,DOS中名字管理部分的功能：通过管理名字在系统的地址去定位命名过的对象；创建、删除、改变对象的名字；改变对象的位置，以支持对象在系统中的迁移；利用对象名字来支持对象的共享；创建一个对象组；,19,一、名字管理器的主要功能（续）,从组中删除成员或将成员加入其中；枚举组中的成员；测试组中成员之间的关系；借助组名共享资源或共享服务程序；支持对象组的递归结构；完成外部名(符号名)到内部名(系统名)的映射工作。,20,二、分布式系统中的命名方案,分布式系统中常用的命名方案有绝对命名、相对命名和层次式命名三种。由绝对命名方案命名的名字是全系统范围唯一的、无二义性的。在机内，这类名字通常是由时

12、钟或计数器之值产生的位串。由相对命名方案命名的名字依赖于使用它的上下文。对于不同的使用者，一个对象的名字可以是不同的，或者说，一个对象的名字不唯一。,21,二、分布式系统中的命名方案（续）,层次式命名方案用如下方式组织系统中的对象名：对象被分划成若干组；每组给定全局唯一的组名；每组中的每个对象在组内给定唯一的名字；一个组中对象名还可按此方式进一步分划成若干子组。,22,二、分布式系统中的命名方案-实例1,VMS的命名体系：层次式，完全路径名由一个设备名接任何个数的目录名再接文件名和扩展文件名构成。图2-22展示了VMS中两个设备 Userdisk 和Sysdisk的目录结构。Userdisk有

13、两个目录dirl和dir2。文件letter.dom 的完全路径名是Userdisk:dir2.me letter.dom.,23,二、分布式系统中的命名方案-实例2,DEC网命名方式：把类似VMS的命名体系再向上扩充一层，使之包含场点名，如图2-23所示。远程场点上的文件可通过把该场点名加在相应文件的路径名之首来进行访问。例如，在sitel上的文件letter.dom的完全路径名现在为sitel:userdisk:dir2.meletter.dom.,24,二、分布式系统中的命名方案-实例2（续）,DEC网命名方案中，场点名必须唯一，且每个场点必须知道系统中所有其他场点的名字。这种方案容易实

14、现，用户也比较容易掌握。但存在下面的问题：由于文件的位置事实上已作为文件名的一部分，那么当一文件从一场点迁移到另一场点时，意味着该文件的名字也必须改变，从而导致凡涉及到访问该文件名的所有操作也不得不作相应的修改。若一文件有多个副本且位于不同的场点上，它们就会有不同的名字，那么对它们的任何更改都容易导致不一致性。系统的某些细节(如场点)对用户是可见的。一般说来，这是分布式系统的设计者所不希望的。,25,二、分布式系统中的命名方案-设计原则,设计命名方案的一个基本观点：名字是依赖于位置还是独立于位置。这也可以说是性能对灵活性的问题。在不依赖于位置的命名方案中，对象的名字不含其在系统中的位置。这使得

15、可对系统中的远程或本地资源(对象)进行一致的存取。但在依赖于位置的命名方案中，就可能出现像DEC网命名方案的问题。移动文件要注意改名，后续操作也要注意名字问题多副本情况一致性的维护问题透明性的问题,26,三、唯一标识符和字符串名,UID系统中的每一对象给定一个唯一的标识符(UID)，即在系统中，它唯一地指称该对象。一个对象的UID 在其整个生命期内决不改变。特别，当一对象从一场点迁移到另一场点时其UID 仍保持不变。一个UID是相关对象的绝对名字，它通常是利用系统时钟产生的。UID 也可作为一种权限使用，此时，与其相关的对象是受保护的，它既不能由用户改变，也不应被用户忘却。为了使UID 在全系

16、统范围内唯一，也可以将局部宿主ID作为它的一部分。此外，它还可含有一些随机生成的位，使得它难以猜测，从而起到保密作用。,27,三、唯一标识符和字符串名（续）,字符串名(简称串名)具有如下特征：同一串名可由不同的用户用来访问不同的对象；不同的串名可由(不同的)用户用来访问相同的对象；对象可以在场点间迁移不必改变其串名。,28,三、唯一标识符和字符串名（续）-总结,在大多数系统中，字符串名主要供用户使用，而UID仅供操作系统使用。UID通常是定长、压缩形式的(一般有64128位)，这就有利于系统级的构造、使用和管理；字符串名一般较长且往往是可变长的(如10-100字节)，这对用户是方便的，但不太适

17、合在系统级使用。操作系统提供了从字符串名到UID 的映射。,29,2.3.4名字服务器的设计,名字服务器(name server)的主要功能：将一个符号串名(一个整数串名或字符串名)映射成系统内唯一的物理地址。名字服务器管理着包含有“名字及其物理地址”的对照表，系统中的所有服务程序都由名字服务器来寻址和定位。例子：,30,2.3.4名字服务器的设计（续）,剑桥大学设计CDCS中的服务程序族利用其名字服务器来寻址和定位。为了引用一个服务程序，client 将代表某个服务程序名字的一个ASCII串发送给名字服务器，名字服务器收到这一信息后，就查看该串是否在其管理的表中。若在，它就返回所指服务程序的

18、所在处理机编号、用于编址它的端口和相应的协议等。在CDCS中，名字服务器本身的地址是固定的，系统提供了向名字服务器管理的表中添加或从中删除信息的命令。不过，出于保护原因，这类命令只能由系统管理人员使用。,31,2.3.4名字服务器的设计（续）,设计名字服务器一般有中央方式、复制方式和分划方式三种途径。用中央方式设计时，全系统仅有一个(中央)名字服务器，系统中的所有服务程序都由它来寻址和定位。但由于性能及可靠性方面的原因，这种方式不常采用。用复制方式时，每个场点都有一个名字服务器的副本，用以管理该场点上的所有服务程序及本场点与其他场点间相互请求的服务信息。,32,2.3.4名字服务器的设计（续）

19、,分划方式意指：若系统由若干子系统(子网)组成，则对于每个子系统，用一个名字服务器管理本子系统上的所有服务程序及本子系统与其他子系统相互请求的服务信息；或者若系统的名字空间可根据某种方式来分划，则对于每个经这样分划后的实体，用单独的或复制式的名字服务器管理；或者将名字空间组织成层次结构来管理。,33,2.4 DOS中的同步,分布式系统中的进程通信消息传递（Send、Receive、Replay等原语）RPC组通信这并不是分布式系统的全部内容。与此紧密相关的是进程之间如何协作及如何彼此同步。比如说，在分布式系统中临界区如何实现，资源如何分配。,34,2.4 DOS中的同步（续）,在单CPU系统中

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

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

22、况是，一个分布式系统应该比单机系统更可靠，一台机器崩溃不影响其它机器的继续运行，不通过集中而获得同步所使用的方法应该与传统操作系统所用的方法不同。上述的最后一点是十分关键的，在集中式系统中时间的概念很清楚，当进程想知道时间时，它使用系统调用，由内核提供。如果进程A询问时间，之后进程B也询问时间，B得到的时间值就应该大于或等于A所得到的时间值，但一定不会小于A得到的时间值。在分布式系统中，获得时间上的一致是并不容易。,38,一个简单的例子：在缺少全局时间时的UNIX下的make程序-DOS中很难获得时间上的一致,UNIX系统中一个大程序通常可被分割成多个源文件，如果某个源文件发生变化，只需将该文

23、件重新编译即可，而不需要对所有的文件进行重编译。Make程序所使用的方法：当编程者修改完所有的源文件，他启动make程序，看一下源文件和目标文件最后一次修改的时间，如果源文件INPUT.C时间为2151，而相应的目标文件INPUT.O时间为2150，make就知道INPUT.C在INPUT.O创建后被改动过。因此，INPUT.C必须重新编译。相反，若INPUT.C时间为2144，而INPUT.O时间为2145，就不必再重编译了。make检查所有的源文件并找出哪一个需要重编译，调用编译器重新编译它。,39,一个简单的例子：在缺少全局时间时的UNIX下的make程序-DOS中很难获得时间上的一致（

24、续）,在没有统一时间的分布式系统中：假设OUTPUT.O的时间为2144，紧随其后OUTPUT.C被修改，但是由于它所在机器上的时钟略慢，造成OUTPUT.C时间为2143，如图2-24所示。make将不再调用编译器，最终可执行的二进制程序将包括由老的源文件和新的源文件所产生的混合目标文件，这样可能将不能再正常执行。,40,一、问题提出,所有的计算机都有一个计时电路（计时器），通常是由一个精确的石英晶体制成，当其在张力限度内时，石英晶体以一定的频率振荡。与每个晶体相关的是两个寄存器、一个计数器和一个保持寄存器。每次振荡时使计数器减1，当计数器减为0时，产生一次中断，计数器重新从保持寄存器中装入

25、起始值，通过这种方法可以编程使得一个计时器每秒能产生60次中断或以其它希望的频率产生中断成为可能，每次中断称作一个时钟点（clock tick）。当系统刚启动时，总是要求操作者输入日期和时间，然后将它们转换成某一已知起始时间后的时钟值，并将它存储在存储器中，在每个时钟点时，中断服务程序将此值加1，用这种方法进行（软）时钟计时。,41,一、问题提出（续）,在单机单时钟中，如果时钟被瞬间关闭其问题不会太大，因为这台机器上所有进程使用同一时钟，它们仍将内在地保持一致。比如，文件INPUT.C时间为2151，文件INPUT.O时间为2150，make将重新编译源文件，假设时钟关闭的时间为2，真正的时间

26、则分别为2153和2152，有用的只是相对时间。,42,一、问题提出（续）,多CPU系统中，每个CPU将拥有自己的时钟，情况发生变化。尽管每个晶体振荡频率总是相当稳定，但保证不同计算机上的晶体以完全相同的频率振荡是不太现实的。实际上，当系统有N台计算机时，所有N个晶体将以略微不同的速度振荡，导致（软）时钟逐渐不同步，当同时读这些时钟时，也会得到不同的值。这种在时间值上的不同称作时钟偏移（clock skew）。一个程序期望与文件、目标文件、进程或消息相联系的时间应是正确的，且与产生它们的机器（即使用哪个时钟）无关。,43,一、问题提出（续）,问题：同步所有时钟产生一个单一的、无二义的时间标准是

27、否可能。解决：Lamport（1978）阐明了时钟同步是可能的，并且描述了实现的算法，他还继续对这个问题进行了一些研究（Lamport 1990）。,44,二、逻辑时钟与事件定序,Lamport的观点：时钟同步不需要绝对同步。如果两个进程无相互作用，它们的时钟无须同步，因为即使缺少同步也觉察不出来，不会产生什么问题。通常并不必需所有进程在时间上完全一致，而是它们在事件发生的顺序要上完全一致。在上述make程序的例子中，计时目的在于说明INPUT.C比INPUT.O早或晚产生，而并不是它们各自产生的绝对时间。,45,二、逻辑时钟与事件定序（续）,如有特殊限制，不仅时钟要完全一致，而且不能与真实时

28、间有一点点的误差，这种时钟称作物理时钟(physical clocks)，本节将讨论Lamport算法，它用逻辑时钟进行同步。,46,二、逻辑时钟与事件定序（续）,Lamport 为同步逻辑时钟定义了“先发生”关系：表达式AB读做“A在B之前发生”，意思是所有进程认为先发生事件A，接着发生事件B，这种关系有如下两种情况：如果A和B是在同一进程中的两个事件，且A发生在B之前，则AB为真。如果A是一个进程发送消息的事件，B为另一个进程接收这一消息的事件，则AB为真，消息不能在发送之前接收，也不能在发送的同时接收，因为传送过程还需要一定时间。先发生是一个传递关系，即，若AB且BC则AC。“先发生”也

29、称为前趋关系（happen-before relation）如果两个事件X和Y，出现在不同进程中，但并不交换消息（甚至不由第三方间接交换），则XY为假，YX也为假。则事件X和Y称为并发事件，即它们之间不存在谁先谁后的问题。,47,二、逻辑时钟与事件定序（续）,水平方向表示空间(不同的进程)，垂直方向表示时间。设A、B为任意两个事件，当且仅当在图中不存在从A到B或从B到A的一条路径时，事件A 与事件B 是并发的。一些存在前趋关系的事件是：p1q2，r0q4，q3rl，p1q4。并发事件是：q0和p2，r0和q3，r0和p3，q3和p3。无法知道两个并发事件(例如q0和p2)哪一个先发生。既然这两

30、个事件没有一个影响另一个，因此哪一个先发生并不重要。,48,三、时间戳,需要一种测量时间的方法，使得对每一事件a，在所有进程中都认可给它分配一个时间值C(a），即打上时间戳，这些时间值必须有如下性质：若AB则C(A)C(B)。若a和b是同一进程中的两个事件，且ab，则C(a)C(b)同理，若a是一个进程发送消息的事件，b为另一个进程接收消息的事件，那么C(a)C(b)。时钟时间值C必须向前走（递增），不能倒退（减少）。校正时间的操作是给时间加上一个正值，而不是减一个正数。,49,三、时间戳Lamport算法怎么给事件分配时间,各进程运行在不同的机器上，每个机器都有自己的时钟，以各自不同的速率工

31、作。进程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时刻到达，这是绝对不可能出现的，必须防止这种情况的出现。,50,三、时间戳Lamport算法怎么给事件分配时间（续）,Lamport的

32、解决方案：直接使用先发生关系，因为C在60时刻离开，它只能在61时刻或更晚时刻到达所以每条消息都携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟若比消息发送时钟小，就立即将自己的时钟调到比发送时间大1或更多的值。在图b中，C现在到达的时间是61。同样D到达的时间是70。,51,三、时间戳Lamport算法怎么给事件分配时间（续）,为适应全局统一时间的需要，只需对此作一点补充即可，即在每两个事件之间，时钟必须至少滴答一下，如果一个进程以相当快的速度连续发送或接收两条消息，它必须在这中间至少滴答一下。在某些情况下需要一个附加条件：两个事件不会精确地同时发生，为了实现这个目标，我们可以将

33、事件所在的进程号附加在事件发生时间的低位，并用小数点分开。这样，如果在进程1和进程2中同时发生了2个事件，发生时刻都是40，则前者记为40.1，后者记为40.2。,52,三、时间戳-Lamport算法怎么给事件分配时间（续）,使用这种方法，分布式系统中将时间分配给所有事件的方法遵照如下规则：若在同一进程中a发生在b之前，则C(a)C(b)；若a和b分别代表发送消息和接收消息，则C(a)C(b)；对所有事件a和b，C(a)C(b)这个算法给我们提供了对系统中所有的事件进行排序的一种方法，许多其它的分布式算法也需要这种排序以避免混乱。,53,四、时钟同步算法,所有算法都有相同的系统基础模型：每台机

34、器上假设都有一个每秒产生H次中断的计时器。当时间到时，中断处理程序将软时钟加1，软时钟记录从过去某一约定值开始的中断次数。我们把这个时钟值记为C。更特殊的，当UTC时间为t时，在机器p上的时间值是Cp(t)，最完美的情况是对所有的p和t，有Cp(t)=t，换言之，dC/dt理想值为1。UTC：世界协调时间(Universal Time Coordinated)。GPS 系统中有两种时间区分，一为UTC，另一为LT（地方时）。两者的区别为时区不同，UTC就是0时区的时间，地方时为本地时间。,54,四、时钟同步算法（续）,真正计时器并不是每秒精确的中断H次，理论上当H=60时，计时器每小时应该产生

35、216,000个滴答。实际上，用现代计时时钟芯片可以获得相关的延迟是10-5，意味着一台机器每小时可以获得 215,998216,002范围的滴答，若存在某一常数，便有：,55,四、时钟同步算法（续）,计时器可以在它规定的范围内工作，制造商标明的常数是最大漂移速度。稍慢的、精确的、稍快的时钟如图2-27所示。,56,四、时钟同步算法（续）,若两个时钟相对于UTC时间以相反方向漂移，在它们同步后的t时间内，它们可能的差值为2t，若操作系统的设计者要保证每两个时钟之间的相差不超过，时钟必须至少在每/(2)秒内再同步一次（用软件方法），不同算法实现再同步的方法不同。,57,1.Cristian算法,

36、非常适合于只有一台机器上有WWV接收器，其它所有机器与它同步的系统。把拥有WWV接受器的那台机器称作时间服务器，算法是基于Cristian(1989)和以前的一些工作。每台机器以小于或等于/(2)秒的周期定期地向时间服务器发送消息询问当前的时间，时间服务器接到消息后就尽快回答含有当前时间CUTC值的消息，如图2-28所示。,58,1.Cristian算法（续）,当发送者得到回答后，就将它的时钟设为CUTC，但是这种算法有两个问题：第一个重要的问题是时间决不能倒退，若发送者的时钟快，CUTC将会比发送者的时间值C小，若把发送者的时间值直接改成CUTC会导致严重的错误，比如在时钟变化后，编译产生的

37、目标文件的时间早于时钟变化前源文件的修改时间。这种变化必须逐步进行，一种方法是假设将计时器设置为每秒产生100次中断，通常，每次中断将时间加10毫秒，当时钟需要慢下来时，中断服务程序每次仅加9毫秒，直到调整好为止。同样时钟要加快时，每次中断服务程序将时钟加11毫秒，而不是立即把时间调到所需要的值。,59,1.Cristian算法（续）,另一个小问题是从时间服务器端发送的应答到发送者要花费时间，这种延迟可能较大，而且随着网络负荷的改变而改变。Cristian的处理方法是试图测量这个延迟值。最简单的方法：发送者精确地记录从向时间服务器发送请求到接收到应答的时间间隔，假设起始时间是T0与结束时间T1

38、，他们都是通过同一个时钟来测量的，就算发送者的时钟与UTC有一定的差值，它所测得的时间间隔还是较精确的。在没有其它任何信息时，消息传送时间的最佳估计值是（T1-T0）/2，当应答消息到达时，消息中的时间值再加上此值就得到了当前时间服务器的时间估计值，如果理论上知道了最小的传送时间，那么与时间估算相关的其它性质也能推算出来。,60,1.Cristian算法（续）,如果知道时间服务器中断处理的时间和处理消息的时间，这样的估算还能进一步改进，设中断处理的时间是I，那么传输时间间隔为T1-T0-I，所以估算单向传输时间为它的一半。系统中确实存在着从A到B的消息和从B到A的消息传输路径不同，因此就有不同

39、的传输时间，但我们目前先不考虑这种情况。为了提高精确度，Cristian建议不要只做一次测量，而做一系列测量，测量中T1-T0超出一定范围就认为是网络阻塞，为不可信值。对剩余的测量值取平均值会得到较好的估算值，也就是说，最快返回的消息是最精确的，因为消息遇到阻塞最少，所以它最能代表纯粹的传输时间。,61,2.Berkeley算法,在Berkeley UNIX中采取了完全相反的方法，这里的时间服务器（实际是时间守护进程）是主动的，它定期地询问每台机器的时间。然后基于这些回答，计算出平均值并告诉所有的机器将它们的时钟拨快或拨慢到一个新的值。这种方法适合于没有WWV接收器的系统，时间守护进程的时间必

40、须由操作者定期地手工设置，这种方法如图2-29所示。,62,2.Berkeley算法（续）,(a),时间守护进程在3:00把它的时间告诉其它机器，并且询问它们各自的时间(b)，各机器将它们各自的时间与时间守护进程时间的差值告诉时间守护进程，(c)守护进程计算出它们的平均值，通知各机器如何调整各自的时间。,63,3.平均值算法,上述两种方法都高度集中的，有不足之处。存在一些非集中式算法，如：一种分布式时钟同步算法：它是将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于 T0+(i+1)R，这里的T0是过去某一约定的时间，R是一个系统参数。在每次间隔的开始处，每台机器根据自己的

41、时钟广播发送当前的时间，由于在不同机器上的时钟不可能完全同速工作，这种广播就不会完全同时发生。,64,3.平均值算法（续）,在机器广播发送时间之后，它启动本地计时器收集在S时间间隔中到达的其它广播，当所有广播到达后，执行一个算法，得到新的时间值。仅将这些值取平均值；最简单先除去m个最大值和m个最小值，平均其余值。去掉两端值可认为是一种对m个错误时钟发出毫无意义的时间值的一种自我保护。给每条消息值加上一个从源到目的地的传送时间估计值，这种估计值可参考网络的拓扑结构或计算试探消息的响应时间而得出,65,4.多个外部时钟源,对使用UTC进行同步又要求特别精确的系统来说，可给系统安装如WWV，GEOS

42、或其它UTC源的多接收器来实现的。时间源自身固有的不精确性以及信号传送的不定性，最好的操作系统能做的也只是建立一个UTC时间范围。一般来说，不同的时间源会产生不同的时间范围，这种范围需要机器和它们达成一致。,66,4.多个外部时钟源（续）,为达到一致，每个具有UTC源的处理机定期在每一UTC精确分的开始处广播其时间范围，但没有处理机会同时获得时间包，传输和接收延迟依赖于缆线的距离和包必须经过的网关数，它对于每一对UTC源和处理机之间都不相同。其它因素，如多台机器要同时在以太网上传输而发生的碰撞。更进一步，如一台处理机忙于处理以前的包，它可能在相当长的几微秒内不去理会到来的时间包，从而导致了时间

43、的不确定性。,67,4.多个外部时钟源（续）,解决：Open Software Foundation（开放软件组织）的分布式计算环境的处理方法某个接收器接收到所有时间源的UTC时间范围后，首先检查是否有与其他范围不相交的UTC范围。如果有，这些UTC范围一定是错误的，弃而不用。剩余的时间范围都是准确的UTC时间所在的范围；因此接着就求出这些范围相交的部分；最后将相交部分的中点作为准确的UTC时间，并将内部时钟设置为该值。,68,4.多个外部时钟源（续）,69,2.4.2互斥,涉及多个进程的系统使用临界区容易编程当一个进程必须读或修改某些共享数据结构时，它首先进入临界区获得互斥锁，保证没有其它的

44、进程能同时使用该共享数据结构。在单处理机系统中，使用信号量、管程和一些近似的结构来保护临界区。几个例子：在分布式系统中临界区和互斥是如何实现的。,70,一、集中式算法,在分布式系统中获得互斥的最直接方法是仿照单处理机系统的方法，选一个进程为协调者（比如在最大网络地址机器上运行的进程）。无论什么时候进程要进入临界区，它将向协调者发送请求消息，说明它想进入哪个临界区并希望获得允许。如果当前该临界区内没有其它任何进程，协调者就发送允许进入消息，如图2-30(a)所示。当应答到达时，请求者就可以进入临界区。,71,一、集中式算法（续）,现在假设有另一个进程，如图2-30(b)所示，请求进入同一个临界区

45、，协调者知道该临界区已有一个进程，所以不能同意该请求，最好的办法是发出拒绝允许应答。而在图2-30中，协调者回避应答，这样就阻塞了进程2，使它等待应答。另一方面，协调者还可以发送“拒绝请求”应答。两种方法都会把进程2放入等待队列，等待临界区的释放。,72,一、集中式算法（续）,当进程1从临界区退出时，它向协调者发送释放互斥消息访问，如图2-30(c)所示，协调者从推迟请求队列中取出最前面的进程，向它发送允许进入消息。如果该进程仍然阻塞（即，这是第一条发给它的允许进入消息）它去除阻塞且进入临界区；如果明确发送一消息拒绝它进入临界区，此进程应该不时地查询输入的消息，或者接着将它阻塞等待许可响应。不

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

47、mport关于时钟同步的论文中，后来Ricart 和Agrawale对它作了进一步的改进，算法前提：Ricart 和Agrawale算法要求系统中所有事件都是全序的。也就是说，对任何事件组如消息，哪个先发生必须无歧异。算法：当一个进程想进入临界区时，它要建立一个包括它要进入的临界区的名字、处理机号和当前时间的消息，然后将消息发送给所有其它进程。概念上讲也包括发送给它自身。发送的消息假设是可靠的，即每条消息都应该被确认，如可能应使用可靠的组通信，避免使用单个的消息通信。,75,二、分布式算法（续）,当一个进程接收另一个进程请求消息时，根据接收方的状态以及临界区的名字。有三种情况要加以区别：若接收

48、者不在临界区中，也不想进入临界区，它就向发送者发送OK消息。若接收者已经在临界区中，它就不必回答，而是负责对请求队列排队。若接收者要进入临界区，但是还没有进入时，它要将发来的消息和它发送给其余进程的时间戳对比，取小的那个，如果来的消息的时戳小，接收者发送OK消息，如果接收者本身的时间戳更小，那么接收者负责排列请求队列而不发送任何消息。,76,二、分布式算法（续）,在发送完允许进入临界区的请求后，进程将不做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区，它从临界区退出时，向队列中的所有的进程发送OK消息，并把它从队列中删除。,77,二、分布式算法（续）,分析：如果没有冲突，则正常工作

49、。但是，假设两个进程要同时试图进入一个临界区，如图2-31(a)所示,78,二、分布式算法（续）,进程0发出时戳为8的请求，而同时进程2发出时间戳为12的请求。进程1不想进入临界区，所以它向2个发送者发回OK。进程0和2同时发现冲突，比较时间戳，进程2发现自己的大，它只好同意进程0进入临界区，向0发送OK，进程0就把进程2的请求排在队列中，为以后处理用，自己进入临界区，如图2-31(b)所示。,79,二、分布式算法（续）,当进程0结束退出临界区时，它把进程2的请求从队列中取出，并向进程2发送OK，允许进程2进入临界区，如图2-31(c)所示。算法之所以能够使用，因为在产生请求冲突时，遵守按时间

50、戳排序，小时戳优先的规则。,80,二、分布式算法（续）,注意：如果进程2比进程0早发送消息，进程0在它请求进入临界区之前获得了进程2的请求消息，它允许进程2进入临界区，当进程2接收到进程0的请求时，它发现自己已经在临界区了，所以把进程0排在等待队列中。,81,二、分布式算法（续）,问题：互斥必须无死锁或无饥饿。每次进入临界区需要2(n-1)条消息，这里n为系统中的进程数目。最好的是不存在单点故障。若有一个进程崩溃，它就不能回答请求，这种不发言将被解释为不允许进入临界区，这样就阻止了任何试图进入临界区的进程。因为n个进程之一失效的可能性是单协调者失效的n倍，我们必须设法换一种n倍复杂和需要更多启