资源描述
分布式复习资料第1章分布式系统是若干独立计算机的结合，这些计算机对于用户来说就像是单个相关系统。硬件方面：机器本身是独立的。软件方面：对用户来说就像与单个系统打交道。重要特性：1、各种计算机之间的差别以及计算机之间的通信方式的差别对用户是隐藏的。2、用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。中间件：为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件层”组织起来。该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间。如图，这样的分布式系统有时又称为中间件。计算机I计草机2计篦机m计算机4一一一i:；!应用裡卑A应用程序B应用程序廿帝盘系统层（中闻件i本地操作系统l|本地損作系蹟2木地揮作系轨3本地加乍聚境4.1.1作为中问件组织的井布式廉如中间件层延神到f雾台亂謂上，且为每个应用程序提供了村同的接口注意层次分布与组件分布式系统的最主要目标是使用户能够方便地访问远程资源，并且以一种受控的方式与其他用户共享这些资源透明性：如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式系统就是透明的。透明的类型：1、访问透明性：指对不同数据表示形式以及资源访问方式的隐藏。2、位置透明性：指用户无法判别资源在系统中的物理位置。3、并发透明性：在资源共享时，用户不会感觉到他人也在使用自己正使用的资源。4、故障透明性：用户不会注意到某个资源（也许他从未听说过这个资源）无法正常工作，以及系统随后从故障中恢复的过程。开放性：一个开放式的分布式系统，是根据一系列准则来提供服务，这些准则描述了所提供服务的语法和含义。互操作性：刻画了来自不同厂商的系统或组件的两种实现能够在何种程度上共存并且协同工作，这种共存和协同工作只能依赖于通过双方在公共标准中规定的各自所提供的服务来完成。可移植性：刻画了这样的性能，如果为分布式系统A开发了某个应用程序，并且另一个分布式系统B与A具有相同的接口，该应用程序在不做任何修改的情况下在B上执行的可行程度。可扩展性：当一个系统需要进行扩展时，必须解决多方面的问题。首先考虑规模上的扩展。在需要支持更多的用户或资源时，我们常常收到集中的服务、数据以及算法所造成的限制，如图所示。例如，许多服务是以集中的方式实现的，它们由分布式系统中一台特定的计算机上运行的单个服务来提供。这种方案存在的问题是显而易见的：用户增多时该服务将成为系统的瓶颈。即使它拥有无限的处理能力和存储能力，在系统达到一定规模后与该服务器的通信也将发生困难。从而使得系统规模无法继续增长。概念实例集中武服务供所有用户切问的单个蔗务器i集中式数据甲个花线电话簿1集中式算袪1根10芫整的信息来安措路由图L3M扩展性限制的宴例扩展技术：1、隐藏通信等待时间对于地域扩展是比较适用的。基本想法：尽量避免等待远程服务对请求的响应。例如，当对远程计算机的某个服务发出请求时，在发出请求端，除了等待服务器响应之外，还可以利用这段时间做其他工作。本质上，以这种方式构建的应用程序使用的异步通信。当响应到来时，应用程序产生中断，并且调用专门的处理程序对前面发出的请求进行处理。2、分布技术分布技术把某个组件分割成多个部分，然后再将它们分散到系统中区。3、缓存缓存是复制的一种特殊形式。与复制相同，缓存一般是在访问资源的客户附近制作该资源的副本。然而，与复制不同的是，是否进行缓存是由要访问资源的客户决定的，而不是由资源拥有者决定的。缓存和复制都存在严重的缺点，这些缺点可能会对可扩展性造成不良影响。进行缓存或者复制以后，由于资源存在多个副本，修改其中的一个会导致它与其他副本不相同，从而导致一致性方面的问题。集群计算：底层硬件是由类似的工作站或PC集组成，通过高速的局域网紧密连接起来。而且，每个节点运行的都是相同的操作系统。主结点计点井行应刑程序俎件井厅库本地刪乍乘统本地掾忤系纸1ii算椀洁点计草机站点井肓应同程庁迥牛并行应用槪序迴件本地噪悴糸本地擱年系竦1kk远程访诃标准网觀悶给图集群计算落班两个示制应用层汇東层连接Y育源层光纤层网格计算：组成分布式系统的这种子分组通常构建成一个计算机系统联盟,其中的每个系统归属于不同的管理域，而且在硬件、软件和部署网格技术上也差别很大。光纤层：在特定站点提供对局部资源的接口。这些接口都进行了定制，以允许在某个虚拟组织中实现资源共享。连接层：由通信协议组成，用于支持网格事务处理，延伸多个资源的使用。例如，用于在资源之间传输数据或从远程地点访问资源的协议。另外，连接层还有安全协议，用于进行用户和资源的认证。资源层：负责管理单个资源。它使用由连接层提供的功能，直接调用对光图1.了陶格计算系统的分层休系结构线层可用的接口。汇集层：负责处理对多个资源的访问，通常由资源分派、把任务分配和调度到多资源以及数据复制等服务组成。连接层和资源层由相对较小、较标准的协议集组成，而汇集层由很多用于不同目的的不同协议组成。应用层：由应用程序组成。第2章体系结构样式：1、分层体系结构2、基于对象的体系结构3、以数据为中心的体系机构4、基于事件的体系结构图2分层佔）和基于对象的（小体系结构痒式(b)图丈呂垂于事伴5和共享数据空间从的体系給构样式客户服务器模型分为三层：1）用户接口层2）处理层3）数据层多层体系结构冃尸接口翅用程序id咨尸机用户接口一-用户接匚散据库埶据号数押率直用溟序应用程序国2.5各种客户-眼并视组织轴构為）（曰用户接口垃用稈序金圧程序世户按n应用程序数据库用力按口点对点体系结构：在结构化的点对点体系机构中，覆盖网络是一个确定性的过程来构成的。这个使用最多的进程是通过一个分布式哈希表来组织继承的。超级对等体：能维护一个索引或者充当一个代理程序的结点。控制管理多个常规对等体。网塔剛2.12述级灯等復网端中雪山的分心執飯诂陶边界服务器系统这种系统部署在因特网中，服务器放置在网络的“边界”。这种边界是由企业网络和实际的因特网之间的分界线形成的。协作分布式系统混合结构主要部署在协作式分布式系统中。在很多重要的系统中，主要问题是先启动起来，因为经常会部署一个传递的客户-服务器结构。一旦某个结点要加入系统，就可以使用完全非集中式的组织结构，用于协作。自治计算：以高级反馈控制系统的形式来组织分布式系统，允许自动自适应变换。也叫做自主系统。自适应的多样性：自我管理、自我恢复、自我配置、自我优化等。反馈控制模型十匕甘析不町控暮数匚T扰/嗪丧）现制输岀善苹输人圈比16应馆控制疯统的逻憶组织结构初皓配置广x纠lE谓萤融发器已测It输出舟布式系统的枝心反馈控制系统的核心由需要管理的组件形成。这些组件能通过可控输入参数驱动，受干扰或噪声输入的影响。系统本身需要被监视，因此需要对系统各个方面进行测量。但是实际测量很难做到，就需要一个逻辑尺度预测组件。控制循环的核心部分是反馈分析组件，分析上述测量值，并把它们与参考值进行比较。包含了决定自适应的各种算法。第三章线程为什么要使用线程？虽然进程构成了分布式系统中的基本组成单元，但是实践表明，操作系统提供的用于构建分布式系统的进程在粒度上还是太大了。而就粒度而言，将每个进程细分为若干控制线程的形式则更加合适，可以使构建分布式应用程序变得更加方便，获得更好的性能。进程间通信机制IPC进柠A1一-J摄作抵焼SI从用户空问切换加S3从内檢字网刃换封用户空闾S2:从进艮A切捶刘谜程H&13.lFCiGft的上卜文如换IPC需要内核干预。从用户模式切换到内核模式S1,在内核中进行上下文切换S2,再从内核模式切换到用户模式S3。完成进程之间的切换。多线程客户隐藏通信时间延迟的常规方法是启动通信后立即进行其他工作。例子：Web浏览器。Web浏览器一般在开始获取HTML页面后随即就显示它。为了尽量隐藏通信时间延迟，某些浏览器在接收数据的过程中就开始显示这些数据。首先将文本显示出来,并提供页面滚动之类的功能,同时获取组成页面的其他文件,比如图像等。用户不必等待浏览器取得整个页面的所有组件就能够查看页面。从效果来看，web浏览器好像在同时进行多任务一样。只要取得了主HTML文件，就可以激活多个独立的线程，它们分别负责取得页面的各个部分。每个线程都与服务器建立一个独立连接以获取数据。多线程服务器虚拟化计算机界面1）由机器指令组成，可由任何程序激起的硬件软件界面。2）由机器指令组成，只有特权程序（如OS）才可激活的。3）由操作系统提供的系统调用组成的界面。4）由库调用组成的界面，通常形成了所谓的应用程序编程结构（API）。很多情况下前述的系统调用由API隐藏。虚拟化的实质是模仿这些界面的行为。虚拟化可采用两种方式。（a）迟郴总拟机.谊令毒牛应用稈律和坯忡时察址山曲按机监視器，泪書#牛症川軒序和權件垂统第一种：可以构建一个运行时系统，实质上提供一套抽象指令集来执行程序。指令可以被翻译执行，也可以仿真执行，就像在Unix平台上运行Windows应用程序。第二种：提供一种系统。把它做成一层完全屏蔽硬件但是提供一个同样指令集（或其他硬件）的界面。这个界面可以同时提供给不同的程序。可以有多个不同的操作系统独立并发地运行在同一平台。客户端软件与分布透明性再户机阳务醉I阳务卷2眼茅器3in:i中的信任关乘所描述的侑理结购。它们的关系如下r（II结点拥冇者把它的结点加人一个骨理橙校屑的骨理域如果合适的话可龍会限制使用方式u（2）骨理授叔畀提供必需的戟件用丁壇加一个结点绪PhneiLab.（3）眼勢捉供片向管理授权耆江班佰任它会提供及好行为的结点=U）呢务提供者联系切片授权苦盹一殂结点上创建一个切片“佝）切片授权茗需耍认证服务提供者6）结点拥奋舌为切片授权祥提供切片创建服务用以创建切片.它兵质I：让切片授权者町以便州它的霍源.3.16PlanetLab实体间的管理关系7）管理授权普把切片创建的任务委托蛤切片授机咅第四章通信表示层OSI模型是用来支持开放式系统间通信的。开放式系统通过一系列标准规则来与其他开放式系统通信的系统。每一层都规定了与上一层的接口。接口中包括一组操作，定义向用户提供的服务。圏4,I灼棋塑中的层、接口贞茂协议面向连接的协议：消息发送方和接收方必须首先显式地确立连接，可能还需要就采用的协议进行协商，然后才能进行数据交换。在通信完毕后，必须终止连接。如电话系统。无连接的协议：交换数据之前不需要有建立连接的过程，消息发送方只需要在准备好的时候传送第一个消息即可。如将信件投入邮箱。如果机器1上的进程A想传消息给机器2上的进程B。那么消息先到机器1上的应用层,依次向下传递，每传递一层，就在消息前增加一个报头。第n层添加的报头中的信息是供第n层协议使用的。某些层还要增加报尾。物理层只负责传输位，而数据链路层是负责检查传输是否出错。数据链路层在每一帧的开头和结尾分别放置特殊的位来对头尾进行标记，并用某种方法将帧中的所有字节相加，计算出校验和。再将校验和放入帧中。当接收到消息后，接收方重新计算校验和，跟原有进行比较。目前应用最广泛的网络协议就是无连接的网际协议(IP)。客户应答图4,容户与服务器之间的RPC的原理等恃结黑凋用远程过桿从谒阳遶问服务器谒用本胞辽程并返回结果远程过程调用包括以下步骤：1) 客户过程以正常的方式调用客户存根2) 客户存根生成一个消息，然后调用本地操作系统3) 客户端操作系统将消息发送给远程操作系统4) 远程操作系统将消息交给服务器存根5) 服务器存根提取参数，然后调用服务器6) 服务器执行要求的操作，操作完成后将结果返回给服务器存根7) 服务器存根将结果打包成一个消息，然后调用本地操作系统8) 服务器操作系统将含有结果的消息发送给客户端操作系统9) 客户端操作系统将消息交给客户存根10) 客户存根将结果从消息中提取出来，返回给调用它的客户过程窖户机客户过程|.客户阔用过程眼站器过程add的第现ptM：kikTiM：val(i)int;2l(j)客卢的操作乖竣贏务器停根客户存杞2存棍程序创建啃恳存根崔序对机d作苓地调用proc：adjdnr：valQ)mival(j)呢务器的揀作至统勺存招提序把消息解包工通过肌绪发送艄层團4適过RPC进行远程忡茸的坐曝传递引用参数？异步RPC从澗用中/返冋脂箔器调用本地过程吋间一1怡）壽户学遗釁嬰囲阳远糅1/d诅用中过稈/返同请求/接査谪求鴨夯魁调用本地过操时何-图LPiRFX中弄户-眼衿器间的交互过呼榕址KP申徉Q-刚务器间的交吃过和；b便用#步RPCH的玄互过理在异步RPC中，服务器接收到RPC请求后立即向客户端发送应答，再调用客户端请求。应答的作用是向客户确认服务器已准备开始处理该RPC请求。客户收到服务器的确认消息后，将不再阻塞，而是继续向下执行。延迟的同步RPC游用远荐过程从调用返回返回鲂果/确认4.11客户和服弟器感过闊个异步RPCi/tti交圧胎务器跑用本地过冷诸我推曼谕求时间调.用含单向RPC的容户尊代接嗫中断客户远程服务器在处理请求时，客户同时做一些其他的事情。当服务器处理好请求时，返回结果去中断客户，服务器端变成发送端，实现第二个异步RPC。套接字：一种通信端点。如果应用程序要通过底层网络发送某些数据，可以把这些数据写入套接字，然后从套接字读出数据。原语含艾socket创鹽新的通倍端点bind将本地地址附加到套接字上Jlisten宣布已准备好接受连接accept在收到连接诸求之餉阻塞调用方Connect主动讐试确立连接send通过连複发送数拯1receive:通过连接接收散据dose释枚连接图4*14TCP/IP箕接字原诺服务器一般执行前4个原语，一般按照图中顺序执行。调用套接字原语的时候，调用者创建一个新的通信端点，用于某种特定的传输协议的。原语含义MPLbsend蔣要送也的消总迪加到本地发送缓冲区中MPLsnd发送消息|并等待直到消息逐制到本地或远程缓冲区中为止MPl_ssenl发送消息，并等特直到对方开始接收为止MPLsendrecv发送消息.并等待直劃收到应答梢息狗止MPl_ist?nd传递翌送出的消岂的引用*随后继续执行MPIJssend传递要送山的消息的引用并等待直到时方开始接收为止MPl_recv接收消息乜如杲不存在尋待接收的消息则凰塞MPIJrecv检査是否有输入的消息但是无论有没有消息都不会阻塞MPI的先进之处：程序的硬件独立性需要导致MPI的出台。MPI是为并行应用程序设计的，是为瞬时通信量身定做的。它直接使用的是底层网络。图4.16MPI中一些最苴观的消息传递原语消息队列系统：面向消息的中间件服务。为持久异步通信提供多种支持。本质是，提供消息的中介存储能力，这样就不需要消息发送方和接收方在消息传输中都保持激活状态。与套接字和MPI的重要区别在于，它的设计目标一般是支持那些时间要求较为宽松的消息传输，不适合几秒甚至几微秒内要完成的传输。发送力闵发送勺被功懂收方主动IfJ消息进入接收方的消息队列时，接收方不必处于运行状态。发送方和接收方可以彼此完全独立地运行。接收方社幼图L)7便用队列的松般就合通信的丨种殂合方式It:4.19駅列饭编址与柯端绳編址之间的黄系虚肉队列的传输圾地址队卵圾地址坦址査询敢据库悴辅层地圻消息队列系统的队列集合是分布在多台机器上的，因此需要维护一个从队列到其所在网络位置之间的映射关系。个数据库，存储到网络位置所对应的队列名。岌送方J1队列隈本地操沖吊抗1队列屋本地擢惟系统了密送方A閉+.20含冇路由器閔消息臥列条烧的一般飙织纳樹发送方A只需要找到最近的路由器，并将队列发送给路由器。路由器负责接下来寻找路径将消息发送给接收方B。采用这种方式，只有在路由器需要添加队列或者删除队列时进行更新，其他队列管理器只需要知道最近的路由器的位置即可。源客户消息托换器含转换规圖和厘序的摩目标客门kI14(1-21消息羸列系统申洎息转换器的能堵构消息转换器：的消息处理，需要消息转换器，是队列网络中负责转换消息的特定结点。对于消息队列系统来说，消息转换器也不过是一个应用程序而已。异步传输模式：流中的数据项是逐个传输的，但是对某一项在何时进行传输并没有进一步的限制。这是采用离散数据流时常见的情况。比如文件的传输。同步传输模式：数据流中每一个单元都定义了一个端到端的最大延迟时间，容许延迟。数据单元的传输时间是否远远小于最大允许延迟并不重要。等时传输模式：数据单元必须按时传输，端到端的延迟时间同时又上限和下限。这个上、下限也称为边界延迟抖动。在视频和音频方面很常用，比如音视频的同步(对口型)。QoS服务质量特性：1)数据传输所要求的比特率2) 创建会话的最大延时(比如应用程序何时可以开始发送数据)3) 端到端的最大延时4) 最大延时抖动5) 最大往返延时。从菊地出联的数摇包121345f-300到达釀沖区的数据包Q213炳辭眦沁密收中呗间別目亟丽ME、狗族冋園1J.LN11io时间f秒）图L27僚用绷冲憧来融少抖功当数据包有不同的延时，接收方先把它们存储在缓冲区，当总是有足够的数据包进入缓冲区时，接收方就可以以固定的速率把数据包传递给应用程序。发送nT|0300E.町叵叵亘回回回网已传送llEIIlSSSLZSIKICn回回回回网丢灾輔的阿隔忑失的数松社发送00回辺日回回IM囚冈回回已传送叵|国37SH回回回回Li回回Jf丢失的桢一图仁霸数据包丢失的陽果舉玄祷传雜：Cb交锵礼输如在传送音视频时，采用交错传输，丢失的帧分布较广，这样丢失的就不是一大段而是零散的帧，对于音视频的播放影响就较小。但是这样需要更大的缓冲区，因此程序的开始延时更高。流同步莎中稈序用应用程序进行同步力毎亍视师融据弧元处取曲乍甘脚数锯单元的卫璨、同步机制-J|彗4+鵲在数粧单朮层欣匕进柑显式同涉的涼理捲蚊A眄机矣圉碁旳旳过高级抿口支祷同歩的原埠爭喪体控觀是中圖件的组就邹好、直用徨庠皆诉巾詣件和肾世理幡入渡多媒体中间件提供接口控制视频和音频流。每个设备和流都有自己的高级接口。覆盖网络m4.31覆雀网堵的栓捲+H多蚯世络凰中路由菇的锥报之间的龙系中间件层负责处理同步。信息传播模型anti-entropy结点P随机选取另一结点Q,然后与Q交换信息。更新信息的方法:1) P只是把自己的更新信息发出给Q,基于push的方法2) P只是从Q那里获取更新，基于pull的方法3) P和Q相互发送更新信息给对方，基于push-pull的方法第5章命名系统名称是用来与实体当前位置无关的方式来定位它们。名称与实体的位置可能毫不相干。访问点：用来实体的一种特殊实体。地址：访问点的名称。所以访问点就是实体的地址。标识符属性：1）一个标识符最多引用一个实体2）每个实体最多由一个标识符引用3）一个标识符始终引用同一个实体（也就是说标识符永远不会重新使用）地址&标识符地址和标识符都是名称类型，但是用于不同目的。地址是用于访问实体的，找到实体的位置，而标识符不一定与实体的位置相关，只是一个使得实体区别于其他实体的标志。广播&多播广播：包含某个实体所用标识符的消息会广播到每台机器上，请求每台机器产看它是否拥有该实体。拥有该实体的机器发送回复消息，消息包含访问点的地址。但是随着网络的扩大，越来越低效。多播：只有符合条件的一组机器才能接收到消息请求。转发指针客户存根链长，断的可能性大，可靠性差團昆1艳用客八存握.服务器存根）对的转堂弟皆的原理当对象从地址空间A移到B时，会留一个客户存根在A中，一个服务器存根在B中。服务器存根要么包含实际对象的本地应用，要么包含该对象远程客户存根的本地引用。对象调用携带一个客户存根的标识，这是调用发起的地方。当调用到达位于当前位置的对象后，会向发起调用的客户存根发送回一个响应。当前位置中包含了对象的当前位置。客户存根会把自己的对应服务器存根调整为对象当前位置中的那个服务器存根。宿主位置：创建实体的位置。分布式散列表4241Q4Q18J指状衣271421II从站点1解-桁k=26；2从结点28跳析k=12实肉:招点iccp+S1-1)211128345412022032S42H5411$11IS31艮斗2KL5119299A14如2113144IK、2K圏5.4在Chortl系统中尿结点1解析褪倚2乩展结点疏解柝程備12分层方法：叶城.包含在5中图5“把定位服务划牛为域的分层细织，毎*域都拥有其联的目录結点根日录结点A顶皴域丁F顶圾城下的一个子坯呂/、七岱包含在丁白)S賊中的冃量结点dir(S)不骨剋据的字段结点中有E的记录,凶此出I青亦转友鋁图5.7亚分圧组纹的毎位服务中的位置弈找结点有E的记录出此不再转戏滑求!ffiAiii求E15.B更新操作心)描几请北強賞发劉第一孑即道宝障E的结点j(U；粋盍晞向叶结点的措时所书龙的隹链接挂载在涉及多个命名空间合并使用的时候，会出现挂载，从这个命名空间挂载到另一空间。访问另一空间的地址存储结点标识符的目录结点称为挂接点。外部名称空间中的目录结点为挂载点。名称空间的分布全局层：由最高级别的结点组成，由根节点和根节点的子节点组成。涉及到统筹。特点：通常是稳定的，目录表很少改变。可以用来代表组织或组织群。行政层：由那些在单个组织内一起被管理的目录结点组成。特点：代表属于同一组织或行政单位的实体组。虽然会改变，但通常也是稳定的。管理层：由经常改变的结点组成。涉及到个体。在可用性和性能方面，每层的名称服务器都必须满足不同的需求。性能问题：因为全局层结点变化不频繁，所以查找操作的结果一般会长期有效。所以客户可以缓存这些结果。当再次执行同样的操作时，可以直接从缓存中获取结果，而不用再调用名称服务器。所以，全局层的名称服务器不需要快速响应单一的查询请求，需要较大的吞吐能力。内容全局层行政层管理层网络的龟理范围世界范围组织部门:结点数星少许1$诃响应立1更新的传搁青况延迟立即立即许多设目或很少没有1是習采用嘗户端緩存是是育时图5,14为大型名称乍间所属的全局层*行枚层和程理恳实规结点的若称眠务器之间的比牧迭代名称解析：名称解析程序把完整的名称转发给根名称所在的服务器。服务器每次解析后都将结果返回给客户。5.15袪代名称解析原埠啷hwq用p由m一脂务遵管理的结点.啊称服务器n】結点8.坤叫A+.#,.nl.u,隅ftp-棍名称腿务露2.#,wu?cs,ftpi專尸的名歆解析程序|flp旳结白.根名祢眼务器宅称眼务器E结点容称辰努器vu皓点递归名称解析：名称服务器会把结果传递给它找到的下一台服务器，解析的结果保存在当前服务器。当最后一台服务器解析结束后，会依次向上取出解析结果，最后汇总到根名称服务器，统一发送回客户。图况16递日名称解析原理,#n容戶的龍桁程序名秫旺务器CK第点11客户【3閨S.18递归名称無析与迭代名称郦析在通信开销方面的对比递归名称解析优点：1)与迭代名称解析相比，缓存结果更为有效2)减少通信开销运距禹通佶递口容鞭解析迭代容称解析二名称脈务器iM结点_名称服势器名妳膈务器弱*吉点目录服务：基于属性的命名系统。实体有一个可以用于查找的相关属性集。如电子邮件系统中，可以用发送者、主题等属性来标记邮件。资源描述框架RDF统一资源描述方法。RDF模型的基础是，资源用由主题、断言和对象组成的三联体来描述。如(Person,name,Alice),主题是Person,断言是name,对象是Alice。第六章同步化物理时钟：计时器。編障爲所矩的计算机2144214521462147、OLCpUtXfilJ建本地fl寸钟的时何輪借器所在的计算机2142214321442145車地时钟的时问mpim被创逹対了与丁曲慄持同步,在IHT中引人国秒当每台机器都有它自已的时钟时，一亍发牛一于另一个慕件之石的事再可能会械标记匕较早的时间时钟同步算法最大偏移率存在某-常数旷使得；1-卩羔普1+。UTCJU巨意图矗馬当时钟以不同的速率漓答时.时钟时间和UTCN间的关蔡如果时钟A落后，那么可以在每个中断添加时间来调整。调整的时钟要参考另一个时钟，另一个时钟被称为参考时钟。逻辑时钟：机器的相对时间，不一定与实际时间相同。先发生：ab“a在b之前发生”1）如果a和b是同一进程中的两个时间，且a在b之前发生，则ab为真2）如果a是一个进程发送消息的事件，而b作为另一个进程接收这个消息的事件，则ab也为真。再发送到下一个进程后，如果时钟小于或等于当前进程，那么把后一进程的时钟改为当前进程时钟+1，并且把下一进程以后的时钟都要按照原来的间隔延后。比如P2中56改为61后，那么后面的64也要改成69,72改为77，80改为85。向量时钟Lamport时间戳不能捕获因果关系，而向量时钟可以。区别？瓠分配给事件的向量时钟VCU)具有下列性质：如果对某一事件b,有vc(a)-vcEk)来调整自己的向量口然后*抡行射一步+并把该消息传送蛤应用程序。强制因果有序通信柞为个示例.来看看阳乩打所示的二牛进程F已和P/在由地茁间4进梶P.发送消息m到其他两个进程匚该消息由进程】、：接收后，进程卩l决定发送消息口館，它比m先到达进稈P-此时，ni*的传送餓进理巳延迟直到如被按收且传送给了巳的应7层*VCr.iJJ.0)VCrILL0)-AVC20,0Xi)553%叫匸图&口强制丙果通信互斥算法1、集中式算法3na(番L廊柞皆不粧许！2进程L生薛放资源时迪知悔作者祚作吿然洛对进和m做岀应答3进程1请疋协件音准许访问JVX資抑”请求得到f准许7然巨进程2也淸求淮许英丰资|队列刘空协作者进程在使用资源时独占资源，当有其他进程发送请求时，放入到请求队列中。2、非集中式算法每个协作者都被复制了n次。某个进程要访问资源，只需从mn/2个协作者中获取多数投票即可。3、分布式算法当一个进程要访问资源时，发送一个消息给所有其他进程，包括自己。当一个进程接收到消息时，做出判断1) 若接受者没有访问资源，也不想访问，就返回一个OK消息2) 若接受者已获得访问，就不应答看，并将请求放入队列中3) 若接受者也想访问资源但尚未访问，就比较收到消息的时间戳和自己发送消息的时间戳进行比较，早的获胜。如果发送者获胜，接受者就返回OK。否则接受者将获得访问，不应答，然后将请求消息放到队列中。00120K(t)團15齊个誉穆同时要访代-吓共卩资源这輕0具有星早的时问戳折出它茯胜：CC固进程0完戒时，它戻逢一吓OK梢息所以進輕F堪址Z1访问筑源4、令牌环算法将进程以环状连接到一起，每个进程只需知道谁在它的下一位上。设置一个令牌，每个进程进行传递。每个进程得到令牌后，看自己要不要访问资源，如果要，就执行。进程执行结束后，把令牌向下传递。如果不要访问资源，就直接把令牌向下传递。四种算法比较算法毎次进/出需要的消息数进入前的延迟按消息数)问题集中式32协作者崩擾非集中式3mkhk=l,2,21T1会发性饥哦效率低廿布式2(n-l)2(n-li任何进程匍溃夕牌环严80*n令牌丟失，进程崩溃图了四神互斥算法的比轨欺负算法当任何一个进程发现协作者不再响应请求时，它就发起一次选举1) P向所有编号比它大的进程发送一个ELECTION消息2) 如果无人响应，P获胜并称为协作者3) 如果有编号比它大的进程响应，则由响应者接管选举工作。P的工作完成。以前的协件者已期制(b)6,20跟负选举真法(a)进煜4主持一个堆(b)进轉S和石画行响应.自诉选程4停止憑举：让进程&和&此肘柠门宝持一牛选举d)进桎ri通知进稈5停止选特t厲进稈疳兼眈并曲知毎卒进稈当有ELECTION消息到达时，接收者回送一个OK消息给发送者，表明自己仍在运行，并接管选举工作。最终除了一个进程外，其他进程都将放弃，这个进程就是新的协作者。它将获胜的消息发送给所有进程。当以前的一个崩溃了的进程恢复过来时，它将主持一次选举。环算法当任何一个进程发现协作者不工作时，它就构造一个带有它自己进程号的ELECTION消息，发送给后继者。如果后继者崩溃，就跳过崩溃的进程，继续往下走，直到找到一个正在运行的进程。每一步，发送者都将自己的进程号加入到消息中，使自己也成为协作者的候选人。最终消息返回到发起选举的进程。当发起者接收到包含自己号的消息，识别出这个事件，选出进程号最大的作为协作者。然后消息类型变为COORDINATOR，并再一次绕环运行，通知大家谁是新的协作者以及新环中的成员。消息循环一周后被删除，然后每个进程恢复正常工作。无线系统环境中的选举算法Q砧(bjcC(d(d)c图E22无线网络中的选半算法，梵中$为源结点小初蜡网堵Mb）构建树的荐牛酚團M打向源结点报雪暈狂结点父结点向子节点广播ELECTION消息，直到最底层。然后从最底层开始每个结点向父结点报告自己的容量和节点号，又父结点选择容量大的作为最佳结点，继续再向自己的父结点报告。最终到根节点选出一个容量最大的最佳结点。大型系统中的选举算法需要选举多个结点。在几何空间中推动令牌。A儿作用于匕的睢动力O当某个令牌被一个结点拥有了给定长的时间，那么这个结点就会变成超级点。站戌口特莊为會牌持有爭一OD6.23使用椎功力在一一堆空冊中移戲令聊第7章一致性和复制副本B一致性单元49-WiW*i弍吃尸3I1-致性单元I1Ix=2：y=5ILJ*操作结果结果gy-5向MatWAH5t5瀚序怕墨=3数值扫建円1刃向誥时忡B弓311】朋序偏羞=2敦值怕差6）RS7,2阐述一致性偏差的斥例（摘自（Yu和Vahdat2002）单调读如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值。也就是，如果一个进程在t时刻看到x的值，那以后不会再看到较老版本的x值。比如一个用户的邮箱在多个计算机上。如果用户在旧金山开邮箱看邮件，进行操作。那么他到纽约后，纽约的邮箱是旧金山操作后的样子。WS(K()L|：wsg)Rg)Sk：WSfXi.Xj)V-R(x;)L：:WS(x2)R(x3)(町(b)图7.12单一进穆N対間一数据年储前阿个平同本地副本听执行的读襟作M擬供中调读一敗性的救据存储门血不摄供单凋债负性的敕搦存储单调写一个进程对数据项x执行的写操作必须在该进程对x执行任何后续写操作之前完成。比如在一个软件库上进行更新操作，那要查看其他副本在这个库的当前版本后有没有更新过，如果有，那么要把之前的那些更新补上，然后再进程本次的更新，最终这个软件库达到最新版本。L(:W(X|)L：W(黑J、L21WSX|)*W(x2L/W(x4,(b)图7.13曝一进稈P对同一枚据存储的两令不同奉地副本所执行的吗撚作5)提供单陶写-建性的数据存储；b用崔供单一调驾一毀性的数撫释储读写一致性一个进程对数据项x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。图X14|：.)捉供埒读-炖性的籾振存储：h)不舉惟专读-致件前數据存储远程写协议数据项x的主服务器爸份服务熬W4W4W3閘一读请求R2.读请求的晌应本地写协议R1.读请求数据项的I日主at务器W】.结请求W2肥数鉅项K移到新主胆务器上WM通知箔份服务器更新W4,确认写攫件已完成XV*确认更新数拥项x的新主脂务器wi.写i靑求W2杷谓求转发结主腑务器认3通知蕾扮服务as更新*4”确认更新伙,确认写操作已完成图7.20空缶份协谡的原理R2-读请求的响应图7.21主备份协议苴中主备份移动到要执行更新的进程那里
展开阅读全文