第十二章第十二章分布式操作系统分布式操作系统分布性分布性自治性自治性透明性透明性统一性统一性操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.1标识符系统标识符系统保证命名标识符的唯一性保证命名标识符的唯一性支持多级标识符支持多级标识符名字与名字所代表的对象的物理位置无关名字与名字所代表的对象的物理位置无关操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2分布式进程互斥分布式进程互斥/同步同步12.2.1事件定序事件定序给系统中的事件提供了一个编序，称前发生关给系统中的事件提供了一个编序，称前发生关系系(happenedbefore，简称，简称HB)，并用，并用“”表示，表示，其定义如下：其定义如下：ab若若a到到b是同一进程内的两个事件且是同一进程内的两个事件且a在在b前发前发生或者生或者a是一进程中的发送消息的事件而是一进程中的发送消息的事件而b是另一是另一进程中接受同一消息的事件进程中接受同一消息的事件操作系统东南大学滕至阳chapter(6)课件图图12-3分布式系统中的事件顺序分布式系统中的事件顺序操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2.1事件定序事件定序给进程给进程Pi中事件中事件a的逻辑时钟值记为的逻辑时钟值记为Ci(a)进程进程Pi中的事件中的事件a先于进程先于进程Pj中的事件中的事件b(用用ab表示表示)，当且仅当，当且仅当Ci(a)Cj(b)或者或者Ci(a)=Cj(b)且且PiPj若进程号若进程号i进程号进程号j，则，则PiPj。通常把。通常把称为全序关系称为全序关系操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2.2Lamport算法算法Lamport算法基本假定如下：算法基本假定如下：进程进程Pi发送的请求消息形如发送的请求消息形如request(Ti,i)，其中，其中Ti=Ci是进程是进程Pi发送此消息时对应的逻辑时钟值，发送此消息时对应的逻辑时钟值，i代表消息内容代表消息内容每个进程保持一个请求队列，队列中的请求消息根据每个进程保持一个请求队列，队列中的请求消息根据关系关系定序，队列初始为空定序，队列初始为空操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2.2Lamport算法算法下面是下面是Lamport算法描述：算法描述：当进程当进程Pi请求资源时，它把请求消息请求资源时，它把请求消息request(Ti,i)排在排在自己的请求队列中，同时也把该消息发送给系统中的其他自己的请求队列中，同时也把该消息发送给系统中的其他进程；进程；当进程当进程Pj接收到外来消息接收到外来消息request(Ti,i)后，发送回答消后，发送回答消息息reply(Tj,j)，并把，并把request(Ti,i)放入自己的请求队列。放入自己的请求队列。应当说明，若进程应当说明，若进程Pj在收到在收到request(Ti,i)前已提出过对同前已提出过对同一资源的访问请求，那么其时间戳应比一资源的访问请求，那么其时间戳应比(Ti,i)小。小。操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2.2Lamport算法算法若满足下述两条件，则允许进程若满足下述两条件，则允许进程Pi访问该资源访问该资源(即允许进入即允许进入临界段临界段)：Pi自身请求访问该资源的消息已处于请求队列的最前面；自身请求访问该资源的消息已处于请求队列的最前面； Pi已收到从所有其他进程发来的回答消息，这些回答消已收到从所有其他进程发来的回答消息，这些回答消 息的时间戳均晚于息的时间戳均晚于(T(Ti i, i). , i). 操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.2.2Lamport算法算法为了释放该资源，为了释放该资源，Pi从自己的队列中撤消请求消息，从自己的队列中撤消请求消息， 并发送一个打上时间戳的释放消息并发送一个打上时间戳的释放消息release给其他进程；给其他进程；当进程当进程P Pj j收到收到P Pi i的的releaserelease消息后，它撤消自己队列中消息后，它撤消自己队列中 的原的原P Pi i的的request(Trequest(Ti i , i), i)消息。消息。 操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.3资源管理资源管理局部集中式管理局部集中式管理分级式管理分级式管理分散式管理及其算法分散式管理及其算法操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.4死锁问题死锁问题进程等待图进程等待图(processwaitinggraph，简写，简写PWG)图图12-5局部局部PWG图图操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.4.1预防死锁的时间戳方法预防死锁的时间戳方法当进程当进程Pi申请当前已由申请当前已由Pj占有的资源时，仅当占有的资源时，仅当Pi的时的时间戳小于间戳小于Pj的时间戳的时间戳(即，即，Pi比比Pj年长年长)时，让时，让Pi等待，否等待，否则，则，Pj被撤离。例如，假定进程被撤离。例如，假定进程P1,P2和和P3分别有时间戳分别有时间戳5，10和和15，若，若P1申请已由申请已由P2占有的资源，占有的资源，P1就等待：如就等待：如果果P3申请已由申请已由P2占有的资源，占有的资源，P2就被撤离。就被撤离。操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.4.2死锁检测死锁检测任何局部任何局部PWG中不出现环路并不意味着中不出现环路并不意味着 系统不存在死锁系统不存在死锁图图12-6全局全局PWG操作系统东南大学滕至阳chapter(6)课件第十二章第十二章分布式操作系统分布式操作系统12.5任务分布任务分布任务分布则是把各模块分布给站点，使得它们任务分布则是把各模块分布给站点，使得它们 由站点间的通信由站点间的通信(IPC)引起的开销最小引起的开销最小12.5.1基于图论的分布策略基于图论的分布策略操作系统东南大学滕至阳chapter(6)课件A640012B81230 C011 0 D50 E0 模块模块ABCDEFF(a)IMC开销开销图图12-96模块模块2站点站点操作系统东南大学滕至阳chapter(6)课件A510B2 C44D63E52模块模块P1开销开销P2开销开销F 4(b)处理开销处理开销 图图12-96模块模块2站点站点操作系统东南大学滕至阳chapter(6)课件图图12-10模块通信图模块通信图操作系统东南大学滕至阳chapter(6)课件图图12-11完全图完全图操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.1概述概述所谓所谓“系统安全系统安全”包括三个方面：包括三个方面： 安全性安全性 完整性完整性 保密性保密性操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.2访问控制的矩阵模型访问控制的矩阵模型防止非法用户进入系统及合法用户的非法使防止非法用户进入系统及合法用户的非法使用是访问控制的基本任务用是访问控制的基本任务通常访问控制采用矩阵模型通常访问控制采用矩阵模型操作系统东南大学滕至阳chapter(6)课件原状态原状态基本操作基本操作条件条件新状态新状态(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 OSS，OO oP(s,o)P(s,o)，s S，o OP(s,o)，s Sdelsbj删除主体删除主体s SSS- -s，OO- -sP(s,o)P(s,o)，s S，o Odelobj删除客体删除客体o OSS，OO- -oP(s,o)P(s,o)，s S，o O图图13-1访问控制矩阵上的基本操作访问控制矩阵上的基本操作操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.2.1自主访问控制自主访问控制自主是指主体能够自主地自主是指主体能够自主地(也可能是间接的也可能是间接的)将将 访问权或访问权的某个子集授予其它主体访问权或访问权的某个子集授予其它主体操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.2.2强制访问控制强制访问控制13.2.2.2强制访问控制强制访问控制在强制访问控制中，系统对主体与客体都分配一个在强制访问控制中，系统对主体与客体都分配一个特殊的一般不能更改的安全属性，系统通过比较主体特殊的一般不能更改的安全属性，系统通过比较主体与客体的安全属性来决定一个主体是否能够访问某个与客体的安全属性来决定一个主体是否能够访问某个客体客体操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.3信息流的格阵模型信息流的格阵模型13.3.1格阵模型格阵模型格阵模型用来描述信息流的通道与流动策略格阵模型用来描述信息流的通道与流动策略信息流动策略信息流动策略信息状态信息状态状态转换与信息流状态转换与信息流格阵结构格阵结构操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.3.2流控制机制流控制机制Lampson研究了研究了3种类型的信息流动通道：种类型的信息流动通道： 正规通道正规通道(LegifimateChannels) 存储通道存储通道(StorageChannels) 隐蔽通道隐蔽通道(CoverChannels)操作系统东南大学滕至阳chapter(6)课件第十三章第十三章安全与保密机制安全与保密机制 13.4信息加密信息加密13.4.2数字签名数字签名签名必须达到如下效果：在信息通信过程中，收方能够签名必须达到如下效果：在信息通信过程中，收方能够对公正的仲裁者证明其收到报文内容是真实的，而且确实对公正的仲裁者证明其收到报文内容是真实的，而且确实是由那个发送方发送过来的，同时，签名还必须保证发送是由那个发送方发送过来的，同时，签名还必须保证发送方事后不能根据自己的利益来否认他所发送过的报文，而方事后不能根据自己的利益来否认他所发送过的报文，而收方也不能根据自己的利益来伪造报文或签名。收方也不能根据自己的利益来伪造报文或签名。13.4.1加密算法加密算法操作系统东南大学滕至阳chapter(6)课件操作系统东南大学滕至阳chapter(6)课件