1.6-8

高级操作系统 1. 分布式系统简介 1.6-1.8. 硬件 软件 设计问题 熊焰,yxiong@ustc.edu.cn 黄 文超, huangwc@ustc.edu.cn http://staff.ustc.edu.cn/~huangwc/advancedos 参考书 目 : 分布式操作系统 Distributed Computing: Principles, Algorithms, and Systems

1. 分布式系统简介 1. 分布式系统的诞 生和定义 2. 分布式系统发展的动 力力 3. 分布式系统的 目标 4. 分布式系统的优缺点 5. 计算机 网络与分布式系统的关系 6. 分布式系统硬件 7. 分布式系统软件 8. 分布式系统的设计问题

Flynn 分类 方案 1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 两个重要特征 指令流数量量 Instruction 数据流数量量 Data 分类 SISD, SIMD, MISD, MIMD, 过去 人们曾提出过各种不不同的多 CPU 系统分类 方案, 但还没有 一个得到 广泛采 用 被应 用最多的分类法可能是弗林林 (flynn,1972) 分类法, 尽管它还相当不不完善 弗林林选择了了两个他认为是最本质的特征既指令流数 目和数据流数 目作为分类依据 : 第 一类 : 具有单 一指令流 单 一数据流的计算机称之为 SISD, 从个 人计算机到 大型机, 所有传统的单处理理器器计算机 ( 即只有 一个 CPU) 均属此类 第 二类 : 单指令流 多数据流 SIMD 这 一类是指只有 一个指令单元的处理理器器阵列列 指令单元取 一条指令, 然后控制多个数据单元并 行行地进 行行数据处理理, 每个数据单元均有 自 己的数据 这种机器器对多组数据的重复计算相当有 用, 例例如 64 个独 立向量量的所有元素求和 某些超级计算机也属于 SIMD(757 向量量机 ) 第三类 : 多指令流 单数据流 MISD 目前, 没有 一个已知的计算机属于这 一类 第四类 : 多指令流 多数据流 MIMD 它是 一组独 立计算机的集合, 每 一个独 立计算机都具有程序计数器器 程序以及数据 所有的分布式系统都属于 MIMD 所以, 弗林林分类法分类法对分布式系统来说并 无太 大意义

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 SISD (Single instruction stream, single data stream) von Neumann 体系经典计算机 SIMD (Single instruction stream, multiple data stream) 早期的并 行行计算机 如 Illiac-IV, MPP, CM2, MasPar MP-1 Intel 芯 片 (MMX) 用途 : 向量量运算 矩阵运算

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 MISD (Multiple instruction stream, single data stream) 用途 : 虚拟化 MIMD (Multiple instruction stream, multiple data stream) 分布式系统

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 具有共享存储器器的多处理理器器系统 没有共享存储器器的多计算机系统 两者的区别在于 : 在 一个多处理理器器计算机系统中, 所有 CPU 共享 一个单 一的虚拟地址空间 两者的区别在于 : 在 一个多处理理器器计算机系统中, 所有 CPU 共享 一个单 一的虚拟地址空间 如果 一个 CPU 把值 44 写 入地址 1000 中, 那么, 任何其它 CPU 从地址 1000 读出的值均是 44 而在多计算机系统中, 每台机器器均有它私有的存储器器 如果某个 CPU 把值 44 写 入地址 1000 中, 那么, 另 一个 CPU 从地址 1000 中读出的值将不不是 44 一个多计算机系统例例 子是由 网络连接起来的 一群计算机

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 总线型 是指单 一的主 干线 总线 线缆或其它把所有机器器 连接起来的介质 交换型 由 一个开关来选择信息的下 一条出发线 根据互连 网络结构的不不同, 以上两个分类还可进 一步细分 : 总线型 : 是指单 一的主 干线 总线 线缆或其它把所有机器器连接起来的介质 有线电视便便采 用了了这样的 方案 : 架线公司沿街铺设线缆, 一个分 支线将 用户的电视连接到主 干线上 开关型 ( 交换型 ): 开关型不不像有线电视那样具有单 一的 干线 机器器与机器器之间有专 门的线路路连接 它可以有许多种布线 方式 信息沿着线路路传输 由 一个开关来选择信息的下 一条出发线 世界上的公 用电话系统就是这样组织的

1.6 分布式系统硬件 1.6.1 分布式系统硬件分类 处理理机是紧耦合的 信息从 一台处理理机发向另 一台处理理机的延迟是短暂的且数 据传输率 ( 每秒传输位的数 目 ) 较 高 并 行行系统 机器器是松散耦合的 机器器间发送信息的延迟较 长且数据传输率较低 分布式系统 处理理机是紧耦合的 : 信息从 一台处理理机发向另 一台处理理机的延迟是短暂的且数据传输率 ( 每秒传输位的数 目 ) 较 高, 例例如, 两个在同 一印刷线路路板上由蚀刻在板上的线路路连接在 一起的 CPU 是紧耦合的 机器器是松散耦合的 : 机器器间发送信息的延迟较 长且数据传输率较低, 例例如, 由 一个 2400 位 / 秒的调制解调器器通过电话系统连接的两台计算机 无疑是松散耦合的 一般来说, 紧耦合系统更更多地 用于并 行行系统 ( 用来解决单 一的问题 ) 而中等松散耦合系统 ( 即局域 网 ) 主要 用于分布式系统 ( 用来解决多个相关性不不 大的问题 ) 总之, 多处理理器器系统 比多计算机系统的耦合更更紧密 因为它们能以存储器器读写速度来交换数据, 不不过有些基于光纤的多计算机系统也能以存储器器读写速度来交换数据 尽管 紧耦合 与 松散耦合 的界限并不不是很明确, 但他们仍不不失为有 用的概念

