大学操作系统

1、9.5 事件排序事件排序 n前发生关系前发生关系 (用符号用符号“”表示表示 ).n如果如果A和和B是同一进程内部的事件，而且是同一进程内部的事件，而且A在在B前执行，则有前执行，则有AB。n如果如果A是一个由某一进程发送消息的事件，是一个由某一进程发送消息的事件，B是由另一进程接收该消息的事件，则有是由另一进程接收该消息的事件，则有 AB。n如果如果 AB 且且 BC，则有则有 AC。n非自反的偏序非自反的偏序实现实现 n将每个系统事件都打上一个将每个系统事件都打上一个“时间邮戳时间邮戳”。 n每一个事件对每一个事件对A和和B, 如果如果AB, 则则A的邮戳时的邮戳时间应小于间应小于B的邮戳

2、时间。的邮戳时间。n在每个进程在每个进程Pi内部定义一个相关联的逻辑内部定义一个相关联的逻辑时钟时钟 Lci。n由简单的计数器来实现，即作为在一个进程内由简单的计数器来实现，即作为在一个进程内任何两个连续执行的事件之间的增量。任何两个连续执行的事件之间的增量。“”的实现的实现n一进程在接收到一个消息一进程在接收到一个消息, 而且该消息的邮而且该消息的邮戳时间戳时间TS比接收进程逻辑时钟的当前值还比接收进程逻辑时钟的当前值还大时大时, 接收进程推进它的逻辑时钟。接收进程推进它的逻辑时钟。Count=TS+1。n如果事件如果事件A和事件和事件B的邮戳时间相同的邮戳时间相同, 则事则事件是并发的。件

3、是并发的。9.6 进程互斥进程互斥 (DME) n假设假设n系统包含系统包含n个进程个进程; 每个进程每个进程 Pi 都存在于不同的处理机当中都存在于不同的处理机当中.n每个进程有个临界区需要互斥每个进程有个临界区需要互斥.n必要条件必要条件n如果进程如果进程Pi 正在它的临界区域内执行，则在这个临界区域内没有正在它的临界区域内执行，则在这个临界区域内没有其他进程其他进程 Pj 执行执行.n这里给出三个算法来确保执行进程在其临界区内互斥这里给出三个算法来确保执行进程在其临界区内互斥. n集中算法集中算法n分布算法分布算法n令牌算法令牌算法DME：集中方式集中方式 n指派一个协调者进程指派一个协

4、调者进程( (coordinator),),负负责控制对于临界区的进入。责控制对于临界区的进入。n每一个要求进入临界区的进程都必须发每一个要求进入临界区的进程都必须发送一个请求给协调者进程。送一个请求给协调者进程。n协调者决定哪个进程可以进入临界区域，协调者决定哪个进程可以进入临界区域，之后给它发送答复消息。之后给它发送答复消息。n当进程收到协调者进程的回答信号后当进程收到协调者进程的回答信号后, 它它才能进入自己的临界区才能进入自己的临界区.DME: 集中方式集中方式 n当一个进程退出临界区时，发送一个释当一个进程退出临界区时，发送一个释放信号给协调者进程，然后再继续运行。放信号给协调者进程

5、，然后再继续运行。n无死锁，若协调者进程公平（如无死锁，若协调者进程公平（如FCFS)，无饿死无饿死n每次进入临界区需要三个消息：每次进入临界区需要三个消息：n请求请求n回答回答n释放释放DME: 分布方式分布方式 n算法算法n进程进程Pi想进入临界区，产生一个时间戳想进入临界区，产生一个时间戳TSi, 发消息发消息request(Pi,TSi)给所有其他进程给所有其他进程; n进程进程Pj接收到接收到request消息后，可能立即，消息后，可能立即，也可能延迟回复也可能延迟回复reply消息；消息；n当进程当进程Pi接收到所有进程回复的接收到所有进程回复的reply消息消息后，可以进入临界区

