《分布式操作系统复习大纲.ppt》由会员分享，可在线阅读，更多相关《分布式操作系统复习大纲.ppt（47页珍藏版）》请在三一办公上搜索。
1、分布式操作系统复习大纲,（一）分布式操作系统,（0）分布式操作系统的定义（1）分布式系统的体系结构类型（2）构造分布式操作系统的途径（3）分布式操作系统的层次结构（4）多机，网络和分布式操作系统间差别（5）透明性(Transparency)意义（6）分布式计算机系统的资源管理（7）分布式操作系统的同步算法,（0）分布式操作系统的定义,文献中已经给出分布式系统的各种定义，没有一个是满意的并且没有一个为其他所同意。为此，给出一个松散的特征就够了。Tanenbaum给出如下定义：A distributed system is a collection of independent computers
2、 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）分布式操作系统的层次结构,一个
3、分布式操作系统大致可分成四层，由内向外依次是：执行层；进程通信层；服务支持层；用户接口层。,（4）多机、网络和分布式操作系统间差别,（5）透明性(Transparency)意义,（6）分布式计算机系统的资源管理,从单个资源与多个管理者的相互关系从多个资源与多个管理者的相互关系从实用的角度分布式计算机系统的资源管理的算法,从单个资源与多个管理者的相互关系,全集中管理方式 即专制(autocratic)管理功能分布管理方式即分担管理或分割(partitioned)管理浮动管理方式即 轮流(successive)管理全分散管理方式即 民主(democratic)管理,从多个资源与多个管理者的相互关系
4、,集中:所有资源属一个管理者管理。分管：每一资源只属一个管理者管理。部分管理：每一资源属于若干管理者管理。合管：每一资源属于全部管理者共同管理。,从实用的角度,分布式计算机系统的资源管理的算法,招标（投标）算法回声算法由近及远算法,（7）分布式操作系统的同步算法,偏序Happened-Before关系(筒称HB)的定义时钟（clock）条件的定义系统的逻辑时钟的定义事件e的时间戳的定义全序先于（）关系的定义向量时钟的定义和向量时钟的实现规则以及例子,（7）分布式操作系统的同步算法,集中式互斥算法分布式算法（Lamport算法）分布式算法（Ricart-Agrawala算法）令牌算法欺负（霸主B
5、ully）算法局部状态的定义全局状态的定义一致的全局状态、不一致的全局状态、无过渡的全局状态和强一致的全局状态的定义及例子,偏序Happened-Before关系(筒称HB)的定义：,a b若a和b是同一进程中的两个事件，且a在b前发生；或者，若a是一进程中发送消息的事件，b是另一进程中接收同一消息的事件。该关系是传递的，即若a b且b c，则有a c。该关系是非自反的，即a(aa)，因一事件不可能它自身之前发生。,时钟（clock）条件的定义：,对系统中的任何事件a和b，若a b，则LC(a)必须小于LC(b)。,系统的逻辑时钟的定义：,系统的逻辑时钟（Logic Clock简记为LC）是满
6、足时钟条件的系统事件集合到非负整数的映射。当事件e 进程Pi时，LC(e)=LCi(e)。,事件e的时间戳的定义：,称事件e的逻辑时钟值LC(e)为事件e的时间戳（Time Stamp简记为TS）。,全序先于（）关系的定义：,我们称进程pi中的事件a先于进程pj中的事件b(以a b表示)当且仅当LCi(a)LCj(b)；或LCi(a)=LCj(b)，且pipj，其中关系“”是进程的一个任意偏序。实现关系“”的一个简单方法是给系统中每个进程赋以一个唯一的进程号，且规定：若i j，则pi pj。a b定义了一个全序关系。,向量时钟的定义和向量时钟的实现规则以及例子：,设n为分布式系统中进程个数，每
7、个进程Pi装配一个向量时钟VCi1,n，它是一个长度为n的向量。可以把它想象为一个函数，赋给任何事件a一个向量VCi(a)。VCi的第i个分量VCii对应于Pi自己的逻辑时间，即Pi的内部事件计数。VCij，ji是Pi对Pj逻辑时间最佳猜测。更具体讲，在任何时间点，VCi的第j个分量VCij指示在Pi当前时间点“发生之前HB”在Pj最近事件出现的逻辑时间，即进程Pj中在因果关系上处于当前Pi之前的事件计数。,向量时钟的实现规则,IR1向量时钟VCi，在进程Pi的任何两个相继事件之间被增加。VCi i:=VCi i+d(d0)IR2如果进程Pi的事件a是发送消息m事件，则消息m被赋予一个向量时间
8、戳tm=VCi(a)；进程Pj接收同样消息m时VCj作如下修改：kVCj k:=max(VCj k,tmk),向量时钟例子,集中式互斥算法,分布式算法（Lamport算法）,分布式算法（Ricart-Agrawala算法）,令牌算法,选举算法,欺负（霸主Bully）算法,局部状态的定义：,transit(LSi,LSj)=mij|send(mij)LSi rec(mij)LSj inconsistent(LSi,LSj)=mij|send(mij)LSi rec(mij)LSj,全局状态的定义：,一个系统的全局状态GS是一个它的所有场点的局部状态集合；即GS=LS1,LS2,.,LSn其中n是
9、系统中场点的个数。,一致的全局状态、不一致的全局状态、无过渡的全局状态和强一致的全局状态的定义及例子：,一个全局状态GS=LS1,LS2,.,LSn是一致的(consistent)当且仅当1 i n1j n(inconsistent(LSi,LSj)=)一个全局状态是无过渡的(transitless)，当且仅当1 i n1j n(transit(LSi,LSj)=)因此，在一个无过渡的全局状态中，所有通信通道均为空。如果一个全局状态是一致的和无过渡的，则称为强一致的(strongly consistent)。,例子,（二）分布式共享内存,（1）体系结构和动力（2）实现分布式共享内存的算法（3）
10、存储一致性（4）一致性协议,（1）体系结构和动力,（2）实现分布式共享内存的算法,中央服务器(Central-Server)算法迁移算法读复制(Read-Replicatin)算法完全复制算法,（3）存储一致性,严格一致性（Strict Consistency）顺序的一致性(Sequential consistency)因果一致性一般一致性(General Consistency)处理机一致性(Processor consistency)管道（PRAM）一致性弱一致性(Weak consistency)释放一致性(Release consistency)入口一致性(Release consis
11、tency),（4）一致性协议。,写-使无效协议和写更新协议,（三）分布式系统中的死锁,（1）死锁和饥饿的定义（2）分布式死锁的策略（3）利用时间戳预防死锁方法（4）死锁检测方法,（1）死锁和饥饿的定义,（2）分布式死锁的策略,四个策略被用来处理死锁：鸵鸟(ostirch)算法：忽略死锁问题。检测和恢复(detection and recovery)：允许死锁出现，检测并试图恢复之。预防(prevention)：静态地使死锁结构上成为不可能。避免(avoidance)：由仔细地分配资源算法避免死锁。,（3）利用时间戳预防死锁方法,等-死（wait-die）方法因伤（wound-wait）等待,
12、（4）死锁检测方法,集中式死锁检测方式层次式死锁检测方法其它分布式方法Chandy-Misra-Haas算法分布式事务处理死锁检测方法,(四)并发程序设计的数学模型,（1）Petri网模型（2）时态逻辑模型,（1）Petri网模型,Petri网结构和Petri网图的定义标志的定义作标志的Petri网结构和作标志的Petri网图的定义能行的转移的定义点燃的规则用作标志的Petri网结构和作标志的Petri网图模拟并发程序设计的例子，例如，临界区，有界缓冲取，读者和作者，五个哲学家问题等，点燃45次,（2）时态逻辑模型,模态逻辑的定义时态逻辑的定义，线性离散时态逻辑的定义，语义模型用时态逻辑证明Dekker算法和Peterson算法的安全性和活动性,（五）命名系统,（1）在一个系统中有多级标识符，一般至少有两级标识符：面向机器的标识符和面向用户的标识符。（2）标识符系统的组成一个标识符系统由三部分组成：一级或多级标识符的字母表，构成标识符的规则以及映射函数或映射表。在对对象进行重定位、共享、创建、取消等操作时，必须修改相应的映射机构。,
