操作系统(东南大学滕至阳ppt)chapter(8)

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