分布式操作系统复习大纲

在全面复习的基础上，注意掌握下列内容

（一）分布式操作系统

（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)意义

(6)分布式计算机系统的资源管理

⑴从单个资源与多个管理者的相互关系

 全集中管理方式 即专制(autocratic)管理

 功能分布管理方式即分担管理或分割(partitioned)管理

 浮动管理方式即 轮流(successive)管理

 全分散管理方式即 民主(democratic)管理

⑵从多个资源与多个管理者的相互关系

①集中:所有资源属一个管理者管理。 透明性 描述

访问Access 隐藏数据表示中的差异以及如何访问资源

位置Location 隐藏一个资源位于何处

迁移Migration 隐藏一个资源可能移到另外位置

浮动Relocation 隐藏在使用时一个资源可能移到另外位置

复制Replication 隐藏一个资源被复制

并发Concurrency 隐藏一个资源可能被若干竞争用户共享

失效Failure 隐藏一个资源的失效和恢复

存留Persistence 隐藏是否一个（软件）资源在内存或在磁盘上

②分管：每一资源只属一个管理者管理。

③部分管理：每一资源属于若干管理者管理。

④合管：每一资源属于全部管理者共同管理。

⑶从实用的角度

⑷分布式计算机系统的资源管理的算法

①招标（投标）算法

②回声算法

③由近及远算法

（7）分布式操作系统的同步算法

⑴偏序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  进程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)，且pipj，其中关系“”是进程的一个任意偏序。

实现关系“”的一个简单方法是给系统中每个进程赋以一个唯一的进程号，且规定：若i < j，则pi  pj。

a  b定义了一个全序关系。

⑹向量时钟的定义和向量时钟的实现规则以及例子：

 设n为分布式系统中进程个数，每个进程Pi装配一个向量时钟VCi[1, n]，它是一个长度为n的向量。可以把它想象为一个函数，赋给任何事件a一个向量VCi(a)。  VCi的第i个分量VCi[i]对应于Pi自己的逻辑时间，即Pi的内部事件计数。 VCi[j]，j≠i是Pi对Pj逻辑时间最佳猜测。更具体讲，在任何时间点，VCi的第j个分量VCi[j]指示在Pi当前时间点“发生之前HB”在Pj

最近事件出现}{}{非负整数集合事件集合LC的逻辑时间，即进程Pj中在因果关系上处于当前Pi之前的事件计数。

[IR1]向量时钟VCi，在进程Pi的任何两个相继事件之间被增加。

VCi[i] := VCi[i] + d (d>0)

[IR2]如果进程Pi的事件a是发送消息m事件，则消息m被赋予一个向量时间戳tm= VCi(a)；进程Pj接收同样消息m时VCj作如下修改：

kVCj[k] := max(VCj[k], tm[k]) 向量时钟例子

在向量时钟系统中a→b iff vta < vtb

⑺集中式互斥算法

⑻分布式算法（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是系统中场点的个数。

⒁一致的全局状态、不一致的全局状态、无过渡的全局状态和强一致的全局状态的定义及例子：

（二）分布式共享内存

（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）分布式死锁的策略

四个策略被用来处理死锁：

⑴鸵鸟(ostirch)算法：忽略死锁问题。

⑵检测和恢复(detection and recovery)：允许死锁出现，检测并试图恢复之。

⑶预防(prevention)：静态地使死锁结构上成为不可能。

⑷避免(avoidance)：由仔细地分配资源算法避免死锁。

（3）利用时间戳预防死锁方法

⑴等-死（wait-die）方法

⑵因伤（wound-wait）等待 （4）死锁检测方法

 集中式死锁检测方式

 层次式死锁检测方法

 其它分布式方法Chandy-Misra-Haas算法

 分布式事务处理死锁检测方法

(四)并发程序设计的数学模型

（1） Petri网模型

⑴Petri网结构和Petri网图的定义

⑵标志的定义

⑶作标志的Petri网结构和作标志的Petri网图的定义

⑷能行的转移的定义

⑸点燃的规则

⑹用作标志的Petri网结构和作标志的Petri网图模拟并发程序设计的例子，例如，临界区，有界缓冲取，读者和作者，五个哲学家问题等，点燃4~5次

（2）时态逻辑模型

⑴模态逻辑的定义

⑵时态逻辑的定义，线性离散时态逻辑的定义，语义模型

⑶用时态逻辑证明Dekker算法和Peterson算法的安全性和活动性

（五）命名系统

（1）在一个系统中有多级标识符，一般至少有两级标识符：

面向机器的标识符和 面向用户的标识符。

（2）标识符系统的组成

一个标识符系统由三部分组成：一级或多级标识符的字母表，构成标识符的规则以及映射函数或映射表。在对对象进行重定位、共享、创建、取消等操作时，必须修改相应的映射机构。