09第九章网络与分布式操作系统1.ppt

37 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比接收进程逻辑时钟的当前值还大时, 接收进程推进它的逻辑时钟。Count=TS+1。 如果事件A和事件B的邮戳时间相同, 则事件是并发的。 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: 三个缺点 每个进程必须知道所有其他进程的存在，这使进程动态增减变的复杂 若其中一个进程失效，则整个算法崩溃，为此需要动态监视所有进程状态 不想进入临界区的进程也必须参与协调过程．因而算法比较适合稳定且数量较少的进程集合 标志传递方式(token passing) 这种方式仅适合于逻辑拓扑结构为环形的系统 系统中有一个标志, 它作为特殊类型的消息在系统中环行 当一个进程接收到这个标志后, 它就可以进入其临界区, 并扣留这个标志 当它退出临界区之后, 标志才被释放, 并沿环路继续绕行 如果一个接收到标志的进程并不想进入其临界区, 只需放行此标志 标志传递方式(token passing) 需要考虑两种失效情况 如果消息丢失, 则应能发现并选择一个进程产生一个新的标志; 如果一个进程夭折了, 则逻辑环就将断裂, 此时系统应能重构一个新的逻辑环. 9.7 进程同步与进程通讯 消息传递 (Message Passing) 套接字(Socket) 远程过程调用(Remote Procedure Call，RPC) 远程方法启用(Remote Method Invocation，RMI) 消息传递 (Message Passing) 同步消息传递 -send(接收者,消息,回答): 将消息发送给指定的接收者, 然后挂起, 等待来自接收者