6、；后，可以进入临界区；DME: 分布方式分布方式 (续续.)n进程进程Pi离开临界区后，给所有延迟回复的进离开临界区后，给所有延迟回复的进程发程发reply消息消息n决定进程决定进程Pj 立即回复立即回复request(Pi, TS) 消息消息还是延迟回复主要基于三个因素还是延迟回复主要基于三个因素:n如果如果Pj当前正在临界区中，延迟回复当前正在临界区中，延迟回复.n如果如果Pj不想进入临界区，立即回复不想进入临界区，立即回复.n如果如果Pj想进入但尚未进入临界区，则比较二者的想进入但尚未进入临界区，则比较二者的时间戳时间戳 TS.n如果所持有的时间戳大于如果所持有的时间戳大于TS; 则立即

7、回复则立即回复Pi, (Pi 要求要求占先占先).n否则，延迟回复否则，延迟回复.分布方式分布方式优点优点n确保无死锁确保无死锁n确保无饥饿确保无饥饿n因为进入临界区域是依照时间戳顺序，时间因为进入临界区域是依照时间戳顺序，时间戳顺序确保戳顺序确保FCFS.n每次进入临界区仅需要每次进入临界区仅需要的的消息数量消息数量 2 (n 1)n这是全分布算法最好的结果这是全分布算法最好的结果 DME例子例子n考虑考虑p1,p2,p3构成的系统构成的系统nP1,p3想进入其临界区域想进入其临界区域nP1发发request(1,15)给给p2和和p3, p3发送发送request(3,6)给给p1和和p2

8、. nP2接到请求后，立即回答接到请求后，立即回答p1和和p3；nP1接到接到p3的请求后也立即回答的请求后也立即回答(因为因为p1的时间邮的时间邮戳比戳比P3的时间邮戳大的时间邮戳大)nP3接到接到P1的请求的请求,延迟回答延迟回答;nP3接到来自接到来自P1和和p2的回答的回答,进入临界区进入临界区;nP3离开临界区域离开临界区域,向向P1发回答消息发回答消息,P1进入临界进入临界区域区域DME: 三个缺点三个缺点n每个进程必须知道所有其他进程的存在，每个进程必须知道所有其他进程的存在，这使进程动态增减变的复杂这使进程动态增减变的复杂n若其中一个进程失效，则整个算法崩溃，若其中一个进程失效

9、，则整个算法崩溃，为此需要动态监视所有进程状态为此需要动态监视所有进程状态n不想进入临界区的进程也必须参与协调过不想进入临界区的进程也必须参与协调过程因而算法比较适合稳定且数量较少的程因而算法比较适合稳定且数量较少的进程集合进程集合 标志传递方式标志传递方式(token passing) n这种方式仅适合于逻辑拓扑结构为环形的系统这种方式仅适合于逻辑拓扑结构为环形的系统 n系统中有一个标志系统中有一个标志, 它作为特殊类型的消息在系统它作为特殊类型的消息在系统中环行中环行n当一个进程接收到这个标志后当一个进程接收到这个标志后, 它就可以进入其临它就可以进入其临界区界区, 并扣留这个标志并扣留这

10、个标志 n当它退出临界区之后当它退出临界区之后, 标志才被释放标志才被释放, 并沿环路继续并沿环路继续绕行绕行 n如果一个接收到标志的进程并不想进入其临界区如果一个接收到标志的进程并不想进入其临界区, 只需放行此标志只需放行此标志 标志传递方式标志传递方式(token passing)n需要考虑两种失效情况需要考虑两种失效情况 n如果消息丢失如果消息丢失, 则应能发现并选择一个进程则应能发现并选择一个进程产生一个新的标志产生一个新的标志; n如果一个进程夭折了如果一个进程夭折了, 则逻辑环就将断裂则逻辑环就将断裂, 此时系统应能重构一个新的逻辑环此时系统应能重构一个新的逻辑环.9.7 进程同步

