操作系统chapter(8)课件.ppt

1、第十二章第十二章分布式操作系统分布式操作系统 分布性分布性 自治性自治性 透明性透明性 统一性统一性 第十二章第十二章分布式操作系统分布式操作系统 12.1 标识符系统标识符系统 保证命名标识符的唯一性保证命名标识符的唯一性 支持多级标识符支持多级标识符 名字与名字所代表的对象的物理位置无关名字与名字所代表的对象的物理位置无关 第十二章第十二章分布式操作系统分布式操作系统 12.2 分布式进程互斥分布式进程互斥/同步同步 12.2.1 事件定序事件定序 给系统中的事件提供了一个编序，称前发生关给系统中的事件提供了一个编序，称前发生关系系(happened before，简称，简称HB)，并用，

2、并用“”表示，表示，其定义如下：其定义如下：ab 若若a到到b是同一进程内的两个事件且是同一进程内的两个事件且a在在b前前发生或者发生或者a是一进程中的发送消息的事件而是一进程中的发送消息的事件而b是另是另一进程中接受同一消息的事件一进程中接受同一消息的事件 图图12-3 分布式系统中的事件顺序分布式系统中的事件顺序p0p1p2p3p4站点 P局部时钟 P站点 Q局部时钟 Qq0q1q2q3q4站点 R局部时钟 Rr0r1r2r3r4第十二章第十二章分布式操作系统分布式操作系统 12.2.1 事件定序事件定序 给进程给进程Pi中事件中事件a的逻辑时钟值记为的逻辑时钟值记为Ci(a)进程进程Pi

3、中的事件中的事件a先于进程先于进程Pj中的事件中的事件b (用用ab表示表示)，当且仅当，当且仅当 Ci(a)Cj(b)或者或者 Ci(a)=Cj(b)且且PiPj 若进程号若进程号i进程号进程号j，则，则PiPj。通常把。通常把 称为全序关系称为全序关系 第十二章第十二章分布式操作系统分布式操作系统 12.2.2 Lamport算法算法 Lamport算法基本假定如下：算法基本假定如下：进程进程Pi发送的请求消息形如发送的请求消息形如request(Ti,i)，其中，其中Ti=Ci是进程是进程Pi发送此消息时对应的逻辑时钟值，发送此消息时对应的逻辑时钟值，i代表消息内容代表消息内容 每个进程

4、保持一个请求队列，队列中的请求消息根据每个进程保持一个请求队列，队列中的请求消息根据关系关系定序，队列初始为空定序，队列初始为空 第十二章第十二章分布式操作系统分布式操作系统 12.2.2 Lamport算法算法 下面是下面是Lamport算法描述：算法描述：当进程当进程Pi请求资源时，它把请求消息请求资源时，它把请求消息request(Ti,i)排在排在自己的请求队列中，同时也把该消息发送给系统中的其他自己的请求队列中，同时也把该消息发送给系统中的其他进程；进程；当进程当进程Pj接收到外来消息接收到外来消息request(Ti,i)后，发送回答消后，发送回答消息息reply(Tj,j)，并把

5、，并把request(Ti,i)放入自己的请求队列。放入自己的请求队列。应当说明，若进程应当说明，若进程Pj在收到在收到request(Ti,i)前已提出过对同前已提出过对同一资源的访问请求，那么其时间戳应比一资源的访问请求，那么其时间戳应比(Ti,i)小。小。第十二章第十二章分布式操作系统分布式操作系统 12.2.2 Lamport算法算法 若满足下述两条件，则允许进程若满足下述两条件，则允许进程Pi访问该资源访问该资源(即允许进入即允许进入临界段临界段)：Pi自身请求访问该资源的消息已处于请求队列的最前面；自身请求访问该资源的消息已处于请求队列的最前面；Pi已收到从所有其他进程发来的回答消

6、息，这些回答消已收到从所有其他进程发来的回答消息，这些回答消 息的时间戳均晚于息的时间戳均晚于(T Ti i,i).,i).第十二章第十二章分布式操作系统分布式操作系统 12.2.2 Lamport算法算法 为了释放该资源，为了释放该资源，Pi从自己的队列中撤消请求消息，从自己的队列中撤消请求消息，并发送一个打上时间戳的释放消息并发送一个打上时间戳的释放消息release给其他进程；给其他进程；当进程当进程P Pj j收到收到P Pi i的的releaserelease消息后，它撤消自己队列中消息后，它撤消自己队列中 的原的原P Pi i的的request(Trequest(Ti i,i),i

7、)消息。消息。第十二章第十二章分布式操作系统分布式操作系统 12.3 资源管理资源管理 局部集中式管理局部集中式管理 分级式管理分级式管理 分散式管理及其算法分散式管理及其算法 第十二章第十二章分布式操作系统分布式操作系统 12.4 死锁问题死锁问题 进程等待图进程等待图(process waiting graph，简写，简写PWG)图图12-5 局部局部PWG图图p1p2p2p4p5p3p3站 点 A站 点 B第十二章第十二章分布式操作系统分布式操作系统 12.4.1 预防死锁的时间戳方法预防死锁的时间戳方法 当进程当进程Pi申请当前已由申请当前已由Pj占有的资源时，仅当占有的资源时，仅当P

