分布式操作系统复习大纲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,分布式操作系统复习大纲,（一）分布式操作系统,（,0,）,分布式操作系统的定义,（,1,）,分布式系统的体系结构类型,（,2,）,构造分布式操作系统的途径,（,3,）,分布式操作系统的层次结构,（,4,）,多机，网络和分布式操作系统间差别,（,5,）,透明性,(Transparency),意义,（,6,）,分布式计算机系统的资源管理,（,7,）,分布式操作系统的同步算法,（,0,）,分布式操作系统的,定义,文献中已经给出分布式系统的各种定义，没有一个是满意的并且没有一个为其他所同意。为此，给出一个松散的特征就够了。,Tanenbaum,给出如下定义：,A distributed system is a collection of independent computers that appears to its user as a single coherent system.,分布式操作系统,是分布式系统的操作系统。,（,1,）分布式系统的体系结构类型,Tanenbaum,和,Renesse,将分布式系统分成五类：,小型机类型,(minicomputer model),工作站类型,(workstation model),处理机池类型,(processor pool model),工作站服务器类型,(workstation-server model),混合类型,(hybrid model),（,2,）构造分布式操作系统的途径,从头开始；,修改、扩充式；,层次式。,（,3,）分布式操作系统的层次结构,一个分布式操作系统大致可分成四层，由内向外依次是：,执行层；,进程通信层；,服务支持层；,用户接口层。,（,4,）多机、网络和分布式操作系统间差别,（,5,）透明性,(Transparency),意义,透明性,描述,访问,Access,隐藏数据表示中的差异以及如何访问资源,位置,Location,隐藏一个资源位于何处,迁移,Migration,隐藏一个资源可能移到另外位置,浮动,Relocation,隐藏在使用时一个资源可能移到另外位置,复制,Replication,隐藏一个资源被复制,并发,Concurrency,隐藏一个资源可能被若干竞争用户共享,失效,Failure,隐藏一个资源的失效和恢复,存留,Persistence,隐藏是否一个（软件）资源在内存或在磁盘上,（,6,）分布式计算机系统的资源管理,从单个资源与多个管理者的相互关系,从多个资源与多个管理者的相互关系,从实用的角度,分布式计算机系统的资源管理的算法,从单个资源与多个管理者的相互关系,全集中管理方式 即专制,(autocratic),管理,功能分布管理方式即分担管理或分割,(partitioned),管理,浮动管理方式即 轮流,(successive),管理,全分散管理方式即 民主,(democratic),管理,从多个资源与多个管理者的相互关系,集中,:,所有资源属一个管理者管理。,分管：每一资源只属一个管理者管理。,部分管理：每一资源属于若干管理者管理。,合管：每一资源属于全部管理者共同管理。,从实用的角度,分布式计算机系统的资源管理的算法,招标（投标）算法,回声算法,由近及远算法,（,7,）分布式操作系统的同步算法,偏序,Happened-Before,关系,(,筒称,HB),的定义,时钟（,clock,）条件的定义,系统的逻辑时钟的定义,事件,e,的时间戳的定义,全序先于（,关系的定义,向量时钟的定义和向量时钟的实现规则以及例子,（,7,）分布式操作系统的同步算法,集中式互斥算法,分布式算法（,Lamport,算法）,分布式算法（,Ricart-Agrawala,算法）,令牌算法,欺负（霸主,Bully,）算法,局部状态的定义,全局状态的定义,一致的全局状态、不一致的全局状态、无过渡的全局状态和强一致的全局状态的定义及例子,偏序,Happened-Before,关系,(,筒称,HB),的定义：,a,b,若,a,和,b,是同一进程中的两个事件，且,a,在,b,前发生；或者，,若,a,是一进程中发送消息的事件，,b,是另一进程中接收同一消息的事件。,该关系是传递的，即若,a,b,且,b,c,，则有,a,c,。,该关系是非自反的，即,a(a,a,),，因一事件不可能它自身之前发生。,时钟（,clock,）条件的定义：,对系统中的任何事件,a,和,b,，若,a,b,，则,LC(a,),必须小于,LC(b,),。,系统的逻辑时钟的定义：,系统的逻辑时钟（,Logic Clock,简记为,LC,）是满足时钟条件的系统事件集合到非负整数的映射。,当事件,e,进程,P,i,时，,LC(e,)=,LC,i,(e,),。,事件,e,的时间戳的定义：,称事件,e,的逻辑时钟值,LC(e,),为事件,e,的时间戳（,Time Stamp,简记为,TS,）。,全序先于（,）关系的定义：,我们称进程,p,i,中的事件,a,先于进程,p,j,中的事件,b(,以,a,b,表示,),当且仅当,LC,i,(a),LC,j,(b),；或,LC,i,(a)=,LC,j,(b),，且,p,i,p,j,，其中关系“,”是进程的一个任意偏序。,实现关系“,”的一个简单方法是给系统中每个进程赋以一个唯一的进程号，且规定：若,i 0),IR2,如果进程,P,i,的事件,a,是发送消息,m,事件，则消息,m,被赋予一个向量时间戳,tm=,VC,i,(a),；,进程,P,j,接收同样消息,m,时,VC,j,作如下修改：,k,VC,j,k:=,max(VC,j,k,tmk,),向量时钟例子,集中式互斥算法,分布式算法（,Lamport,算法）,分布式算法（,Ricart-Agrawala,算法）,令牌算法,选举算法,欺负（霸主,Bully,）算法,局部状态的定义：,transit(LS,i,LS,j,)=,m,ij,|,send(m,ij,),LS,i,rec(m,ij,),LS,j,inconsistent(,LS,i,LS,j,)=,m,ij,|,send(m,ij,),LS,i,rec(m,ij,),LS,j,全局状态的定义：,一个系统的全局状态,GS,是一个它的所有场点的局部状态集合；即,GS=LS1,LS2,.,LSn,其中,n,是系统中场点的个数。,一致的全局状态、不一致的全局状态、无过渡的全局状态和强一致的全局状态的定义及例子：,一个全局状态,GS=LS,1,LS,2,.,LS,n,是一致的(,consistent),当且仅当,1,i n,1,j n,(,inconsistent,(LS,i,LS,j,)=,),一个全局状态是无过渡的(,transitless,)，,当且仅当,1,i n,1,j n,(,transit,(LS,i,LS,j,)=,),因此，,在一个无过渡的全局状态中，所有通信通道均为空。,如果一个全局状态是一致的和无过渡的，则称为强一致的(,strongly consistent)。,例子,（二）分布式共享内存,（,1,）体系结构和动力,2,）实现分布式共享内存的算法,（,3,）存储一致性,（,4,）一致性协议,（,1,）体系结构和动力,（,2,）实现分布式共享内存的算法,中央服务器,(Central-Server),算法,迁移算法,读复制,(Read-,Replicatin,),算法,完全复制算法,（,3,）存储一致性,严格一致性（,Strict Consistency,）,顺序的一致性,(Sequential consistency),因果一致性,一般一致性,(General Consistency),处理机一致性,(Processor consistency),管道（,PRAM,）一致性,弱一致性,(Weak consistency),释放一致性,(Release consistency),入口一致性,(Release consistency),（,4,）一致性协议。,写,-,使无效协议和,写更新协议,（三）分布式系统中的死锁,（,1,）,死锁和饥饿的定义,（,2,）,分布式死锁的策略,（,3,）,利用时间戳预防死锁方法,（,4,）,死锁检测方法,（,1,）死锁和饥饿的定义,（,2,）分布式死锁的策略,四个策略被用来处理死锁：,鸵鸟,(,ostirch,),算法：忽略死锁问题。,检测和恢复,(detection and recovery),：允许死锁出现，检测并试图恢复之。,预防,(prevention)静态地使死锁结构上成为不可能。,避免,(avoidance),：由仔细地分配资源算法避免死锁。,（,3,）利用时间戳预防死锁方法,等,-,死（,wait-die,）方法,因伤（,wound-wait,）等待,（,4,）死锁检测方法,集中式死锁检测方式,层次式死锁检测方法,其它分布式方法,Chandy-Misra-Haas,算法,分布式事务处理死锁检测方法,(,四,),并发程序设计的数学模型,（,1,）,Petri,网模型,（,2,）,时态逻辑模型,（,1,）,Petri,网模型,Petri,网结构和,Petri,网图的定义,标志的定义,作标志的,Petri,网结构和作标志的,Petri,网图的定义,能行的转移的定义,点燃的规则,用作标志的,Petri,网结构和作标志的,Petri,网图模拟并发程序设计的例子，例如，临界区，有界缓冲取，读者和作者，五个哲学家问题等，点燃,45,次,（,2,）时态逻辑模型,模态逻辑的定义,时态逻辑的定义，线性离散时态逻辑的定义，语义模型,用时态逻辑证明,Dekker,算法和,Peterson,算法的安全性和活动性,（五）命名系统,（,1,）在一个系统中有多级标识符，一般至少有两级标识符：,面向机器的标识符和,面向用户的标识符。,（,2,）标识符系统的组成,一个标识符系统由三部分组成：一级或多级标识符的字母表，构成标识符的规则以及映射函数或映射表。在对对象进行重定位、共享、创建、取消等操作时，必须修改相应的映射机构。,