1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 基于总线的多处理理器器系统 由多个连接在 一根公共总线上的 CPU 以及单个存储器器模块 所组成 例例 : 一块 高速的 母板, 在上 面可插 入 CPU 和存储器器条 基于总线的多处理理器器系统是由多个连接在 一根公共总线上的 CPU 以及单个存储器器模块所组成 一个简单的例例 子就是使 用 一块 高速的 母板, 在上 面可插 入 CPU 和存储器器条 一条典型的总线有 32 或 64 条地址线 32 或 64 条数据线以及 32 条或更更多的控制线, 这些线都是并 行行 工作的 为了了从存储器器中读出 一个字,CPU 首先将所需字的地址放到地址总 线上, 然后在适当的控制线上设置 一个信号以表示读 作为响应, 存储器器将对应地址中的内容放到数据线上以便便 CPU 读 入 写的过程与此类似 由于只有 一个存储器器, 如果当 CPU A 往存储器器中写 入 一个字 而后 CPU B 在 一微秒后读出, 则 B 将得到刚写 入的值 这种特性称之为 一致性, 一致性在分布式统中具有 非常重要的作 用 基于总线的多处理理器器存在的问题 : 当有 4-5 个 CPU 时, 通常总线会过载 而造成性能急剧下降 解决 方法是在 CPU 和总线之间加 一个 高速缓存, 如图 1-5 所示 高速缓存保存最常访问的数据 所有存储器器的访问请求均经过缓存 如果所要访问的字在 高速缓存中, 则 高速缓存响应 CPU, 无需进 行行总线请求

1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 概念 : 由于只有 一个存储器器, 如果当 CPU A 往存储器器中写 入 一个字 而后 CPU B 在 一微秒后读出, 则 B 将得到刚写 入的值 这种特性称之为 一致性, 或相关性 (coherent) 基于总线的多处理理器器系统是由多个连接在 一根公共总线上的 CPU 以及单个存储器器模块所组成 一个简单的例例 子就是使 用 一块 高速的 母板, 在上 面可插 入 CPU 和存储器器条 一条典型的总线有 32 或 64 条地址线 32 或 64 条数据线以及 32 条或更更多的控制线, 这些线都是并 行行 工作的 为了了从存储器器中读出 一个字,CPU 首先将所需字的地址放到地址总 线上, 然后在适当的控制线上设置 一个信号以表示读 作为响应, 存储器器将对应地址中的内容放到数据线上以便便 CPU 读 入 写的过程与此类似 由于只有 一个存储器器, 如果当 CPU A 往存储器器中写 入 一个字 而后 CPU B 在 一微秒后读出, 则 B 将得到刚写 入的值 这种特性称之为 一致性, 一致性在分布式统中具有 非常重 要的作 用

1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 问题 : 当有 4-5 个 CPU 时, 通常总线会过载 而造成性能急 剧下降 可选 方案 : 在 CPU 和总线之间加 一个 高速缓存 如果 高速缓存 足够 大, 总线通信量量将会 大幅降低 基于总线的多处理理器器存在的问题 : 当有 4-5 个 CPU 时, 通常总线会过载 而造成性能急剧下降 解决 方法是在 CPU 和总线之间加 一个 高速缓存 高速缓存保存最常访问的 数据 所有存储器器的访问请求均经过缓存 如果所要访问的字在 高速缓存中, 则 高速缓存响应 CPU, 无需进 行行总线请求 如果 高速缓存 足够 大, 那么, 所要访问的字在 高速缓存的可能性即命中率将会很 高, 而每个 CPU 的总线通信量量将会 大幅降低, 这将允许更更多的 CPU 连到总线上 通常 高速缓存 大 小为 64k 到 1M 时, 命中率将达到 90% 以上

高速缓存引发的问题 不不 一致性 1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 使得系统编程变得相当困难 但是, 高速缓存的引 入也带来了了 一个严重的问题, 假设有 A 和 B 两个 CPU, 分别将相同的字读 入到各 自的 高速缓存中 然后 A 重写这个字 当 B 再次读这个字时, 它从其 高 速缓存中得到是以前的值, 而不不是 A 刚刚写 入的那个值 由于 高速缓存的不不 一致性, 使得系统编程变得相当困难

高速缓存引发的问题 1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 一个解决 方法 : 当在 高速缓存中写 入 一个字时, 同时也往存储器器中写 入 称之为 高速缓存写 一个解决办法 : 当在 高速缓存中写 入 一个字时, 同时也往存储器器中写 入 这样的 高速缓存称之为通过 高速缓存写 高速缓存读的成功不不会引起总线通信, 而 高速缓存读的失效以及所有 高速缓存写的成功和失败均会造成总线通信 所有的 高速缓存都 一直监视着总线, 每当 一个 高速缓存发现它的 一个单元在存储器器中对应的单元被写时 它要么从 高速缓存中去掉该单元, 要么 用新值更更新这个 高速缓存单元 这种 高速缓存称为窃听 高速缓存 (snooping cache) 这种设计具有 一致性并对程序员是透明的, 所以, 几乎所有基于总线的多处理理器器都采 用与之相同或相似的结构 采 用这种结构可以在 一个单 一总线上挂接 32 或 64 个 CPU