11、与进程通讯进程同步与进程通讯 n消息传递消息传递 (Message Passing) n套接字套接字( (Socket) ) n远程过程调用远程过程调用( (Remote Procedure Call，RPC) ) n远程方法启用远程方法启用( (Remote Method Invocation，RMI) ) 消息传递消息传递 (Message Passing)n同步消息传递同步消息传递 -send( (接收者接收者,消息消息,回答回答) ): 将消息发送将消息发送给指定的接收者给指定的接收者, 然后挂起然后挂起, 等待来自接等待来自接收者的回答消息收者的回答消息, 之后继续。之后继续。 -r

12、eceive( (发送者发送者,消息消息) ): 等待接收来自等待接收来自发送进程的消息。发送进程的消息。 -reply( (发送者发送者,回答回答) ): 将回答信息发给将回答信息发给发送进程发送进程, 使之继续执行。使之继续执行。 同步消息传递站点站点A, 进程进程PiSend(接收者，消息，回答接收者，消息，回答)阻塞阻塞继续继续站点站点B, 进程进程Pjreceive(发送者，消息发送者，消息)Reply(发送者，回答发送者，回答)n异步消息传递异步消息传递 -send(接收者接收者,消息消息/回答回答): 将消息或回将消息或回答发送给接收者答发送给接收者, 然后继续。然后继续。 -r

13、eceive(发送者发送者,消息消息/回答回答): 由发送者由发送者处接收消息或回答处接收消息或回答, 然后继续。然后继续。 消息传递消息传递 (Message Passing)异步消息传递异步消息传递站点站点A, 进程进程Pisend(接收者，消息接收者，消息)继续继续receive(发送者，回答发送者，回答)站点站点B, 进程进程Pjreceive(发送者，消息发送者，消息)send(接收者，回答接收者，回答)9.7.2 套接字套接字(Socket)n套接字定义为通讯的一端套接字定义为通讯的一端 n地址形式为地址形式为( (IP,port) ) n套接字是一种低级套接字是一种低级(low

14、level)、不完全可靠的通不完全可靠的通讯方式讯方式 nAll Ports pri(Pj ), Pi 等待等待;n否则否则 Pi 回退回退.nThe scheme is deadlock-free. nFor every edge Pi Pj in the wait-for graph, Pi has a higher priority than Pj. Thus a cycle cannot exist.nPossibility of starvation-low priority process may always be rolled back.nResolve: use timest

15、amp instead of priority等等-死死( (wait-die) ) n基于非剥夺策略。基于非剥夺策略。n当一个进程当一个进程Pi要求另外一个进程要求另外一个进程Pj保持的资源时，保持的资源时，Pi被允许等待，仅当它具有比被允许等待，仅当它具有比Pj更小的邮戳时间，更小的邮戳时间，即即Pi是比是比Pj更老，否则更老，否则Pi回退。回退。n例如，设进程例如，设进程 P1, P2, P3分别具有邮戳时间分别具有邮戳时间 5, 10, 15。n如果如果P1要求要求P2占用的资源占用的资源, 则则P1等待。等待。n如果如果P3要求要求P2占用的资源占用的资源, 则则P3回退。回退。n等

16、待边等待边n( (更老更老) )PiPj( (更年轻更年轻) )伤伤-等等( (wound-wait) )n基于剥夺策略，是等死的改版。基于剥夺策略，是等死的改版。n当进程当进程Pi要求进程要求进程Pj当前所保持的资源时，则当前所保持的资源时，则Pi获准等待的条件是它具有比获准等待的条件是它具有比Pj更大的邮戳时间，更大的邮戳时间，即即Pi比比Pj更年轻，否则更年轻，否则Pj回退，即回退，即Pj被被Pi所伤。所伤。n例如例如, 设进程设进程 P1, P2, P3分别具有邮戳时间分别具有邮戳时间 5, 10, 15。n如果如果P1要求要求P2所占用的资源，则将剥夺所占用的资源，则将剥夺P2的资源

