操作系统东南大学滕至阳chapter11

1、第十二章分布式操作系统 分布性 自治性 透明性 统一性 1第十二章分布式操作系统 12.1 标识符系统 保证命名标识符的唯一性 支持多级标识符 名字与名字所代表的对象的物理位置无关 2第十二章分布式操作系统 12.2 分布式进程互斥/同步 12.2.1 事件定序 给系统中的事件提供了一个编序，称前发生关系(happened before，简称HB)，并用“”表示，其定义如下： ab 若a到b是同一进程内的两个事件且a在b前发生或者a是一进程中的发送消息的事件而b是另一进程中接受同一消息的事件 3图12-3 分布式系统中的事件顺序4第十二章分布式操作系统 12.2.1 事件定序 给进程Pi中事件

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

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

4、有其他进程发来的回答消息，这些回答消 息的时间戳均晚于(Ti, i). 8第十二章分布式操作系统 12.2.2 Lamport算法 为了释放该资源，Pi从自己的队列中撤消请求消息， 并发送一个打上时间戳的释放消息release给其他进程；当进程Pj收到Pi的release消息后，它撤消自己队列中 的原Pi的request(Ti , i)消息。 9第十二章分布式操作系统 12.3 资源管理 局部集中式管理 分级式管理 分散式管理及其算法 10第十二章分布式操作系统 12.4 死锁问题 进程等待图(process waiting graph，简写PWG) 图12-5 局部PWG图11第十二章分布式

5、操作系统 12.4.1 预防死锁的时间戳方法 当进程Pi申请当前已由Pj占有的资源时，仅当Pi的时间戳小于Pj的时间戳(即，Pi比Pj年长)时，让Pi等待，否则，Pj被撤离。例如，假定进程P1, P2和P3分别有时间戳5，10和15，若P1申请已由P2占有的资源，P1就等待：如果P3申请已由P2占有的资源，P2就被撤离。 12第十二章分布式操作系统 12.4.2 死锁检测 任何局部PWG中不出现环路并不意味着 系统不存在死锁 图12-6 全局PWG13第十二章分布式操作系统 12.5 任务分布 任务分布则是把各模块分布给站点，使得它们 由站点间的通信(IPC)引起的开销最小 12.5.1 基于

6、图论的分布策略 14A640012B81230C0110D50E0模块ABCDEFF(a) IMC开销 图12-9 6模块2站点 15A510B2C44D63E52模块P1开销P2开销F4(b) 处理开销 图12-9 6模块2站点 16图12-10 模块通信图 17图12-11 完全图 18第十三章安全与保密机制 13.1 概述 所谓“系统安全”包括三个方面： 安全性 完整性 保密性 19第十三章安全与保密机制 13.2 访问控制的矩阵模型 防止非法用户进入系统及合法用户的非法使 用是访问控制的基本任务通常访问控制采用矩阵模型20原状态基本操作条件 新状态(S,O,A)(S,O,A)entpv

7、g增加特权psiSoiOS=S, O=OP(si,oj)=P(si,oj)p矩阵其他元素不变delpvg删除特权p同上SS, OOP(si,oj)P(si,oj)-p矩阵其他元素不变crtsbj生成主体sSSSs，OOsP(s,o)P(s,o)，sS，oOP(s,o)，oOP(s,o),sScrtobj生成客体oOSS，OOoP(s,o)P(s,o)，sS，oOP(s,o)，sSdelsbj删除主体sSSS-s，OO-sP(s,o)P(s,o)，sS，oOdelobj删除客体oOSS，OO-oP(s,o)P(s,o)，sS，oO图13-1 访问控制矩阵上的基本操作 21第十三章安全与保密机制

8、13.2.1 自主访问控制 自主是指主体能够自主地(也可能是间接的)将 访问权或访问权的某个子集授予其它主体 22第十三章安全与保密机制 13.2.2 强制访问控制 13.2.2.2 强制访问控制 在强制访问控制中，系统对主体与客体都分配一个特殊的一般不能更改的安全属性，系统通过比较主体与客体的安全属性来决定一个主体是否能够访问某个客体 23第十三章安全与保密机制 13.3 信息流的格阵模型 13.3.1 格阵模型 格阵模型用来描述信息流的通道与流动策略 信息流动策略 信息状态 状态转换与信息流 格阵结构24第十三章安全与保密机制 13.3.2 流控制机制 Lampson研究了3种类型的信息流动通道： 正规通道(Legifimate Channels) 存储通道(Storage Channels) 隐蔽通道(Cover Channels) 25第十三章安全与保密机制 13.4 信息加密 13.4.2 数字签名 签名必