高速缓存写的实现 1.6 分布式系统硬件 1.6.2 基于总线的多处理理器器 所有的 高速缓存都 一直监视着总线称为窃听 高速缓存 (snooping cache) 每当 一个 高速缓存发现它的 一个单元在存储器器中对应的单元被写时 要么从 高速缓存中去掉该单元, 要么 用新值更更新该单元 一个解决办法 : 当在 高速缓存中写 入 一个字时, 同时也往存储器器中写 入 这样的 高速缓存称之为通过 高速缓存写 高速缓存读的成功不不会引起总线通信, 而 高速缓存读的失效以及所有 高速缓存写的成功和失败均会造成总线通信 所有的 高速缓存都 一直监视着总线, 每当 一个 高速缓存发现它的 一个单元在存储器器中对应的单元被写时 它要么从 高速缓存中去掉该单元, 要么 用新值更更新这个 高速缓存单元 这种 高速缓存称为窃听 高速缓存 (snooping cache) 这种设计具有 一致性并对程序员是透明的, 所以, 几乎所有基于总线的多处理理器器都采 用与之相同或相似的结构 采 用这种结构可以在 一个单 一总线上挂接 32 或 64 个 CPU

1.6 分布式系统硬件 1.6.3 基于开关 ( 交换 ) 的多处理理器器系统 为了了制造 一个超过 64 个处理理器器的多处理理器器系统, 需 要其它的 方法把 CPU 和存储器器连接起来 方法 1: 十字交叉开关 优点 : 多个 CPU 可以同时访问存储模 块 缺点 : 当两个 CPU 要同时访问相同的存储模块时, 它们当中之 一必须等待 n 较 大时, 交叉点的数 目将急剧增 加 为了了制造 一个超过 64 个处理理器器的多处理理器器系统, 需要其它的 方法把 CPU 和存储器器连接起来 一种 方法就是把存储器器分成模块并 用交叉杆 (crossbar) 开关将它们与 CPU 相连接, 如图 1.3(a) 所示 每个 CPU 和每 一个存储模块均由 一个交叉杆开关将其连接 每个交叉点都是 一个由硬件控制开或关的 小电 子交叉点开关 (crosspoint switch), 当 CPU 要访问某个特定的存储模块时, 连接它们的交叉点开关会 立即合上, 允许对存储模块的访问 优点 : 多个 CPU 可以同时访问存储模块 缺点 : 当两个 CPU 要同时访问相同的存储模块时, 它们当中之 一必须等待 如果有 n 个 CPU 和 n 个存储模块 则交叉点开关必须有 n^2 个, 当 n 较 大时, 交叉点的数 目将急剧增加 所以, 人们试图寻找 一个需要更更少开关的开关 网络

1.6 分布式系统硬件 1.6.3 基于开关 ( 交换 ) 的多处理理器器系统 为了了制造 一个超过 64 个处理理器器的多处理理器器系统, 需 要其它的 方法把 CPU 和存储器器连接起来 方法 2: 多级互连 网络 ( 如 Omega 网络 ) 每 一个开关有两个输 入及两个输 出 当正确地设置开关时, 每个 CPU 可以访问任意 一个存储模块 多级互连 网络 (Multi-stage Interconnection Networks, 简称 MINs):An N N MIN consists of several columns(called stages) of switch elements(ses) and links that connect the N outputs from a stage to the N inputs of the next stage in a certain pattern(2 2 SEs are commonly used). 典型的多级互连 网络就是 N N Omega 网络 图是 一个 Omega 网络 这个 网络含有 4 个 2 2 开关, 每 一个开关有两个输 入及两个输出 每个开关都可以设置成通过和交叉两种形式 当正确地设置开关时, 每个 CPU 可以访问任意 一个存储模块 开关设置仅需 几纳秒或更更短的时间

1.6 分布式系统硬件 1.6.3 基于开关 ( 交换 ) 的多处理理器器系统 为了了制造 一个超过 64 个处理理器器的多处理理器器系统, 需 要其它的 方法把 CPU 和存储器器连接起来 方法 2: 多级互连 网络 ( 如 Omega 网络 ) Omega 网络需要 logn 开关级 每级有 N/2 个开关, 总开关数为 (NlogN)/2 大 一般情况即 N 个 CPU 和 N 个存储模块,Omega 网络需要 logn 开关级, 每级有 N/2 个开关, 总开关数为 (NlogN)/2 虽然对于 大 N, 开关总数要 比 N2 少得多, 但仍然相当庞

1.6 分布式系统硬件 1.6.3 基于开关 ( 交换 ) 的多处理理器器系统 为了了制造 一个超过 64 个处理理器器的多处理理器器系统, 需 要其它的 方法把 CPU 和存储器器连接起来 方法 2: 多级互连 网络 ( 如 Omega 网络 ) 问题 : 延时 Omega 网络的问题 : 延迟 --- 例例如, 对于 N=1024, 从 CPU 到存储模块共有 10 个开关级, 再加上数据回来时的 10 个开关级 假设 CPU 是速度为 100MIPS 的现代 RISC 芯 片即指令执 行行时间为 10 纳秒, 那么 一个访问存储模块请求要在 10 纳秒内 走完全部的 20 个开关级即开关时间必须为 500 皮秒 (0.5 纳秒 ) 整个多处理理器器系统要 5120 个 500 皮秒的开关 这需要付出昂贵的代价 总之, 对于基于总线的多处理理器器系统, 即使有窃听 高速缓存, 其总线容量量也会受到最多只能接 64 个 CPU 的限制 超过这个限制就需要 一个开关 网络, 大规模交叉杆开关相当的昂贵, 而 大规模的 Omega 网络不不仅贵 而且慢 所以建造 一个 大型紧耦合且共享存储器器的多处理理器器系统是可 行行的, 但是 比较困难 而且昂贵