17、给的资源给P1，P2回退；回退；n如果如果P3要求要求P2占用的资源，则占用的资源，则P3等待。等待。n等待边等待边n( (更年轻更年轻) ) PiPj ( (更老更老) )l银行家算法银行家算法 指定系统中某个进程为银行家指定系统中某个进程为银行家，由它保持执行由它保持执行银行家算法所必需的信息银行家算法所必需的信息。银行家负责系统中资源的分配。银行家负责系统中资源的分配。l优点和缺点优点和缺点easy implementationmay incur too much overheadpossibility of bottleneckif banker fails, the algorith

18、m fails9.8.3 死锁检测死锁检测n每个站点保持一个局部等待图。每个站点保持一个局部等待图。 n站点：所有进程站点：所有进程(或者持有或者请求或者持有或者请求)本地站点本地站点的资源。的资源。站点 AP1P2P3P5P2P4P3站点 B9.8.3 死锁检测死锁检测( (Cont.) )n全局等待图是所有局部等待图的合并。全局等待图是所有局部等待图的合并。 P1P2P3P5P4站点站点 A 和站点和站点 B的全局等待图的全局等待图9.9 资源管理资源管理9.9.1 集中方式集中方式n中央资源管理者负责系统中所有资源的中央资源管理者负责系统中所有资源的分配分配. 系统资源表系统资源表资源类

19、型资源类型 资源数量资源数量 物理位置物理位置 物理特性物理特性 分配状态分配状态 9.9.1 集中方式集中方式( (Cont.) )n优点优点n可以做出全局优化的资源分配策略可以做出全局优化的资源分配策略。n系统扩充和裁减容易系统扩充和裁减容易n这只需要在系统资源分配表中增加一个新项目或这只需要在系统资源分配表中增加一个新项目或删除一个旧项目删除一个旧项目 n减少了资源管理算法的开销减少了资源管理算法的开销n除中央资源管理者外，其它站点不参与资源决策除中央资源管理者外，其它站点不参与资源决策事务事务。9.9.1 集中方式集中方式( (Cont.) )n缺点缺点n可靠性低可靠性低n因为一旦资源

20、管理者失效，则整个系统瘫痪。因为一旦资源管理者失效，则整个系统瘫痪。n尽管引入多个资源管理者可以克服这一缺点，但尽管引入多个资源管理者可以克服这一缺点，但保持多副本的一致性是困难的。保持多副本的一致性是困难的。n中央资源管理者可能成为系统的瓶颈中央资源管理者可能成为系统的瓶颈 n由于中央资源管理者的存在，使整个系统失由于中央资源管理者的存在，使整个系统失去了自治性。去了自治性。9.9.2 分布方式分布方式n每个站点都有一个局部资源表每个站点都有一个局部资源表，用于记用于记载属于该站点的局部资源载属于该站点的局部资源n当一个站点要申请局部资源时当一个站点要申请局部资源时，它可由本地它可由本地得到

21、。得到。n当一个站点要申请全局资源时，它向其它站当一个站点要申请全局资源时，它向其它站点发送申请命令点发送申请命令，其它站点根据情况做出分其它站点根据情况做出分配决策。配决策。9.9.2 分布方式分布方式(Cont.)n优点优点n可靠性高可靠性高n因为任何一个站点、资源或服务的失效通常不会因为任何一个站点、资源或服务的失效通常不会影响整个系统影响整个系统n每个站点具有较高的自治性每个站点具有较高的自治性n它可以将其所拥有的资源提供给整个系统使用，它可以将其所拥有的资源提供给整个系统使用，也可留为私用也可留为私用 9.9.2 分布方式分布方式(Cont.)n缺点缺点n通讯量增加通讯量增加n因为要

