网络与分布式操作系统1

《网络与分布式操作系统1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、9.5事件排序清华大学前发生关系(用符号“”表示).如果A和B是同一进程内部的事件，而且A在B前执行，则有AB。如果A是一个由某一进程发送消息的事件，B是由另一进程接收该消息的事件，则有AB。如果AB且BC，则有AC。非自反的偏序实现将每个系统事件都打上一个“时间邮戳”。每一个事件对A和B,如果AB,则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(P

4、i,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接到请求后，立

5、即回答p1和p3；P1接到p3的请求后也立即回答(因为p1的时间邮戳比P3的时间邮戳大)P3接到P1的请求,延迟回答;P3接到来自P1和p2的回答,进入临界区;P3离开临界区域,向P1发回答消息,P1进入临界区域DME:三个缺点每个进程必须知道所有其他进程的存在，这使进程动态增减变的复杂若其中一个进程失效，则整个算法崩溃，为此需要动态监视所有进程状态不想进入临界区的进程也必须参与协调过程．因而算法比较适合稳定且数量较少的进程集合标志传递方式(tokenpassing)这种方式仅适合于逻辑拓扑结构为环形的系统系统中有一个标志,它作为特殊类型的消息在系统中环行当一个进程接收到这个

6、标志后,它就可以进入其临界区,并扣留这个标志当它退出临界区之后,标志才被释放,并沿环路继续绕行如果一个接收到标志的进程并不想进入其临界区,只需放行此标志标志传递方式(tokenpassing)需要考虑两种失效情况如果消息丢失,则应能发现并选择一个进程产生一个新的标志;如果一个进程夭折了,则逻辑环就将断裂,此时系统应能重构一个新的逻辑环.9.7进程同步与进程通讯消息传递(MessagePassing)套接字(Socket)远程过程调用(RemoteProcedureCall，RPC)远程方法启用(RemoteMethodInvocation，RMI)消息传递(MessagePa

7、ssing)同步消息传递-send(接收者,消息,回答):将消息发送给指定的接收者,然后挂起,等待来自接收者的回答消息,之后继续。-receive(发送者,消息):等待接收来自发送进程的消息。-reply(发送者,回答):将回答信息发给发送进程,使之继续执行。同步消息传递站点A,进程Pi…Send(接收者，消息，回答)…阻塞…继续…站点B,进程Pj…receive(发送者，消息)……Reply(发送者，回答)…异步消息传递-send(接收者,消息/回答):将消息或回答发送给接收者,然后继续。-recei