1.6 分布式系统硬件 1.6.4 基于总线的多计算机系统 在 一个 无共享存储器器的多计算机系统中 每个 CPU 都与 自 己的局部存储器器直接相连 由于通信量量少, 所以, 不不需要 高速主 干总线 在 一个 无共享存储器器的多计算机系统中 每个 CPU 都与 自 己的局部存储器器直接相连 这 一类系统所涉及的问题是 CPU 间的通讯 由于 CPU 之间的通信量量要 比 CPU 到存储 器器之间的通信量量少 几个数量量级, 所以, 采 用互连 网络 比较合适 图 1-7 中是 一个基于总线的多计算机系统 它的拓拓扑结构与基于总线的多处理理器器很相似 由于通信量量少, 所 以, 不不需要 高速主 干总线, 一个速度较低的 LAN 就 足够了了 因此, 图 1-7 实际上是 LAN 上的 工作站集合 而不不是插在 一个快速总线上的 CPU 集合 (CSMA/CD)

1.6 分布式系统硬件 1.6.5 基于开关 ( 交换 ) 的多计算机系统 两个常 见的拓拓扑结构 网孔 ( 或 网格 ) 和超 立 方体 目前, 人们已提出了了各种不不同的互连 网络 在这些互连 网络中, 每个 CPU 都可以直接访问 自 己的私有存储器器 而拒绝其它 CPU 访问 自 己的私有存储器器 图 1-8 给出了了两个常 见的拓拓扑结构 : 网孔 ( 或 网格 ) 和超 立 方体 网孔 比较规整且易易于布线 最适合那些具有两维性质的问题, 如图论或视觉 一个超 立 方体是 一个 n 维 立 方体 图 1-8(b) 的超 立 方体是四维的 我们可以把它看成是由两个普通的 立 方体所组成 每个 立 方体有 8 个顶点和 12 条边 每个顶点代表 一个 CPU, 每条边表示两个 CPU 之间的连接 两个 立 方体中对应的顶点被连接起来 如果把这个 4 维超 立 方体扩展成 5 维超 立 方体, 则只需将这两个 4 维超 立 方体的对应顶点连接起来即可, 以此类推 对于 一个 n 维的超 立 方体, 每个 CPU 都与其它 n 个 CPU 相连 这样, 布线复杂度将随维数的 大 小成对数增加 只有相邻的 CPU 才直接相连, 许多信息在到达 目的地前必须经过 几个段 这样, 最 长路路径也随维数的 大 小成对数增加 而 网孔的最 长路路径将随 CPU 数 目成平 方根增加 目前, 具有 1024 个 CPU 超级 立 方体的商业性应 用已有多年年 具有 16,384 个 CPU 的超 立 方体也应 用了了 一段时间了了

1.7 分布式系统软件 在分布式系统中, 软件的重要性要远远 高于硬件的重 要性 操作系统划分远不不象硬件那样清晰明了了, 因为, 软件 本身就是不不明确的 尽管如此, 我们仍将根据两个多 CPU 系统的划分分别定义两种软件 ( 这 里里软件指得是操作系统 ) 即松散耦合软件和紧耦合软件 在分布式系统中, 软件的重要性要远远 高于硬件的重要性 呈现在 用户 面前的分布式系统以及 用户对分布式系统的看法很 大 一部分都是取决于操作系统 而不不是硬件 操作系统远不不象硬件那样清晰明了了, 因为, 软件本身就是不不明确的 尽管如此, 我们仍将根据两个多 CPU 系统的划分分别定义两种软件 ( 这 里里软件指得是操作系统 ) 即松散 耦合软件和紧耦合软件 松散耦合软件和紧耦合软件都可运 行行在松散耦合硬件和紧耦合硬件之上

1.7 分布式系统软件 1.7.1 网络操作系统 网络操作系统是运 行行在松散耦合硬件之上的松散耦合软件 它是 用户和 网络之间的 一个接 口 除了了应该具备通常操作系统所应具备的基本功能外 还应该具有联 网功能, 支持 网络体系结构和各种 网络通信协议, 提供 网络互连能 力力, 支持有效可靠安全地数据传输 早期 网络操作系统功能较为简单, 仅提供基本的数据通信 文件和打印服务等 现代 网络操作系统把通信协议作为内置功能来实现 网络操作系统是运 行行在松散耦合硬件之上的松散耦合软件 它是 用户和 网络之间的 一个接 口, 它除了了应该具备通常操作系统所应具备的基本功能外, 还应该具有联 网功能, 支持 网络体系结构和各种 网络通信协议, 提供 网络互连能 力力, 支持有效可靠安全地数据传输 早期 网络操作系统功能较为简单, 仅提供基本的数据通信 文件和打印服务等 随着 网络的规模化和复杂化, 现代 网络的功能不不断扩展, 性能 大幅度提 高, 很多 网络操作系统把通信协议作为内置功能来实现, 提供与局域 网和 广域 网的连接 Linux 网络操作系统的特征 : 硬件独 立性 : 网络操作系统可以运 行行在不不同的 网络硬件上, 可以通过 网桥或路路由器器与别的 网络连接 ; 支持多 用户 : 能同时 支持多个 用户对 网络的访问, 对信息资源提供完全的安全和保护功能 ; 支持 网络实 用程序及其管理理功能 : 系统备份 安全管理理 容错和性能控制 ; 支持多种客户端 : 如 WindowsNT 可以 支持 MS-DOS OS/2 Windows98 Windows for wrokgroup UNIX 等多种客户端, 极 大地 方便便了了 网络 用户的使 用 ;

