09第九章_网络与分布式操作系统(5)

9.5事件排序先发生关系(用符号“”表示).如果A和B是同一进程内部的事件，而且A在B前执行，则有AB。如果A是一个由某一进程发送消息的事件，B是由另一进程接收该消息的事件，则有AB。如果AB且BC，则有AC。非自反的偏序：因为一个事件不可能在其本身之前发生。9.5事件排序采用时空图来定义并发性和前发性。时空图中水平方向表示空间（即不同的处理机），垂直方向表示时间，带标记的实线表示进程（或处理机），带标记的圆点表示事件，虚线表示进程间的消息传送。结论：如果A、B是不同进程中的两个事件，且AB，则A之前发生的事件与B之后发生的事件不能并发执行。全序关系将每个系统事件都打上一个“时间邮戳”。每一个事件对A和B,如果AB,则A的邮戳时间应小于B的邮戳时间。在每个进程Pi内部定义一个相关联的逻辑时钟Lci。由简单的计数器来实现，即作为在一个进程内任何两个连续执行的事件之间的增量。“”的实现一进程在接收到一个消息,而且该消息的邮戳时间TS比接收进程逻辑时钟的当前值还大时,接收进程推进它的逻辑时钟。Count=TS+1。如果事件A和事件B的邮戳时间相同,则事件是并发的。时空图p0p1p2p3p4r0r1r2r3r4q0q1q2q3q4s0s1s2s3s4例子在上述例子中，当P2接收到一个来自P1的消息时，它应将其逻辑时钟推进到LC2(B)=101,基于此方法，上图中的事件的逻辑事件如下表所示：在任意站点k，事件的排序由以下规则确定：对于来自站点i的消息x和来自站点j的消息y，如果下述条件之一成立，则称x在y之前。（1）TiTj（2）Ti=Tj且ij事件与逻辑时间表事件P0P1P2P3P4逻辑时间14567事件q0q1q2q3q4逻辑时间12378事件r0r1r2r3r4逻辑时间1891011事件s0s1s2s3s4逻辑时间12345时间戳算法例子057000322357111297(a,1,1)(f,8,1)(d,6,3)(c,4,2)(g,10,4)(e,8,4)(b,1,4)时间戳算法例子消息（a,1,1）先于消息（b,1,4）到达站点P2，而这两个消息却以相反的本地时间次序到达站点P3。由于两个消息的时间戳相同，但是进程标识14，因而当两个接收进程都接收到上述两个消息后，可以得到一致的消息事件排序，即（a,1,1）先于（b,1,4）。另外，消息（g,10,4）先于消息（f,8,1）到达站点P2，但当两个消息都到达P2后，可以根据时间戳确定（f,8,1）先于（g,10,4）。注意：本方法所产生的排序不需要与实际时间顺序一致。对于这种基于时间戳方法的算法，哪个事件首先发生实际上并不重要，重要的是实现算法的所有进程对于事件产生的顺序意见一致。9.6进程互斥(DME)假设系统包含n个进程;每个进程Pi都存在于不同的处理机当中.每个进程有个临界区需要互斥.必要条件如果进程Pi正在它的临界区域内执行，则在这个临界区域内没有其他进程Pj执行.这里给出三个算法来确保执行进程在其临界区内互斥.集中算法分布算法令牌算法DME：集中方式指派一个协调者进程(coordinator),负责控制对于临界区的进入。每一个要求进入临界区的进程都必须发送一个请求给协调者进程。协调者决定哪个进程可以进入临界区域，之后给它发送答复消息。当进程收到协调者进程的回答信号后,它才能进入自己的临界区.DME:集中方式当一个进程退出临界区时，发送一个释放信号给协调者进程，然后再继续运行。无死锁，若协调者进程公平（如FCFS)，无饿死每次进入临界区需要三个消息：请求回答释放DME:分布方式算法进程Pi想进入临界区，产生一个时间戳TSi,发消息request(Pi,TSi)给所有其他进程;进程Pj接收到request消息后，可能立即，也可能延迟回复reply消息；当进程Pi接收到所有进程回复的reply消息后，可以进入临界区；DME:分布方式(续.)进程Pi离开临界区后，给所有延迟回复的进程发reply消息决定进程Pj立即回复request(Pi,TS)消息还是延迟回复主要基于三个因素:如果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；P1接到p3的请求后也立即回答(因为p1的时间邮戳比P3的时间邮戳大)P3接到P1的请求,延迟回答;P3接到来自P1和p2的回答,进入临界区;P3离开临界区域,向P1发回答消息,P1进入临界区域DME:三个缺点每个进程必须知道所有其他进程的存在，这使进程动态增减变的复杂若其中一个进程失效，则整个算法崩溃，为此需要动态监视所有进程状态不想进入临界区的进程也必须参与协调过程．因而算法比较适合稳定且数量较少的进程集合标志传递方式(tokenpassing)这种方式仅适合于逻辑拓扑结构为环形的系统系统中有一个标志,它作为特殊类型的消息在系统中环行当一个进程接收到这个标志后,它就可以进入其临界区,并扣留这个标志当它退出临界区之后,标志才被释放,并沿环路继续绕行如果一个接收到标志的进程并不想进入其临界区,只需放行此标志标志传递方式(tokenpassing)需要考虑两种失效情况如果消息丢失,则应能发现并选择一个进程产生一个新的标志;如果一个进程夭折了,则逻辑环就将断裂,此时系统应能重构一个新的逻辑环.9.7进程同步与进程通讯消息传递(MessagePassing)套接字(Socket)远程过程调用(RemoteProcedureCall，RPC)远程方法启用(RemoteMethodInvocation，RMI)消息传递(MessagePassing)同步消息传递-send(接收者,消息,回答):将消息发送给指定的接收者,然后挂起,等待来自接收者的回答消息,之后继续。-receive(发送者,消息):等待接收来自发送进程的消息。-reply(发送者,回答):将回答信息发给发送进程,使之继续执行。同步消息传递站点A,进程Pi…Send(接收者，消息，回答)…阻塞…继续…站点B,进程Pj…receive(发送者，消息)……Reply(发送者，回答)…异步消息传递-send(接收者,消息/回答):将消息或回答发送给接收者,然后继续。-receive(发送者,消息/回答):由发送者处接收消息或回答,然后继续。消息传递(MessagePassing)异步消息传递站点A,进程Pi…send(接收者，消息)继续receive(发送者，回答)…站点B,进程Pj…receive(发送者，消息)……send(接收者，回答)…9.7.2套接字(Socket)套接字定义为通讯的一端地址形式为(IP,port)套接字是一种低级(lowlevel)、不完全可靠的通讯方式AllPorts1024areConsidered“well-known”-TELNETusesport23-FTPusesport21-HTTPusesport80套接字通讯Socket(161.25.19.8/80)Socket(146.86.5.20/1625)主机X(146.86.5.20)网络服务器(161.25.19.8)9.7.3远程过程调用(RPC)套接字是一种低级(lowlevel)、不完全可靠的通讯方式RPCs提供一种高级通讯方式Clientmakesprocedurecallto“remote”serverusingordinaryprocedurecallmechanisms.WidelyacceptedandstandardizedmechanismindistributedenvironmentRPCcanbesynchronizedorasynchronousVec,MAX,10调用消息返回消息v……顾客进程：…………RPC_name(vec,MAX,10)(挂起)…………vec:=v(继续)…………服务进程：…………RPC_name(v,n,k)v:=vec;n:=MAX;k:=10;FORI:=1TOnDOv[I]:=v[I]*k;……站点A站点B例:呼叫方调用参数打包发送等待接收开包结果返回消息参数接收开包调用打包发送结果执行过程返回客户代理服务员代理客户服务员消息被呼叫方RPC的实现为每个远程过程调用创建一个代理进程调用时创建，结束时撤销，代理进程的生存期为调用过程，一个站点可以同时存在多个执行同一远程过程的进程并发性好，空间开销小，时间开销大；对每位顾客创建一个代理进程顾客进程开始时创建代理进程，顾客进程结束时撤销代理进程。并发性好，空间开销大，时间开销小；RPC的实现为每项服务建立代理进程一个站点中仅存在一个执行远程过程的代理进程，读取控制请求，执行相应过程，然后返回回答消息。这个服务进程可被多个顾客调用时空开销小，响应速度慢。9.7.4远程方法启用(RemoteMethodInvocation，RMI)Java中的RPC版本被命名为RMI一个线程可以启用另外一个远程对象中的方法“远程”指处于不同的Java虚拟机(JVM)中远程方法启用(Cont.)RPC与RMI的比较RPC支持过程型程序设计风格RMI支持面向对象程序风格RPC的参数为普通数据类型RMI的参数为对象Local(Non-Remote)ObjectsarePassedbyCopyusingObjectSerializationRemoteObjectsarePassedbyReference9.8死锁处理死锁预防全局资源排序基于“优先权/回退”方式的时间戳死锁避免分布银行家算法死锁检测对每个资源类型的实例集中方式分布方式9.8.1死锁预防死锁预防全局资源排序+请求排序给每个资源赋予一个唯一的整数.如果一个进程没持有资源编号等于或大于i的资源，则可以申请编号为i的资源.优点和缺点simpleimplementationlittleoverheaddifficultyinglobalresourceorderinginconvenientfordistributedprocessestoabidebytheprotocol优先级死锁预防每个进程Pi被赋予一个唯一的优先数优先数用来决定进程Pi是否应该等待进程Pj;如果pri(Pi)pri(Pj),Pi等待;否则Pi回退.Theschemeisdeadlock-free.ForeveryedgePiPjinthewait-forgraph,PihasahigherprioritythanPj.Thusacyclecannotexist.Possibilityofstarvation--lowpriorityprocessmayalwaysberolledback.Resolve:usetimestampinsteadofpriority等-死(wait-die)基于非剥夺策略。当一个进程Pi要求另外一个进程Pj保持的资源时，Pi被允许等待，仅当它具有比Pj更小的邮戳时间，即Pi是比Pj更老，否则Pi回退。例如，设进程P1,P2,P3分别具有邮戳时间5,10,15。如果P1要求P2占用的资源,则P1等待。如果P3要求P2占用的资源,则P3回退。等待边(更老)PiPj(