分布式操作系统复习大纲 （一）分布式操作系统（0）分布式操作系统的定义（1）分布式系统的体系结构类型（2）构造分布式操作系统的途径（3）分布式操作系统的层次结构（4）多机，网络和分布式操作系统间差别（5）透明性(Transparency)意义（6）分布式计算机系统的资源管理（7）分布式操作系统的同步算法（0）分布式操作系统的定义 文献中已经给出分布式系统的各种定义， 没有一个是满意的并且没有一个为其他所 同意。为此，给出一个松散的特征就够了 。 Tanenbaum给出如下定义： A distributed system is a collection of A distributed system is a collection of independent computers that appears independent computers that appears to its user as a single coherent to its user as a single coherent system.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(aa)，因一 事件不可能它自身之前发生。 时钟（clock）条件的定义： 对系统中的任何事件a和b，若a b，则 LC(a)必须小于LC(b)。 系统的逻辑时钟的定义： 系统的逻辑时钟（Logic Clock简记为LC ）是满足时钟条件的系统事件集合到非负 整数的映射。 当事件e 进程Pi时， LC(e)= LCi(e)。 事件e的时间戳的定义： 称事件e的逻辑时钟值LC(e)为事件e的时 间戳（Time Stamp简记为TS）。 全序先于（）关系的定义：我们称进程pi中的事件a先于进程pj中的事件 b(以a b表示) 当且仅当 LCi (a) 0) IR2如果进程Pi的事件a是发送消息m事件 ，则消息m被赋予一个向量时间戳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是系统中场点的个数。一致的全局状态、不一致的全局状态 、无过渡的全局状态和强一致的全局状 态的定义及例子： 一个全局状态 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）存储一致性（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）标识符系统的组成一个标识符系统由三部分组成：一级或多级标识 符的字母表，构成标识符的规则以及映射函数 或映射表。在对对象进行重定位、共享、创建 、取消等操作时，必须修改相应的映射机构。