分布式系统原理与范型第二版复习资料

1、分布式复习资料第1章分布式系统 是若干独立计算机的结合，这些计算机对于用户来说就像是单个相关系统。硬件方面：机器本身是独立的。软件方面：对用户来说就像与单个系统打交道。重要特性：1、各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。2、用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。中间件：为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件层”组织起来。该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间。如图，这样的分 布式系统有时又称为中间件。廿鄆扒1计算机2L计K机、ttim4应用时A应用程序

2、H逼用程序C z n1本關*作系统2本地拘乍乘拔耳丄剛备图1. I件为中间件盥纵的分布式羸班*叩何忡层延呻到參合机祷上.且为毒个应用程序挫供丁梱同的接口注意层次分布与组件分布式系统的最 主要目标 是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源。透明性：如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就是透明的。 透明的类型：1、访问透明性：指对不同数据表示形式以及资源访问方式的隐藏。2、位置透明性：指用户无法判别资源在系统中的物理位置。3、并发透明性：在资源共享时，用户不会感觉到他人也在使用自己正使用的资源。4、故障透明性：用户不会注

3、意到某个资源（也许他从未听说过这个资源 ）无法正常工作，以及系统随后 从故障中恢复的过程。开放性：一个开放式的分布式系统，是根据一系列准则来提供服务，这些准则描述了所提供服务的语法和含义。互操作性：刻画了来自不同厂商的系统或组件的两种实现能够在何种程度上共存并且协同工作，这种共存和协同工作只能依赖于通过双方在公共标准中规定的各自所提供的服务来完成。可移植性：刻画了这样的性能，如果为分布式系统 A开发了某个应用程序， 并且另一个分布式系统 B与A具有相同 的接口，该应用程序在不做任何修改的情况下在B上执行的可行程度。可扩展性：当一个系统需要进行扩展时，必须解决多方面的问题。首先考虑规模上的扩展。

4、在需要支持更多的用户或资源时，我们常常收到集中的服务、数据以及算法所造成的限制，如图所示。例如，许多服务是以集中的方式实现的，它们由分布式系统中一台特定的计算机上运行的单个服务来提供。这种方案存在的问题是显而易见的：用户增多时该服务将成为系统的瓶颈。即使它拥有无限的处理能力和存储能力，在系统达到 一定规模后与该服务器的通信也将发生困难。从而使得系统规模无法继续增长。11 / 37概念-实例集5贞服务1供所有用户切河的单，嫌务器.荣中戌数据1甲亍花线电诂溥1机猶宪幣的倍息来安持路由ffi 1.3 可扩艇性限制的宝例扩展技术：1、隐藏通信等待时间对于地域扩展是比较适用的。基本想法：尽量避免等待远程

5、服务对请求的响应。例如，当对远程计算机的某个 服务发出请求时，在发出请求端，除了等待服务器响应之外，还可以利用这段时间做其他工作。本质上，以这 种方式构建的 应用程序使用的异步通信。 当响应到来时，应用程序产生中断， 并且调用专门的处理程序对前面 发出的请求进行处理。2、分布技术分布技术把某个组件分割成多个部分，然后再将它们分散到系统中区。3、缓存缓存是复制的一种特殊形式。与复制相同，缓存一般是在访问资源的客户附近制作该资源的副本。然而，与复 制不同的是，是否进行缓存是由要访问资源的客户决定的，而不是由资源拥有者决定的。缓存和复制都存在严重的缺点，这些缺点可能会对可扩展性造成不良影响。进行缓存

6、或者复制以后，由于资源 存在多个副本，修改其中的一个会导致它与其他副本不相同，从而导致一致性方面的问题。集群计算：底层硬件是由类似的工作站或PC集组成，通过高速的局域网紧密连接起来。而且，每个节点运行的都是相同的操作系统。11ta件if ff机财*1 LC 0：群计轩斋疑的个看例网格计算：组成分布式系统的这种子分组通常构建成一个计算机系统联盟， 其中的每个系统归属于不同的管理域，而且在硬件、软件和部署网格技术上也差别很大。光纤层：在特定站点提供对局部资源的接口。这些接口都进行了定制， 以允许在某个虚拟组织中实现资源共享。连接层：由通信协议组成，用于支持网格事务处理，延伸多个资源的使用。 例如，