网络操作系统的特征 : 硬件独 立性 支持多 用户 1.7 分布式系统软件 1.7.1 网络操作系统 支持 网络实 用程序及其管理理功能 支持多种客户端 提供 目录服务 等等 网络操作系统的特征 : 硬件独 立性 : 网络操作系统可以运 行行在不不同的 网络硬件上, 可以通过 网桥或路路由器器与别的 网络连接 ; 支持多 用户 : 能同时 支持多个 用户对 网络的访问, 对信息资源提供完全的安全和保护功能 ; 支持 网络实 用程序及其管理理功能 : 系统备份 安全管理理 容错和性能控制 ; 支持多种客户端 : 如 WindowsNT 可以 支持 MS-DOS OS/2 Windows98 Windows for wrokgroup UNIX 等多种客户端, 极 大地 方便便了了 网络 用户的使 用 ; 提供 目录服务 : 以单 一逻辑的 方式让 用户访问所有 网络服务和资源的技术 ; 支持多种增值服务 : 如 文件服务 打印服务 通信服务 数据库服务 W W W 服务等等 ; 可操作性 : 允许多种操作系统和 厂商的产品共享相同的 网络电缆系统, 且彼此可以连通访问

网络操作系统的三种类型 集中模式 1.7 分布式系统软件 1.7.1 网络操作系统 系统的基本单元是 一台主机和若 干台与主机相连的终端构成 客户 / 服务器器模式 网络中连接许多台计算机, 其中, 一部分计算机称为服务 器器, 而另外 一些计算机称客户机 对等模式 让 网络中的每台计算机同时具有客户和服务器器两种功能 网络操作系统的三种类型 : 集中模式 : 是由分时操作系统加上 网络功能演变 而成的, 系统的基本单元是 一台主机和若 干台与主机相连的终端构成, 把多台主机连接起来就形成了了 网络, 而信息的处理理和控制都是集中的,UNIX 系统是这类系统的典型例例 子 ; 客户 / 服务器器模式 : 网络中连接许多台计算机, 其中, 一部分计算机称为服务器器, 提供 文件 打印 通信 数据库访问等功能, 提供集中的资源管理理和安全控制 而另外 一些计算机称客户机, 它向服务器器请求服务, 如 文件下载和信息打印等 服务器器通常配置 高, 运算能 力力强, 有时还需要专职 网络管理理员维护 客户机与集中式 网络中的终端不不同的是, 客户机有独 立处理理和计算能 力力, 仅在需要某种服务时才向服务器器发出请求 客户服务器器模式在逻辑上是星形结构, 以服务器器为中 心, 服务器器与各客户间采 用点到点通信 方式 对等模式 : 让 网络中的每台计算机同时具有客户和服务器器两种功能, 既可以向其他机器器提供服务, 又可以向其他机器器请求服务, 而 网络中没有中央控制 手段 尽管所有的机器器可以运 行行相同的 网络操作系统, 但这并不不是必须的 如果客户和服务器器运 行行不不同的操作系统, 那么, 对于所有需要交换的信息, 他们 至少在信息的格式及意义上要保持 一致 因此, 每台机器器具有 高度的 自治性并且对系统范围内的要求较少

1.7 分布式系统软件 1.7.1 网络操作系统

1.7 分布式系统软件 1.7.1 网络操作系统 登陆到远程 工作站 rlogin machine 远程拷 贝 文件 rcp machine1:file1 machine2:file2

1.7 分布式系统软件 1.7.2 分布式操作系统 网络操作系统 运 行行在松散耦合硬件上的松散耦合软件 用户能够明显地知道系统有多少个服务器器存在 分布式操作系统 在松散耦合硬件上运 行行 的紧耦合软件 单系统映像 用户不不知道也不不必知道系统有多个台计算机的存在 网络操作系统是运 行行在松散耦合硬件上的松散耦合软件 除了了共享资源以外, 用户能够明显地知道系统有多少个服务器器存在 每台计算机均运 行行 自 己的操作系统, 做主 人所要求做的事 分布式操作系统是在松散耦合 ( 即多计算机 ) 硬件上运 行行紧耦合软件 这样 一个系统给 用户制造了了 一个假象 : 整个计算机 网络就象 一个单 一的分时系统 一样, 而不不是各种机器器的集合 这被称之为单系统映像 分布式操作系统实际上是 一个在 网络计算机集合上运 行行的系统, 整个系统就象 一个单 一的虚拟处理理器器 一样 用户不不知道也不不必知道系统有多个台计算机的存在

1.7 分布式系统软件 1.7.2 分布式操作系统 分布式操作系统的特征 : 有 一个统 一的全局进程间通信机制来保证每 一个进程可以与任意 一个其它进程进 行行联系 有 一个全局保护 方案 所有机器器上的进程管理理必须相同 所有机器器上有统 一的 一组系统调 用, 并且这些调 用必 须适应分布式环境 分布式操作系统的特征 : 有 一个统 一的全局进程间通信机制来保证每 一个进程可以与任意 一个其它进程进 行行联系 不不允许在不不同机器器上采 用不不同的通信机制或者对本地通信与远程通信采 用不不同的通信机制 有 一个全局保护 方案 仅把访问控制列列表和 UNIX 的保护位以及各种能 力力堆砌在 一起是形成不不了了单 一的系统映像的 所有机器器上的进程管理理必须相同即进程的创建 撤消 运 行行和停 止不不能因机器器 而异 所有机器器上有统 一的 一组系统调 用, 并且这些调 用必须适应分布式环境