22、获得有关资源的信息因为要获得有关资源的信息，每个站点都需要与每个站点都需要与其它站点交换信息其它站点交换信息。n每个站点都需要为资源分配策略的实施付出每个站点都需要为资源分配策略的实施付出开销开销n即资源分配设施消耗局部资源。即资源分配设施消耗局部资源。 9.9.3 层次方式层次方式 n集中方式与分布方式的结合集中方式与分布方式的结合，同时兼有同时兼有二者的优点二者的优点, 并克服二者的缺点并克服二者的缺点 n对于局部资源对于局部资源n采用分布式管理策略采用分布式管理策略 n对于全局资源对于全局资源n采用集中式管理策略采用集中式管理策略 9.10 分布式文件系统分布式文件系统(Distribu

23、ted File System，DFS) n一般结构一般结构 n命名与透明性命名与透明性 n远程文件存取远程文件存取 Remote File Accessn远程文件服务远程文件服务 n副本复制副本复制 n有状态服务与无状态服务有状态服务与无状态服务 n缓存策略缓存策略 9.10.1 一般结构 n分布式文件系统(DFS)是集中式文件系统的分布式实现9.10.2 命名与透明性命名与透明性 n命名是逻辑实体到物理实体的映射命名是逻辑实体到物理实体的映射n对于真正意义的对于真正意义的DFS，整个系统具有统一的整个系统具有统一的命名机制，用户以透明的视图共享所有文件命名机制，用户以透明的视图共享所有文件

24、和存储器。和存储器。n三种命名形式：三种命名形式：n网络命名方式，命名与物理位置完全相关，网络命名方式，命名与物理位置完全相关，不透明不透明 n远程安装方式，远程安装是不透明的，一旦远程安装方式，远程安装是不透明的，一旦安装完毕，远程访问是透明的安装完毕，远程访问是透明的 n完全分布方式，所有文件具有全局唯一的名完全分布方式，所有文件具有全局唯一的名字，文件名与物理位置无关字，文件名与物理位置无关 9.10.3 远程文件存取远程文件存取 n远程文件服务远程文件服务 n工作模式工作模式:n向服务员提出文件访问请求向服务员提出文件访问请求 n服务员执行相应操作服务员执行相应操作 n将结果返回给顾客

25、将结果返回给顾客 n实现实现: RPCn副本复制缓存副本复制缓存 n将远程文件复制到本地，然后如同本地文件一将远程文件复制到本地，然后如同本地文件一样访问样访问 n问题问题: 一致性一致性 副本复制缓存副本复制缓存 n文件仍然由一个位于服务器上的主拷贝标识，文件仍然由一个位于服务器上的主拷贝标识，但其副本可能分散在多个站点上但其副本可能分散在多个站点上n当进程所需文件不在本地时，由服务器向本地当进程所需文件不在本地时，由服务器向本地缓存一个副本缓存一个副本.n存取操作在缓存副本上执行存取操作在缓存副本上执行.n缓存粒度缓存粒度n块为单位，块为单位，n整个文件为单位整个文件为单位.n缓存一致性问

26、题缓存一致性问题n保证主文件和缓存副本的一致保证主文件和缓存副本的一致.缓存副本存放方式缓存副本存放方式 n磁盘缓存磁盘缓存n更可靠更可靠n本地机器故障后恢复容易本地机器故障后恢复容易n内存缓存内存缓存n速度快速度快n支持无盘客户端工作站支持无盘客户端工作站 缓存更新策略缓存更新策略 n通写通写( (write through) ) 每当缓存副本发生变化每当缓存副本发生变化时就更新主本时就更新主本 n可靠性高；可靠性高；n一致性好；一致性好；n效率很低。效率很低。n延迟写延迟写( (delayed write) ) 副本数据经过若干副本数据经过若干次访问次访问( (更新更新) )后才最终写回主