7、用于在资源之间传输数据或从远程地点访问资源的协议。另外，连接层还有安全协议，用于进行用户和资源的认证。图1+7网格计”算系统的分层 体系结构资源层 ：负责管理单个资源。它使用由连接层提供的功能，直接调用对光线层可用的接口。汇集层 ：负责处理对多个资源的访问，通常由资源分派、把任务分配和调度到多资源以及数据复制等服务 组成。连接层和资源层由相对较小、较标准的协议集组成，而汇集层由很多用于不同目的的不同 协议组成。应用层 ：由应用程序组成。谒求斜层工层i(b)图2分层（叮和圣于对象的（b|*系结构样式组件组件爭半传送C发五组件圈巳2基于事件5）和共享數帼空间（計的体系结杪样式客户一服务器模型分为三

8、层：1）用户接口层2）处理层3）数据层多层体系结构用户樓口用戶接n用戶接门! ” ，十1* 4-f iff诵戶接口 J 1 - 应誦序1宓用現序1应用理序=命程序1敕描眸1用户接2 耳用程帛数据卿 |阖2.5 呑种吝丹眼旁辭蛆媪站构（扩讥）第2章体系结构样式：1、分层体系结构2、基于对象的体系结构3、以数据为中心的体系机构4、基于事件的体系结构点对点体系结构：在结构化的点对点体系机构中，覆盖网络是一个确定性的过程来构成的。这个使用最多的进程是 通过一个分布式哈希表来组织继承的。超级对等体：能维护一个索引或者充当一个代理程序的结点。控制管理多个常规对等体。边界服务器系统。这种边界是由企业网络和实

9、际的因特网之间的分界线形这种系统部署在因特网中，服务器放置在网络的“边界” 成的。协作分布式系统混合结构主要部署在协作式分布式系统中。在很多重要的系统中，主要问题是先启动起来，因为经常会部署一个传 递的客户-服务器结构。一旦某个结点要加入系统，就可以使用完全非集中式的组织结构，用于协作。自治计算：以高级反馈控制系统的形式来组织分布式系统，允许自动自适应变换。也叫做自主系统。自适应的多样性：自我管理、自我恢复、自我配置、自我优化等。反馈控制模型不町柠琴说干挖丿嗥面P團16 反沖控抽痰统的逻曲级级鮎构反馈控制系统的核心由需要管理的组件形成。这些组件能通过可控输入参数驱动，受干扰或噪声输入的影响。系

10、统本身需要被监视，因此需要对系统各个方面进行测量。 但是实际测量很难做到， 就需要一个逻辑 尺度预测组件 控制循环的核心部分是反馈分析组件，分析上述测量值，并把它们与参考值进行比较。包含了决定自适应的各种算 法。第三章线程为什么要使用线程？虽然进程构成了分布式系统中的基本组成单元，但是实践表明，操作系统提供的用于构建分布式系统的进程在粒度 上还是太大了。而就粒度而言，将每个进程细分为若干控制线程的形式则更加合适，可以使构建分布式应用程序变 得更加方便，获得更好的性能。进程间通信机制IPCS1 :从川户卫问屮極划1内帳空同14樓件果蜒S2AVJftlfA Fl巒mi t肿汴IS2,再从内核模式切

11、换到用户模式S3。IPC需要内核干预。从用户模式切换到内核模式 S1,在内核中进行上下文切换 完成进程之间的切换。多线程客户隐藏通信时间延迟的常规方法是启动通信后立即进行其他工作。例子：Web浏览器。Web浏览器一般在开始获取 HTML页面后随即就显示它。为了尽量隐藏通信时间延迟，某些浏览器在接收数据的过 程中就开始显示这些数据。首先将文本显示出来，并提供页面滚动之类的功能，同时获取组成页面的其他文件，比 如图像等。用户不必等待浏览器取得整个页面的所有组件就能够查看页面。从效果来看，web浏览器好像在同时进行多任务一样。只要取得了主HTML文件，就可以激活多个独立的线程，它们分别负责取得页面的