1.7 分布式系统软件 1.7.2 分布式操作系统 分布式操作系统的特征 : 所有机器器上的 文件系统也必须 一样 除了了受保护及安全性限制以外, 每个 文件应在任 何 一个地 方都是可访问的 系统中所有的 CPU 必须运 行行相同内核 需要 一个全局的 文件系统 每个内核对 自 己的局部资源应有较 大的控制权 所有机器器上的 文件系统也必须 一样 在某些地 方 文件 长度有 11 个字符的限制 而在其它 一些地 方则没有, 这种情况是不不允许出现的 除了了受保护及安全性限制以外, 每个 文件应在任何 一个地 方都是可访问的 系统中所有的 CPU 必须运 行行相同内核 这样做 比较容易易协调全局活动 需要 一个全局的 文件系统 每个内核对 自 己的局部资源应有较 大的控制权 例例如, 由于没有共享存储器器, 应该允许每个内核来管理理它 自 己的存储器器 再如, 如果某个机器器上需要换 页, 那么, 应由该机器器 CPU 的内核 自 己来进 行行换 页 整个系统完全没有必要集中这个权 力力 同样, 如果在某个 CPU 上有多个进程在运 行行, 那么, 也应该在该 CPU 上进 行行进程调度

1.7 分布式系统软件 1.7.2 多处理理器器分时操作系统 多处理理器器分时操作系统是在紧耦合硬件上运 行行的紧 耦合软件 典型紧耦合硬件是多处理理器器计算机 由于整个设计可以集中化, 所以, 多处理理器器系统的 实现 比较容易易 但是, 它需要 一个单 一的运 行行队列列, 即系统中所有 进程的列列表 多处理理器器分时操作系统是在紧耦合硬件上运 行行的紧耦合软件 典型紧耦合硬件是多处理理器器计算机 它象 UNIX 分时系统那样运 行行, 使 用多个 CPU 而不不是单个 CPU 从 用户的观点来看,32 个 30-MIPS CPU 的多处理理器器系统与单个的 960-MIPS 的 CPU 没什什么两样 ( 这就是前 面所讨论的单 一系统映像 ) 此外, 由于整个设计可以集中化, 所以, 多处理理器器系统的实现 比较容易易 但是, 它需要 一个单 一的运 行行队列列即系统中所有进程的列列表, 表中的进程是 非阻塞的并处于就绪状态, 运 行行队列列是共享存储器器中的 一个数据结构 让我们来看 一看图 1-11 中的 一个例例 子

1.7 分布式系统软件 1.7.2 多处理理器器分时操作系统 调度程序作为 一个临界区来运 行行 该例例 子中有 3 个 CPU 和 5 个进程, 这五个进程均在共享存储器器中, 其中三个正在运 行行 : 进程 A 在 CPU 1 上, 进程 B 在 CPU 2, 进程 C 在 CPU 3 其它两个进程 D 和 E 在运 行行队列列中等待调度 假设进程 B 由于 I/O 而阻塞或 用完了了时间 片 CPU 2 将它挂起, 并调度另 一个进程投 入运 行行 通常 CPU 2 将执 行行位于共享存储器器中的操作系统代码 在保存所有 B 的寄存器器之后, 它将进 入 一个临界区运 行行 一个调度程序调度另 一个进程投 入运 行行 由于调度程序作为 一个临界区来运 行行以防 止两个 CPU 调度同 一个进程投 入运 行行, 所以, 必须采 用互斥机制 该例例 子中有 3 个 CPU 和 5 个进程, 这五个进程均在共享存储器器中, 其中三个正在运 行行 : 进程 A 在 CPU 1 上, 进程 B 在 CPU 2, 进程 C 在 CPU 3 其它两个进程 D 和 E 在运 行行队列列中等待调度 假设进程 B 由于 I/O 而阻塞或 用完了了时间 片 CPU 2 将它挂起, 并调度另 一个进程投 入运 行行 通常 CPU 2 将执 行行位于共享存储器器中的操作系统代码 在保存所有 B 的寄存器器之后, 它将进 入 一个临界区运 行行 一个调度程序调度另 一个进程投 入运 行行 由于调度程序作为 一个临界区来运 行行以防 止两个 CPU 调度同 一个进程投 入运 行行, 所以, 必须采 用互斥机制 一旦 CPU 2 获得对运 行行队列列的互斥访问权, 则它移去第 一个项 D, 退出临界区并开始执 行行D 刚开始时执 行行速度较慢, 因为 CPU 2 的 高速缓存中装有共享存储器器中进程 B 的内容 但稍后将被 D 的代码和数据所覆盖, 因此, 执 行行速度将会加快 由于所有的 CPU 都没有局部存储器器, 程序和数据都放在全局共享存储器器中, 所以, 进程在哪个 CPU 上运 行行都 无关紧要 如果 一个运 行行时间较 长的进程在结束前多次被调度, 那么, 平均来说, 它在每个 CPU 上运 行行的时间是差不不多的 CPU 的选择所产 生的影响就是性能好坏 例例如, 如果所有的 CPU 都在等待 I/O 而空闲, 此时有某个进程就绪, 那么应该将该进程分配给它最近使 用的那个 CPU( 假设其它进程 一直没有使 用过这个 CPU) 这样分配可以提 高 一部分性能 原因是该进程在共享存储器器中的内容已存储在这个被分配 CPU 的 高速缓存中 如果在 一个多处理理器器上的进程由于 I/O 而阻塞, 那么, 操作系统或者把它挂起或者让它等待 如果这个 I/O 可以在 小于 一个进程切换时间内完成, 那么, 让进程等待是 比较合适的 某些系统的做法是让该进程继续占 用CPU 几个毫秒时间以希望 I/O 能很快结束, 如果在时间 片结束之前 I/O 还未结束, 则进 行行进程的切换 如果 大多数临

1.8 分布式系统的设计问题 透明性 灵活性 可靠性 性能 可扩放性 ( 可伸缩性 )