27、本后才最终写回主本n实现效率较高；实现效率较高；n一致性差；一致性差；n可靠性低可靠性低，一旦副本所在结点失效则更新数据可能丢一旦副本所在结点失效则更新数据可能丢失。失。 缓存更新缓存更新策略策略( (Cont.) )n增量刷新增量刷新( (incremental flush) )n定时扫描缓存数据，只将上次更新后发生变定时扫描缓存数据，只将上次更新后发生变化的数据块回写到主本。化的数据块回写到主本。n关闭写关闭写( (write on close) )n只在文件被关闭时才将缓存信息写回主本。只在文件被关闭时才将缓存信息写回主本。 n适合于长时间对数据进行较多更新操作的应用环适合于长时间对数据

28、进行较多更新操作的应用环境境.9.10.4 有状态服务与无状态服务有状态服务与无状态服务n有状态服务有状态服务(State-full service)n服务器端保持文件状态信息服务器端保持文件状态信息n打开文件表，块缓冲打开文件表，块缓冲n无状态服务无状态服务(Stateless service)n服务器端不保持文件状态信息服务器端不保持文件状态信息n无打开文件表，块缓冲无打开文件表，块缓冲有状态服务有状态服务(state-full service)n特征特征nAPI界面中包含显式的打开和关闭命令界面中包含显式的打开和关闭命令n对于打开命令，文件服务器端需要将文件控对于打开命令，文件服务器端需

29、要将文件控制信息读入内存打开文件表中，同时维持文制信息读入内存打开文件表中，同时维持文件的读写指针件的读写指针n关闭时若控制信息已变化则回写磁盘关闭时若控制信息已变化则回写磁盘有状态服务有状态服务( (Cont.) )n优点优点n界面一致，远程文件界面一致，远程文件API与本地文件与本地文件API相同相同 n状态信息在内存，响应快状态信息在内存，响应快 n可以通过预先读等手段提高访问速度可以通过预先读等手段提高访问速度 n可以对文件加锁可以对文件加锁n缺点缺点n对于小量偶然性访问使用麻烦，开销大对于小量偶然性访问使用麻烦，开销大n服务器端以服务器端以open和和close识别远程客户会话期，一

30、识别远程客户会话期，一旦用户不活动要及时撤销文件控制信息，若远程用旦用户不活动要及时撤销文件控制信息，若远程用户忘记户忘记close则给状态表维护带来困难则给状态表维护带来困难无状态服务无状态服务(stateless service)n特征特征nAPI界面中不包含文件打开和关闭命令界面中不包含文件打开和关闭命令 n服务器端在内存文件控制表中不保持远程文服务器端在内存文件控制表中不保持远程文件访问的控制信息件访问的控制信息 n每个文件读写命令必须是自包含的每个文件读写命令必须是自包含的( (self contained) ) n远程文件读写命令中包括：文件名、位置远程文件读写命令中包括：文件名、

31、位置(记录号记录号)、内存地址、内存地址无状态服务无状态服务( (Cont.) ) n优点优点n服务器不需在内存中保持文件状态信息，节服务器不需在内存中保持文件状态信息，节省空间省空间n没有打开文件数的限制没有打开文件数的限制n不需识别远程用户的会话期，实现简单，客不需识别远程用户的会话期，实现简单，客户崩溃时不会造成服务器错误户崩溃时不会造成服务器错误n缺点缺点n大量访问速度慢大量访问速度慢n无法实现预先读无法实现预先读 选举算法选举算法nBully算法算法nSuppose That process Pi send a request that is not answered by the

32、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算法算法nProcess Pi send an election message to every process with a higher priority numb

33、er. Process Pi then wait for a time interval T for an answer from anyone of these processes.nIf 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 se

34、nds a message to inform all active process with priority number less than I that Pi is the coordinator. Bully算法算法nIf 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 elect

35、ing itself 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算法算法nIf Pi is not the coordinator, then, at any time during execution, Pi may receive one of the following messages from process Pj: