操作系统：09第九章 网络与分布式操作系统2）

9.5 事件排序事件排序 9.5.1 先发生关系先发生关系(用符号用符号“”表示表示):n 如果如果 A 和和 B 是同一进程内部的事件是同一进程内部的事件,而且而且 A 在在 B 前执行前执行,则有则有AB;n 如果如果 A 是一个由某一进程发送消息的事件是一个由某一进程发送消息的事件,B是由另一进程接收该消息的事件是由另一进程接收该消息的事件,则有则有 A B。n 如果如果 A B 且且 B C,则有则有 A C。n先发生关系是非自反的先发生关系是非自反的偏序关系偏序关系;n如果两个事件没有关系如果两个事件没有关系，则两个事件可以并行；，则两个事件可以并行；n如果如果A、B分别是进程分别是进程P、Q中的两个事件中的两个事件,且有且有A B,则则P进程中进程中A之前的事件与之前的事件与Q进程中进程中B之后的事件不能并行。之后的事件不能并行。9.5.1 先发生关系先发生关系 进程时间与事件描述进程时间与事件描述Pp1p0p2p3p4Qq1q0q2q3q4Rr1r0r2r3r4Ss1s0s2s3s49.5.2 全序关系全序关系 n全序关系全序关系:基于时间戳基于时间戳(timestamp)的方法的方法将每个系统事件都打上一个将每个系统事件都打上一个“时间戳时间戳”:对每一个事件对每一个事件A 和和 B,如果如果 A B,则则 A 的时间戳应小于的时间戳应小于 B 的时间戳。的时间戳。n时间戳定义时间戳定义 在每个进程在每个进程 Pi 内部定义一个相关联的逻辑时钟内部定义一个相关联的逻辑时钟 LCi,初值为初值为0;n带有时间戳的消息定义带有时间戳的消息定义:(m,Tj,j)含义含义:“进程进程Pj发送消息发送消息m”这一事件发生时这一事件发生时,进程进程Pj的逻辑时钟的逻辑时钟LCj=Tj.n全序关系的实现：全序关系的实现：l进程进程Pi某事件发生前某事件发生前,LCi=LCi+1.该事件的时间戳该事件的时间戳LCi.l进程进程Pi接收到一个消息接收到一个消息(m,Tj,j),则则:LCi=maxLCi,Tj+1l对于消息对于消息(x,Ti,i)和和(y,Tj,j),如果如果 TiTj|(Ti=Tj)&ij)则称则称x在在y之前。之前。9.5.2 全序关系全序关系(Cont.)Pp1p0p2p3p4Qq1q0q2q3q4Rr1r0r2r3r4Ss1s0s2s3s4事件与逻辑时间事件与逻辑时间事件事件p0p1 p2 p3 p4 q0 q1q2 q3 q4r0r1 r2 r3 r4 s0 s1 s2 s3s4逻辑时间逻辑时间145671237 818910 11123459.5.2 全序关系全序关系(Cont.)9.6 进程互斥进程互斥 n假设假设(Distributed Management Environment:DME)l 系统包含系统包含n个处理机个处理机;l 每个处理机中仅有一个进程每个处理机中仅有一个进程;l 每个进程有一个临界区需要互斥。每个进程有一个临界区需要互斥。n必要条件必要条件 如果进程如果进程 Pi 正在它的临界区域内执行正在它的临界区域内执行,则在这个临界区域内没有其它进程则在这个临界区域内没有其它进程 Pj 执行。执行。n三个算法确保执行进程在其临界区内互斥三个算法确保执行进程在其临界区内互斥:l 集中算法集中算法l 分布算法分布算法l 标志传递算法标志传递算法9.6.1 集中方式集中方式集中方式处理过程集中方式处理过程:n指派一个协调者进程指派一个协调者进程(coordinator),负责控制对于临界区的进入负责控制对于临界区的进入;n每一个要求进入临界区的进程都必须每一个要求进入临界区的进程都必须 发送一个请求给协调者进程发送一个请求给协调者进程;n协调者决定哪个进程可以进入临界区域协调者决定哪个进程可以进入临界区域,之后给它发送应答消息之后给它发送应答消息;n当进程收到协调者进程的应答消息后当进程收到协调者进程的应答消息后,才能进入自己的临界区。才能进入自己的临界区。n当一个进程退出临界区时当一个进程退出临界区时,发送一个释放信号给协调者进程发送一个释放信号给协调者进程,然后再继续运行然后再继续运行;n无死锁无死锁;若协调者进程公平若协调者进程公平(如如FCFS),无饿死无饿死;n每次进入临界区需要三个消息：每次进入临界区需要三个消息：l 请求请求:进程进程;l 应答应答:协调者协调者;l 释放释放:进程。进程。9.6.1 集中方式集中方式(Cont.)9.6.2 分布方式分布方式(Richard/Agrawala)全分布互斥算法全分布互斥算法:进程进程 Pi 想进入临界区想进入临界区,产生一个时间戳产生一个时间戳TSi,发消息发消息 request(Pi,TSi,i)给所有其它进程给所有其它进程;进程进程 Pj 接收到接收到 request 消息后消息后,可能立即可能立即,也可能延迟回复也可能延迟回复 reply 消息消息:lPj 在临界区在临界区,延迟回复延迟回复;lPj 不想进入临界区不想进入临界区,立即回复立即回复;lPj 想进入、但还未进入临界区想进入、但还未进入临界区,比较两者的时间戳比较两者的时间戳:若若(TSi,i)(TSj,j),则立即回复则立即回复;否则延迟回复。否则延迟回复。当进程当进程 Pi 接收到所有进程回复的接收到所有进程回复的 reply 消息后消息后,可以进入临界区可以进入临界区;进程进程 Pi 离开临界区后离开临界区后,给所有延迟回复的进程发给所有延迟回复的进程发reply 消息。消息。9.6.2 分布方式分布方式(Cont.)DME例子例子:系统有系统有p1,p2,p3,p1,p3想进入其临界区域。想进入其临界区域。p1发送发送request(1,15)给给 p2 和和 p3,p3发送发送request(3,6)给给 p1 和和 p2;p1p3p2replyreplyP3接收到两个接收到两个reply,进入临界区。延迟应答进入临界区。延迟应答P1P2接收到接收到P3的延迟的延迟reply后后,进入临界区。进入临界区。request(1,15)request(1,15)request(3,6)request(3,6)(立即立即)reply(P3退出临界区后退出临界区后)reply分布方式分布方式优点优点n确保无死锁确保无死锁;n确保无饥饿确保无饥饿:因为进入临界区域是依照时间戳顺序因为进入临界区域是依照时间戳顺序,时间戳顺序确保时间戳顺序确保FCFS.n每个进程每次进入临界区需要的消息数量每个进程每次进入临界区需要的消息数量:2(n1)这是全分布算法最好的结果。这是全分布算法最好的结果。9.6.2 分布方式分布方式(Cont.)9.6.2 分布方式分布方式(Cont.)分布方式缺点分布方式缺点n每个进程必须知道所有其它进程的存在每个进程必须知道所有其它进程的存在,这使进程动态增减变的复杂这使进程动态增减变的复杂;n若其中一个进程失效若其中一个进程失效,则整个算法崩溃则整个算法崩溃,为此需要动态监视所有进程状态为此需要动态监视所有进程状态;n不想进入临界区的进程也必须参与协调过程不想进入临界区的进程也必须参与协调过程,因而算法比较适合稳定且数量较少的进程集合。因而算法比较适合稳定且数量较少的进程集合。9.6.3 标志传递方式标志传递方式仅适合于逻辑拓扑结构为环形的系统。仅适合于逻辑拓扑结构为环形的系统。n系统中有一个标志系统中有一个标志,它作为特殊类型的消息在系统中环行它作为特殊类型的消息在系统中环行;n当一个进程接收到这个标志后当一个进程接收到这个标志后,它就可以进入其临界区它就可以进入其临界区,并扣留这个标志并扣留这个标志;n当它退出临界区之后当它退出临界区之后,标志才被释放标志才被释放,并沿环路继续绕行并沿环路继续绕行;n如果一个接收到标志的进程并不想进入其临界区如果一个接收到标志的进程并不想进入其临界区,只需放行此标志只需放行此标志token passing需要考虑两种失效情况需要考虑两种失效情况 n如果消息丢失如果消息丢失,则应能发现并选择一个进程则应能发现并选择一个进程产生一个新的标志产生一个新的标志;n如如果果一一个个进进程程夭夭折折了了,则则逻逻辑辑环环就就将将断断裂裂,此时系统应能重构一个新的逻辑环此时系统应能重构一个新的逻辑环.9.6.3 标志传递方式标志传递方式(Cont)9.7 进程同步与进程通信进程同步与进程通信 n消息传递消息传递(Message Passing)n套接字套接字(Socket)n远程过程调用远程过程调用 Remote Procedure Call:RPCn远程方法启用远程方法启用 Remote Method Invocation:RMI9.7.1 消息传递消息传递(Message Passing)同步消息传递同步消息传递 send(接收者接收者,消息消息)将消息发送给指定的接收者将消息发送给指定的接收者,然后挂起然后挂起,等待来自接收者的应答消息等待来自接收者的应答消息,之后继续。之后继续。receive(发送者发送者,消息消息)等待接收来自发送进程的消息。等待接收来自发送进程的消息。reply(发送者发送者,应答应答)将应答信息发给发送进程将应答信息发给发送进程,使之继续执行。使之继续执行。9.7.1 消息传递消息传递(Cont.)进程进程Pi.send(接收者接收者,消息消息);.阻阻 塞塞继继 续续站点站点A进程进程Pj.receive(发送者发送者,消息消息);reply(发送者发送者,应答应答)站点站点B同步消息传递同步消息传递 异步消息传递异步消息传递 send(接收者接收者,消息消息/应答应答)将消息将消息/回答发送给接收者回答发送给接收者,然后继续。然后继续。receive(发送者发送者,消息消息/应答应答)由发送者处接收消息由发送者处接收消息/应答应答,然后继续。然后继续。9.7.1 消息传递消息传递(Cont.)9.7.1 消息传递消息传递(Cont.)进程进程Pi.send(接收者接收者,消息消息);继继 续续receive(发送者发送者,应答应答);站点站点A进程进程Pj.receive(发送者发送者,消息消息);send(发送者发送者,应答应答)站点站点B异步消息传递异步消息传递9.7.2 套接字套接字(Socket)n套接字是一种端套接字是一种端端的通信协议端的通信协议;n套接字定义为通信的一端套接字定义为通信的一端,与一个地址相联系与一个地址相联系;n地址形式为地址形式为(IP,port);n套接字是一种低级套接字是一种低级(low level),不完全可靠的通信方式不完全可靠的通信方式;nAll Ports 1024 are Considered“well-known”l TELNET uses port 23l FTP uses port 21l HTTP uses port 809.7.2 套接字套接字(Socket)socket():建立流式套接字建立流式套接字,返回套接字号返回套接字号sconnect():将套接字将套接字s与远端主机连接与远端主机连接send()/recev():在在s上传输数据上传输数据,直到结束直到结束closesocket():关闭套接字关闭套接字s,结束结束TCP/IP通信通信客户端客户端(146.86.5.20)服务器端服务器端(161.25.19.8)socket():建立流式套接字建立流式套接字,返回套接字号返回套接字号sbind():绑定套接字绑定套接字s与本地地址与本地地址listen():通知通知TCP/IP,服务器准备好接受连接服务器准备好接受连接accept():接受连接接受连接,并得到新的套接字并得到新的套接字nsrecev()/send():在在ns上传输数据上传输数据,直到结束直到结束closesocket():关闭套接字关闭套接字nsclosesocket():关闭套接字关闭套接字s建立连接建立连接请求服务请求服务服务