1.8 分布式系统的设计问题 1.8.1 透明性 系统设计者如何使 用户将机器器的集合看成是 一个 老老式的分时系统 实现这个 目标的系统通常被称为是透明的系统 透明性可以在两个不不同层次上实现 : 在 高层次上的实现 : 将分布性对 用户透明 如 make, 对 用户 而 言, 性能变好了了 在低层次上的实现 : 是对程序员的透明 系统调 用接 口可以设计成使多个处理理器器不不可 见 系统设计者如何使 用户将机器器的集合看成是 一个 老老式的分时系统 实现这个 目标的系统通常被称为是透明的系统 透明性可以在两个不不同层次上实现 : 在 高层次上的实现 : 将分布性对 用户透明 例例如, 当 一个 UNIX 用户键 入make 来重新编译 一个 目录中的许多 文件时, 它不不必知道所有 文件的编译是在不不同机器器上并 行行完成的, 也不不必知道该编译使 用了了多少个 文件服务器器 对 用户来说唯 一不不同的是系统的性能变好了了 命令由终端发出, 结果返回终端, 整个分布式系统看起来象 一个单处理理器器系统 在低层次上的实现 : 是对程序员的透明, 尽管 比较困难, 但也不不是做不不到的 换句句话说, 系统调 用接 口可以设计成使多个处理理器器不不可 见 然 而, 对程序员的透明 比对终端 用户的透明要难得多 考虑 一个由 工作站构成的分布式系统 每台 工作站均运 行行某个标准的操作系统 如果远程 文件的访问是通过显式地建 立 网络连接到远程服务器器上并发送信息给远程服务器器来实现的, 那么, 这样的 一个系统是不不透明的 因为远程 文件与本地 文件的访问是不不 一样的 程序员知道它必须同系统中多个机器器打交道, 这是透明性所不不允许的

1.8 分布式系统的设计问题 1.8.1 透明性 透明性的概念可以表现在分布式系统的许多 方 面 : 位置透明 迁移透明 : 资源可以 自由地移动 而名字不不 用改变 复制透明性 : 用户不不知道有多少个副本存在 并发透明 : 多个 用户可以 自动并发地共享资源 并 行行透明 : 程序可以在多台计算机上并 行行地执 行行 而 无须 用 户 干预 透明性的概念可以表现在分布式系统的许多 方 面 : 位置透明 : 是指在 一个分布式系统中, 用户不不知道软硬件资源如 CPU 打印机 文件及数据库的位置 资源的名字不不能含有资源的位置 迁移透明 : 是指资源可以 自由地移动 而名字不不 用改变 复制透明性 : 用户不不知道有多少个副本存在 并发透明 : 多个 用户可以 自动并发地共享资源 并 行行透明 : 程序可以在多台计算机上并 行行地执 行行 而 无须 用户 干预 在透明性中, 最复杂的是并 行行透明性, 即分布式系统在 用户看来是 一个传统的单处理理器器分时系统 如果 一个程序员知道他所 用的分布式系统有 1000 台计算机并且要使 用其中 一部分来运 行行计算程序, 那么, 对他来说并 行行是不不透明的 解决的办法是让编译器器 运 行行系统和操作系统来合理理地利利 用多个计算机的并 行行性 而不不是让 用户 自已来安排 不不幸的是 目前的 水平要达到这 一点还差得很远 实际上, 目前程序员要 用多个计算机来解决 一个问题, 那么他只能 自已编程显示地使 用多个计算机的并 行行性 因此, 解决并 行行透明性是当前分布式系统设计者的主要 工作

1.8 分布式系统的设计问题 1.8.2 灵活性 分布式操作系统的结构, 目前存在着两派 大内核 : 认为每台机器器应运 行行 一个传统的内核, 由内核提供 大多数的 服务 微内核 : 认为内核所提供的服务应尽可能的少, 大量量操作系统服务可 从 用户级服务器器上获得 第 二个重要设计问题是灵活性 对于分布式操作系统的结构, 目前存在着两派 一派认为每台机器器应运 行行 一个传统的内核, 由内核提供 大多数的服务 另 一派认为内核所提 供的服务应尽可能的少, 大量量操作系统服务可从 用户级服务器器上获得 我们将它们分别被称之为 大内核和微内核, 如图所示

1.8 分布式系统的设计问题 1.8.2 灵活性 分布式操作系统的结构, 目前存在着两派 大内核 : 大多数分布式系统 ( 辅以 网络设备和集成的远程 服务 ) 微内核 : 因为微内核提供的服务极少, 所以更更加灵活 目前 大多数分布式系统都是采 用 大内核并辅以 网络设备和集成的远程服务 大多数系统调 用由内核执 行行所需的功能并将结果返回给 用户进程 这些分布式系统基本上都是 UNIX 的扩展, 因为 UNIX 本身具有 一个 大内核 大多数采 用微内核的分布式操作系统都必须从头开始设计 因为微内核提供的服务极少, 所以更更加灵活

1.8 分布式系统的设计问题 1.8.2 灵活性 微内核主要提供下 面四个最基本的服务 进程间通信机制 存储管理理 低层进程管理理及调度 低层输 入输出 微内核不不提供 文件系统 目录系统 全部的进程管理理 大量量系统调 用处理理 1. 进程间通信机制 ; 2. 存储管理理 ; 3. 低层进程管理理及调度 ; 4. 低层输 入输出 微内核不不提供 文件系统 目录系统 全部的进程管理理以及 大量量系统调 用处理理 它只提供这 几个最基本服务的原因是这些服务若在别处提供会很困难或者代价较 高 另 一个原 因是让微内核尽可能的 小