12、各个部分。每个线程都与服务器建立一个独立连接以获取数据。多线程服务器虚拟化U） frrt*個的fttflMNri b tt A位于豪址11之上訥朗眞创恂计算机界面1）由机器指令组成，可由任何程序激起的硬件软 件界面。2）由机器指令组成，只有特权程序（如OS）才可激 活的。3）由操作系统提供的系统调用组成的界面。4）由库调用组成的界面，通常形成了所谓的应用程序编程结构（API）。很多情况下前述的系统调用由API隐藏。虚拟化的实质是模仿这些界面的行为。虚拟化可米用两种方式。图秘命爭gw用tv睜扁运衬时橋址3.7I廉忙机Hi观器.Iftfr*牛应用軒痔和幡悄乖嫌第一种：可以构建一个运行时系统，实质上

13、提供一套抽象指令集来执行程序。指令可以被翻译执行，也可以仿真执 行，就像在Unix平台上运行 Windows应用程序。（或其他硬件）的界面。这个界面可以第二种：提供一种系统。把它做成一层完全屏蔽硬件但是提供一个同样指令集同时提供给不同的程序。可以有多个不同的操作系统独立并发地运行在同一平台。客户端软件与分布 透明性靑户机脈务器I羁务罰2巖活爲3圈:i. If 俺用需尸端解决方案*谢旳地剂本股晋器客户端通过将调用请求转发给每一个服务器的副本来达到复制透明性。服务器组织结构：1）迭代服务器：自己处理请求，并且在必要的情况下将响应返回给发出请求的客户。2）并发服务器：并不自己处理请求，而是将请求传递

14、给某个独立线程或者其他进程来处理，自身立即返回并等待 下一个请求。或者每收到一个输入请求都派生出一个新进程来对其进行处理。多线程服务器就是个特例。3）状态无关服务器：不保存其客户的状态信息，而且也不将自身的状态变化告知任何客户。如Web服务器，仅仅对输入的HTTP请求做出响应，在处理请求的时候，彻底忽略用户的存在。软状态：有一种特别的状态无关设计是服务器维护软状态的信息。服务器仅维护一小段时间的客户状态。时间 到期后就删除相关客户信息，到无状态行为。4）状态相关服务器：一直保存客户端的信息直到显式地删除。如文件服务器，它让客户保留文本的本地副本，甚 至进行更新操作。端口：客户总是向服务器所在机

15、器上的端点发送请求，这种端点就是端口。ihi为请止鵬 竹琏厳务器图 3. 11利用守护乾序来进行睿户脏务歸轉定快用副经噩务t垠逋行需小舉等器轉從a）有许多服务不需要 预先分配好端点。比如，一个时间服务器可能会使用由本地操作系统动态分配给它的端点。在这种情况下，客户首先必须查询到该端点号。一种解办法在运行服务器的每一台机器上都运行一个特殊的守 护程序，该守护程序负责跟踪位于同一台机器上的服务器实现的每一项服务所使用的当前端点。守护程序还监 听一个已知的端口。客户通过这个端口与该守护程序进行联系，请求得到指定服务器的端点号，随后再与该服 务器进行联系。b）与其对这么多被动进程进行跟踪，不如由一个超

16、级服务器来负责监听所有与这些服务关联的端点。当收到请求 时候，派生出一个进程以对该请求进行进一步处理，这个派生出的进程在处理完毕后自动退出运行。中断服务器 工作：处理通信中断的更好方法是在开发客户程序和服务器程序的时候考虑到对带外数据 发送的支持。带外数据 是服务器在处理客户发送的其他所有数据之前必须处理的数据。一种办法是让客户将带外数据发送到一个另外的控制端点，服务器则监听该端点，同时也监听常规数据传输的端点。另一种方法是通过发送原始请求所使用 的连接来发送带外数据。当交换机接收到一个 TCP连接请求时，找到处理这个请求 的最佳服务器，把请求包转发给这个服务器。服务器反过 来发送一个响应给客

17、户，同时把交换机的IP地址也放入数据段。这种纠织结樹糟致栩图L 1（1瞬狀的JIHPeterman尊的中的信任蛙歩所描述的管 理结构.它们的关系如下，U）结点拥有巧把它的结点加人一个霁理授权耆的悴理域如集合址的话可能会限制 便用 叽评理授桩扑握供必需的较件用于熾加一个结点给PhnetLab.脏务捉供呂洵普理授权者注册*伯任它去提供良好行为的第点（O眼务捉供者联系切片挖权者在细结虑匸创it-牛切片拓切片攪权宵需變认证服务捉供宵.（6第贞拥有秆为切片授权托提供切片创程眼务用以创建幼片.它实质上让切片段杞 舞町以使用它的资源.7）怦理般权占把切片创建的隹务妥托辭切斤授叔？J ,第四章通信OSI模型是

