《网络与分布式操作系统.ppt》由会员分享，可在线阅读，更多相关《网络与分布式操作系统.ppt（62页珍藏版）》请在三一办公上搜索。
1、9.5 事件排序 清华大学,前发生关系(用符号“”表示).如果A和B是同一进程内部的事件，而且A在B前执行，则有AB。如果A是一个由某一进程发送消息的事件，B是由另一进程接收该消息的事件，则有 AB。如果 AB 且 BC，则有 AC。非自反的偏序,实现,将每个系统事件都打上一个“时间邮戳”。每一个事件对A和B,如果AB,则A的邮戳时间应小于B的邮戳时间。在每个进程Pi内部定义一个相关联的逻辑时钟 Lci。由简单的计数器来实现，即作为在一个进程内任何两个连续执行的事件之间的增量。,“”的实现,一进程在接收到一个消息,而且该消息的邮戳时间TS比接收进程逻辑时钟的当前值还大时,接收进程推进它的逻辑时
2、钟。Count=TS+1。如果事件A和事件B的邮戳时间相同,则事件是并发的。,9.6 进程互斥(DME),假设系统包含n个进程;每个进程 Pi 都存在于不同的处理机当中.每个进程有个临界区需要互斥.必要条件如果进程Pi 正在它的临界区域内执行，则在这个临界区域内没有其他进程 Pj 执行.这里给出三个算法来确保执行进程在其临界区内互斥.集中算法分布算法令牌算法,DME：集中方式,指派一个协调者进程(coordinator),负责控制对于临界区的进入。每一个要求进入临界区的进程都必须发送一个请求给协调者进程。协调者决定哪个进程可以进入临界区域，之后给它发送答复消息。当进程收到协调者进程的回答信号后
3、,它才能进入自己的临界区.,DME:集中方式,当一个进程退出临界区时，发送一个释放信号给协调者进程，然后再继续运行。无死锁，若协调者进程公平（如FCFS)，无饿死每次进入临界区需要三个消息：请求回答释放,DME:分布方式,算法进程Pi想进入临界区，产生一个时间戳TSi,发消息request(Pi,TSi)给所有其他进程;进程Pj接收到request消息后，可能立即，也可能延迟回复reply消息；当进程Pi接收到所有进程回复的reply消息后，可以进入临界区；,DME:分布方式(续.),进程Pi离开临界区后，给所有延迟回复的进程发reply消息决定进程Pj 立即回复request(Pi,TS)消
4、息还是延迟回复主要基于三个因素:如果Pj当前正在临界区中，延迟回复.如果Pj不想进入临界区，立即回复.如果Pj想进入但尚未进入临界区，则比较二者的时间戳 TS.如果所持有的时间戳大于TS;则立即回复Pi,(Pi 要求占先).否则，延迟回复.,分布方式优点,确保无死锁确保无饥饿因为进入临界区域是依照时间戳顺序，时间戳顺序确保FCFS.每次进入临界区仅需要的消息数量 2(n 1)这是全分布算法最好的结果,DME例子,考虑p1,p2,p3构成的系统P1,p3想进入其临界区域P1发request(1,15)给p2和p3,p3发送request(3,6)给p1和p2.P2接到请求后，立即回答p1和p3；
5、P1接到p3的请求后也立即回答(因为p1的时间邮戳比P3的时间邮戳大)P3接到P1的请求,延迟回答;P3接到来自P1和p2的回答,进入临界区;P3离开临界区域,向P1发回答消息,P1进入临界区域,DME:三个缺点,每个进程必须知道所有其他进程的存在，这使进程动态增减变的复杂若其中一个进程失效，则整个算法崩溃，为此需要动态监视所有进程状态不想进入临界区的进程也必须参与协调过程因而算法比较适合稳定且数量较少的进程集合,标志传递方式(token passing),这种方式仅适合于逻辑拓扑结构为环形的系统 系统中有一个标志,它作为特殊类型的消息在系统中环行当一个进程接收到这个标志后,它就可以进入其临界
6、区,并扣留这个标志 当它退出临界区之后,标志才被释放,并沿环路继续绕行 如果一个接收到标志的进程并不想进入其临界区,只需放行此标志,标志传递方式(token passing),需要考虑两种失效情况 如果消息丢失,则应能发现并选择一个进程产生一个新的标志;如果一个进程夭折了,则逻辑环就将断裂,此时系统应能重构一个新的逻辑环.,9.7 进程同步与进程通讯,消息传递(Message Passing)套接字(Socket)远程过程调用(Remote Procedure Call，RPC)远程方法启用(Remote Method Invocation，RMI),消息传递(Message Passing)
7、,同步消息传递-send(接收者,消息,回答):将消息发送给指定的接收者,然后挂起,等待来自接收者的回答消息,之后继续。-receive(发送者,消息):等待接收来自发送进程的消息。-reply(发送者,回答):将回答信息发给发送进程,使之继续执行。,同步消息传递,站点A,进程PiSend(接收者，消息，回答)阻塞继续,站点B,进程Pjreceive(发送者，消息)Reply(发送者，回答),异步消息传递-send(接收者,消息/回答):将消息或回答发送给接收者,然后继续。-receive(发送者,消息/回答):由发送者处接收消息或回答,然后继续。,消息传递(Message Passing),
8、异步消息传递,站点A,进程Pisend(接收者，消息)继续receive(发送者，回答),站点B,进程Pjreceive(发送者，消息)send(接收者，回答),9.7.2 套接字(Socket),套接字定义为通讯的一端 地址形式为(IP,port)套接字是一种低级(low level)、不完全可靠的通讯方式 All Ports 1024 are Considered“well-known”-TELNET uses port 23-FTP uses port 21-HTTP uses port 80,套接字通讯,Socket(161.25.19.8/80),Socket(146.86.5.20
9、/1625),主机 X(146.86.5.20),网络服务器(161.25.19.8),9.7.3 远程过程调用(RPC),套接字是一种低级(low level)、不完全可靠的通讯方式 RPCs 提供一种高级通讯方式Client makes procedure call to“remote”server using ordinary procedure call mechanisms.Widely accepted and standardized mechanism in distributed environmentRPC can be synchronized or asynchrono
10、us,Vec,MAX,10,调用消息,返回消息,v,顾客进程：,RPC_name(vec,MAX,10)(挂起)vec:=v(继续),服务进程：,RPC_name(v,n,k)v:=vec;n:=MAX;k:=10;FOR I:=1 TO n DOvI:=vI*k;,站点A,站点B,例:,呼叫方,调用,参数打包发送 等待接收开包结果返回,消息,参数接收开包 调用打包发送结果,执行过程返回,客户代理,服务员代理,客户,服务员,消息,被呼叫方,RPC的实现,为每个远程过程调用创建一个代理进程调用时创建，结束时撤销，代理进程的生存期为调用过程，一个站点可以同时存在多个执行同一远程过程的进程并发性好，
11、空间开销小，时间开销大；对每位顾客创建一个代理进程顾客进程开始时创建代理进程，顾客进程结束时撤销代理进程。并发性好，空间开销大，时间开销小；,RPC的实现,为每项服务建立代理进程一个站点中仅存在一个执行远程过程的代理进程，读取控制请求，执行相应过程，然后返回回答消息。这个服务进程可被多个顾客调用时空开销小，响应速度慢。,远程方法启用(Remote Method Invocation，RMI),Java中的RPC版本被命名为RMI 一个线程可以启用另外一个远程对象中的方法“远程”指处于不同的Java虚拟机(JVM)中,远程方法启用(Cont.),RPC与RMI的比较,RPC支持过程型程序设计风格
12、 RMI支持面向对象程序风格 RPC的参数为普通数据类型 RMI的参数为对象Local(Non-Remote)Objects are Passed by Copy using Object SerializationRemote Objects are Passed by Reference,9.8 死锁处理,死锁预防 全局资源排序 基于“优先权/回退”方式的时间戳死锁避免分布银行家算法 死锁检测 对每个资源类型的实例集中方式分布方式,9.8.1 死锁预防,死锁预防 全局资源排序+请求排序给每个资源赋予一个唯一的整数.如果一个进程没持有资源编号等于或大于i 的资源，则可以申请编号为i 的资源.
13、优点和缺点simple implementationlittle overheaddifficulty in global resource orderinginconvenient for distributed processes to abide by the protocol,优先级死锁预防,每个进程Pi被赋予一个唯一的优先数 优先数用来决定进程Pi 是否应该等待进程Pj;如果 pri(Pi)pri(Pj),Pi 等待;否则 Pi 回退.The scheme is deadlock-free.For every edge Pi Pj in the wait-for graph,Pi h
14、as a higher priority than Pj.Thus a cycle cannot exist.Possibility of starvation-low priority process may always be rolled back.Resolve:use timestamp instead of priority,等-死(wait-die),基于非剥夺策略。当一个进程Pi要求另外一个进程Pj保持的资源时，Pi被允许等待，仅当它具有比Pj更小的邮戳时间，即Pi是比Pj更老，否则Pi回退。例如，设进程 P1,P2,P3分别具有邮戳时间 5,10,15。如果P1要求P2占用的
15、资源,则P1等待。如果P3要求P2占用的资源,则P3回退。等待边(更老)PiPj(更年轻),伤-等(wound-wait),基于剥夺策略，是等死的改版。当进程Pi要求进程Pj当前所保持的资源时，则Pi获准等待的条件是它具有比Pj更大的邮戳时间，即Pi比Pj更年轻，否则Pj回退，即Pj被Pi所伤。例如,设进程 P1,P2,P3分别具有邮戳时间 5,10,15。如果P1要求P2所占用的资源，则将剥夺P2的资源给P1，P2回退；如果P3要求P2占用的资源，则P3等待。等待边(更年轻)PiPj(更老),9.8.2 死锁避免,银行家算法 指定系统中某个进程为银行家，由它保持执行银行家算法所必需的信息。银
16、行家负责系统中资源的分配。优点和缺点easy implementationmay incur too much overheadpossibility of bottleneckif banker fails,the algorithm fails,9.8.3 死锁检测,每个站点保持一个局部等待图。站点：所有进程(或者持有或者请求)本地站点的资源。,站点 A,P2,P4,P3,站点 B,9.8.3 死锁检测(Cont.),全局等待图是所有局部等待图的合并。,站点 A 和站点 B的全局等待图,9.9 资源管理,9.9.1 集中方式中央资源管理者负责系统中所有资源的分配.系统资源表,9.9.1 集
17、中方式(Cont.),优点可以做出全局优化的资源分配策略。系统扩充和裁减容易这只需要在系统资源分配表中增加一个新项目或删除一个旧项目 减少了资源管理算法的开销除中央资源管理者外，其它站点不参与资源决策事务。,9.9.1 集中方式(Cont.),缺点可靠性低因为一旦资源管理者失效，则整个系统瘫痪。尽管引入多个资源管理者可以克服这一缺点，但保持多副本的一致性是困难的。中央资源管理者可能成为系统的瓶颈 由于中央资源管理者的存在，使整个系统失去了自治性。,9.9.2 分布方式,每个站点都有一个局部资源表，用于记载属于该站点的局部资源当一个站点要申请局部资源时，它可由本地得到。当一个站点要申请全局资源时
18、，它向其它站点发送申请命令，其它站点根据情况做出分配决策。,9.9.2 分布方式(Cont.),优点可靠性高因为任何一个站点、资源或服务的失效通常不会影响整个系统每个站点具有较高的自治性它可以将其所拥有的资源提供给整个系统使用，也可留为私用,9.9.2 分布方式(Cont.),缺点通讯量增加因为要获得有关资源的信息，每个站点都需要与其它站点交换信息。每个站点都需要为资源分配策略的实施付出开销即资源分配设施消耗局部资源。,9.9.3 层次方式,集中方式与分布方式的结合，同时兼有二者的优点,并克服二者的缺点 对于局部资源采用分布式管理策略 对于全局资源采用集中式管理策略,9.10 分布式文件系统(
19、Distributed File System，DFS),一般结构 命名与透明性 远程文件存取 Remote File Access远程文件服务 副本复制 有状态服务与无状态服务 缓存策略,一般结构,分布式文件系统(DFS)是集中式文件系统的分布式实现,命名与透明性,命名是逻辑实体到物理实体的映射对于真正意义的DFS，整个系统具有统一的命名机制，用户以透明的视图共享所有文件和存储器。三种命名形式：网络命名方式，命名与物理位置完全相关，不透明 远程安装方式，远程安装是不透明的，一旦安装完毕，远程访问是透明的 完全分布方式，所有文件具有全局唯一的名字，文件名与物理位置无关,9.10.3 远程文件存
20、取,远程文件服务 工作模式:向服务员提出文件访问请求 服务员执行相应操作 将结果返回给顾客 实现:RPC副本复制缓存 将远程文件复制到本地，然后如同本地文件一样访问 问题:一致性,副本复制缓存,文件仍然由一个位于服务器上的主拷贝标识，但其副本可能分散在多个站点上当进程所需文件不在本地时，由服务器向本地缓存一个副本.存取操作在缓存副本上执行.缓存粒度块为单位，整个文件为单位.缓存一致性问题保证主文件和缓存副本的一致.,缓存副本存放方式,磁盘缓存更可靠本地机器故障后恢复容易内存缓存速度快支持无盘客户端工作站,缓存更新策略,通写(write through)每当缓存副本发生变化时就更新主本 可靠性高
21、；一致性好；效率很低。延迟写(delayed write)副本数据经过若干次访问(更新)后才最终写回主本实现效率较高；一致性差；可靠性低，一旦副本所在结点失效则更新数据可能丢失。,缓存更新策略(Cont.),增量刷新(incremental flush)定时扫描缓存数据，只将上次更新后发生变化的数据块回写到主本。关闭写(write on close)只在文件被关闭时才将缓存信息写回主本。适合于长时间对数据进行较多更新操作的应用环境.,9.10.4 有状态服务与无状态服务,有状态服务(State-full service)服务器端保持文件状态信息打开文件表，块缓冲无状态服务(Stateless
22、service)服务器端不保持文件状态信息无打开文件表，块缓冲,有状态服务(state-full service),特征API界面中包含显式的打开和关闭命令对于打开命令，文件服务器端需要将文件控制信息读入内存打开文件表中，同时维持文件的读写指针关闭时若控制信息已变化则回写磁盘,有状态服务(Cont.),优点界面一致，远程文件API与本地文件API相同 状态信息在内存，响应快 可以通过预先读等手段提高访问速度 可以对文件加锁缺点对于小量偶然性访问使用麻烦，开销大服务器端以open和close识别远程客户会话期，一旦用户不活动要及时撤销文件控制信息，若远程用户忘记close则给状态表维护带来困难,
23、无状态服务(stateless service),特征API界面中不包含文件打开和关闭命令 服务器端在内存文件控制表中不保持远程文件访问的控制信息 每个文件读写命令必须是自包含的(self contained)远程文件读写命令中包括：文件名、位置(记录号)、内存地址,无状态服务(Cont.),优点服务器不需在内存中保持文件状态信息，节省空间没有打开文件数的限制不需识别远程用户的会话期，实现简单，客户崩溃时不会造成服务器错误缺点大量访问速度慢无法实现预先读,选举算法,Bully算法Suppose That process Pi send a request that is not answere
24、d by the coordinator within time interval T.In this situation,it is assumed that the coordinator has failed,and Pi tries to elect itself as the new coordinator.This task is completed through the following algorithm.,Bully算法,Process Pi send an election message to every process with a higher priority
25、number.Process Pi then wait for a time interval T for an answer from anyone of these processes.If no response is received within time T,Pi assumes that all processes with numbers greater than i have failed,and elects itself the new coordinator.Process Pi restart a new copy of the coordinator and sen
26、ds a message to inform all active process with priority number less than I that Pi is the coordinator.,Bully算法,If an answer is received,Pi begins a time interval T,waiting to receive a message informing it that a process with higher priority number has been elected.(some other process is electing it
27、self coordinator,and should report the result within time T).If no message is sent within T,then the process with a higher number is assumed to have failed,and process Pi should restart the algorithm.,Bully算法,If Pi is not the coordinator,then,at any time during execution,Pi may receive one of the fo
28、llowing messages from process Pj:Pj is the new coordinator(jI),process Pi records this information.Pj started a election(jI).Process Pi send a response to Pj and begins its own election algorithm,provided that process Pi has not already initiated such an election.,Bully算法例子,All processes are active,
29、P4 is the coordinator process.P1 and P4 fail.P2 determines P4 has failed by sending a request that is not answered within time T.P2 then begin its election algorithm by sending a request to P3.P3 receives the request,responds to P2,and begin its own algorithm by sending an election request to P4.P2
30、receives P3s response,and begin waiting for an interval T.,Bully算法例子,P4 does not respond within an interval T,so P3 elects itself the new coordinator,and send number 3 to P2 and P1(which P1 does not receive since it has failed)Later,when P1 recovers,it sends an election request to P2,P3,and P4.P2 and P3 respond to P1,and begin their own election algorithm.P3 will again be elected,using the same event as before.Finally,P4 recovers and notice P1,P2,P3 that it is the current coordinator.(P4 send no election request,since it is the process with highest number in the system),