1.8 分布式系统的设计问题 1.8.2 灵活性 微内核的优点 : 高度模块化 : 操作系统服务通常由 用户级服务器器 来提供 容易易实现安装及调试新的服务 大内核的优点 : 性能好? 微内核的优点 : 高度模块化 : 操作系统服务通常由 用户级服务器器来提供, 例例如, 为了了查询名字 读取 文件或获得其它服务, 用户必须向指定的服务器器发送 一个消息, 该服务器器完成服务后返回结果 容易易实现安装及调试新的服务 : 增加或改变某项服务 无需关闭系统和引导新内核 正是由于这种增加 删除及修改服务的能 力力赋予了了内核极 大的灵活性 : 操作系统服务通常由 用户级服务器器来提供 大内核的 一个优点 : 性能好 由内核完成所需服务可能 比向远程服务器器发送消息要快的多 实际上 大内核的这种优点并不不存在 主要原因是在 LAN 上发送 一个消息和接收 一 个应答所需的时间通常可忽略略不不计 因此, 具有微内核的分布式系统 方案将逐步占主导地位, 大内核将最终消失或发展成微内核

1.8 分布式系统的设计问题 1.8.3 可靠性 在分布式系统中, 当某台机器器出故障时, 其它机器器可接 替它的 工作 可靠性包含着多个 方 面 : 可 用性 : 指系统可 用时间所占的 比例例 ( 应对各种故障 ) 安全性 : 文件与其它资源必须被保护起来以免 非授权 的使 用 容错 : 服务器器崩溃后, 用户正常 工作 信息恢复 在分布式系统中, 当某台机器器出故障时, 其它机器器可接替它的 工作 整个系统的可靠性是每台计算机可靠性的布尔或 例例如, 有四台 文件服务器器, 每台不不出错的概率为 0.95, 则全部同时出故障的概率是 0.05^4 =0.000006, 所以, 至少有 一台服务器器在 工作的概率是 0.999994 比任何单服务器器要好得多 上述的结果是理理论上的 实际上, 由于 目前分布式系统主要依靠 一些正常 工作的特定服务器器, 所以, 它正常 工作的概率更更多的是布尔与 而不不是布尔或 可靠性包含着多个 方 面 : 可 用性 : 指系统可 用时间所占的 比例例 可 用性可以通过设计来提 高 而不不是采 用 大量量关键部件同时 工作来获得 改善可 用性的办法是冗余 : 重要的硬件 软件应有备份, 以便便当其中 一个发 生故障时其它备份可以接替它继续 工作 一个 高度可靠的系统必须是 高度可 用的, 但仅有这 一点还不不够, 交付给系统的数据决不不能丢失或被窜改 如果 一个 文件在多个服务器器上冗余存储, 那么, 其所有的拷 贝必须保持 一致 一般来说, 保存的拷 贝越多, 可 用性越 高, 但发 生不不 一致性的可能性越 大 安全性 : 文件与其它资源必须被保护起来以免 非授权的使 用, 虽然在单处理理器器系统中也有这个问题, 但是在分布式系统中情况更更为严重 在分布式系统中, 当服务器器收到 一 条请求消息时它没有 一个简单的 方法来确定该消息是谁发来的话 那么, 该消息中的名字域或标识域都是不不可信的, 因为发送者可能在作弊 在这种情况下需要 非常的谨慎 容错 : 如果 一台服务器器崩溃后迅速地重启动, 服务器器的崩溃有可能引起 用户 无法 工作 如果服务器器中含有重要的 用户后继活动信息, 那么, 信息的恢复将 十分重要 然 而, 信息的恢复是相当困难的

1.8 分布式系统的设计问题 1.8.4 性能 度量量性能的 方法 响应时间 吞吐率 利利 用率 网络容量量消耗 性能也是 一个重要的设计问题 建 立 一个透明 灵活 可靠但 非常慢的分布式系统并不不能给 用户带来任何好处 特别是, 在 一个分布式系统上运 行行 一个应 用程序不不应 比在单个处理理器器上运 行行该程序慢 遗憾地是, 这说起来容易易 而做起来难 度量量性能的 方法 : 响应时间 : 吞吐率 : 利利 用率 : 网络容量量消耗 :

1.8 分布式系统的设计问题 1.8.4 性能 提升性能的 手段 减少通信量量 考虑计算粒度 减少通信量量 : 通常, 通信是相当慢的 为了了使性能最佳化, 人们常常不不得不不尽可能少的发送消息 虽然提 高性能的最好 方法是让多个处理理器器并 行行地运 行行应 用程序, 但这样做需要发送 大量量的消息 考虑计算粒度 : 在远程机器器上运 行行 一个 小的计算例例如两个整数相加是不不值得的 因为通信开销远远超过了了节省下来的 几个 CPU 周期 另 一 方 面, 在远程机器器上执 行行 一个计算时间较 长的作业也不不值得 一般来说, 对于那些具有许多 小计算的任务, 特别是那些 小计算之间需要 高度交互的作业, 如果让其在通信速度相对较慢的分布式系统上运 行行, 那么, 系统的性能就 比较差 我们将这类作业称之为具有细粒度的并 行行性 另 一 方 面, 那些具有 大量量 大计算 交互率低以及数据少的作业 ( 我们将其称之为具有粗粒度的并 行行性 ) 比较适合在分布式系统上运 行行

1.8 分布式系统的设计问题 1.8.5 可扩放性 ( 可伸缩性 ) 目前, 大多数分布式系统都有 几百个 CPU 未来的系统其 CPU 的数 目将会变得越来越 大 那么, 一个适 用于 200 台机器器的分布式算法对 200,000,000 台来说不不 一定适合