18、用来支持开放式系统间通信的。开放式系统通过一系列标准规则来与其他开放式系统通信的系统。闻用层舍话厘判1斶层会话协谊MMaM!-=- W网络协过每一层都规定了与上一层的接口。 括一组操作，定义向用户提供的服务。接口中包ffl 4 I )ST 3?申的圧、播口面向连接的协议：消息发送方和接收方必须首先显式地确立连接，可能还需要就采用的协议进行协商，然后才能进 行数据交换。在通信完毕后，必须终止连接。如电话系统。无连接的协议：交换数据之前不需要有建立连接的过程，消息发送方只需要在准备好的时候传送第一个消息即可。如将信件投入邮箱。計世衲种厅珂厂剛绪忙fii k 厂传桔臬卑灵 L佥佶區报头Ir谀点圧柑畫

19、L应甲朋州央MB1=丄N出理楼I車各二的仏ffi 4.2血h（绪I传输的鼻刘?fia如果机器1上的进程A想传消息给机器2上 的进程B。那么消息先到机器 1上的应用层， 依次向下传递，每传递一层，就在消息前增 加一个报头。第n层添加的报头中的信息是 供第n层协议使用的。某些层还要增加报尾。44 / 37物理层只负责传输位，而 数据链路层 是负责检查传输是否出错。数据链路层在每一帧的开头和结尾分别放置特殊的 位来对头尾进行标记，并用某种方法将帧中的所有字节相加，计算出校验和。再将校验和放入帧中。当接收到消息 后，接收方重新计算校验和，跟原有进行比较。目前应用最广泛的网络协议就是无连接的网际协议（I

20、P）。调用远程过程从矚用返冋谓用本地过程 丼返回蜻果at(|图山飞容户与服务器之间的RIH：的原理远程过程调用包括以下步骤 ：1）客户过程以正常的方式调用客户存根2）客户存根生成一个消息，然后调用本地操作系统3）客户端操作系统将消息发送给远程操作系统4）远程操作系统将消息交给服务器存根5）服务器存根提取参数，然后调用服务器6）服务器执行要求的操作，操作完成后将结果返回给服务器存根7）服务器存根将结果打包成一个消息，然后调用本地操作系统8) 服务器操作系统将含有结果的消息发送给客户端操作系统9) 客户端操作系统将消息交给客户存根10) 客户存根将结果从消息中提取出来，返回给调用它的客户过程。传递