8、i的时的时间戳小于间戳小于Pj的时间戳的时间戳(即，即，Pi比比Pj年长年长)时，让时，让Pi等待，否等待，否则，则，Pj被撤离。例如，假定进程被撤离。例如，假定进程P1,P2和和P3分别有时间戳分别有时间戳5，10和和15，若，若P1申请已由申请已由P2占有的资源，占有的资源，P1就等待：如就等待：如果果P3申请已由申请已由P2占有的资源，占有的资源，P2就被撤离。就被撤离。第十二章第十二章分布式操作系统分布式操作系统 12.4.2 死锁检测死锁检测 任何局部任何局部PWG中不出现环路并不意味着中不出现环路并不意味着 系统不存在死锁系统不存在死锁 图图12-6 全局全局PWGp1p2p4p5

9、p3第十二章第十二章分布式操作系统分布式操作系统 12.5 任务分布任务分布 任务分布则是把各模块分布给站点，使得它们任务分布则是把各模块分布给站点，使得它们 由站点间的通信由站点间的通信(IPC)引起的开销最小引起的开销最小 12.5.1 基于图论的分布策略基于图论的分布策略 A 640012 B 81230 C 011 0 D 50 E 0 模块模块ABCDEFF(a)IMC开销开销 图图12-9 6模块模块2站点站点 A510B2 C44D63E52模块模块P1开销开销P2开销开销F 4(b)处理开销处理开销 图图12-9 6模块模块2站点站点 B12ACFDE648121135图图12

10、-10 模块通信图模块通信图 12FBCADEP1P21048323512856411445682图图12-11 完全图完全图 第十三章第十三章安全与保密机制安全与保密机制 13.1 概述概述 所谓所谓“系统安全系统安全”包括三个方面：包括三个方面：安全性安全性 完整性完整性 保密性保密性 第十三章第十三章安全与保密机制安全与保密机制 13.2 访问控制的矩阵模型访问控制的矩阵模型 防止非法用户进入系统及合法用户的非法使防止非法用户进入系统及合法用户的非法使 用是访问控制的基本任务用是访问控制的基本任务通常访问控制采用矩阵模型通常访问控制采用矩阵模型原状态原状态基本操作基本操作条件条件 新状态

11、新状态(S,O,A)(S,O,A)entpvg增加特权增加特权psi Soi OS=S,O=OP(si,oj)=P(si,oj)p矩阵其他元素不变矩阵其他元素不变delpvg删除特权删除特权p同上同上SS,OOP(si,oj)P(si,oj)-p矩阵其他元素不变矩阵其他元素不变crtsbj生成主体生成主体s SSS s，OO sP(s,o)P(s,o)，s S，o OP(s,o)，o OP(s,o),s Scrtobj生成客体生成客体o OS S，O O o P(s,o)P(s,o)，s S，o OP(s,o)，s Sdelsbj删除主体删除主体s SSS-s，OO-sP(s,o)P(s,o)

12、，s S，o Odelobj删除客体删除客体o OS S，O O-o P(s,o)P(s,o)，s S，o O图图13-1 访问控制矩阵上的基本操作访问控制矩阵上的基本操作 第十三章第十三章安全与保密机制安全与保密机制 13.2.1 自主访问控制自主访问控制 自主是指主体能够自主地自主是指主体能够自主地(也可能是间接的也可能是间接的)将将 访问权或访问权的某个子集授予其它主体访问权或访问权的某个子集授予其它主体 第十三章第十三章安全与保密机制安全与保密机制 13.2.2 强制访问控制强制访问控制 13.2.2.2 强制访问控制强制访问控制 在强制访问控制中，系统对主体与客体都分配一个在强制访问

13、控制中，系统对主体与客体都分配一个特殊的一般不能更改的安全属性，系统通过比较主体特殊的一般不能更改的安全属性，系统通过比较主体与客体的安全属性来决定一个主体是否能够访问某个与客体的安全属性来决定一个主体是否能够访问某个客体客体 第十三章第十三章安全与保密机制安全与保密机制 13.3 信息流的格阵模型信息流的格阵模型 13.3.1 格阵模型格阵模型 格阵模型用来描述信息流的通道与流动策略格阵模型用来描述信息流的通道与流动策略 信息流动策略信息流动策略 信息状态信息状态 状态转换与信息流状态转换与信息流 格阵结构格阵结构第十三章第十三章安全与保密机制安全与保密机制 13.3.2 流控制机制流控制机

14、制 Lampson研究了研究了3种类型的信息流动通道：种类型的信息流动通道：正规通道正规通道(Legifimate Channels)存储通道存储通道(Storage Channels)隐蔽通道隐蔽通道(Cover Channels)第十三章第十三章安全与保密机制安全与保密机制 13.4 信息加密信息加密 13.4.2 数字签名数字签名 签名必须达到如下效果：在信息通信过程中，收方能够签名必须达到如下效果：在信息通信过程中，收方能够对公正的仲裁者证明其收到报文内容是真实的，而且确实对公正的仲裁者证明其收到报文内容是真实的，而且确实是由那个发送方发送过来的，同时，签名还必须保证发送是由那个发送方发送过来的，同时，签名还必须保证发送方事后不能根据自己的利益来否认他所发送过的报文，而方事后不能根据自己的利益来否认他所发送过的报文，而收方也不能根据自己的利益来伪造报文或签名。收方也不能根据自己的利益来伪造报文或签名。13.4.1 加密算法加密算法