21、引用参数?异步RPC汰】的实现fr：悴理序炖攻 作卜世调用k=*dd(L j)|in( vatfU inc： 2町)暮户存帼口务器的冷作爭氓滴息mr：: val0)4,7適过RPC进行远穆计茸的歩篠*户等特堵黑F7回用远輕从谢用屮过稈 /返问谪求/脛祥融當看匸闇本地連了 SrNT=幷越冋姑果U)閉用述阵从诅书中辻程 返何请求、/按受请求*?B- -M ML VMl陋笛詩rr 何-(b图4+ 10 KPV中無户-眼存褓间购交坯过楼(p砖址RP中需八-限务器间的？!矿过丹t bi使HI异兀RPC时的空互过胖在异步RPC中，服务器接收到 RPC请求后立即向客户端发送应答，再调用客户端请求。应答的作用

22、是向客户确认服 务器已准备开始处理该 RPC请求。客户收到服务器的确认消息后，将不再阻塞，而是继续向下执行。延迟的同步RPC中貽書1调用含单向 RFC的卒门图I.】1窩户樹脂帝器诵讨曲节#毎RFC讲荷奁圧远程服务器在处理请求时，客户同时做一些其他的事情。当服务器处理好请求时，返回结果去中断客户，服务器端变成发送端，实现第二个异步RPC 套接字：一种通信端点。如果应用程序要通过底层网络发送某些数据，可以把这些数据写入套接字，然后从套接字 读出数据。原语含义socket创遇新的通信端点bind|将本地地址附加到套接孑上IlMCn宣布已准备好援受连捲accept住收到连接请求之训阻赛调用方conne

23、ct主茹尝试确立连接send:通过连矗发恋数据1receiveSil连接接收敎据close释杈连援图 N TCP/J卩套接字原语服务器一般执行前 4个原语，一般按照图中顺序执行。调用套接字原语的时候，调用者创建一个新的通信端点，用 于某种特定的传输协议的。图4. 15使用仝接字的面向连抿通信模式MPI的先进之处：程序的硬件独立性需要导致MPI的出台。MPI是为并行应用程序设计的，是为瞬时通信量身定做的。它直接使用的是底层网络。含Q MPLbsend蒋咚送出的消息迫加到冷地发送缓冲区中MPLsend发送潸息并祐待賀到消息僵制到本地或远程缓冲区中为止MPLLscnd发送消息 1II巾按收方丄动（C

24、）消息进入接收方的消息队列时，接收方 不必处于运行状态。发送方和接收方可以彼此完全独立地 运行。伸用臥列帖松敢耦弭通信的I种泪令方式图4.吗限利81说址与网塔塑编址之同的艾拓消息队列系统的队列集合是分布在多台机器上的，因此需要维护一个从队列到其所在网络位置之间的映射关系。个数据库，存储到网络位置所对应的队列名。B。发送方A只需要找到最近的路由器，并将队列发送给路由器。路由器负责接下来寻找路径将消息发送给接收方 采用这种方式，只有在路由器需要添加队列或者删除队列时进行更新，其他队列管理器只需要知道最近的路由器的 位置即可。消息转换器：的消息处理，需要消息转换器，是队列网络中负责转换消息的特定结点

25、。对于消息队列系统来说，消 息转换器也不过是一个应用程序而已。异步传输模式：流中的数据项是逐个传输的，但是对某一项在何时进行传输并没有进一步的限制。这是采用离散数 据流时常见的情况。比如文件的传输。同步传输模式：数据流中每一个单元都定义了一个端到端的最大延迟时间，容许延迟。数据单元的传输时间是否远远小于最大允许延迟并不重要。等时传输模式：数据单元必须按时传输， 端到端的延迟时间同时又上限和下限。这个上、下限也称为边界延迟抖动。在视频和音频方面很常用，比如音视频的同步（对口型）。圈16用于匕存话的導舉悴数翳的哉眸输的再户臓务器休系络恂QoS服务质量特性：1）数据传输所要求的比特率2）创建会话的最

26、大延时（比如应用程序何时可以开始发送数据）。3）端到端的最大延时4）最大延时抖动5）最大往返延时。从瀬地出”的竝抿悝|l p 1 4斤卜到达IS沖区的故期包 + 习卩|出目0E从if神区移出的1H她 -钿冲【3的咖 电內目內目甘甘电网孜I刃隔时间|秒|罔1.27 筑用履沖帆电械少抖功当数据包有不同的延时，接收方先把它们存储在缓冲区，当总是有足够的数据包进入缓冲区时，接收方就可以以固 定的速率把数据包传递给应用程序。|旦回Pl划殛回回H回回回画u件込 m SEp SHH3IE &回回回回回应!占安的 RE 回 |回日回回E ?: U a辺也回冋|已传送国叵|0国回因回回回回回回m|H回 去先的輛

27、(b)L2S 独据包棗的姑来卩龙辟吿h女铝仿辅如在传送音视频时，采用交错传输，丢失的帧分布较广，这样丢失的就不是一大段而是零散的帧，对于音视频的播 放影响就较小。但是这样需要更大的缓冲区，因此程序的开始延时更高。流同步W 4.29朋敎摇甲朮恳次上谨行显式同步的谦理用应用程序进行同步覆盖网络多媒体中间件提供接口控制视频和音频流。设备和流都有自己的高级接口。中间件层负责处理同步。每个MR 4. T1構盘IM蜡的祎捲柏实际岡堺空屮略由胖的链馥之何的死信息传播模型 anti n tropy结点P随机选取另一结点Q,然后与Q交换信息。更新信息的方法:1) P只是把自己的更新信息发出给Q,基于push的方

28、法2) P只是从Q那里获取更新，基于pull的方法3) P和Q相互发送更新信息给对方，基于push-pull的方法第5章命名系统名称是用来与实体当前位置无关的方式来定位它们。名称与实体的位置可能毫不相干。访问点：用来实体的一种特殊实体。地址：访问点的名称。所以访问点就是实体的地址。标识符属性1）一个标识符最多引用一个实体2）每个实体最多由一个标识符引用3）一个标识符始终引用同一个实体（也就是说标识符永远不会重新使用） 地址&标识符地址和标识符都是名称类型，但是用于不同目的。地址是用于访问实体的，找到实体的位置，而标识符不一定与实 体的位置相关，只是一个使得实体区别于其他实体的标志。广播&多播广

29、播：包含某个实体所用标识符的消息会广播到每台机器上，请求每台机器产看它是否拥有该实体。拥有该实体的 机器发送回复消息，消息包含访问点的地址。但是随着网络的扩大，越来越低效。多播：只有符合条件的一组机器才能接收到消息请求。转发指针零阿的务對輻进IW才与B可I用相的閑乳1低用 奪门坪帆.服界禧存根心扌的轻雄帝忡的匝抨链长，断的可能性大，可靠性差当对象从地址空间 A移到B时，会留一个客户存根在 A中，一个服务器存根在 B中。服务器存根要么包含实际对象 的本地应用，要么包含该对象远程客户存根的本地引用。in 2 通说在中总轄-个掾秤亲申定向转发祈計对象调用携带一个客户存根的标识，这是调用发起的地方。当

30、调用到达位于当前位置的对象后，会向发起调用的客 户存根发送回一个响应。当前位置中包含了对象的当前位置。客户存根会把自己的对应服务器存根调整为对象当前 位置中的那个服务器存根。宿主位置：创建实体的位置。分布式散列表分层方法:耳!* 9A18SI7gno:21石;辽rib从结 ftffrf k从站点2K 鮮析址=E+2)111 山14Tk讐罚 M 在Chord系统沖从结点1裁析剪值26.詰解析辭们 吃T7%41599土93914142011UL:3林A2K542022032X2$5412$342($5|W H录结也顶级咸T5域中的口或结卫dirfS)、可瞅鹹下的一卜了域& 也含在丁中 %腐域，包含

31、在5中图5. 5把定也般务划分为域的分层纽帜，毎几威都梱冇关联的甘玻给点cm域D2域DI肌琬“瞰們字段 年口桶向N阴宿串卜：不會戡据的字啟W Vl位同 / i己余.含肓-个地址十结壷M处的V rt的位直吃汞M图S.-G实休信宜存储示例过凰的实棒在不同的叶域申蚂有的6地址-結口中自有e的 记录因此把请 衣箕井给工结更经划哨E的记录, 凶此巴洁济转龙餡 它曲了结点图5.7在分层绢织的毎位脱务中的位置杏找结点有E的记录，/入请求hoH：Cnl存粘在的数据叶纳点o 冃录站点匚j.rmrepM hh hume/steen keys*圈壬B雲新操作估摘爪请欢被转发到第一卜划迄实体E的结日4厲】传发搐向叶纳

32、点0勺皓仲所昭曲的徒链接；n2：Mclkc nmaxl_ 4;stcvn _厂inax图云11命名图中侨讲述的符号链響的就念用于蚪审習射空间 的名林服舟器指向外踊苦林空间杓引用阳竄12翅过持定的/阿孙坟捷量赵程君称空间挂载在涉及多个命名空间合并使用的时候，会出现挂载，从这个命名空间挂载到另一空间。访问另一空间的地址。存储结点标识符的目录结点称为 挂接点。外部名称空间中的目录结点为 挂载点。名称空间的分布全局层：由最高级别的结点组成，由根节点和根节点的子节点组成。涉及到统筹。特点：通常是稳定的，目录表很少改变。可以用来代表组织或组织群。行政层：由那些在单个组织内一起被管理的目录结点组成。特点：代

33、表属于同一组织或行政单位的实体组。虽然会改变，但通常也是稳定的。管理层：由经常改变的结点组成。涉及到个体。在可用性和性能方面，每层的名称服务器都必须满足不同的需求。性能问题：因为全局层结点变化不频繁，所以查找操作的结果一般会长期有效。所以客户可以缓存这些结果。当再 次执行同样的操作时，可以直接从缓存中获取结果，而不用再调用名称服务器。所以，全局层的名称服务器不需要 快速响应单一的查询请求，需要较大的吞吐能力。f備I4局层行政展|网培的拔理粘国世界苞圉组织I少许i萱甸响应HJSI更扁的替播情况延迟立即许多没有是否采月售尸端綬存是丽阡5, 11为大舉名称空剧所风的全前展，冇玻圧和常理层实现结点的笛

34、称狠奇嘉N间的比牧迭代名称解析：名称解析程序把完整的名称转发给根名称所在的服务器。服务器每次解析后都将结果返回给客户。上T1I,悒竖即：2.cs, ftpJ.盲尸的容栩 轉析氏序4. “VvuF叫3.心ftr4H vftp眼畜和；服务購川結也中同-哪务萎”二 音理的结点艸结璃结占冬5* I 了迭优兽称解析金坤递归名称解析：名称服务器会把结果传递给它找到的下一台服务器，解析的结果保存在当前服务器。当最后一台服 务器解析结束后，会依次向上取出解析结果，最后汇总到根名称服务器，统一发送回客户。递归名称解析优点：1）与迭代名称解析相比，缓存结果更为有效2）减少通信开销KI递旧畠称解析喜尸一 7送代專称

35、解析远距髙通信茎5.眉遲归宓称辭析与选代喀称能析在適信开销方面的对比目录服务：基于属性的命名系统。实体有一个可以用于查找的相关属性集。如电子邮件系统中，可以用发送者、主 题等属性来标记邮件。资源描述框架RDF统一资源描述方法。RDF模型的基础是，资源用由主题、断言和对象组成的三联体来描述。如(Person,name,Alice)，主题是 Pers on,断言是n ame,对象是 Alice。第六章同步化物理时钟：计时器。IS 16 17 18 19 21 22 23 M 25 末阳秒 H-H I I J HI一I一I7 t I II-一1卜 ” I III 为了与TAI樑持同步,/ 社UTC中

36、引人舗轴谭為所毎的 计算机2M52146mitpig械刨违2147-本地时钟的T 时何编辑器所在的 计算机医6-12U22143214*12145車抱时钟的1*11 时问uutputx被创建当梅台机黙都有它自己的时钟时个堆牛于号一牛 頊件之首的事件可能会械标迅上狡早的时间阳反占TAI戦辰度恒宦.与太朋秒不冋“当需笈勺太阳保持一裁时引人闺秒时钟同步算法最大偏移率冇在某一常数pt使得*1-応穽W】 + pUTCJ &,5晋时钟以不问的遼事漓答吋,时钟时间和in之闸的关系图匸6从一个时问服芳轿樹到当前吋问达到的吋间T“假设A A JJ B的传綸延时与从R到工的大致相同*即T.-TT.- n, 这样，

37、A就可以计算出与B的财间俑差*,、 下 （TE -T-kT. 一丁J _ （T.-T + CT. -TJ日=a2参考时如果时钟A落后，那么可以在每个中断添加时间来调整。调整的时钟要参考另一个时钟，另一个时钟被称为 钟。逻辑时钟：机器的相对时间，不一定与实际时间相同。先发生：b “ a在b之前发生”1）如果a和b是同一进程中的两个时间，且a在b之前发生，则ab为真2）如果a是一个进程发送消息的事件，而b作为另一个进程接收这个消息的事件，则b也为真。pjTlo2636亦566d76s6wbo白己旳吋忡I峯乩9 1/mpo理箱法楼正三牛进趕的不同时钟再发送到下一个进程后，如果时钟小于或等于当前进程，

38、那么把后一进程的时钟改为当前进程时钟+1,并且把下一进程以后的时钟都要按照原来的间隔延后。比如P2中56改为61后，那么后面的64也要改成69, 72改为77, 80改为85。向量时钟Lamport时间戳不能捕获 因果关系，而向量时钟可以。区另U?分配给峯件日的向蜻时钟VC（a）具冇卜列性质t如果对某一罪件X有VlXaXVC “儿那么从为事件占柱囚果关系上光T1F件S向出时钟的创建是通过止毎bit程P地护 一个向掾VU来完戍的该向鈕貝有下閒曲牛性歳*（1）vcij是到目阶为止进程珂发生的爭件的数塑；C2）饷果VCLJ-kU么进程P.XUj02ff程叽叩已经发生丁 k牛事件.为此，巳他道F 的逻

39、辑时冋。“車一个弊旗是连过住进禅P；中的劉中件发生时血增VCi）k维护的第二个性质魁 通过任所发送的淸息中携带向曲来继护的.特別地，执行以F歩骤；CD在执行一个事件之前（如在络1冶诜一亍消息传送一个消息给应州稈冷或者 其他内殊事件）卫执行Gir vccn+i2）洋进程匕爰送亍谢息m结F时+在抗行繭面的步软后把m的时间餓Me）设 置肯等于TC*（引 在接收柑巳m时.迸零比暹过为娥牛*设普vq：kmaxne. 13强谢啊耒週伯互斥算法1、集中式算法何（b）（c）谢SJ4心）遷裡1请家询作者准许访问建-亨费殺+请朮導到r崔许；（bi然石进昶乂也清求唯许共拱斎源，协件靑不希许I 进程I #释放资沥时遴

40、知协杵者，得咋丰養厉对进程2做出应件进程在使用资源时独占资源，当有其他进程发送请求时，放入到请求队列中。2、非集中式算法每个协作者都被复制了n次。某个进程要访问资源，只需从 mn/2个协作者中获取多数投票即可。3、分布式算法当一个进程要访问资源时，发送一个消息给所有其他进程，包括自己。当一个进程接收到消息时，做出判断1）若接受者没有访问资源，也不想访问，就返回一个OK消息2）若接受者已获得访问，就不应答看，并将请求放入队列中3）若接受者也想访问资源但尚未访问，就比较收到消息的时间戳和自己发送消息的时间戳进行比较，早的获胜。如果发送者获胜，接受者就返回OK。否则接受者将获得访问，不应答，然后将请

41、求消息放到队列中。卜00K齿冋资沥W0W fi- is1）西伞老稈伺时鉴谕何1仆扶卩當諱t lb）退屁0貝有曲早梵时间戳*昕它获柑：（c）当进程0完眦吋，它峑送一个OK2堆馥4、令牌环算法将进程以环状连接到一起，每个进程只需知道谁在它的下一位上。设置一个令牌，每个进程进行传递。每个进程得到令牌后，看自己要不要访问资源，如果要，就执行。进程执行结束后，把令牌向下传递。如果不 要访问资源，就直接把令牌向下传递。四种算法比较丘二前的延迟血寤衣划集中式32协作者崩溃莽聲中式Jmk, K=L2h.2m会发生汎零效華低廿布式2仙一门2(n-l)r任何进程就溃i夕牌环O*n-1令牌丢先，进程崩瘟5.17 阿

42、网互斥算魅的比较欺负算法 当任何一个进程发现协作者不再响应请求时，它就发起一次选举1）P向所有编号比它大的进程发送一个ELECTION消息2）如果无人响应，P获胜并称为协作者3）如果有编号比它大的进程响应，则由响应者接管选举工作。P的工作完成。以前的协件晋已耐ftb)jo(d)(e)图6,20 歆负选游算法5逬理4主特一牛&畢丨(b)遴椁5却点进仃吗显、吿非邊程4停止烹皐：“】逬程5和&此卅齐0 11T5 M5*i (d) jfiR Al进界亍舒止遶4h进韩扳秩井時皿每卜谨丹当有ELECTION消息到达时，接收者回送一个 0K消息给发送者，表明自己仍在运行，并接管选举工作。最终除了一 个进程外，其他进程都将放弃，这个进程就是新的协作者。它将获胜的消息发送给所有进程。当以前的一个崩溃了 的进程恢复过来时，它将主持一次选举。环算法当任何一个进程发现协作者不工作时，它就构造一个带有它自己进程号的ELECTION消息，发送给后继者。如果后继者崩溃，就跳过崩溃的进程，继续往下走，直到找到一个正在运行的进程。每一步，发送者都将自己的进程号加 入到消息中，使自己也成为协作者的候选人。最终消息返回到发起选举的进程。当发起者接收到包含自己号的消息，识别出这个事件，选出进程号最大的作为协 作者。然后消